« Project Euler - Problem 37 : 素数を作ってしまえ | トップページ | Project Euler - Problem 1 再び »

2009年4月15日 (水)

Project Euler - Problem 43 : Pandigital 数を作ってしまえ

Problem 43 は次のような問題でした。

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

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

  • d2d3d4 = 406 は 2 で割り切れる
  • d3d4d5 = 063 は 3 で割り切れる
  • d4d5d6 = 635 は 5 で割り切れる
  • d5d6d7 = 357 は 7 で割り切れる
  • d6d7d8 = 572 は 11 で割り切れる
  • d7d8d9 = 728 は 13 で割り切れる
  • d8d9d10 = 289 は 17 で割り切れる

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

まず考えるのは、10 桁の Pandigital 数を順列を使って求めて、条件に合うものをピックアップしていく方法でしょう。

でも 10 桁の Pandigital 数は、d1 に 0 が来るときも含めると、10P10 = 3628800 通りになります。まともにループを回すのはちょっと大変なので、別な方法を考えてみます。

Problem 37 の考え方を使って、条件に合う数を作ってしまいましょう。(だって、1000 未満の 17 の倍数なんて、58 個しかないんですよ)

ただし、今回は途中に "0" が来てもいいので、データを数値のまま使っていくと、桁落ちをする可能性があります。そこで、今回はデータをリストの形で保持して、必要に応じて数値に変換する方法をとりました。

(なお、「自作の手続きたち」で紹介した手続きを使用していますので、こちらも参照してみてください)

;; * lst1 から lst2 の要素を取り除く (define diff-list (lambda (lst1 lst2) (let loop ([lst1 lst1] [lst2 lst2]) (if [null? lst2] lst1 (loop (remove (car lst2) lst1) (cdr lst2)))))) (define problem-043 (lambda () (define seq-0-9 (iota 10)) ;; d8d9d10 の候補をりすとにまとめて返す。 ;; => ((0 1 7) (0 3 4) ... (9 6 9) (9 8 6)) (define make-first-list (lambda () (filter all-different? (map (lambda (n) (if [< n 100] (cons 0 (integer->list n)) (integer->list n))) (sequence 17 999 17))))) ;; 以下の条件に合う新しいリストを返す。 ;; * すべての数字が異なる ;; * リストの前から 3 個の数字をつなげたものが d で ;; 割り切れる。 (define make-new-list (lambda (lst d) (filter (lambda (ls) (zero? (remainder (list->integer (list-head ls 3)) d))) (map (lambda (n) (cons n lst)) (diff-list seq-0-9 lst))))) ;; d1 を決めて数字を完成させる。 (define finish (lambda (lst) (let ([rest (- 45 (apply + lst))]) (if [zero? rest] 0 (list->integer (cons rest lst)))))) (let loop ([lst (make-first-list)] [d-lst '(13 11 7 5 3 2)]) (if [null? d-lst] (printf "~d~%" (apply + (map finish lst))) (loop (apply append (map (lambda (ls) (make-new-list ls (car d-lst))) lst)) (cdr d-lst)))))) (problem-043)

自宅のパソコンで実行したら、REPL 上では約 0.002 秒、Shell 上でスクリプトとして実行した場合には約 0.16 秒で答えが出ました。


ちなみに、その後、順列を使って 10 桁の Pandigital 数を作っていく方法も試して見ましたが、7 秒で答えが出ました。案外速くてビックリでした。


※追記 : Ruby でコードを組んだときの手法をフィードバックしてコードを若干改良しました。(2009/08/04)

« Project Euler - Problem 37 : 素数を作ってしまえ | トップページ | Project Euler - Problem 1 再び »

Project Euler」カテゴリの記事

Scheme」カテゴリの記事

コメント

コメントを書く

コメントは記事投稿者が公開するまで表示されません。

(ウェブ上には掲載しません)

« Project Euler - Problem 37 : 素数を作ってしまえ | トップページ | Project Euler - Problem 1 再び »

2016年7月
          1 2
3 4 5 6 7 8 9
10 11 12 13 14 15 16
17 18 19 20 21 22 23
24 25 26 27 28 29 30
31            
フォト

最近のトラックバック

無料ブログはココログ