Advent of Code 2021

[Marcj]

Klein beetje uitdagend, toen ik de tweede vraag zag kon ik mezelf wel voor de kop slaan. Natuurlijk ging dat niet werken door de echte string te genereren. Toch heb ik dat ook redelijk vlot opgelost. Het uiteindelijke antwoord werd binnen 40ms uitgerekend om mijn laptop, dus nog behoorlijk performant.

spoiler:

Ik ben met een recursieve oplossing gekomen waar ik mijn Memoize helper weer heb kunnen gebruiken. Dan nog even opletten dat ik geen zaken dubbel tel. Uiteindelijk ben ik voor de oplossing gegaan dat ik alles behalve de laatste character tel, omdat deze ook meegeteld wordt in het volgende paar aan letters. Het uiteindelijke resultaat is nog redelijk compact en leesbaar vind ik: https://github.com/marcde...jonge/advent2021/Day14.kt

[ Voor 6% gewijzigd door Marcj op 14-12-2021 11:27 ]

[Remcoder]

Behold my sin

Members only:

Alleen zichtbaar voor ingelogde gebruikers. Inloggen

spoiler:

Ik was begonnen met de naieve implementatie wetende dat het uiteraard niet ging werken voor deel 2. Bij deel 2 uiteraard toch even proberen, maar bij ronde 28 ging die toch stuk hij kwam dus een stuk verder dan ik verwacht had. Gelukkig duurde dat hooguit een paar minuten dus veel tijd niet verloren door het toch te proberen.

Daarna aan een nieuwe oplossing begonnen die de aantallen pairs bijhoudt, en daarna die gebruikt om de resulterende aantallen te berekenen. Op het einde nog even de tail erbij tellen omdat ik anders een kans heb op een off-by-one error, en de uitkomst komt eruit rollen binnen 33 ms.

[armageddon_2k1]

Hydra schreef op dinsdag 14 december 2021 @ 10:22:
[...]


Heb je aanpak gewoon grof gejat. Met 3 iteraties redelijk in de buurt gekomen maar ben er nu wel klaar mee

Dit is mijn versie.

Er is geen grotere lof voor je code dan dat ie gejat wordt

[DataGhost]

Ehhhh, een mogelijke upping the ante is

spoiler:

50000 steps

spoiler:

Dat duurt op mijn trage laptop met de invoer uit de probleemomschrijving nog geen drie seconden, het antwoord is 63213...50798

Ik dacht dat het niet nodig zou zijn maar ik zie hier wel een paar oplossingen waarvan ik het vermoeden (!) heb dat er nog schaalbaarheids-issues in kunnen zitten, ik kan alleen niet iedereens code even makkelijk zelf draaien om dat te testen helaas. Ook de eventueel benodigde wijzigingen zijn lastiger voor mij in talen die ik niet ken

[ Voor 44% gewijzigd door DataGhost op 14-12-2021 11:48 ]

[coop]

Dag 14 in Python

Net als velen hier begonnen met de string op te bouwen, maar bij deel 2 moest het toch echt anders. Nu best tevreden over mijn oplossing. Blijft goed presteren, ook bij 1500 stappen.

[KabouterSuper]

DataGhost schreef op dinsdag 14 december 2021 @ 11:45:
Ehhhh, een mogelijke upping the ante is

spoiler:

50000 steps

spoiler:

Dat duurt op mijn trage laptop met de invoer uit de probleemomschrijving nog geen drie seconden, het antwoord is 63213...50798

Ik dacht dat het niet nodig zou zijn maar ik zie hier wel een paar oplossingen waarvan ik het vermoeden (!) heb dat er nog schaalbaarheids-issues in kunnen zitten, ik kan alleen niet iedereens code even makkelijk zelf draaien om dat te testen helaas. Ook de eventueel benodigde wijzigingen zijn lastiger voor mij in talen die ik niet ken

3.6 sec met dezelfde uitkomst.

[Diderikdm]

DataGhost schreef op dinsdag 14 december 2021 @ 11:45:
Ehhhh, een mogelijke upping the ante is

spoiler:

50000 steps

spoiler:

Dat duurt op mijn trage laptop met de invoer uit de probleemomschrijving nog geen drie seconden, het antwoord is 63213...50798

Ik dacht dat het niet nodig zou zijn maar ik zie hier wel een paar oplossingen waarvan ik het vermoeden (!) heb dat er nog schaalbaarheids-issues in kunnen zitten, ik kan alleen niet iedereens code even makkelijk zelf draaien om dat te testen helaas. Ook de eventueel benodigde wijzigingen zijn lastiger voor mij in talen die ik niet ken

1.87s, verkeek me eerst op de 12.5s van mijn eigen input en snapte niet waarom mijn uitkomst anders was.. #beterlezen

[ Voor 8% gewijzigd door Diderikdm op 14-12-2021 12:05 ]

[coop]

DataGhost schreef op dinsdag 14 december 2021 @ 11:45:
Ehhhh, een mogelijke upping the ante is

spoiler:

50000 steps

spoiler:

Dat duurt op mijn trage laptop met de invoer uit de probleemomschrijving nog geen drie seconden, het antwoord is 63213...50798

Ik dacht dat het niet nodig zou zijn maar ik zie hier wel een paar oplossingen waarvan ik het vermoeden (!) heb dat er nog schaalbaarheids-issues in kunnen zitten, ik kan alleen niet iedereens code even makkelijk zelf draaien om dat te testen helaas. Ook de eventueel benodigde wijzigingen zijn lastiger voor mij in talen die ik niet ken

Even uit de onnodige recursion (na 3242 stappen via recursion kreeg ik geen output meer) gehaald en in een normale for loop gezet. 1.8s met dezelfde output als jij.

[Janoz]

ZieglerNichols schreef op dinsdag 14 december 2021 @ 08:42:
Ik had een off-by-one voor de test-input, dus heb mijn antwoord voor de echte input 1 kleiner gemaakt en dat was correct. Nu nog even uitzoeken waarom

Eén B vergeten mee te tellen in de totalen

[FrankMennink]

Dag 14 in Python

Zag al redelijk snel dat naief uitvoeren misschien nog wel ging werken voor deel 1 maar zeer waarschijnlijk niet voor deel 2 dus gelijk maar op een slimme manier aangepakt. Resulteerde in dat ik voor deel 2 enkel de 10 naar een 40 en ik had het antwoord. Deel 2 runt in 2.5ms

DataGhosts upping the ante draait in 1.5s

[ Voor 5% gewijzigd door FrankMennink op 14-12-2021 12:15 ]

[EfBe]

Had uiteraard het weer zo opgelost dat ik bij puzzle 2 opnieuw kon beginnen
https://github.com/FransB...lasses/PolymerProducer.cs

spoiler:

Duurde toch wel een kwartier voordat ik zag wat je moest doen. Toen nog de nodige domme counter errors oplossen en klaar

[iThinkSo]

DataGhost schreef op dinsdag 14 december 2021 @ 11:45:
Ehhhh, een mogelijke upping the ante is

spoiler:

50000 steps

spoiler:

Dat duurt op mijn trage laptop met de invoer uit de probleemomschrijving nog geen drie seconden, het antwoord is 63213...50798

Ik dacht dat het niet nodig zou zijn maar ik zie hier wel een paar oplossingen waarvan ik het vermoeden (!) heb dat er nog schaalbaarheids-issues in kunnen zitten, ik kan alleen niet iedereens code even makkelijk zelf draaien om dat te testen helaas. Ook de eventueel benodigde wijzigingen zijn lastiger voor mij in talen die ik niet ken

spoiler:

Ik denk dat een oplossing mbv LinAlg nog beter zou kunnen schalen, heb die zelf alleen niet uitgewerkt

[EfBe]

DataGhost schreef op dinsdag 14 december 2021 @ 11:45:
Ehhhh, een mogelijke upping the ante is

spoiler:

50000 steps

spoiler:

Dat duurt op mijn trage laptop met de invoer uit de probleemomschrijving nog geen drie seconden, het antwoord is 63213...50798

Welke invoer bedoel je precies? De invoer die je moet gebruiken als example? Ik krijg (nadat ik de int64's heb vervangen door unsigned int64's een ander antwoord (maar mn code levert wel de juiste oplossingen voor de puzzle invoer die je moet gebruiken)

met de invoer in de opdracht text:

spoiler:

6539418751133228486

met de invoer voor de puzzles:

spoiler:

14479253040420804840

[ Voor 11% gewijzigd door EfBe op 14-12-2021 12:13 ]

[DataGhost]

EfBe schreef op dinsdag 14 december 2021 @ 12:12:
[...]

Welke invoer bedoel je precies? De invoer die je moet gebruiken als example? Ik krijg (nadat ik de int64's heb vervangen door unsigned int64's een ander antwoord (maar mn code levert wel de juiste oplossingen voor de puzzle invoer die je moet gebruiken)

Precies die. Unsigned int64's gaan je niet helpen want de uitkomst is een getal van iets meer dan 15000 cijfers lang

[EfBe]

DataGhost schreef op dinsdag 14 december 2021 @ 12:13:
[...]
Precies die. Unsigned int64's gaan je niet helpen want de uitkomst is een getal van iets meer dan 15000 cijfers lang

LOL vandaar

[Janoz]

DataGhost schreef op dinsdag 14 december 2021 @ 12:13:
[...]

Precies die. Unsigned int64's gaan je niet helpen want de uitkomst is een getal van iets meer dan 15000 cijfers lang

Een mooie incentive om mijn histogram class ook even uit te breiden naar een BigInteger variant

Bij mij duurde het iets minder dan een seconden, maar dat komt vast omdat ik hier niet op een trage laptop zit

[TrailBlazer]

spoiler:

Met het tonen van die string stuurt hij je lekker het bos in. Ik zag gelukkig het al aankomen en dus gewoon lekker bijgehouden hoeveel van elk paartje er was. Het tellen van individuele elementen ging even mis omdat ik elk element dubbel tel nu even ranzig opgelost moet nog even kijken naar iets moois

[DataGhost]

TrailBlazer schreef op dinsdag 14 december 2021 @ 12:31:

spoiler:

Met het tonen van die string stuurt hij je lekker het bos in. Ik zag gelukkig het al aankomen en dus gewoon lekker bijgehouden hoeveel van elk paartje er was. Het tellen van individuele elementen ging even mis omdat ik elk element dubbel tel nu even ranzig opgelost moet nog even kijken naar iets moois

Simpel eigenlijk, volgens mij weet je elke stap precies

spoiler:

hoeveel letters erbij komen

[Remcoder]

DataGhost schreef op dinsdag 14 december 2021 @ 11:45:
Ehhhh, een mogelijke upping the ante is

spoiler:

50000 steps

spoiler:

Dat duurt op mijn trage laptop met de invoer uit de probleemomschrijving nog geen drie seconden, het antwoord is 63213...50798

Ik dacht dat het niet nodig zou zijn maar ik zie hier wel een paar oplossingen waarvan ik het vermoeden (!) heb dat er nog schaalbaarheids-issues in kunnen zitten, ik kan alleen niet iedereens code even makkelijk zelf draaien om dat te testen helaas. Ook de eventueel benodigde wijzigingen zijn lastiger voor mij in talen die ik niet ken

2.131 ms nadat ik alle longs vervangen heb door BigIntegers

Ik vermoed dat mijn oplossing dus gerust schaalbaar genoemd kan worden

[Dricus]

DataGhost schreef op dinsdag 14 december 2021 @ 11:45:
Ehhhh, een mogelijke upping the ante is

spoiler:

50000 steps

spoiler:

Dat duurt op mijn trage laptop met de invoer uit de probleemomschrijving nog geen drie seconden, het antwoord is 63213...50798

Ik dacht dat het niet nodig zou zijn maar ik zie hier wel een paar oplossingen waarvan ik het vermoeden (!) heb dat er nog schaalbaarheids-issues in kunnen zitten, ik kan alleen niet iedereens code even makkelijk zelf draaien om dat te testen helaas. Ook de eventueel benodigde wijzigingen zijn lastiger voor mij in talen die ik niet ken

Mijn Clojure oplossing doet er 1,6 seconde over. Niet slecht!

En voor de volledigheid: Het antwoord is

spoiler:

15053 digits lang. Een naïeve implementatie gaat dus never nooit in je RAM passen .

[ Voor 8% gewijzigd door Dricus op 14-12-2021 13:03 ]

[TrailBlazer]

DataGhost schreef op dinsdag 14 december 2021 @ 12:39:
[...]

Simpel eigenlijk, volgens mij weet je elke stap precies

spoiler:

hoeveel letters erbij komen

spoiler:

Klopt maar omdat ik initieel alleen de paartjes bijhield en later pas de letters per paar optel mis ik dus de eerste en laatste letter van de start string in mijn totalen

[iThinkSo]

spoiler:

Mijn oplossing nog aangepast met wat lineaire algebra truukjes (zou netter kunnen, doe nu "matrix multiplicatie" in O(n^3) vermenigvuldigingen, de challenge van @DataGhost draait nu in 800ms.

https://github.com/Synthe...lob/master/day14/day14.py

[breew]

haha... vraag 6 is hilarisch... eerste deel is eitje brute-forcen.. tweede deel loopt na stasp 150 keihard uit het geheugen..
totdat

spoiler:

je ziet dat je aantallen in bakjes kunt gooien en deze bakjes kunt doorschuiven

en dan is het ineens zo gepiept...

dag 6 in R

[ Voor 3% gewijzigd door breew op 14-12-2021 13:27 ]

[Cranzai]

iThinkSo schreef op dinsdag 14 december 2021 @ 13:16:

spoiler:

Mijn oplossing nog aangepast met wat lineaire algebra truukjes (zou netter kunnen, doe nu "matrix multiplicatie" in O(n^3) vermenigvuldigingen, de challenge van @DataGhost draait nu in 800ms.

https://github.com/Synthe...lob/master/day14/day14.py

spoiler:

Hmmm, lineaire algebra....
Werk je dan met een fixed volgorde voor alle combinaties ofzo en maak je een diagram zoals we die voor de visjes groei vraag met het histogram konden maken?

[Creepy]

Ik heb de juiste methode gevonden voor deel 2 van dag 14. Maar ergens zit een foutje want ik krijg nog niet het goede antwoord

[ydderf]

DataGhost schreef op dinsdag 14 december 2021 @ 09:48:
[...]
Leuke vandaag, ik las hem en kreeg direct flashbacks naar vorige week. Gelukkig klopte mijn gok dus deel 2 heb ik in 17 seconden correct ingestuurd

Thanks, dat was net genoeg om mij aan het denken te krijgen en tot een oplossing voor deel 2 in C# te komen die met 60msec de antwoorden vindt.
Programma technisch niet het mooiste omdat ik aan het klooien kwam met waardes inlezen vanuit een hashtable. Maar voor nu ff genoeg tijd gespendeerd aan de hobby.

spoiler:

Voor deel 2 hou ik bij hoevaak een pair voorkomt. En met elke ronde verdwijnen de pairs weer, maar komen er weer twee nieuwe pairs bij per pair.
En dan aan het einde de eerste letters van alle pairs tellen. En de laatste letter van je input niet vergeten.

[iThinkSo]

Cranzai schreef op dinsdag 14 december 2021 @ 13:33:
[...]

spoiler:

Hmmm, lineaire algebra....
Werk je dan met een fixed volgorde voor alle combinaties ofzo en maak je een diagram zoals we die voor de visjes groei vraag met het histogram konden maken?

spoiler:

Gebruik een dict[tuple, Counter[tuple]] ipv een matrix omdat ik dan m'n code minder hoefde aan te passen. Deze kan je namelijk ook "verdubbelen", en vervolgens een macht van nemen op dezelfde manier als dat je dat met een matrix zou doen.

Klinkt zo allemaal een beetje vaag, m'n code is redelijk leesbaar al zeg ik het zelf dus misschien is het makkelijkst om te kijken of je die snapt en terug te komen met een specifieke vraag wat ik in een bepaald stuk doe?

[TrailBlazer]

ydderf schreef op dinsdag 14 december 2021 @ 13:37:
[...]


Thanks, dat was net genoeg om mij aan het denken te krijgen en tot een oplossing voor deel 2 in C# te komen die met 60msec de antwoorden vindt.
Programma technisch niet het mooiste omdat ik aan het klooien kwam met waardes inlezen vanuit een hashtable. Maar voor nu ff genoeg tijd gespendeerd aan de hobby.

spoiler:

Voor deel 2 hou ik bij hoevaak een pair voorkomt. En met elke ronde verdwijnen de pairs weer, maar komen er weer twee nieuwe pairs bij per pair.
En dan aan het einde de eerste letters van alle pairs tellen. En de laatste letter van je input niet vergeten.

spoiler:

Dat is idd vee slimmer ik tel alle letter maar dan heb ik alles dubbel behalve de 1e en de laatste letter.

[Creepy]

ydderf schreef op dinsdag 14 december 2021 @ 13:37:

spoiler:

Voor deel 2 hou ik bij hoevaak een pair voorkomt. En met elke ronde verdwijnen de pairs weer, maar komen er weer twee nieuwe pairs bij per pair.
En dan aan het einde de eerste letters van alle pairs tellen. En de laatste letter van je input niet vergeten.

Ik doe precies hetzelfde. Het duurde alleen veel te lang voordat ik met dat idee kwam.
https://github.com/CodeEn...er/aoc/aoc2021/Day14.java

spoiler:

En daarna ipv Long ook nog BigIntegers moeten gebruiken anders klopte het nog steeds niet..

[Varienaja]

Creepy schreef op dinsdag 14 december 2021 @ 14:00:

spoiler:

En daarna ipv Long ook nog BigIntegers moeten gebruiken anders klopte het nog steeds niet..

OMG werkelijk? Dat is al de tweede keer dat ik zoiets lees. Dan heb ik veel geluk gehad. Tot nu lukt bij mij alles nog met 'gewone' datatypen.

[Creepy]

Varienaja schreef op dinsdag 14 december 2021 @ 14:03:
[...]

OMG werkelijk? Dat is al de tweede keer dat ik zoiets lees. Dan heb ik veel geluk gehad. Tot nu lukt bij mij alles nog met 'gewone' datatypen.

Ik ben toch een beetje te gaar vandaag blijkbaar. Met het gewone datatype werkt het ook prima. Geen idee wat er net nog mis ging dan..

[DataGhost]

Varienaja schreef op dinsdag 14 december 2021 @ 14:03:
[...]

OMG werkelijk? Dat is al de tweede keer dat ik zoiets lees. Dan heb ik veel geluk gehad. Tot nu lukt bij mij alles nog met 'gewone' datatypen.

Nog, ja. Nou is het niet gezegd dat het er wel in komt te zitten maar het lijkt me bij de makkelijkere dagen fijner om dit uitgezocht te hebben zodat je daar bij de moeilijkere dagen geen tijd meer aan kwijt bent

[Janoz]

Creepy schreef op dinsdag 14 december 2021 @ 14:10:
[...]

Ik ben toch een beetje te gaar vandaag blijkbaar. Met het gewone datatype werkt het ook prima. Geen idee wat er net nog mis ging dan..

Precies, die BigInteger had ik pas nodig toen ik 50000 ging proberen

[iThinkSo]

Nog een rewrite, vrij zeker dat heel veel sneller dan dit in Python niet kan:

code:

time python day14.py check --iterations 500000 > /dev/null

________________________________________________________
Executed in    8.52 secs    fish           external
   usr time    8.47 secs    0.41 millis    8.47 secs
   sys time    0.04 secs    1.10 millis    0.03 secs

( https://github.com/Synthe...4f7d047f1d/day14/day14.py )

[ Voor 12% gewijzigd door iThinkSo op 14-12-2021 15:26 ]

[DataGhost]

iThinkSo schreef op dinsdag 14 december 2021 @ 15:21:
Nog een rewrite, vrij zeker dat heel veel sneller dan dit in Python niet kan:

code:

time python day14.py check --iterations 500000 > /dev/null

________________________________________________________
Executed in    8.52 secs    fish           external
   usr time    8.47 secs    0.41 millis    8.47 secs
   sys time    0.04 secs    1.10 millis    0.03 secs

( https://github.com/Synthe...4f7d047f1d/day14/day14.py )

Voor het volledige antwoord waarschijnlijk niet, maar er is een upping the ante met 1000000000 iteraties die binnen een minuut klaar zou moeten zijn. Het antwoord mag dan modulo 1000000007 gegeven worden, wat volgens mij redelijk eenvoudig zou moeten zijn met jouw aanpak.

[ydderf]

Ik zag nog een mooie toepassing voor de vouwtelefoon voorbij komen
Dag 13 weergave op vouwtelefoon

[NickThissen]

Damn, ik dacht dat ik een prima methode gevonden had voor deel 2, maar die lijkt ook te langzaam helaas... Al 15 min bezig en is pas op driekwart

Mijn methode is misschien te simpel maar ik had dit bedacht:

spoiler:

1. Houd een count bij van elke mogelijke pair (BC, CB, BB, ...)
2. Initialize die count op de pairs die in de input template voorkomen.
3. Voor elke pair die voorkomt: check welke letter er tussen komt. Dit maakt 2 nieuwe pairs en de originele pair gaat weg. Bijvoorbeeld: AB->X geeft nieuwe pairs AX en XB, maar verwijdert pair AB. Omdat ik de count van alle pairs bij houdt kan ik gewoon de count van AX en XB ophogen, en de count van AB verminderen.
4. Ten slotte hou ik nog een aparte teller bij voor hoevaak elk karakter voorkomt, en die hoog ik met 1 op voor elk pair (in dit geval dus de count van X eentje hoger).

Dit geeft het juiste antwoord voor deel 1 en veel sneller, maar het lijkt nog steeds te langzaam voor deel 2


Edit
Aha, een overbodig loopje gevonden wat de boel "iets" (exponentieel) te vaak liet herhalen

[ Voor 5% gewijzigd door NickThissen op 14-12-2021 17:30 ]

[Martin Sturm]

NickThissen schreef op dinsdag 14 december 2021 @ 17:24:
Damn, ik dacht dat ik een prima methode gevonden had voor deel 2, maar die lijkt ook te langzaam helaas... Al 15 min bezig en is pas op driekwart

Mijn methode is misschien te simpel maar ik had dit bedacht:

spoiler:

1. Houd een count bij van elke mogelijke pair (BC, CB, BB, ...)
2. Initialize die count op de pairs die in de input template voorkomen.
3. Voor elke pair die voorkomt: check welke letter er tussen komt. Dit maakt 2 nieuwe pairs en de originele pair gaat weg. Bijvoorbeeld: AB->X geeft nieuwe pairs AX en XB, maar verwijdert pair AB. Omdat ik de count van alle pairs bij houdt kan ik gewoon de count van AX en XB ophogen, en de count van AB verminderen.
4. Ten slotte hou ik nog een aparte teller bij voor hoevaak elk karakter voorkomt, en die hoog ik met 1 op voor elk pair (in dit geval dus de count van X eentje hoger).

Dit geeft het juiste antwoord voor deel 1 en veel sneller, maar het lijkt nog steeds te langzaam voor deel 2


Edit
Aha, een overbodig loopje gevonden wat de boel "iets" (exponentieel) te vaak liet herhalen

spoiler:

Op zich zou dit snel genoeg moeten zijn. Je beschrijving klinkt niet heel anders dan dat ik het opgelost heb, en die van mij deed er 200ms over. Ik denk dat er iets anders niet helemaal lekker gaat. Welk datatype gebruik je?

Zie nu pas de edit... Mijn opmerking hierboven is dus nu nutteloos.

[NickThissen]

Al gevonden!

spoiler:

Ik deed een beetje dom: voor elk pair "AB" deed ik weer een loop van 1 tot aantal pairs AB, en verhoogde ik de counts met 1 elke iteratie. Maar die hele loop is overbodig en ik moet gewoon de count met "aantal AB pairs" verhogen.

[Kazu]

Ik kom er niet lekker uit vandaag, ik heb het idee dat mijn oplossing voor deel 2 sneller zou moeten zijn dan dat hij is. Misschien dat iemand een tip heeft?

spoiler:

Ik hou een count bij van alle letters, per paar trap ik een recursieve functie af die kijkt welke letter erbij komt, daarvan de count ophoogt, en van de twee nieuwe paren dezelfde recursieve functie start. De functie terminate wanneer hij 40 stappen is aangeroepen. Imo zou dit een stuk sneller moeten zijn dan de naive manier van continu de string opbouwen, maar toch duurt het te lang. Ik heb al de hele middag een achtergrondthread in m'n hoofd draaien op zoek naar een extra efficientieslag die ik zou kunnen maken, maar ik kom er maar niet op . Ik mis overduidelijk iets heel simpels

[KabouterSuper]

Kazu schreef op dinsdag 14 december 2021 @ 18:15:
Ik kom er niet lekker uit vandaag, ik heb het idee dat mijn oplossing voor deel 2 sneller zou moeten zijn dan dat hij is. Misschien dat iemand een tip heeft?

spoiler:

Ik hou een count bij van alle letters, per paar trap ik een recursieve functie af die kijkt welke letter erbij komt, daarvan de count ophoogt, en van de twee nieuwe paren dezelfde recursieve functie start. De functie terminate wanneer hij 40 stappen is aangeroepen. Imo zou dit een stuk sneller moeten zijn dan de naive manier van continu de string opbouwen, maar toch duurt het te lang. Ik heb al de hele middag een achtergrondthread in m'n hoofd draaien op zoek naar een extra efficientieslag die ik zou kunnen maken, maar ik kom er maar niet op . Ik mis overduidelijk iets heel simpels

Welke taal?

spoiler:

Volgens mij is de meest gebruikte aanpak om een count per paar bij te houden, niet per letter. Bij elke stap verandert elk paar in twee nieuwe paren. Pas aan het einde tel je de letters

[DataGhost]

Kazu schreef op dinsdag 14 december 2021 @ 18:15:
Ik kom er niet lekker uit vandaag, ik heb het idee dat mijn oplossing voor deel 2 sneller zou moeten zijn dan dat hij is. Misschien dat iemand een tip heeft?

spoiler:

Ik hou een count bij van alle letters, per paar trap ik een recursieve functie af die kijkt welke letter erbij komt, daarvan de count ophoogt, en van de twee nieuwe paren dezelfde recursieve functie start. De functie terminate wanneer hij 40 stappen is aangeroepen. Imo zou dit een stuk sneller moeten zijn dan de naive manier van continu de string opbouwen, maar toch duurt het te lang. Ik heb al de hele middag een achtergrondthread in m'n hoofd draaien op zoek naar een extra efficientieslag die ik zou kunnen maken, maar ik kom er maar niet op . Ik mis overduidelijk iets heel simpels

Als je kijkt naar hoe snel de string groeit in het voorbeeld (dit wil je even wiskundig uitrekenen denk ik)

spoiler:

en nog eens kijkt naar de definitie van jouw algoritme en hoeveel functie-calls je nodig hebt om tot de uitkomst van de volgende stap te komen

spoiler:

dan kan je uitrekenen of toch zeker een schatting maken hoeveel functie-calls je grofweg doet voor alle 40 stappen en je bedenken of dat voor het eind van het jaar klaar gaat zijn

Als je een betere aanpak wilt bedenken,

spoiler:

zou ik verder gaan met vooral het eerste gedeelte van je recursieve functie, en de rest ervan vergeten. Dit kan zonder recursie en je wilt dit ook zonder recursie doen. Moet je alleen nog iets anders bijhouden.

[Kazu]

KabouterSuper schreef op dinsdag 14 december 2021 @ 18:17:
[...]

Welke taal?

spoiler:

Volgens mij is de meest gebruikte aanpak om een count per paar bij te houden, niet per letter. Bij elke stap verandert elk paar in twee nieuwe paren. Pas aan het einde tel je de letters

DataGhost schreef op dinsdag 14 december 2021 @ 18:21:
[...]

Als je kijkt naar hoe snel de string groeit in het voorbeeld (dit wil je even wiskundig uitrekenen denk ik)

spoiler:

en nog eens kijkt naar de definitie van jouw algoritme en hoeveel functie-calls je nodig hebt om tot de uitkomst van de volgende stap te komen

spoiler:

dan kan je uitrekenen of toch zeker een schatting maken hoeveel functie-calls je grofweg doet voor alle 40 stappen en je bedenken of dat voor het eind van het jaar klaar gaat zijn

Als je een betere aanpak wilt bedenken,

spoiler:

zou ik verder gaan met vooral het eerste gedeelte van je recursieve functie, en de rest ervan vergeten. Dit kan zonder recursie en je wilt dit ook zonder recursie doen. Moet je alleen nog iets anders bijhouden.

Dat waren inderdaad even de nudges die ik nodig had. Ik bleef hangen in m'n oplossing, maar had niet even de moeite genomen om door te rekenen of het wel daadwerkelijk beter was.

Even ombouwen en dan kom ik terug

[DataGhost]

KabouterSuper schreef op dinsdag 14 december 2021 @ 18:17:
[...]

Welke taal?

spoiler:

Volgens mij is de meest gebruikte aanpak om een count per paar bij te houden, niet per letter. Bij elke stap verandert elk paar in twee nieuwe paren. Pas aan het einde tel je de letters

Dit kan je trouwens prima ook onderweg bijhouden bij de meeste algoritmes. Zo heb ik dat wel gedaan in ieder geval.

[YoToP]

Leuke puzzel,

Mijn inzending:

spoiler:

https://github.com/YoToP/AoC-2021/blob/main/14/p1.py

50000 iteraties lukt in 3 sec.. ben best tevreden al valt er nog wel wat te verbeteren. Maar ga toch mijn krachten sparen voor morgen
En ik denk ook dat het spannend wordt in de ranglijst voor wie het snelst part 2 heeft ingevoerd.

[Kazu]

Nou, toch nog met een oplossing gekomen. Balen dat ik zo lang vast bleef zitten, maargoed. Hopelijk gaat morgen beter

Uiteindelijke deel 2:

Members only:

Alleen zichtbaar voor ingelogde gebruikers. Inloggen

Was er niet helemaal tevreden over, dus een kleine cleanup gedaan aan het einde, maar voor nu laat ik het maar zo.

[P_Tingen]

Toen ik deel 1 las had ik al door dat mijn oplossing die ik nog moest gaan bedenken niet zou gaan werken voor deel 2.

spoiler:

Toch op de naïeve manier opgelost door een string te expanden. Ik heb het voor de vorm ook nog even op deel 2 geprobeerd en een tellertje mee laten lopen. Van 1 tot 12 zag ik hem niet verspringen, zo snel ging het. Daarna ging het steeds langzamer en toen ik een tijdje naar "16" had gekeken had ik al snel geëxtrapoleerd dat het waarschijnlijk voor mijn pensionering niet meer zou finishen.

AoC zelf zegt dat in principe alle opgaven op alle hardware binnen acceptabele tijd op te lossen moet zijn, dus als je oplossing lang duurt, weet je dat je op de verkeerde weg bent.

Ik had een paar hints nodig om op het goede spoor te komen, maar deel 2 is nu sneller dan deel 1 (117ms tegen 320ms). Ik heb de code voor deel 1 gelaten zoals hij was. Vind ik ook wel leuk, vorig jaar paste ik het programma nog wel eens zo aan dat het beide delen oploste, maar dat doe ik nu in principe niet meer, of er moet heel weinig verschil in zitten.

Dag 14 in Progress 4GL

[breew]

zo, dat was even zweten op het tweede deel van dag 8 (met R).. en het eerste deel was nog wel <1 minuut gefixt

[Verwijderd]

Creepy schreef op dinsdag 14 december 2021 @ 13:36:
Ik heb de juiste methode gevonden voor deel 2 van dag 14. Maar ergens zit een foutje want ik krijg nog niet het goede antwoord

Wat voor mij een instinker was, was dat ik (zoals zoveel anderen ook hier) een lijst met mogelijke paren bijhield, voor de voorbeeldvraag met 'doubles'werkte, en toen ik overging naar unsigned longs ff vergeten was dat er ook een stap was waar de 'oude' inhoud eraf getrokken werd...
Koste me wel wat tijd...

[Verwijderd]

DataGhost schreef op dinsdag 14 december 2021 @ 18:27:
[...]

Dit kan je trouwens prima ook onderweg bijhouden bij de meeste algoritmes. Zo heb ik dat wel gedaan in ieder geval.

ellicht banale vraag, maar ik ga 'm toch stellen, welke talen ondersteunen native die enorme getallen waar jij zo nu en dan mee stoeit?

[iThinkSo]

Verwijderd schreef op dinsdag 14 december 2021 @ 20:47:
[...]


ellicht banale vraag, maar ik ga 'm toch stellen, welke talen ondersteunen native die enorme getallen waar jij zo nu en dan mee stoeit?

Python onder andere, maar iedere moderne programmeertaal heeft wel een biginteger library

[DataGhost]

Verwijderd schreef op dinsdag 14 december 2021 @ 20:47:
[...]


ellicht banale vraag, maar ik ga 'm toch stellen, welke talen ondersteunen native die enorme getallen waar jij zo nu en dan mee stoeit?

O.a. Python ondersteunt dat native, in de meeste andere talen zijn er gewoon libraries voor als het er niet native in zit. In sommige talen moet je dat nog expliciet aangeven bij het declareren van je variabelen, in Python zijn ints in ieder geval altijd "oneindig" groot, het wordt alleen een keertje behoorlijk langaam. Maar is die vraag specifiek op die quote gericht? Want dat in m'n quote, daar heb je die grote getallen nog lang niet voor nodig, past allemaal prima in 64 bits.

[Lisper]

Vandaag toch weer Clojure gebruikt in plaats van Rust, beetje weinig tijd gehad vandaag dus ik had geen zin in geruzie met de borrow checker. Gelukkig is het snel genoeg zo.

Dag 14 in Clojure

[ Voor 25% gewijzigd door Lisper op 14-12-2021 22:50 ]

[ElkeBxl]

Dag 14 in Rust gedaan. Vanavond eindelijk de tijd gevonden om er op te focussen op deel 2.

[MrHaas]

Dag 15 was al weer iets lastiger maar nog prima te doen

spoiler:

BFS gebruikt en risks per punt bijgehouden en opnieuw processen als deze lager is (is dat niet Dijkstra?). Niet meest optimale algoritme aangezien deel 2 er 6 seconden over deed maar goed genoeg voor nu. Verder te lang gestruggeld met deel 2 om de grid uit te breiden, had beter numpy kunnen gebruiken . https://github.com/arjand...ain/python/15/solution.py

[ZieglerNichols]

Dag 15 in MATLAB

spoiler:

Uit de vraag kon ik al zien dat dit met A* opgelost kan worden, maar ik had dat nog nooit zelf geïmplementeerd, dus maar even wat pseudocode van Wikipedia omgezet naar een MATLAB script.

[armageddon_2k1]

Dag 15 in Kotlin

Deze was leuk, vooral ook omdat ik toevallig met deze materie bezig ben voor mijn werk.

Dit is natuurlijk een klassiek voorbeeld van:

spoiler:

Dijkstra

.

Mooi dat ik die algoritmes laatst in mijn common module gegooid had, dus het was zo gepiept.

[Verwijderd]

DataGhost schreef op dinsdag 14 december 2021 @ 22:22:
[...]

O.a. Python ondersteunt dat native, in de meeste andere talen zijn er gewoon libraries voor als het er niet native in zit. In sommige talen moet je dat nog expliciet aangeven bij het declareren van je variabelen, in Python zijn ints in ieder geval altijd "oneindig" groot, het wordt alleen een keertje behoorlijk langaam. Maar is die vraag specifiek op die quote gericht? Want dat in m'n quote, daar heb je die grote getallen nog lang niet voor nodig, past allemaal prima in 64 bits.

bedankt, nee, niet specifiek die quote. Al kwam gisteren de max grootte wel heel dichtbij. Maar goed te weten dat python dus oneindig grote getallen (ints neem ik aan) kan gebruiken.

[ydderf]

Hmmm, gezien de input grote zal de brute force methode wel weer ff bezig zijn....

[ZieglerNichols]

Verwijderd schreef op dinsdag 14 december 2021 @ 20:47:
[...]


ellicht banale vraag, maar ik ga 'm toch stellen, welke talen ondersteunen native die enorme getallen waar jij zo nu en dan mee stoeit?

MATLAB ondersteunt dit ook via de Symbolic Math Toolbox:

>> 2^2317

ans =

Inf

>> sym(2)^2317

ans =

30654903508108357077958654144825937585978808922337901521692741170911447076693116235513237095579066485773937279334784139954181575840986269850991750398202331213943274278112396793424683275528507127617356737974156212114985333650793917021532655353073330339869206521452698460733186617040160262848093715277704279290680230304150547684590960276420040187406068172642162633162861058913834479146788713758308941909711983231722076836272997428595743463045969399361824711110350992834115834375631290260030543671026084690659491964528746134305444576187523233231429766154483330868291973263704666586462246580637588991629908758131771642269031718471782924220000298094429698919484347691856871276393621193756312248959107072

[Diderikdm]

Python dag 15

Ze worden al moeilijker Ik kan wel echt nog wel wat refactoren denk ik te zien aan hoe lang mijn code erover doet, maar ben blij dat die het doet

0:00:00.639212
0:01:28.586831

spoiler:

Waarschijnlijk is q = sorted(q) een vrij exponentieel dure operatie, en is heapq hier beter op zn plek

[ Voor 24% gewijzigd door Diderikdm op 15-12-2021 09:38 ]

[Janoz]

Diderikdm schreef op woensdag 15 december 2021 @ 08:57:

spoiler:

Waarschijnlijk is q = sorted(q) een vrij exponentieel dure operatie, en is heapq hier beter op zn plek

spoiler:

Kopt. Je bent helemaal niet geïnteresseerd in de hele gesorteerde lijst. Je wilt alleen de kleinste weten. Wel vreemd dat hij er alsnog zo lang over doet. Mijn Dijkstra implementatie heft een halve seconde nodig voor Deel2

[DataGhost]

Janoz schreef op woensdag 15 december 2021 @ 10:10:
[...]

spoiler:

Kopt. Je bent helemaal niet geïnteresseerd in de hele gesorteerde lijst. Je wilt alleen de kleinste weten. Wel vreemd dat hij er alsnog zo lang over doet. Mijn Dijkstra implementatie heft een halve seconde nodig voor Deel2

spoiler:

Als je elke iteratie het ding helemaal opnieuw gaat sorteren kan het wel eventjes duren ja, dan is je insertion effectief O(n log n) ipv O(log n). Als je dat n keer doet schiet het op

Het viel me trouwens tegen dat de (fatsoenlijke) datastructuur hiervoor niet standaard in Python zit. En ook dat ik die de afgelopen twee jaar kennelijk niet nodig heb gehad. Daar ga ik denk ik toch maar een klasse voor schrijven want de implementatie die er wel in zit vind ik veel te traag.

spoiler:

Wie verzint dat je dat effectief in een sorted list moet bijhouden?

Edit: nou ja, die klasse zit er dus wel in maar die is er strikt genomen niet voor bedoeld, en nog 2x zo langzaam. Misschien is de input gewoon groot genoeg, dat het echt vier seconden kost om uit te rekenen.
Edit2: de originele functies die ik ervoor gebruikt had zijn kennelijk wel in O(log n) geimplementeerd dus dan klopt die looptijd gewoon. Een klasse eromheen zou alleen voor een klein beetje leesbaarheid zijn.

[ Voor 41% gewijzigd door DataGhost op 15-12-2021 15:29 ]

[Diderikdm]

Janoz schreef op woensdag 15 december 2021 @ 10:10:
[...]

spoiler:

Kopt. Je bent helemaal niet geïnteresseerd in de hele gesorteerde lijst. Je wilt alleen de kleinste weten. Wel vreemd dat hij er alsnog zo lang over doet. Mijn Dijkstra implementatie heft een halve seconde nodig voor Deel2

spoiler:

Nu tot 36s afgeschaafd.. Moet wel nog iets vinden op die list die ik (nu) telkens opnieuw opbouw, dat is de bottleneck uiteindelijk denk ik in deze versie

[Devilfish]

Deel 1 al behoorlijk effectief opgepakt, maar wist bij deel 2 dat het toch te traag zou gaan zijn. Ik wou al zelf iets bouwen, maar kwam achter een nieuwigheidje in .Net 6 (

spoiler:

PriorityQueue

, dus die gebruikt en het was in eens allemaal razend snel .

spoiler:

Dag 16 in C#

[EfBe]

Die was weer eens erg makkelijk (als je het zag uiteraard)
https://github.com/FransB...src/AoC2021.Code/Day15.cs

spoiler:

Dacht eerst aan Dijkstra's Shortest Path, maar overkill. Het idee is hetzelfde overigens: vervang de minimal risk van een cel in de grid wanneer een pad die cel bereikt met minder risk. Wanneer dat gebeurt enqueue je die nieuwe cel, anders niet (want het pad is dan al meer risk). In feite vloei je de risk values over de grid en gaat alleen verder met een cel als die kan leiden tot een pad met minder riks.

Geen priority queue gebruikt, gewoon een grid met per cel de risk voor die cel. Dacht nog even aan het uitwerken van de source tile naar een volledig array voor deel 2 maar dat was niet nodig, een berekeningetje voor de echte source risk voor een cel was niet zo moeilijk.

[ Voor 31% gewijzigd door EfBe op 15-12-2021 10:58 ]

[TrailBlazer]

Kan iemand met wat hints geven

spoiler:

Ik kan het sample oplossen met recursion maar de echte puzzel niet als gevolg van een recursion depth issue. Is recursion gewoon de foute methode doordat het aantal paden gewoon te groot is.

[DataGhost]

TrailBlazer schreef op woensdag 15 december 2021 @ 10:55:
Kan iemand met wat hints geven

spoiler:

Ik kan het sample oplossen met recursion maar de echte puzzel niet als gevolg van een recursion depth issue. Is recursion gewoon de foute methode doordat het aantal paden gewoon te groot is.

Ja.

spoiler:

Je zal het probleem dus moeten opsplitsen in een soort sub-probleem waarvan je de uitkomst bijhoudt

[ Voor 14% gewijzigd door DataGhost op 15-12-2021 10:57 ]

[Diderikdm]

TrailBlazer schreef op woensdag 15 december 2021 @ 10:55:
Kan iemand met wat hints geven

spoiler:

Ik kan het sample oplossen met recursion maar de echte puzzel niet als gevolg van een recursion depth issue. Is recursion gewoon de foute methode doordat het aantal paden gewoon te groot is.

Yes.

spoiler:

De map is al 100x100, dus stel je zou een recht pad kunnen volgen, zit je al op minimaal 1000 stappen/recursion depth

[DataGhost]

Diderikdm schreef op woensdag 15 december 2021 @ 10:58:
[...]


Yes.

spoiler:

De map is al 100x100, dus stel je zou een recht pad kunnen volgen, zit je al op minimaal 1000 stappen/recursion depth

- nvm deel 2

[ Voor 5% gewijzigd door DataGhost op 15-12-2021 11:00 ]

[EfBe]

TrailBlazer schreef op woensdag 15 december 2021 @ 10:55:
Kan iemand met wat hints geven

spoiler:

Ik kan het sample oplossen met recursion maar de echte puzzel niet als gevolg van een recursion depth issue. Is recursion gewoon de foute methode doordat het aantal paden gewoon te groot is.

spoiler:

Je zit op (x,y), je gaat dan kijken welke cellen kun je bereiken. Als je daar naartoe gaat, wat wordt dan de risk van die cel, in acht nemende de risk van (x, y)? Is de risk van die nieuwe cel dan, komende van (x, y) lager dan dat hij op dit moment is? Zo ja dan heb je een nieuw pad ontdekt naar die cel die kan werken. Je gaat dan verder kijken vanaf die cel (maar niet met recursie). Is de risk hoger, dan gaat dat pad het nooit worden dus doe je niets.

MrHaas schreef op woensdag 15 december 2021 @ 07:04:

spoiler:

BFS gebruikt en risks per punt bijgehouden en opnieuw processen als deze lager is (is dat niet Dijkstra?).

Heb hetzelfde gedaan Ja lijkt er wel op, althans het idee van het algoritme is hetzelfde.

[ Voor 16% gewijzigd door EfBe op 15-12-2021 11:05 ]

[Diderikdm]

DataGhost schreef op woensdag 15 december 2021 @ 10:59:
[...]

- nvm deel 2

spoiler:

Oh ja, ik zat wel aan deel 1 te denken tijd voor koffie

[ Voor 8% gewijzigd door Diderikdm op 15-12-2021 11:09 ]

[Creepy]

Wel begonnen maar nog geen werkende oplossing, en genoeg andere dingen te doen vandaag. Ergens vandaag weer verder

spoiler:

Begonnen met recursief doorrekenen en direct te stoppen zodra de huidige score groter ie dan de bestaande laagste maar dat faalde uiteraard al gelijk in deel 1. De oplossing nu is duidelijk: kortste pad algoritme van Dijksta. Maar die is dus later voor vandaag

[Hydra]

Ok, dafuq. Deel 1 werkt prima, deel 2 werkt prima met de voorbeeldinput.

spoiler:

Maar met de 'echte' input is het gewoon te traag. Kennelijk is mij implementatie van Dijkstra niet bepaald efficient Ik denk dat ik wel weet waar het aan ligt, ik heb alleen nu ff geen tijd meer het te fixen

Edit: En done! Was gewoon een domme fout...

[ Voor 7% gewijzigd door Hydra op 15-12-2021 11:47 ]

[Janoz]

EfBe schreef op woensdag 15 december 2021 @ 10:54:
Die was weer eens erg makkelijk (als je het zag uiteraard)
https://github.com/FransB...src/AoC2021.Code/Day15.cs

spoiler:

Dacht eerst aan Dijkstra's Shortest Path, maar overkill. Het idee is hetzelfde overigens: vervang de minimal risk van een cel in de grid wanneer een pad die cel bereikt met minder risk. Wanneer dat gebeurt enqueue je die nieuwe cel, anders niet (want het pad is dan al meer risk). In feite vloei je de risk values over de grid en gaat alleen verder met een cel als die kan leiden tot een pad met minder riks.

Geen priority queue gebruikt, gewoon een grid met per cel de risk voor die cel. Dacht nog even aan het uitwerken van de source tile naar een volledig array voor deel 2 maar dat was niet nodig, een berekeningetje voor de echte source risk voor een cel was niet zo moeilijk.

spoiler:

Ik heb je algoritme eens geprobeerd naast mijn dijkstra implementatie, maar hij is maar marginaal sneller. Ik gok iets van 20%. Het is ook niet vreemd dat jou voorstel in dit geval niet significant sneller is omdat ten eerste de kosten per stap in een relatief kleine range vallen en goed verdeeld zijn, en ten tweede omdat de route die we zoeken de langste Manhattan-distance heeft. Beiden zorgen ervoor dat een significant deel van alle punten een lager risico hebben. Je bent eigenlijk maar een relatief klein deel van je veld aan het uitsluiten.

spoiler:

Oh wacht, had ergens een inefficient stukje. Je oplossing is eerder een derde sneller.

[ Voor 3% gewijzigd door Janoz op 15-12-2021 11:45 ]

[Hydra]

Dag 15 in Kotlin

spoiler:

Grootste deel van de implementatie zit in een generieke Dijkstra implementatie, hierzo.

Veel tijd kwijt geweest aan twijfelen over data structuren en er ook achter komen dat ik allemaal half-geimplementeerde versies heb van voorgaande jaren die weer net niet lekker werken.

Moet dat echt eens op gaan schonen en ook gaan zorgen dat ik voor elk type search maar 1 generieke Graph search gebruik. Maar da's leuk voor later. Ooit

[EfBe]

Janoz schreef op woensdag 15 december 2021 @ 11:38:
[...]

spoiler:

Ik heb je algoritme eens geprobeerd naast mijn dijkstra implementatie, maar hij is maar marginaal sneller. Ik gok iets van 20%. Het is ook niet vreemd dat jou voorstel in dit geval niet significant sneller is omdat ten eerste de kosten per stap in een relatief kleine range vallen en goed verdeeld zijn, en ten tweede omdat de route die we zoeken de langste Manhattan-distance heeft. Beiden zorgen ervoor dat een significant deel van alle punten een lager risico hebben. Je bent eigenlijk maar een relatief klein deel van je veld aan het uitsluiten.

spoiler:

Oh wacht, had ergens een inefficient stukje. Je oplossing is eerder een derde sneller.

Heh Ik had het niet zo geimplementeerd vanwege efficientie overigens, maar meer omdat het simpeler te implementeren was Maar wel mooi dat het sneller is, dat is dan weer mooi meegenomen Ik heb nog niet naar Tarjan's variant van Dijkstra gekeken hoe die het heeft verbeterd, en of dat nog een optimalere benadering oplevert.

[KabouterSuper]

Pffft...Het ging zo lekker vandaag.
Deel 1 testdata: goed
Deel 1 eigen data: goed
Deel 2 testdata: goed
Deel 2 eigen data: fout

spoiler:

Kom ik er na een tijd achter dat het pad niet per se alleen naar rechts of onder hoeft te gaan, wat wel zo was in alle voorbeelden.

Toen maar een handvol extra iteraties toegevoegd om boven en links ook te checken. Dus de eerste run vul ik een matrix met risks vanuit rechts/onder, daarna verbeter ik mijn matrix vanuit links/onders/boven/rechts. Daarmee heb ik het goede antwoord gekregen, maar waarschijnlijk is het algoritme niet generiek te gebruiken.

[NickThissen]

spoiler:

Deel 1 dacht ik meteen aan Dijkstra, en eigenlijk had ik al het idee dat deel 2 op een of andere manier onmogelijk zou zijn met Dijkstra (ofwel een variant ervan moeten verzinnen of niet efficient genoeg meer). Maar mijn implementatie werkte ook meteen voor deel 2. Eigenlijk wel jammer, ik had het wel leuk gevonden als je voor deel 2 een twist op Dijkstra moest verzinnen, nu heb ik gewoon wat pseudocode overgetikt en het werkt zonder dat ik 100% begrijp wat ik nou doe.

[armageddon_2k1]

NickThissen schreef op woensdag 15 december 2021 @ 14:00:

spoiler:

Deel 1 dacht ik meteen aan Dijkstra, en eigenlijk had ik al het idee dat deel 2 op een of andere manier onmogelijk zou zijn met Dijkstra (ofwel een variant ervan moeten verzinnen of niet efficient genoeg meer). Maar mijn implementatie werkte ook meteen voor deel 2. Eigenlijk wel jammer, ik had het wel leuk gevonden als je voor deel 2 een twist op Dijkstra moest verzinnen, nu heb ik gewoon wat pseudocode overgetikt en het werkt zonder dat ik 100% begrijp wat ik nou doe.

spoiler:

Je bedoelt A*?

[NickThissen]

armageddon_2k1 schreef op woensdag 15 december 2021 @ 14:17:
[...]

spoiler:

Je bedoelt A*?

spoiler:

Nee, niet echt. Ik bedoelde meer: misschien dat in deel 2 je bepaalde gebieden meerdere keren moest bezoeken, of sommige doorgangen maar in een richting mogelijk zijn, etc, dat soort twists. Waardoor je je algoritme moet aanpassen en niet gewoon een Dijkstra library kan gebruiken of overtypen

[Hydra]

KabouterSuper schreef op woensdag 15 december 2021 @ 12:25:

spoiler:

Kom ik er na een tijd achter dat het pad niet per se alleen naar rechts of onder hoeft te gaan, wat wel zo was in alle voorbeelden.

Je bent niet de enige als ik zo naar de reacties op Reddit kijkt. M.i. had de tekst dat wel een stuk explicieter kunnen maken.

[armageddon_2k1]

NickThissen schreef op woensdag 15 december 2021 @ 14:20:
[...]

spoiler:

Nee, niet echt. Ik bedoelde meer: misschien dat in deel 2 je bepaalde gebieden meerdere keren moest bezoeken, of sommige doorgangen maar in een richting mogelijk zijn, etc, dat soort twists. Waardoor je je algoritme moet aanpassen en niet gewoon een Dijkstra library kan gebruiken of overtypen

spoiler:

Tja, de uitdaging zit hem hier er in dat je Dijkstra kan herkennen. Alhoewel nogal obvious was, als je hem kent. Daarna kan je natuurlijk gewoon zelf Dijkstra implementeren. De keuze om een library te gebruiken of over te typen is natuurlijk de eigen

[NickThissen]

armageddon_2k1 schreef op woensdag 15 december 2021 @ 14:29:
[...]

spoiler:

Tja, de uitdaging zit hem hier er in dat je Dijkstra kan herkennen. Alhoewel nogal obvious was, als je hem kent. Daarna kan je natuurlijk gewoon zelf Dijkstra implementeren. De keuze om een library te gebruiken of over te typen is natuurlijk de eigen

Laat ik het anders uitleggen; ik had dit in gedachte:

spoiler:

Part 1: "oh dat is toch gewoon Dijkstra? Maar ik gok dat part 2 dan niet meer simpel via Dijkstra kan of ik een twist moet implementeren. Ik heb ooit een Dijkstra algoritme geprogrammeerd maar dat is veel te lang geleden: ik ga toch gewoon part 1 met Dijkstra doen en dan ben ik benieuwd hoe part 2 dit breekt en wat ik moet aanpassen."
Part 2: "oh, het werkt nog steeds met Dijkstra, wat saai."

Ik heb overigens geen library gebruikt maar de pseudocode op Wikipedia gebruikt om het zelf te implementeren, maar dat is natuurlijk ook niet echt spannend.

[Lisper]

Dag 15 in Rust, ik vond het vandaag goed te doen, ik dacht gelukkig meteen aan Dijkstra's algoritme. Ik verwachte ook in deel 2 een twist, maar het viel mee.

Ik wilde proberen Dijkstra's algoritme zelf te schrijven, maar toen zag ik op de docs van de rust priority queue een implementatie en heb ik het daar maar op gebaseerd.

[ Voor 32% gewijzigd door Lisper op 15-12-2021 14:44 ]

[ydderf]

Day 15 in C#
Hij is gelukt, zonder gebruik te maken van een library oid. Maar deel twee koste wel 2000 seconde....

spoiler:

Geprobeerd om deze uilteg te programmeren.
Voor mijn gevoel kost vooral deze instructie veel tijd:
riskMap.Where(x => x.Value.visited == false).OrderBy(x => x.Value.Risk).FirstOrDefault().Key;
Maar ik weet niet of het mogelijk is om Visual Studio Code te laten bepalen welke instructies het langs duren.

Heb nog gedacht om tussendoor mijn lijst op te schonen of uit te bereiden. In het begin interesseert me eigenlijk nog niet de posities met X of Y > 10. Maar daar ben ik nog niet aan toegekomen.

Ook hier moest ik voor deel 2 naar links en boven zoeken om mijn route te vinden.

[DataGhost]

NickThissen schreef op woensdag 15 december 2021 @ 14:34:
[...]

Laat ik het anders uitleggen; ik had dit in gedachte:

spoiler:

Part 1: "oh dat is toch gewoon Dijkstra? Maar ik gok dat part 2 dan niet meer simpel via Dijkstra kan of ik een twist moet implementeren. Ik heb ooit een Dijkstra algoritme geprogrammeerd maar dat is veel te lang geleden: ik ga toch gewoon part 1 met Dijkstra doen en dan ben ik benieuwd hoe part 2 dit breekt en wat ik moet aanpassen."
Part 2: "oh, het werkt nog steeds met Dijkstra, wat saai."

Ik heb overigens geen library gebruikt maar de pseudocode op Wikipedia gebruikt om het zelf te implementeren, maar dat is natuurlijk ook niet echt spannend.

Nja er zijn natuurlijk voldoende oplossingen die voor deel 1 wel snel zijn maar voor deel 2 niet, dus dat je voor deel 1 toevallig het goede algoritme pakte... tsja, daar moet je eigenlijk alleen maar blij mee zijn. Als je het verder geen uitdaging vond omdat je het hebt overgetikt kan je natuurlijk altijd nog gaan beredeneren hoe het algoritme werkt, waarom het werkt en waarom het werkt zoals het werkt. Dat lijkt me ook veel nuttiger voor als je het over een paar dagen aan moet gaan passen. Ik ken het algoritme ondertussen goed genoeg om het uit m'n hoofd uit te typen, de wikipedia-pseudocode vind ik eigenlijk zelfs een beetje tegenintuitief. Het is eigenlijk hetzelfde algoritme als twee andere vergelijkbare algoritmes, alleen heeft elk van die drie een verschillende onderliggende datastructuur die het complete gedrag van het algoritme aanpast. Het kan zeker nuttig zijn om ook die verschillen en overeenkomsten te zien en beredeneren waarom ze er zijn.

[iThinkSo]

Zelf een search algo in elkaar geknutseld, niet super snel maar had geen zin om op te zoeken hoe de "standaard" algos ook al weer gingen...


https://github.com/Synthe...b1edf3db28/day15/day15.py

[Soultaker]

Dag 15 in Python

Easy-peasy als je bekend bent met het juiste algoritme.

[Janoz]

NickThissen schreef op woensdag 15 december 2021 @ 14:00:

spoiler:

nu heb ik gewoon wat pseudocode overgetikt en het werkt zonder dat ik 100% begrijp wat ik nou doe.

Misschien is jouw uitdaging voor vandaag dan om eens te proberen het algo wel 100% te begrijpen

spoiler:

Het leuke aan Dijkstra is dat het een redelijk complex, maar makkelijk voor te stellen probleem oplost met een paar relatief simpele regeltjes waarbij je vervolgens ook nog met allemaal verschillende datastructuren in aanraking komt, (mits je de variant neemt met een priority queue).

Als je aan geeft welke procenten je nog niet begrijpt van het algo, dan wil ik ze best proberen uit te leggen.

[NickThissen]

Nee hoor ik begrijp het algoritme prima, ik overdreef een beetje. Punt was meer: zonder het nog eens op te zoeken had ik het niet zomaar uit m'n hoofd getypt, maar met het opzoeken was ik ook binnen 10 min klaar. De puzzels waar je iets niet zomaar van internet kan plukken vind ik leuker haha.

[P_Tingen]

Pff, tijd vastgezeten.

spoiler:

Eerst geprobeerd naïef op te lossen. Testinput lukte wel maar duurde al relatief lang. Dus niet de goede aanpak. Toen Dijkstra herkend en geprobeerd te implementeren, maar kennelijk toch wat roestig.

Uiteindelijk met hulp van https://www.program-uurtje.org/kortstepad.html#fase3 toch op weten te lossen. Mooie uitleg!

Nu deel 2 nog....

[Cranzai]

Wie heeft zin om mee te kijken? Ik zit vast
https://github.com/Cranza...021/day15/python/day15.py
De code is nog een zootje maar dat komt door het debuggen

spoiler:

Mijn intentie was om een soort van depth-first Dijkstra algoritme te gebruiken.
Neem je uitgangspositie, ga vervolgens alle buur-coordinaten af in volgorde van groot naar klein.
Dit probeer ik recursief te doen met bijhouden van paden.

Ik krijg 3 paden als antwoord voor het voorbeeld maar allen zijn fout, ze gaan namelijk allemaal alleen rechtsaf ipv naar beneden te gaan.

Met alle deepcopy's en het spawnen van nieuwe instances ben ik volledig in de war.

[ Voor 5% gewijzigd door Cranzai op 15-12-2021 16:47 ]

[Remcoder]

8 seconden voor deel 2, dat moet sneller kunnen

Members only:

Alleen zichtbaar voor ingelogde gebruikers. Inloggen

spoiler:

Straks maar Dijkstra met een priority queue proberen

[Kazu]

KabouterSuper schreef op woensdag 15 december 2021 @ 12:25:
Pffft...Het ging zo lekker vandaag.
Deel 1 testdata: goed
Deel 1 eigen data: goed
Deel 2 testdata: goed
Deel 2 eigen data: fout

spoiler:

Kom ik er na een tijd achter dat het pad niet per se alleen naar rechts of onder hoeft te gaan, wat wel zo was in alle voorbeelden.

Toen maar een handvol extra iteraties toegevoegd om boven en links ook te checken. Dus de eerste run vul ik een matrix met risks vanuit rechts/onder, daarna verbeter ik mijn matrix vanuit links/onders/boven/rechts. Daarmee heb ik het goede antwoord gekregen, maar waarschijnlijk is het algoritme niet generiek te gebruiken.

Hahaha, ik had precies hetzelfde probleem.

spoiler:

Ik interpreteerde de "restricting your motion to two dimensions" i.c.m. het voorbeeld wat alleen naar rechts/beneden ging alszijnde dat naar boven of links bewegen verboden was. Alleen bij mij had deel 1 ook al een actie naar boven nodig, dus ik maar uit proberen te vlooien waarom al m'n testcases gewoon goed waren, maar de input niet werkte...

Maar verder was ie goed te doen.

spoiler:

Ik had meteen bij deel 1 al voor Dijkstra gekozen, omdat ik er al vanuit ging dat de map bij deel 2 een stuk groter zou worden. Wel de poor-man's versie van de queue geimplementeerd, maar ik kom er net achter dat Go wat native packages heeft hiervoor, dus die ga ik nog eens even verbeteren.

Uiteindelijk deel 2 in 1.8s, dus dat kan nog beter.

Members only:

Alleen zichtbaar voor ingelogde gebruikers. Inloggen

[ Voor 3% gewijzigd door Kazu op 15-12-2021 17:05 ]

[Hydra]

spoiler:

Zo, de hele bende omgebouwd naar een Dijkstra search met een PriorityQueue op basis van een Graph. Wel fijn om nu gewoon een willekeurige 'ding' naar een Graph om te kunnen zetten en dan gewoon de kortste route te kunnen vinden.

Het gebruik van de PriorityQueue ipv een simpele Set haalde de runtime van 12s naar 6s, lekkere verbetering dus.

Taak voor morgen: A* imlementeren!

[deboder]

P_Tingen schreef op woensdag 15 december 2021 @ 15:36:
Pff, tijd vastgezeten.

spoiler:

Eerst geprobeerd naïef op te lossen. Testinput lukte wel maar duurde al relatief lang. Dus niet de goede aanpak. Toen Dijkstra herkend en geprobeerd te implementeren, maar kennelijk toch wat roestig.

Uiteindelijk met hulp van https://www.program-uurtje.org/kortstepad.html#fase3 toch op weten te lossen. Mooie uitleg!

Nu deel 2 nog....

Ahh, fijn dat je weer vrij bent en de advent kan doen.
Heb je daar programmeren geleerd ?
Mooi geschreven tutorial page !

[Dricus]

Dag 15 in Clojure

Eerst had ik...

spoiler:

A* geïmplementeerd (zonder priority queue).

Dat was echt bokketraag (25 seconden voor deel 2), en de code verdiende ook niet de schoonheidsprijs.

Toen heb ik, om de code wat simpeler te krijgen en de performance te verbeteren...

spoiler:

Dijkstra geïmplementeerd, met een priority queue.

Daarmee zit ik nu op 1,5 seconde voor deel 2. De code zou nog steeds wel wat leesbaarder kunnen...

[evanraalte]

Pff vandaag ging niet zo lekker.

Eerst bruteforce, toen dat te traag bleek een eigen dijkstra implementatie geschreven. Daarna werkte het nog niet omdat ik niet naar boven en links keek (Jaja lezen, maar ik keek naar de voorbeeld input).

Vervolgens deel 2 geschreven. Het voorbeeld ging goed met een executie tijd van 6 seconden . Daarna de echte input aangezet, en 2.5 uur later had ik m'n resultaat .

Helaas snap ik niet helemaal waarom mijn implementatie zo traag was.. Ik had geen dequeue gebruikt, maar ik had niet het idee dat het zoveel trager zou zijn:
https://github.com/evanra...ob/master/python/day15.py

Ook excuus voor de beun code, ik was het een beetje zat op het laatst

[ Voor 5% gewijzigd door evanraalte op 15-12-2021 18:56 ]

[breew]

ok, inlopen gaat nog steeds sneller dan er puzzels bijkomen
inmiddels dag 10 klaar (in R)... was ff klooien, tot ik echter kwam dat ik in de code een { had gebruikt wat een } had moeten zijn

[ Voor 12% gewijzigd door breew op 15-12-2021 19:27 ]