Oggi decisamente il giorno più difficile. Ci ho dedicato non so più quante ore (forse sei o sette nell’arco dell’intera giornata), e sono riuscito a portare a casa la seconda parte solo con un approccio più procedurale in Python. Con Wolfram, non ci sono ancora riuscito perché continuo a incepparmi in nested loop e altri costrutti simili. L’ho già detto di come, a volte, un approccio procedurale è più diretto e facile da implementare di uno purely functional. Ma voglio comunque scrivere due commenti sulla Part 1, che mi sembrano interessanti.

Date alcune regole iniziali, dobbiamo rimappare dei range di numeri su altri range. Queste remapping rules si concatenano, cioè i risultati di una diventano l’input della successiva.

La cosa un po’ strana è come vengono costruiti questi range da rimappare. Abbiamo 3 numeri: la destinazione, l’inizio, e la lunghezza. Ogni numero nel range iniziale verrà riportato nel nuovo range a partire dal valore della destinazione per tanti elementi quanti ne indica la lunghezza. Quindi, dati questi 3 numeri, per costruire dove andrà a finire ogni numero del range di partenza nel range di destinazione ci basta una cosa del genere:

buildRanges[{end_, start_, len_}] :=
 AssociationThread[start + Range[0, len - 1], end + Range[0, len - 1]]

C’è solo un piccolo problema. Cioè, molto grande in realtà. Se diamo un’occhiata all’input, ci accorgiamo che il primo set di remapping rules è questo (solo le prime righe):

seed-to-soil map:
2642418175 2192252668 3835256
2646253431 2276158914 101631202
2640809144 3719389865 1609031
2439110058 2377790116 121628096
...

La terza riga, per esempio, ci dice che il numero di elementi nei due range è circa 100 milioni. Ripeto: 100 milioni. È subito evidente che non è possibile costruire questi range in memoria. Bisogna trovare un’altra strada.

Try again

In realtà, non abbiamo bisogno di costruire gli interi intervalli. Abbiamo solo bisogno di un modo per scoprire dove un numero che appartiene all’intervallo di partenza è mappato nell’intervallo di destinazione. Inoltre, se un numero non è coperto da alcuna regola, viene restituito così com’è.

Supponiamo di avere la seguente regola: 13 101 4. Per ciascuna di queste regole dobbiamo eseguire le seguenti operazioni:

  1. Verificare se un numero $N$ è coperto da questa regola. In questo esempio, controlliamo se $0 \leq (N - 101) < 4$.

  2. Se non è coperto, si passa alla regola successiva, se ce n’è una. Se questa è l’unica regola, fine: si restituisce il valore.

  3. Se è coperto da questa regola, dobbiamo scoprire dove finisce. In questo esempio: $(N - 101) + 13$.

Ci basta questa semplice aritmetica per evitare di costruire gli interi range. Mettiamo insieme questa logica in una funzione:

lookup[n_Integer, rules_List] :=
 FirstCase[
  If[#[[2]] <= n < #[[2]] + #[[3]], #[[1]] + (n - #[[2]])] & /@
   rules, _Integer, n]

Stiamo applicando gli step sopra a tutte le regole di un certo blocco. Se il numero corrente non rientra in una regola, allora If ritorna Null. Alla fine, andiamo a prendere il primo numero intero disponibile con FirstCase. Se non ce ne sono – perché sono tutti Null – allora ritorniamo il numero stesso.

Non ho commentato il parsing. Eccolo:

parseInput[input_String] :=
 Block[{data = Flatten[StringCases[StringSplit[input, "\n\n"],
      __ ~~ ":" ~~ WhitespaceCharacter ~~ rules__ :>
       IntegerList /@ SplitLines[rules]
      ], 1], seeds, maps},
  {seeds, maps} = TakeDrop[data, 1];
  {Flatten@seeds, maps}
  ]

Nulla di speciale, importa solo la forma dell’output: due liste, una con i numeri iniziali (chiamati seeds) e con i vari blocchi di regole. Ogni blocco può contenere più di una regola (vedi lo stralcio dell’input più sopra).

La soluzione alla Part 1 è presto ottenuta:

Block[{seeds, maps},
  {seeds, maps} = parseInput[day5];
  Fold[lookup[#1, #2] &, #, maps] & /@ seeds
  ] // Min

Torna il nostro amico Fold che è incredibilmente versatile quando dobbiamo applicare più volte una funzione con argomenti sempre diversi. Il Min è semplicemente perché il puzzle ci chiede di trovare il numero più piccolo in cui viene rimappato un seed dall’ultimo blocco di regole.

Part 2

La seconda parte complica la faccenda, e non di poco. I numeri iniziali (i seeds) non sono singoli numeri, ma interi range. E anche qui si tratta di range non proprio piccoli:

seeds: 2906422699 6916147 3075226163 146720986 689152391 244427042 279234546 382175449 1105311711 2036236 3650753915 127044950 3994686181 93904335 1450749684 123906789 2044765513 620379445 1609835129 60050954

I numeri di questa prima riga vanno letti a coppie: il primo è l’inizio, mentre il secondo è il numero di elementi. Prendiamo la seconda coppia: dovrebbe contenere 146 milioni di elementi. Non saprei dire quanta memoria servirebbe per poter risolvere questa seconda parte con un approccio brute force – cioè fare uno scan dell’intero range di seed.

Anche qui, la chiave è cambiare strategia e ragionare per interi intervalli. Il punto essenziale è trovare un modo di confrontare questi intervalli e rimappare quelli necessari, senza dimenticarsi che porzioni di un intervallo potrebbero rimanere così come sono. Non dobbiamo perderci dei pezzi però!

Non ho una soluzione in Wolfram alla seconda parte, purtroppo. Non ho aggiunto una seconda ⭐ al titolo proprio per questo motivo, anche se la soluzione in Python funziona.

Ci tornerò sicuramente, ma mi sono impantanato più volte a tradurre loop in costrutti funzionali. E volevo scrivere queste due righe prima di andarmene a dormire.

Nonostante abbia risolto solo metà, è stato un puzzle assai divertente e istruttivo. E non posso che ammirare il creatore di questa challenge, Eric Wastl, che riesce a partorire queste piccole diavolerie computazionali.