Sequências preguiçosas que “olham para o futuro” para o Projeto Euler Problem 14

Question

Estou tentando resolver Projeto Euler Problema 14 de uma maneira preguiçosa. Infelizmente, posso estar tentando fazer o impossível: criar uma sequência preguiçosa que seja preguiçosa, mas também de alguma forma 'Looks Foryd' para valores que ainda não calculou.

A versão não preguiçosa que escrevi para testar a correção foi:

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

Que funciona, mas é muito lento. Claro que eu poderia memorizar isso:

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

No entanto, o que eu realmente queria fazer era arranhar minha coceira para entender os limites das seqüências preguiçosas e escrever uma função como esta:

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

Puxar elementos disso causará um excesso de pilha para n> 2, o que é compreensível se você pensar sobre por que precisa olhar 'para o futuro' em n = 3 para saber o valor do décimo elemento na lista preguiçosa porque (+ 1 (* 3 n)) = 10.

Como as listas preguiçosas têm muito menos sobrecarga do que a memórias, gostaria de saber se esse tipo de coisa é possível de alguma forma por meio de avaliação ou fila ainda mais atrasada?

Answer 1

O seguinte me dá uma sequência preguiçosa de valores de colatz. Em Microbenchmarks na minha máquina, ele supera levemente a solução memorizada. Por outro lado, ele também se destaca muito para encontrar 1 milhão de comprimentos de corrente de colatz, e a pilha transborda em algum lugar entre o 100.000 e 1.000.000 anos, mas isso pode ser resolvido com um pouco de trabalho 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])))

No entanto, ainda não é o que eu queria: essa mesma funcionalidade sem o hashmap. Pensando no excelente comentário de Michal e no conceito de construir uma árvore recursiva, acho que o que eu queria aqui não era um preguiçoso sequência, mas um recursivo preguiçoso estrutura de dados de algum tipo, provavelmente uma árvore. Essas técnicas de fluxo de dados existem?

Minha idéia original era construir cadeias de 'atrasos' a partir do valor desconhecido (n) que continuam a se repetir até atingirem um número conhecido (como 1) e depois relaxar, preenchendo a preguiçoso datacture com valores reais à medida que a recursão se desenrola. Se pensarmos em uma sequência preguiçosa como uma lista vinculada preguiçosa, o que eu queria era um vetor ou árvore preguiçoso de comprimento infinito que descobriria suas dependências de dados automaticamente usando a regra Collatz. Um hashmap foi suficiente para esse problema, mas, em certo sentido, é apenas uma aproximação do que eu queria: um vetor de fluxo de dados preguiçoso com uma regra aplicada sobre como preencher os elementos no vetor.

Desafio extra difícil: Alguém pode pensar em uma maneira de representar facilmente uma árvore/vetor preguiçoso sem usar um hashmap?

Answer 2

Um SEQ "olhando para o futuro"

Um exemplo de uma seq descolada olhando para o futuro pode ser assim:

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

(Um biscoito para quem faz isso mais simples sem quebrá-lo. :-))

Obviamente, se determinar o valor de um elemento pode envolver a análise de um elemento "futuro" que depende de um elemento adicional que exige o cálculo de um elemento ainda mais distante ..., a catástrofe não pode ser ajudada.

Euler 14

O problema fundamental com o esquema de "olhar para o futuro" o código da pergunta tenta empregar de lado, essa abordagem não resolve o problema, porque, se você decidir começar de 1 e vá para cima, você precisa se ramificar em consideração: um 10 em uma cadeia de colatz pode ser alcançada através da aplicação de qualquer regra (a n / 2 regra aplicada a 20 ou o 3n + 1 regra a partir de 3). Além disso, se você deseja construir suas correntes para cima, deve reverter as regras e multiplicar por 2 ou subtrair 1 e dividir por 3 (Aplicando, em cada etapa, essa regra que produz um número inteiro - ou possivelmente ambos, se ambos).

Claro que você poderia construir um árvore, em vez de uma lista preguiçosa, mas isso não se pareceria com o esboço do código na pergunta e eu esperaria que você acabasse por finalmente memorando a coisa.

O exposto acima deve ser qualificado com a observação de que você pode ter uma conjectura sobre qual "regra de construção de cadeia" provavelmente gerará a cadeia mais longa a partir de 1 enquanto a entrada final fica abaixo do limite fornecido. Se for esse o caso, você provavelmente deve prove correto e depois implemente -o diretamente (através loop / recur Começando às 1); Sem uma prova, você realmente não pode alegar ter resolvido o problema.

Answer 3

Eu penso iterate e take-while Pode ser de ajuda (embora esse código não olhe para o 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)