Project Euler: Problem 8

scheme euler

Find the greatest product of five consecutive digits in the 1000-digit number.

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

http://projecteuler.net/index.php?section=problems&id=8

1000 桁の数字の化け物の中に現れる連続する 5 つの数字の積を求めて、そのうち最大のものを答えよとのこと。問題文を読んだとき、連続する 5 つの同じ数字の積を求めよということかと勘違いしていたけど、それじゃ答えは 10 パターンしかないですね....

#!/usr/bin/env gosh

(use util.queue)
(define (main args)
  (define blob (string-append
"73167176531330624919225119674426574742355349194934"
"96983520312774506326239578318016984801869478851843"
"85861560789112949495459501737958331952853208805511"
"12540698747158523863050715693290963295227443043557"
"66896648950445244523161731856403098711121722383113"
"62229893423380308135336276614282806444486645238749"
"30358907296290491560440772390713810515859307960866"
"70172427121883998797908792274921901699720888093776"
"65727333001053367881220235421809751254540594752243"
"52584907711670556013604839586446706324415722155397"
"53697817977846174064955149290862569321978468622482"
"83972241375657056057490261407972968652414535100474"
"82166370484403199890008895243450658541227588666881"
"16427171479924442928230863465674813919123162824586"
"17866458359124566529476545682848912883142607690042"
"24219022671055626321111109370544217506941658960408"
"07198403850962455444362981230987879927244284909188"
"84580156166097919133875499200524063689912560717606"
"05886116467109405077541002256983155200055935729725"
"71636269561882670428252483600823257530420752963450"))

;;;; 連続して出現した 5 つの数字の積を求める (問題文の取り違え)
;;(let loop [(tks (string->list blob))
;;           (pre #f)
;;           (cnt 0)
;;           (lis '())]
;;  (if (pair? tks)
;;    (let [(tok (car tks))
;;          (tks (cdr tks))]
;;      (if (equal? pre tok)
;;        (let [(cnt (+ cnt 1))]
;;          (if (< cnt 5)
;;            (loop tks tok cnt lis)
;;            (loop tks #f 0 (cons (expt (digit->integer tok) 5) lis))))
;;        (loop tks tok 1 lis)))
;;    (print lis)))

;; Queue に 5 つ溜め込んで積を求めて lis に入れておく
  (define (prod5 que) ; 長さ 5 の queue から取り出して積を求める
    (fold * 1 (map digit->integer (queue->list que))))
  (let loop [(tks (string->list blob))
             (que (make-queue))
             (lis '())]
    (if (pair? tks)
      (let [(tok (car tks))
            (tks (cdr tks))]
        (if (< (queue-length que) 5)
          [begin
            (enqueue! que tok)
            (loop tks que lis)]
          (let [(prod (prod5 que))]
            (dequeue! que)
            (enqueue! que tok)
;; 次に読み込むべき token が空のときには、現在の token を事前に処理しておく
            (let [(lis (cons prod lis))]
              (loop tks que (if (null? tks)
                              (cons (prod5 que) lis)
                              lis))))))
      (print (apply max lis))))
  0)