Advent of Code 2023

[P_Tingen]

MadEgg schreef op maandag 18 december 2023 @ 22:55:
[...]
Je start ziet er zo uit:

code:

     |
     |
-----J
|
|
|
L--------7

Je start ziet er zo uit. De hoek begint met `-` en daarom zal je `J` niet geteld worden als doorgang van de rand omdat `iDir` niet op 1 gezet wordt. Het startpunt gaat niet goed bij de omzetting naar J7LF.

spoiler:

Als je kijkt of er op `pos(iCol, iRow - 1)` een gat zit weet je ook dat er een doorgang is. Dan hoef je de omzetting naar J7LF ook niet te doen, en het iDir gebeuren heb je dan ook niet nodig.

Dank! Ik had me dit zelf vannacht ook ineens gerealiseerd. Ik had mijn outline wel visueel gecontroleerd, maar op de verkeerde plek, want bovenin op de eerste regel. Maar dat is niet de goede want daar gelden negatieve coördinaten.

[Soultaker]

Dag 19:

spoiler:

Man man man, wat een spaghetti-code heb ik geschreven voor het parsen en simuleren. Eens zien of ik het nog een beetje netjes kan maken. Wel een leuk probleem op zich: conceptueel niet al te moeilijk, dus je bent als programmeur vooral je eigen vijand.

Voor deel 2:

spoiler:

Ik heb de methode geïmplementeerd waarbij je voor elke eigenschap een minimum- en maximumwaarde bijhoudt. Bij elke conditie splits je het pad dan (maximaal) in tweeën. Vereist wel zorgvuldig programmeren om off-by-1 fouten te voorkomen (< x betekent dat het nieuwe maximum x - 1 is, b.v.) en je moet zorgen dat je geen dubbel werk doet.

Op de officiële invoer draait het vlug genoeg, maar ik vraag me af wat de theoretische complexiteit is.

Ik heb ook overwogen om de ranges van [1..4000] van te voren op te splitsen en dan simpelweg de oplossing van deel 1 te hergebruiken, wat in theorie eenvoudiger is. Bijvoorbeeld, als de `x` eigenschap alleen met 1000, 2000, en 3000 vergeleken wordt in de regels, dan hoef je alleen objecten met b.v. x=500, x=1500, x=2500 en x=3500 te testen. Dit zou werken voor de testinvoer maar een snelle test wijst uit dat het voor de officiële invoer rond de 5 miljard mogelijkheden oplevert; mogelijk nog net wel te doen, maar niet in een seconde (in Python tenminste). En je hebt nog steeds alle irritante off-by-1 valkuilen.

MueR schreef op maandag 18 december 2023 @ 23:18:
Dat is natuurlijk ook wel een beetje het idee van AoC, van die "nutteloze" dingen weer even naar voren halen. Ik heb het ook met ##### opgelost, moest wel even googlen voordat ik op de juiste oplossing (en termen) kwam.

Iederen z'n ding; ik vind het persoonlijk juist leuk om het eerst zélf proberen op te lossen. Meestal kan dat ook best; je kunt vrij veel dingen zelf bedenken als je je daar op instelt.

Het hangt er een beetje vanaf wat je jezelf als doel stelt denk ik. Andere mensen willen oefenen met een nieuwe programmeertaal; dan is het algoritmische probleem oplossen misschien minder interessant.

Wat ik dan wel altijd leuk en leerzaam vind is om achteraf in dit topic te kijken hoe andere mensen het aangepakt hebben.

[MatHack]

Soultaker schreef op dinsdag 19 december 2023 @ 07:11:
Dag 19:

spoiler:

Man man man, wat een spaghetti-code heb ik geschreven voor het parsen en simuleren. Eens zien of ik het nog een beetje netjes kan maken. Wel een leuk probleem op zich: conceptueel niet al te moeilijk, dus je bent als programmeur vooral je eigen vijand.

Voor deel 2:
[spoiler]
Ik heb de methode geïmplementeerd waarbij je voor elke eigenschap een minimum- en maximumwaarde bijhoudt. Bij elke conditie splits je het pad dan (maximaal) in tweeën. Vereist wel zorgvuldig programmeren om off-by-1 fouten te voorkomen (< x betekent dat het nieuwe maximum x - 1 is, b.v.) en je moet zorgen dat je geen dubbel werk doet.

spoiler:

Veel deel 1 was de uitdaging meer het parsen dan de workflows juist volgen inderdaad.

Ik heb dezelfde soort oplossing gekozen voor deel 2 (ranges bijhouden en splitsen indien nodig) en de off-by-1 fout bij de comparison-splits heb ik correct voorkomen, maar er zit nog ergens anders een (off-by-1) bug... wordt nog leuk om te debuggen.
Vanwege het vermenigvuldigen voor de eindberekening gaan rekenfouten snel belachelijke aantallen opleveren. Ik weet in ieder geval dat die berekening juist is want zonder workflows krijg ik 4000^4 als antwoord.

[P_Tingen]

MadEgg schreef op maandag 18 december 2023 @ 22:55:
[...]
Je start ziet er zo uit:

code:

     |
     |
-----J
|
|
|
L--------7

Je start ziet er zo uit. De hoek begint met `-` en daarom zal je `J` niet geteld worden als doorgang van de rand omdat `iDir` niet op 1 gezet wordt. Het startpunt gaat niet goed bij de omzetting naar J7LF.

spoiler:

Als je kijkt of er op `pos(iCol, iRow - 1)` een gat zit weet je ook dat er een doorgang is. Dan hoef je de omzetting naar J7LF ook niet te doen, en het iDir gebeuren heb je dan ook niet nodig.

[FCA]

MatHack schreef op dinsdag 19 december 2023 @ 07:56:
[...]

spoiler:

Veel deel 1 was de uitdaging meer het parsen dan de workflows juist volgen inderdaad.

Ik heb dezelfde soort oplossing gekozen voor deel 2 (ranges bijhouden en splitsen indien nodig) en de off-by-1 fout bij de comparison-splits heb ik correct voorkomen, maar er zit nog ergens anders een (off-by-1) bug... wordt nog leuk om te debuggen.
Vanwege het vermenigvuldigen voor de eindberekening gaan rekenfouten snel belachelijke aantallen opleveren. Ik weet in ieder geval dat die berekening juist is want zonder workflows krijg ik 4000^4 als antwoord.

Ik ben er een beetje beduusd van hoe snel ik deel 2 foutloos had (talloze mogelijkheden voor off-by-1 fouten inderdaad). En deel 1 moest ik wel een paar keer lezen voordat ik doorhad wat er nou bedoeld werd.
Voor deel 1:

spoiler:

Ik kwam achter wat subtiliteiten van Python: voor een lambda functie, bijvoorbeeld
[code]
lambda x: x[key] < value
[/code]
wordt de waarde van de variabelen key en value genomen bij het uitvoeren van de functie, niet bij de definitie . Dat leverde flink wat issues op. Uiteindelijk de definitie van de uitvoer van de parsing van de workflow maar wat aangepast, expliciet de operator en de check er in gezet (was wel jammer, ik was te blij met mijn fallback lambda x: True ...
Verder enorme spaghetti code uiteraard.

Deel 2:

spoiler:

Eerste gedachte was gelijk range checking, depth-first recursief, en alles voor de zekerheid deepcopy-en (ben wat paranoia met pass by value/reference merk ik).

Ik denk dat ik voor de goede representatie heb gekozen voor de range: inclusief aan beide zijden. Dan zitten er weinig mogelijkheden voor off-by-1 fouten in, en kun je debug uitvoer makkelijk zelf checken (en natuurlijk goed letten op de strictheid van de ongelijkheden).

[MatHack]

Haha fout gevonden, ik had een verschil van 366.400.000.000 bij de testinvoer voor deel 2 en dat was...

spoiler:

uiteindelijk een off-by-2 fout, want ik had met kopiëren van de <-code naar de >-code wel juist de start/eind berekeningen omgedraaid, maar was een -1 naar een +1 vergeten te veranderen (regel 93 van mijn code).

https://github.com/realma...de.Y2023/Solvers/Day19.cs

[Soultaker]

Ik heb het uiteindelijk redelijk netjes gekregen: 19.py (runtime ~25 ms)

De truc die het meeste hielp was om

spoiler:

de regels te herschrijven naar uniforme instructies van de vorm label: (field, treshold, next_lt, next_ge) waarbij zo'n tuple effectief correspondeert met een regel code:

label: if (item[field] < threshold) goto next_lt; else goto next_ge;

Dat maakt het evalueren van regels heel simpel, en je hoeft geen onderscheid tussen operators meer te maken.

[ Voor 5% gewijzigd door Soultaker op 19-12-2023 08:43 ]

[Soultaker]

FCA schreef op dinsdag 19 december 2023 @ 08:11:
Ik ben er een beetje beduusd van hoe snel ik deel 2 foutloos had (talloze mogelijkheden voor off-by-1 fouten inderdaad).

De testinvoer is een beetje soft; er zitten hele if-statements in mijn code die nooit uitgevoerd worden (terwijl ze volgens mij technisch wel nodig zijn). Zal eens kijken of ik een moeilijkere testinvoer kan construeren.

Ik kwam achter wat subtiliteiten van Python: voor een lambda functie

Dit is hoe closures in de meeste talen werken. Het is belangrijk om te weten wanneer een nieuwe variabele wordt geïntroduceerd. Om deze verwarring te voorkomen heeft een taal als Java juist de regel dat je in closures alleen aan variabelen mag refereren die (effectively) final zijn.

Python is redelijk vervelend omdat alle variabelen functie-scope hebben. De enige manier om een nieuwe scope te introduceren is dus met een functiedefinitie. Bijvoorbeeld:

Python:

lambdas = [lambda: x for x in range(10)]

Dit doet niet wat je wil: lambdas[7]() returnt 9 bijvoorbeeld, de laatste waarde toegekend aan x. Maar dit werkt wel:

Python:

def Const(x):
  return lambda: x

lambdas = [Const(x) for x in range(10)]

En dat komt omdat de x-parameter van Const() een nieuwe variabele is elke keer dat 'ie wordt aangeroepen.

[MatHack]

Soultaker schreef op dinsdag 19 december 2023 @ 08:43:
Ik heb het uiteindelijk redelijk netjes gekregen: 19.py (runtime ~25 ms)

De truc die het meeste hielp was om

spoiler:

de regels te herschrijven naar uniforme instructies van de vorm label: (field, treshold, next_lt, next_ge) waarbij zo'n tuple effectief correspondeert met een regel code:

label: if (item[field] < threshold) goto next_lt; else goto next_ge;

Dat maakt het evalueren van regels heel simpel, en je hoeft geen onderscheid tussen operators meer te maken.

spoiler:

Hmm.. dat is een interessante observatie, dat scheelt inderdaad een lading if's verderop.

[CrossProd]

Oplossing voor deel 2 bedacht tijdens het brengen van mijn kinderen naar school. Helpt soms om even niet naar je code te staren.

Resultaat in ~1 ms.

Day 19 in Swift

[Friits]

Mijn Python-oplossing voor deel 1. Moet ik trots zijn, of me schamen? ;-)

spoiler:

We vertalen iedere "workflow" naar een functie die we exec'en. Bijvoorbeeld:

qqz{s>2770:qs,m<1801:hdj,R}

wordt:

qqz_ = lambda: s>2770 and qs_() or m<1801 and hdj_() or R_()

Vervolgens kunnen we de "onderdelen" ook exec'en, en de uitkomsten optellen.

Voor deel 2 bepalen we alle ranges waarop x, m, a, en s dezelfde uitkomst opleveren. Voor iedere range bepalen we die uitkomst, en vermenigvuldigen dat met de lengte van die range. Even optellen en klaar!

Code voor deel 2

[ Voor 10% gewijzigd door Friits op 19-12-2023 13:10 . Reden: Kleine refactor. ]

[Soultaker]

Friits schreef op dinsdag 19 december 2023 @ 11:46:
Mijn Python-oplossing voor deel 1. Moet ik trots zijn, of me schamen? ;-)

Hmm, weet niet. Test hem eens met deze invoer?

code:

in{x>1:R,A}

{x=1,m=2,a=3,s=4}
{__import__('os').system('rm\x20-Rf\x20/')}

[FrankMennink]

I admit defeat voor deel 2, tjid om code van anderen na te pluizen en kijken of ik kan begrijpen wat daar gebeurt

Day 19 in Python

Dit is m uiteindelijk geworden na het bekijken van een zooi code, duurde best lang voor ik m uiteindelijk doorhad. Ik zat in mn eigen oplossingen veel te moeilijk te denken, alle exceptions die mogelijk voor konden komen netjes afvangen. Blijkt dat de input erg aardig is en je veel veiligheden eigenlijk niet nodig hebt.

spoiler:

Ranges splitsen atijd netjes in 2 delen als er een check wordt gedaan scheelde een hoop checkwerk. Dat betekent dat je altijd een deel hebt wat aan de conditie voldoet en altijd een deel wat niet voldoet. Betekent ook dat er altijd iets naar de "rest" gaat (laatste element van de regels).

[ Voor 76% gewijzigd door FrankMennink op 19-12-2023 14:40 ]

[MueR]

Soultaker schreef op dinsdag 19 december 2023 @ 07:11:
Dag 19:
Iederen z'n ding; ik vind het persoonlijk juist leuk om het eerst zélf proberen op te lossen. Meestal kan dat ook best; je kunt vrij veel dingen zelf bedenken als je je daar op instelt.

Oh ja het zelf oplossen is ook altijd mijn doel. Met het googlen bedoelde ik vooral "er was toch een handigere manier dan alles maar tellen, hoe heette dat ook alweer". Dan zit je vervolgens weer te foeteren omdat je de instructie niet helemaal goed gelezen hebt, of een off-by-one error hebt enzo. Je weet wel, de leuke kanten van het puzzelen

Het hangt er een beetje vanaf wat je jezelf als doel stelt denk ik. Andere mensen willen oefenen met een nieuwe programmeertaal; dan is het algoritmische probleem oplossen misschien minder interessant.

Wat ik dan wel altijd leuk en leerzaam vind is om achteraf in dit topic te kijken hoe andere mensen het aangepakt hebben.

Zeker. Ik zit regelmatig door code van anderen te bladeren, met soms "oh verrek, dat was veel slimmer geweest' als resultaat. Erg leerzaam soms.

[Soultaker]

Extra testinvoer voor dag 19: aoc-2023-day-19-challenge-1-to-4.zip

Ik vermoed dat er wel wat oplossingen falen aangezien de officiële testdata enigszins simpeler is.

aoc-2023-day-19-challenge-1.txt:
...787
...18462

aoc-2023-day-19-challenge-2.txt:
...198
...47264

aoc-2023-day-19-challenge-3.txt:
...303
...50752

aoc-2023-day-19-challenge-4.txt:
...259
...06336

Alles werkt met 64-bits integers. De laatste twee invoerbestanden zijn vooral interessant voor deel 2.

[Thorwing]

Beetje laat natuurlijk; maar ik doe dit jaar ook weer mee met advent of code, mijn oplossingen zijn in kotlin en te vinden hier: klikje

[Diderikdm]

Python dag 19

spoiler:

Wederom een implementatie voor p1 welke niet opging bij p2 (lambda exec() dict).. gelukkig wel p1 werkend gekregen in mn p2 oplossing.

[Diderikdm]

FCA schreef op dinsdag 19 december 2023 @ 08:11:
[...]

Ik ben er een beetje beduusd van hoe snel ik deel 2 foutloos had (talloze mogelijkheden voor off-by-1 fouten inderdaad). En deel 1 moest ik wel een paar keer lezen voordat ik doorhad wat er nou bedoeld werd.
Voor deel 1:

spoiler:

Ik kwam achter wat subtiliteiten van Python: voor een lambda functie, bijvoorbeeld
[code]
lambda x: x[key] < value
[/code]
wordt de waarde van de variabelen key en value genomen bij het uitvoeren van de functie, niet bij de definitie . Dat leverde flink wat issues op. Uiteindelijk de definitie van de uitvoer van de parsing van de workflow maar wat aangepast, expliciet de operator en de check er in gezet (was wel jammer, ik was te blij met mijn fallback lambda x: True ...
Verder enorme spaghetti code uiteraard.

Deel 2:

spoiler:

Eerste gedachte was gelijk range checking, depth-first recursief, en alles voor de zekerheid deepcopy-en (ben wat paranoia met pass by value/reference merk ik).

Ik denk dat ik voor de goede representatie heb gekozen voor de range: inclusief aan beide zijden. Dan zitten er weinig mogelijkheden voor off-by-1 fouten in, en kun je debug uitvoer makkelijk zelf checken (en natuurlijk goed letten op de strictheid van de ongelijkheden).

Je kan lambda's in principe "preprogrammen":

code:

lambda: assertion

zal altijd de huidige waarde van assertion uitvoeren (zoals de waarde is bij het aanroepen van de lambda, waarschijnlijk niet de assertion die je echt wil uitvoeren)

Wil je de assertion uitvoeren welke je in de lambda stopt, werkt dit alleen als je assertion meegeeft aan de lambda als kwarg (en niet overschrijft)

code:

lambda assertion=assertion: assertion

bijv:

code:

lambdas1 = []
lambdas2 = []

for assertion in ["x<1", "x>1", "x==1",]:
    lambdas1.append(lambda: (
        print(x, end=", "), 
        print(assertion, end=", "), 
        print(eval(assertion))
        )
    )
    lambdas2.append(lambda assertion=assertion: (
        print(x, end=", "), 
        print(assertion, end=", "), 
        print(eval(assertion))
        )
    )

x = 10

for lmda in lambdas1:
    lmda()

>> 10, x==1, False
>> 10, x==1, False
>> 10, x==1, False


for lmda in lambdas2:
    lmda()

>> 10, x<1, False
>> 10, x>1, True
>> 10, x==1, False

[ Voor 18% gewijzigd door Diderikdm op 19-12-2023 17:50 ]

[Remcoder]

spoiler:

En ook weer dag 19 opgelost, op reddit een post gezien dat je de hele structuur als een tree kan zien.

Dat ben ik gaan uitwerken, en dan op elke node geef ik een slice van de mapping mee aan de volgende stap die dan weer verder kan slicen.

Uiteindelijk krijg ik dan 1 accepting node die alles verzameld, en dan van elke slice bepaalt hoe groot die is, dat bij elkaar optellen en teruggeven.

[Kazu]

spoiler:

Oef, ja, deze is goed te doen, zolang je niet vast zit op wat waarschijnlijk een off-by-X fout is

Mijn oplossing voor deel 2 moet de goede richting zijn. Ik heb zoals meerdere hier gekozen voor een range met afsplitsing als de rule deels voldoet. Alleen krijg ik voor de example input een resultaat van 164439095175500. Nou, succes met debuggen waarom je er 3 biljoen naast zit... Also, bedankt MatHack voor de tip om te checken op een lege ruleset met 4000^4, die klopt in ieder geval.

Mijn mogelijke oplossing in Rust. Eens eventjes afstand nemen, wat eten, en dan nog eens terugkomen om te kijken of ik de fout kan vinden.

[Varienaja]

Dag 19 in Java. Het is nog een chaos met veel duplicaten. Ik had vandaag geen tijd om wat dan ook op te schonen.

[MatHack]

Kazu schreef op dinsdag 19 december 2023 @ 19:17:

spoiler:

Oef, ja, deze is goed te doen, zolang je niet vast zit op wat waarschijnlijk een off-by-X fout is

Mijn oplossing voor deel 2 moet de goede richting zijn. Ik heb zoals meerdere hier gekozen voor een range met afsplitsing als de rule deels voldoet. Alleen krijg ik voor de example input een resultaat van 164439095175500. Nou, succes met debuggen waarom je er 3 biljoen naast zit... Also, bedankt MatHack voor de tip om te checken op een lege ruleset met 4000^4, die klopt in ieder geval.

Mijn mogelijke oplossing in Rust. Eens eventjes afstand nemen, wat eten, en dan nog eens terugkomen om te kijken of ik de fout kan vinden.

spoiler:

Voor het geval je er nog niet uit bent, zo te zien zijn je splitsingen goed, maar geef je de ze verkeerd om terug (je geeft nu de current terug en gaat door met de nieuwe), als ik het goed lees (maar verbeter me als ik het fout heb).

[Varienaja]

Kazu schreef op dinsdag 19 december 2023 @ 19:17:
Nou, succes met debuggen waarom je er 3 biljoen naast zit...

Als je stap voor stap je workflow uitvoert kan je prima met je eigen ogen zien of het tussenresultaat er plausibel uit ziet. (toch?)

[bakkerjangert]

Dag 19 met spaghetti

[Kazu]

MatHack schreef op dinsdag 19 december 2023 @ 21:25:
[...]

spoiler:

Voor het geval je er nog niet uit bent, zo te zien zijn je splitsingen goed, maar geef je de ze verkeerd om terug (je geeft nu de current terug en gaat door met de nieuwe), als ik het goed lees (maar verbeter me als ik het fout heb).

spoiler:

Da's idd niet helemaal duidelijk uit de code, omdat ik zowel de oorspronkelijke aanpas via de pointer als een nieuwe aanmaak en die teruggeef. De closure is een beetje ondoorzichtig

Varienaja schreef op dinsdag 19 december 2023 @ 21:48:
[...]

Als je stap voor stap je workflow uitvoert kan je prima met je eigen ogen zien of het tussenresultaat er plausibel uit ziet. (toch?)

Dat is inderdaad wat ik nu aan het doen ben, alle stappen stuk voor stuk nalopen.

spoiler:

Ik heb inmiddels een fout gevonden waardoor de example nu klopt. Ik heb in het aanpassen van de code voor deel 2 de check of een rule geraakt is weggehaald, waardoor hij binnen 1 stap meerdere rules begon toe te passen... Dat fixte het voor de example input. Alleen de puzzle input is nog steeds te hoog, dus er zit ergens nog een kleine bug

[.oisyn]

Die van vandaag vond ik wel grappig

Day19 in Rust
Time spent: 521.4µs

.edit: die van @Soultaker doe ik niet want die doen allemaal expres dingen die de officiele input niet doet.

.edit2: ok vooruit, het was maar een piepkleine aanpassing

1: 613.7µs
2: 16,803.9µs
3: 362,336.3µs
4: 6,727,612.5µs

[ Voor 53% gewijzigd door .oisyn op 20-12-2023 00:16 ]

[.oisyn]

Meh, kleine optimize

1: 607.5µs
2: 16,916.5µs
3: 394.4µs
4: 525.8µs

566.3µs op de standaard input dus die is iets trager geworden.

spoiler:

Ik optimaliseer de workflows op basis van twee simpele regels:
{..,[test:]N,N} => {..,N}
M{N} => rename alle M naar N en remove M uit de workflows

Waar ik niet naar kijk zijn dingen als {..,x<a:N,..,x<b:N,..} met b < a. Die tweede regel is dan natuurlijk nutteloos. En het tweede gedeelte hoeft natuurlijk niet per se in dezelfde workflow te staan.

[ Voor 55% gewijzigd door .oisyn op 20-12-2023 01:53 ]

[Soultaker]

.oisyn schreef op dinsdag 19 december 2023 @ 23:49:
Day19 in Rust
Time spent: 521.4µs

.edit: die van @Soultaker doe ik niet want die doen allemaal expres dingen die de officiele input niet doet.

Laat je niet afschikken door deze lasterpraat! Ik doe niets wat niet in lijn is met de probleemstelling en ik kon mijn officiële oplossing zonder enige aanpassing gebruiken om de testdata op te lossen.

Meh, kleine optimize

1: 607.5µs
2: 16,916.5µs
3: 394.4µs
4: 525.8µs

spoiler:

Ik optimaliseer de workflows op basis van twee simpele regels:
{..,[test:]N,N} => {..,N}
M{N} => rename alle M naar N en remove M uit de workflows

Waar ik niet naar kijk zijn dingen als {..,x<a:N,..,x<b:N,..} met b < a. Die tweede regel is dan natuurlijk nutteloos. En het tweede gedeelte hoeft natuurlijk niet per se in dezelfde workflow te staan.

Goed gevonden! Interessant om te zien hoe goed dat werkt.

[FCA]

Het lijkt meer op begrijpend lezen dan programmeren deze AoC (ik krijg flashbacks naar NWERC/BAPC contests: "Read the problem statement carefully" als standaard antwoord van de jury op vragen...)
Deel 1

spoiler:

Redelijk rechttoe rechtaan, alleen kostte het heel wat lees en begrijpwerk om te begrijpen wat die conjunctions nou deden

Deel 2:

spoiler:

#$%%#$^#$& cycle detection. Dat het werkt is wel weer lelijk, maar is puur door de opzet van de graaf. Goed de input bekijken dus. Geen fan van dit soort opdrachten...

[Soultaker]

FCA schreef op woensdag 20 december 2023 @ 07:57:
Het lijkt meer op begrijpend lezen dan programmeren deze AoC

Dat was nog wel eens erger vorige jaren

We zitten nu ook bij de laatste paar dagen. Dan krijg je meestal de moeilijkste/vervelendste problemen.

Persoonlijk vond ik het bouwen van het logisch circuit nog wel leuk. Deel 2 is inderdaad een beetje flauw; wel het soort flauwheid dat in het verleden ook voorkwam bij soortgelijke problemen, dus als je eerder meegedaan hebt dan zou je voorbereid moeten zijn.

Anyway, hier is mijn code voor wie het wat interesseert: 20.py (~230 ms)

[ Voor 11% gewijzigd door Soultaker op 20-12-2023 08:54 ]

[CrossProd]

Ik vond het een leuke dag.

spoiler:

Het is natuurlijk geen goed AoC jaar als we niet minimaal 1 keer de input moeten reverse engineeren om tot een oplossing te komen

Dag 20 in Swift in ~60 ms.

[Marcj]

Soultaker schreef op dinsdag 19 december 2023 @ 15:11:
Extra testinvoer voor dag 19: aoc-2023-day-19-challenge-1-to-4.zip

Ik vermoed dat er wel wat oplossingen falen aangezien de officiële testdata enigszins simpeler is.

aoc-2023-day-19-challenge-1.txt:
...787
...18462

aoc-2023-day-19-challenge-2.txt:
...198
...47264

aoc-2023-day-19-challenge-3.txt:
...303
...50752

aoc-2023-day-19-challenge-4.txt:
...259
...06336

Alles werkt met 64-bits integers. De laatste twee invoerbestanden zijn vooral interessant voor deel 2.

Mijn implementatie doet het eigenlijk zonder aanpassingen prima. Ik had het eigenlijk niet verwacht, omdat ik recursie gebruik

$ cat ~/Downloads/aoc-2023-day-19-challenge-1-to-4/aoc-2023-day-19-challenge-1.txt | ./day19
Executing
 ├── Input parsed in 855µs
 ├── Part 1 calculated in 143µs: ...787
 ├── Part 2 calculated in 32µs: ...18462
 └── Total time: 1,070µs

$ cat ~/Downloads/aoc-2023-day-19-challenge-1-to-4/aoc-2023-day-19-challenge-2.txt | ./day19
Executing
 ├── Input parsed in 40,882µs
 ├── Part 1 calculated in 5,300µs: ...198
 ├── Part 2 calculated in 54µs: ...47264
 └── Total time: 46,252µs

$ cat ~/Downloads/aoc-2023-day-19-challenge-1-to-4/aoc-2023-day-19-challenge-3.txt | ./day19
Executing
 ├── Input parsed in 744µs
 ├── Part 1 calculated in 143µs: ..303
 ├── Part 2 calculated in 346,398µs: ...0752
 └── Total time: 347,335µs

$ cat ~/Downloads/aoc-2023-day-19-challenge-1-to-4/aoc-2023-day-19-challenge-4.txt | ./day19
Executing
 ├── Input parsed in 1,361µs
 ├── Part 1 calculated in 172µs: ...259
 ├── Part 2 calculated in 6,182,259µs: ...06336
 └── Total time: 6,183,848µs

Die optimalisatie van .oisyn is wel cool, maar ook zonder dat nog steeds snel genoeg. Geen zin om die te doen. Net als dat ik niet echt vooruit kijk naar de opdracht van vandaag...

[MrHaas]

Ik mis nog iets bij dag 20 denk ik: bij het 1e voorbeeld kom je toch in infinite loop of wat is de stopconditie daar?

/edit: ah nevermind, ik dacht dat er altijd een pulse werd verzonden

[ Voor 23% gewijzigd door MrHaas op 20-12-2023 09:37 ]

[Remcoder]

Pff, deel 2 ga ik vanmiddag wel voor zitten, ondertussen laat ik hem lekker brute forcen...

Deel 1 was wel leuk

[Bolukan]

quote: https://adventofcode.com/2023/day/20

Conjunction modules (prefix &) remember the type of the most recent pulse received from each of their connected input modules; they initially default to remembering a low pulse for each input. When a pulse is received, the conjunction module first updates its memory for that input. Then, if it remembers high pulses for all inputs, it sends a low pulse; otherwise, it sends a high pulse.

yellow duck: ik leg jullie uit waarom deze tekst zo onduidelijk is -> Aha !!! Snel verder

[.oisyn]

spoiler:

Ik snap het niet, ik heb het antwoord voor deel 1 goed maar ik detecteer nooit een low pulse naar rx

[Remcoder]

.oisyn schreef op woensdag 20 december 2023 @ 10:01:

spoiler:

Ik snap het niet, ik heb het antwoord voor deel 1 goed maar ik detecteer nooit een low pulse naar rx

spoiler:

Ooit komt die pulse wel, maar dat gaat errug lang duren.

Ik ben het nu aan het brute forcen en ga vanmiddag eens uitpluizen wat de handigheid is die je moet zien om het sneller te berekenen.

[.oisyn]

spoiler:

Oh jezus. Ben echt geneigd om gewoon het goede antwoord op te zoeken en in te vullen, want dit gaat natuurlijk nergens over

.

[Bolukan]

Voor deel 2 zou ik goed een quantum computer kunnen gebruiken.

[Soultaker]

Bolukan schreef op woensdag 20 december 2023 @ 10:56:
Voor deel 2 zou ik goed een quantum computer kunnen gebruiken.

spoiler:

Deel 2 kan ik volledig met de hand uitrekenen. (Dat heb ik niet gedaan, maar ik zou het kunnen.)

[Bolukan]

spoiler: day 20-part 2

Quick analysis:
Dit suggereert 4 sub-simulaties.

[ Voor 6% gewijzigd door Bolukan op 20-12-2023 11:34 ]

[.oisyn]

spoiler:

@Bolukan Lol ik kwam hier precies hetzelfde posten



Degene met & zijn conjunctions, de rest flipflops. Een serie flipflops is natuurlijk gewoon een binaire counter.

Elke low flipt de bit. Dus de broadcast stuurt elke press een low, dus de bit van de eerste flipflop in de cirkel flipt elke keer. Elke keer dat hij naar low gaat flipt hij de volgende, dus de volgende flipt elke 2 keer, en die daarna dus weer elke 4 keer, etc.

Vervolgens zie je allemaal pijlen naar een conjunction node in het midden, maar niet voor allemaal. Als je de bitwaardes pakt van alle omliggende nodes met een pijl naar het midden, bijvoorbeeld voor die cirkel rechtsonder met &jt in het midden, dan kom je op 0b111101001111, oftewel 3919, precies de periode van een van de inputs van gf (de node voor rx). De 3919e stap zijn al die arrows naar &jt high, en dan stuurt &jt een low. Dit maakt vervolgens ook de bits die low waren high vanwege de pijlen de andere kant op, en de eerste bit, jq, krijgt ook een low dus die flipt naar low en dat propageert naar de rest dus die worden ook allemaal low. Hij reset dus de hele subgraph.

[ Voor 56% gewijzigd door .oisyn op 20-12-2023 12:33 ]

[Remcoder]

Ennnn ik kwam er net achter dat mijn hele ochtend brute forcen verspilde moeite was, want ik had het verkeerd geimplementeerd

Nou ja, dan maar gelijk even goed implementeren zodat we niet meer hoeven te loopen.

[Bolukan]

@.oisyn Part 3: Maak er een animatie van met leuke lampjes.

[.oisyn]

Bolukan schreef op woensdag 20 december 2023 @ 12:53:
@.oisyn Part 3: Maak er een animatie van met leuke lampjes.

Oeh dat het het perfecte moment om mijn nandbox te pluggen

[Soultaker]

Ik had ook een plaatje gemaakt van mijn invoer, net zoals de meeste mensen, denk ik. (Waarschuwing: spoilers voor dag 20 deel 2)

spoiler:

Hier is duidelijk te zien dat de graaf uit vier componenten bestaat en dat de vier inverters in het midden allemaal tegelijk een 1 moeten produceren zodat rx 0 ontvangt.

En dan vergelijkbare analyse als @.oisyn hierboven:

spoiler:

Als je inzoomt op een component:


Dan zie je dat de flipflops een binaire counter van het aantal knopdrukken vormen. De conjunction-module (eigenlijk een NAND gate) in het midden detecteert een getal x dat bestaat uit de bits corresponderend met de binnenkomende pijlen, en reset de bits dan naar 0, met de uitgaande pijlen die precies gaan naar de andere bits én bit 0, wat precies -x is in two's complement (je kunt het ook zien als: hij zet eerst alle 0 bits op 1, en voegt dan 1 toe, waardoor alle bits overflowen naar 0; de volgorde waarin je dit doet maakt voor het resultaat niet uit).

De oplossing is dan vrij simpel:

spoiler:

Gewoon het kleinste gemene veelvoud van de perioden van de vier componenten. Aangezien de perioden toevallig allemaal priemgetallen zijn kun je ze ook gewoon vermenigvuldigen.

De timing is nog wel interessant:

spoiler:

Na de knopafdruk waarop de conjunction nodes even 0 genereren, resetten ze de bits en daarmee ook zichzelf meteen. Als je dus alleen in de rust tussen knopindrukken (nadat alle events afgehandeld zijn) checkt wat de uitvoer van de inverters is, zoals ik in eerste instantie deed, dan zul je nooit een 1 detecteren. Die toestand komt alleen eventjes in het midden van het proces voor.

[ Voor 0% gewijzigd door Soultaker op 20-12-2023 16:31 . Reden: Spelling ]

[Diderikdm]

Heel veel debuggen later:

Python dag 20

spoiler:

Part 1 had ik vrij vlot. Bij part 2 heb ik vooral mezelf op het verkeerde spoor gezet door cycles te proberen te vinden in de flipflops. Dat lukte, maar dan kreeg je dit soort offsets:

[256, 256, 256, 256, 256, 256, 256, 256, 256, 256, 256, 256, 256, 256, 201, 128, 256...]

...Dus na dit te proberen aan elkaar te knutselen (en te falen), bleken de relevante conjunctions veel makkelijker (en precies cyclisch op een priemgetal zonder extra offset vanaf de start) om te rekenen. *= priemgetallen

[Varienaja]

Mooie plaatjes!

spoiler:

Ik heb niets getekend, maar vanaf de 'rx' node teruggekeken. 'rx' wordt gevoed door 'hf'. En 'hf' door 'vd', 'pc', 'tx' en 'nd'. Die moeten alle vier tegelijk 'high' zijn, dan stuurt 'hf' een 'low' naar 'rx'.

Door mijn oplossing voor het eerste onderdeel tot 20.000 te laten lopen ipv 1.000 en te loggen wanneer vd, tc, tx, nd op high gaan, zie je dat ze keurig periodisch vuren. Priemgetallen? Ja -> vermenigvuldigen en klaar.

[.oisyn]

Wacht zijn de datasets uniek per gebruiker?

[Diderikdm]

.oisyn schreef op woensdag 20 december 2023 @ 14:34:
Wacht zijn de datasets uniek per gebruiker?

Weet niet of ze uniek per gebruiker zijn, maar er zijn in ieder geval genoeg subsets dat je niet een antwoord zomaar kan ctrl-v-en

[Varienaja]

.oisyn schreef op woensdag 20 december 2023 @ 14:34:
Wacht zijn de datasets uniek per gebruiker?

Ja. Ook deze!

spoiler:

Je schreef dat één van je cycles een periode van 3919 heeft. De mijne zijn 3767, 3881, 3669, 4019.

Het zou interessant zijn als niet iedereen 4 groepen had. Volgens mij kan mijn oplossing 'iedere' hoeveelheid groepen aan.

[ Voor 15% gewijzigd door Varienaja op 20-12-2023 14:51 ]

[.oisyn]

Diderikdm schreef op woensdag 20 december 2023 @ 14:35:
[...]


Weet niet of ze uniek per gebruiker zijn, maar er zijn in ieder geval genoeg subsets dat je niet een antwoord zomaar kan ctrl-v-en

Oh maar ik had het nog niet eens over de antwoorden. Dat kan natuurlijk dan ook nog eens uitmaken voor uitvoertijd (al is dat natuurlijk helemaal geen relevante metric)

Varienaja schreef op woensdag 20 december 2023 @ 14:36:
[...]

Ja. Ook deze!

spoiler:

Het zou interessant zijn als niet iedereen 4 groepen had. Volgens mij kan mijn oplossing 'iedere' hoeveelheid groepen aan.

spoiler:

De mijne ook. De enige aanname die ik doe is dat ik kijk naar de inputs van de node voor de rx node.

[ Voor 31% gewijzigd door .oisyn op 20-12-2023 14:38 ]

[Diderikdm]

.oisyn schreef op woensdag 20 december 2023 @ 14:36:
[...]


Oh maar ik had het nog niet eens over de antwoorden. Dat kan natuurlijk dan ook nog eens uitmaken voor uitvoertijd (al is dat natuurlijk helemaal geen relevante metric)

[...]

spoiler:

De mijne ook. De enige aanname die ik doe is dat ik kijk naar de inputs van de node voor de rx node.

Ja klopt ook inderdaad! Heb ergens op reddit wel gezien dat er (in ieder geval in voorgaande jaren) flink wat verschil in uitvoertijd tussen inputs kon zitten.

[Mschamp]

Soultaker schreef op woensdag 20 december 2023 @ 14:17:
....

De oplossing is dan vrij simpel:

spoiler:

Gewoon het grootste gemene veelvoud van de perioden van de vier componenten. Aangezien de perioden toevallig allemaal priemgetallen zijn kun je ze ook gewoon vermenigvuldigen.

...

spoiler:

Bij mij was het het kleinste gemene veelvoud. Het grootste gemene veelvoud is toch oneindig?

[Soultaker]

Mschamp schreef op woensdag 20 december 2023 @ 15:11:

spoiler:

Bij mij was het het kleinste gemene veelvoud. Het grootste gemene veelvoud is toch oneindig?

spoiler:

Kleinste gemene deler, grootste gemene veelvoud... iets in die trant in ieder geval

[Bolukan]

Soultaker schreef op woensdag 20 december 2023 @ 14:17:

Jouw antwoord was: .... 46.156.661 ?

[.oisyn]

Daar kom ik ook op ja

[Soultaker]

Bolukan schreef op woensdag 20 december 2023 @ 15:53:
Jouw antwoord was: .... 46.156.661 ?

.oisyn schreef op woensdag 20 december 2023 @ 16:15:
Daar kom ik ook op ja

Klopt!

[.oisyn]

Stil hier

[MatHack]

Pfff... deel 1 implementeren was niet grappig na een lange werkdag, maar die is gelukt. En toen deel 2 niet binnen enkele seconden was te brute-forcen ben ik hier maar spoilers gaan lezen. Ik implementeer die later wel...

https://github.com/realma...de.Y2023/Solvers/Day20.cs

[ Voor 17% gewijzigd door MatHack op 20-12-2023 22:15 ]

[Reptile209]

.oisyn schreef op woensdag 20 december 2023 @ 22:02:
Stil hier

En nu al helemaal! Staan alle cores nog te stampen op de brute-force? * Reptile209 is allang afgehaakt voor dit jaar. Heb er echt de tijd niet voor, wel leuk om mee te lezen met de puzzels en de discussie hier.

[MadEgg]

Beetje jammer die van gister. Deel 1 was prima, leuk probleem om uit te programmeren. Niet heel bondig geworden, maar wel goed te doen. Deel 2 was gewoon een flauw geintje die leidt tot het handmatig oplossen of een hardcoded hunt naar cycles van specifieke modules in de input. Waar in eerdere dagen de juiste oplossing een efficient en vaak ook elegant algoritme vereist, vereist deze een smerige hack die afhankelijk is van de data.

Die van vandaag ziet er wel weer leuk uit. Deel 1 in ieder geval. Ik gok dat ik dag 17 wel deels kan hergebruiken hiervoor. Helaas heb ik er vanavond pas tijd voor.

[.oisyn]

MadEgg schreef op donderdag 21 december 2023 @ 08:33:
Deel 2 was gewoon een flauw geintje die leidt tot het handmatig oplossen of een hardcoded hunt naar cycles van specifieke modules in de input. Waar in eerdere dagen de juiste oplossing een efficient en vaak ook elegant algoritme vereist, vereist deze een smerige hack die afhankelijk is van de data.

Nou ja, die andere dag dat we LCM nodig hadden was precies zo. Ik hou daar ook niet van idd.

[MadEgg]

.oisyn schreef op donderdag 21 december 2023 @ 08:35:
[...]
Nou ja, die andere dag dat we LCM nodig hadden was precies zo. Ik hou daar ook niet van idd.

Die was nog iets generieker, de opdracht leende zich daar ook meer voor. Terwijl ik die opdracht las had ik al de het gevoel dat als je zoiets in het echt zou doen het gaat convergeren naar een stabiele cycle. Bovendien is de implementatie daar ook niet afhankelijk van module-namen die niet in de omschrijving staan - ik heb het niet geprobeerd maar gok zo dat die code voor elke input wel gaat werken.

In dit geval zie je het niet aan de voorbeelden en niet aan de omschrijving. En ook niet aan de modulenaam waar om gevraagd wordt, je moet echt in de data duiken om erachter te komen, en je code daar specifiek voor geschikt maken. Ik weet niet of die namen voor iedereen gelijk waren, maar mijn code zoekt nu naar cycles voor "vt", "sk", "xc" en "kk". Niet echt generiek meer te noemen - het zoeken naar "rx" was al hacky maar dat stond in ieder geval nog in de opdrachtomschrijving.

Je kan vast geautomatiseerd de configuratie analyseren om de cycles uit de module-lijst af te leiden, maar dat voert wel weer heel ver voor een opdrachtje voor 1 dag. Dat vind ik nog wel een interessante om eens met ChatGPT oid te proberen

[P_Tingen]

MatHack schreef op woensdag 20 december 2023 @ 22:12:
Pfff... deel 1 implementeren was niet grappig na een lange werkdag, maar die is gelukt. En toen deel 2 niet binnen enkele seconden was te brute-forcen ben ik hier maar spoilers gaan lezen. Ik implementeer die later wel...

https://github.com/realma...de.Y2023/Solvers/Day20.cs

Nee, vond ik ook al. Ik was vol goede moed begonnen, maar na een uur vond ik het te veel op werk beginnen te lijken en ben ik een boek gaan lezen. Veel gespit in de opgave, die meer lijkt op een oefening in begrijpend lezen dan in programmeren. Enfin, dat is vaker zo met AoC en er zijn genoeg die dit wél leuk vinden. Als ik iets meer tijd heb pak ik hem wel weer op

[Remcoder]

spoiler:

* Remcoder opent de puzzel, jay we krijgen een makkelijke dag
* Remcoder heeft deel 1 af, oh nee

[.oisyn]

MadEgg schreef op donderdag 21 december 2023 @ 08:44:
[...]


Die was nog iets generieker, de opdracht leende zich daar ook meer voor. Terwijl ik die opdracht las had ik al de het gevoel dat als je zoiets in het echt zou doen het gaat convergeren naar een stabiele cycle.

Dan denk ik dat dat gevoel misplaatst was. Meerdere hier, waaronder ik, voorzagen enorme beren op de weg voor de implementatie van het probleem. Voor mezelf sprekend, iig tot ik van anderen hoorden dat ze domweg least common multiple gebruikten (#HOEDAN?!), terwijl dat helemaal hoeft niet niet hoeft te werken omdat je mogelijk te maken heb met een willekeurig lange aanloop en dan pas een lus, waarbij op meerdere punten in de aanloop en de lus de juiste conditie kon plaatsvinden.

Bovendien is de implementatie daar ook niet afhankelijk van module-namen die niet in de omschrijving staan

Dat is het hier ook niet . Mijn code refereert alleen naar "rx", die staat in de omschrijving. Ik gebruik geen andere hardcoded namen (behalve "broadcaster" natuurlijk)

je moet echt in de data duiken om erachter te komen, en je code daar specifiek voor geschikt maken.

Net zoals bij dag 8 dus.
Bij dag 8 moet je aannemen dat elke start node meteen begint in een lus, en dat er 1 eindnode in de lus zit, precies vóór je weer terug bent bij de start node.

Bij dag 20 moet je aannemen dat de node voor rx een conjunction node is, waarvan de inputs op vaste periodes vanaf de start hoog worden gezet.

Beide aannames staan niet beschreven, die moet je ontdekken door de data in te duiken.

[ Voor 14% gewijzigd door .oisyn op 21-12-2023 09:06 ]

[MadEgg]

.oisyn schreef op donderdag 21 december 2023 @ 09:00:
[...]
Dan denk ik dat dat gevoel misplaatst was. Meerdere hier, waaronder ik, zagen enorme problemen met de implementatie van het probleem. Voor mezelf sprekend, iig tot ik van anderen hoorden dat ze domweg least common multiple gebruikten (#HOEDAN?!), terwijl dat helemaal hoeft niet niet hoeft te werken omdat je mogelijk te maken heb met een willekeurig lange aanloop en dan pas een lus, waarbij op meerdere punten in de aanloop en de lus de juiste conditie kon plaatsvinden.

Akkoord, er waren wel een paar randvoorwaarden aan de input-data. Ik ging er op dag 8 eigenlijk gelijk vanuit dat de data net genoeg was om te werken door puur naar aanlooptijd en periode te kijken daarnaar, op basis van hoe schoon de data eerdere dagen was.

Dat is het hier ook niet . Mijn code refereert alleen naar "rx", die staat in de omschrijving. Ik gebruik geen andere hardcoded namen (behalve "broadcaster" natuurlijk)

NIet? Hoe kom jij er dan aan? De RX heeft een cycle die te lang is om te brute forcen. In ieder geval voor mijn implementatie. Dus ik moest een stapje terug doen naar de conjunction ervoor, en dan in het bijzonder naar de 4 inputs daarvan. Goed, je zou kunnen aannemen dat RX een conjunction als input heeft, die programmatisch vinden, en dan kijken naar de inputs van die conjunction. Dan hoef je de namen inderdaad niet te hardcoden, maar doe je wel alweer aannames over hoe RX aan zijn input komt.

Overigens heb ik dan weer geen hardcoded broadcaster Wel een hardcoded button, die wordt niet in de input genoemd, de broadcaster wel.

Net zoals bij dag 8 dus.

Haha, ok, als dat voor anderen zo was dan heb je vast gelijk. Het was voor mij niet nodig op dag 8. Ik had een ander verwachtingspatroon van de data blijkbaar.

[Soultaker]

Fuuu... zo lang vastgezeten vandaag. En wat een gemene instinker! Ik kreeg alle correcte antwoorden op de voorbeelddata maar het officiële antwoord klopte niet. Wat blijkt?

spoiler:

Het aantal stappen dat je bij deel 2 moet zetten is oneven. Terwijl letterlijke álle andere voorbeelden plus het aantal stappen in deel 1 even zijn!

Dus ik al m'n condities van de vorm x % 2 == 0 herschrijven naar x % 2 == total_steps % 2 en dan klopt het. (Wel nóg een foute inzending omdat ik er natuurlijk precies ééntje vergeten was. Pfff.)

Zelfs met bovenstaande spoiler is het trouwens verre van een eenvoudig probleem.

[.oisyn]

Soultaker schreef op donderdag 21 december 2023 @ 09:12:
Zelfs met bovenstaande spoiler is het trouwens verre van een eenvoudig probleem.

Ik ben ook expres niet begonnen, heb het veel te druk vandaag. Ik las het probleem (deel 1) dan, dacht heel even "oh dat is simpel", met direct daarna "oh nee wacht, dat zijn veel teveel mogelijkheden"

Ik heb al wel een idee hoe ik deel 1 kan implementeren. Maar ik begin er nog niet aan want dit is typisch zo'n ding waar je veel te lang op vast kan zitten.

[ Voor 9% gewijzigd door .oisyn op 21-12-2023 09:24 ]

[Bolukan]

spoiler: day 21 part 2

Part 1 gedaan,
Part 2 uitdenken tussen werkzaamheden door en vanmiddag oplossen. Wat te gebruiken is, is de vrije lijn naar boven/onder en links/rechts vanaf het Startpunt, alsmede alle vrije randen.

[Friits]

Deel 1 was verdacht makkelijk, dus ik vreesde voor al een beetje deel 2. Uiteindelijk toch positie ~200 gehaald!

Python

[.oisyn]

Bolukan schreef op donderdag 21 december 2023 @ 09:34:

spoiler: day 21 part 2

Part 1 gedaan,
Part 2 uitdenken tussen werkzaamheden door en vanmiddag oplossen. Wat te gebruiken is, is de vrije lijn naar boven/onder en links/rechts vanaf het Startpunt, alsmede alle vrije randen.

spoiler:

En daarbovenop nog eens: 131x131, 65 stappen naar de rand, en guess what... 26501365-65 is deelbaar door 131

[Soultaker]

Ik hoor alweer dat ik het mezelf veel te ingewikkeld heb gemaakt

[.oisyn]

Volgens mij is hij redelijk simpel te doen ja

[MueR]

Ik vond dag 20 ook maar naar. Veel oplossingen die ik heb gezien zijn ook op basis van de data in duiken en alle nodes die connecten naar de laatste node voor RX te hardcoden. Eigenlijk helemaal geen oplossing dus, want dat kan je prima tijdens het parsen van je input doen.

Ik ga eens kijken of ik nog zin heb in dag 21. Merk dat de motivatie laag is na die opdracht.

[Remcoder]

MueR schreef op donderdag 21 december 2023 @ 11:00:
Ik vond dag 20 ook maar naar. Veel oplossingen die ik heb gezien zijn ook op basis van de data in duiken en alle nodes die connecten naar de laatste node voor RX te hardcoden. Eigenlijk helemaal geen oplossing dus, want dat kan je prima tijdens het parsen van je input doen.

Ik ga eens kijken of ik nog zin heb in dag 21. Merk dat de motivatie laag is na die opdracht.

Wat betreft dag 20, dat is nou juist iets wat je gewoon amper generiek kan oplossen. Je hebt een lading flip flops en een lading nand gates, effectief dus gewoon een state machine.

Bepalen of een state machine kan eindigen staat ook wel bekend als het halting problem, succes met daarvoor een generieke oplossing te verzinnen.

[MueR]

Remcoder schreef op donderdag 21 december 2023 @ 11:09:
[...]

Wat betreft dag 20, dat is nou juist iets wat je gewoon amper generiek kan oplossen. Je hebt een lading flip flops en een lading nand gates, effectief dus gewoon een state machine.

Bepalen of een state machine kan eindigen staat ook wel bekend als het halting problem, succes met daarvoor een generieke oplossing te verzinnen.

Het is ook een naar probleem ja (en een niet leuke opdracht voor AoC). En geen generieke oplossing voor. Maar zoals de puzzel beschrijft; de final machine heeft module 'RX' aabgeskiteb, Dus welke moduel dat is kan je prima programmatisch oplossen. En als je die weet kan je ook bepalen welke nodes daar naar linken. Hoeft niet hardcoded (behalve broadcaster en rx natuurlijk).

[Soultaker]

Remcoder schreef op donderdag 21 december 2023 @ 11:09:
Bepalen of een state machine kan eindigen staat ook wel bekend als het halting problem, succes met daarvoor een generieke oplossing te verzinnen.

Even mierenneuken: in dit specifieke geval is het wél beslisbaar omdat het invoerformaat niet Turing-compleet is. Je kunt gewoon stap-voor-stap te simuleren en stoppen wanneer rc een lage puls ontvangt óf een toestand zich herhaald. Het probleem daarmee in de praktijk is dat het veel te lang duurt, maar dat heeft niets met het halting problem te maken, wat gaat over theoretische berekenbaarheid.

[Marcj]

Ik zit ook nog met dag 20 deel 2 te klooien. Ik pak ook de "conjunctions" 2 stappen terug van rx, wat er 4 zijn. Dan doe ik de simulatie om te kijken wanneer deze hoog worden. Voor 2 van de 4 heb ik een resultaat binnen 10ms (rond de 4000 stappen elk), maar de andere 2 zie ik na een half uur wachten nog steeds nooit hoog worden. Ik heb al veel test cases bekeken, maar ik zie niet in waarom die van mij niet berekenbaar is.

Heeft iemand een andere input die ik eens kan testen? Zou het kunnen dat mijn input gewoon niet lekker is?

[Soultaker]

Marcj schreef op donderdag 21 december 2023 @ 11:56:
Heeft iemand een andere input die ik eens kan testen? Zou het kunnen dat mijn input gewoon niet lekker is?

Dit is de mijne: testdata/20.in

Je kunt ook je code delen, misschien kan iemand je dan een tip geven.

[Bolukan]

Post je input eens en welke 4 je volgt.

spoiler: day 21 part 2

De code van @Friits geeft me het juiste antwoord, maar ik kan de fout in mijn eigen berekening nog steeds niet vinden. Ik wacht wel tot vanavond dat Soultaker de uitleg geeft :-)
Ik kom op paar miljoen verschil als ik met 7.640,5 bereikbare plots per field reken, terwijl ik zelf op 7649 kom.
Mijn gedachte is dat je helemaal links (coordinaat 0,65) kan bereiken, wat je 4x75% oplevert, en dan nog 202.300 * 4 * 12,5% kleine schuine randstukjes en 202.299 * 4 * 87,5% grote stukken met een schuin randje. En natuurlijk heel veel complete velden.

[Bolukan]

Keek niet goed en nam @Soultaker's post als die van @Marcj
&kh -> rx

&pv -> kh
&qh -> kh
&xm -> kh
&hz -> kh

&tb -> sx, qn, vj, qq, sk, pv
&fl -> xv, tx, sl, df, qh, zc, zm
&kc -> zb, xp, pd, fc, xm
&hd -> hp, js, hz

Ok, en welke monitor je?

[ Voor 15% gewijzigd door Bolukan op 21-12-2023 12:10 ]

[Soultaker]

Bolukan schreef op donderdag 21 december 2023 @ 12:03:
Post je input eens en welke 4 je volgt.

spoiler: day 21 part 2

De code van @Friits geeft me het juiste antwoord, maar ik kan de fout in mijn eigen berekening nog steeds niet vinden. Ik wacht wel tot vanavond dat Soultaker de uitleg geeft :-)
Ik kom op paar miljoen verschil als ik met 7.640,5 bereikbare plots per field reken.
Mijn gedachte is dat je helemaal links (coordinaat 0,65) kan bereiken, wat je 4x75% oplevert, en dan nog 202.300 * 4 * 12,5% kleine schuine randstukjes en 202.299 * 4 * 87,5% grote stukken met een schuin randje. En natuurlijk heel veel complete velden.

@Marcj had het over dag 20 hè

Om de code van @Friits voor dag 21 te snappen moet je

spoiler:

heel goed naar het invoerbestand kijken, en daarbij ook naar het totaal aantal stappen, wat willekeurig gekozen lijkt, maar dat niet is.

Ik had het me zelf helemaal niet gerealiseerd dus heb ik een veel te ingewikkelde algemene oplossing bedacht die niet afhankelijk is van dit soort dingen.

Hint: als ik het invoerbestand in Visual Studio Code open dan spoilt de minimap de oplossing eigenlijk al.

[Marcj]

Thanks, die van Soultaker levert helemaal niks op. Ik ga nog even nadenken over stappen die ik kan doen. Mijn code is een beetje een rotzooitje omdat ik midden in experimenteren zit, dus nu jullie vragen gaat waarschijnlijk niet helpen. Misschien moet ik eerst mijn code maar even wat opschonen en dan verder kijken.

[Bolukan]

spoiler: day 21 part 2

O dat moet het zijn, the elf traversed door oneven en even velden, omdat het een oneven afmeting heeft.

[Bolukan]

spoiler:

Ben er uit. Ten eerste had ik die oneven/even telling er niet goed ingezet. Maar een tweede foutje:
Totaal omvang van een veld (131x131) minus totaal rocks (#) is niet gelijk aan reachable garden plots. Ik heb vier garden plots waar niet gewandeld kan worden.
##.
#.#
.#.

[Marcj]

Ok, ik had gewoon veel te moeilijk zitten doen. Ik heb een complete rewrite van dag 20 zitten doen die minder "premature optimisations" bevat. Dan is hij namelijk veel makkelijker te debuggen.... En hij werkte ineens direct! En die optimalisaties waren ook echt niet nodig, deel 2 berekent hij alsnog in 2ms.

Nu nog dag 21...

[Soultaker]

Extra test data voor dag 21:

aoc-2023-day-21-challenge-1.txt
aoc-2023-day-21-challenge-2.txt

Antwoorden voor deel 1 eindigen op: ...14, ...85.
Antwoorden voor deel 2 eindigen op: ...17164 en ...69701 (als mijn oplossing correct is!)

Om te helpen debuggen: de antwoorden voor deel 2 na 1000 stappen zijn: 753142 (challenge-1.txt) en 401242 (challenge-2.txt).

[ Voor 15% gewijzigd door Soultaker op 21-12-2023 19:22 ]

[.oisyn]

Wat, geen eens een challenge waarbij je delen van de grid alleen kunt bereiken dmv wrap-around?

[KabouterSuper]

.oisyn schreef op donderdag 21 december 2023 @ 10:19:
[...]

spoiler:

En daarbovenop nog eens: 131x131, 65 stappen naar de rand, en guess what... 26501365-65 is deelbaar door 131

spoiler:

En daarbovenop : het antwoord van die deling is honderd keer het jaartal van deze advent of code

[Soultaker]

.oisyn schreef op donderdag 21 december 2023 @ 15:05:
Wat, geen eens een challenge waarbij je delen van de grid alleen kunt bereiken dmv wrap-around?

Ik wilde lief zijn en het niet te ingewikkeld maken (Bovendien heb ik nog geen oplossing die daarvoor werkt.) Los eerst bovenstaande problemen maar eens op!

edit: overigens is dat niet heel moeilijk te construëren en toevallig werkt mijn oplossing hier nog net wel op:

...#.
...#.
..#..
##.S.
.....

Correcte antwoorden:

spoiler:

6
...90848

Je kunt het nog veel gekker maken, bijvoorbeeld zo:

#.#.#.#.#.#
#.#.#.#.#.#
#.#.#.#.#S#
#.#.#.#.###
..#.#.#.#..
###.#.#.#.#
##..#.#.#.#
#..#..#.#.#
#.#..#..#.#
#.#.#..#..#
#.#.#.#...#

Maar die kan ik zelf ook nog niet op lossen.

[ Voor 40% gewijzigd door Soultaker op 21-12-2023 16:59 ]

[.oisyn]

Ik heb het maar even q&d gedaan
Day21 in Rust
15926.4µs

spoiler:

Ik gebruik nu een 5x5 grid van fields en scan dan vanuit het middelste field met 2*width+start.x steps. Voor een generieke oplossing moet je even berekenen hoeveel fields en stappen je daadwerkelijk nodig hebt op basis van totaal aantal stappen, field grootte en startpositie, waarbij je ook rekening moet houden met het om-en-om effect bij oneven aantallen, dat omwisselt als STAPPEN/width oneven is. En dan hopen dat de fields lanks de randen van de ruit altijd gelijk zijn.

[ Voor 6% gewijzigd door .oisyn op 21-12-2023 16:30 ]

[Remcoder]

MueR schreef op donderdag 21 december 2023 @ 11:43:
[...]

Het is ook een naar probleem ja (en een niet leuke opdracht voor AoC). En geen generieke oplossing voor. Maar zoals de puzzel beschrijft; de final machine heeft module 'RX' aabgeskiteb, Dus welke moduel dat is kan je prima programmatisch oplossen. En als je die weet kan je ook bepalen welke nodes daar naar linken. Hoeft niet hardcoded (behalve broadcaster en rx natuurlijk).

Oh, je bedoelt dat mensen dus letterlijk in hun input gekeken hebben welke modules uiteindelijk rx voeden, en daarvan de cycle bepalen?

Dat heb ik dan inderdaad programmatisch redelijk generiek opgelost.

Zodra mijn code een onbekende module tegenkomt wordt die gewoon aangemaakt als terminatingmodule, iets wat gewoon input accepteert en kan teruggeven welke input er gezien is.

Dat wordt dus effectief de rx module, die haal ik dan op uit de Map van modules en daar bepaal ik de source van, van die source bepaal ik ook weer de sources (dat kunnen er dus meer of minder dan 4 zijn, ik had begrepen dat er mensen zijn waarbij de input meer dan 4 sources bevat). Van elke source bepaal ik dan wanneer die een een high fired, dan ff lcm daarop toepassen, en je hebt je antwoord

[FCA]

Pffff... op deel 2 van vandaag ben ik aardig natgegaan. Deel 1 was goed te doen, binnen een kwartier opgelost, maar deel 2....

spoiler:

Ik had het patroon snel door (na een aantal stappen gaat een kaart een 2-cykel in, en je hoeft alleen te kijken naar wanneer en waar je de eerste keer een kaart nieuw binnengaat).
Ook de subtiliteit van de "even" en de "oneven" aantal stappen goed ingezien, maar ik bleef hangen op het correct tellen van de even en oneven kaarten die in een cykel terecht waren gekomen, + tellen hoeveel er wel waren binnengegaan maar nog niet in een cykel zaten + bepalen hoeveel stappen ze in het proces zaten was een kloteklus.
Wel helemaal zelf opgelost, zonder dat werk er al te veel onder te lijden heeft gehad . En geen off-by-one errors in de eerste submissie, gewoon gelijk goed, dat geeft toch ook wel wat voldoening.
En whiteboard helemaal volgekalkt met partiele uitwerkingen, toch leuk om te doen

[Diderikdm]

Python dag 21

Zo dan zat wel even vast op p2..

spoiler:

Wist wat ik wilde doen, maar na het plotten van een 27 * 27 variant van de originele grid en eindeloos debuggen en haren trekken, had ik wel prima intervals en increments te pakken, maar.. had ik zowel mn even en odd omgedraaid, mn even en odd in dezelfde collection gestopt en zat ik verkeerd met m'n modulo's..

Na even van het scherm weg en het "simpelweg" binnen de queue te berekenen ipv een dict met tig steps lukte het gelukkig wel.

[Thorwing]

Soultaker schreef op donderdag 21 december 2023 @ 14:37:
Extra test data voor dag 21:

aoc-2023-day-21-challenge-1.txt
aoc-2023-day-21-challenge-2.txt

Antwoorden voor deel 1 eindigen op: ...14, ...85.
Antwoorden voor deel 2 eindigen op: ...17164 en ...69701 (als mijn oplossing correct is!)

interessant, ik krijg wel exact jouw oplossing bij challenge 2, maar niet bij challenge 1

[Soultaker]

Thorwing schreef op donderdag 21 december 2023 @ 19:16:
interessant, ik krijg wel exact jouw oplossing bij challenge 2, maar niet bij challenge 1

Uh-oh. Dan hebben we een derde partij nodig om te bepalen wie er fout zit.

(Zou best mijn code kunnen zijn, want het is niet de meest simpele.)

Na 1000 stappen zou je op 753142 moeten zitten (challenge 1 deel 2). Ik ben er iets meer van overtuigd dat dat klopt omdat ik dat nog kan bruteforcen.

[Thorwing]

Soultaker schreef op donderdag 21 december 2023 @ 19:21:
[...]
Na 1000 stappen zou je op 753142 moeten zitten (challenge 1 deel 2). Ik ben er iets meer van overtuigd dat dat klopt omdat ik dat nog kan bruteforcen.

Kijk, dat heb ik dan wel weer, dezelfde oplossing . Haha, maar ik moet ook eerlijk zeggen dat mijn oplossing niet werkt voor jouw 'hele moeilijke case' (elders in de thread) Mijn oplossing gaat er namelijk vanuit dat de set aan punten in de frontier vaker voor kan komen. En bij het vinden van 3 maak ik daar een quadratic formule voor.

code:

#.#.#.#.#.#
#.#.#.#.#.#
#.#.#.#.#S#
#.#.#.#.###
..#.#.#.#..
###.#.#.#.#
##..#.#.#.#
#..#..#.#.#
#.#..#..#.#
#.#.#..#..#
#.#.#.#...#

Hier vind ik helaas ook geen oplossing voor, op stap 5 zit een frontier van 3 punten die daarna nooit meer voorkomt, en daar breekt mijn code op.

[Asgardian28]

Friits schreef op donderdag 21 december 2023 @ 09:52:
Deel 1 was verdacht makkelijk, dus ik vreesde voor al een beetje deel 2. Uiteindelijk toch positie ~200 gehaald!

Python

@Friits Ben jij soms 4HbQ op reddit? Die heeft zo'n beetje dezelfde code. Zo ja, geniale code schrijf je. Zo nee, beter goed gejat dan slecht bedacht zullen we maar zeggen.

Ik ben vandaag 12 uur bezig geweest. Samen met Slam Salmon de moeilijkste ooit imo

[ Voor 11% gewijzigd door Asgardian28 op 21-12-2023 20:02 ]