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

```