09

24

[Ruby] ナムドット問題を解きました

2013.09.24(21:00)

結城浩 @hyuki さんのツイートで知った
ナムドット問題
http://www.hyuki.com/codeiq/#c13
を解いてCodeIQへ投稿しました。
考えた過程と、解答を生成するプログラムを残しておきます。

ナムドット問題は、与えられた(52-20)行の文字列からその生成規則を見つける問題。
不規則に見えるものから規則を見つけるのもプログラマのお仕事。

出題の先頭部分は以下のとおり。
12345
1234.5
1235.4
123.45
123.4.5
1245.3
124.35
124.3.5
...
最初に考えたこと
・52行のパターンのうち重なっているものはないので何かの繰り返しではなさそう。
・曜日とか月とかも関係なさそう。何かの規則で52行が生成されているらしい。
・簡単でもない代わりに、ランダムとか意地悪もないはず。

次に考えたこと
・単純な規則ではなく、複数の規則を組み合わせた結果なんだろう。
・なので、見つかった規則から順番に取り除いてゆけばやがて単一の規則に
たどりつくのではないだろうか。
・全部の行の先頭に1があるのでこれは取り除いてOK
・5は左から右へ移動してゆくような気がする。
・5が左から右へ移動するときにドット(.)が関係しているような。
・ドット(.)が移動するアルゴリズムと、ドット(.)の周辺を入れ替える
ようなアルゴリズムが組み合わさっているのでないか。★

ここで2日経過。

・★ではどうにも解答に行き着かず、その延長線上で考えるのをやめる。
・改めて、
・1行目と2行目を見比べると、"5"が".5"に変わっている。
・それと同じことが、4~5行目、7~8行目、10~11行目、以後ずっと
続いているようだ。そこで、2行目まで、5行目まで、8行目まで、11行目まで
で区切ってみる。
・それぞれのブロックで"5"や".5"を取り除くと、
3~5行目までは全部"123.4",
6~8行目までは全部"124.3",
9~11行目までは全部"12.34"
である。これを各ブロックの基本文字列と呼ぶことにする。

あらためて、3~5行目を見ると、"123.4"に対して、
ドットの左に"5"を、一番右に"5"を、一番右に".5"を追加した形になっている。
7~8行目、10~11行目、、、、48~52行目までそうなっている。
1~2行目はドットがない "1234"に対して、一番右に"5"を、
一番右に".5"を追加した形になっている。規則的だ。

これでブロックの基本文字列が与えられれば
1ブロック分は生成できるようになった。

あとはブロックの基本文字列をどうやって作るかだ。

もとの出題の
"12345","1234.5","1235.4","123.45","123.4.5",...
と、ブロックの基本文字列
"1234","123.4","124.3","12.34","12.3.4",...
を見比べると、そっくり。
出題の文字列の先頭の"1"を削除して、残った数字を全部1ずつ引くと、
ブロックの基本文字列ができる。

つまり、出題の文字列から、ブロックの基本文字列を作り出すことができる。解けた!

以下のRubyプログラムはそのとおりを表現したものになっています。

# encoding: Shift_JIS
# print("numdot mondai\n")

def generate(array,word)
  first = word.split(//)
  first.shift     # 先頭を取り除く
  second = Array.new
  first.each { |ch|
    if ch == '.' 
      second << ch
    else
      second << ((ch.to_i) - 1).to_s  # 各要素を1減らす
    end
  }
  len = second.length
  second.each_with_index { |ch,idx|
    if ch == '.'  # ドットごとにドットの手前に5をいれた数を作る
       array << (second[0..idx-1].join + "5" + second[idx..len].join)
    end
  }
  array << (second.join + "5")  # "5"を後置
  array << (second.join + ".5") # ".5"を後置
end

array = Array.new
word = "12345"
array = generate(array,word)    # 最初の種で配列を作る
1.upto(15) { |idx|
  array = generate(array,array[idx]) # 2回目以降は配列のn番目を使って生成する
}
array.each_with_index { |word,idx|
  printf "#{word}\n"
  break if idx == 51
}
exit
このプログラムで生成した答え
12345
1234.5
1235.4
123.45
123.4.5
1245.3
124.35
124.3.5
125.34
12.345
12.34.5
125.3.4
12.35.4
12.3.45
12.3.4.5
1345.2
134.25
134.2.5
135.24
13.245
13.24.5
135.2.4
13.25.4
13.2.45
13.2.4.5
145.23
14.235
14.23.5
15.234
1.2345
1.234.5
15.23.4
1.235.4
1.23.45
1.23.4.5
145.2.3
14.25.3
14.2.35
14.2.3.5
15.24.3
1.245.3
1.24.35
1.24.3.5
15.2.34
1.25.34
1.2.345
1.2.34.5
15.2.3.4
1.25.3.4
1.2.35.4
1.2.3.45
1.2.3.4.5
おそらく、もっときれいなアルゴリズムがあるのだと思う。@hyuki さんの解説を待ちたい。
プロフィール

島敏博

Shima Toshihiro 島敏博
信州アルプスハイランド在住。HaskellとElixirが好き。組み込みソフトウェアアーキテクト、C++プログラマ、山歩き、美術館巡り、和食食べ歩き、日本赤十字社救急法指導員、インデックス投資、クラシック音楽、SESSAME会員、状態マシン設計、モデル駆動開発、ソフトウェアプロダクトライン、Rubyist、実践ビジネス英語

■ ツイッター
http://twitter.com/saltheads
■ Facebook
http://www.facebook.com/saltheads
■ Qiita
http://qiita.com/saltheads

印刷する場合は、ブラウザの印刷メニューではなく、このページの上から3cmくらいの青いところにある、「印刷」を押してみてください。少しうまく印刷できます。まだ完全ではないのですが、これで勘弁してください。


カテゴリ
最新記事
月別アーカイブ
最新コメント
検索フォーム
リンク
sessame
RSSリンクの表示