ホーム - Project Euler

Problem 32¶

Pandigital Products¶

We shall say that an $n$-digit number is pandigital if it makes use of all the digits $1$ to $n$ exactly once; for example, the $5$-digit number, $15234$, is $1$ through $5$ pandigital.

The product $7254$ is unusual, as the identity, $39 \times 186 = 7254$, containing multiplicand, multiplier, and product is $1$ through $9$ pandigital.

Find the sum of all products whose multiplicand/multiplier/product identity can be written as a $1$ through $9$ pandigital.

HINT: Some products can be obtained in more than one way so be sure to only include it once in your sum.

パンデジタル積¶

すべての桁に 1 から n が一度だけ使われている数をn桁の数がパンデジタル (pandigital) であるということにしよう: 例えば5桁の数 15234 は1から5のパンデジタルである.

7254 は面白い性質を持っている. 39 × 186 = 7254 と書け, 掛けられる数, 掛ける数, 積が1から9のパンデジタルとなる.

掛けられる数/掛ける数/積が1から9のパンデジタルとなるような積の総和を求めよ.

ヒント: いくつかの積は, 1通り以上の掛けられる数/掛ける数/積の組み合わせを持つが1回だけ数え上げよ.

(import (scheme base)
        (gauche base)
        (scheme sort))

(define (my-permutation lis)
  (let perm-sub ([rest lis] [sub '()] [result '()])
    (if (null? rest)
      (cons (reverse sub) result)
      (fold-right (^[n result]
                    (perm-sub (delete n rest) (cons n sub) result))
                  result
                  rest))))

(define (unique lis)
  (let loop ([prev #f] [rest lis] [result '()])
    (cond
      [(null? rest) (reverse result)]
      [(and prev
            (= prev (car rest)))
       (loop prev (cdr rest) result)]
      [else
        (loop (car rest)
              (cdr rest)
              (cons (car rest) result))])))

; 有効な a * b = c のそれぞれの桁数は次の通り
; (1 4 4)
; (2 3 4)
; (3 2 4)
; (4 1 4)
; ただし、a * b = b * a なので後半は必要ない
(define pandigital-num-triplets
  (let ([perm-list (my-permutation (iota 9 1))])
    (let loop ([rest perm-list] [result '()])
      (if (null? rest)
        result
        (let* ([digital (car rest)]
               [rest (cdr rest)]
               [digital-vec (list->vector digital)]
               [a1 (vector-ref digital-vec 0)]
               [b1 (+ (* (vector-ref digital-vec 1) 1000)
                      (* (vector-ref digital-vec 2) 100)
                      (* (vector-ref digital-vec 3) 10)
                      (vector-ref digital-vec 4))]
               [c (+ (* (vector-ref digital-vec 5) 1000)
                     (* (vector-ref digital-vec 6) 100)
                     (* (vector-ref digital-vec 7) 10)
                     (vector-ref digital-vec 8))]
               [a2 (+ (* (vector-ref digital-vec 0) 10)
                      (vector-ref digital-vec 1))]
               [b2 (+ (* (vector-ref digital-vec 2) 100)
                      (* (vector-ref digital-vec 3) 10)
                      (vector-ref digital-vec 4))]
               [new-result result])
          (when (= (* a1 b1) c)
            (set! new-result (cons `(,a1 ,b1 . ,c) new-result)))
          (when (= (* a2 b2) c)
            (set! new-result (cons `(,a2 ,b2 . ,c) new-result)))
          (loop rest new-result))))))

(define pandigital-nums
  (unique
    (list-sort < (map (cut cddr <>)
                      pandigital-num-triplets))))

(define answer-32
  (apply + pandigital-nums))

(format #t "32: ~d~%" answer-32)