common-lisp - 将列表理解转换为 Common Lisp 循环

Question

我最近开始学习 lisp。像许多其他人一样，我正在尝试解决 Project Euler 问题，但是我有点卡在 Problem 14 上。 : 最长的 Collat​​z 序列。

这是我到目前为止:

(defun collatz (x)
  (if (evenp x) 
      (/ x 2)
      (+ (* x 3) 1)))

(defun collatz-sequence (x)
  (let ((count 1))
    (loop
     (setq x (collatz x))
       (incf count)
       (when (= x 1)
     (return count)))))

(defun result ()
  (loop for i from 1 to 1000000 maximize (collatz-sequence i)))

这将正确打印最长序列 (525)，但不会打印生成最长序列的数字。

我想要的是

result = maximum  [ (collatz-sequence n, n) | n <- [1..999999]]

如果可能，翻译成 Common Lisp。

Answer 1

在宏的帮助下并使用 iterate库，它允许您扩展其 loop -like 宏，你可以做如下的事情:

(defun collatz (x)
  (if (evenp x) (floor x 2) (1+ (* x 3))))

(defun collatz-path (x)
  (1+ (iter:iter (iter:counting (setq x (collatz x))) (iter:until (= x 1)))))

(defmacro maximizing-for (maximized-expression into (cause result))
  (assert (eq 'into into) (into) "~S must be a symbol" into)
  `(progn
     (iter:with ,result = 0)
     (iter:reducing ,maximized-expression by
      (lambda (so-far candidate)
        (if (> candidate so-far)
            (progn (setf ,result i) candidate) so-far)) into ,cause)))

(defun euler-14 ()
  (iter:iter
    (iter:for i from 1000000 downto 1)
    (maximizing-for (collatz-path i) into (path result))
    (iter:finally (return (values result path)))))

(在不要求一般性的情况下提出。:))