Ruby Advent Calendar 2018 の11日目の投稿となります。
10日目は @Yuki-Inoue さんによる「Daru のちょっと詳しい説明: Index, Vector, DataFrame のデータ構造について」 でした。
「数学の問題をRubyで解いたよ」ってだけの記事です。
スレ違いな気もしますが、カレンダーが1日だけ空いていたので滑り込んじゃいました。
アジェンダ
概要
笑わない数学者 - MATHMATICAL GOODBYE -
森博嗣著 1996年9月 講談社刊
天才数学者である天王寺博士が作中、数学の問い(組み合わせ順列問題)を出題します。
劇中にて解答は明かされず、物語は完結します。
読了後その問題に挑戦しましたが、最後に数学をちゃんと学んでかれこれ数年経っていることもあり解けませんでした。
しかしその間に学んだRubyを使って答えには辿り着けたので、今回記事にしてみました。
答えは一番最後に載せたので、暇な人は一度自力で解いてみる、本を手に取ってみるなどしてみると良いと思われます。
余談ですが、Rubyは好き勝手書ける感が好きです。僕と同い年なところもなんとなく良いです。ブラザー。object.c は僕と同じ日に生まれています。いつかメンテしてあげたい。
Rubyistの方は「もっと短く書けるぞ！」「なんだそのウ○コードは」などのツッコミお願いします。余談終わり。
#問題
「さて、では、もう一つ問題を出そう。五つのビリヤードの玉を、真珠のネックレスのように、リングにつなげてみるとしよう。
玉には、それぞれナンバが書かれている。さて、この五つの玉のうち、幾つ取っても良いが、隣どうし連続したものしか取れないとしよう。一つでも、二つでも、五つ全部でも良い。しかし、離れているものは取れない。
この条件で取った玉のナンバを足し合わせて、1から21までのすべての数ができるようにしたい。さあ、どのナンバの玉を、どのように並べて、ネックレスを作れば良いかな？」
※ビリヤードの数字球は1~15の15種類
1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15
スクリプト
僕が知っているRubyの文法(極僅か)を駆使し、上記を解くスクリプトを書きました。
解答が幾つか表示されますが、メンドくさいので同一の順列をそのまま表示しているためです。解答は一通り(のはず)です。逆に並べるパターンを入れたら2つかな。
ビリヤード玉15から5つの順列を選ぶ全ての組み合わせを生成し、1-21の数字を作れるかを判定します。力で解決。
# ビリヤードの数字球は1-15
billiard_ball = [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15]
# [f,f,f,f,f,f,f,f,f,f,f,f,f,f,f,f,f,f,f,f,f,f,f]
# 22個のフラグ（可読性の為に22個用意、0番目は未使用）
# 5つのビリヤード球から1を作れたら1番目をtに、15を作れたら15番目をtに…
generated = Array.new(22, false)
# [f,t,t,t,t,t,t,t,t,t,t,t,t,t,t,t,t,t,t,t,t,t,t]
# 1-21の数字を作れた場合の22個のフラグの状態。
# 最終的にgeneratedとの比較に使用する。
# 0番目のみがfになっている
goal = Array.new(22, true)
goal[0] = false
# 15球から5つを選んだ場合の順列、全ての組み合わせに対して
billiard_ball.to_a.permutation(5).to_a.each do |combination|
# インデックス0,1,2,3,4
(0..4).each do |n|
# 数字球1つによる数字のフラグをtに
generated[ combination[n] ] = true
# 数字球2つ〃
# 配列インデックスにおいて0未満を指定すると配列末尾にアクセス
generated[ combination[n-1] + combination[n] ] = true
# 数字球3つ〃
generated[ combination[n-2] + combination[n-1] + combination[n]] = true
# 数字球4つ〃
generated[ combination[n-3] + combination[n-2] + combination[n-1] + combination[n]] = true
# 数字球5つ〃
generated[ combination[n-4] + combination[n-3] + combination[n-2] + combination[n-1] + combination[n]] = true
end
# 1-21を作れた場合、その順列を表示
p combination if generated == goal
# フラグを初期化 - すべてがFになる(笑
generated = Array.new(22, false)
end
考えた道筋
ここからはRubyの話からは逸れるので、興味のない方は 解答 をどうぞ。
僕が途中まで考えて、ギブアップしたところまでを説明します。
問題文を読んで、必須となる玉、除外しても良さそうな玉などを挙げていき、組み合わせを絞りました。詳しい解説を知りたい方は、ググって いただけると、ちゃんと数学的に解答を導き出した記事を見つけられるかもしれません。
1. ルールに沿って作ることができる数字の種類は21種類
玉1つ…5種類、隣どうし連続2つ…5種類、隣どうし連続3つ…5種類、隣どうし連続4つ…5種類、玉5つ…1種類
その為1~21を一組ずつ、重複無く作る必要が有る。
2. 1と2は必須
1と2は数字玉による組み合わせで作ることができない。よって、
使用する玉「1,2,?,?,?」
残りの玉「3,4,5,6,7,8,9,10,11,12,13,14,15」
3. 玉を5つ取った場合、最大の数字である21となる。
1と2は確定しているので、3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15から3つ選ぶ。
この3つの総計は 21 - 1 - 2 = 18 。
12を選んだとすると、残る2つにどの組み合わせを選んでも3玉の総計は18を超える。その為12は除外。
同様の理由で、13, 14, 15も除外。よって、
使用する玉「1,2,?,?,?」
残りの玉「3,4,5,6,7,8,9,10,11」
後は泥臭く……
3, 4, 5, 6, 7, 8, 9, 10, 11から3つ選び、その総計は18となる。
これを満たす組み合わせは、
(3,4,11), (3,5,10), (3,6,9), (3,7,8), (4,5,9), (4,6,8), (5,6,7) (これら3玉に1, 2が加わる。)
このうち、(5,6,7)は4を作れないので除外
残る組み合わせは
(3,4,11), (3,5,10), (3,6,9), (3,7,8), (4,5,9), (4,6,8)
ここで、3が含まれる四組は、1, 2が隣合ってはならない(∵3になってしまい、既にある3の玉と重複する)
また、4が含まれる二組は、1, 2が隣り合う必要がある(∵3を作る為)
(3,4,11)はこれらの条件を同時に満たす事が不可能であるため除外
よって、(3,5,10), (3,6,9), (3,7,8), (4,5,9), (4,6,8) にまで絞ることができる。
1,2の数字玉を足して、
(1,2,3,5,10), (1,2,3,6,9), (1,2,3,7,8), (1,2,4,5,9), (1,2,4,6,8)
となる。
ここで降参！＼(^o^)／
ここまで出せれば、行ける人は後は紙と鉛筆でも力技で行ける……かも？
僕には無理でした。
そもそも組み合わせ問題をちゃんと解ければこんなことくだくだと書く必要は無いのかも。
天王寺博士か 犀川先生 に解法を教えて頂きたいです……。
ちなみに、ここまでで使用するビリヤード玉は1, 2及び3,4,5,6,7,8,9,10から3つという事は判明したので、スクリプトのbilliard_ballから11以上の数字を消してあげると、計算量を減らしてコンピュータに楽させてあげられます。
解答
(1, 3, 10, 2, 5)
(1, 5, 2, 10, 3)
各数字の取り方は省略します。
終わりに
今年は新社会人一年目で慣れないこともありましたが、こうしてのんびりとadvent calendarに投稿できてホッとしています。
皆さん良いお年を！ 2019年も良い年になりますように。
それはそうと早く新元号知りたいですね！元モリ だったらどうしよう。