Problem 62 - 立方数

Scheme

なかなかうまく解けた。


Problem 62 - PukiWiki

立方数の数字を入れ替えると、また立方数になっちゃう数を見つける。


41063625 (345^3)に対して、数字を入れ替えて探すと膨大な組合せが必要になってしまうので、ここは考え方を変えて、数字の占める数を保存しておく方法を取ってみる。

  • 41063625 (345^3)は、0が1個。1が1個。2が0個....として、ハッシュに保存しとく。
  • 56623104 (384^3)が来たら同じ組合せなので、同じハッシュに保存。
  • 66430125 (405^3)が来たら3個目なので、ループ終了。最小の値、41063625を返す。


ハッシュのキーにリストが使えるというSchemeの利点を生かしてみた。

(require (lib "1.ss" "srfi"))
(require (lib "69.ss" "srfi"))

(define (number->list n . base)
  (letrec ((b (if (null? base) 10 (car base)))
           (iter (lambda (acc n)
                   (let ((q (quotient n b))
                         (m (cons (modulo n b) acc)))
                        (if (zero? q)
                            m
                            (iter m q))))))
          (iter '() n)))

(define (problem62 n)
  (letrec ((table (make-hash-table))
           (collect-10
             (lambda (l)
               (fold-right
                 (lambda (n acc)
                   (let ((m (find (lambda (i) (= (car i) n)) acc)))
                     (set-cdr! m (+ (cdr m) 1))
                     acc))
                 (list-tabulate 10 (lambda (n) (cons n 0)))
                 l)))
           (iter
             (lambda (i)
               (let* ((cube (* i i i))
                      (cube-list (collect-10 (number->list cube)))
                      (item (cons cube (if (hash-table-exists? table cube-list)
                                           (hash-table-ref table cube-list)
                                           '()))))
                 (if (= (length item) n)
                     (apply min item)
                     (begin
                       (hash-table-set! table cube-list item)
                       (iter (+ i 1))))))))
    (iter 1)))

(problem62 2) ; 125
(problem62 3) ; 41063625
(problem62 4) ; 1006012008
(time (problem62 5))
; cpu time: 135 real time: 135 gc time: 14
; 127035954683

0.1秒。なかなかうまく解けた。