Faule Sequenzen, die „Look Ahead“ für das Projekt Euler Problem 14

Question

Ich versuche Projekt Euler Problem 14 in einem faulen zu lösen Weg. Leider kann ich das Unmögliche zu tun versuchen: eine faule Sequenz erstellen, die beide faul ist, aber auch irgendwie ‚sieht voraus‘ für Werte, die es noch nicht berechnet hat.

Die nicht-faul Version, die ich zu Test Richtigkeit schrieb, war:

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

Welche funktioniert, aber ist sehr langsam. Natürlich konnte ich memoize, dass:

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

Aber was ich wirklich wollte, war, meine Juckreiz kratzen für das Verständnis der Grenzen der faulen Sequenzen, und schreiben Sie eine Funktion wie folgt aus:

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

Elemente aus diesem Pulling wird einen Stapelüberlauf für n verursachen> 2, was verständlich ist, wenn man darüber nachdenkt, warum muss es aussehen ‚in die Zukunft‘ bei n = 3 den Wert des zehnten Elements in der faulen Liste wissen da (+ 1 (* 3 n)) = 10.

Da faul Listen haben viel weniger Overhead als memoization, würde ich gerne wissen, ob diese Art der Sache möglich ist, irgendwie über noch mehr verzögerte Auswertung oder Queueing?

Answer 1

Im Folgenden gibt mir eine faule Folge von collatz Werten. Auf Microbenchmarks auf meinem Rechner, schlägt es leicht die memoized Lösung. Auf der anderen Seite recurses es auch zu tief 1 Million collatz Kettenlängen zu finden, und der Stapel überläuft irgendwo zwischen dem 100.000sten und 1000000. Elemente, aber das könnte mit einer wenig Arbeit und recur gelöst werden.

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

Doch es ist immer noch nicht, was ich wollte: diese gleiche Funktionalität ohne die hashmap. Das Nachdenken über Michal ausgezeichneten Kommentar und das Konzept einen rekursiven Baum zu bauen, ich denke, was ich hier wollte, war nicht ein faul Sequenz, aber ein fauler rekursive Datenstruktur von einer Art, die wahrscheinlich ein Baum. Sind solche Datenfluß Techniken gibt es?

war meine ursprüngliche Idee zu bauen Ketten von ‚Verzögerungen‘ aus dem unbekannten Wert (n), die weiterhin Rekursion, bis sie eine bekannte Anzahl getroffen (wie 1), und dann Abroller, die faule Datenstruktur mit dem tatsächlichen Werten als die Rekursion bevöl abwickelt. Wenn wir von einem faulen Sequenz denken wie eine faule verknüpfte Liste zu sein, was ich wollte, war ein faules unendliche Länge Vektor oder Baum, die Abhängigkeiten seiner Daten automatisch die Collatz Regel herausfinden würde. Ein hashmap genügte für dieses Problem, aber es ist in gewissem Sinne nur eine Annäherung an, was ich wollte: a. Faul Datenfluß Vektor mit einer Regel angewandt darüber, wie die Elemente in dem Vektor zu füllen

Extra Hart Herausforderung : denken kann jemand eine Möglichkeit, auf einfache Weise darstellen, so ein faulen Baum / Vektor ohne hashmap mit

Answer 2

A seq "Blick in die Zukunft"

Ein Beispiel für eine flippige seq in die Zukunft könnte wie folgt aussehen:

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

(Ein Cookie wem auch immer macht dies einfacher, ohne sie zu brechen: -.))

Natürlich, wenn Sie den Wert eines Elements bestimmen, beinhalten könnte zu einem „Zukunft“ Element suchen, das sich auf ein weiteres Element abhängt, die für die Berechnung eines noch weiter entfernten Element ruft ..., kann die Katastrophe nicht geholfen werden.

Euler 14

Das grundlegende Problem mit dem System des „Blick in die Zukunft“ der Code aus dem Frageversuch beiseite zu beschäftigen, ist dieser Ansatz nicht löst das Problem wirklich, weil, wenn Sie von 1 beginnen entscheiden und unterwegs nach oben , müssen Sie Verzweigung berücksichtigen: a 10 in einer Collatz Kette könnte von jeder Regel (die n / 2 Regel angewandt 20 oder 3n + 1 Regel ausgehend von 3) bei durch die Anwendung angekommen werden. Auch, wenn Sie wünschen, dass Ihre Ketten nach oben zu bauen, sollten Sie die Regeln umkehren und entweder mehrfach durch 2 oder subtrahieren 1 und dividieren durch 3 (Anwendung, bei jedem Schritt, dass die Regel, die eine ganze Zahl produziert - oder möglicherweise beide, wenn beides) .

Natürlich können Sie einen Baum bauen , anstatt eine Liste faul, aber das wäre nicht so etwas wie die Code-Skizze in der Frage suchen, und ich würde erwarten, dass Sie schließlich am Ende memoizing die Sache.

Das ist oben mit der Bemerkung relativiert wird, dass Sie eine Vermutung darüber, welche „Ketten Aufbau-Regel“ ist wahrscheinlich haben könnten die längste Kette von 1 beginnen zu erzeugen, während den letzten Eintrag Aufenthalt unter der angegebenen Grenze hat. Wenn das der Fall ist, sollten Sie wahrscheinlich beweisen, dass es richtig und es dann direkt implementieren (durch loop / recur bei 1 Start); ohne Beweis, kann man nicht wirklich behaupten, das Problem gelöst zu haben.

Answer 3

Ich denke, iterate und take-while eine Hilfe sein könnten (obwohl dieser Code sieht nicht in die Zukunft):

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