最近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
この場合が一番厄介です。どんな動作するんですかと言うと、本で言うところの11->
と00->
は普通のプログラミング言語で使える正規表現で言うところの1と0と同じ動作なのでこれに置き換え、1<-
は貧者が銅貨を置く動作で、これを¥p
とし、0<-
は富者が金貨を置く動作で、これを¥r
と書くことにします。この設計図の動作を正規表現で書くと次のようになります。
(0|(1(1|0)))*(¥r|(1¥p))
次の表が週の最後の日に像たちがどのように動作をするのかの一覧になります。INが週の最後の日までに置かれた硬貨の配置、OUTが像が動作したあとの硬貨の配置になります。残りの場合の動作についても、設計図とそれに対応する正規表現と表だけ載せております。
IN | OUT |
---|---|
"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
0*((1(0|1)*¥p)|¥r)
IN | OUT |
---|---|
"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
((1+0)|0)*((1+¥p)|¥r)
IN | OUT |
---|---|
"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重に足されるところの値は大きい値になるようにします。
文字の無し、有り、太いという情報を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)] = ?┎