Advent of Code 2021

[Dricus]

Ik heb zelfs nog colored debug output gemaakt om de analyse te vergemakkelijken (plaatje is klikbaar).

[armageddon_2k1]

Dricus schreef op zondag 19 december 2021 @ 14:13:
Dag 18 in Kotlin

Ik had gewoon geen idee hoe ik dit in Clojure op moest lossen.
...

Ik dacht gisteren echt letterlijk: Hoe de f*ck gaat Dricus dit in Clojure functioneel oplossen? Want ik zie het niet.

[Lisper]

armageddon_2k1 schreef op zondag 19 december 2021 @ 15:17:
[...]


Ik dacht gisteren echt letterlijk: Hoe de f*ck gaat Dricus dit in Clojure functioneel oplossen? Want ik zie het niet.

Waarschijnlijk zou het met zippers kunnen, dat is een functionele manier om aanpassingen binnen geneste structuren te doen. Clojure heeft een ingebouwde library ervoor, helaas heb ik nog geen tijd gehad om het echt te proberen.

[Dricus]

armageddon_2k1 schreef op zondag 19 december 2021 @ 15:17:
Ik dacht gisteren echt letterlijk: Hoe de f*ck gaat Dricus dit in Clojure functioneel oplossen? Want ik zie het niet.

Haha . Ik had je graag verrast, maar het zat er niet in. Nu ik het in Kotlin werkend heb, begin ik zo langzamerhand wel een idee te krijgen. Je hebt sowieso een immutable tree nodig, met de operaties find-first-leaf-to-the-left-of(node), find-first-leaf-to-the-right-of(node) en replace/update functionaliteit om nodes te wijzigen. Wellicht nog wat meer, maar dat kan ik nu even niet overzien.

Misschien ga ik nog een poging wagen...

[armageddon_2k1]

Dricus schreef op zondag 19 december 2021 @ 15:27:
[...]

Haha . Ik had je graag verrast, maar het zat er niet in. Nu ik het in Kotlin werkend heb, begin ik zo langzamerhand wel een idee te krijgen. Je hebt sowieso een immutable tree nodig, met de operaties find-first-leaf-to-the-left-of(node), find-first-leaf-to-the-right-of(node) en replace/update functionaliteit om nodes te wijzigen. Wellicht nog wat meer, maar dat kan ik nu even niet overzien.

Misschien ga ik nog een poging wagen...

En wat nou als je een lijst met nodes en een lijst met edges bijhoudt? Ik moet zeggen dat trees mij af en toe in immutable talen (of in Rust!) me het heel moeilijk maakte, maar een pair met twee lijsten (nodes, en edges) maakte het leven makkelijk. Stuk makkelijker itereren onder andere.

[DataGhost]

Omdat er vandaag nog zoveel met dag 18 gedaan wordt en de Up1 van gisteren toch niet helemaal legaal bleek, toch nog maar een testset, met een aanpassing aan de opgave omdat het anders lastig is trage code te "bestraffen":

If any pair is nested inside four sixteen pairs, the leftmost such pair explodes.

Verder zijn alle inputs wel al geldige snailcodes (met deze aanpassing inachtnemend). Dag 18 Up 2 en antwoorden. Bij mij duurt deze 14 en 6 seconden.
Eit: heftig, het wordt 3 resp. 5 seconden met een andere runtime (pypy3 ipv python3), dus daarom ook Dag 18 Up 3 die daarmee in 15 resp. 7 seconden klaar is.

[ Voor 25% gewijzigd door DataGhost op 19-12-2021 15:42 ]

[Dricus]

armageddon_2k1 schreef op zondag 19 december 2021 @ 15:30:
[...]


En wat nou als je een lijst met nodes en een lijst met edges bijhoudt? Ik moet zeggen dat trees mij af en toe in immutable talen (of in Rust!) me het heel moeilijk maakte, maar een pair met twee lijsten (nodes, en edges) maakte het leven makkelijk. Stuk makkelijker itereren onder andere.

Hmm, dat zie ik in Clojure ook nog niet helemaal voor me, moet ik zeggen. Maar de zippers die @Lisper noemt zien er interessant uit! Zit wel een aardige leercurve aan vast, zo te zien.

[armageddon_2k1]

Dag 19 in Kotlin met fucking quaternions.

Nondeju....wat een werk.

[iThinkSo]

Vandaag dag 18 en 19 afgemaakt (gisteren geen tijd gehad):

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

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

[iThinkSo]

Dricus schreef op zondag 19 december 2021 @ 15:27:
[...]

Haha . Ik had je graag verrast, maar het zat er niet in. Nu ik het in Kotlin werkend heb, begin ik zo langzamerhand wel een idee te krijgen. Je hebt sowieso een immutable tree nodig, met de operaties find-first-leaf-to-the-left-of(node), find-first-leaf-to-the-right-of(node) en replace/update functionaliteit om nodes te wijzigen. Wellicht nog wat meer, maar dat kan ik nu even niet overzien.

Misschien ga ik nog een poging wagen...

spoiler:

Wat ik gedaan heb is een in-order traverse over de tree. Als je je huidige node tegenkomt, is de eerste leaf daarna die niet een descendent is van je huidige node je target.

[armageddon_2k1]

Dricus schreef op zondag 19 december 2021 @ 15:36:
[...]

Hmm, dat zie ik in Clojure ook nog niet helemaal voor me, moet ik zeggen. Maar de zippers die @Lisper noemt zien er interessant uit! Zit wel een aardige leercurve aan vast, zo te zien.

Gewoon wachten tot uncle Bob z’n Clojure oplossing heeft toch? Kijken of die ouwe boomer dat voor elkaar krijgt

[Soultaker]

Dag 19 in Python. Nogal traag momenteel (~40 seconden mét Pypy), maar ik denk dat er nog wel een paar trucs te verzinnen zijn om het sneller te maken.

Overigens heb ik geen quaternions of externe libraries hoeven gebruiken. De benodigde lineaire algebra is eenvoudig genoeg om het zelf uit te kunnen schrijven. Waarschijnlijk is het wel een stuk sneller om een library als numpy te gebruiken.

[Varienaja]

Dag 19 in Java Ik had het vanmorgen al redelijk op tijd klaar. Nu net nog even ingelezen hoe dat zit met de 24 oriëntaties, en dat ingebouwd. Nu heb ik resultaat in 15 seconden in plaats van de 4 minuten van vanmorgen.

[Daos]

Vandaag kostte mij tot nu toe verreweg het meeste tijd. Ik ben er de hele middag zoet mee geweest. Alleen al begrijpen hoe die oriëntaties werken heeft mij een paar uur gekost.

spoiler:

Ik heb ze uiteindelijk maar allemaal uitgeschreven. Ik kon niet iets moois bedenken om ze te genereren.

https://github.com/gjscho...b/master/Day19/Program.cs

[P_Tingen]

Zijn er ook mensen die de AoC opgaven oplossen op onconventionele manieren? Een oud collega van mij heeft een paar dagen opgelost in qbasic maar misschien zijn er ook mensen die het in een batch file oplossen, in Excel of in Outlook VBA. Ik ben wel nieuwsgierig.

[Cranzai]

Beide puzzels van dit weekend beide nog niet opgelost. Die van gisteren wel aan begonnen maar nog niet afgerond (pittig opdrachtje)

Nog geen studie gemaakt van die van vandaag, maar dat komt door een uitgebreide studie van wat anders gisteravond

Wil ze hoe dan ook nog wel op gaan lossen, lijken mij heel leerzame opdrachten. Juist doordat ik niet echt een idee had wat te doen.
Misschien tussen kerst en oud en nieuw sowieso wat van de eerdere dagen refactoren nu ik weer wat beter in python zit. Een enkele opdracht omschrijven naar C lijkt me ook nog wel lachen.

[Soultaker]

P_Tingen schreef op zondag 19 december 2021 @ 20:00:
Zijn er ook mensen die de AoC opgaven oplossen op onconventionele manieren?

Heb je m'n Brainfuck oplossing gezien?

[armageddon_2k1]

Varienaja schreef op zondag 19 december 2021 @ 18:43:
Dag 19 in Java Ik had het vanmorgen al redelijk op tijd klaar. Nu net nog even ingelezen hoe dat zit met de 24 oriëntaties, en dat ingebouwd. Nu heb ik resultaat in 15 seconden in plaats van de 4 minuten van vanmorgen.

Huh? Ik zit op 450ms in Kotlin. En die compileert dus ook naar de JVM

[Diderikdm]

Alright ga ook eens een poging wagen.. Ben benieuwd of het er vandaag nog van komt zo de reacties te lezen

[armageddon_2k1]

Soultaker schreef op zondag 19 december 2021 @ 18:27:
Dag 19 in Python. Nogal traag momenteel (~40 seconden mét Pypy), maar ik denk dat er nog wel een paar trucs te verzinnen zijn om het sneller te maken.

Overigens heb ik geen quaternions of externe libraries hoeven gebruiken. De benodigde lineaire algebra is eenvoudig genoeg om het zelf uit te kunnen schrijven. Waarschijnlijk is het wel een stuk sneller om een library als numpy te gebruiken.

Tja, m’n quaternion waren ook niet echt nodig. Maar m’n hersenen werkten gewoon niet mee. En nu hoefde ik alleen maar te vermenigvuldigen en heb ik weer een mooie class voor m’n common library

Ik heb nota bene rotatie matrices tot in den treure uitgeschreven tijdens m’n studie. Maar dat is ook alweer 12 jaar geleden….

[Dricus]

armageddon_2k1 schreef op zondag 19 december 2021 @ 18:20:
Gewoon wachten tot uncle Bob z’n Clojure oplossing heeft toch? Kijken of die ouwe boomer dat voor elkaar krijgt

Dag 18 in Clojure

Ik kon het niet laten, en heb het toch voor elkaar gekregen. Het is véél compacter geworden dan mijn Kotlin oplossing (die is met z'n 217 regels ook wel fors). Hij is ook een stuk trager (7 seconden versus 800 ms).

In deze oplossing representeer ik een getal niet als een tree, maar als een lijst, bestaande uit 2 typen elementen: een "groep marker" en een "regular number". Simpel voorbeeld:

Het getal [[1,[2,3]],4] ziet er als volgt uit (maar even als JSON voor de duidelijkheid om de structuur aan te geven:

JavaScript:

[
  {depth: 1, leaf: false},
  {depth: 2, leaf: false},
  {depth: 2, leaf: true, value: 1},
  {depth: 3, leaf: false},
  {depth: 3, leaf: true, value: 2},
  {depth: 3, leaf: true, value: 3},
  {depth: 1, leaf: true, value: 4}
]

Met deze structuur kan ik betrekkelijk makkelijk exploden en behoorlijk makkelijk splitten.

[armageddon_2k1]

Dricus schreef op zondag 19 december 2021 @ 20:27:
[...]

Dag 18 in Clojure

Ik kon het niet laten, en heb het toch voor elkaar gekregen. Het is véél compacter geworden dan mijn Kotlin oplossing (die is met z'n 217 regels ook wel fors). Hij is ook een stuk trager (7 seconden versus 800 ms).

In deze oplossing representeer ik een getal niet als een tree, maar als een lijst, bestaande uit 2 typen elementen: een "groep marker" en een "regular number". Simpel voorbeeld:

Het getal [[1,[2,3]],4] ziet er als volgt uit (maar even als JSON voor de duidelijkheid om de structuur aan te geven:

JavaScript:

[
  {depth: 1, leaf: false},
  {depth: 2, leaf: false},
  {depth: 2, leaf: true, value: 1},
  {depth: 3, leaf: false},
  {depth: 3, leaf: true, value: 2},
  {depth: 3, leaf: true, value: 3},
  {depth: 1, leaf: true, value: 4}
]

Met deze structuur kan ik betrekkelijk makkelijk exploden en behoorlijk makkelijk splitten.

Held. Jij kan er dus ook niet tegen als je er niet uitkomt. Ik had de handdoek in de ring gegooid na het lezen van de opdracht. Maarja, vanmiddag gedwee de handdoek maar weer uit de ring gevist.

Edit: jouw oplossing is elegant. Die ga ik wellicht ook ff in Kotlin proberen.

[ Voor 3% gewijzigd door armageddon_2k1 op 19-12-2021 20:32 ]

[Varienaja]

armageddon_2k1 schreef op zondag 19 december 2021 @ 20:25:Huh? Ik zit op 450ms in Kotlin. En die compileert dus ook naar de JVM

Oef. Dan is er dus nog heel veel ruimte voor verbetering!!

[Dricus]

armageddon_2k1 schreef op zondag 19 december 2021 @ 20:28:
Held. Jij kan er dus ook niet tegen als je er niet uitkomt. Ik had de handdoek in de ring gegooid na het lezen van de opdracht. Maarja, vanmiddag gedwee de handdoek maar weer uit de ring gevist.

Edit: jouw oplossing is elegant. Die ga ik wellicht ook ff in Kotlin proberen.

Haha, dankje . Ik denk dat hij in Kotlin ook een stuk sneller kan zijn, vanwege mutability.

[armageddon_2k1]

Varienaja schreef op zondag 19 december 2021 @ 20:32:
[...]
Oef. Dan is er dus nog heel veel ruimte voor verbetering!!

Hoogstwaarschijnlijk doe je ergens een onhandige collection actie.

[armageddon_2k1]

Dricus schreef op zondag 19 december 2021 @ 20:34:
[...]

Haha, dankje . Ik denk dat hij in Kotlin ook een stuk sneller kan zijn, vanwege mutability.

Heeft Clojure geen persistent collections? Die data delen bij mutaties, zoals Scala?

[Dricus]

armageddon_2k1 schreef op zondag 19 december 2021 @ 20:40:
Heeft Clojure geen persistent collections? Die data delen bij mutaties, zoals Scala?

Zeker wel. Maar die hebben wel een performance penalty (hoeft niet zo groot te zijn als hij nu bij mij is, overigens). Het is voor mij nog wel een uitdaging om daar goed op te optimaliseren. Dit komt doordat Clojure niet staticly typed is, en er meestal ook niet moeilijk over doet om impliciet conversies tussen verschillende collection types te doen.

[KabouterSuper]

P_Tingen schreef op zondag 19 december 2021 @ 20:00:
Zijn er ook mensen die de AoC opgaven oplossen op onconventionele manieren? Een oud collega van mij heeft een paar dagen opgelost in qbasic maar misschien zijn er ook mensen die het in een batch file oplossen, in Excel of in Outlook VBA. Ik ben wel nieuwsgierig.

Ik wil nog altijd een keer een poging wagen in pl-sql (oracle). Het programmeren lukt me wel, maar van het moeten inlezen van de data word ik heel verdrietig....daar is oracle niet goed in.

[P_Tingen]

Soultaker schreef op zondag 19 december 2021 @ 20:17:
[...]
Heb je m'n Brainfuck oplossing gezien?

Damn, hoe máák je dat, programmeer je dat eerst in een andere taal en doe je dan transpilen of maak je het gelijk in brainfuck?

KabouterSuper schreef op zondag 19 december 2021 @ 20:58:
[...]
Ik wil nog altijd een keer een poging wagen in pl-sql (oracle). Het programmeren lukt me wel, maar van het moeten inlezen van de data word ik heel verdrietig....daar is oracle niet goed in.

Ik heb zelf ooit ook wel iets met pl/sql gedaan in een grijs verleden. Zou moeten lukken denk ik.

[Devilfish]

Dag 19 in C#

Vanaf vanochtend bezig geweest en achteraf gezien had ik hem rond 12 uur klaar, maar ik was vergeten 0,0,0 aan m'n scanner lijst toe te voegen . Perfomance is redelijk, iets meer dan 3 seconden.

[Remcoder]

6 minuten voor mijn input...

Het werkt, het geeft een resultaat, ik ben er klaar mee voor vandaag. Ik optimaliseer het ooit nog wel een keer.

Members only:

Alleen zichtbaar voor ingelogde gebruikers. Inloggen

[DataGhost]

P_Tingen schreef op zondag 19 december 2021 @ 20:00:
Zijn er ook mensen die de AoC opgaven oplossen op onconventionele manieren? Een oud collega van mij heeft een paar dagen opgelost in qbasic maar misschien zijn er ook mensen die het in een batch file oplossen, in Excel of in Outlook VBA. Ik ben wel nieuwsgierig.

Vorig jaar heb ik na AoC dag 1 in APL gedaan (met als plan de rest van de dagen ook daarin op te lossen) maar dat was echt een hel om te bouwen. Dat lijkt me voor wiskundige dingen een prima taal maar het is toch een heftig andere manier van programmeren dus daar ben ik snel mee afgehaakt.

Dit jaar heb ik voor de gein dag 6 in Excel gedaan, dat was behoorlijk eenvoudig. Alle opgaven kunnen daar in principe in maar op een gegeven moment is het gewoon niet leuk meer om mee te werken.

[Lisper]

Dricus schreef op zondag 19 december 2021 @ 15:36:
[...]

Hmm, dat zie ik in Clojure ook nog niet helemaal voor me, moet ik zeggen. Maar de zippers die @Lisper noemt zien er interessant uit! Zit wel een aardige leercurve aan vast, zo te zien.

Zo ik had er eigenlijk geen zin in, maar de gedachte dat het met zippers zou moeten kunnen gaf me motivatie, uiteindelijk nog best leesbaar geworden:

Day 18 in Clojure, met zippers

Het voordeel van deze opgave was dat alle voorbeelden valide Clojure datastructuren zijn, die ik zo kon copy pasten in de unit tests.

Het zal niet heel performant zijn, nu deel 2 nog...

EDIT: het valt mee, brute force oplossing in 30 seconden.

[ Voor 4% gewijzigd door Lisper op 19-12-2021 22:00 ]

[Lisper]

Dag 19 lijkt me wel een leuke opdracht, maar daar ga ik vandaag niet meer aan beginnen.

De andere jaren haakte ik ook af rond deze tijd, de opdrachten kosten best wat tijd en ik had tegen kerst vaak andere verplichtingen. Nu met de lockdown ga ik het proberen door te zetten, maar zal een paar dagen achter gaan lopen.

[Soultaker]

P_Tingen schreef op zondag 19 december 2021 @ 21:03:
Damn, hoe máák je dat, programmeer je dat eerst in een andere taal en doe je dan transpilen of maak je het gelijk in brainfuck?

Ik schrijf de Brainfuck code 100% zelf; ik transpile niet, want dat doet de uitdaging teniet, en waarom zou je Brainfuck schrijven als je jezelf niet wil uitdagen?

Mijn aanpak is grofweg als volgt. Eerst probeer ik een algoritme te vinden dat simpel genoeg is om in Brainfuck te implementeren. Daarbij moet je goed nadenken over hoe je je data representeert. Brainfuck heeft een enkele tape met bytes. Daarmee kun je een lijst of een stack implementeren, en eventueel twee of drie lijsten als je wil, maar twee- of meer-dimensionale arrays zijn ingewikkeld, en complexe data structuren zoals hash tables kun je vergeten, net als floating point berekeningen, want die zijn praktisch niet te doen. Je moet je algoritme dus zo formuleren dat het alleen eenvoudige datastructuren zoals lijsten gebruikt.

Ook gebruik ik een traditionele Brainfuck interpreter waarbij elke cel waarden van 0 tot 255 kan opslaan, dus als je een groter getal als uitvoer wil representeren, moet je meerdere cellen gebruiken. Meestal representeer ik getallen in het decimale stelsel; dat is minder efficient, in theorie, maar heeft als voordeel dat je geen conversie hoeft te doen op het eind. Om van binair naar decimaal te converteren moet je kunnen delen door 10, en delingen zijn niet eenvoudig om te implementeren in Brainfuck.

Voor dag 10 begon ik met m'n gewone oplossing in Python, maar die is nog niet geschikt omdat 'ie de invoer regel voor regel verwerkt, wat niet eenvoudig is in Brainfuck. Dus heb ik 'm omgeschreven naar een simpelere versie die byte-voor-byte werkt. Voor deel 1 zie je dat ik slechts twee variabelen heb: answer1 (een integer van variable grootte) en stack (een lijst van kleine getallen).

Op dat moment probeer ik mezelf te overtuigen dat ik elk statement in Python ook in Brainfuck kan implementeren. Daarbij is nog steeds een vertaalslag nodig, bijvoorbeeld: regel 19 hier (answer1 += values[i]) kost ongeveer 40 regels in Brainfuck. Het is dus niet zo dat er een 1-op-1 vertaling mogelijk is, maar meer dat ik mezelf heb overtuigd dat ik elke regel op de een of andere manier kan vertalen naar Brainfuck.

Als je het zelf eens wil proberen zou ik je aanraden om met simpele problemen te beginnen. Bijvoorbeeld: schrijf een programma dat regels inleest, en de letters van elke regel omkeert ("foo", "bar", "baz" wordt "oof", "rab", "zab", b.v.). Of een programma dat twee decimale getallen van willekeurige grootte inleest en optelt (123 + 45678 = 45801). Of een programma dat priemgetallen print. Als je zulke basisproblemen kunt oplossen in Brainfuck dan kun je aan complexere problemen beginnen.

[Janoz]

Pfff, door alle dreigende lockdown perikelen van gisteren vooral met heel veel andere dingen bezig geweest dus vandaag maar even een inhaalslag gemaakt. Vanochtend dag 18 afgemaakt en zojuist dag 19 weten af te ronden. Ik had nog een bugje in mijn rotatie (zat denk ik een spiegeling tussen) waardoor ik de verkeerde 24 had, maar na een beetje prutsen toch nog snel iets in elkaar weten te hacken wat binnen een halve minuut de juiste antwoorden uitspuugt.

[Varienaja]

WTF? Dag 20. Voorbeeld goed. Echte input niet?

spoiler:

Mijn 'enhanced' image heeft heeft een witte rand, welke alleen maar dikker word, naarmate ik meer pixels uitreken. Dus mijn oneindig grote plaatje heeft oneindig witte pixels?? Heeft iedereen een hekje op positie 0 van z'n algoritme?

[Janoz]

Varienaja schreef op maandag 20 december 2021 @ 06:39:
WTF? Dag 20. Voorbeeld goed. Echte input niet?

spoiler:

Mijn 'enhanced' image heeft heeft een witte rand, welke alleen maar dikker word, naarmate ik meer pixels uitreken. Dus mijn oneindig grote plaatje heeft oneindig witte pixels?? Heeft iedereen een hekje op positie 0 van z'n algoritme?

spoiler:

klopt, je moet infinite serieus nemen. Kijk gelijk ook even wat er op positie 511 staat en bedenk waarom je 2x moet enhancen

Whoei.. Vandaag voor deel twee 966e

[MrHaas]

Varienaja schreef op maandag 20 december 2021 @ 06:39:
WTF? Dag 20. Voorbeeld goed. Echte input niet?

spoiler:

Mijn 'enhanced' image heeft heeft een witte rand, welke alleen maar dikker word, naarmate ik meer pixels uitreken. Dus mijn oneindig grote plaatje heeft oneindig witte pixels?? Heeft iedereen een hekje op positie 0 van z'n algoritme?

spoiler:

Yes, dat was de hele uitdaging in deze puzzel, wel weer evil dat de test input dat geintje niet had
Verder niet zo spannend, recht toe recht aan nieuwe lijst opbouwen en de default voor de pixels die buiten de input image liggen laten bepalen door de parity van de enhance.

https://github.com/arjand...ain/python/20/solution.py

[bakkerjangert]

Lol, op zich makkelijke opgave vandaag, ik denk wel dat veel mensen het eerst fout hebben en denken huh

spoiler:

Het oneidige veld flashed steeds van . --> # --> . --> # etc. Aangezien dit niet de test input zit zullen veel mensen eerst een fout antwoord geven, waaronder ik ook lol.

[Remcoder]

Remcoder schreef op zondag 19 december 2021 @ 21:15:
6 minuten voor mijn input...

Het werkt, het geeft een resultaat, ik ben er klaar mee voor vandaag. Ik optimaliseer het ooit nog wel een keer.


***members only***

Today I learned that Set iterators in Java traag zijn...

Set vervangen door List zorgt voor een flinke speed boost...

[tarlitz]

bakkerjangert schreef op maandag 20 december 2021 @ 07:45:
Lol, op zich makkelijke opgave vandaag, ik denk wel dat veel mensen het eerst fout hebben en denken huh

spoiler:

Het oneidige veld flashed steeds van . --> # --> . --> # etc. Aangezien dit niet de test input zit zullen veel mensen eerst een fout antwoord geven, waaronder ik ook lol.

Ja, hier ging ik ook keihard de mist in. De testdata werkte perfect, maar op de echte data ging het mis.

spoiler:

De truc is om eerst het veld zo groot te maken dat alle stappen er in passen. Net zoals bij de test input, die heeft ook overal puntjes om het veld heen. Met `numpy` / `ndimage.generic_filter` is hier trouwens een nette oplossing mee te maken van een paar regels code.

[DataGhost]

Ik zag dus vandaag voordat ik begon met coden alweer gebeuren dat deel 2 "moeilijk" zou zijn dus had alvast een "slim" algoritme gemaakt wat heel snel zou zijn, die 100% leunde op die ene aanname die voor de echte input dus fout bleek te zijn en daarna veel te lang bezig geweest met het te frankenstein-fixen, gewoon naief herschrijven was sneller geweest denk ik.

[EfBe]

Bleh al 5 keer het verkeerde antwoord. .

spoiler:

Heb toch echt mn convoluter zo aangepast dat hij de infinite space goed meeneemt (plaats een 1 pixel rand om de source image en ga dan alle pixels af in dat image zodat de image kan expanden in de rand waar nodig) maar kennelijk toch verkeerd...

[DataGhost]

EfBe schreef op maandag 20 december 2021 @ 10:49:
Bleh al 5 keer het verkeerde antwoord. .

spoiler:

Heb toch echt mn convoluter zo aangepast dat hij de infinite space goed meeneemt (plaats een 1 pixel rand om de source image en ga dan alle pixels af in dat image zodat de image kan expanden in de rand waar nodig) maar kennelijk toch verkeerd...

spoiler:

Ik zou nog eens goed lezen bij "For example, to determine the output"

[Janoz]

tarlitz schreef op maandag 20 december 2021 @ 10:31:
[...]


Ja, hier ging ik ook keihard de mist in. De testdata werkte perfect, maar op de echte data ging het mis.

spoiler:

De truc is om eerst het veld zo groot te maken dat alle stappen er in passen. Net zoals bij de test input, die heeft ook overal puntjes om het veld heen. Met `numpy` / `ndimage.generic_filter` is hier trouwens een nette oplossing mee te maken van een paar regels code.

spoiler:

Niet zo moeilijk doen. Gewoon een 'default' gebruiken voor out of bounds opvragingen. Die default kun je vervolgens na elke enhance aanpassen. Elk punt in de oneindige space word of 000000000 bij een '.' of 111111111 bij een '#'. die vraag je op in je mapping en je hebt je default voor de volgende enhance.

[EfBe]

DataGhost schreef op maandag 20 december 2021 @ 10:52:
[...]

spoiler:

Ik zou nog eens goed lezen bij "For example, to determine the output"

spoiler:

ik weet hoe convolution kernels werken Maar ik denk dat mn fout zit in de check dat wanneer ik in de infinite space zit ik altijd een 0 zie, maar dat is niet zo, want na 1 keer enhancen is de complete infinite space omgezet naar een set pixel en niet naar een 0 pixel.

[ydderf]

Hier een kleine achterstand. Zaterdag geen tijd gehad voor dag 18, en gezien de opdrachten maar gekozen om prio te geven aan dag 19 te geven.
Deze vond ik wel een mooie opdracht. Was wel ff nadenken hoe ik het zou oplossen, maar uiteindelijk vrij snel kunnen maken op een paar domme foutjes na die weer veel debug tijd kosten (vergeten om de laatste scanner vanuit de input toe te voegen).

spoiler:

En voor deel ff vergeten dat een afstand van -2000 langer is dan +1000

M.b.t. de 24 rotatie mogelijkheden:

spoiler:

Stel je een dobbelsteen voor op tafel. Hiervan zie je het vak met het getal 1, en het vak met getal twee ligt naar het noorden. Deze kun je draaien zodat je nog steeds de 1 ziet, alleen het vak met twee ligt naar het westen, zuiden of oosten. Dit zijn dus 4 rotaties.
Dit trukje moet je vervolgens herhalen voor alle vlakken.

Hopelijk vandaag nog ergens tijd voor dag 20. Deel 1 ziet er nog als te doen uit. Maar goed, dat heb ik wel eens vaker gedacht....

[ Voor 0% gewijzigd door ydderf op 20-12-2021 16:51 . Reden: url fix ]

[Creepy]

EfBe schreef op maandag 20 december 2021 @ 10:49:
Bleh al 5 keer het verkeerde antwoord. .

spoiler:

Heb toch echt mn convoluter zo aangepast dat hij de infinite space goed meeneemt (plaats een 1 pixel rand om de source image en ga dan alle pixels af in dat image zodat de image kan expanden in de rand waar nodig) maar kennelijk toch verkeerd...

Ik heb hetzelfde

spoiler:

En ook ik hou rekening met de rand omdat ik in de input zag dat 0 een '#' was, dus per stap wordt de image groter en de nieuwe pixels wisselen dus af tussen # en . met de input. Eens kijken wat er scheef gaat...

[DataGhost]

Ja ik wil het niet helemaal spoileren hoor maar weten jullie zeker dat

spoiler:

je rand dik genoeg is?

[bakkerjangert]

Voor wie nog moeite heeft met de rotaties van dag 19:

spoiler:

[KabouterSuper]

Hehe, eindelijk dag 18 en 19 ingehaald.

Dag 18 vond ik veel werk. Misschien heb ik het overdone, maar ik heb netjes een boomstructuur geimplementeerd met mooie methoden om voorgangers te vinden, een explode/split/addition te doen. Lang mee bezig geweest, maar wel in één keer het goede antwoord.

Dag 19 vond ik wel grappig. Geen flauw idee hoe anderen dit geprogrammeerd hebben.

spoiler:

Ik heb denk ik een onconventionele truc toegepast door een operator te maken die de boel translatie en rotatie-invariant maakt. Zo kon ik gemakkelijk per beacon terugvinden of er 12 dezelfde scanners waren (simpelweg de locaties na de operator vergelijken). Het gevolg was wel dat ik de beacons zelf niet nodig had om deel 1 op te lossen en de rotaties met een flauwe truc kon doen.

Ben erg benieuwd wat de rest gedaan heeft bij dag 19.

[ Voor 3% gewijzigd door KabouterSuper op 20-12-2021 11:18 ]

[ydderf]

@KabouterSuper Je verklapt je spoiler door het ontbrekende / in de afsluit tag Is al gefixed zie ik

[ Voor 14% gewijzigd door ydderf op 20-12-2021 11:20 ]

[iThinkSo]

Heeft iemand al een image encoder voor dit probleem voorbij zien komen?

Voor de rest idd niet zo spannend als je de bovenstaande spoilers leest

spoiler:

Als je er niet uit komt, heeft het mij erg geholpen de 1e '.' van de test input door een '#' te vervangen, en de laatste '#' door een '.'. Het antwoord hier zou 24 moeten zijn.

[EfBe]

Creepy schreef op maandag 20 december 2021 @ 11:09:
[...]

Ik heb hetzelfde

spoiler:

En ook ik hou rekening met de rand omdat ik in de input zat dat 0 een '#' was, dus per stap wordt de image groter en de nieuwe pixels wisselen dus af tussen # en . met de input. Eens kijken wat er scheef gaat...

spoiler:

Ik had dus de fout dat ik altijd 0 returnde bij 'outofbound pixels' bij de pixel read. Dus (-1, -1) was altijd 0. Maar dat is niet zo, dat is alleen bij de start zo. De volgende stappen moet je het result van de vorige enhance gebruiken voor de out of bound pixels. wellicht heb jij hetzelfde

[Creepy]

EfBe schreef op maandag 20 december 2021 @ 11:36:
[...]

spoiler:

Ik had dus de fout dat ik altijd 0 returnde bij 'outofbound pixels' bij de pixel read. Dus (-1, -1) was altijd 0. Maar dat is niet zo, dat is alleen bij de start zo. De volgende stappen moet je het result van de vorige enhance gebruiken voor de out of bound pixels. wellicht heb jij hetzelfde

spoiler:

Nee, dat is het niet. Daar hou ik al rekening mee, er zal wel ergens nog een domme fout inzitten want ik zie dat de test image nu ook niet meer goed gaat.

[EfBe]

Day 20: https://github.com/FransB...src/AoC2021.Code/Day20.cs

spoiler:

ontzettende overdraw omdat ik bij de expand eerst alles init, maar geen zin in om dat te optimizen, hij is binnen de seconde klaar in puzzel 2, dus boeiend

[Remcoder]

Dag 20 is ook opgelost hier

Members only:

Alleen zichtbaar voor ingelogde gebruikers. Inloggen

spoiler:

Hij is alleen nog ietwat traag voor deel 2, mogelijk doordat ik string operaties gebruik om het de positie in de enhancement te bepalen. Dit zou waarschijnlijk ook moeten lukken via bit-shifting, maar nu geen zin om dat uit te werken. Dat komt later wel

[tarlitz]

Janoz schreef op maandag 20 december 2021 @ 10:55:
[...]

spoiler:

Niet zo moeilijk doen. Gewoon een 'default' gebruiken voor out of bounds opvragingen. Die default kun je vervolgens na elke enhance aanpassen. Elk punt in de oneindige space word of 000000000 bij een '.' of 111111111 bij een '#'. die vraag je op in je mapping en je hebt je default voor de volgende enhance.

spoiler:

Dat is inderdaad een efficiente work-around voor het probleem 👍 Ik had deze in eerste instantie ook gevonden. Ik vond het echter conceptueel eenvoudiger om te denken over een oneindig veld met `.` als default zoals in het voorbeeld.

[Janoz]

Daar begin je inderdaad ook mee

[Creepy]

En dag 20
https://github.com/CodeEn...er/aoc/aoc2021/Day20.java

spoiler:

Als je de image vergroot moet je natuurlijk wel netjes nieuwe de rand berekenen ipv direct de "infinite" pixel er in te zetten.....

[iThinkSo]

spoiler:

Uiteindelijk een recursieve oplossing geschreven. Niet super snel (30s) maar wel erg elegant, en houd impliciet rekening met de oneindige rand.

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

[KabouterSuper]

iThinkSo schreef op maandag 20 december 2021 @ 12:58:

spoiler:

Uiteindelijk een recursieve oplossing geschreven. Niet super snel (30s) maar wel erg elegant, en houd impliciet rekening met de oneindige rand.

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

spoiler:

Mijn oplossing van dag 20 doet er 45 seconden over, maar is ook redelijk elegant. Ik initialiseer mijn matrix elke stap met de default waarde (het oneindige punt die door de enhancer is gehaald). Daarna bereken ik de relevante punten. De snelheid is matig, maar ik ben allang blij dat ik snel een antwoord had.

[Diderikdm]

Python dag 20

Prima te doen puzzel vandaag! Hoop later nog tijd te hebben om 19 af te ronden

[zwippie]

Ik lig inmiddels een paar dagen achter omdat ik overnieuw ben begonnen in Nim ipv Elixir. Even uit mijn comfort zone, best leuk!

[bras]

Mijn dag 20 deel 1 oplossing werkt voor de testdata maar niet voor mijn eigen opgave. Ik heb alleen geen idee hoe te beginnen met debuggen. Enige tips qua debuggen of obvious fout in m'n code?

https://github.com/MBras/AOC2021/blob/main/20/part1.py

[bakkerjangert]

bras schreef op maandag 20 december 2021 @ 14:21:
Mijn dag 20 deel 1 oplossing werkt voor de testdata maar niet voor mijn eigen opgave. Ik heb alleen geen idee hoe te beginnen met debuggen. Enige tips qua debuggen of obvious fout in m'n code?

https://github.com/MBras/AOC2021/blob/main/20/part1.py

spoiler:

check eens wat drie x drie "." oplevert als resultaat.

[Creepy]

bras schreef op maandag 20 december 2021 @ 14:21:
Mijn dag 20 deel 1 oplossing werkt voor de testdata maar niet voor mijn eigen opgave. Ik heb alleen geen idee hoe te beginnen met debuggen. Enige tips qua debuggen of obvious fout in m'n code?

https://github.com/MBras/AOC2021/blob/main/20/part1.py

spoiler:

Check het eerste karakter van je input eens....

[Reynouts]

Wat een fijne dag na het harde werk van de afgelopen dagen!

Gisteren bezig geweest tot 2u 's nachts om day19 te solven. Had bijna de handdoek in de ring gegooid, maar kon het niet over mijn hart verkrijgen om de ster niet te hebben binnen 24u.

[Soultaker]

Wat gemeen, de testinvoer van dag 20. Ik ben wel blij dat ik zelf uitgevonden heb wat er mis ging.

Over de verschillende oplossingstechnieken:

spoiler:

Ik neem aan dat iedereen bedacht heeft dat je bij elke simulatiestap een rand van lege pixels om je bord moet toevoegen, omdat je weet dat elke stap de bounding box met maximaal 1 kan toenemen (omdat elke pixel alleen door z'n buren wordt beïnvloedt). Als je van te voren weet dat je N stappen gaat simuleren kun je ook gelijk in het begin een rand van N pixels toevoegen.

Die aanname gaat stuk als t[0] = '#' zoals in de testinvoer: je bounding box wordt dan oneindig na 1 stap. Er zijn drie manieren om het op te lossen.

1: De eenvoudigste is om een rand van 2N in plaats van N pixel in te voegen. Na N stappen kloppen de buitenste N pixels van je grid niet meer maar dat geeft niet; je neemt gewoon de binnenste (N + H + N) x (N + W + N) pixels in beschouwing. Dit werkt voor alle transitietabellen.

2: Een iets snellere oplossing is wat Janoz hierboven zegt (en ik ook gedaan had): een default waarde meegeven voor lookups buiten het bord. Als t[0] = '.' dan is de default altijd 0. Als t[0] = '#' en t[511] = '#' dan is de waarde de eerste keer 0 en daarna 1. En als t[0] = '#' and t[511] = '.' dan alterneert de waarde tussen 0 en 1 (zoals in de testinvoer).

3: De inverse regel bedenken, en alterneren tussen berekenen van de donkere punten en de lichte punten. Dit is de techniek die hier beschreven wordt (onder “Emulating B0 rules”). Dit is eigenlijk de meest elegante oplossing en in het algemeen ook het meest efficiënt, al zal het voor de testinvoer niet veel uitmaken.

[iThinkSo]

Ik zou voor vandaag wel eens de stats willen zien voor hoeveel mensen in 1 keer het goede antwoord hadden...

[Remcoder]

Soultaker schreef op maandag 20 december 2021 @ 15:23:
Wat gemeen, de testinvoer van dag 20. Ik ben wel blij dat ik zelf uitgevonden heb wat er mis ging.

Over de verschillende oplossingstechnieken:

spoiler:

Ik neem aan dat iedereen bedacht heeft dat je bij elke simulatiestap een rand van lege pixels om je bord moet toevoegen, omdat je weet dat elke stap de bounding box met maximaal 1 kan toenemen (omdat elke pixel alleen door z'n buren wordt beïnvloedt). Als je van te voren weet dat je N stappen gaat simuleren kun je ook gelijk in het begin een rand van N pixels toevoegen.

Die aanname gaat stuk als t[0] = '#' zoals in de testinvoer: je bounding box wordt dan oneindig na 1 stap. Er zijn drie manieren om het op te lossen.

1: De eenvoudigste is om een rand van 2N in plaats van N pixel in te voegen. Na N stappen kloppen de buitenste N pixels van je grid niet meer maar dat geeft niet; je neemt gewoon de binnenste (N + H + N) x (N + W + N) pixels in beschouwing. Dit werkt voor alle transitietabellen.

2: Een iets snellere oplossing is wat Janoz hierboven zegt (en ik ook gedaan had): een default waarde meegeven voor lookups buiten het bord. Als t[0] = '.' dan is de default altijd 0. Als t[0] = '#' en t[511] = '#' dan is de waarde de eerste keer 0 en daarna 1. En als t[0] = '#' and t[511] = '.' dan alterneert de waarde tussen 0 en 1 (zoals in de testinvoer).

3: De inverse regel bedenken, en alterneren tussen berekenen van de donkere punten en de lichte punten. Dit is de techniek die hier beschreven wordt (onder “Emulating B0 rules”). Dit is eigenlijk de meest elegante oplossing en in het algemeen ook het meest efficiënt, al zal het voor de testinvoer niet veel uitmaken.

spoiler:

Oplossing 2 is overigens geen correcte oplossing, die werkt niet op de voorbeeld input

Wat ik dus doe, is bekijken wat de waarde van de pixel op positie 0,0 en dat is dan de waarde van de pixels die buiten de rand van het grid liggen.

Daarmee werkt de code zowel voor de voorbeeld input, als de daadwerkelijke input.

[Varienaja]

iThinkSo schreef op maandag 20 december 2021 @ 15:25:
Ik zou voor vandaag wel eens de stats willen zien voor hoeveel mensen in 1 keer het goede antwoord hadden...

Ongeveer kan je dat hier zien: https://www.maurits.vdschee.nl/scatterplot/ Deel 2 schijnt dus niet echt moeilijk gevonden te worden. Dat was op dag 8 wel anders, blijkbaar.

[bras]

bakkerjangert schreef op maandag 20 december 2021 @ 14:32:
[...]

spoiler:

check eens wat drie x drie punten oplevert als resultaat.

spoiler:

de blokjes van drie x drie zien er telkens goed uit

Creepy schreef op maandag 20 december 2021 @ 14:45:
[...]

spoiler:

Check het eerste karakter van je input eens....

spoiler:

ik heb m'n officiele input gechecked (input.1 regel 1) en als ik naar mijn output kijk klopt dat met de input. Ik snap hem nu met een hint een paar posts verderop, thanks!

[ Voor 5% gewijzigd door bras op 20-12-2021 16:06 . Reden: snap het nu wel :D ]

[Soultaker]

Remcoder schreef op maandag 20 december 2021 @ 15:29:
Oplossing 2 is overigens geen correcte oplossing, die werkt niet op de voorbeeld input

Waarom niet?

spoiler:

Merk op dat de waarde van de default-pixel afhangt van de transitietabel he. Om mezelf te herhalen:

Als t[0] = '.' dan is de default altijd 0. Als t[0] = '#' en t[511] = '#' dan is de waarde de eerste keer 0 en daarna 1. En als t[0] = '#' and t[511] = '.' dan alterneert de waarde tussen 0 en 1 (zoals in de testinvoer).

[NickThissen]

Dag 20:

spoiler:

Volgens mij heb ik het niet helemaal goed gedaan, maar uiteindelijk wel het goeie antwoord

Ik hou volgens mij niet helemaal correct rekening met de infinite grid. Wat ik heb gedaan is simpelweg de input matrix in een veel grotere nul matrix stoppen (100 rijen en kolommen extra en beide kanten). De rand van de output klopt daarna geen kant van, maar als ik vervolgens gewoon alleen het stuk binnen rij/kolom 200 - 500 tel dan is het gewoon goed

[DataGhost]

Soultaker schreef op maandag 20 december 2021 @ 15:47:
[...]

Waarom niet?

spoiler:

Merk op dat de waarde van de default-pixel afhangt van de transitietabel he. Om mezelf te herhalen:

Als t[0] = '.' dan is de default altijd 0. Als t[0] = '#' en t[511] = '#' dan is de waarde de eerste keer 0 en daarna 1. En als t[0] = '#' and t[511] = '.' dan alterneert de waarde tussen 0 en 1 (zoals in de testinvoer).

Nou,

spoiler:

als t[0] ='#' en t[511] = '#' kan het antwoord niet als een integer gedefinieerd worden, dus die situatie kan niet voorkomen.

Relevantie met de voorbeeldinput zie ik niet direct verder, maar de case die je beschrijft klopt niet helemaal dus.

[ Voor 8% gewijzigd door DataGhost op 20-12-2021 15:52 ]

[RogierJames]

NickThissen schreef op maandag 20 december 2021 @ 15:51:
Dag 20:

spoiler:

Volgens mij heb ik het niet helemaal goed gedaan, maar uiteindelijk wel het goeie antwoord

Ik hou volgens mij niet helemaal correct rekening met de infinite grid. Wat ik heb gedaan is simpelweg de input matrix in een veel grotere nul matrix stoppen (100 rijen en kolommen extra en beide kanten). De rand van de output klopt daarna geen kant van, maar als ik vervolgens gewoon alleen het stuk binnen rij/kolom 200 - 500 tel dan is het gewoon goed

[Afbeelding]

spoiler:

Aan de rand gaat het waarschijnlijk niet goed. Hoe update je de cellen aan de rand? Cell (0,0) moet ook naar de 9 cellen om zich heen kijken en niet alleen naar een subset ervan.

[NickThissen]

RogierJames schreef op maandag 20 december 2021 @ 16:04:
[...]

spoiler:

Aan de rand gaat het waarschijnlijk niet goed. Hoe update je de cellen aan de rand? Cell (0,0) moet ook naar de 9 cellen om zich heen kijken en niet alleen naar een subset ervan.

spoiler:

Als het goed is pak ik een 0 ("dark") voor de cellen buiten de grid, maar ik heb de code ff niet meer bij de hand.

[Soultaker]

DataGhost schreef op maandag 20 december 2021 @ 15:51:
Nou,

spoiler:

als t[0] ='#' en t[511] = '#' kan het antwoord niet als een integer gedefinieerd worden, dus die situatie kan niet voorkomen.

Relevantie met de voorbeeldinput zie ik niet direct verder, maar de case die je beschrijft klopt niet helemaal dus.

Het punt is dat er drie relevante scenarios zijn, waarvan de eerste op de voorbeeldinvoer van toepassing is, de tweede op de testinvoer, en de derde hier niet voorkomt (en om de reden die je aangeeft niet kán voorkomen omdat het antwoord dan ongedefinieerd zou zijn), maar voor de volledigheid wilde ik 'm ook noemen.

Volgens mij klopt m'n uitleg precies voor elk van de drie situaties. Doe er mee wat je wil.

[ydderf]

Vandaag eerst ff bezig geweest omdat ik de testinput niet goed had gekopieerd. Daarna was de testinput wat makkelijker / vergevingsgezinde dan de echte input....
Hierna gevonden waardoor het mis ging met mijn echte input en mijn testinput aangepast om het principe te testen. Echter voor deel twee vergeten om mijn testinput weer goed te zetten, dus daar klopten de test uitkomsten nooit

spoiler:

ik heb mijn begin image veel te groot gemaakt. Na elke beeldverwerking haal ik er vervolgens de buitenste rand af zodat ik uiteindelijk over blijf met de echte image.
Voor de test input was de oneindige afbeelding niet relevant, maar voor de echte input wel

[Soultaker]

NickThissen schreef op maandag 20 december 2021 @ 15:51:
Dag 20:
Volgens mij heb ik het niet helemaal goed gedaan, maar uiteindelijk wel het goeie antwoord

spoiler:

Hier is eigenlijk niets mis mee. Dat is oplossing 1 hier. Het is eenvoudig te bewijzen dat dat werkt; na 50 stappen klopt de buitenste rand van 50 pixels niet, maar als je die weggooit klopt de rest wel.

[HennieGL]

Deze opgave wordt heel eenvoudig als je...

spoiler:

een veld gebruikt dat in het kader van deze opgave oneindig is. Ik gebruik f[700,700]. Lees de eerste regel in een array genaamd bits, en zet dan de input midden in f (dus van 300..400). Veld f2 is ook 700x700 en bevat tussenresultaten.

De code wordt dan niet meer dan:

for(r=1 to 50) // 50 rounds
{ for(x=5 to 695)
for(y=5 to 695)
f2[x,y] = bits[ 256*f[x-1,y-1] + ... + 1*f[x+1,y+1] ];
f=f2;
}
return sum( f[180,180]...f[520,520] );


Op deze manier hoef je je op geen enkele wijze na te denken of je "buiten het array kijkt" of wat er met je infinity waardes gebeurt. Alle controles op randgevallen vervallen. Er ontstaat wel chaos aan de randen van je universum maar dat zal in 50 stappen jouw data in het centrum niet bereiken dus die kun je negeren.

[armageddon_2k1]

Pfff Ben gaar na een dag werken. Ik krijg hem vandaag niet af, ook al is ie redelijk simpel.

[Creepy]

Remcoder schreef op maandag 20 december 2021 @ 15:29:
[...]

spoiler:

Oplossing 2 is overigens geen correcte oplossing, die werkt niet op de voorbeeld input
.

Ik weet niet hoe je de uitleg van oplossing 2 interpreteert, maar dat is ook hoe ik het doe, en dat werkt ook prima met de voobeeld input.

spoiler:

Dat is overigens niet hardcoded op de manier dat het er staat. De infinite pixels zijn bij de start altijd leeg. Indien het eerste karakter een pixel is dan volgt dus dat de volgende ronde er 511 uit komt en anders 0. Die waarde hou je bij voor de volgende ronde en afhankelijk of de pixel wel of niet gezet is pak je respectievelijk de pixel op 511 of 0, en dat geeft het effect zoals beschreven.

infinitePixel = infinitePixel ? enhancementAlgo[511] : enhancementAlgo[0];

[ Voor 5% gewijzigd door Creepy op 20-12-2021 17:15 ]

[Soultaker]

DataGhost schreef op zondag 19 december 2021 @ 15:31:
Verder zijn alle inputs wel al geldige snailcodes (met deze aanpassing inachtnemend). Dag 18 Up 2 en antwoorden. Bij mij duurt deze 14 en 6 seconden.
Eit: heftig, het wordt 3 resp. 5 seconden met een andere runtime (pypy3 ipv python3), dus daarom ook Dag 18 Up 3 die daarmee in 15 resp. 7 seconden klaar is.

Leuke uitdaging. Ik heb m'n implementatie helemaal moeten herschrijven (18.py) maar hij draait nu in ~600 ms (up 2) en ~1700 ms (up 3) met PyPy.

Ik vraag me af of het nog sneller kan. Ik ben er niet helemaal zeker van of DoSplits() O(N) is of niet; misschien valt daar nog wat te verbeteren.

[Varienaja]

Bij oneindige grids werk ik altijd een Map<Point,Value>. Dan heb je nooit zorgen over gepre-alloceerde arrays die ineens te klein blijken. De Values die er niet zijn kan je weglaten. En het is snel zat. Dag 20 in Java.

[ Voor 6% gewijzigd door Varienaja op 20-12-2021 19:26 ]

[Remcoder]

Soultaker schreef op maandag 20 december 2021 @ 15:47:
[...]

Waarom niet?

spoiler:

Merk op dat de waarde van de default-pixel afhangt van de transitietabel he. Om mezelf te herhalen:

Als t[0] = '.' dan is de default altijd 0. Als t[0] = '#' en t[511] = '#' dan is de waarde de eerste keer 0 en daarna 1. En als t[0] = '#' and t[511] = '.' dan alterneert de waarde tussen 0 en 1 (zoals in de testinvoer).

Ah, ik had verkeerd gelezen.

Ik had een vergelijkbare oplossing geïmplementeerd maar net iets anders, die van mij pakte elke keer óf element 0 óf element 511, en die werkte dus niet voor de test input, maar wel voor de echte input.

Daar baseerde ik die opmerking op

[Soultaker]

KabouterSuper schreef op maandag 20 december 2021 @ 11:17:
Dag 19 vond ik wel grappig. Geen flauw idee hoe anderen dit geprogrammeerd hebben.

spoiler:

Ik heb denk ik een onconventionele truc toegepast door een operator te maken die de boel translatie en rotatie-invariant maakt. Zo kon ik gemakkelijk per beacon terugvinden of er 12 dezelfde scanners waren (simpelweg de locaties na de operator vergelijken). Het gevolg was wel dat ik de beacons zelf niet nodig had om deel 1 op te lossen en de rotaties met een flauwe truc kon doen.

Kun je hier meer over vertellen?

spoiler:

Ik dacht er zelf ook aan om de scanner data te vertalen naar een "canonieke" representatie, maar het probleem is dat paren van scanners maar in een subset van de data overlappen, en ik zag dus geen manier om dat handig op te lossen.

Zelf heb ik het uiteindelijk maar gebruteforcet: om twee datasets te vergeleken doe ik alle 24 rotaties op de tweede dataset, en vervolgens probeer ik als translatie alle afstanden tussen een punt in de eerste dataset en een punt in de tweede dataset. Vrij inefficient natuurlijk.

[KabouterSuper]

Soultaker schreef op maandag 20 december 2021 @ 20:12:
[...]

Kun je hier meer over vertellen?

spoiler:

Ik dacht er zelf ook aan om de scanner data te vertalen naar een "canonieke" representatie, maar het probleem is dat paren van scanners maar in een subset van de data overlappen, en ik zag dus geen manier om dat handig op te lossen.

Zelf heb ik het uiteindelijk maar gebruteforcet: om twee datasets te vergeleken doe ik alle 24 rotaties op de tweede dataset, en vervolgens probeer ik als translatie alle afstanden tussen een punt in de eerste dataset en een punt in de tweede dataset. Vrij inefficient natuurlijk.

Tuurlijk.

spoiler:

Ik bereken per scanner voor elk beacon de relatieve coordinaten tot de andere beacons. Van deze coordinaten neem ik de absolute waarde per as en sla deze gesorteerd op (dus [-10,4,-15] wordt [4,10,25]). Voor 25 beacons heb je 25 sets van 24 coordinaten. Het mooie is dat deze onafhankelijk zijn van de scanner lokatie en rotatie. Als je deze sets dus matcht met andere scanner sets, dan krijg je voor sommige andere scanner sets een overlap van 12 elementen. Als je dan één van deze overlappende elementen pakt, kan je de lokatie en rotatie van de ene scanner gemakkelijk terugrekenen naar die van de andere scanner. En dat probeer je paarsgewijs totdat je alle scanners teruggerekend hebt naar scanner 0.

[armageddon_2k1]

Dag 20 in Kotlin

Goed leermomentje met mutable en immutable collections. Het snelheidsverschil is ongeveer een factor 900.

[Soultaker]

KabouterSuper schreef op maandag 20 december 2021 @ 20:44:

spoiler:

Ik bereken per scanner voor elk beacon de relatieve coordinaten tot de andere beacons. Van deze coordinaten neem ik de absolute waarde per as en sla deze gesorteerd op (dus [-10,4,-15] wordt [4,10,25]). Voor 25 beacons heb je 25 sets van 24 coordinaten. Het mooie is dat deze onafhankelijk zijn van de scanner lokatie en rotatie. Als je deze sets dus matcht met andere scanner sets, dan krijg je voor sommige andere scanner sets een overlap van 12 elementen.

Slim bedacht!

spoiler:

Om twee scanners te vergelijken moet je dan nog steeds 25 × 25 paren van sets vergelijken, toch? Niet per se heel schaalbaar, maar wel een interessante alternatieve aanpak.

Ook is er een risico op false positives omdat beacons kunnen verschillen in relatieve positie (b.v. {<1,0,0>, <-1,0,0>} mapt niet op <{1,0,0}, {0,1,0}> maar na jouw codering zijn ze hetzelfde) maar ik denk dat de invoer willekeurig gegenereerd is en het dus niet uitmaakt.

Trouwens, je bedoelt een overlap van 11 elementen neem ik aan? Aangezien je de beacon zelf niet meetelt.

[DataGhost]

KabouterSuper schreef op maandag 20 december 2021 @ 20:44:
[...]

Tuurlijk.

spoiler:

Ik bereken per scanner voor elk beacon de relatieve coordinaten tot de andere beacons. Van deze coordinaten neem ik de absolute waarde per as en sla deze gesorteerd op (dus [-10,4,-15] wordt [4,10,25]). Voor 25 beacons heb je 25 sets van 24 coordinaten. Het mooie is dat deze onafhankelijk zijn van de scanner lokatie en rotatie. Als je deze sets dus matcht met andere scanner sets, dan krijg je voor sommige andere scanner sets een overlap van 12 elementen. Als je dan één van deze overlappende elementen pakt, kan je de lokatie en rotatie van de ene scanner gemakkelijk terugrekenen naar die van de andere scanner. En dat probeer je paarsgewijs totdat je alle scanners teruggerekend hebt naar scanner 0.

Je gooit volgens mij informatie weg, kan je op deze manier niet meerdere beacons op verschillende locaties krijgen die met jouw vertaling "dezelfde uitkomst" krijgen, waardoor je bijv. 6 verschillende beacons uit de eerste scanner kan mappen op 1 beacon van de tweede, die je dan zesmaal meetelt? Het zal bij random inputs op een grote grid wel goed gaan maar ik denk, als ik het goed begrijp (en ik kan het best fout hebben) dat er inputs te maken zijn die een verkeerd antwoord opleveren.

[P_Tingen]

Nou, ik geef het op, wat een k*t opgave. Ook met de tips hier niks nakko nada. Ik haat dit soort opgaven, wel testcases meegeven maar dan een of ander sneaky iets er in stoppen. Bah, kijk morgen nog wel eens

[bakkerjangert]

hmmm, nog een gedachte over dag 19, want mijn Python code duurt veeeels te lang (30 minuten ofzo).

spoiler:

kun je niet iets met de manhatan distances tussen de beacons? als beacons overlappen moet die per definitie gelijk zijn, dus als er minimaal 12 moeten overlappen moeter er minimaal 11 + 10 + .... + 2 + 1 = 66 distances matchen tussen twee scanners. Gezien de grote van het scanner bereik lijkt me niet dat er veel dezelfde lengtes tussen zitten. van het weekend misschien maar eens verder proberen uit te vogelen.

-- Edit -- Door enkel al de scanners te skippen die niet aan bovenstaande voldoen gaat mijn code van 30 minuten naar 3 minuten. De aanpakt lijkt dus te werken. Dit is voorlopig voldoende nu, geen zin om mijn hele code opnieuw te schrijven gebaseerd op manhattan distances.

[ Voor 18% gewijzigd door bakkerjangert op 20-12-2021 22:11 ]

[KabouterSuper]

bakkerjangert schreef op maandag 20 december 2021 @ 21:45:
hmmm, nog een gedachte over dag 19, want mijn Python code duurt veeeels te lang (30 minuten ofzo).

spoiler:

kun je niet iets met de manhatan distances tussen de beacons? als beacons overlappen moet die per definitie gelijk zijn, dus als er minimaal 12 moeten overlappen moeter er minimaal 11 + 10 + .... + 2 + 1 = 66 distances matchen tussen twee scanners. Gezien de grote van het scanner bereik lijkt me niet dat er veel dezelfde lengtes tussen zitten. van het weekend misschien maar eens verder proberen uit te vogelen.

Da's ongeveer wat ik heb gedaan, zie mijn post hier vlak boven.

[Diderikdm]

Python dag 19

Nou dat was me een bevalling..
Heb heel lang vast gezeten omdat ik

spoiler:

double linked lists en referenties binnen een dictcall binnen deze lists wilde bewaren. Needless to say, veel te complex en niet overzichtelijk, bleek ook niet nodig

Na een refactor van onderstaand loopt die nu in 15 seconden voor part 1 & 2. Uiteindelijk erg tevreden mee

spoiler:

De looptijd was eerst richting 15 minuten omdat ik de grid met bekende punten elke keer als die werd uitgebreid opnieuw de afstanden + xyz-offshift opnieuw berekende voor alle punten, en vervolgens voor alle nog te vinden scanners al deze punter weer langsging waardoor die steeds langzamer werd.. maar dat was helemaal niet nodig

[ydderf]

P_Tingen schreef op maandag 20 december 2021 @ 21:30:
Nou, ik geef het op, wat een k*t opgave. Ook met de tips hier niks nakko nada. Ik haat dit soort opgaven, wel testcases meegeven maar dan een of ander sneaky iets er in stoppen. Bah, kijk morgen nog wel eens

Als ik nog tips mag geven:

spoiler:

gebruik de eerste regel van de testinput maar voeg zelf een image toe van 3x3 met alleen zwarte pixels. Beredeneer wat de uitkomst zou moeten zijn.
Daarna hetzelfde maar dan met de eerste regel van jou opdracht.

Extra tip

spoiler:

Doe nogmaals de bovenstaande test, maar dan met een image van 5x5 zwarte pixels.

spoiler:

De uitkomst zou identiek moeten zijn bij beide testen, want de afbeelding is oneindig groot

[KabouterSuper]

Soultaker schreef op maandag 20 december 2021 @ 20:58:
[...]

Slim bedacht!

spoiler:

Om twee scanners te vergelijken moet je dan nog steeds 25 × 25 paren van sets vergelijken, toch? Niet per se heel schaalbaar, maar wel een interessante alternatieve aanpak.

Ook is er een risico op false positives omdat beacons kunnen verschillen in relatieve positie (b.v. {<1,0,0>, <-1,0,0>} mapt niet op <{1,0,0}, {0,1,0}> maar na jouw codering zijn ze hetzelfde) maar ik denk dat de invoer willekeurig gegenereerd is en het dus niet uitmaakt.

Trouwens, je bedoelt een overlap van 11 elementen neem ik aan? Aangezien je de beacon zelf niet meetelt.

Scherp, overlap van 11.

De false posities kan je er gemakkelijk uithalen omdat je kunt kiezen uit 11 punten (of allemaal). Dubbele coordinaten zoals (1,2,2) zijn niet handig en nullen ook niet. Ik heb ervoor gekozen om te checken of de scannerposities en rotaties consistent waren.

Qua schaalbaarheid; ik stop met zoeken zodra ik iets gevonden heb, dus ik hoef vaak niet de hele oplossingsruimte door.

Maar als jullie het niet hetzelfde gedaan hebben, hoe hebben jullie het dan gedaan?

[ Voor 4% gewijzigd door KabouterSuper op 20-12-2021 22:17 ]

[HennieGL]

KabouterSuper schreef op maandag 20 december 2021 @ 22:15:
Maar als jullie het niet hetzelfde gedaan hebben, hoe hebben jullie het dan gedaan?

spoiler:

Voor elk paar scanners
{ voor elke rotatie van de tweede scanner
--{ voor elk beacon P van de eerste scanner
----{ voor elk beacon Q van de tweede scanner
------{ Bepaal dx, dy en dz tussen P en Q. Kijk hoeveel meer beacons je hiermee kunt matchen voor deze scanners/rotatie. >= 12 is bingo.
}}}}

De volgorde voor de scanners is nog iets slimmer want ik bouw mijn graaf van de scanners op vanuit scanner 0 zodat ik met iedere nieuwe match meteen de positie tot scanner 0 kan vastleggen.