Problem 8 » 履歴 » リビジョン 6
リビジョン 5 (Noppi, 2023/12/28 02:37) → リビジョン 6/8 (Noppi, 2023/12/29 10:34)
[ホーム](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 problem8-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 product-list (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 ([count (- 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)]) problem8-number-string) 13)]) (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 ([index 0] [result result]) '()]) (if (< end-pos i) count index) result (loop (add1 i) (cons (let* ([sub-num (substring substrings i problem8-number-string index (+ i 13)) index 13))] [char-lis (string->list sub-num)] [num-lis (map 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) (- (char->integer char) (char->integer #\0))) char-lis)] [product-num (apply * lis)) number-lists)) num-lis)]) (loop (add1 index) (cons product-num result))))))) (define answer-8 (apply max product-nums)) product-list)) (printf "8: ~D~%" answer-8) ```