/u/22283/crop5e2c64c410533.png?f=community)
- challenge-1.txt: OK 22s 2,6s.
- challenge-2.txt: OK 1070s.
- challenge-3.txt: Geen zin om zo lang te wachten.
Het schaalt momenteel in ieder geval mooi kl*te met het aantal bakstenen.
Siditamentis astuentis pactum.
Het schaalt momenteel in ieder geval mooi kl*te met het aantal bakstenen.
:strip_exif()/u/11775/SoulTaker.gif?f=community)
Ah ja, zou kunnen dat dat dag 20 was. We hebben ook nog maar 2½ dag te gaan dus een hele set van puzzels zoals met IntCode zit er sowieso niet in.
Niet slecht! Ik moest mijn oorspronkelijke oplossing ook aanzienlijk verbeteren om deze problemen op te kunnen lossen (zonder optimalisaties doet 'ie net challenge-1.txt in 1 minuut). Het is ook de bedoeling om je een beetje uit te dagen je oplossing sneller en meer solide te maken, en zoals je terecht opmerkt, zijn er bij dit probleem veel plekken waar je makkelijk veel snelheidswinst kunt behalen. Dat maakt het een leuk probleem naar mijn mening.:Eerst ging mijn oplossing stuk. Er zat nog een domme typefout in. Daarna heb ik de boel versneld door de baksteen met zijn stukje vloer te vergelijken ipv de hele vloer met de baksteen. Daardoor kon ik challenge 1 überhaupt in eindige tijd uitvoeren. Zo te zien valt er nog vééééél meer te optimaliseren.
- challenge-1.txt: OK 22s 2,6s.
- challenge-2.txt: OK 1070s.
- challenge-3.txt: Geen zin om zo lang te wachten.
[ Voor 16% gewijzigd door Soultaker op 22-12-2023 18:35 ]
Challenge 1 werkt (nadat ik eerst deel 1 een stuk sneller had gemaakt, niet meer 1 per keer droppen, maar netjes bijhouden hoever je naar beneden kunt vallen en direct daar neer zetten). Had eerst nog een off-by-one error in deel 2 die ik blijkbaar niet triggerde in de officiele invoer. Tijd voor challenge 1 is niet geweldig, 40,4 s.
Challenge 2 gooit een OOM bij het alloceren van de initiele array voor de posities
Misschien ga ik eens van de kerstvakantie wat optimaliseren, maar voor vandaag houd ik het voor gezien, elke dag om 6 uur opstaan bouwt de vermoeidheid aardig op.
Denk dat ik mijn graafalgoritme nog kan verbeteren als ik bijvoorbeeld een topological sort toepas en gelijk afbreek als ik te laag in de graaf zit o.i.d. En natuurlijk een nette DP oplossing, i.p.v. mijn gare memoization (ik besef me nu dat ik de in de memoization key ook de node die ik disintegrate zet, waardoor ik alles opnieuw bereken voor elke disintegrated node...
)
[ Voor 13% gewijzigd door FCA op 22-12-2023 20:36 ]
Verandert z'n sig te weinig.
Dag 25 is meestal relatief simpel (en sowieso maar 1 deel). Maar een cellular automaton zou best kunnen voor morgen of overmogen! Iedereen heeft zijn Hashlife implementatie klaar hoop ik?
Ah, jammer. Op basis van je beschrijving vermoedde ik dat je een meer geavanceerd algoritme had geïmplementeerd.:
Challenge 1 werkt (nadat ik eerst deel 1 een stuk sneller had gemaakt, niet meer 1 per keer droppen, maar netjes bijhouden hoever je naar beneden kunt vallen en direct daar neer zetten). Had eerst nog een off-by-one error in deel 2 die ik blijkbaar niet triggerde in de officiele invoer. Tijd voor challenge 1 is niet geweldig, 40,4 s.
Challenge 2 gooit een OOM bij het alloceren van de initiele array voor de posities
Ja, ik begin dat ook wel zat te worden
Nog een paar dagen doorbikkelen...
:strip_icc():strip_exif()/u/12461/crop65b195553d948.jpg?f=community)
Day22 in Rust
Superweinig tijd gehad, gelukkig een simpele opdracht.
.edit:
Superweinig tijd gehad, gelukkig een simpele opdracht.
spoiler:
Mijn implementatie is niet heel efficient. Ik weet dat ik voor deel 2 zou kunnen bijhouden welke stenen er vallen en dan van boven naar onderen kan werken en zo niet steeds dingen opnieuw zou hoeven uitrekenen, maar daar had ik even geen zin in. Wellicht dat ik dat later nog eens implementeer. Ook gebruik ik een fixed size 10x10 grid dus die sets van @Soultaker gaan 'm sowieso niet worden 
.edit:
spoiler:
Heh, nu ik de reacties van vandaag teruglees blijkt dat ik het voor deel 1 van meet af aan toch een stuk efficiënter heb geïmplementeerd dan velen hier 
[ Voor 23% gewijzigd door .oisyn op 22-12-2023 23:44 ]
Give a man a game and he'll have fun for a day. Teach a man to make games and he'll never have fun again.
Ik heb van mijn statische array even een hashmap gemaakt zodat ik iig je challenges kan runnen, maar ik krijg voor deel 2 de juiste antwoorden, terwijl ik voor deel 1 iets anders krijg (resp. 74 en 2)
spoiler:
Mijn volledige antwoorden voor challenge 1 zijn 3760 en 175572
Running tijd is trouwens 10,9ms en 50,9s
.edit: oh interessant, als ik de sort vervang door een unstable sort dan krijg ik andere antwoorden voor challenge 1.
.edit2: ah, je hebt een foutje in je data. Heb even een test ingebouwd.
code:
1
| bricks ((72, 83, 758), (72, 83, 792)) and ((59, 83, 787), (92, 83, 787)) overlap |
.edit3: oh shit dat is bij lange na niet de enige overlap
. code:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| bricks ((72, 83, 758), (72, 83, 792)) and ((59, 83, 787), (92, 83, 787)) overlap bricks ((72, 54, 1848), (72, 54, 1881)) and ((65, 54, 1852), (97, 54, 1852)) overlap bricks ((72, 53, 2673), (72, 92, 2673)) and ((56, 62, 2673), (99, 62, 2673)) overlap bricks ((78, 73, 2896), (78, 73, 2942)) and ((78, 62, 2913), (78, 75, 2913)) overlap bricks ((73, 70, 2912), (73, 93, 2912)) and ((73, 79, 2912), (73, 79, 2900)) overlap bricks ((56, 80, 5671), (56, 80, 5698)) and ((56, 53, 5684), (56, 103, 5684)) overlap bricks ((89, 66, 6167), (89, 86, 6167)) and ((65, 78, 6167), (92, 78, 6167)) overlap bricks ((53, 82, 6293), (53, 82, 6336)) and ((53, 68, 6318), (53, 114, 6318)) overlap bricks ((60, 63, 7124), (60, 63, 7128)) and ((60, 56, 7125), (60, 71, 7125)) overlap bricks ((97, 87, 7134), (97, 87, 7180)) and ((97, 59, 7172), (97, 98, 7172)) overlap bricks ((94, 73, 7241), (94, 73, 7285)) and ((66, 73, 7265), (98, 73, 7265)) overlap bricks ((87, 73, 7250), (87, 73, 7288)) and ((66, 73, 7265), (98, 73, 7265)) overlap bricks ((82, 62, 7882), (82, 62, 7901)) and ((82, 60, 7883), (82, 101, 7883)) overlap bricks ((95, 57, 7916), (95, 106, 7916)) and ((95, 58, 7916), (95, 58, 7931)) overlap bricks ((89, 78, 8251), (89, 78, 8271)) and ((89, 77, 8263), (89, 97, 8263)) overlap bricks ((58, 69, 8326), (95, 69, 8326)) and ((63, 69, 8326), (63, 69, 8280)) overlap bricks ((57, 99, 9362), (57, 99, 9406)) and ((57, 99, 9363), (74, 99, 9363)) overlap bricks ((89, 65, 10702), (89, 112, 10702)) and ((72, 86, 10702), (98, 86, 10702)) overlap bricks ((78, 64, 11139), (78, 64, 11163)) and ((78, 51, 11152), (78, 69, 11152)) overlap bricks ((54, 90, 11493), (54, 90, 11537)) and ((52, 90, 11536), (75, 90, 11536)) overlap bricks ((85, 52, 12515), (85, 52, 12537)) and ((68, 52, 12532), (85, 52, 12532)) overlap bricks ((85, 100, 14102), (85, 100, 14134)) and ((67, 100, 14126), (117, 100, 14126)) overlap |
Ook heb je heel veel negatieve z-coordinaten er in staan. Dat lijkt me onjuiste data, want de puzzel tekst heeft het erover dat de grond zich op z=0 bevindt, dus dan zouden er stenen door de grond zijn gezakt.
2 en 3 valideren wel volgens mijn check.
.edit4: challenge 2 nu in 18s.
[ Voor 63% gewijzigd door .oisyn op 23-12-2023 02:52 ]
Give a man a game and he'll have fun for a day. Teach a man to make games and he'll never have fun again.
Give a man a game and he'll have fun for a day. Teach a man to make games and he'll never have fun again.
Lekker niet om 6 uur opgestaan, maar ik lach me een aap: "vind het langste pad".
Siditamentis astuentis pactum.
Pfff...
Deel 1:
Deel 2 was weer een killer voor mij
Deel 1:
spoiler:
Gewoon brute force proberen, recursief met het gelopen pad bijhouden in een set. Werkt niet bijster snel, maar wel goed genoeg. Redelijk snel geimplementeerd, positie < 1000.
Deel 2 was weer een killer voor mij
spoiler:
Brute force vergelijkbaar met deel 1 (maar dus meer toegestane transities) werd hem niet binnen een minuut, dus alternatieven zoeken. Zoals al eerder opgemerkt, graafalgoritmes zijn niet mijn sterkste punt, dus dat schept geen hoge verwachtingen.
Na veel zoeken kom ik erachter dat het waarschijnlijk NP compleet is, dus ik ga zoeken naar speciale eigenschappen van de graaf. Half uurtje prutsen voor ik een fatsoenlijke plaatje van de graaf kan maken (graphviz, pygraphviz en Windows lopen niet lekker samen).
Blijkt dat de graaf uit veel a_1 <-> a_2 <-> ... <-> a_n rijen bestaat. Dat kunnen we versimpelen naar a_1 <-> a_n met gewicht n.
Recursief op de versimpelde graaf blijkt te werken. Nog steeds niet snel (het blijft brute-force), maar de graaf heeft nog maar 36 edges, dan gaat het blijkbaar net (net even gecheckt: 1.262.816 unieke paden om te checken, maar er zijn natuurlijk nog veel meer doodlopende/in zichzelf kerende paden)
BTW: mijn gereduceerde graaf:
/f/image/0QwmO9lHe86YVUHEnnRz8Tt1.png?f=fotoalbum_large)
Na veel zoeken kom ik erachter dat het waarschijnlijk NP compleet is, dus ik ga zoeken naar speciale eigenschappen van de graaf. Half uurtje prutsen voor ik een fatsoenlijke plaatje van de graaf kan maken (graphviz, pygraphviz en Windows lopen niet lekker samen).
Blijkt dat de graaf uit veel a_1 <-> a_2 <-> ... <-> a_n rijen bestaat. Dat kunnen we versimpelen naar a_1 <-> a_n met gewicht n.
Recursief op de versimpelde graaf blijkt te werken. Nog steeds niet snel (het blijft brute-force), maar de graaf heeft nog maar 36 edges, dan gaat het blijkbaar net (net even gecheckt: 1.262.816 unieke paden om te checken, maar er zijn natuurlijk nog veel meer doodlopende/in zichzelf kerende paden)
BTW: mijn gereduceerde graaf:
:fill(white):strip_exif()/f/image/0QwmO9lHe86YVUHEnnRz8Tt1.png?f=user_large)
[ Voor 18% gewijzigd door FCA op 23-12-2023 09:46 ]
Verandert z'n sig te weinig.
Give a man a game and he'll have fun for a day. Teach a man to make games and he'll never have fun again.
86 74 hier
Give a man a game and he'll have fun for a day. Teach a man to make games and he'll never have fun again.
Ok, hier is mijn debug uitvoer. Wijs maar een blok aan dat ik ten onrechte heb gemarkeerd als “NOT safe to remove”:
86 74 hier
Ik was vanochtend ook helemaal niet wakker (nu nog nauwelijks) en heb ontzettend zitten prutsen. Sterker nog, de aanpak die jij beschrijft had ik al bij deel 1 gebruikt (wat natuurlijk volslagen overkill was, dom!) en dan zou je denken: dan was deel 2 zeker makkelijk. Ja, ware het niet dat ik op de een of andere manier bedacht had dat
spoiler:
je elke edge in de graaf maar 1 keer mag bezoeken, maar elke vertex meerdere keren. Dat is een heel ander probleem!
En ook plaatjes gemaakt van de graaf:
(De kleuren geven aan of een vertex een even of oneven aantal buren heeft. Dat heb je nergens voor nodig.)
edit: de plaatjes kloppen niet eens
Dit zijn de correcte versies:
Voorbeeld deel 1 / 2:
Officiële invoer deel 1 / 2:
En ook plaatjes gemaakt van de graaf:
(De kleuren geven aan of een vertex een even of oneven aantal buren heeft. Dat heb je nergens voor nodig.)
edit: de plaatjes kloppen niet eens
Dit zijn de correcte versies:Voorbeeld deel 1 / 2:
Officiële invoer deel 1 / 2:
Uiteindelijk hetzelfde gedaan als jij, maar ook een teleurstellende runtime simpelweg vanwege het grote aantal mogelijkheden. Nog even nadenken of dat efficiënter kan. Overigens is het in z'n algemeenheid wel een NP-compleet probleem.
[ Voor 23% gewijzigd door Soultaker op 23-12-2023 19:42 ]
Ik kwam deze observatie tegen dat dag 21 juist de cellular automaton opdracht was. Ik zie best wat die daar bedoelt.:
[...]
Dag 25 is meestal relatief simpel (en sowieso maar 1 deel). Maar een cellular automaton zou best kunnen voor morgen of overmogen! Iedereen heeft zijn Hashlife implementatie klaar hoop ik?
Was best snel met p2 vandaag
Maar nu nog ~55s runtime voor p2
... Dus ik ga er nog even mee stoeien.
Voor wie de huidige staat wil zien:
Python
spoiler:
Omdat ik bij part 1 al de conjunctions relatief aan elkaar had berekend om mee te gaan rekenen.
Maar nu nog ~55s runtime voor p2
... Dus ik ga er nog even mee stoeien.Voor wie de huidige staat wil zien:
Python
spoiler:
Ownee sorry, het is gewoon dezelfde dfs als deel 1 die je door laat draaien, maar nu met kruispunten ipv cellen.
Een state is (het kruispunt, afgelegde afstand, al bezochte kruispunten)
En als je dan bij je bestemming komt check je of deze beter is dan je maximale afstand tot nu toe
Ik was even in de war omdat je bij weighted edges standaard dijkstra gebruikt.
Een state is (het kruispunt, afgelegde afstand, al bezochte kruispunten)
En als je dan bij je bestemming komt check je of deze beter is dan je maximale afstand tot nu toe
Ik was even in de war omdat je bij weighted edges standaard dijkstra gebruikt.
Leuke puzzel vandaag! Zoals de meesten hier maak ik een vereenvoudigde graaf. Oplossen kost voor mijn input 15 seconden, maar ik heb geoptimaliseerd voor leesbaarheid, niet performance
Code (Python)
Code (Python)
Ah ik zie het al, jij hebt regels als:
[...]
Ok, hier is mijn debug uitvoer. Wijs maar een blok aan dat ik ten onrechte heb gemarkeerd als “NOT safe to remove”
99,79,139~62,79,139
Waarbij componenten van het eerste coordinaat hoger zijn dan die van het tweede coordinaat. Ik weet niet of dat de bedoeling was? De omschrijving noemt verder niet dat dat verboden is, maar de voorbeeld en de officiele input doet dat nooit. Als ik dat support kom ik ook op 71. Ik vind persoonlijk dat je je input moet fixen
[ Voor 20% gewijzigd door .oisyn op 23-12-2023 13:27 ]
Give a man a game and he'll have fun for a day. Teach a man to make games and he'll never have fun again.
:strip_icc():strip_exif()/u/633426/crop658152b10d6b4_cropped.jpg?f=community)
spoiler:
Bij mijn input werkte het blijkbaar
Ik had gewoon de compareTo van mijn nodes omgedraaid, zodat de sortering in de queue andersom is. Voor de test input gaf die het op 1 na beste resultaat terug, ik runde hem voor de gein maar eens met de echte input, en blijkbaar gaf die daar het goede antwoord terug.
Ik had gewoon de compareTo van mijn nodes omgedraaid, zodat de sortering in de queue andersom is. Voor de test input gaf die het op 1 na beste resultaat terug, ik runde hem voor de gein maar eens met de echte input, en blijkbaar gaf die daar het goede antwoord terug.
/u/36698/avatar.png?f=community){kind=avatar}
Het is in ieder geval correct! Je kunt het nog aanzienlijk sneller maken (spoiler!)::
Maar nu nog ~55s runtime voor p2
Voor wie de huidige staat wil zien: Python
spoiler:
In je huidige oplossing bestaat je state uit (steps, current, seen). Je sorteert seen wat een goed optimalisatie is om het aantal states van O(V × V!) naar O(V × 2V) te verlagen. Maar je doet nu nog onnodig extra werk omdat je dezelfde combinatie van (current, seen) meerdere keren bezoekt, namelijk élke keer dat je steps verlaagt (wat in de officiële testinvoer gelukkig niet vaak voorkomt).
Om dat sneller te maken moet je het van de andere kant bekijken. Bereken niet hoeveel stappen je nodig hebt om tot current te komen, maar bereken wat de maximale afstand tot het eindpunt is gegeven current en seen.
Om dat sneller te maken moet je het van de andere kant bekijken. Bereken niet hoeveel stappen je nodig hebt om tot current te komen, maar bereken wat de maximale afstand tot het eindpunt is gegeven current en seen.
Ah ja, dat verklaart het
Bijzonder dat je voor een iteratieve oplossing met een while-loop gekozen hebt in plaats van een simpelere DFS met een recursieve functie. En de ordening van de deque, daar heb je hier niets aan (maar kwaad kan het ook niet). Wel lekker strakke code om de graaf voor deel 2 op te bouwen.Trouwens wel leuk om te zien dat Github die notebook kan previewen.
Dit klinkt alsof er een bug in je code zit... Als je een DFS zonder optimalisaties doet is het aantal paden O(V!) en dat is toch veel te veel om in 1 seconde te doen? De oplossingen van @Asgardian28 en @Friits hebben dezelfde logica en doen er logischerwijs veel langer over.
[ Voor 18% gewijzigd door Soultaker op 23-12-2023 14:29 ]
Dat was expres, precies omdat het volgens het problem statement kan. De negatieve/overlappende z-coördinaten was onbedoeld.
Waarom? Jij hebt je code toch al gefixtIk vind persoonlijk dat je je input moet fixen
Maar je mag ook testinvoer 3 oplossen, die heeft volgens mij geen geïnverteerde coördinaten.
:
[...]
spoiler:Bij mijn input werkte het blijkbaar
Ik had gewoon de compareTo van mijn nodes omgedraaid, zodat de sortering in de queue andersom is. Voor de test input gaf die het op 1 na beste resultaat terug, ik runde hem voor de gein maar eens met de echte input, en blijkbaar gaf die daar het goede antwoord terug.
spoiler:
Helaas ging diezelfde vlieger niet op voor deel 2, dus toch maar even een nette oplossing gemaakt die voor elke input kan werken.
De efficientie laat te wensen over, voor deel 2 draait die 17 seconden.
Ik bouw eerst een graph op met de kruispunten als nodes, dan bepaal ik elk mogelijk pad dat naar de exit kan leiden, en daarvan geef ik dan de grootste lengte terug.
De efficientie laat te wensen over, voor deel 2 draait die 17 seconden.
Ik bouw eerst een graph op met de kruispunten als nodes, dan bepaal ik elk mogelijk pad dat naar de exit kan leiden, en daarvan geef ik dan de grootste lengte terug.
Als ik het vergelijk met de code van Friits hier dan wordt search() ~100 miljoen keer gecalled, waarbij 'ie ~29 miljoen keer langs de eerste twee if-statements komt. Dat zit dus ongeveer in de orde van grootte van jouw oplossing. Mischien is Swift gewoon swifter dan ik dacht
Ik was niet tevreden met mijn oplossing van dag 22, het werkte, maar was supertraag (~30s totaal voor beide antwoorden) en ik wist dat ik die toch zeker nog een stuk kon verbeteren, nou dat is gelukt. Voornamelijk verbetering van datatypes en berekeningen. Nu runnen beide sets in ongeveer 75ms, dat is 400x zo snel. Nu ben ik wel tevreden over mijn oplossing. 
https://github.com/realma...de.Y2023/Solvers/Day22.cs
https://github.com/realma...de.Y2023/Solvers/Day22.cs
There's no place like 127.0.0.1
Bedankt voor deze check!:
[...]
Als ik het vergelijk met de code van Friits hier dan wordt search() ~100 miljoen keer gecalled, waarbij 'ie ~29 miljoen keer langs de eerste twee if-statements komt. Dat zit dus ongeveer in de orde van grootte van jouw oplossing. Mischien is Swift gewoon swifter dan ik dacht
:strip_exif()/u/68919/logoblad.gif?f=community)
Zo, hèhè, eindelijk even tijd gehad om de bug uit mijn day22 algo te halen
Officiele input: 582.3µs
Op @Soultaker's sets:
1: 3,949.0µs
2: 159,689.1µs
3: 244,243.6µs
Officiele input: 582.3µs
Op @Soultaker's sets:
1: 3,949.0µs
2: 159,689.1µs
3: 244,243.6µs
spoiler:
Voor deel 2 doe ik 2 passes.
In de eerste pass bepaal ik welke steen je moet omgooien om een steen te laten vallen. Hierbij heb je gegevens nodig over op welke stenen een steen rust. Ik werk van onder naar boven (stenen gesorteerd op minimale y-waarde). Voor elke steen voeg ik de stenen waar de steen op rust toe aan een max-queue. Dan pop ik steeds een waarde van de max-queue en vervang die met de steen die die steen doet laten vallen (die ik dan al weet, want die zijn lager dus die zijn al aan de beurt geweest). Als er maar 1 entry in de lijst zit, dan valt de steen bij het verwijderen van die ene steen in de lijst. Als we een steen bereiken die nooit kan vallen (omdat hij op de grond staat) met meerdere stenen in de queue, dan kan deze steen ook niet vallen.
Dan heb ik een lijstje met wanneer elke steen valt. Voor de tweede pass maak ik een nieuw lijstje; hoeveel stenen er vallen bij het omgooien van elke steen. Nu loop van boven naar onderen, waarbij ik steeds 1 + het aantal stenen dat valt bij omgooien van deze steen, optel bij de steen die deze steen doet laten vallen. Het antwoord van deel twee is de som van dit lijstje.
In de eerste pass bepaal ik welke steen je moet omgooien om een steen te laten vallen. Hierbij heb je gegevens nodig over op welke stenen een steen rust. Ik werk van onder naar boven (stenen gesorteerd op minimale y-waarde). Voor elke steen voeg ik de stenen waar de steen op rust toe aan een max-queue. Dan pop ik steeds een waarde van de max-queue en vervang die met de steen die die steen doet laten vallen (die ik dan al weet, want die zijn lager dus die zijn al aan de beurt geweest). Als er maar 1 entry in de lijst zit, dan valt de steen bij het verwijderen van die ene steen in de lijst. Als we een steen bereiken die nooit kan vallen (omdat hij op de grond staat) met meerdere stenen in de queue, dan kan deze steen ook niet vallen.
Dan heb ik een lijstje met wanneer elke steen valt. Voor de tweede pass maak ik een nieuw lijstje; hoeveel stenen er vallen bij het omgooien van elke steen. Nu loop van boven naar onderen, waarbij ik steeds 1 + het aantal stenen dat valt bij omgooien van deze steen, optel bij de steen die deze steen doet laten vallen. Het antwoord van deel twee is de som van dit lijstje.
[ Voor 76% gewijzigd door .oisyn op 23-12-2023 20:36 ]
Give a man a game and he'll have fun for a day. Teach a man to make games and he'll never have fun again.
/u/450302/crop65666e73a1424_cropped.png?f=community)
Even tussendoor met een meta-berichtje, niet aan een dag gerelateerd. Voor de liefhebbers heb ik de resultaten van mijn jaarlijkse Advent of Code Survey gepubliceerd, dit jaar 3000+ mensen die 'm hebben ingvuld dus geeft enig beeld van wat men doet en gebruikt.
Enjoy! En succes met de laatste puzzels natuurlijk allemaal
- Survey resultaten:https://jeroenheijmans.github.io/advent-of-code-surveys/
- Reddit announcement: https://www.reddit.com/r/..._aoc_2023_survey_results/
spoiler: Multi-select vraag: "anno 2023 what are your thoughts on AI and LLM's for Advent of Code?":fill(white):strip_exif()/f/image/UfLVP3TYlW2I9D1oxSiZ20XE.png?f=user_large)
Enjoy! En succes met de laatste puzzels natuurlijk allemaal
spoiler: day 23, part 2:strip_exif()/f/image/oSVdqMLI82aByZzvkVxzNqd2.png?f=user_large)
Dit verklaart de hoeveelheid routes tussen begin (1) en eind (36)
Dit verklaart de hoeveelheid routes tussen begin (1) en eind (36)
[ Voor 42% gewijzigd door Bolukan op 23-12-2023 21:51 ]
Ik vond dat mijn dag 23 deel 2 er wel erg lang over deed. Ik print ondertussen de tot nu toe langst gevonden route, maar daar was al een tijdje geen update op geweest. Ik doe nog niet aan pruning verder dus ik ging gewoon eens kijken of dat dan het juiste antwoord was.
"Your anwer is too high"
Wait, what?!
Ik maak dus exact dezelfde fout. Typisch dat dat niet op deel 1 van toepassing is, noch op het voorbeeld.
"Your anwer is too high"
Wait, what?!
d'Oh!
Ik maak dus exact dezelfde fout. Typisch dat dat niet op deel 1 van toepassing is, noch op het voorbeeld.spoiler:
Inderdaad even niet bedacht dat alle nodes natuurlijk dezelfde tile delen. Je kunt dus niet naar dezelfde node maar dan een ander pad nemen, want die ene tile die alle paden verbindt is al belopen
spoiler:
Mijn graaf for good measure
/f/image/FxNLWgyaivnw7Cy0ZDp65WsO.png?f=fotoalbum_large)
:fill(white):strip_exif()/f/image/FxNLWgyaivnw7Cy0ZDp65WsO.png?f=user_large)
[ Voor 66% gewijzigd door .oisyn op 24-12-2023 02:04 ]
Give a man a game and he'll have fun for a day. Teach a man to make games and he'll never have fun again.
Give a man a game and he'll have fun for a day. Teach a man to make games and he'll never have fun again.
:strip_icc():strip_exif()/u/1857/crop5a4d06ced6afe_cropped.jpeg?f=community)
Dit wordt zo te zien een makkie. Jammer dat ik wrinig tijd heb vandaag
Give a man a game and he'll have fun for a day. Teach a man to make games and he'll never have fun again.
spoiler:
Heb deel 2 ook nog niet, maar ik vermoed dat je iets kan met de punten die dezelfde snelheid in een bepaalde richting hebben, volgens mij kan je daarmee het aantal mogelijke snelheden van de steen die je gooit in een bepaalde richting flink reduceren.
/edit: hiermee is het me inmiddels gelukt om de velocity vector te vinden, nu nog de positie
/edit2: en uiteindelijk gelukt door ook voor het vinden van de initiele positie de parallelen te gebruiken: ik pak de eerste 2 punten die parallel zijn voor x over t en kan tussen die 2 makkelijk dt bepalen door `dx*t1 = vx1 * t1 + x1` en `dx*t2 = vx2 * t2 + x2` op te lossen. Deze dt kan je dan weer gebruiken door mbv y1(t) en y2(t) de daadwerkelijke t te vinden. Uren naar lijnen en snijpunten zitten staren, maar blij dat ik het zonder hints heb kunnen oplossen
/edit: hiermee is het me inmiddels gelukt om de velocity vector te vinden, nu nog de positie
/edit2: en uiteindelijk gelukt door ook voor het vinden van de initiele positie de parallelen te gebruiken: ik pak de eerste 2 punten die parallel zijn voor x over t en kan tussen die 2 makkelijk dt bepalen door `dx*t1 = vx1 * t1 + x1` en `dx*t2 = vx2 * t2 + x2` op te lossen. Deze dt kan je dan weer gebruiken door mbv y1(t) en y2(t) de daadwerkelijke t te vinden. Uren naar lijnen en snijpunten zitten staren, maar blij dat ik het zonder hints heb kunnen oplossen
[ Voor 58% gewijzigd door MrHaas op 24-12-2023 16:31 ]
spoiler:
Waar ik aan denk is dat je 300 lijnen in de tijd kunt tekenen die ergens een lijn die je zoekt doorkruist, waarbij het tijdstip niet belangrijk is (niet belangrijk = per vergelijking anders).
In tegenstelling tot part 1 doe je dat niet tussen die 300 vergelijkingen maar met de onbekende 301e vergelijking, waarvan je de parameters nog niet kent.
/f/image/vxguCqp2UbT9gOC6C472WTA4.png?f=fotoalbum_large)
In tegenstelling tot part 1 doe je dat niet tussen die 300 vergelijkingen maar met de onbekende 301e vergelijking, waarvan je de parameters nog niet kent.
:fill(white):strip_exif()/f/image/vxguCqp2UbT9gOC6C472WTA4.png?f=user_large)
[ Voor 68% gewijzigd door Bolukan op 24-12-2023 17:29 ]
Ik heb het ook weer even opgepakt. Momenteel ben ik aan het werken met getallen modulo 529233060817505690510304950800612746886167535693661804372887187718111564412284041920041722342379610808287460926855236217917467249455008000. Geen idee of ik brilliant ben of compleet zot; een van de twee in ieder geval
edit: Ik ben brilliant!
edit: Ik ben brilliant!
[ Voor 5% gewijzigd door Soultaker op 24-12-2023 19:14 ]
spoiler: even nadenken
als we de te vinden lijn nummer 0 geven, en de rest 1 tm 300:
1) pxi + ti * dxi = px0 + ti * dx0 voor i=1..300 en idem voor y en z
Herschreven tot:
2) px0 = pxi + ti * ( dxi - dx0 )
Toegepast op i=1 en 2:
3) px1 + t1 * ( dx1 - dx0 ) = px2 + t2 * ( dx2 - dx0 )
idem voor y en z
Herschreven:
4) ( px1 - px2 + t1 * dx1 - t2 * dx2 ) / ( t2 - t1 ) = dx0
en de rest komt na de kerstnachtdienst
1) pxi + ti * dxi = px0 + ti * dx0 voor i=1..300 en idem voor y en z
Herschreven tot:
2) px0 = pxi + ti * ( dxi - dx0 )
Toegepast op i=1 en 2:
3) px1 + t1 * ( dx1 - dx0 ) = px2 + t2 * ( dx2 - dx0 )
idem voor y en z
Herschreven:
4) ( px1 - px2 + t1 * dx1 - t2 * dx2 ) / ( t2 - t1 ) = dx0
en de rest komt na de kerstnachtdienst
:strip_icc():strip_exif()/u/341556/crop5dce11181361b.jpeg?f=community)
Zo, dag 23 eindelijk af (Python code). Ik zat al een tijdje in de correcte richting te denken maar de implementatie-details waren nog wel tricky.
Als iemand interesse heeft kan ik (morgen of overmorgen) een gedetailleerde uitleg posten.
Als iemand interesse heeft kan ik (morgen of overmorgen) een gedetailleerde uitleg posten.
Oh interessant. Ik heb geen gebruik van gemaakt van dit soort eigenschappen van de invoer. Ik had wel een aantal observaties maar de meeste leken niet heel bruikbaar. Ik moet later nog eens in detail naar je code kijken om te begrijpen wat je precies doet. Op het eerste gezicht is het aanzienlijk simpeler dan mijn aanpak.:
spoiler:/edit2: en uiteindelijk gelukt door ook voor het vinden van de initiele positie de parallelen te gebruiken: ik pak de eerste 2 punten die parallel zijn voor x over t en kan tussen die 2 makkelijk dt bepalen door `dx*t1 = vx1 * t1 + x1` en `dx*t2 = vx2 * t2 + x2` op te lossen. Deze dt kan je dan weer gebruiken door mbv y1(t) en y2(t) de daadwerkelijke t te vinden. Uren naar lijnen en snijpunten zitten staren, maar blij dat ik het zonder hints heb kunnen oplossen
Grappig genoeg is het wel een beetje jouw vakgebied. Ik denk dus dat je met deel 1 relatief weinig moeite zal hebben. (Voor deel 2 durf ik het niet te zeggen.):
Dit wordt zo te zien een makkie. Jammer dat ik wrinig tijd heb vandaag
Ik had op enig moment dezelfde vergelijking opgesteld, maar:
spoiler: even nadenkenHerschreven:
4) ( px1 - px2 + t1 * dx1 - t2 * dx2 ) / ( t2 - t1 ) = dx0
en de rest komt na de kerstnachtdienst
spoiler:
het probleem is dat de deling de vergelijking niet-lineair maakt, en dan wordt het heel moeilijk oplossen. Mogelijk moet je dus in een andere richting denken.
Zelfde hier; 100% integer arithmetic, wat bij deel 1 al nodig was. Gelukkig maakt Python dit erg makkelijk. 128-bits integers waren niet voldoende voor mijn oplossing.
Daarom. Lijnintersecties tik ik uit het hoofd in
. Volgens mij kun je ook wel bepalen of het intersectiepunt in het vierkant ligt zonder het uit te rekenen.Jammer dat ik deel 2 nog niet kan inzien.
Give a man a game and he'll have fun for a day. Teach a man to make games and he'll never have fun again.
Pfff...
Ga later nog maar eens kijken naar de andere oplossingen, wat ik gemist heb, ben er even klaar mee.
Ga later nog maar eens kijken naar de andere oplossingen, wat ik gemist heb, ben er even klaar mee.
spoiler:
Deel 1 inderdaad goed te doen. Deel 2 daarentegen....
Eerst met wat geprutst 3 vergelijkingen met 3 onbekenden, alleen niet lineair (inhomogeen bilinear), door in te zien dat als A_12 = (H_1 + t_1 V_1) - (H_2 + t_2 V_2) en A_13 = (H_1 + t_1 V_1) - (H_3 + t_3 V_3) parallel zijn (wat ze moeten zijn, anders kan er geen steen door alle 3 heen), dan krijg je uit crossproduct(A_12, A_13) = 0,
3 vergelijkingen met 3 onbekenden (de t_1, t_2 en t_3).
Alleen niet-lineair...
Eerst brute-force geprobeerd, maar dat ging hem niet worden.
Toen ingezien dat je t_3 uit t_1 en t_2 kunt bepalen, maar ook een brute-force search over t_1 en t_2 ging hem niet worden.
Toen met veel gepruts een vergelijking voor t_3 en t_2 uit t_1 kunnen bepalen (Sylvester matrices en resultant polynomials...). Maar ook een brute-force over t_1 alleen ging hem niet worden.
Er is een mogelijkheid om t_1 ook direct te bepalen, maar na talloze vellen papier volgekladderd te hebben kwam ik tot de conclusie dat dat een 6e graads polynoom zou worden. Die gaan we niet proberen op te lossen (hoewel ik vermoed dat er wel een mooie algebraische oplossing zou zijn, gezien het feit dat de oplossing in integers uitgedrukt kon worden).
Ook nog geprobeerd: de oplossing benaderen door een gradient descent search. Werkt niet, door de grote getallen gaat het niet convergeren.
Toen maar sympy erbij gepakt: oorspronkelijke vergelijking erin stoppen, fout antwoord krijgen
Toen alle numpy (cross products e.d.) vervangen door bare python, en alles opnieuw uitrekenen. Nu een vergelijking waarin t3 een onbekende bleef: er is blijkbaar nog een vrijheidsgraad over. Nu met sympy de resulterende 2 vergelijkingen (een voor t1 in termen van t3, een voor t2 in termen van t3) diophantisch oplossen (dus alleen integers...). Eindelijk de oplossing, maar door het gebruik van Sympy niet echt voldoening
Wel nog even gecheckt, mijn methode met 1 variable brute force werkte correct als ik rond de goede waarde zoek, maar ja, brute force naar ~60 miljard gaat hem niet worden.
Eerst met wat geprutst 3 vergelijkingen met 3 onbekenden, alleen niet lineair (inhomogeen bilinear), door in te zien dat als A_12 = (H_1 + t_1 V_1) - (H_2 + t_2 V_2) en A_13 = (H_1 + t_1 V_1) - (H_3 + t_3 V_3) parallel zijn (wat ze moeten zijn, anders kan er geen steen door alle 3 heen), dan krijg je uit crossproduct(A_12, A_13) = 0,
3 vergelijkingen met 3 onbekenden (de t_1, t_2 en t_3).
Alleen niet-lineair...
Eerst brute-force geprobeerd, maar dat ging hem niet worden.
Toen ingezien dat je t_3 uit t_1 en t_2 kunt bepalen, maar ook een brute-force search over t_1 en t_2 ging hem niet worden.
Toen met veel gepruts een vergelijking voor t_3 en t_2 uit t_1 kunnen bepalen (Sylvester matrices en resultant polynomials...). Maar ook een brute-force over t_1 alleen ging hem niet worden.
Er is een mogelijkheid om t_1 ook direct te bepalen, maar na talloze vellen papier volgekladderd te hebben kwam ik tot de conclusie dat dat een 6e graads polynoom zou worden. Die gaan we niet proberen op te lossen (hoewel ik vermoed dat er wel een mooie algebraische oplossing zou zijn, gezien het feit dat de oplossing in integers uitgedrukt kon worden).
Ook nog geprobeerd: de oplossing benaderen door een gradient descent search. Werkt niet, door de grote getallen gaat het niet convergeren.
Toen maar sympy erbij gepakt: oorspronkelijke vergelijking erin stoppen, fout antwoord krijgen
Toen alle numpy (cross products e.d.) vervangen door bare python, en alles opnieuw uitrekenen. Nu een vergelijking waarin t3 een onbekende bleef: er is blijkbaar nog een vrijheidsgraad over. Nu met sympy de resulterende 2 vergelijkingen (een voor t1 in termen van t3, een voor t2 in termen van t3) diophantisch oplossen (dus alleen integers...). Eindelijk de oplossing, maar door het gebruik van Sympy niet echt voldoening
Wel nog even gecheckt, mijn methode met 1 variable brute force werkte correct als ik rond de goede waarde zoek, maar ja, brute force naar ~60 miljard gaat hem niet worden.
spoiler:
Zie nu (op reddit) dat ik het om had kunnen schrijven naar 6 lineaire vergelijkingen met 6 onbekenden... dat had ik wel kunnen oplossen 
Ik ben te geintrigeerd door moeilijke oplossingen blijkbaar.
Andere mogelijkheid was blijkbaar brute-force op snelheden van de steen, dat is natuurlijk flauw dat dat werkt
Ik ben te geintrigeerd door moeilijke oplossingen blijkbaar.
Andere mogelijkheid was blijkbaar brute-force op snelheden van de steen, dat is natuurlijk flauw dat dat werkt
[ Voor 7% gewijzigd door FCA op 24-12-2023 22:44 ]
Verandert z'n sig te weinig.
Zo, in een keer goed, maar ik heb wel 2 uur zitten debuggen voor een stom foutje 
day24 in Rust
Time spent: 26533.6µs
Deel 2 was wel even pittig ja. Deel 1 had ik in 15 minuten ingetypt
day24 in Rust
Time spent: 26533.6µs
Deel 2 was wel even pittig ja. Deel 1 had ik in 15 minuten ingetypt
spoiler:
Ik heb het uiteindelijk opgelost door voor paren van stenen die op een as dezelfde snelheid hebben een verzameling van mogelijke snelheden (de delers van de afstand tussen die stenen op die as, relatief aan hun snelheid) bepaald, die ik uiteindelijk wegstreep tegen de mogelijke snelheden bij andere paren.
Blijkt dat je voor de officiele input maar 1 mogelijkheid per as overhoud, maar voor het voorbeeld is dat niet zo, dus ik heb het generiek geimplementeerd waarbij hij ze gewoon probeert. Met een snelheid op 1 as de twee snijpunten op een andere as bepaald om op zo'n manier op te lossen voor positie en snelheden op alle assen. En dan kijken of dat de juiste oplossing is voor alle stenen.
Blijkt dat je voor de officiele input maar 1 mogelijkheid per as overhoud, maar voor het voorbeeld is dat niet zo, dus ik heb het generiek geimplementeerd waarbij hij ze gewoon probeert. Met een snelheid op 1 as de twee snijpunten op een andere as bepaald om op zo'n manier op te lossen voor positie en snelheden op alle assen. En dan kijken of dat de juiste oplossing is voor alle stenen.
spoiler:
Ah ik zie dat meer mensen voor die oplossing hebben gekozen
Deel 2 gewoon in i64. Ik had even geen zin om over deel 1 na te denken dus daar wel even een i128 gebruikt.
Deel 2 gewoon in i64. Ik had even geen zin om over deel 1 na te denken dus daar wel even een i128 gebruikt.
[ Voor 9% gewijzigd door .oisyn op 25-12-2023 04:28 ]
Give a man a game and he'll have fun for a day. Teach a man to make games and he'll never have fun again.
Fijne kerstdagen allemaal!
Dag 25:
Python code: 25-minimal.py (~150 ms) (of 25.py voor een iets leesbaardere versie).
Dag 25:
spoiler: Oplossing voor dag 25
Eerst probeerde ik 'm gewoon te brute forcen: voor elke drie edges een depth-first search om de componenten te detecteren. Dat was natuurlijk veel te traag. Toen had ik code geschreven om cliques te detecteren en samen te trekken. Dat werkte uitstekend op de voorbeeldinvoer, maar de officiële invoer blijkt geen cliques groter dan 3 te hebben, dus dat bleek verspilde tijd.
Uiteindelijk heb ik het Ford-Fulkerson algoritme maar geïmplementeerd om de minimum cut in de graaf te vinden. Probleem is dat je een start- en een eindvertex moet hebben in aparte componenten, anders vind je de minimum cut niet. Ik heb dat simpelweg opgelost door in een while-loop random twee vertices te kiezen. Als de componenten ongeveer even groot zijn is de kans dat je twee goede vertices hebt ongeveer 50%. Vraag me af of dat slimmer kan.
Uiteindelijk heb ik het Ford-Fulkerson algoritme maar geïmplementeerd om de minimum cut in de graaf te vinden. Probleem is dat je een start- en een eindvertex moet hebben in aparte componenten, anders vind je de minimum cut niet. Ik heb dat simpelweg opgelost door in een while-loop random twee vertices te kiezen. Als de componenten ongeveer even groot zijn is de kans dat je twee goede vertices hebt ongeveer 50%. Vraag me af of dat slimmer kan.
Python code: 25-minimal.py (~150 ms) (of 25.py voor een iets leesbaardere versie).
spoiler: Alternatieve aanpak
Het viel me op dat ik het antwoord ook zonder algoritme kan vinden. Als ik de invoer converteer naar GraphViz formaat en open met Qt Visual Graph Editor, dan zijn de twee helften duidelijk te zien.
Je kunt dan simpelweg op de kritieke edges klikken om de eindpunten te identificeren, en de vertices selecteren om te zien hoe groot de componenten zijn. Het verbaasde me enigszins dat QVGE geen moeite heeft met zulke grote bestanden.
edit:
neato maakt er ook een “mooi” plaatje van:
De edges binnen de componenten zijn een grote warboel maar de drie kritieke edges tússen de componenten zijn duidelijk herkenbaar, en dat is precies de informatie die je nodig hebt Jammer dat ik dit niet meteen geprobeerd had. Had me een heleboel tijd gescheeld (al had ik het probleem ook nog écht op willen lossen).
Je kunt dan simpelweg op de kritieke edges klikken om de eindpunten te identificeren, en de vertices selecteren om te zien hoe groot de componenten zijn. Het verbaasde me enigszins dat QVGE geen moeite heeft met zulke grote bestanden.
edit:
neato maakt er ook een “mooi” plaatje van:
De edges binnen de componenten zijn een grote warboel maar de drie kritieke edges tússen de componenten zijn duidelijk herkenbaar, en dat is precies de informatie die je nodig hebt
Jammer dat ik dit niet meteen geprobeerd had. Had me een heleboel tijd gescheeld (al had ik het probleem ook nog écht op willen lossen).[ Voor 12% gewijzigd door Soultaker op 25-12-2023 14:45 ]
Ik heb nog niet in gepost in dit topic, maar wel veel interesse gevolgd. Voor mij was dit het derde jaar dat ik meedeed en voor het eerst dat ik er redelijk soepel doorheen fietste. Dank voor al jullie inzichten! Ik heb uiteindelijk niet alle sterren binnen geharkt, maar wel weer enorm veel geleerd. Speciale shoutout naar @Soultaker , je zou docent moeten worden.
Fijne dagen allemaal!
Fijne dagen allemaal!
:strip_icc():strip_exif()/u/140697/crop6180fb9103afa_cropped.jpg?f=community)
Haha, ik ben juist onder de indruk van iedereen die de puzzels in "serieuze" talen oplost, en zich druk moet maken over types, overflows en allerlei andere zaken, en heel veel meer (foutloze) regels code moet schrijven.
Bijvoorbeeld gisteren: vergeleken met de code van .oisyn voelen mijn 20 regels Python een beetje als Lego
Tot slot nog mijn code voor vandaag, met iets wat lijkt op Karger's.
spoiler:
Leuk, die kende ik nog niet! Interessant om te zien dat zowel dit als mijn compleet andere algoritme allebei gebruik maken van randomization.
Ik ben vooral ontzettend klaar met het “vroeg opstaan” aspect van de competitie
Voor het geval iemand toch nog tijd over heeft vandaag, of misschien morgen teleurgesteld is dat er geen nieuw probleem is om op te lossen, hier wat extra testinvoer voor dag 25:
aoc-2023-day-25-challenge-1-to-4.zip
Correcte antwoorden eindigen op: ..16144, ..05408, ..80480 en ..41796.
Ik natuurlijk ook niet tot vanmorgen.:
Gebruikt? Ik had er nog nooit van gehoord
Siditamentis astuentis pactum.
Grappig, de puzzel van vandaag is precies iets waar ik afgelopen tijd op m'n werk mee bezig ben geweest
Hier trouwens een representatie van het voorbeeld waarin het op het oog direct duidelijk is welke je moet knippen.
/f/image/p18HqrnsQMPNqaqPmuV29CiV.png?f=fotoalbum_large)
spoiler:
Namelijk het partitioneren van een graaf in N delen waarbij je de edge cut minimaliseert. Ik gebruik daar een library voor. Zou wel flauw zijn om die gewoon aan te slingeren
Hier trouwens een representatie van het voorbeeld waarin het op het oog direct duidelijk is welke je moet knippen.
:fill(white):strip_exif()/f/image/p18HqrnsQMPNqaqPmuV29CiV.png?f=user_large)
[ Voor 43% gewijzigd door .oisyn op 25-12-2023 14:13 ]
Give a man a game and he'll have fun for a day. Teach a man to make games and he'll never have fun again.
:strip_icc():strip_exif()/u/237526/crop5e05c1d265781_cropped.jpeg?f=community)
Poeh, was een heftige klus dit jaar. Dankzij de switch naar een andere taal wel eindelijk een keertje de 1 second challenge gehaald . Was even bang dat het niet ging lukken de laatste paar dagen, maar met wat inspiratie links en rechts genoeg kunnen optimaliseren om eronder te blijven.
. Was even bang dat het niet ging lukken de laatste paar dagen, maar met wat inspiratie links en rechts genoeg kunnen optimaliseren om eronder te blijven.code:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
| $ ./target/release/aoc2023 --all | grep "time: " Day 1 time: 2.16ms (A: 145.67µs, B: 2.02ms) Day 2 time: 166.42µs (A: 89.33µs, B: 76.96µs) Day 3 time: 1.23ms (A: 599.38µs, B: 629.79µs) Day 4 time: 403.46µs (A: 207.13µs, B: 196.33µs) Day 5 time: 155.67µs (A: 53.79µs, B: 101.79µs) Day 6 time: 20.98ms (A: 2.21µs, B: 20.97ms) Day 7 time: 1.33ms (A: 682.71µs, B: 644.46µs) Day 8 time: 3.68ms (A: 724.21µs, B: 2.95ms) Day 9 time: 531.46µs (A: 265.17µs, B: 266.13µs) Day 10 time: 3.33ms (A: 1.35ms, B: 1.98ms) Day 11 time: 5.14ms (A: 2.64ms, B: 2.49ms) Day 12 time: 13.96ms (A: 1.35ms, B: 12.62ms) Day 13 time: 2.13ms (A: 1.07ms, B: 1.07ms) Day 14 time: 30.19ms (A: 114.63µs, B: 30.07ms) Day 15 time: 494.54µs (A: 81.25µs, B: 413.25µs) Day 16 time: 45.76ms (A: 1.60ms, B: 44.16ms) Day 17 time: 67.23ms (A: 21.94ms, B: 45.28ms) Day 18 time: 167.00µs (A: 80.88µs, B: 86.13µs) Day 19 time: 1.04ms (A: 449.67µs, B: 586.75µs) Day 20 time: 5.28ms (A: 1.04ms, B: 4.24ms) Day 21 time: 73.45ms (A: 4.86ms, B: 68.59ms) Day 22 time: 259.93ms (A: 6.26ms, B: 253.67ms) Day 23 time: 307.94ms (A: 5.17ms, B: 302.78ms) Day 24 time: 1.39ms (A: 595.58µs, B: 797.17µs) Day 25 time: 2.99ms (A: 2.99ms, B: 125.00ns) Total time: 851.07ms |
Day25 in Rust
29381.9µs
.edit:
29381.9µs
spoiler:
Voordat ik het register opentrok met een min-cut algoritme wilde ik eerst zelf wat aankloten. Ik heb een hele vieze oplossing. Voor alle edges check ik hoe lang een loopje minimaal is voor je weer bij dezelfde edge aankomt. Of anders gezegd, het kortste pad van A naar B zonder gebruik te maken van edge AB. Het euvel wil dat zowel in het voorbeeld als in de officiele input, de edges die je door moet knippen een veel langer loopje hebben dan de rest van de edges. Daarna brute-force ik het op volgorde van de loop-grootte, maar die vindt dus in deze datasets direct het antwoord bij de eerste poging.
.edit:
spoiler:
Ah volgens mij precies wat @Remcoder ook doet
[ Voor 10% gewijzigd door .oisyn op 26-12-2023 02:44 ]
Give a man a game and he'll have fun for a day. Teach a man to make games and he'll never have fun again.
Interessant idee! Het werkt vast op de officiële invoer die een bepaalde structuur heeft, maar zoals veel greedy algoritmes kan het soms een suboptimale oplossing geven.
Je had je code ook kunnen testen op mijn extra testinvoer, daar gaat 'ie op de eerste invoer al mis
spoiler:
Het deel van de logica dat correct is, is: als een knoop v in S meer dan drie verbindingen heeft met knopen in S \ G, dan hoort v niet in S thuis en kun je 'm verwijderen. Het probleem is dat het kan voorkomen dat geen enkele individuele knoop meer dan 3 verbindingen heeft, terwijl het totaal aantal verbindingen tussen S en S \ G nog wel groter dan 3 is, en dan kies je een willekeurige knoop, die mogelijk wel in S moet blijven.
Hier is een concreet tegenvoorbeeld:
a: b c d g
b: c d g
c: d e
d: f
e: f g h
f: g h
g: h
Dat ziet er zo uit:
Het is duidelijk dat de componenten A = {a, b, c, d, e, f, g} en B = {h} zijn. Als je code toevallig begint met het verwijderen van e, f en g zodat S = {a, b, c, d, h} (wat consistent is met de regels), dan zul je vervolgens h willen verwijderen: h heeft immers exact 3 verbindingen met {e, f, g}, terwijl {a, b, c, d} er elk maar 1 hebben. Dan concludeer je ten onrechte dat h niet in S thuishoort, terwijl je juist met S={h} wil eindigen. Wanneer je eenmaal zo'n fout maakt is het onmogelijk die te herstellen.
Hier is een concreet tegenvoorbeeld:
a: b c d g
b: c d g
c: d e
d: f
e: f g h
f: g h
g: h
Dat ziet er zo uit:
Het is duidelijk dat de componenten A = {a, b, c, d, e, f, g} en B = {h} zijn. Als je code toevallig begint met het verwijderen van e, f en g zodat S = {a, b, c, d, h} (wat consistent is met de regels), dan zul je vervolgens h willen verwijderen: h heeft immers exact 3 verbindingen met {e, f, g}, terwijl {a, b, c, d} er elk maar 1 hebben. Dan concludeer je ten onrechte dat h niet in S thuishoort, terwijl je juist met S={h} wil eindigen. Wanneer je eenmaal zo'n fout maakt is het onmogelijk die te herstellen.
Grappig genoeg geeft je code op bovenstaande voorbeeld soms wel het goede antwoord, afhankelijk van waar je toevallig begint. Blijkbaar is het een randomized algoritme, omdat in Python de volgorde van elementen in een set() niet alleen ongedefinieerd is, maar actief gerandomized wordt, zodat elke run de volgorde anders is (wat ik me niet gerealiseerd had).
Thanks voor de uitleg. Mijn aanpak leek al te mooi (te eenvoudig) om volledig correct te zijn. Gelukkig werkt 'ie prima op de officiële AoC inputs, en in het uitzonderlijke geval dat 'ie de mist in gaat kan ik 'm gewoon opnieuw draaien. Het is een voor een puzzeltje, niet mission-critical software
Elementen worden in een set geplaatst op basis van hun hash. Sinds 3.3 wordt er bij het hashen van strings een seed gebruikt voor security-redenen. Die seed wordt random gekozen wanneer de interpreter opstart.
Je kan dit uitzetten met export PYTHONHASHSEED=0, en dan zal de volgorde ook tussen runs gelijk zijn.
Klopt, dit is er aan de hand:
Elementen worden in een set geplaatst op basis van hun hash. Sinds 3.3 wordt er bij het hashen van strings een seed gebruikt voor security-redenen. Die seed wordt random gekozen wanneer de interpreter opstart.
Je kan dit uitzetten met export PYTHONHASHSEED=0, en dan zal de volgorde ook tussen runs gelijk zijn.
[ Voor 6% gewijzigd door Friits op 26-12-2023 13:12 ]
:strip_icc():strip_exif()/u/53677/2009-07-01_avatar060x060.jpg?f=community){kind=avatar}
spoiler: dag24
Ik gebruik dus het gegeven dat sommige paren dezelfde snelheid op een bepaalde as hebben.
Ik zat te denken dat je dezelfde oplossing kunt gebruiken zonder paren van hagels te hebben in de input waarvoor dat geldt, door gebruik te maken van lineaire transformaties.
Bijvoorbeeld, in 2d, stel je hebt een steen met snelheid (0, 1) en een steen met snelheid (1,0). Als je dat transformeert naar een stelsel met als basis-assen (1,0) en (-1, 1), dan worden de snelheden in dit nieuwe stelsel respectievelijk (1,0) en (1,1) en dan heb je dus een paar met gelijke snelheid op de nieuwe x-as.
Je moet alleen wel oppassen dat je geen non-integer antwoorden krijgt. Volgens mij is dat wel op te lossen.
Ik zat te denken dat je dezelfde oplossing kunt gebruiken zonder paren van hagels te hebben in de input waarvoor dat geldt, door gebruik te maken van lineaire transformaties.
Bijvoorbeeld, in 2d, stel je hebt een steen met snelheid (0, 1) en een steen met snelheid (1,0). Als je dat transformeert naar een stelsel met als basis-assen (1,0) en (-1, 1), dan worden de snelheden in dit nieuwe stelsel respectievelijk (1,0) en (1,1) en dan heb je dus een paar met gelijke snelheid op de nieuwe x-as.
Je moet alleen wel oppassen dat je geen non-integer antwoorden krijgt. Volgens mij is dat wel op te lossen.
.edit:
spoiler:
Heb even zitten pieken met een online matrix calculator op m'n telefoon. In dit specifieke voorbeeld is de transformatiematrix zijn eigen inverse, dus alle transformaties vallen in Z . Waar je specifiek naar moet kijken is de determinant van de matrix, daar zul je door moeten delen bij het terugtransformeren. Dus de resultaten die je berekent in de getransformeerde ruimte moeten een veelvoud zijn van de determinant.
. Waar je specifiek naar moet kijken is de determinant van de matrix, daar zul je door moeten delen bij het terugtransformeren. Dus de resultaten die je berekent in de getransformeerde ruimte moeten een veelvoud zijn van de determinant.[ Voor 23% gewijzigd door .oisyn op 27-12-2023 10:15 ]
Give a man a game and he'll have fun for a day. Teach a man to make games and he'll never have fun again.
Beetje laten reactie, maar ik had nu pas tijd om deze slimme oplossing goed genoeg te bestuderen dat ik 'm ook volledig begrijp:
Als je bijvoorbeeld aan aoc-2023-day-22-challenge-3.txt één regel toevoegt:
Dan gaat de runtime van ~400 ms naar ~7 minuten
Ter vergelijking, mijn snelle oplossing gebaseerd op
Dit is heel slim gevonden en werkt heel goed voor alle drie van mijn testcases, maar het is helaas worst case nog steeds een kwadratisch algoritme.:
Zo, hèhè, eindelijk even tijd gehad om de bug uit mijn day22 algo te halen
[..]
spoiler:Voor deel 2 doe ik 2 passes.
In de eerste pass bepaal ik welke steen je moet omgooien om een steen te laten vallen. Hierbij heb je gegevens nodig over op welke stenen een steen rust. Ik werk van onder naar boven (stenen gesorteerd op minimale y-waarde). Voor elke steen voeg ik de stenen waar de steen op rust toe aan een max-queue. Dan pop ik steeds een waarde van de max-queue en vervang die met de steen die die steen doet laten vallen (die ik dan al weet, want die zijn lager dus die zijn al aan de beurt geweest). Als er maar 1 entry in de lijst zit, dan valt de steen bij het verwijderen van die ene steen in de lijst. Als we een steen bereiken die nooit kan vallen (omdat hij op de grond staat) met meerdere stenen in de queue, dan kan deze steen ook niet vallen.
Als je bijvoorbeeld aan aoc-2023-day-22-challenge-3.txt één regel toevoegt:
1,42,2~7,42,2
Dan gaat de runtime van ~400 ms naar ~7 minuten
Ter vergelijking, mijn snelle oplossing gebaseerd op
spoiler:
runt deel 2 in O(V + E log V) tijd, waarbij V het aantal blokjes in de invoer is, en E het aantal paren van blokjes dat elkaar raakt.spoiler:
Hier doen we bijna precies hetzelfde, maar net wat anders. We hebben dezelfde informatie berekend: wat bij jou fall_at[x] heet, heet bij mij Parent(x).
fall_at[x] = Parent(x) = y zodat y het hoogstgelegen bokje is dat blokje x doet vallen. Deze relatie is logischerwijs transitief (als x valt wanneer y valt, en y valt wanneer z valt, dan valt x ook wanneer z valt). Je kunt het dus zien als een boomstructuur (vandaar Parent()) en dan is het antwoord op deel 2 simpelweg het aantal paren (x, y) in de boom zodat y een voorouder is van x.
Om dat aantal paren te berekenen neem jij de som van de groottes van de deelbomen (i.e., als ik dit blokje weghaal, hoeveel hogergelegen blokjes vallen er dan) wat je berekent door bij de bladeren te beginnen en dan naar beneden te werken. Ik bereken juist de som van de diepten van de knooppunten (i.e., hoeveel lagergelegen blokjes kunnen de val van dit blokje veroorzaken). Het loopt beide in O(N) tijd. Het praktische voordeel van de bottom up approach is dat je maar één pass nodig hebt. Wat niet wil zeggen dat het ook sneller is natuurlijk.
fall_at[x] = Parent(x) = y zodat y het hoogstgelegen bokje is dat blokje x doet vallen. Deze relatie is logischerwijs transitief (als x valt wanneer y valt, en y valt wanneer z valt, dan valt x ook wanneer z valt). Je kunt het dus zien als een boomstructuur (vandaar Parent()) en dan is het antwoord op deel 2 simpelweg het aantal paren (x, y) in de boom zodat y een voorouder is van x.
Om dat aantal paren te berekenen neem jij de som van de groottes van de deelbomen (i.e., als ik dit blokje weghaal, hoeveel hogergelegen blokjes vallen er dan) wat je berekent door bij de bladeren te beginnen en dan naar beneden te werken. Ik bereken juist de som van de diepten van de knooppunten (i.e., hoeveel lagergelegen blokjes kunnen de val van dit blokje veroorzaken). Het loopt beide in O(N) tijd. Het praktische voordeel van de bottom up approach is dat je maar één pass nodig hebt. Wat niet wil zeggen dat het ook sneller is natuurlijk.
Ik vermoed dat je met deze analyse 98% van je publiek kwijt bent. Maar ik snap waar je naartoe wil. Ik weet niet of het goed komt met de non-integer getallen. Maar dat is een kwestie van proberen. Dat in dit specifieke voorbeeld de inverse de matrix zelf is, is wel bijzonder. Dat betekent dat er ergens een 0° of 180° hoek in zit (het is een transformatiematrix). Ik zou trouwens vooral bezorgd zijn over determinant=0; dit moet je dan apart gaan afvangen.:
spoiler: dag24Ik gebruik dus het gegeven dat sommige paren dezelfde snelheid op een bepaalde as hebben.
Ik zat te denken dat je dezelfde oplossing kunt gebruiken zonder paren van hagels te hebben in de input waarvoor dat geldt, door gebruik te maken van lineaire transformaties.
Bijvoorbeeld, in 2d, stel je hebt een steen met snelheid (0, 1) en een steen met snelheid (1,0). Als je dat transformeert naar een stelsel met als basis-assen (1,0) en (-1, 1), dan worden de snelheden in dit nieuwe stelsel respectievelijk (1,0) en (1,1) en dan heb je dus een paar met gelijke snelheid op de nieuwe x-as.
Je moet alleen wel oppassen dat je geen non-integer antwoorden krijgt. Volgens mij is dat wel op te lossen.
.edit:
spoiler:Heb even zitten pieken met een online matrix calculator op m'n telefoon. In dit specifieke voorbeeld is de transformatiematrix zijn eigen inverse, dus alle transformaties vallen in Z
Ik heb trouwens vooral gewerkt met QR decomposities, eigenvectoren en eigenwaarden. Maar dat lijkt in deze opgave niet de goede aanpak te zijn.
When life gives you lemons, start a battery factory
Dan is er geen inverse en is er een rij of kolom de 0-vector of zijn de assen lineair afhankelijk, dus dat wil je sowieso vermijden
Give a man a game and he'll have fun for a day. Teach a man to make games and he'll never have fun again.