Come sa chiunque abbia partecipato ad almeno un paio di Advent of Code, le difficoltà non sono sempre crescenti, ma piuttosto seguono un ordine calibrato dal creatore della challenge. Va detto: non sempre questa calibrazione è centrata, secondo me, ma rompe la monotonia di una progressione lineare della difficoltà. Oggi quindi si è tornati a livelli un po’ più terreni, ma non senza alcuni aspetti interessanti che vale la pena discutere.

Sempre nel tentativo di capire perché manchi l’acqua necessaria alla produzione della neve, ci imbattiamo in una competizione di imbarcazioni giocattolo. E dato che siamo competitivi – altrimenti non saremmo qui – decidiamo di iscriverci e di studiare una strategia per vincere senza troppe difficoltà. Anzitutto, diamo un’occhiata ai tempi e alle distanze record passate:

Time:      7  15   30
Distance:  9  40  200

Le unità sono irrilevanti, ma le regole di come funziona una gara no: nel tempo assegnato a ogni gara (prima riga), ogni partecipante può scegliere quando far partire la propria barca. E perché non dovrebbe farla partire subito? Perché ogni barca ha bisogno di essere caricata per acquisire una certa velocità. Più tempo la carichiamo, più veloce andrà. Però, più tempo rimarrà ferma a caricarsi, meno tempo avrà a disposizione per spostarsi. Vince chi arriva più lontano.

Nell’input sono indicate le durate e le distanze più lunghe ottenute nelle gare passate. Avendo a disposizione un certo tempo, dobbiamo capire quante combinazioni di charge time e race time ci farebbero battere un record. Anzi: dobbiamo trovare quante sono le combinazioni vincenti per ogni coppia tempo-distanza e moltiplicarle.

Per la Part 1, sono partito a testa bassa con un approccio brute force: costruire tutte le combinazioni sensate ti charge time + race time e vedere quali soddisfacevano il criterio. Ho fatto le cose sicuramente più complicate del necessario, forse spinto dal fatto che il Wolfram Language ha una quantità spropositata di metodi built-in. La standard library è davvero sconfinata.

In pratica:

  1. Ho costruito le combinazioni di due interi che sommano al valore del tempo totale della gara. Ho moltiplicato i due interi per ottenere la distanza.
  2. Ho selezionato solo quelle combinazioni la cui distanza era maggiore del valore riportato nell’input.
  3. Ho contato le combinazioni rimaste.

Ci sono due note importanti da fare. Prima: non tutte le combinazioni sono necessarie. Precisamente, solo la metà. Se la gara dura 15 secondi e carico la mia barca per 3 secondi, le rimarranno 12 secondi per spostarsi a una certa velocità. Ma se la caricassi per 12 secondi e la lasciassi andare a soli 3 secondi dalla fine, si sposterebbe comunque della stessa distanza: $v \cdot t = d$. Poiché la velocità è identica al wait time (in modulo), quel prodotto è sempre uguale.

Seconda cosa: dato che le combinazioni possibili sono il doppio di quelle ottenute (per la simmetria di cui sopra), dobbiamo moltiplicare per 2 il risultato. Attenzione però: non dobbiamo contare due volte la stessa combinazione! Ciò succede quando il tempo totale è un numero pari. Nel terzo caso dell’input sopra, $t=30$, possiamo aspettare 15 secondi e lasciare navigare la barca per i restanti 15. Ecco, queste combinazioni con due tempi identici vanno contate una sola volta. Questo piccolo problema è una conseguenza diretta del mio approccio un po’ naif.

La soluzione rimane abbastanza semplice e compatta:

With[{inputs =
   Thread@Flatten[
     StringCases[
      SplitLines@day6, __ ~~ ":" ~~ nums__ :> IntegerList@nums], 1]},
 Block[{res},
  res = MapApply[{x, y} |->
     Select[{#1, #2, #1 #2} & @@@
       IntegerPartitions[x, {2}, Range[0, x]], Last@# > y &],
    inputs];
  Apply[Times,
   2 Length@# - Count[#, {a_, b_, __} /; a == b] & /@ res]
  ]
 ]

Il parsing è la linea che assegna inputs:

Thread@Flatten[
  StringCases[
   SplitLines@ex6, __ ~~ ":" ~~ nums__ :> IntegerList@nums], 1]

Dove IntegerList è un’altra scorciatoia che ho definita io per estrarre degli interi da una stringa. Questi possono essere separati da spazi (default) o da un separatore a piacere che può essere passato come secondo argomento, e.g., IntegerList["1; 2; 3; 4", ";"]. La lista inputs è semplicemente una lista di coppie: {{7, 9}, {15, 40}, {30, 200}}, nel caso dell’esempio.

Nella soluzione sopra c’è un altro pezzetto di sintassi del Wolfram Language che è utile ripassare: il triplo @. In breve:

  • Singolo @ è uno shortcut per [___]: f[a] coincide con f@a.
  • Doppio @@ è sinonimo di Apply
  • Triplo @@@ è sinonimo di MapApply, una combinazione di Map (scorciatoia /@) e Apply di cui sopra. È talmente comune questa operazione che si merita un simbolo a parte.

C’è un’ultima osservazione da fare, forse la più importante. Il problema si può semplificare notevolmente rendendosi conto di una cosa: le soluzioni che stiamo cercando, cioè quante combinazioni dei due tempi ci farebbero vincere, si possono ottenere analiticamente. Infatti devono soddisfare la disuguaglianza $Tx-x^2 \ge D$, dove $T$ è il tempo totale e $D$ la distanza da battere. In particolare, il lato sinistro della disequazione rappresenta una parabola con concavità verso il basso, mentre il membro di destra è una retta parallela all’asse delle ascisse.

Part 2

Abbiamo letto male l’input: non si tratta di tre gare separate, ma di una sola. Le due righe riportano un solo numero, che adesso diventa un numero discretamente grande.

Torna lo spettro del Day 5, quando non potevamo salvare in memoria dei dizionari di dieci milioni (o più) di elementi. Oggi il problema è diverso, però, perché qui si tratta al più di fare un loop molto lungo, ma non abbiamo necessità di tenere in memoria alcunché di enorme.

Ci sono due approcci:

  1. Anche nel nostro input, l’intervallo di cui fare lo scan non è enorme. È grande, ma ancora gestibile. Un codice scritto in Python impiega forse un paio di secondi. Forse con un linguaggio compilato impiegherebbe anche meno.
  2. Sfruttiamo la matematica: possiamo ricavare gli estremi dell’intervallo in cui cadono le soluzioni, e poi approssimarne gli estremi agli interi più vicini. Ci basta poi fare la differenza di questi due estremi per ottenere le soluzioni. Questa seconda strada è praticamente istantanea.
Block[{t, d, sols},
 {t, d} =
  numberParse /@
   Flatten[StringCases[
     SplitLines[day6], __ ~~ ":" ~~ nums__ :>
      StringDelete[nums, " "]]];

  sols = SolveValues[x (t - x) == d, x];
  1 + Floor@Max@sols - Ceiling@Min@sols
 ]

Per curiosità, il (mio) risultato finale è 23'501'589, un numero grande sì, ma neanche così tanto in fondo. Anche il valore della distanza del mio input non è una cosa così impressionante: 241'154'910'741'091 – un numero che non so neanche leggere – oppure $2.415 \times 10^{14}$. Se pensiamo che il numero di molecole in un grammo d’acqua è circa dell’ordine di $10^{23}$ – cioè 9 ordini di grandezza di differenza – questi numeri sono ben poca cosa.