Project Euler

[ホーム](https://redmine.noppi.jp) - [[Wiki|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回だけ数え上げよ.

```scheme

(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)

```