Problem 38 - Pandigital数

後で読み返してみたら、案外簡単だったり。

組合せ数が多いかと思ってたけど、そうでもなかった。

1のだけの組合せは無い。と書いてあったのでほっと一安心。回答が9876...になっちゃうのでありえないか。

安心したところで範囲を考える。

12345 24680となることは無いので、最大4桁まで見ればいい。1万 * 9回検索すればなんとかなるようだ。

後はガンガン連結。もちろん総当り検索。

(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 (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 (problem38 n)
  (letrec ((cmp (iota n 1))
           (pandigital? (lambda (l) (and (= (length l) n)
                                         (null? (lset-difference = cmp l)))))
           (search
             (lambda (m i acc)
               (let ((a (append acc (number->list (* m i)))))
                 (cond ((> (length a) n) #f)
                       ((pandigital? a) (list->number a))
                       (else
                         (search m (+ i 1) a))))))
           (iter
             (lambda (m acc)
               (if (= m 10000)
                   acc
                   (let ((res (search m 1 '())))
                     (iter (+ m 1) (if res (max res acc) acc)))))))

    (iter 1 0)))

(problem38 9) ; 932718654

ちと若い番号を攻めようかな。