Haskell modi per il problema 3n + 1

Risponderò in Scala, perché il mio Haskell non è così nuovo, e quindi la gente crederà che questa sia una domanda generale di algoritmo di programmazione funzionale. Mi attenerò alle strutture e ai concetti di dati che sono facilmente trasferibili.

Possiamo iniziare con una funzione che genera una sequenza di collatz, che è relativamente semplice, tranne per il fatto che è necessario passare il risultato come argomento per renderlo ricorsivo in coda:

def collatz(n: Int, result: List[Int] = List()): List[Int] = {
   if (n == 1) {
     1 :: result
   } else if ((n & 1) == 1) {
     collatz(3 * n + 1, n :: result)
   } else {
     collatz(n / 2, n :: result)
   }
 }

Questo in realtà mette la sequenza in ordine inverso, ma questo è perfetto per il nostro prossimo passo, che è quello di memorizzare le lunghezze in una mappa:

def calculateLengths(sequence: List[Int], length: Int,
  lengths: Map[Int, Int]): Map[Int, Int] = sequence match {
    case Nil     => lengths
    case x :: xs => calculateLengths(xs, length + 1, lengths + ((x, length)))
}

Lo chiameresti con la risposta del primo passaggio, la lunghezza iniziale e una mappa vuota, come calculateLengths(collatz(22), 1, Map.empty)) . Questo è come si memorizza il risultato. Ora dobbiamo modificare collatz per poter usare questo:

def collatz(n: Int, lengths: Map[Int, Int], result: List[Int] = List()): (List[Int], Int) = {
  if (lengths contains n) {
     (result, lengths(n))
  } else if ((n & 1) == 1) {
    collatz(3 * n + 1, lengths, n :: result)
  } else {
    collatz(n / 2, lengths, n :: result)
  }
}

Eliminiamo il controllo n == 1 perché possiamo solo inizializzare la mappa con 1 -> 1 , ma dobbiamo aggiungere 1 alle lunghezze che abbiamo inserito nella mappa all'interno di calculateLengths . Ora restituisce anche la lunghezza memorizzata dove si è arrestata la ricorsione, che possiamo usare per inizializzare calculateLengths , come:

val initialMap = Map(1 -> 1)
val (result, length) = collatz(22, initialMap)
val newMap = calculateLengths(result, lengths, initialMap)

Ora abbiamo implementazioni relativamente efficienti dei pezzi, dobbiamo trovare un modo per alimentare i risultati del calcolo precedente nell'input del prossimo calcolo. Questo è chiamato fold , e assomiglia a:

def iteration(lengths: Map[Int, Int], n: Int): Map[Int, Int] = {
  val (result, length) = collatz(n, lengths)
  calculateLengths(result, length, lengths)
}

val lengths = (1 to 10).foldLeft(Map(1 -> 1))(iteration)

Ora per trovare la risposta effettiva, dobbiamo solo filtrare le chiavi nella mappa tra l'intervallo specificato e trovare il valore massimo, dando un risultato finale di:

def answer(start: Int, finish: Int): Int = {
  val lengths = (start to finish).foldLeft(Map(1 -> 1))(iteration)
  lengths.filterKeys(x => x >= start && x <= finish).values.max
}

Nel mio REPL per intervalli di dimensioni pari a circa 1000, come l'input di esempio, la risposta ritorna praticamente istantaneamente.

Karl Bielefeld ha già risposto bene alla domanda, aggiungerò solo una versione Haskell.

Prima una semplice versione non memoizing dell'algoritmo di base per mostrare la ricorsione efficiente:

simpleCollatz :: Int -> Int -> Int
simpleCollatz count 1 = count + 1
simpleCollatz count n | odd n     = simpleCollatz (count + 1) (3 * n + 1)
                      | otherwise = simpleCollatz (count + 1) (n 'div' 2)

Questo dovrebbe essere quasi auto-esplicativo.

Anche io userò un semplice Map per memorizzare i risultati.

-- double imports to make the namespace pretty
import           Data.Map  ( Map )
import qualified Data.Map as Map

-- a new name for the memoizer
type Store = Map Int Int

Possiamo sempre cercare i nostri risultati finali nello store, quindi per un singolo valore la firma è

memoCollatz :: Int -> Store -> Store

Iniziamo con il caso finale

memoCollatz 1 store = Map.insert 1 1 store

Sì, potremmo aggiungerlo in anticipo, ma non mi interessa. Il prossimo caso semplice, per favore.

memoCollatz n store | Just _ <- Map.lookup n store = store

Se il valore è lì, allora lo è. Ancora senza fare niente.

                    | odd n     = processNext store (3 * n + 1)
                    | otherwise = processNext store (n 'div' 2)

Se il valore non è lì dobbiamo fare qualcosa . Mettiamo l'in una funzione locale. Nota come questa parte sia molto vicina alla soluzione "semplice", solo la ricorsione è un po 'più complessa.

  where processNext store'' next | Just count <- Map.lookup next store''
                                 = Map.insert n (count + 1) store''

Ora finalmente facciamo qualcosa. Se troviamo il valore calcolato in store'' (sidenote: ci sono due evidenziatori della sintassi haskell, ma uno è brutto, l'altro viene confuso dal simbolo principale. Questo è l'unico motivo per il doppio-primo.), Abbiamo solo aggiungi il nuovo valore. Ma ora diventa interessante. Se non troviamo il valore, dobbiamo calcolarlo e fare l'aggiornamento. Ma abbiamo già funzioni per entrambi! Quindi

                                | otherwise
                                = processNext (memoCollatz next store'') next

E ora possiamo calcolare un singolo valore in modo efficiente. Se vogliamo calcolare diversi, passiamo il negozio semplicemente tramite una piega.

collatzRange :: Int -> Int -> Store
collatzRange lower higher = foldr memoCollatz Map.empty [lower..higher]

(È qui che è possibile inizializzare il caso 1/1.)

Ora tutto ciò che dobbiamo fare è estrarre il massimo. Per ora non può esserci un valore nello store superiore a uno nell'intervallo, quindi è sufficiente dire

collatzRangeMax :: Int -> Int -> Int
collatzRangeMax lower higher = maximum $ collatzRange lower higher

Ovviamente se vuoi calcolare diverse gamme e condividere lo store tra questi calcoli (le pieghe sono i tuoi amici) ti servirebbe un filtro, ma qui non è l'obiettivo principale.