Problem 43 - Pandigital数(2)

日本人50位になりました。数学なんてちんぷんかんぷんだった僕がここまで来れるとは思ってなかったっす。

数学おもろいっす。後は英語・・・。

またまたPandigital数。こちらはちときつい。

0〜9までの順列出して全アタック。先頭のゼロを除くと組合せ数は9!*9

アタック回数は最大7。

2千万回アタック（汗

(define (permutations s . n)
  (letrec ((remove-1 (lambda (item s)
                       (cond ((null? s) '())
                             ((equal? (car s) item) (cdr s))
                             (else (cons (car s)
                                         (remove-1 item (cdr s)))))))
           (iter (lambda (s m)
                   (if (or (zero? m) (null? s))
                       (list '())
                       (append-map (lambda (l)
                                     (map (lambda (p) (cons l p))
                                          (permutations (remove-1 l s) (- m 1))))
                                   s)))))
    (iter s (if (null? n) (length s) (car n)))))


(define (list->number l)
  (letrec ((iter (lambda (l cont)
                  (if (null? l)
                      (cont 0 0)
                      (iter (cdr l) (lambda (sum k)
                                      (cont (+ (* (car l) (expt 10 k)) sum)
                                            (+ k 1))))))))
    (iter l (lambda (sum k) sum))))

(define (problem43)
  (letrec ((primes '(2 3 5 7 11 13 17))
           (seed (iota 10))
           (test
             (lambda (l p)
               (or (null? p)
                   (and (zero? (modulo (list->number (take l 3)) (car p)))
                        (test (cdr l) (cdr p))))))
           (iter
             (lambda (n)
               (if (zero? n)
                   '()
                   (append (map (lambda (l) (cons n l))
                                (filter (lambda (l)
                                          (test l primes)) (permutations (delete n seed))))
                           (iter (- n 1)))))))
    (apply + (map list->number (iter 9)))))

(time (problem43))
; cpu time: 18566 real time: 18569 gc time: 4907
; 16695334890

18秒。結構かかる。

srfi-1を見たら、flatmapと同じ効果を持つappend-map発見。

(append-map f clist1 clist2 ...)  = (apply append (map f clist1 clist2 ...))

permutationsが微妙に短くなった。

可能性の無いものを順列生成時に絞れば早くなりそうだけど、ちょっと大変そうだ。