对于Project Euler问题8,我被告知要通过1000位数字进行解析。这是一个强力Lisp解决方案,基本上每5个连续的数字进行一次遍历,并从开始到结束进行乘法运算,并在循环结束时返回最大的一个。
代码:
(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)))))))
它编译时没有任何警告,但运行后我得到:
no non-whitespace characters in string "73167176531330624919225119674426574742355349194934...".
[Condition of type SB-INT:SIMPLE-PARSE-ERROR]
我通过将局部函数product-of-5n
再次写入全局函数来检查它是否工作:
(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))))))
这是在没有警告的情况下编译的,并且在运行它时,似乎运行得很好。例如,
CL_USER>(5n 1产品)=>882
这似乎是正确的,因为前五位数字是7、3、1、6和7。
至于1000digits-str
,它只是用defvar
和Emacs的longlines-show-hard-newlines
编译的,我不认为字符串中有空格字符,因为这就是SBCL所抱怨的,对吧?
我不认为字符串中有空格字符,因为这就是SBCL所抱怨的,对吧?
错误消息不是抱怨空白的存在,而是抱怨非空白的不存在。但这实际上有点误导:消息应该说在要解析的特定子字符串中没有非空白。这是因为您用完了字符串的末尾,所以分析的是一个零长度的子字符串。
此外,product-of-5n
的定义也不完全正确。(product-of-5n 1)
返回前五位数字的乘积只是偶然的。字符串是从0
开始索引的,因此(product-of-5n 1)
以第二个字符开头;函数从n+0迭代到n+5,总共六个字符;所以(product-of-5n 1)
返回3×1×6×7×1×7,恰好与7×3×1?6×7?相同。
EVAL
不是一个好主意。
你的循环上限是错误的。
否则,我用数字字符串进行了尝试,结果成功了。
它也是欧拉8,而不是9。
这是我的版本:
(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)))
由于我不知道常见的lisp,我稍微修改了您的代码以适应elisp。就寻找bug而言,除了前面所说的((product-of-5n 1)
应该返回126),我唯一的评论是,在(pep8)
中,长度为-4,而不是-6(否则最后2个字符会丢失)。很抱歉,我不知道如何修复您的解析错误(我使用了string-to-number
),但以下是代码,以防您发现它有用:
(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)
返回(在前20个字符上运行时)
"73167176531330624919"
126
("next good cd" . 0)
("with corresponding lp" . 882)
("next good cd" . 3)
("with corresponding lp" . 1764)
("best ever lp" . 1764)
我前段时间做过这个问题,,在对这个问题的描述中有一件事你遗漏了。您需要将结果读取为从开始的任何偏移到一个字符串,而不仅仅是可被5整除的偏移。因此,问题的解决方案将更像以下内容:
(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)))))
这有点难看,但它说明了这个想法。
编辑对不起,我混淆了您的两个函数。所以这种说法是不正确的。