2

For Project Euler Problem 8, I am told to parse through a 1000 digit number. This is a brute-force Lisp solution, which basically goes through every 5 consecutive digits and multiplies them from start to finish, and returns the largest one at the end of the loop.

The code:

(defun pep8 ()
  (labels ((product-of-5n (n)
         (eval (append '(*)
               (loop for x from n to (+ n 5)
                collect (parse-integer
                1000digits-str :start x :end (+ x 1)))))))
    (let ((largestproduct 0))
      (do ((currentdigit 0 (1+ currentdigit)))
          ((> currentdigit (- (length 1000digits-str) 6)) (return largestproduct))
        (when (> (product-of-5n currentdigit) largestproduct)
          (setf largestproduct (product-of-5n currentdigit)))))))

It compiles without any warnings, but upon running it I get:

no non-whitespace characters in string "73167176531330624919225119674426574742355349194934...".
   [Condition of type SB-INT:SIMPLE-PARSE-ERROR]

I checked to see if the local function product-of-5n was working by writing it again as a global function:

(defun product-of-5n (n)
  (eval (append '(*)
        (loop for x from n to (+ n 5)
           collect (parse-integer
                1000digits-str :start x :end (+ x 1))))))

This compiled without warnings and upon running it, appears to operate perfectly. For example,

CL_USER> (product-of-5n 1) => 882

Which appears to be correct since the first five digits are 7, 3, 1, 6 and 7.

As for 1000digits-str, it was simply compiled with defvar, and with Emacs' longlines-show-hard-newlines, I don't think there are any white-space characters in the string, because that's what SBCL is complaining about, right?

Martijn Pieters
  • 1,048,767
  • 296
  • 4,058
  • 3,343
Soyuz
  • 1,077
  • 1
  • 8
  • 16

4 Answers4

3

EVAL is not a good idea.

Your loop upper bound is wrong.

Otherwise I tried it with the number string and it works.

It's also Euler 8, not 9.

This is my version:

(defun euler8 (string)
  (loop for (a b c d e) on (map 'list #'digit-char-p string)
        while e maximize (* a b c d e)))
Rainer Joswig
  • 136,269
  • 10
  • 221
  • 346
  • This code humbles me. Would you like to explain why EVAL is not a good idea? – Soyuz Jul 19 '12 at 00:47
  • Nevermind! Just dug around and found your answer here: http://stackoverflow.com/questions/2571401/why-exactly-is-eval-evil/2571549#2571549 Thanks! – Soyuz Jul 19 '12 at 01:21
3

I don't think there are any white-space characters in the string, because that's what SBCL is complaining about, right?

The error-message isn't complaining about the presence of white-space, but about the absence of non-white-space. But it's actually a bit misleading: what the message should say is that there's no non-white-space in the specific substring to be parsed. This is because you ran off the end of the string, so were parsing a zero-length substring.

Also, product-of-5n is not defined quite right. It's just happenstance that (product-of-5n 1) returns the product of the first five digits. Strings are indexed from 0, so (product-of-5n 1) starts with the second character; and the function iterates from n + 0 to n + 5, which is a total of six characters; so (product-of-5n 1) returns 3 × 1 × 6 × 7 × 1 × 7, which happens to be the same as 7 × 3 × 1 × 6 × 7 × 1.

ruakh
  • 175,680
  • 26
  • 273
  • 307
  • When I wrote (product-of-5n 1) I knew something was wrong...but it was really late and I didn't bother trying it with 0. Thanks for elucidating what SBCL was really whining about! – Soyuz Jul 19 '12 at 00:46
0

since I don't know common lisp, I slightly modified your code to fit with elisp. As far as finding bugs go and besides what have been said ((product-of-5n 1) should return 126), the only comment I have is that in (pep8), do length-4 instead of -6 (otherwise you loose last 2 characters). Sorry that I don't know how to fix your parse-error (I used string-to-number instead), but here is the code in case you find it useful:

(defun product-of-5n (n)       ;take 5 characters from a string "1000digits-str" starting with nth one and output their product
  (let (ox)                    ;define ox as a local variable
    (eval                      ;evaluate
     (append '(*)              ;concatenate the multiplication sign to the list of 5 numbers (that are added next)
         (dotimes (x 5 ox)     ;x goes from 0 to 4 (n is added later to make it go n to n+4), the output is stored in ox
           (setq ox (cons      ;create a list of 5 numbers and store it in ox 
             (string-to-number 
              (substring 1000digits-str (+ x n) (+ (+ x n) 1) ) ;get the (n+x)th character  
              )                ;end convert char to number
             ox )              ;end cons
             )                 ;end setq
           )                   ;end dotimes, returns ox outside of do, ox has the list of 5 numbers in it
         )                     ;end append
     )                         ;end eval
    )                          ;end let
  )

(defun pep8 () ;print the highest 
  (let ((currentdigit 0) (largestproduct 0))                    ;initialize local variables
    (while  (< currentdigit  (- (length 1000digits-str) 4)    ) ;while currentdigit (cd from now on) is less than l(str)-4
      ;(print (cons "current digit" currentdigit))              ;uncomment to print cd
      (when (> (product-of-5n currentdigit) largestproduct)     ;when current product is greater than previous largestproduct (lp)
      (setq largestproduct (product-of-5n currentdigit))        ;save lp
      (print (cons "next good cd" currentdigit))                ;print cd
      (print (cons "with corresponding lp" largestproduct))     ;print lp
      )                                                         ;end when
    (setq currentdigit (1+ currentdigit))                       ;increment cd
    )                                                           ;end while
    (print (cons "best ever lp" largestproduct) )               ;print best ever lp
    )                                                           ;end let
  )

(setq 1000digits-str "73167176531330624919")
(product-of-5n 1)
(pep9)

which returns (when ran on the first 20 characters)

"73167176531330624919"
126 

("next good cd" . 0)
("with corresponding lp" . 882)

("next good cd" . 3)
("with corresponding lp" . 1764)

("best ever lp" . 1764)
alexey
  • 453
  • 6
  • 15
  • Turns out the problem was simply that the upper bound I set in product-of-5n was wrong, and length - 4 doesn't work, since I'm parsing 5 digits by 5 digits, and so length - 4 would mean I end parsing at digit 996, and I try to get to digit 1001 but I actually only have 1000. – Soyuz Jul 19 '12 at 00:55
0

I've done this problem some time ago, and there's one thing you are missing in the description of the problem. You need to read consequent as starting at any offset into a sting, not only the offsets divisible by 5. Therefore the solution to the problem will be more like the following:

(defun pe-8 ()
  (do ((input  (remove #\Newline
"73167176531330624919225119674426574742355349194934
96983520312774506326239578318016984801869478851843
85861560789112949495459501737958331952853208805511
12540698747158523863050715693290963295227443043557
66896648950445244523161731856403098711121722383113
62229893423380308135336276614282806444486645238749
30358907296290491560440772390713810515859307960866
70172427121883998797908792274921901699720888093776
65727333001053367881220235421809751254540594752243
52584907711670556013604839586446706324415722155397
53697817977846174064955149290862569321978468622482
83972241375657056057490261407972968652414535100474
82166370484403199890008895243450658541227588666881
16427171479924442928230863465674813919123162824586
17866458359124566529476545682848912883142607690042
24219022671055626321111109370544217506941658960408
07198403850962455444362981230987879927244284909188
84580156166097919133875499200524063689912560717606
05886116467109405077541002256983155200055935729725
71636269561882670428252483600823257530420752963450"))
       (tries 0 (1+ tries))
       (result 0))
      ((= tries 5) result)
    (setq result
          (max result
               (do ((max 0)
                    (i 0 (+ 5 i)))
                   ((= i (length input)) max)
                 (setq max
                       (do ((j i (1+ j))
                            (current 1)
                            int-char)
                           ((= j (+ 5 i)) (max current max))
                         (setq int-char (- (char-code (aref input j)) 48))
                         (case int-char
                           (0 (return max))
                           (1)
                           (t (setq current (* current int-char))))))))
          input (concatenate 'string (subseq input 1) (subseq input 0 1)))))

It's a tad ugly, but it illustrates the idea.

EDIT sorry, I've confused two of your functions. So that like was incorrect.