项目欧拉问题"未来"的懒惰序列14

Question

我试图以懒惰的方式解决Project Euler Problem 14.不幸的是,我可能正在尝试做不可能的事情:创建一个既懒惰的懒惰序列,又以某种方式"向前看"尚未计算的值.

我写的测试正确性的非懒惰版本是:

(defn chain-length [num]
  (loop [len 1
         n  num]
(cond
  (= n 1) len 
  (odd? n) (recur (inc len) (+ 1 (* 3 n)))
  true     (recur (inc len) (/ n 2)))))

哪个有效,但确实很慢.当然我可以记住:

(def memoized-chain
   (memoize
     (fn [n]
       (cond
        (= n 1) 1 
         (odd? n) (+ 1 (memoized-chain (+ 1 (* 3 n))))
         true     (+ 1 (memoized-chain (/ n 2)))))))

然而,我真正想要做的是抓住我的痒,以理解延迟序列的限制,并编写如下函数:

(def lazy-chain
     (letfn [(chain [n] (lazy-seq
                         (cons (if (odd? n)
                                 (+ 1 (nth lazy-chain (dec (+ 1 (* 3 n)))))
                                 (+ 1 (nth lazy-chain (dec (/ n 2)))))
                               (chain (+ n 1)))))]
       (chain 1)))

从中拉出元素将导致n> 2的堆栈溢出,如果您考虑为什么它需要在n = 3处查看"未来"以了解惰性列表中第十个元素的值,这是可以理解的,因为(+ 1(*3 n))= 10.

由于懒惰列表的开销比备忘录少得多,我想知道这种事情是否可能以某种方式通过更加延迟的评估或排队？

Answer 1

一个seq"展望未来"

一个展望未来的时髦seq的例子可能如下所示:

(def funky-seq
     (let [substrate (atom ())]
       (letfn [(funk [n] (delay (if (odd? n) n @(nth @substrate (inc n)))))]
         (reset! substrate (map funk (range))))
       (map deref @substrate)))

user> (take 10 funky-seq)
(1 1 3 3 5 5 7 7 9 9)

(无论谁使这个更简单而不破坏它的cookie.:-))

当然,如果确定元素的值可能涉及查看"未来"元素,该元素本身依赖于需要计算更远的元素的另一个元素......,灾难就无法帮助.

欧拉14

"展望未来"方案的根本问题是试图将问题的代码放在一边,这种方法并没有真正解决问题,因为,如果你决定从头开始1 向上,你需要采取分支考虑到:10Collat​​z链中的a可能是通过应用任一规则(应用n / 2规则20或从3n + 1规则开始3)来实现的.此外,如果您希望向上构建链,则应该反转规则并乘以2或减去1除以3(在每个步骤应用产生整数的规则 - 或者如果两者都这样,则应用两者).

当然你可以构建一个树,而不是一个懒惰的列表,但这看起来不像问题中的代码草图,我希望你最终最终记住这个东西.

以上内容可以说明您可能会猜测哪条"连锁建筑规则"可能会产生最长的链条,从1最终条目低于给定限制开始.如果是这种情况,你应该证明它是正确的,然后直接实现它(通过loop/ recur开始1); 没有证据,你不能真正声称已经解决了问题.

Answer 2

下面给了我一个 collat​​z 值的惰性序列。在我的机器上的微基准测试中，它稍微击败了记忆的解决方案。不利的一面是，它递归得太深，无法找到 100 万条 collat​​z 链长度，并且堆栈在第 100,000 个和第 1,000,000 个元素之间的某个位置溢出，但这可以通过一些工作来解决recur。

 (defn collatz [n cache]
   (if-let [v (cache n)]
     [v cache]
     (let [[p cache] (if (odd? n)
                       (collatz (+ 1 (* 3 n)) cache)
                       (collatz (/ n 2) cache))]
       [(inc p) (assoc cache n (inc p))])))

 (def lazy-collatz
      (map first (iterate (fn [[v cache n]]
                            (concat (collatz n cache) [(inc n)]))
                          [1 {1 1} 2])))

然而，这仍然不是我想要的：没有哈希图的相同功能。考虑到 Michal 的出色评论和构建递归树的概念，我想我在这里想要的不是一个惰性序列，而是某种惰性递归数据结构，可能是一棵树。这样的数据流技术存在吗？

我最初的想法是从未知值 (n) 构建“延迟”链，这些延迟链继续递归，直到达到已知数字（例如 1），然后展开，在递归展开时用实际值填充惰性数据结构。如果我们将惰性序列视为惰性链表，那么我想要的是一个惰性无限长度向量或树，它可以使用 Collat​​z 规则自动找出其数据依赖性。哈希图足以解决这个问题，但从某种意义上说，它只是我想要的近似值：一个惰性数据流向量，其规则应用于如何填充向量中的元素。

额外困难的挑战：任何人都可以想出一种方法来轻松表示这样一个惰性树/向量而不使用哈希图吗？