読者です 読者をやめる 読者になる 読者になる

最近Rails newをカスタマイズしてます

my_rails_template」という、Rails newするときのテンプレートを作っていっています。その過程で、ジェネレータ系のプラグインも書いたりしてます。ジェネレータ書くまで知らなかったのですが、ジェネレータxxxがあったとしてRails g xxx yyyで生成したものはRails d xxx yyyで削除することができるんですね。生成も削除も同じジェネレータのファイルで管理されているのですが、生成するときと、削除するときで、処理を分岐することもできます。Rails newするとユーザー登録機能まで付けてくれるテンプレート書きました。とは言っても、これは全部決めつけで生成しているので、今のところ作ったRailsプロジェクトをgitでクローンしてきたのと差はありません。

精霊の箱1章の面倒な計算について

はじめに

精霊の箱 上: チューリングマシンをめぐる冒険』の1章でガレットが夕方からやった計算についてまとめておきます。2文字、像に書かれた塔文字の修正された後があり、そこには2通りの文字があるので、2 ** 2の4通りの可能性がありますが、1つは既に誤りであることが分かっている状況です。直して欲しいと主人には頼まれていますが、どのような動作が正しいのか教えて貰えない状況だったので、残りの3つの可能性を全て調べて、一番望ましい動作をする場合を見ないといけなくなりました。1週間のうちの6日までの金貨(0で表現)、と銅貨(1で表現)のならび方は2 ** 6の64通りあります。ガレットは夕方から寝るまでに、次のようになることを確かめました。

1

f:id:nabeyang:20170420082423p:plain この場合が一番厄介です。どんな動作するんですかと言うと、本で言うところの11->00->は普通のプログラミング言語で使える正規表現で言うところの1と0と同じ動作なのでこれに置き換え、1<-は貧者が銅貨を置く動作で、これを¥pとし、0<-は富者が金貨を置く動作で、これを¥rと書くことにします。この設計図の動作を正規表現で書くと次のようになります。

(0|(1(1|0)))*(¥r|(1¥p))

次の表が週の最後の日に像たちがどのように動作をするのかの一覧になります。INが週の最後の日までに置かれた硬貨の配置、OUTが像が動作したあとの硬貨の配置になります。残りの場合の動作についても、設計図とそれに対応する正規表現と表だけ載せております。

INOUT
"000000 ""0000000"
"000001 ""0000011"
"000010 ""0000100"
"000011 ""0000110"
"000100 ""0001000"
"000101 ""0001011"
"000110 ""0001100"
"000111 ""0001111"
"001000 ""0010000"
"001001 ""0010011"
"001010 ""0010100"
"001011 ""0010110"
"001100 ""0011000"
"001101 ""0011011"
"001110 ""0011100"
"001111 ""0011110"
"010000 ""0100000"
"010001 ""0100011"
"010010 ""0100100"
"010011 ""0100110"
"010100 ""0101000"
"010101 ""0101011"
"010110 ""0101100"
"010111 ""0101111"
"011000 ""0110000"
"011001 ""0110011"
"011010 ""0110100"
"011011 ""0110110"
"011100 ""0111000"
"011101 ""0111011"
"011110 ""0111100"
"011111 ""0111111"
"100000 ""1000000"
"100001 ""1000011"
"100010 ""1000100"
"100011 ""1000110"
"100100 ""1001000"
"100101 ""1001011"
"100110 ""1001100"
"100111 ""1001111"
"101000 ""1010000"
"101001 ""1010011"
"101010 ""1010100"
"101011 ""1010110"
"101100 ""1011000"
"101101 ""1011011"
"101110 ""1011100"
"101111 ""1011110"
"110000 ""1100000"
"110001 ""1100011"
"110010 ""1100100"
"110011 ""1100110"
"110100 ""1101000"
"110101 ""1101011"
"110110 ""1101100"
"110111 ""1101111"
"111000 ""1110000"
"111001 ""1110011"
"111010 ""1110100"
"111011 ""1110110"
"111100 ""1111000"
"111101 ""1111011"
"111110 ""1111100"
"111111 ""1111110"

2

f:id:nabeyang:20170420082445p:plain

0*((1(0|1)*¥p)|¥r)
INOUT
"000000 ""0000000"
"000001 ""0000011"
"000010 ""0000101"
"000011 ""0000111"
"000100 ""0001001"
"000101 ""0001011"
"000110 ""0001101"
"000111 ""0001111"
"001000 ""0010001"
"001001 ""0010011"
"001010 ""0010101"
"001011 ""0010111"
"001100 ""0011001"
"001101 ""0011011"
"001110 ""0011101"
"001111 ""0011111"
"010000 ""0100001"
"010001 ""0100011"
"010010 ""0100101"
"010011 ""0100111"
"010100 ""0101001"
"010101 ""0101011"
"010110 ""0101101"
"010111 ""0101111"
"011000 ""0110001"
"011001 ""0110011"
"011010 ""0110101"
"011011 ""0110111"
"011100 ""0111001"
"011101 ""0111011"
"011110 ""0111101"
"011111 ""0111111"
"100000 ""1000001"
"100001 ""1000011"
"100010 ""1000101"
"100011 ""1000111"
"100100 ""1001001"
"100101 ""1001011"
"100110 ""1001101"
"100111 ""1001111"
"101000 ""1010001"
"101001 ""1010011"
"101010 ""1010101"
"101011 ""1010111"
"101100 ""1011001"
"101101 ""1011011"
"101110 ""1011101"
"101111 ""1011111"
"110000 ""1100001"
"110001 ""1100011"
"110010 ""1100101"
"110011 ""1100111"
"110100 ""1101001"
"110101 ""1101011"
"110110 ""1101101"
"110111 ""1101111"
"111000 ""1110001"
"111001 ""1110011"
"111010 ""1110101"
"111011 ""1110111"
"111100 ""1111001"
"111101 ""1111011"
"111110 ""1111101"
"111111 ""1111111"

3

f:id:nabeyang:20170420082457p:plain

((1+0)|0)*((1+¥p)|¥r)
INOUT
"000000 ""0000000"
"000001 ""0000011"
"000010 ""0000100"
"000011 ""0000111"
"000100 ""0001000"
"000101 ""0001011"
"000110 ""0001100"
"000111 ""0001111"
"001000 ""0010000"
"001001 ""0010011"
"001010 ""0010100"
"001011 ""0010111"
"001100 ""0011000"
"001101 ""0011011"
"001110 ""0011100"
"001111 ""0011111"
"010000 ""0100000"
"010001 ""0100011"
"010010 ""0100100"
"010011 ""0100111"
"010100 ""0101000"
"010101 ""0101011"
"010110 ""0101100"
"010111 ""0101111"
"011000 ""0110000"
"011001 ""0110011"
"011010 ""0110100"
"011011 ""0110111"
"011100 ""0111000"
"011101 ""0111011"
"011110 ""0111100"
"011111 ""0111111"
"100000 ""1000000"
"100001 ""1000011"
"100010 ""1000100"
"100011 ""1000111"
"100100 ""1001000"
"100101 ""1001011"
"100110 ""1001100"
"100111 ""1001111"
"101000 ""1010000"
"101001 ""1010011"
"101010 ""1010100"
"101011 ""1010111"
"101100 ""1011000"
"101101 ""1011011"
"101110 ""1011100"
"101111 ""1011111"
"110000 ""1100000"
"110001 ""1100011"
"110010 ""1100100"
"110011 ""1100111"
"110100 ""1101000"
"110101 ""1101011"
"110110 ""1101100"
"110111 ""1101111"
"111000 ""1110000"
"111001 ""1110011"
"111010 ""1110100"
"111011 ""1110111"
"111100 ""1111000"
"111101 ""1111011"
"111110 ""1111100"
"111111 ""1111111"

終わりに

ガレットが1章で動作について説明しているところがあります。僕も、そのような表現でこの2つの像の動作を理解しようとしましたが、なかなか難しかったです。妥協して、正規表現で表現することにしました。普段から見るもので慣れているってだけかもしれませんが、この方が僕には分かりやすかったです。

『精霊の箱』に登場する「塔文字」の言語処理系split_boxについて

nnabeyng/split_boxに『精霊の箱』に登場する「塔文字」の言語処理系を置きました。いくつかサンプルもresourcesディレクトリに置いております。

実行方法

git cloneするかダウンロードして、rubyをインストールしていれば、main.rbを以下のようにして実行することができます。

富者の像と貧者の像

$./main.rb  resources/rich_and_poor.sb "010110 "

文字列の比較

./main.rb  resources/str_cmp.sb " 101-101 "

足し算

./main.rb  resources/sum.sb  " 111+010 "

NFAを使って足し算の関数を作りました

精霊の箱 上: チューリングマシンをめぐる冒険』の足し算する関数を書きました。requireで呼び出しているファイルはここに置いてます。本に登場する塔文字のようなものをコンパイルして使います。「文字列比較」と「富者の像と貧者の像」も同様にして、作成できることを確認しています。

#!/usr/bin/env ruby
require './parser.rb'
require './reg2post.rb'
require './nfa.rb'


require 'minitest/autorun'

class MainTest < MiniTest::Test
  def test_1
 p = Parser.new
 src = <<-SRC
1,00->,1
1,11->,1
1,++->,1
1,  <-,2
2,II<-,2
2,OO<-,2
2,0O<-,3
2,1I<-,4
2,++<-,14
3,00<-,3
3,11<-,3
3,++<-,5
4,00<-,4
4,11<-,4
4,++<-,6
5,OO<-,5
5,II<-,5
5,0O->,7
5,1I->,7
6,II<-,6
6,OO<-,6
6,0I->,7
6,1O->,13
7,00->,7
7,11->,7
7,OO->,7
7,II->,7
7,++->,7
7,  <-,2
8,OO<-,8
8,II<-,8
8,0O<-,9
8,1I<-,10
8,++<-,15
9,00<-,9
9,11<-,9
9,++<-,11
10,00<-,10
10,11<-,10
10,++<-,12
11,II<-,11
11,OO<-,11
11,1O->,13
11,0I->,7
12,OO<-,12
12,II<-,12
12,0O->,13
12,1I->,13
13,00->,13
13,11->,13
13,OO->,13
13,II->,13
13,++->,13
13,  <-,8
14,O0<-,14
14,I1<-,14
14,  <-,16
15,O0<-,15
15,I1<-,15
15, 1<-,16
SRC
  s = compile(reg2post(p.parse(src)))
  m = Machine.new(s)
  (0..10).each do|a|
    (0..10).each do|b|
      n = [a.to_s(2).length, b.to_s(2).length].max
      src = " #{("0" * n + a.to_s(2))[-n..-1]}+#{("0" * n + b.to_s(2))[-n..-1]} "
      assert_equal "#{(a+b).to_s(2)}", m.exec(src, 1).scan(/\w+/)[0]
    end
  end

  end
end

NFAで数を補って1の数を偶数に調整する関数を作りました

精霊の箱 上: チューリングマシンをめぐる冒険』の最初の貧者の像と富者の像が元ネタです。nfa.rbはここに載せているのと同じです。像の裏に書いてある命令から設計図を作って、個々の命令を要素と見なした正規表現に変換して、それをポストフィックス記法にしたものをcompile関数に与えると、NFAに変換するので、それを実行して実行しています。

#!/usr/bin/env ruby
require './nfa.rb'
require 'minitest/autorun'

class MainTest < MiniTest::Test
  def test_rich_and_poor
    a = "00->"
    b = "11->"
    c = " 1->"
    d = " 0->"
    s = compile("#{a}#{b}#{a}*.#{b}.|*#{d}#{b}#{a}*.#{c}.|.")
    m = Machine.new(s)
    assert_equal "0101101", m.exec("010110 ")
  end
end

NFAで文字列比較する関数を書きました

精霊の箱 上: チューリングマシンをめぐる冒険』が元ネタです。parser書いて、次みたいな感じで動くようにしたいですが、まだできてません。

src = <<-END
100->1
111->1
1 0<-3
200->2
211->1
2 1<-3
END

m = Machine.compile(src)
puts m.exec("100101011 ", 3)

本の中の設計図を正規表現に変形して、カッコの扱いが面倒なのでポストフィックス記法にしたコードを手で作ります(ポストフィックス記法への変換はツール使ってます)。そのソースをコンパイルして実行ということをしています。下のコードのa, b, c…は本を読めば分かると思います。これだけ書いて、なんとできることは文字列の比較だけなんです。文字列が等しければXXXX,XXXXのような出力になります。違えばnilが返ってきます。

#!/usr/bin/env ruby
require './nfa.rb'
require 'minitest/autorun'

class MainTest < MiniTest::Test
  def test_cmp_str
   a = "XX->"
   b = "0X->"
   c = "1X->"
   d = "00->"
   e = "11->"
   f = ",,->"
   g = "0X<-"
   h = "00<-"
   i = "11<-"
   j = ",,<-"
   k = "XX<-"
   l = "  ->"
   m = "1X->"
   n = "  <-"
   o = "1X<-"
   s = compile("#{a}#{l}|#{b}#{d}#{e}|*.#{f}.#{a}*.#{g}.#{c}#{d}#{e}|*.#{f}.#{a}*.#{o}.|#{h}#{i}#{j}#{k}|||*.#{l}.|*#{f}.#{a}*.#{n}.")
   m = Machine.new(s)
   assert !m.exec(" 0,1 ")
   assert !m.exec(" 1,0 ")
   assert_equal " X,X ", m.exec(" 1,1 ")
   assert_equal " XXXXXXXXXX,XXXXXXXXXX ", m.exec(" 1010001111,1010001111 ")
  end
end
#./nfa.rb
class Machine
  def initialize(state)
    @init  = state
  end
  def step(str)
    state_lists = []
    is = []
    strs = []
    @state_lists.each.with_index do|states, j|
      pos = @is[j]
      str = @strs[j]
      states.each do|s|
        if s.b == str[pos]
          new_str = str.dup
          s.exec(pos, new_str)
          strs << new_str
          is << pos + s.steps
          state_lists << next_states(s.out1)
        end
      end
    end
    @is = is
    @strs = strs
    state_lists
  end
  def isMatch
    v = nil
    i = 0
    @state_lists.each do |states|
      if (states.find{|s| s.type == :end})
         v = i
         break
      end
      i += 1
    end
    v
  end
  def exec(str)
    @state_lists = [next_states(@init)]
    @strs = [str]
    @is = [0]
    l = str.length
    while !isMatch && @state_lists.size > 0 do
      @state_lists = step(str)
    end
    (i = isMatch) ? @strs[i] : nil
  end
  def next_states(state)
    nstates = []
    return [] if !state
    case state.type
    when :split
       nstates << next_states(state.out1)
       nstates << next_states(state.out2)
    else
       nstates << state
    end
    nstates.flatten.compact
  end
end

class Frag
  attr_accessor :start, :out
  def initialize(start, out)
    @start = start
    @out = out
  end
  def patch(other)
    @out.each do |state|
      state.out1 = other
    end
  end
end

class StateList
   include Enumerable
   attr_accessor :head, :next
   def initialize(head)
     @head = head
   end
   def append(l)
    e = self
    while e.next do
      e = e.next
    end
    e.next = l
    self
   end
   def each
     e = self
     while e && e.head do
       yield e.head
       e = e.next
     end
   end
end

class State
  attr_reader :b, :steps, :type, :a
  attr_accessor :out1, :out2
  def initialize(type, b, a, steps)
    @type = type
    @b = b
    @a = a
    @steps = steps
  end
  def inspect
    "S(#{@type}, #{@b.inspect}, #{@a.inspect})"
  end
  def to_s
    "S(#{@type},#{@b},#{@a}, #{@steps})"
  end
  def exec(i, str)
    str[i] = @a
    #puts "(#{self.to_s}).exec(#{i}, #{str})"
  end
end

def compile(source)
  stack = []
  l = source.length
  i = 0
  while i < l do
    c = source[i]
    case c
    when '*'
      e = stack.pop
      s = State.new(:split, nil, nil, nil)
      s.out2 = e.start
      e.patch(s)
      stack.push(Frag.new(s, StateList.new(s)))
      i+=1
    when '.'
      e2 = stack.pop
      e1 = stack.pop
      e1.patch(e2.start)
      stack.push(Frag.new(e1.start, e2.out))
      i+=1
    when '|'
      e2 = stack.pop
      e1 = stack.pop
      s = State.new(:split, nil, nil, nil)
      s.out2 = e1.start
      s.out1 = e2.start
      stack.push(Frag.new(s, e1.out.append(e2.out)))
      i+=1
    else
      s = State.new(:value, source[i, 1], source[i + 1, 1], ('->' == source[i + 2, 2])? 1 : -1)
      i+= 4
      stack.push(Frag.new(s, StateList.new(s)))
    end
  end
  e = stack.pop
  e.patch(State.new(:end, nil, nil, nil))
  e.start
end

罫線用文字の重なり部分の処理を簡単にするgemを書きました

文字列で数独を表示するときに、罫線用の文字をたくさん使うのでそれを扱う専用クラスを書きました。gemを書いたことが無かったので、せっかくなのでgemにして(/nnabeyang/box_drawing_char)に公開しています。罫線の重なり、例えば└と┘が隣接するとき、┴で置き換えると隙間なく表示されます。この置き換えは、このgemを使えば次のような文字同士の足し算で楽に処理できます。

    a = BoxDrawingChar::Char.new(?└)
    b = BoxDrawingChar::Char.new(?┘)
    expect((a + b).to_s).to eq(?┴)

罫線は、下の図のような十字の4つの線の無し、有り、太いから成ります。足し算は、足される文字の4要素を足します。ただし2重に足されるところの値は大きい値になるようにします。

f:id:nabeyang:20170413092733j:plain

文字の無し、有り、太いという情報を0, 1, 2として、4桁の3進数で表すことにします。この時計回りに書く仕様はCSSのパディングとか書くときの順番と一致させています。説明が分かりにくいですが、次の例を見ればなんとなく分かると思います。

    dict[t_ary_num(0d0110)] = ?┌

    dict[t_ary_num(0d0111)] = ?┬ 

    dict[t_ary_num(0d0112)] = ?┭ 

    dict[t_ary_num(0d0120)] = ?┎