Ленивые последовательности, которые «смотрят в будущее» для задачи Эйлера проекта 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

Последовательность "взгляд в будущее"

Пример того, как в будущее можно смотреть в стиле фанк, может выглядеть так:

(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 и идти вверх , вам нужно принять во внимание разветвление: 10 в цепочке Коллатца может быть получен путем применения любого из правил (правило n / 2, применяемое к 20 или правило 3n + 1 начиная с 3). Кроме того, если вы хотите построить свои цепочки вверх, вы должны изменить правила и либо умножить на 2, либо вычесть 1 и разделить на 3 (применяя на каждом шаге то правило, которое дает целое число - или возможно оба, если оба делают).

Конечно, вы можете построить дерево , а не ленивый список, но это не будет похоже на набросок кода в вопросе, и я ожидаю, что вы в конечном итоге запомните вещь .

Вышеприведенное должно быть дополнено замечанием о том, что у вас может быть предположение о том, какое «правило построения цепочки» может генерировать самую длинную цепочку, начиная с 1, при этом конечная запись остается ниже заданного предела. Если это так, вы, вероятно, должны доказать, что он правильный , а затем реализовать его напрямую (через loop / recur, начиная с 1); без доказательства вы не сможете утверждать, что решили проблему.

Answer 2

Я думаю, iterate и take-while могли бы помочь (хотя этот код не смотрит в будущее):

(defn next-collatz [n]
  (cond
    (= n 1) 1
    (odd? n) (+ 1 (* 3 n))
    true (/ n 2)))

(defn collatz-seq [n]
  (iterate next-collatz n))

(defn collatz [n]
    (take-while #(not (= % 1)) (collatz-seq n)))

user> (collatz 100)
=> (100 50 25 76 38 19 58 29 88 44 22 11 34 17 52 26 13 40 20 10 5 16 8 4 2)

Answer 3

Следующее дает мне ленивую последовательность значений коллатца. Что касается микробенчмарков на моей машине, то он слегка превосходит запомненное решение. С другой стороны, он слишком рекурсивен, чтобы найти 1 миллион цепочек коллатца, и стек переполняется где-то между 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])))

Тем не менее, это все еще не то, что я хотел: та же функциональность без хэш-карты. Думая об отличном комментарии Михала и концепции построения рекурсивного дерева, я думаю, что здесь я хотел не последовательность lazy , а ленивую рекурсивную структуру данных в некотором роде, вероятно, дерево , Существуют ли такие методы передачи данных?

Моя первоначальная идея состояла в том, чтобы создать цепочки «задержек» из неизвестного значения (n), которые продолжают повторяться до тех пор, пока они не достигают известного числа (например, 1), а затем раскручиваются, заполняя ленивую структуру данных фактическими значениями в качестве рекурсии раскручивается. Если мы думаем о ленивой последовательности как о ленивом связанном списке, то я хотел получить ленивый вектор или дерево с бесконечной длиной, который бы автоматически определял зависимости данных, используя правило Коллатца. Хеш-карты было достаточно для этой задачи, но в некотором смысле это всего лишь приближение к тому, что я хотел: ленивый вектор потока данных с правилом, применяемым для заполнения элементов в векторе.

Extra Hard Challenge : Кто-нибудь может придумать способ легко представить такое ленивое дерево / вектор без использования hashmap?