2006-06-05
■ [Ruby][Quiz][Q3]GEDCOM Parser 
今日は調子がいいので、さぼっていたRuby Quizの続きを書こう。
3問目。
GEDCOM(GEnealogical Data COMmunication)フォーマットという構造化されたテキストをXMLに変換しようという問題。
GEDCOMフォーマットサンプルは下のような感じ
0 @I1@ INDI 1 NAME Jamis Gordon /Buck/ 2 SURN Buck 2 GIVN Jamis Gordon 1 SEX M ...
各行は
という構成になっていて、LEVELは注目してる行の階層の深さを表している。
TAG-OR-IDはそのままでタグかIDが入る。タグとは英大文字3文字から4文字から成りその後に続くデータの型を表す。
IDは@で囲まれた文字列でファイル内でかぶらないユニークな文字列が入り、その後に続くデータがサブツリーの型を表す。
まぁ、毎度のことながら言葉で説明してもわからんのでXMLで上のGEDCOMを変換すると下のような感じになる。
<gedcom> <indi id="@I1@"> <name> Jamis Gordon /Buck/ <surn>Buck</surn> <givn>Jamis Gordon</givn> </name> <sex>M</sex> ... </indi> ... </gedcom>
まぁ一目瞭然ですな。
ようするにこんな感じになるように変換しろってことです。
了解。把握した。
ちなみに、でかいGEDCOMフォーマットのファイルはここにあるらしいのでテストするのに使おう。
続く
2006-05-30
■ [Ruby][Quiz][Q2]続・解答 
昨日の続き。
3つめの解答。コードはcode/lcd_number/states.rb。
この解答はちょっと変わっていて、縦棒のある行と横棒のある行にそれぞれ以下のような状態をもたせる。
縦棒のある行
- 0 縦棒なし
- 1 右側にだけ縦棒がある
- 2 左側にだけ縦棒がある
- 3 両側に縦棒がある
横棒のある行
- 0 横棒なし
- 1 横棒あり
でこれらの状態を使って図形を配列で表すと
LCD_DISPLAY_DATA = { #0だけわかりやすく書いてみる "0" => [1, # - 横棒がある 3, # | | 縦棒が両側にある 0, # 横棒がない 3, # | | 縦棒が両側にある 1 # - 横棒がある ], "1" => [ 0, 1, 0, 1, 0 ], "2" => [ 1, 1, 1, 2, 1 ], "3" => [ 1, 1, 1, 1, 1 ], "4" => [ 0, 3, 1, 1, 0 ], "5" => [ 1, 2, 1, 1, 1 ], "6" => [ 1, 2, 1, 3, 1 ], "7" => [ 1, 1, 0, 1, 0 ], "8" => [ 1, 3, 1, 3, 1 ], "9" => [ 1, 3, 1, 1, 1 ] }
であとは以下のコードのように
横棒のある行、縦棒のある行の状態に対する処理を書き
横棒のある行→縦棒のある行→横棒のある行→縦棒のある行→横棒のある行の順番に処理をしていけば最終的な結果を得られる。
LCD_STATES = [ "HORIZONTAL", "VERTICAL", "HORIZONTAL", "VERTICAL", "HORIZONTAL", "DONE" ] def display( digits ) states = LCD_STATES.reverse 0.upto(LCD_STATES.length) do |i| case states.pop when "HORIZONTAL" #横棒のある行に対する処理 line = "" digits.each_byte do |b| line += horizontal_segment( LCD_DISPLAY_DATA[b.chr][i] ) end print line + "\n" when "VERTICAL" #縦棒のある行にたいする処理 1.upto(@size) do |j| line = "" digits.each_byte do |b| line += vertical_segment( LCD_DISPLAY_DATA[b.chr][i] ) end print line + "\n" end when "DONE" break end end end
この解答のすごいところは、行列を入れ替えたり配列を結合したりしなくても画面で見える1行分の結果が1度に作れるのでメモリを食わないということみたい。
確かに、前2つの解答では入力が多くなればなるだけ巨大な配列の確保と操作をしなければならないがこの解答では繰り返しの回数が多くなるだけで消費するメモリは少なくて済む。
いやいや、今回の問題はrubyというよりも考え方が勉強になりました。
明日は、いよいよ次の問題をやろうと思う。
つづく
2006-05-29
■ [Ruby][Quiz][Q2]解答 
4日も空けてしまったが、LCD Numbersの解答を見てみたいと思う。
なお今回からの模範解答コード一部から引用して勉強になった部分のみ説明しようと思う。
今回の解答はcode/lcd_number/にあるやつ。
(golfed.rbは本文に書かれてないので省略。神業的コードなんで好きな人はどうぞ)
3つあって一つめ。コードはcode/lcd_number/template.rb。
これは自分が書いたコードと同じアプローチでサイズ1の時の文字列を用意しておいてそれを分解したり回転させたり置換したりして結果を作るという方法。
勉強になった部分のみ引用すると、サイズ1の時の文字列を分解する部分。
7 # templates 8 DIGITS = <<END_DIGITS.split("\n").map { |row| row.split(" # ") }.transpose 9 - # # - # - # # - # - # - # - # - 10 | | # | # | # | # | | # | # | # | # | | # | | 11 # # - # - # - # - # - # # - # - 12 | | # | # | # | # | # | # | | # | # | | # | 13 - # # - # - # # - # - # # - # - 14 END_DIGITS
Array#transposeは配列を行列とみなし、行と列を入れ替えてくれるものらしい。
このコードだとまず
DIGITS = <<END_DIGITS.split("\n").map { |row| row.split(" # ") } - # # - # - # # - # - # - # - # - | | # | # | # | # | | # | # | # | # | | # | | # # - # - # - # - # - # # - # - | | # | # | # | # | # | # | | # | # | | # | - # # - # - # # - # - # # - # - END_DIGITS
という部分までで
[ [" - ", " ", " - ", " - ", " ", " - ", " - ", " - ", " - ", " -" ], ["| |", " |", " |", " |", "| |", "| ", "| ", " |", "| |", "| |"], [" ", " ", " - ", " - ", " - ", " - ", " - ", " ", " - ", " -" ], ["| |", " |", "| ", " |", " |", " |", "| |", " |", "| |", " |"], [" - ", " ", " - ", " - ", " ", " - ", " - ", " ", " - ", " -" ] ]
のような配列に分割されさらにtransposeメソッドを呼ぶと
[ #0だけ見やすいようにしてみた [" - ", "| |", " ", "| |", " - "], [" ", " |", " ", " |", " "], [" - ", " |", " - ", "| ", " - "], [" - ", " |", " - ", " |", " - "], [" ", "| |", " - ", " |", " "], [" - ", "| ", " - ", " |", " - "], [" - ", "| ", " - ", "| |", " - "], [" - ", " |", " ", " |", " "], [" - ", "| |", " - ", "| |", " - "], [" -", "| |", " -", " |", " -"]]
のような最上部、上部、中、下部、最下部が一つの配列の中に入るような配列の配列に変形できる。
EnumerableとかArrayに便利すぎるメソッドがありまくり。
この解答はここが肝でここまで整形できてしまえばあとは煮るなり焼くなり好きにしてといった感じである。
この解答は他には特筆すべきとこはないのでここまで。
次、2つ目。コードはcode/lcd_number/bits.rb。
この解答は以下のようにそれぞれのマスに番号をふって、それをビットの並びで表現しようというアイディア。
6 5 4 3 2 1 0
例えば、以下のような図形を表したい場合は
- | - | -
0, 2, 3, 4, 6ビット目を立てて
0b1011101
と表現する。
あとは以下のメソッドを使ってビットの立ってるところに"|"やら"-"を埋めていけば最終的な結果が得られるという寸法。
21 Top, TopLeft, TopRight, Middle, BottomLeft, BottomRight, Bottom = *0 .. 6 25 private 26 27 def line(digit, bit, char = "|") 28 (digit & 1 << bit).zero? ? " " : char #bitビット目が1だったらcharを返す 29 end 30 31 def horizontal(digit, size, bit) 32 [" " + line(digit, bit, "-") * size + " "] #横棒の計算 33 end 34 35 def vertical(digit, size, left_bit, right_bit) 36 [line(digit, left_bit) + " " * size + line(digit, right_bit)] * size #縦棒の計算 37 end 38 39 def digit(digit, size) 40 digit = Digits[digit.to_i] 41 horizontal(digit, size, Top) + #最上部(横棒か空白しかない) 42 vertical(digit, size, TopLeft, TopRight) + #上部(縦棒か空白しかない) 43 horizontal(digit, size, Middle) + #真ん中(横棒か空白しかない) 44 vertical(digit, size, BottomLeft, BottomRight) + #下部(縦棒か空白しかない) 45 horizontal(digit, size, Bottom) #最下部(横棒か空白しかない) 46 end
とここまで書いてすげー眠くなったので今日はここまで。
一気にやると疲れるし時間もかかるから毎日少しずつやろう。そうしよう。
2006-05-24
■ [Ruby][Quiz][Q2]回答 
一日おいてしまったが回答してみる。
CR = "\n" data = [ ' - ' + CR + '|*|' + CR + ' * ' + CR + '|*|' + CR + ' - ' , ' * ' + CR + ' *|' + CR + ' * ' + CR + ' *|' + CR + ' * ', ' - ' + CR + ' *|' + CR + ' - ' + CR + '|* ' + CR + ' - ', ' - ' + CR + ' *|' + CR + ' - ' + CR + ' *|' + CR + ' - ', ' * ' + CR + '|*|' + CR + ' - ' + CR + ' *|' + CR + ' * ', ' - ' + CR + '|* ' + CR + ' - ' + CR + ' *|' + CR + ' - ', ' - ' + CR + '|* ' + CR + ' - ' + CR + '|*|' + CR + ' - ', ' - ' + CR + '|*|' + CR + ' * ' + CR + ' *|' + CR + ' * ', ' - ' + CR + '|*|' + CR + ' - ' + CR + '|*|' + CR + ' - ', ' - ' + CR + '|*|' + CR + ' - ' + CR + ' *|' + CR + ' - ' ] require 'optparse' require 'generator' option = {:size => 2} opts = OptionParser.new opts.on('-s VAL') {|val| option[:size] = val.to_i} opts.parse!(ARGV) def usage puts "#{$PROGRAM_NAME} [-s size] digits" exit end usage unless ARGV.size == 1 digits = Array.new ARGV[0].split(//).each do |i| digits << data[i.to_i].split(CR) end result = "" size = option[:size] tmp_size = option[:size] se = SyncEnumerator.new(*digits) se.each do |arry| line = arry.join(' ') if line.include?('|') result << line.gsub('*', ' ' * size) << CR tmp_size -= 1 if tmp_size != 0 redo else tmp_size = size end else result << line.gsub('-', '-' * size).gsub('*', ' ' * size) << CR end end print result
工夫したところは、SyncEnumeratorで複数の配列を一気にまわしてるところと
redoで"|"を描く回数を制御してるところかな。
あと作ってて気づいたのはString#gsub!は一個も置換できないとnilを返すってこと
なので、gsub!(~).gsub!(~)って続けて書くときは注意。
なんというか、あれですねEnumerableとイテレータ万歳みたいな感じでした。
よし、明日は解答をやろう。
続く
2006-05-22
■ [Ruby][Quiz][Q2]LCD Numbers 
やっと2問目。まじこのペースでやってたらいつ終わるかわからん。。。
でも、とりあえず止めないといのが目標っつことでw
2問目はデジタルな数字を表示しようって問題。
例として以下のようなのが書いてあって
$ lcd.rb 012 -- -- -- | | | | | | | | | | -- -- | | | | | | | | | | -- -- --
コマンドの引数に与えられた数字を"-"と"|"を使って描けと。
で、オプションもあって-sに数字を与えると表示される数字の大きさが変わる。
$ lcd.rb -s 1 012 - - | | | | - | | | | - -
デフォルトが2らしいから初めの例は"-"と"|"が2個ずつ表示されてる。
んで、最後に気をつけなくちゃいけないのが表示される数字と数字の間には大きさにあったスペースが入らないといけないということ。
なるほど、なるほど。
把握した。
明日は回答を書きたいと思ふ。
続く