「精霊の箱」の貧者の像と富者の像のようなものを書きました
『精霊の箱 上: チューリングマシンをめぐる冒険』の1章で登場する貧者の像と富者の像のような動作をする関数rich_and_poorを書きました。のようなと言っているのは、最後の状態の処理で@posが逆に移動するのですが、そこは無視しているからです。そのまま2章の文字列の比較も書こうとしましたが、ループのところ、えーっと正規表現で言うところのe*をオートマトンで表現した部分で、eが複雑な式の場合がうまく書けてないので、コンパクトに書けずにいます。
#!/usr/bin/env ruby class Machine def initialize(state) @pos = 0 @init = @state = state end def step(str) next_states(@state).#tap{|a| puts a.inspect}. each do|s| if s.type == :start @state = s.out1 return elsif s.type == :end @state = s return elsif s.b == str[@pos] s.exec(@pos, str) @state = s.out1 @pos += s.steps return end end raise "failed" end def exec(str) while @state.type != :end step(str) end @state = @init @pos = 0 str 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 State attr_reader :b, :steps, :type, :a, :id attr_accessor :out1, :out2 def initialize(id, type, b, a, steps) @id = id @type = type @b = b @a = a @steps = steps end def inspect "S(#{@id}, #{@type}, #{@b.inspect}, #{@a.inspect})" end def to_s "S(#{@id},#{@b},#{@a})" end def exec(i, str) #puts "S(#{@id}).exec(#{i}, #{str})" str[i] = @a end def push(o) s = self while s.out1 != nil do s = s.out1 end s.out1 = o end end def star(id, before, after, step) s1 = State.new(id, :split, nil, nil, 1) s2 = State.new("#{id}:star", :value, before, after, step) s1.out2 = s2 s2.out1 = s1 s1 end def connect(s1, before, after, step, s2) s3 = State.new("#{s1.id}:#{s2.id}", :value, before, after, step) s = s1 while s do if !s.out1 s.out1 = s3 break elsif s1.out1.type == :value s4 = State.new("", :split, nil, nil, nil) t = s.out1 s.out1 = s4 s4.out1 = t s4.out2 = s3 break end s = s.out2 end s3.out1 = s2 end def rich_and_poor rich = star(1, '0', '0', 1) poor = star(2, '0', '0', 1) goal = State.new(3, :end, nil, nil, nil) connect(rich, '1', '1', 1, poor) connect(rich, ' ', '0', 1, goal) connect(poor, '1', '1', 1, rich) connect(poor, ' ', '1', 1, goal) m = Machine.new(rich) puts "0101101" == m.exec("010110 ") puts "0000000" == m.exec("000000 ") puts "0001001" == m.exec("000100 ") end rich_and_poor