RubyでProject Euler - Problem 43

Problem 43 (Project Euler) [原文]

数1406357289は0から9のPandigital数である (0から9が1度ずつ現れるので). この数は部分語が面白い性質を持っている.

d1を1桁目, d2を2桁目の数とし, 以下順にdnを定義する. この記法を用いると次のことが分かる.

1. d₂d₃d₄ = 406は2で割り切れる
2. d₃d₄d₅ = 063は3で割り切れる
3. d₄d₅d₆ = 635は5で割り切れる
4. d₅d₆d₇ = 357は7で割り切れる
5. d₆d₇d₈ = 572は11で割り切れる
6. d₇d₈d₉ = 728は13で割り切れる
7. d₈d₉d₁₀ = 289は17で割り切れる

このような性質をもつ0から9のPandigital数の総和を求めよ

取りかかったのは昨日でしたが、いろいろやっているうちについ時間を過ごしてしまいました。

最初、事前の枝刈りでもしようと、ナンクロ(数独)気分で紙と鉛筆で解き始めました。すぐに d6が5であることがすぐにわかり、なんとなく正解にたどり着きました。

さすがにこれはなかろう…とコードを書きました。まず、上の各条件を単純に満たす3桁の数をそれぞれ配列に格納した後、最後の条件に合致する配列から前に向かって各要素をつなぎ合わるような操作を行いました。

各配列の様子を適宜表示させてみると、徐々に解答候補が絞り込まれていく様子がよくわかり、いかにも「プログラムが考えている」ようでした。

もっと効率のよい方法はあるのでしょうが、人間と似たような手順でありながらスタートレックNGのデータ君みたいにPCが高速に解いていくのを観察するのはなかなか楽しいものです。

ご注意

当分の間、トラックバックの受信を行わないことといたしました。過去に戴いたトラックバックのリストについてはそのまま保持いたします。

トラックバックはありません

ツムジ posted at 2009/08/02 10:14

初めまして。
私も Ruby で Project Euler を解いています。

私はこの問題を、d8d9d10 に当てはまる数の候補を配列に収めておいて、その候補に d7, d6 ... と付け加えていって候補を絞り込んでいく方法を使って、解いてみました。
最初から調べる数が少ない分、かなり速く答えが出ました。
もし、興味がおありでしたら、一度、私のブログも覗きにきてみてください。

ご注意

当分の間、JavaScript が有効でないとコメント投稿できないようにします。スパム対策であって、投稿される方の個人情報を取得する目的ではありません。悪しからずご了承ください。