Project Euler

[ホーム](https://redmine.noppi.jp) - [[Wiki|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個の連続する数字を取り出す場合, 1*2*3*7*8と2*3*7*8*9の二通りとなり, 後者の2*3*7*8*9=3024が最大の総乗となる.

```scheme

#!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'なら次の文字をチェック

                                [(#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'だったらそれまでの数字の位置を結果に詰め込んで

                                 ; 次に有効な数字までスキップする

                                 [(#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 '()))))

;; 有効な数字の左右12文字分伸ばす

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

```