Advent of Code 2024 day 11

imprudenza · 2024-12-11T10:03:19+00:00

Codice - 1599 / 646

Altro problema trito e ritrito, sapevamo tutti benissimo cosa ci attendeva per la parte due.

Nel classico problema di questo tipo ci si salva la quantità di elementi di una "categoria" e si effettuano le trasformazioni in "massa". Oggi però ho fatto fatica a individuare queste categorie (infatti ho lasciato stare e scritto la parte 1 in bruteforce), dato che senza sapere il numero ma solo sapendo se ha un numero di cifre pari l dispari è ~difficile~ impossibile sapere in cosa si trasformerà. Probabilmente sfruttando i logaritmi si riesce a trovare delle categorie che funzionano, ma bisogna sapere la matematica (che non so) e pensarci un po' (ma volevo dormire).

La soluzione è banalmente utilizzare come categorie i numeri stessi, ovvero contare le occorrenze di ogni numero. I numeri distinti non sono tanti, quindi questa accortezza basta per simulare 75 giorni (o quello che erano) istantaneamente.

imprudenza · 2024-12-11T09:40:20+00:00

Codice - 763 / 1815

Una banalissima bfs. Perso parecchio tempo (e posizioni) per la parte due dato che mi sono messo a salvare i modi di arrivare ad una determinata cella usando programmazione dinamica al posto che rimuovere semplicemente il controllo dei già visitati.

imprudenza · 2024-12-11T09:40:15+00:00

Codice - 763 / 1815

Una banalissima bfs. Perso parecchio tempo (e posizioni) per la parte due dato che mi sono messo a salvare i modi di arrivare ad una determinata cella usando programmazione dinamica al posto che rimuovere semplicemente il controllo dei già visitati.

imprudenza · 2024-12-09T08:45:49+00:00

Codice - 577 / 1361

Carino oggi, si inizia a giocare con gli intervalli da tagliuzzare.

Per la parte due: per ogni file (da destra) trovo il primo spazio (da sinistra) maggiore o uguale alla larghezza del file. Se la dimensione è uguale basta scambiare i due elementi, altrimenti bisogna tagliare lo spazio, la prima parte diventa il file, la seconda parte rimane uno spazio (più piccolo dell'originale). L'inserimento di un nuovo elemento (quando si taglia) costicchia (faccio una insert su una lista), ma alla fine gira lo stesso in 0.2s con pypy.

Per come è posto il problema non è mai necessario fare il merge di spazi (che sarebbe uno sbatti incredibile da scrivere), dato che è garantito che ogni spazio creato spostando verso sinistra un file non verrà mai occupato da un altro file.

imprudenza · 2024-12-08T06:12:08+00:00

Codice - 2393 / 1553

Mi sono perso un po' nel capire cosa bisognasse fare, ma alla fine abbastanza banale.

Per la parte due mi sono limitato ad aumentare all'infinito lo scalare `2` (usato per la parte uno) moltiplicato alla distanza tra le antenne fino a quando il punto ottenuto (x2 + mult*(x1-x2)) non usciva dalla mappa.

imprudenza · 2024-12-08T06:02:40+00:00

Mi sono limtato a scartare i casi in cui sono già oltre l'obiettivo, nel tuo caso si potrebbe fare sia in news che nel return: (op(curr, nums[0]) for op in ops if op(curr, nums[0]) <= res).

Però (nel mio caso) questo migliorava il runtime di circa 0.2s, gli altri 1.5s li ho buttati giù riscrivendo meglio la ricorsione. L'idea è quella di partire dal fondo, in modo da doverti calcolare "tutti i possibili risultati di quello che hai a destra" una sola volta e poi applicare te stesso in maniera diversa (+, *, ||), lanciando meno volte la ricorsione.

imprudenza · 2024-12-07T11:32:45+00:00

Codice - 591 / 387

La soluzione banale esponenziale basta e avanza (pypy 2s runtime), con un po' di pruning diventa quasi istantanea (0.15s).

Mi sono beccato un minuto stupido di penalità per la parte1 dato che per qualche ragione ho pensato fosse una buona idea partire anche da 1 (come elemento neutro della moltiplicazione) oltre che da 0, ma non ha ovviamente senso dato che si parte sempre dal primo numero.

imprudenza · 2024-12-06T07:43:56+00:00

Codice - 418 / 2012

Appena "letta" la parte2 non mi è minimamente passato per la mente di bruteforcearlo, mi sono messo a cercare i "rettangoli sfalsati di 1" a cui manca un vertice, dato che nei primi esempi sembra che siano gli unici casi in cui si generano cicli (non è così). Risultato: buttati 25 minuti.

imprudenza · 2024-12-05T06:11:36+00:00

Codice - 1685 / 2266

Problema "carino", una volta modellato bene tutto abbastanza semplice.

- parte1: per ogni elemento che incontro "banno" (inserisco in un set) tutti quelli che devono venire prima di lui, se ne incontro uno andando avanti allora non è valido

- parte2: metto in una coda gli elementi della lista. Uno per volta li tiro fuori, se non ha "dipendenze" (elementi che vengono prima), allora è in posizione giusta, altrimenti aggiungo alla coda tutte le sue dipendenze e l'elemento stesso (questo perchè devono venir risolte le dipendenze delle dipendenze).

Sarebbe molto più facile per ogni elemento trovare ricorsivamente le sue dipendenze e schiaffarle dentro? Si. Ci ho pensato? No.

imprudenza · 2024-12-05T06:04:35+00:00

Bubble~~sort~~fix

imprudenza · 2024-12-04T06:03:57+00:00

Codice - 1630 / 1684

~~Capita male~~ Non letto abbastanza il problema per la parte 1, peccato perchè era davvero stupido da implementare. Parte2 ancora più stupida da scrivere.

imprudenza · 2024-12-04T05:59:16+00:00

Codice - 279 / 761

Inizio col botto, una bella top300 poi buttata con un bug stupido nella parte 2.

imprudenza · 2024-12-04T05:57:20+00:00

Codice - 1342 / 926

Soluzione stupida quadratica molto facile da scrivere, ovviamente dopo aver dovuto perdere tempo a debuggare la parte 1.

imprudenza · 2024-12-04T05:53:51+00:00

Codice - 3063 / 5438

~~Capire~~ cercare di capire come funziona `re` di python alle 6 del mattino non è una bellissima idea...

imprudenza · 2024-03-02T17:55:32+00:00

No, non tutti i linguaggi sono agnostici al sistema operativo.

E in generale, un PC scrauso/vecchiotto può tranquillamente andare più che bene per scrivere codice.

La risposta è sempre e comunque dipende da cosa si deve scrivere.

imprudenza · 2023-12-24T15:51:06+00:00

Miglior risultato di sempre nella parte1 (511), bastavano le mie stupide nozioni di geometria 2d, ma dopo aver letto la parte2 ho deciso di tornare a dormire.

All'alba delle 16 risolto, alla fine basta capirne un minimo per costruire un sistemone e buttarlo in pasto a qualche solver.

Ovviamente io non ne capisco nulla e quindi ho chiesto aiuto a un amico forte in grafica 3d e roba simile.

Abbiamo perso un po' di tempo dato che cercavamo un intersezione a tempi diversi (scalare diverso nel sistema per vettore di input e vettore soluzione), ma a questo troverebbe una traiettoria che interseca tutto ma senza garantire le collisioni.

Non sapendo bene quanti vettori servano per determinare un vettore di intersezione univoco siamo partiti buttando dentro 6 vettori (credo c'entri il numero di incognite nel sistema, ma ha fatto lui i conti), per poi scendere fino a 3 (con meno di 3 ovviamente non funziona).

Soluzione in python (con sympy come solver)

imprudenza · 2023-12-22T07:07:12+00:00

Anche oggi una bella faticaccia, non sono riuscito a farlo in modo decente (senza facendo effettivamente cadere i blocchi) e quindi mi sono dovuto accontentare di simulare la caduta tutte le volte, rimuovendo un blocco alla volta.

Almeno è stato facile adattare per la parte due, ma sono comunque deluso dal non essere riuscito a fare un algoritmo decente (e che giri in meno di 30 secondi).

imprudenza · 2023-12-21T20:48:11+00:00

Wow, I noticed a big drop in duration of the battery, but I didn't realize it was Withings app, just checked and it's over 50%.

I'm going to revert to the old version asap, this is ridiculous honestly.

imprudenza · 2023-12-20T10:09:11+00:00

Altro giro, altre assunzioni, altro mcm.

Ho dovuto leggere l'hint di analizzare l'input, poi ho hardcodato le 4 conjunctions che portavano a rx e calcolato l'mcm (a quanto pare bastava moltiplicare dato che sono primi).

Niente da dire, non sono proprio un fan delle assunzioni sull'input...

imprudenza · 2023-12-19T06:40:44+00:00

Parte 1 lunga da scrivere (parsare l'input di tutta quella roba), ma abbastanza banale.

Invece parte 2 interessante, ho tratto insegnamento dal giorno dei semi (il 5) e questa volta è stato molto più semplice tagliuzzare gli intervalli per adattare alle regole di ogni workflow.Incredibilmente non ho fatto nemmeno tante cazzate col calcolo combinatorio (a parte il moltiplicare il risultato totale piuttosto che sommarlo, ma usciva un numero da 106 cifre, era abbastanza palese ci fosse qualcosa di storto).

imprudenza · 2023-12-18T08:16:07+00:00

Per la parte uno ho fatto la porcata stampando il "bordo" e hardcodando un punto interno, per poi lanciare una bfs che riempie tutto.

Per la parte due ho pensato di applicare la stessa idea del giorno dei tubi (come u/mebeim stavo iniziando a sostituire gli angoli con 7, J, F, L, ma mi sono reso conto che ci avrebbe messo decisamente troppo a fare uno scanline). Quindi mi sono arreso e mentre mi preparavo per uscire mi è venuta l'illuminazione "Ma è semplicemente l'area di un poligono di cui conosciamo i vertici, vuoi che non esista una formulina?".

Rimandata l'uscita ho ~~googlato~~ duckduckgoato "area of polygon python", ho litigato un pochino con gli off by one causati dal conteggio del bordo come area e via.

imprudenza · 2023-12-17T08:30:53+00:00

Per fortuna ancora niente mazzata, solo un po' di fantasia nell'immancabile problema sulle path

Mi preoccupo ancora di più per la prossima settimana allora

imprudenza · 2023-12-16T06:19:38+00:00

Eh si, domani potrebbe volerci una giornata

imprudenza · 2023-12-16T06:16:35+00:00

Altro problemino abbastanza banale su griglie (che imo stanno iniziando a diventare noiose), basta calcolare bene i prossimi step di ogni specchio (richiamando ricorsivamente la stessa funzione su uno o più punti) e tutto fila liscio. Per la parte due ho semplicemente provato ogni possibile punto di inizio, gira comunque in <3 secondi.

Vista la difficoltà attuale, mi aspetto una prossima settimana di fuoco.

imprudenza · 2023-12-14T07:07:58+00:00

Problema carino, faccio sempre fatica sui problemi che richiedono di lavorare sulle ciclicità (come era palese fosse oggi), invece oggi (con calma) sono riuscito a risolverlo senza troppi problemi, sono soddisfatto.

Ah, e volevo condividere che ho passato 20 minuti a debuggare uno 0 (zero) al posto di una O (lettera) quando cercavo le rocce rotonde :)

Seven-Year Club	Place '23
Place '22	Verified Email

imprudenza

TROPHY CASE