Lazy Sequences que « regarder vers l'avenir » pour le projet Euler Problème 14

Question

Je suis en train de résoudre Projet Euler Problème 14 dans un paresseux façon. Malheureusement, je peux être en train de faire l'impossible: créer une séquence paresseuse qui est à la fois paresseux, mais aussi en quelque sorte « regarde vers l'avenir » pour les valeurs qu'il n'a pas encore calculé.

La version non paresseux je l'ai écrit à la correction du test était:

(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)))))

Ce qui fonctionne, mais il est vraiment lent. Bien sûr, je pourrais memoize que:

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

Cependant, ce que je voulais vraiment faire était gratter démangeaisons pour comprendre les limites des séquences paresseux et écrire une fonction comme ceci:

(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)))

Tirer des éléments de cela provoquera un débordement de pile pour n> 2, ce qui est compréhensible si vous pensez pourquoi il a besoin de regarder « dans l'avenir » à n = 3 pour connaître la valeur du dixième élément de la liste paresseuse parce que (1 + (* 3 n)) = 10.

Étant donné que les listes paresseux ont beaucoup moins de frais généraux que memoization, je voudrais savoir si ce genre de chose est possible en quelque sorte par l'évaluation ou faire la queue encore plus retardée?

Answer 1

Ce qui suit me donne une séquence paresseuse des valeurs de COLLATZ. Sur microbenchmarks sur ma machine, il bat légèrement la solution memoized. En revanche, il récursif aussi trop profondément pour trouver 1 million de longueurs de chaîne Collatz, et la pile déborde quelque part entre le 100.000ème et l'élément 1.000.000ème, mais qui pourrait être résolu avec un peu de travail et 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])))

Et pourtant, il est toujours pas ce que je voulais: cette même fonctionnalité sans hashmap. En pensant à un excellent commentaire de Michal et le concept de la construction d'un arbre récursif, je suppose que ce que je voulais ici était pas paresseux séquence, mais un récursive paresseux structure de données de quelque sorte, probablement un arbre. Est-ce que ces techniques existent de flux de données?

Mon idée originale était de chaînes de construction des « retards » de la valeur inconnue (n) qui continuent de récursivité jusqu'à ce qu'ils atteignent un nombre connu (comme 1), et pourrez ensuite vous détendre, peuplant la structure de données paresseuse avec des valeurs réelles comme la récursion dénouements. Si nous pensons à une séquence paresseuse comme une liste chaînée paresseuse, ce que je voulais était un vecteur de longueur infinie paresseuse ou un arbre qui trouverait ses dépendances de données automatiquement en utilisant la règle Collatz. Un hashmap suffisaient à ce problème, mais il est seulement dans un certain sens une approximation de ce que je voulais:. Un vecteur de flux de données paresseux avec une règle appliquée sur la façon de remplir les éléments dans le vecteur

Défi extra dur : Quelqu'un peut-il penser à une façon de représenter facilement un tel arbre / vecteur paresseux sans utiliser hashmap

Answer 2

A suivants "regarder vers l'avenir"

Un exemple d'un seq funky dans l'avenir pourrait ressembler à ceci:

(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)

(Un cookie à celui qui rend ce simple sans le casser: -.))

Bien sûr, si la détermination de la valeur d'un élément pourrait consister à examiner un élément « futur », qui dépend lui-même un autre élément qui appelle pour le calcul d'un élément encore plus lointain ..., la catastrophe ne peut pas être aidé.

Euler 14

Le problème fondamental avec le système de « regarder vers l'avenir » le code des tentatives de question d'employer de côté, cette approche ne résout pas vraiment le problème, parce que, si vous décidez de partir 1 et aller vers le haut , vous devez prendre en compte de branchement: un 10 dans une chaîne Collatz pourrait être arrivé à travers l'application de l'une règle (la règle de n / 2 appliquée à 20 ou la règle de 3n + 1 à partir de 3). En outre, si vous souhaitez construire vos chaînes vers le haut, vous devez inverser les règles et soit multiplier par 2 ou Soustraire 1 et diviser par 3 (application, à chaque étape, cette règle qui produit un entier - ou peut-être deux si les deux faire) .

Bien sûr, vous pouvez construire une arbre , plutôt qu'une liste paresseuse, mais cela ne ressemblera en rien l'esquisse de code dans la question et je vous attendre à finir memoizing finalement le chose.

Ce qui précède doit être qualifié avec la remarque que vous pourriez avoir une conjecture à laquelle « règle de construction chaîne » est susceptible de générer la plus longue chaîne à partir de 1 tout en ayant le séjour d'entrée finale en dessous de la limite donnée. Si tel est le cas, vous devriez probablement prouvez correct , puis mettre en œuvre directement (par loop / recur à partir de 1); sans preuve, vous ne pouvez pas vraiment prétendre avoir résolu le problème.

Answer 3

Je pense que iterate et take-while pourraient être d'une certaine aide (bien que ce code ne semble pas dans l'avenir):

(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)