Quest’anno Advent of Code sarà all’insegna della AI detox. Solo il terminale, VIm, e il linguaggio di programmazione che più mi ispirerà per ogni puzzle.
- Se vi va di unirvi all’impresa, questa è la mia board:
286401-52cd12e9 - Le mie soluzioni brutte stanno qui su github.
Day 1: Secret Entrance
Gli elfi come sempre hanno fatto casino. La parte uno si risolve facile con un po’ di aritmetica delle superiori, per quanto riguarda la seconda parte ho implementato una vera coda circolare perché non son riuscito a trovre una soluzione numerica semplice.
Day 2: Gift Shop
Parte uno molto semplice, si risolve confrontando le due metà della stringa. Per la seconda parte ho implementato un algoritmo che itera sulla stringa dividendola a gruppi di dimensione crescente in base ai divisori della sua lunghezza (esempio 6, 3 2 e 1 per una stringa di lunghezza 12) e convertendoli un Set. Se il set ha cardinalità uno, la stringa non è valida.
Day 3: Lobby
Oggi è stato il primo giorno che mi ha fatto penare un po’. Per la soluzione della prima parte ho scritto due cicli annidati che fanno quel che devono fare anche se questo porta la complessità della soluzione a . Molto probabilmente esiste una soluzione più efficiente, ma comunque il codice ha girato in qualche decina di millisecondi e direi che resta così.
Sulla seconda parte si sarebbe potuto adottare lo stesso approccio, annidando ben 12 cicli. Probabilmente il programma avrebbe comunque terminato in tempi umani ma non me la sono sentita di fare una porcheria simile.
Per cui, dopo aver testato e scartato varie ipotesi su maschere binarie e permutazioni, mi è saltata in mente una struttura dati che avevo visto in qualche problema simile in passato: lo stack monotonico.
Uno stack monotonico è uno stack che mantiene gli elementi in ordine crescente o decrescente. Viene usato tipicamente per trovare il “prossimo elemento maggiore/minore” in un array con complessità , ed è perfetto per problemi che richiedono di trovare relazioni di ordine tra elementi vicini.
Siccome non ricordavo minimamente i dettagli del suo funzionamento per risolvere il problema in questione ho dovuto googlare un po’ (AI vietata quest’anno) ma alla fine, anche con la seconda parte ne siamo venuti fuori.
In sostanza il giro è il seguente:
- Definisci quanti elementi possono essere scartati. Siccome ci servono numeri di 12 cifre, avremo che
drop = len - 12cifre. - Itera su tutti gli elementi della lista da sinistra a destra
- Confronta l’elemento con quelli in cima allo stack ed eliminali fintanto che sono minori dell’elemento corrente e ci sono
dropresidui. Per ogni elemento eliminato decrementa drop. - Una volta arrivati alla fine si prendono i 12 elementi in fondo allo stack.
Sembra un po’ magia, ma funziona.
Day 4: Printing Department
Oggi è il giorno della ricerca di cose sulla griglia. Niente di troppo complicato. Probabilmente esistono metodi più efficienti per risolvere il puzzle.
Day 5: Cafeteria
Se ieri è stato semplice, oggi per niente. La prima parte è stata molto semplice ma la seconda mi ha portato via diverse ore per colpa di un edge case nei dati che non era presente nell’input di esempio.
Dopo aver raggiunto vette di frustrazione che non toccavo da tempo, l’intuizione è arrivata e anche questa parte è stata risolta.
Certo, col senno di poi avrei potuto ordinare i range e risolvere il tutto in una passata , ma quando si iniziano a overcomplicare le cose, si perdono di vista quelle semplici.
Day 6: Trash Compactor
La seconda parte mi ha causato qualche problema dopo aver pensato di rimuovere gli spazi “inutili” nella prima parte. La chiave è stata quella di immaginare l’input come un natro e scorrerlo da destra a sinistra e dall’altro al basso, applicando di volta in volta gli operatori relativi al blocco preso in considerazione.
Day 7: Laboratories
La giornata di oggi mi ha fatto dannare, infatti è stata risolta con più di un giorno di ritardo. Dopo una prima parte molto semplice, è iniziata la sagra dello stack overflow e dei tempi di esecuzione infiniti. Alla fine la via era quella di contare i path livello per livello, andando di volta in volta a sommare tutti i path che passano per un certo punto del manifold.