ホーム - Project Euler

Problem 8¶

Largest Product in a Series¶

The four adjacent digits in the $1000$-digit number that have the greatest product are $9 \times 9 \times 8 \times 9 = 5832$.

73167176531330624919225119674426574742355349194934
96983520312774506326239578318016984801869478851843
85861560789112949495459501737958331952853208805511
12540698747158523863050715693290963295227443043557
66896648950445244523161731856403098711121722383113
62229893423380308135336276614282806444486645238749
30358907296290491560440772390713810515859307960866
70172427121883998797908792274921901699720888093776
65727333001053367881220235421809751254540594752243
52584907711670556013604839586446706324415722155397
53697817977846174064955149290862569321978468622482
83972241375657056057490261407972968652414535100474
82166370484403199890008895243450658541227588666881
16427171479924442928230863465674813919123162824586
17866458359124566529476545682848912883142607690042
24219022671055626321111109370544217506941658960408
07198403850962455444362981230987879927244284909188
84580156166097919133875499200524063689912560717606
05886116467109405077541002256983155200055935729725
71636269561882670428252483600823257530420752963450

Find the thirteen adjacent digits in the $1000$-digit number that have the greatest product. What is the value of this product?

数字列中の最大の積¶

次の1000桁の数字のうち, 隣接する4つの数字の総乗の中で, 最大となる値は, 9 × 9 × 8 × 9 = 5832である.

73167176531330624919225119674426574742355349194934
96983520312774506326239578318016984801869478851843
85861560789112949495459501737958331952853208805511
12540698747158523863050715693290963295227443043557
66896648950445244523161731856403098711121722383113
62229893423380308135336276614282806444486645238749
30358907296290491560440772390713810515859307960866
70172427121883998797908792274921901699720888093776
65727333001053367881220235421809751254540594752243
52584907711670556013604839586446706324415722155397
53697817977846174064955149290862569321978468622482
83972241375657056057490261407972968652414535100474
82166370484403199890008895243450658541227588666881
16427171479924442928230863465674813919123162824586
17866458359124566529476545682848912883142607690042
24219022671055626321111109370544217506941658960408
07198403850962455444362981230987879927244284909188
84580156166097919133875499200524063689912560717606
05886116467109405077541002256983155200055935729725
71636269561882670428252483600823257530420752963450

この1000桁の数字から13個の連続する数字を取り出して, それらの総乗を計算する. では、それら総乗のうち、最大となる値はいくらか.
EX 6桁の数123789から5個の連続する数字を取り出す場合, 12378と23789の二通りとなり, 後者の23789=3024が最大の総乗となる.

#!r6rs
#!chezscheme

(import (chezscheme))

(define p8-number-string
  (string-append "73167176531330624919225119674426574742355349194934"
                 "96983520312774506326239578318016984801869478851843"
                 "85861560789112949495459501737958331952853208805511"
                 "12540698747158523863050715693290963295227443043557"
                 "66896648950445244523161731856403098711121722383113"
                 "62229893423380308135336276614282806444486645238749"
                 "30358907296290491560440772390713810515859307960866"
                 "70172427121883998797908792274921901699720888093776"
                 "65727333001053367881220235421809751254540594752243"
                 "52584907711670556013604839586446706324415722155397"
                 "53697817977846174064955149290862569321978468622482"
                 "83972241375657056057490261407972968652414535100474"
                 "82166370484403199890008895243450658541227588666881"
                 "16427171479924442928230863465674813919123162824586"
                 "17866458359124566529476545682848912883142607690042"
                 "24219022671055626321111109370544217506941658960408"
                 "07198403850962455444362981230987879927244284909188"
                 "84580156166097919133875499200524063689912560717606"
                 "05886116467109405077541002256983155200055935729725"
                 "71636269561882670428252483600823257530420752963450"))

(define erase-zero-range-vector
  (let* ([work (list->vector (string->list p8-number-string))]
         [work-length (vector-length work)])
    (letrec ([skip-zero-range (lambda (pos)
                                (cond
                                  ; 終端まで到達したら結果を返す
                                  [(<= work-length pos) work]
                                  ; ゼロが見つかったら
                                  ; 左と右をそれぞれ12文字埋める
                                  [(char=? (vector-ref work pos) #\0)
                                   (erase-left (sub1 pos))
                                   (erase-right (add1 pos))]
                                  ; ゼロ以外なら次の文字を探す
                                  [else (skip-zero-range (add1 pos))]))] 
             [erase-left (lambda (pos)
                           (let loop ([i 0])
                             (let ([current-pos (- pos i)])
                               (cond
                                 ; 先頭まで到達したら終了
                                 [(negative? current-pos) void]
                                 ; ゼロ含めて13文字埋めたら終了
                                 [(<= 12 i) void]
                                 ; #fでなかったら#fで埋めてさらに左を調べる
                                 [(vector-ref work current-pos)
                                  (vector-set! work current-pos #f)
                                  (loop (add1 i))]
                                 ; #fまで到達したら終了
                                 [else void]))))]
             [erase-right (lambda (pos)
                            (let loop ([i 0])
                              (let ([current-pos (+ pos i)])
                                (cond
                                  ; 終端まで到達したら結果を返す
                                  [(<= work-length current-pos) work]
                                  ; ゼロ含めて13文字埋めたので次の文字を探す
                                  [(<= 12 i) (skip-zero-range (add1 current-pos))]
                                  ; ゼロが見つかったらそこからさらに13文字埋める
                                  [(char=? (vector-ref work current-pos) #\0)
                                   (erase-right (add1 current-pos))]
                                  ; ゼロでなかったら#fで埋めてさらに右を調べる
                                  [else
                                    (vector-set! work current-pos #f)
                                    (loop (add1 i))]))))])
      (skip-zero-range 0))))

(define rest-substring-pos
  (let ([work-length (vector-length erase-zero-range-vector)])
    (letrec ([skip-char (lambda (pos reverse-result)
                          (if (<= work-length pos)
                            (reverse reverse-result)
                            (let ([current-char (vector-ref erase-zero-range-vector pos)])
                              (case current-char
                                [(#f #\0) (skip-char (add1 pos) reverse-result)]
                                [else (valid-char (add1 pos) pos reverse-result)]))))]
             [valid-char (lambda (pos start-pos reverse-result)
                           (if (<= work-length pos)
                             (reverse (cons
                                        (cons start-pos (sub1 pos))
                                        reverse-result))
                             (let ([current-char (vector-ref erase-zero-range-vector pos)])
                               (case current-char
                                 [(#f #\0)
                                  (skip-char (add1 pos)
                                             (cons (cons start-pos (sub1 pos))
                                                   reverse-result))]
                                 [else (valid-char (add1 pos)
                                                   start-pos
                                                   reverse-result)]))))])
      (skip-char 0 '()))))

(define valid-substring-pos
  (let ([p8-string-length (string-length p8-number-string)])
    (map
      (lambda (cell)
        (cons (max 0 (- (car cell) 12))
              (min (sub1 p8-string-length) (+ (cdr cell) 12))))
      rest-substring-pos)))

(define valid-substrings
  (map
    (lambda (cell)
      (substring p8-number-string
                 (car cell)
                 (add1 (cdr cell))))
    valid-substring-pos))

(define 13-length-strings
  (reverse
    (fold-left
      (lambda (result substrings)
        (let ([end-pos (- (string-length substrings) 13)])
          (let loop ([i 0] [result result])
            (if (< end-pos i)
              result
              (loop (add1 i)
                    (cons (substring substrings i (+ i 13))
                          result))))))
      '()
      valid-substrings)))

(define number-lists
  (map
    (lambda (substrings)
      (map
        (lambda (char)
          (char- char #\0))
        (string->list substrings)))
    13-length-strings))

(define product-nums
  (map
    (lambda (lis) (apply * lis))
    number-lists))

(define answer-8
  (apply max product-nums))

(printf "8: ~D~%" answer-8)