Pigri sequenze che “guardare avanti” per Project Euler Problema 14

Question

Sto cercando di risolvere Project Euler Problema 14 in un pigro modo. Purtroppo, può tentare di fare l'impossibile: creare una sequenza pigro che sia pigro, ma anche in qualche modo 'guarda avanti' per i valori non è ancora calcolato.

La versione non pigro ho scritto a prova di correttezza era:

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

Il che funziona, ma è molto lento. Naturalmente potrei Memoize che:

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

Tuttavia, ciò che veramente volevo fare era grattarmi la tigna per comprendere i limiti di successioni pigri, e scrivere una funzione come questa:

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

Tirando elementi da questo causerà un overflow dello stack per n> 2, il che è comprensibile se si pensa perché ha bisogno di guardare 'al futuro' al n = 3 per conoscere il valore dell'elemento decimo posto nella lista pigro perché (+ 1 (* 3 n)) = 10.

Dato che le liste pigri hanno molto meno overhead di Memoizzazione, vorrei sapere se questo genere di cose è possibile in qualche modo, attraverso l'elaborazione ancora più ritardato o la messa in coda?

Answer 1

Di seguito mi dà una sequenza di valori pigro Collatz. Su microbenchmarks sulla mia macchina, batte leggermente la soluzione memoized. Sul fronte dei ribassi, ma anche troppo profondamente recurses per trovare 1 milione di lunghezze di catena Collatz, e lo stack overflow in qualche luogo fra il 100.000 ° ed elemento 1.000.000, ma che potrebbe essere risolto con un piccolo lavoro e 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])))

Tuttavia, non è ancora quello che volevo: questa stessa funzionalità senza la HashMap. Pensando eccellente commento di Michal e il concetto di costruzione di un albero ricorsivo, credo che quello che volevo qui non era una pigro di sequenza, ma una ricorsiva pigro datastructure di qualche tipo, probabilmente un albero. Esistono tali tecniche di flusso di dati?

La mia idea originale era quella di catene di generazione di 'ritardi' dal valore sconosciuto (n) che continuano a ricorsione fino a colpire un numero noto (come 1), e poi rilassarsi, popolando il datastructure pigro con i valori effettivi come la ricorsione snoda. Se pensiamo ad una sequenza pigro come una lista collegata pigro, quello che volevo era un pigro infinita lunghezza del vettore o albero che avrebbe trovato le sue dipendenze dei dati automaticamente utilizzando la regola Collatz. Un hashmap bastò per questo problema, ma è in un certo senso solo un'approssimazione di quello che volevo:. Un vettore flusso di dati pigro con una regola applicata su come popolare gli elementi nel vettore

Extra Hard Sfida :? Qualcuno può pensare a un modo per rappresentare facilmente ad un albero pigro / vettore senza utilizzare un HashMap

Answer 2

A ss "guardando al futuro"

Un esempio di un funky ss guardando al futuro potrebbe essere simile a questo:

(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 a chi rende questo più semplice senza romperlo: -.))

Naturalmente se la determinazione del valore di un elemento potrebbe coinvolgere guardando un elemento di "futuro" che a sua volta dipende da un ulteriore elemento che prevede il calcolo di un elemento ancora più lontano ..., la catastrofe non può essere aiutato.

Euler 14

Il problema fondamentale con lo schema di "guardare al futuro" il codice dai tentativi di domanda di impiegare parte, questo approccio non davvero risolvere il problema, perché, se si decide di iniziare da 1 and Go verso l'alto , è necessario prendere in considerazione ramificazione: un 10 in una catena Collatz potrebbe essere raggiunte attraverso l'applicazione di una regola (la regola n / 2 applicato al 20 o la regola 3n + 1 a partire dal 3). Inoltre, se si desidera costruire le vostre catene verso l'alto, è necessario invertire le regole e sia moltiplicare per 2 o 1 sottrarre e dividere per 3 (applicando, ad ogni passo, quella regola che produce un numero intero - o forse entrambi se entrambi fare) .

Naturalmente si potrebbe costruire un albero , piuttosto che un elenco pigro, ma che sarebbe non guardare qualcosa di simile al codice di schizzo nel domanda e mi aspetto di finire in ultima analisi, il memoizing cosa.

È possibile che questo deve essere qualificato con l'osservazione che si potrebbe avere una congettura su quale "catena costruzione regola" è in grado di generare la catena più lunga a partire da 1 pur avendo il soggiorno voce finale al di sotto del limite indicato. Se questo è il caso, probabilmente si dovrebbe dimostrarlo corretto e quindi implementare direttamente (tramite loop / recur a partire da 1); senza una prova, non si può davvero dire di aver risolto il problema.

Answer 3

Credo iterate e take-while potrebbero essere di qualche aiuto (anche se questo codice non guardare al futuro):

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