あみだくじを作ってみる。

言語を練習するとき、面白い問題があると便利ですね。どう書く？orgではそんな問題が沢山掲載されています。そこに乗っていた二つの問題を解いてみたのでメモしておきます。コードが稚拙なので投稿するのは憚られますが・・・。
まず1問目の問題を解きます。これは、与えられたあみだくじを解くだけの問題です。基本的な解法としてはあみだくじの行数分ループさせ、最初に与えられた１行をあみだくじに従って入れ替える事が考えられますが、この方法は既に投稿されているので、別の方法をとってみることにします。

class Walker
  LINE_MOVE_NUM = 2
  attr_reader :character
  attr_accessor :x, :y
  def initialize(character,x,y)
    @character = character
    @x = x
    @y = y
  end
  def go_to_next(line)
    @y += 1
    if line[@x+1,1] == "-"
      @x += LINE_MOVE_NUM
    elsif line[@x-1,1] == "-"
      @x -= LINE_MOVE_NUM
    end
  end
end
amidakuji = <<END_OF_AMIDAKUJI
A B C D E
| | |-| |
|-| | |-|
| |-| |-|
|-| |-| |
|-| | | |
END_OF_AMIDAKUJI
result = ""
walkers = Array.new
amidakuji.each_line do |line|
  if walkers.empty?
    line.split(//).each_with_index do |c,i|
      print "#{c}"
      walkers << Walker.new(c,i,0) unless c == " "
      result << c
    end
  else
    walkers.each do |c|
      c.go_to_next(line)
      result[c.x,1] = c.character
    end    
    print("#{line.chomp} : #{result}")
  end
end
puts result

最初の一行を、あみだくじを進める人（Walker）オブジェクトと見なし、go_to_nextメソッドで次の行を見に行く仕組みです。エレガントでもなんでもないですが、Rubyでクラスを使う練習にはなりましたね。確認結果は次のようになります。

A B C D E
| | |-| | : A B D C E
|-| | |-| : B A D E C
| |-| |-| : B D A C E
|-| |-| | : D B C A E
|-| | | | : B D C A E
B D C A E

あみだくじの横の数字は、一行ごとに、そのときwalker(s)がいた座標を表します。もっと複雑なあみだくじも試してみます。

A B C D E F G H
| | |-| | |-| | : A B D C E G F H
|-| | |-| | |-| : B A D E C G H F
| |-| |-| |-| | : B D A C E H G F
|-| |-| |-| |-| : D B C A H E F G
|-| | | | |-| | : B D C A H F E G
B D C A H F E G

ちゃんと答えが出ています。ただし、このコードでは横棒が連なっている場合（|-|-|）は対処できずヘンな結果になります。

とりあえず解く事はできたので、２問目に進みます。これは、あみだくじの答え（結果？）からあみだくじ自体を生成するという問題です。生成されたあみだくじの一行目は、答えを昇順にソートしたものになります。ここではオブジェクトをつかって云々やると大変なので、ソートという特性を使ったコードを書きました。

def generate_amidakuji_from_result(arg)
  #配列をディープコピー
  sorted_list = Marshal.load(Marshal.dump(arg)).sort.to_s
  list        = Marshal.load(Marshal.dump(arg))
  amidakuji = Array.new
  i = 0
  #リストがソート済みの結果になるまでループ
  until(sorted_list == list.to_s)
    j = 0
    #列の最後まで走査
    while(list[j+1] != nil)  
      if(list[j].to_i > list[j+1].to_i)
        #入れ替え
        list[j],list[j+1] = list[j+1],list[j] 
        add = "|-|"
        j+=1
      else
        add = "|"
      end
      j+=1
      #列の最後ならば縦棒で閉じる。
      add << " |" if j < list.size && (list[j] == nil || list[j+1] == nil) 
      (amidakuji[i] ||= "") << add << " "
    end
    amidakuji[i].strip!
    i += 1
  end
  amidakuji
end

#list  = [3,1,5,5,1,2,4,5,5,7,3,1,6,2,4]
#list = [3,5,2,4,0,1]
list = ARGV
puts list.sort.join(" ")
puts generate_amidakuji_from_result(list).reverse
puts list.join(" ")

このコードには汚い点があります。until式で「リストがソート済みの結果になるまでループ」していることです。つまり、最初に受け取った配列をまずソートしてから文字列に直し、処理中の配列も文字列に変換し、毎ループごとに見比べるからです。これはパフォーマンス的にも問題があるし、なんかダサイですね。これ以外の方法を思いついたら教えてください。
結果は以下のようになります。rubyでこのコードを走らせるときは、引数にスペース区切りでリストを与えてください。問題の例を使うならば、コード中のコメントを外して使ってください。また、このコードでは１桁以上の数字はサポートできません。これはあみだくじの体裁のためです。

$ ruby amida2.rb 3 5 2 4 0 1
0 1 2 3 4 5
| |-| | | |
|-| |-| |-|
| |-| |-| |
|-| |-| |-|
| |-| |-| |
3 5 2 4 0 1

なんとか生成できたようです。ところで、どう書く？に投稿されているRubyコード（現時点）では同じ値を含むリストを渡されると正しく処理ができないようです。（問題文にないから当然ですが）このコードはそういったリストも処理できます。

$ ruby amida2.rb 3 3 3 3 3 3 2
2 3 3 3 3 3 3
|-| | | | | |
| |-| | | | |
| | |-| | | |
| | | |-| | |
| | | | |-| |
| | | | | |-|
3 3 3 3 3 3 2

1 1 1 2 2 3 3 4 4 5 5 5 5 6 7
| | |-| |-| | | | | | | | | |
| | | |-| |-| | | | | | | | |
| | | | |-| |-| |-| | | | | |
| | | | | |-| |-| |-| | | | |
| | | | |-| |-| |-| |-| | | |
| | | | | |-| |-| |-| |-| |-|
| | |-| |-| |-| |-| |-| |-| |
| |-| |-| |-| |-| |-| |-| | |
| | |-| |-| | | |-| |-| | |-|
|-| | |-| | | | | |-| | |-| |
3 1 5 5 1 2 4 5 5 7 3 1 6 2 4

１問目のWalkerをつかってあみだくじを解くと、正しくルーティングされている事がわかります。

1 1 1 2 2 3 3 4 4 5 5 5 5 6 7
| | |-| |-| | | | | | | | | | : 1 1 2 1 3 2 3 4 4 5 5 5 5 6 7
| | | |-| |-| | | | | | | | | : 1 1 2 3 1 3 2 4 4 5 5 5 5 6 7
| | | | |-| |-| |-| | | | | | : 1 1 2 3 3 1 4 2 5 4 5 5 5 6 7
| | | | | |-| |-| |-| | | | | : 1 1 2 3 3 4 1 5 2 5 4 5 5 6 7
| | | | |-| |-| |-| |-| | | | : 1 1 2 3 4 3 5 1 5 2 5 4 5 6 7
| | | | | |-| |-| |-| |-| |-| : 1 1 2 3 4 5 3 5 1 5 2 5 4 7 6
| | |-| |-| |-| |-| |-| |-| | : 1 1 3 2 5 4 5 3 5 1 5 2 7 4 6
| |-| |-| |-| |-| |-| |-| | | : 1 3 1 5 2 5 4 5 3 5 1 7 2 4 6
| | |-| |-| | | |-| |-| | |-| : 1 3 5 1 5 2 4 5 5 3 7 1 2 6 4
|-| | |-| | | | | |-| | |-| | : 3 1 5 5 1 2 4 5 5 7 3 1 6 2 4
3 1 5 5 1 2 4 5 5 7 3 1 6 2 4

また、次のようにStringクラスにto_iメソッドを追加すれば、文字列リストを渡しても文字列コードでソートしてくれます。*1

class String
  def to_i
    self
  end
end

$ ruby amida2.rb C D A E F D B
A B C D D E F
| |-| | | | |
| | |-| | | |
| | | |-| | |
| | | | |-| |
|-| | |-| |-|
| |-| | |-| |
C D A E F D B

$ ruby amida2.rb O W A T A  ^ o ^
A A O T W ^ ^ o
| |-| |-| | | |
|-| |-| | | | |
| |-| |-| | |-|
O W A T A ^ o ^

以上。

*1:ruby 1.8系