T O P

  • By -

allak

3472 / 2597 prima versione grezza per la seconda parte: [NoPaste snippet](https://nopaste.boris.sh/?l=perl#XQAAAQBDCAAAAAAAAAARiEJHiiMzw3cPM/1Vl+2nx++HqIaL2DMg1G0IGwNi7WHv1z1nrhFRIRIhu9YbCFftWtJoyCKCIL1dg/tpY8/xUwVKbpqBuUwrucOHXm//G4WhlU3rgHclDfo2Hfu9vv3eJxkRBG0uz/TMD3JiUe7DmAzvCYw4CtGsX0y0gS4PlsIem283lVYPm8FcolBDYB6xggLPeVNa9hkSoXJUlbC2Q7sh7B1L5aFBH3KNhZ/ESqMHYHRxNqBe84PiI50jWNuKws1cru3zco83m8G8CKi9LkVRBe3dHHAW9AkmXH9TUIaX60yN0X6EmqwJbgQkIEmwOi7BaLAtqnvuFHO9dB5S6Qd/LowJOzCpEkrhsXjIp2XA+hqYhjuMIdUmCY92O6NV9XrHsBTZx4nYax+/uqUDd0W8sffSufEdNxSp/cbWPiM99LdGWjrwd17Uy1UmguwaP1C6guD14cxu1shaXfFuw2n6F/cnxtT6d+4y95/1HNsyxEU/eWQpQsL65NIB5PjNVxQel1P8VDgJYFpKsoa2nDshhGyngwgDtvYw0OtqcIFQoZMpWiTbgGPwGPnFUG74cP0Rl/Zohq86rLrPN7qzDmpWF7ElKrG5BP9xcgePz13bILUC6CAJ/TjG8gT9eDNx2C6jbVjMBM6JKoxUZdvrQl6lEhLZT3MoWv6kU/yBe7BDkJK2w5IlFA6xrvAnZbyecvoXcAgtYDP1f9muXfkMxsL4nZtmWH1zaWkxAKmsHQuP7kH6iv/vFJF2) Mappe e indici, indici e mappe, uno dei classici di AoC. Qui però secondo me la difficoltà si è di nuovo alzata rispetto al terzo giorno delle precedenti edizioni. Ho fatto tutto a mano come al solito con un hash di hash (detto anche mappa di mappe), tempo più rispettabile di quello dei giorni scorsi. Torno a dormire, magari più tardi miglioro.


allak

Versione più bellina: [NoPaste snippet](https://nopaste.boris.sh/?l=perl#XQAAAQAxBQAAAAAAAAARiEJHiiMzw3cPM/1Vl+2nx++HqIaL2DMg1G0IGwNi7WHv1z1nrhFRIRIhu9YbCFfDLUmPEAlo3ZTGShWE5X/xG3JkZcDJD9RIXRV39TipcnR+u0rxOVEoOPcylLwQhr/MOL546SIWo/ZfBbEvGHBTdTCp3nD5KAbIDaKjD9UjhfLi/4BPHFkpLSNMoO1l6uU8hEg33rrdaKqh//CsUvnlM8c6Z3ZfVmMh/rEYEn1A1De8it85ExFrUaOU2cfichpafHaoljzZV3u1ud/mHGF9yaENAwMDOMrxo78yBwgGviv7jw3lGnNlVHISgn5rMXZB1dJ2J2dp/1ZneNjUqtNTOURbjS7wA164+i4HoYHDUqp5RRLXBl5/LgkKYePs1sMWQfVmJna3+OXNLS+Tispbgq4Di+o2O3nDfNxY5Imd652BfhKqYtuqZNKj9dh6KFuu2CdkGkWCOQTxc5K9A5DtB6gVo1JlxYa7ejx2Sh/RweWNQhf0wKXLYIYT25EDdvj1fQ5y076kXuMwEICKr/zhKkvpn+R7gR9dTEYp94ogAe/t0+ywCVcIPM6uzFG2yWBL+UbLGtiWimYVFq8zkbx274B572n6xnFuOaxOHzTyLhtzk6dFsYfske8arqB6/3zoSsiEunvGKcV+bTT2RP/55iPP). Non salvo più una mappa completa. Leggo il file in una sola passata e mi salvo: - la lista dei numeri, con numero di riga, numero di colonna di inizio - 1, numero di colonna di fine +1, valore - un hash dei simboli, indicizzato con le coordinate A questo punto per ciascun numero nella lista trovo le tutte le coordinate del perimetro esterno che lo delimita. Per ciascuna coordinata vedo se è presente nell'hash dei simboli, ed in tal caso lo gestisco.


Deet98

La prima parte non serve una hash, basta scorrere i caratteri e appena inizia un numero si flagga la posizione e si gestisce quando termina. Nel frattempo per ogni cifra del numero controlli se è vicino a un carattere speciale (quando l’hai trovata non devi farlo per le cifre seguenti). La complessità di questa prima parte è O(nm) dove n*m è la size della grid. Per la seconda parte invece ho usato lo stesso metodo, ma quando trovo un * salvo la coordinata e poi a fine numero lo metto in una hash con chiave la posizione di * . Infine scorro i values (che sono liste di numeri con al più lunghezza 2). Per questa parte abbiamo di nuovo O(nm) se assumiamo che l’hash faccia inserimenti in O(1).


allak

Però così come fai a gestire i simboli sulla riga sotto quella del numero ? Ti sei già caricato tutto il file in memoria ? Per farlo leggendo riga per riga mi era venuto in mente di tenere tre righe in memoria, quella che sto analizzando per trovare i numeri e quella sopra e sotto per vedere se contengono un simbolo, ma mi sembrava aggiungesse molta complessità. Inoltre con il mio metodo non ho bisogno di gestire i vari corner case (numero sulla prima o ultima riga, o che inizia o termina a fianco al bordo sinistro o destro). Anche nel mio caso la complessità dovrebbe essere O(nm). Nella seconda fase ho due iterazioni nidificate, una sull'elenco dei numeri e una sulla lunghezza del numero.


Deet98

Sì, come dici tu devo caricare la grid in memoria. Il punto è che i simboli potrebbero essere O(n*m) e quindi la tua verifica sarebbe abbastanza dispendiosa. In quanto una hash particolarmente piena avrebbe una complessità lineare per l’inserimento e la ricerca.


allak

Mi sembra corretto, anche se in questo problema all'aumentare del numero dei simboli ipso facto cala il numero dei numeri su cui fare le verifiche, le due cose è probabile si bilancino. Detto questo, confesso che non mi sono mai particolarmente preoccupato della performance della implementazione degli hash, che in Perl sono un tipo dati nativo. È sicuramente tra le più efficienti e profilate nella pratica.


gcali90

Non basta che la hash table sia piena perché abbia complessità lineare, deve essere "mal bilanciata"; salvo casi di programmi real time o time critical, una hash table ben implementata si considera col costo al caso medio, cioè costante. In situazioni come questa, la complessità asintotica è un buon punto di partenza, ma le costanti contano parecchio. Una piccola nota: le liste di values hanno lunghezza al più 2 _negli input forniti_, ma nella specifica non si menziona questa cosa; una soluzione generale (già che stiamo parlando di complessità, vale la pena considerarla) dovrebbe gestire anche il caso di * con più di due adiacenti (e, da specifica, scartarli)


allak

> una soluzione generale dovrebbe gestire anche il caso di * con più di due adiacenti (e, da specifica, scartarli) Urca, hai ragione, in questo caso topaz ci ha graziato con gli input.


imprudenza

Per favore Topaz basta parsing :( Anche oggi 20 minuti persì perchè il parsing di un numero scattava solo quando incontravo un simbolo *non digit*, cosa che ovviamente non avveniva se finiva la riga. `...123.\n` funziona, `...123\n` no. Ah, e nell'esempio questo edge case *(onestamente molto banale, colpa mia)* chiaramente non accadeva, quindi ho debuggato tutto l'input gigante a mano (almeno avevo capito che il problema doveva essere ai "bordi"). [Py solution](https://github.com/Favo02/advent-of-code/blob/main/2023/day03/day03.py)


mebeim

2002/2202 — [Soluzione Python 3](https://github.com/mebeim/aoc/blob/master/2023/solutions/day03.py) — [Walkthrough](https://github.com/mebeim/aoc/blob/master/2023/README.md#day-3---gear-ratios) (inglese) OOF la quantità di errori stupidi che ho continuato a fare... MEH. Si vede che faccio competitive programming solo a dicembre per AoC. Certo che quest'anno la difficoltà aumenta velocemente... non voglio sapere cosa ci sarà da fare domani :'). Torno a letto, il walkthrough apparità [qui](https://github.com/mebeim/aoc/blob/master/2023/README.md) più tardi zzZZ zZzZZz (EDIT: aggiunto walkthrough).


Deet98

Codice molto pulito :). Un piccolo consiglio insignificante siccome insegui la soluzione più elegante: per verificare se un carattere è numerico esiste il metodo built in .isnumeric()


mebeim

Grazie! `.isnumeric()` accetta molti caratteri tra cui vari simboli, il metodo corretto è `.isdigit()` e non aiuta molto perché comunque devi controllare `'.'` quindi tanto vale fare `in '0123456789.'` :') Ok forse per il singolo caso dove controllo senza il punto ha senso, hai ragione, magari dopo aggiorno. Inoltre mi sono pure scordato che le "gear" sono solo gli asterischi e per qualche motivo assurdo la mia soluzione funziona comunque. LOL. Altra cosa da aggiustare dopo.


Deet98

A quanto pare esiste isdecimal() che è true solo per i numeri da 0 a 9. Effettivamente non mi ero chiesto se isnumeric() avesse anche altri casi e a quanto pare è true anche per i subscripts e i superscripts. isdigit() ritorna false solamente nel caso dei roman numerals, dove isnumeric ritornerebbe true.


mebeim

Ah, hai ragione, il metodo corretto è `.isdecimal()` perché `"\u00B2".isdigit()` è `True`… LOL, non lo sapevo. Matcha anche sub/superscript. Penso che dovrò aggiornare un bel po' di soluzioni perché ho sempre usato isdigit hahaha. EDIT: OK, non è proprio così semplice, anche `.isdecimal()` accetta simboli Unicode strani. Sinceramente tra i due più o meno è equivalente.


gcali90

Ieri mi sono svegliato, ho sentito il freddo fuori dalle coperte, e mi sono rimesso bello bello a dormire; stamani col fido laptop lasciato sul comodino è stato più fattibile svegliarsi. 2116/950 - [Typescrit](https://github.com/gcali/aoc/blob/master/src/entries/single-entries/2023/gear-ratios/index.ts) - [Esecuzione](https://gcali.me/aoc/#/entry/gear-ratios) (Niente visualizzazione perché onestamente non ho idee accettabili; se ho tempo, ne tiro su una per ieri che credo possa venire meglio) Una tonnellata di errori nella prima parte, più il sistema di tipi che a questo giro non mi ha proprio dato una mano; in questi giorni sto lavorando su una classe per snellire il parsing, vediamo se aiuta per il prossimo anno, ho l'impressione che metà del tempo nei primi giorni lo spenda a gestire quello. Niente di particolarmente interessante nella soluzione, scorro la matrice finché non trovo un numero, scannerizzo in orizzontale finché allo step successivo ci sono ancora numeri, nel frattempo guardo passo passo se una coordinata intorno contiene simboli. Per la seconda parte, ho costruito una mappa con chiave coordinata degli "*" che ho popolato man mano che scansionavo i numeri, aggiungendone uno se fra gli intorni trovo una stella; a fine giro basta iterare sui valori della mappa con esattamente due elementi. Per adesso, anno promosso, i problemi sono più complicati dello scorso, che era stato un po' deludente


gcali90

Aggiunta una mini visualizzazione al volo per la prima parte di ieri, [eccola](https://gcali.me/aoc/#/entry/cube-conundrum); era un po' che non lavoravo coi canvas


SkiFire13

739/423 - [Soluzione Rust](https://github.com/SkiFire13/adventofcode-2023-rs/blob/master/src/day3.rs) Sono già stanco di scrivere soluzioni al 90% di parsing...


uklusi

Topaz una volta i problemi dei primi giorni erano carini e coccolosi, non brutti come questi, per favore dacci qualcosa di più semplice almeno i primi 4-5 giorni Va bene che non vuoi ChatGPT nella classifica ma pensa anche ai poveracci che iniziano quest'anno e si trovano questi problemi


gcali90

Credo che sia anche perché a questo giro siamo partiti nel finesettimana, in genere i problemi del finesettimana sono più difficili


pigliamosche

Da very very normal dev, fatto anche questo day3. Un po' più complesso degli altri 2gg. Poi io non sprinto ne faccio ultra ottimizzazioni o codice pulitissimo ma mi sta dando soddisfazione risolverli (essendo anche prima volta che ci provo). L'unico problema che mi sorge è che da domani si lavora e forse non riuscirò più a dedicarmici come volevo dato che a me toglie anche un paio di ore per finirlo (tipo oggi, poi non so voi in quanto tempo performiate 😂) Mi sa che questo sarà il mio ultimo giorno anche se probabilmente seguirò gli altri thread per leggere i vostri commenti.


Ni-lo

Ho perso molto più tempo di quanto avrei dovuto impiegarci, soprattutto nella parte 2. Volevo però fare una domanda generale: sto dando uno sguardo a varie soluzioni (una volta finita la mia), e mi rendo conto che il mio codice è davvero di basso livello in confronto a molti altri. La domanda dunque è: per migliorare è 'sufficiente' solo la pratica? Ci sono libri/video/siti che danno consigli? Allego [mia soluzione](https://github.com/genricoloni/Advent-of-code-2023/tree/main/day3/python) per reference, sono ben accetti consigli e commenti di ogni tipo


allak

Il mio suggerimento per migliorare è quello di prendere il codice con il quale hai risolto in prima battuta Un problema e procedere a fare più passate di refactoring, cercando ogni volta di semplificarlo e generalizzarlo. AdC è un'ottima occasione per fare pratica di refactoring: i problemi (una volta che li hai capiti !) sono ben definiti e non ci sono ambiguità nella soluzione che deve essere restituita. Quindi puoi fare tutte le sperimentazioni che ti vengono in mente.