Advent of Code 2023

[Soultaker]

FrankMennink schreef op dinsdag 12 december 2023 @ 13:09:

spoiler:

Uiteraard ook tegen de 1000000 vs 999999 aangelopen, off-by-1 errors Had wel al zo'n vermoeden dus kostte me een minuutje of te verifieren en dan wachten op de AoC cooldown

Checken jullie de voorbeeldinvoer niet? Uit de opgave:

In the example above, if each empty row or column were merely 10 times larger, the sum of the shortest paths between every pair of galaxies would be 1030. If each empty row or column were merely 100 times larger, the sum of the shortest paths between every pair of galaxies would be 8410.

Lijkt me dat je eventuele off-by-one errors hier al zou moeten detecteren.

(Ik weet dat ik ook niet altijd goed lees maar de gegeven test data check ik meestal wel.)

spoiler:

functools cache

Inderdaad, heel erg praktisch! Maar je kunt 'm ook eenvoudig zelf implementeren. Bijvoorbeeld zo:

Python:

def cache(f):
    memo = {}
    def g(*a):
        try:
            return memo[a]
        except KeyError:
            memo[a] = r = f(*a)
            return r
    return g

Of met iets betere performance:

Python:

def cache(f):
    memo = {}
    dummy = object()
    def g(*a):
        r = memo.get(a, dummy)
        if r is dummy:
            memo[a] = r = f(*a)
        return r
    return g

Overigens vind ik het ook mooi dat de meeste Python-programmeurs voor deel 2

spoiler:

het patroon hebben uitgepakt met'?'.join([s]*5)

Daar is in de meeste andere programmeertalen veel meer code voor nodig!

[FrankMennink]

Soultaker schreef op dinsdag 12 december 2023 @ 13:44:
[...]

Checken jullie de voorbeeldinvoer niet? Uit de opgave:

[...]

Lijkt me dat je eventuele off-by-one errors hier al zou moeten detecteren.

(Ik weet dat ik ook niet altijd goed lees maar de gegeven test data check ik meestal wel.)


[...]

Inderdaad, heel erg praktisch! Maar je kunt 'm ook eenvoudig zelf implementeren. Bijvoorbeeld zo:

Python:

def cache(f):
    memo = {}
    def g(*a):
        try:
            return memo[a]
        except KeyError:
            memo[a] = r = f(*a)
            return r
    return g

Of met iets betere performance:

Python:

def cache(f):
    memo = {}
    dummy = object()
    def g(*a):
        r = memo.get(a, dummy)
        if r is dummy:
            memo[a] = r = f(*a)
        return r
    return g

Overigens vind ik het ook mooi dat de meeste Python-programmeurs voor deel 2

spoiler:

het patroon hebben uitgepakt met'?'.join([s]*5)

Daar is in de meeste andere programmeertalen veel meer code voor nodig!

Meestal check ik die wel, maar in dit geval dacht ik oh dat kan ik gewoon zo vervangen, vervangen en hup submitten. Daarna met de voorbeeld input wel gauw de fout gevonden inderdaad Gevalletje luiheid/gemakzucht die in een fout antwoord uitmondde

[MatHack]

Soultaker schreef op dinsdag 12 december 2023 @ 13:44:
[...]

Checken jullie de voorbeeldinvoer niet? Uit de opgave:

[...]

Lijkt me dat je eventuele off-by-one errors hier al zou moeten detecteren.

(Ik weet dat ik ook niet altijd goed lees maar de gegeven test data check ik meestal wel.)

Ik wel in ieder geval, zeker voor dit soort gevallen is dat handig. Je kunt de data meestal ook relatief snel uit de tekst halen (testdata is meestal duidelijk en de output is met <em> omgeven en dus witter/vetter qua tekst). En de testset runt meestal lekker snel en is klein, dus als je evt. moet debuggen is dat ook overzichtelijk. Zeker omdat AoC een incremental timeout heeft op het invoerveld (eerst 1 minuut wachten indien foute invoer, dan 2, etc.) is het fijner om wat zekerder van je antwoord te zijn.

[FCA]

Deel 1 redelijk snel te pakken, deel 2 kostte wat meer denkwerk. Uiteindelijk tijdens een meeting het juiste idee te pakken (yeah boor thuiswerken ), en toen in 10 monuutjes geimplementeerd.

spoiler:

deel 1 brute force met bit fiddling (ofzo, door binaire mogelijkheden lopen), was wel duidelijk dat het niet ging werken voor deel 2.
Deel 2 de "standaard" Python oplossing, recursief + memoization, van links naar rechts, checken of het past

[.oisyn]

Even snel wat optimalisaties doorgevoerd: 4,5ms. Dat lijkt er meer op

spoiler:

Algoritmisch is hij bijna identiek, het is vooral een optimalisatie van de key van de gebruikte hashmap + het hergebruiken van de hashmap's buffer. Ik zeg bijna identiek, want ik hergebruik de hashmap voor stap 2, wat betekent dat hij een klein deel niet opnieuw hoeft te doen omdat dat al in stap 1 is gebeurd. Maar dat was maar een halve ms. De andere optimize ging van 36ms naar 5ms

[Remcoder]

spoiler:

Sodeju, ik had veel tijd nodig om een werkend algorithme te krijgen.

Ik had eerst de test input werkend, maar die ging mis met de volledige input, daarna op reddit een voorbeeld input gevonden die ook bij mij faalde.

Die gaan fixen, toen faalde de voorbeeld input weer, uiteindelijk heb ik het een stuk of 4x opnieuw geschreven tot een werkende oplossing.

Voor deel 2 was het daarna appeltje eitje, door de pattern te vergroten en memoisation toe te voegen.

Ik zie net wel het voordeel van de optimizations die de JVM kan toepassen, als ik alleen de grote input draai voor deel 2 doet die er ~140 ms over, draai ik alle voorbeeld inputs die ik had gemaakt met de grote input op het einde doet die deel 2 in ~85 ms.

[eheijnen]

Ik heb alleen eens zitten kijken naar dag 12 en vroeg me af of je zo'n probleemstelling ook in de dagelijkse praktijk tegenkomt?

[Diderikdm]

Python

Deel 1 eerst ge-bruteforced maar vermoedde wel iets dergelijks voor part 2.

[Varienaja]

eheijnen schreef op dinsdag 12 december 2023 @ 17:38:
Ik heb alleen eens zitten kijken naar dag 12 en vroeg me af of je zo'n probleemstelling ook in de dagelijkse praktijk tegenkomt?

Ik kan me voorstellen dat mijn collega's, die de personeelsplanning optimaliseren onder voorbehoud van inachtneming van (o.a.) de rusttijden zulk soort dingen doen.

[Varienaja]

Aargh crap. Testinvoer goed, echte invoer niet.

Ha. Eindelijk. Happy debugging allemaal :-P

Dag 13 in Java Mijn brute force steekt wel een beetje af tegen @Soultaker's mooie oplossing .

[ Voor 87% gewijzigd door Varienaja op 13-12-2023 12:07 ]

[FCA]

En weer top 1000 een keertje
Als ik nog eens keer top 100 wil halen moet ik wel mijn flow wat verbeteren, en wat meer first time right typen.

spoiler:

python +numpy voelde wel als cheatmode dit keer, hoefde voor deel 2 een enkele check aan te passen.

[Soultaker]

Geen heel geweldige dag voor mij: ik heb 20 minuten zitten pielen met input parsen. Daarna deel 2 wel in ~1 minuut opgelost:

spoiler:

Deel 2 is erg makkelijk als je i.p.v. te checken of de symmetrische delen gelijk zijn, simpelweg het aantal fouten telt (i.e. het aantal posities waarbij het punt en z'n reflectie niet overeenkomen). Dan tel je bij deel 1 simpelweg de lijnen met exact 0 fouten, en bij deel 2 met exact 1 fout.

Python code

[P_Tingen]

Lief dagboek,

Opgave 12, deel a was leuk en had ik relatief snel opgelost. Beetje binair fiddelen, beetje debuggen want recursief (altijd lastig), maar toen ik deel B las, had ik al door dat mijn programma daarvoor niet ging werken, alleen al die voor deel A ook al een paar minuten nodig had.

Ik had je toch al verteld, lief dagboek, dat mijn ontwikkeltaal een 4GL is, en niet speciaal gericht op supersnel uitvoeren? Het is geen python of C# of zo. Maar goed, ik dacht dus dat de AoC opgaven ook te doen moesten zijn op ouwe-meuk-computers. En nou lees ik dat iedereen deel B oplost met iets moderns als memoization. Maar dat heb ik helemaal niet! Moet ik nou mijn computer een half jaar laten stampen of zal ik deze maar laten voor wat het is? Of moet ik eerst nog wat IQ tanken voor een slimme oplossing?

liefs, ik

[Remcoder]

P_Tingen schreef op woensdag 13 december 2023 @ 10:00:
Lief dagboek,

Opgave 12, deel a was leuk en had ik relatief snel opgelost. Beetje binair fiddelen, beetje debuggen want recursief (altijd lastig), maar toen ik deel B las, had ik al door dat mijn programma daarvoor niet ging werken, alleen al die voor deel A ook al een paar minuten nodig had.

Ik had je toch al verteld, lief dagboek, dat mijn ontwikkeltaal een 4GL is, en niet speciaal gericht op supersnel uitvoeren? Het is geen python of C# of zo. Maar goed, ik dacht dus dat de AoC opgaven ook te doen moesten zijn op ouwe-meuk-computers. En nou lees ik dat iedereen deel B oplost met iets moderns als memoization. Maar dat heb ik helemaal niet! Moet ik nou mijn computer een half jaar laten stampen of zal ik deze maar laten voor wat het is? Of moet ik eerst nog wat IQ tanken voor een slimme oplossing?

liefs, ik

Memoization is toch in principe niets meer dan het bijhouden van een lookup table?

Kun je die niet in een 4GL taal maken dan?

[.oisyn]

Het lijkt me idd stug dat een 4GL niet zoiets standaards als een geassocieerde datastructuur heeft

[P_Tingen]

Ik vermoed dat ik jullie moet teleurstellen, voor zover ik weet zit het er niet in. Ik kan zelf een soort van functie-cache namaken, maar ook dat zal matig performen

[.oisyn]

@P_Tingen Hoe heet jouw taal?

En een simpele array is hier al voldoende. Voor deel 2 is de maximale pattern geloof ik 104 lang, en heb je maximaal 20 spans, dus je hebt hooguit een array van 2080 entries nodig.

[P_Tingen]

Progress 4GL, ja die kan wel zo'n array aan

[ Voor 56% gewijzigd door P_Tingen op 13-12-2023 10:32 ]

[.oisyn]

Zonder geassocieerde datastructuur, hoe kun je dan ooit een applicatie maken waarin je zoiets simpels als de adresgegevens van een persoon opzoekt op basis van zijn naam oid?

[P_Tingen]

Wellicht heb ik een verkeerde oplossingsrichting, dat kan ook natuurlijk
https://github.com/patric...ter/2023/Day-12/day-12a.p

[Remcoder]

Progress gebruikt volgens wiki een interne database.

Dan kan je daar toch een tabel in maken voor je memoization?

[Corniel]

Ik doe al sinds 2020 mee, maar had met tot zover niet aangemeld. Bij deze wel. Ik doe het in C# en mijn repo is hier te vinden: https://github.com/Corniel/advent-of-code

Gisteren was k#t, maar het is gelukt...

[P_Tingen]

Remcoder schreef op woensdag 13 december 2023 @ 10:47:
Progress gebruikt volgens wiki een interne database.
Dan kan je daar toch een tabel in maken voor je memoization?

Ja, ik kan een soort pseudo-tabel maken in geheugen en die gebruiken, compleet met indexen

[Soultaker]

P_Tingen schreef op woensdag 13 december 2023 @ 10:00:
En nou lees ik dat iedereen deel B oplost met iets moderns als memoization. Maar dat heb ik helemaal niet!

Een dynamic programming oplossing gebaseerd op recursie kun je ook altijd iteratief schrijven. Voorbeeld: solve-dp.py (bijkomend voordeel: dit is een van de weinige oplossingen die gegarandeerd in O(NM) tijd draait, met N en M de lengte van het patroon en het aantal nummers in de lijst respectievelijk).

.oisyn schreef op woensdag 13 december 2023 @ 10:29:
En een simpele array is hier al voldoende. Voor deel 2 is de maximale pattern geloof ik 104 lang, en heb je maximaal 20 spans, dus je hebt hooguit een array van 2080 entries nodig.

Technisch heb je hooguit O(N) geheugen nodig. Twee arrays van lengte 104 volstaan bijvoorbeeld. Maar een array van 2080 is simpeler als je gewoon de recursieve implementatie wil cachen.

[Diderikdm]

Python

Leuk dagje vandaag

spoiler:

Zat wel even te priegelen bij deel twee.. Je hoeft natuurlijk alleen de nieuwe reflecties op te tellen

[P_Tingen]

Soultaker schreef op woensdag 13 december 2023 @ 11:49:
[...]
Een dynamic programming oplossing gebaseerd op recursie kun je ook altijd iteratief schrijven. Voorbeeld: solve-dp.py

Dank! Ik zit deze te bestuderen (daarom vind ik AoC zo leuk; je kan weer eens wat bijleren*) maar mijn Python is niet optimaal, want wat doet dit:

code:

if s[j] != '#':
  dp[i + 1][j + 1] = dp[i + 1][j] + (n <= max_hashes[j] and dp[i][j - n])

Het deel tussen haakjes ziet er voor mij nml uit als een logische expressie. Ik lees het als:

code:

als s[j] ongelijk is aan "#" dan
   zet dp[i + 1][j + i] op dp[i + 1][j] en tel er nog iets bij op, namelijk: .......
    (als N <= max_hashes[j] EN dp[i][j - n] <> 0 dan 1 anders 0)

of moet ik dit anders lezen?

* en tegelijk zo frustrerend als je je met je bakken ervaring weer een beginner voelt....

[Diderikdm]

P_Tingen schreef op woensdag 13 december 2023 @ 13:22:
[...]

Dank! Ik zit deze te bestuderen (daarom vind ik AoC zo leuk; je kan weer eens wat bijleren*) maar mijn Python is niet optimaal, want wat doet dit:

code:

if s[j] != '#':
  dp[i + 1][j + 1] = dp[i + 1][j] + (n <= max_hashes[j] and dp[i][j - n])

Het deel tussen haakjes ziet er voor mij nml uit als een logische expressie. Ik lees het als:

code:

als s[j] ongelijk is aan "#" dan
   zet dp[i + 1][j + i] op dp[i + 1][j] en tel er nog iets bij op, namelijk: .......
    (als N <= max_hashes[j] EN dp[i][j - n] <> 0 dan 1 anders 0)

of moet ik dit anders lezen?

* en tegelijk zo frustrerend als je je met je bakken ervaring weer een beginner voelt....

De boolean klopt, in Python kun je een boolean optellen bij een getal.

(and dp[i][j - n]) vergelijkt de waarde van het object dp[i][j - n] met de nulwaarde voor dit type object (int: 0, str: "", list: [], etc.) en geeft een boolean terug, dus idd dp[i][j - n] != 0 in dit geval.

maar dan:

zet dp[i + 1][j] + (True (1)/False (0)) op dp[i + 1][j + 1]

[ Voor 18% gewijzigd door Diderikdm op 13-12-2023 13:37 ]

[Remcoder]

spoiler:

Mmh, de inputs van vandaag zijn zo gemaakt dat je altijd maar in 1 richting een mirroring hebt, en niet in 2 richtingen.

Mijn code werkt dus wel voor de officiele input voor deel 2, maar gaat waarschijnlijk stuk zodra je 2 plekken hebt waar je een smudge weg kan halen, bij de ene smudge krijg je dan een nieuwe mirror in horizontale richting, en bij de andere smudge krijg je dan een mirror in verticale richting.

Die state is dan ook niet gedefinieerd hoe je dan bepaalt welke smudge je zou moeten weghalen, en welke score je dan moet berekenen.

Als toevoeging daarop zou je dan kunnen bepalen welke smudge de beste score geeft.

[Stevie-P]

Remcoder schreef op woensdag 13 december 2023 @ 13:58:

spoiler:

Mmh, de inputs van vandaag zijn zo gemaakt dat je altijd maar in 1 richting een mirroring hebt, en niet in 2 richtingen.

Mijn code werkt dus wel voor de officiele input voor deel 2, maar gaat waarschijnlijk stuk zodra je 2 plekken hebt waar je een smudge weg kan halen, bij de ene smudge krijg je dan een nieuwe mirror in horizontale richting, en bij de andere smudge krijg je dan een mirror in verticale richting.

Die state is dan ook niet gedefinieerd hoe je dan bepaalt welke smudge je zou moeten weghalen, en welke score je dan moet berekenen.

Als toevoeging daarop zou je dan kunnen bepalen welke smudge de beste score geeft.

spoiler:

Er staat ook niet gespecificeerd hoe je met de situatie om zou moeten gaan als er meerder smudges zijn.
Ik ben zo lui geweest het maar in 1 richting in te bouwen; het detecteren van de smudge en het aantal regels boven de spiegel te bepalen. Vervolgens transpose ik het patroon en doe ik het nog een keer.

[Mugwump]

Oplossing in Kotlin: https://github.com/robobd.../src/main/kotlin/Day13.kt

spoiler:

Loop een beetje te klooien de laatste dagen vanwege drukte, dus vandaag maar even simpel gehouden voor mezelf aangezien performance geen issue was hier.

Gewoon een List of strings en dan lines boven en onder vergelijken op aantal verschillen, 0 voor deel 1 en 1 voor deel 2.
Voor links / rechts domweg een transpose en dan bovenstaand trucje herhalen.
Even bepalen hoeveel rijen ik moet pakken kan nog veel eleganter met slices waarvoor ik even de ranges moet bepalen, maar dit werkt zullen we maar zeggen.

[DataGhost]

Remcoder schreef op woensdag 13 december 2023 @ 13:58:

spoiler:

Mmh, de inputs van vandaag zijn zo gemaakt dat je altijd maar in 1 richting een mirroring hebt, en niet in 2 richtingen.

Mijn code werkt dus wel voor de officiele input voor deel 2, maar gaat waarschijnlijk stuk zodra je 2 plekken hebt waar je een smudge weg kan halen, bij de ene smudge krijg je dan een nieuwe mirror in horizontale richting, en bij de andere smudge krijg je dan een mirror in verticale richting.

Die state is dan ook niet gedefinieerd hoe je dan bepaalt welke smudge je zou moeten weghalen, en welke score je dan moet berekenen.

Als toevoeging daarop zou je dan kunnen bepalen welke smudge de beste score geeft.

In de probleemomschrijving staat

spoiler:

exactly one smudge

dus daar mag je vanuit gaan. Al het andere is niet gedefinieerd en zal je ook niet tegenkomen.

Verder staat er natuurlijk in de opgave dat je

spoiler:

de spiegels niet kan zien, dus als je denkt een spiegel gevonden te hebben betekent dat niet dat dat zo is, het terrein kan er gewoon zo uitzien zodat het lijkt dat je die gevonden hebt. Dus de echte spiegel vind je pas in deel twee.

[ Voor 13% gewijzigd door DataGhost op 13-12-2023 14:23 ]

[Diderikdm]

Remcoder schreef op woensdag 13 december 2023 @ 13:58:

spoiler:

Mmh, de inputs van vandaag zijn zo gemaakt dat je altijd maar in 1 richting een mirroring hebt, en niet in 2 richtingen.

Mijn code werkt dus wel voor de officiele input voor deel 2, maar gaat waarschijnlijk stuk zodra je 2 plekken hebt waar je een smudge weg kan halen, bij de ene smudge krijg je dan een nieuwe mirror in horizontale richting, en bij de andere smudge krijg je dan een mirror in verticale richting.

Die state is dan ook niet gedefinieerd hoe je dan bepaalt welke smudge je zou moeten weghalen, en welke score je dan moet berekenen.

Als toevoeging daarop zou je dan kunnen bepalen welke smudge de beste score geeft.

spoiler:

Het staat er wel, maar het had wel duidelijker gekund, ik moest ook een paar keer lezen voor ik het helemaal snapte.

"""
In each pattern, you'll need to locate and fix the smudge that causes a different reflection line to be valid. (The old reflection line won't necessarily continue being valid after the smudge is fixed.)

...

In each pattern, fix the smudge and find the different line of reflection. What number do you get after summarizing the new reflection line in each pattern in your notes?
"""

[KabouterSuper]

Ik ben vandaag iets te grof bezig geweest, maar er was gelukkig maar één geval waar het fout ging.

spoiler:

In deel 1 ga ik op zoek naar lijnen waarbij alle relevante rijen of kolommen goed gespiegeld worden.
In deel 2 probeer ik niet eens op zoek te gaan naar de smudge, maar zoek ik naar lijnen waar bijna alle relevante rijen of kolommen goed gespiegeld worden (ik laat één foute spiegeling toe). Er zit in mijn dataset maar één geval waarbij dit zowel een 'valide' verticale als horizontale spiegeling oplevert. Met een visuele inspectie zag ik snel welke van de twee fout was.

[RefleXion]

Ik heb een oplossing geschreven in python die in principe zou moeten werken voor elke unieke hoeveelheid smudges.

spoiler:

# Find horizontal mirror with smudge:
for x in range(1,grid_size[0]):
reflection_size = min(x,grid_size[0]-x)

left = grid_array[x-reflection_size:x,:]
right = grid_array[x:x+reflection_size,:]

if np.logical_xor(left,right[::-1]).sum() == 1:
print("Horizontal mirror at X=",x)
solution += x

# Find vertical mirror with smudge:
for y in range(1,grid_size[1]):
reflection_size = min(y,grid_size[1]-y)

top = grid_array[:,y-reflection_size:y]
bottom = grid_array[:,y:y+reflection_size]

if np.logical_xor(top,bottom[:,::-1]).sum() == 1:
print("Vertical mirror at Y=",y)
solution += y * 100

[Soultaker]

P_Tingen schreef op woensdag 13 december 2023 @ 13:22:
Wat doet dit:

code:

if s[j] != '#':
  dp[i + 1][j + 1] = dp[i + 1][j] + (n <= max_hashes[j] and dp[i][j - n])

Het deel tussen haakjes ziet er voor mij nml uit als een logische expressie. Ik lees het als:

code:

als s[j] ongelijk is aan "#" dan
   zet dp[i + 1][j + i] op dp[i + 1][j] en tel er nog iets bij op, namelijk: .......
    (als N <= max_hashes[j] EN dp[i][j - n] <> 0 dan 1 anders 0)

of moet ik dit anders lezen?

Dat is inderdaad een beetje obscuur geformuleerd, sorry. De manier waarop de and-operator werkt in Python (en ook b.v. in JavaScript) is a and b evalueert naar a als a False is in Boolean context, en anders b. Dus als de operands geen Booleans zijn is het resultaat dat ook niet. Voorbeeld:

Python:

print(123 and 'bla')   # print "bla", want bool(123) == True
print([] and 456)      # print [], want bool([]) == False

Ik gebruik and hier als conditionele expressie, en maak gebruik van het feit dat False gelijk is aan 0 wat optellen betreft. Je moet het dus interpreteren als "als n <= max_hashes[j] dan dp[i][j - n] anders 0". In een C-like taal zou je het schrijven als: n <= max_hashes[j] ? dp[i][j - n] : 0 (in Python kun je ook schrijven: dp[i][j - n] if n <= max_hashes[j] else 0).

Diderikdm schreef op woensdag 13 december 2023 @ 13:29:
De boolean klopt, in Python kun je een boolean optellen bij een getal.

Sterker nog, een Boolean is een getal. bool is een subtype van int:

Python:

print(type(True))  # <class 'bool'>
print(type(1))     # <class 'int'>
print(isinstance(True, int))  # True (True is een int)
print(isinstance(1, bool))    #  False (1 is geen bool)
print(1 == True)   # True (1 is gelijk aan True)
print(1 is True)   # False (1 is niet hetzelfde object als True)
print(1 + True)    # 2

[eheijnen]

Deze vind ik toch wel het mooiste

code:

print(1 + True)    # 2

[Friits]

Voor de liefhebbers weer mijn oplossing voor vandaag.

Nog niet helemaal tevreden, maar ik ben op een vreemd optimum tussen leesbaar en compact beland.

Dit probeerseltje is wat compacter, maar misschien weer iets te veel "trucjes"...

[ Voor 29% gewijzigd door Friits op 13-12-2023 17:35 ]

[MatHack]

Eindelijk tijd om vandaag op te lossen. Hier ook brute force opgelost, was maar 40ms voor deel 2.

Maar ik had hetzelfde als @Varienaja bij deel 2: Testinvoer werkt, echte invoer niet (too low). Kleine debug liet me als snel weten waar het probleem zat. Vermoed zo dat we hetzelfde probleem hadden...

spoiler:

Ik testte of de nieuwe mirror hetzelfde was als de oude nadat ik de mirror had bepaald voor een smudge. Maar er werd bij sommige invoer altijd eerst de oude mirror gevonden. Ik vond dus nooit de nieuwe mirror. Dus die check maar verplaatst naar de FindMirror methode ipv de FindSmudge methode.

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

[FrankMennink]

Day 13 in Python

leuke puzzel vandaag, ik dacht slim te zijn maar dat ging mis met deel 2 dus maar omgebouwd naar deze methode. Daarna ook nog even een leuk Python (semi)one-liner gedrocht van gebakken kan vast nog meer op 1 regel maar is wel genoeg voor nu

spoiler:

Had eerst het lumineuze idee om alles te converteren naar een int (#=1, .=0, dan binair omrekenen), daarna linkerhelft en rechterhelft van de window gesommeerd en gekeken of die hetzelfde zijn. Ging op de test input als een trein, zat in de echte input alleen een patroon in waarbij er 2 sommen hetzelfde waren dus daar ging ik nat.

Dat iets aangepast dat ie checkt of alle nummers links gelijk zijn aan de reversed rechterhelft en zo ja de huidige regel teruggeven. Hoera, dat werkt. Toen kwam deel twee... en had ik niks aan mijn "slimme" conversie naar integers want ik moest weten hoeveel posities verschilden. Maar weer omgebouwd en zo kon ik de code hergebruiken waarbij ik enkel een 0 of een 1 als target mee hoef te geven voor het aantal verschillen voor deel 1 en 2.

[Daanoz]

FrankMennink schreef op woensdag 13 december 2023 @ 21:17:

spoiler:

Had eerst het lumineuze idee om alles te converteren naar een int (#=1, .=0, dan binair omrekenen), daarna linkerhelft en rechterhelft van de window gesommeerd en gekeken of die hetzelfde zijn. Ging op de test input als een trein, zat in de echte input alleen een patroon in waarbij er 2 sommen hetzelfde waren dus daar ging ik nat.

Dat iets aangepast dat ie checkt of alle nummers links gelijk zijn aan de reversed rechterhelft en zo ja de huidige regel teruggeven. Hoera, dat werkt. Toen kwam deel twee... en had ik niks aan mijn "slimme" conversie naar integers want ik moest weten hoeveel posities verschilden. Maar weer omgebouwd en zo kon ik de code hergebruiken waarbij ik enkel een 0 of een 1 als target mee hoef te geven voor het aantal verschillen voor deel 1 en 2.

spoiler:

Voor deel 1 precies hetzelfde gedaan, maar ik heb het wel kunnen gebruiken voor deel 2... Het enige wat je dan nog hoeft te checken hoeveel bits er verschil zit tussen je Ints... Zodra het meer als 1 is kan je de set negeren.

[Corniel]

Op mijn werk doen er dit jaar 24 collega's mee (meer dan de helf is wel inmddels afgehaakt denk ik). Aan het eind van het jaar krijgen de besten vanuit HR ook een kleine prijs. Maar omdat de ranking nogal unfair is als er veel mensen afhaken, omdat dit mensen beloond die in wel is waar niet heel goed zijn, maar de eerste opgaven snel af hadden (lees tering vroeg opstonden). Ook kan de ranglijst dan veranderen als er mensen zich aanmelden die geen enkele puzzel afronden.

Sowieso denk ik dat het beter is als het aantal goede oplossingen gaat voor hoe snel je ze oplost. Enfin, Daar heb ik iets voor geschreven, en e.a. ook op de Tweakers lijst opgemaakt. Ik toon hier enkel de top-10.

Merk op dat de eerste 9 per onderdeel als zodanig in de colomnen zijn terug te vinden, en dat de overigen een + krijgen. (Ik zag ook de AoC-plugin voorbijkomen, een aantal van mijn collega's gebruikt die ook). Ik ga dit zeker niet elke dag doen, maar het leek me toch wel aardig het eenmalig te delen.

code:

| Pos |   Score |0102030405|0607080910|111213|  Rank | Participant         |      Last solved |
|----:|--------:|----------|----------|------|------:|---------------------|------------------|
|   1 | 26.2400 |3132222221|4411111121|111121|  1.69 | Maks Verver         | 2023-12-13 05:23 |
|   2 | 26.2384 |1211111112|1132735412|333253|  2.31 | Jasper van Merle    | 2023-12-13 05:31 |
|   3 | 26.2320 |[phone]|225422333+|2+5974|  4.77 | Jesse van Elteren   | 2023-12-13 06:01 |
|   4 | 26.2229 |79++8+4648|33233+22+8|942586|  8.27 | Michael de Kaste    | 2023-12-13 06:06 |
|   5 | 26.2221 |6855458+6+|+94+4+45++|426+9+|  8.58 | Sebastian Dehne     | 2023-12-13 06:29 |
|   6 | 26.2138 |53++++97++|57++++++++|687+12| 11.77 | janjitse            | 2023-12-13 05:24 |
|   7 | 26.2080 |++++++6553|656554++++|++8335| 14.00 | Varienaja           | 2023-12-13 06:03 |
|   8 | 26.2074 |4+++9978++|++++++++7+|7+4+48| 14.23 | Corniel Nobel       | 2023-12-13 06:16 |
|   9 | 26.2067 |++76++++++|8+++++98+7|++++++| 14.50 | Otto Erkelens       | 2023-12-13 12:37 |
|  10 | 26.2060 |+++++++++4|+++7++++9+|+997++| 14.77 | PhiliPdB            | 2023-12-13 10:11 |

[.oisyn]

FrankMennink schreef op woensdag 13 december 2023 @ 21:17:

spoiler:

Dat iets aangepast dat ie checkt of alle nummers links gelijk zijn aan de reversed rechterhelft en zo ja de huidige regel teruggeven. Hoera, dat werkt. Toen kwam deel twee... en had ik niks aan mijn "slimme" conversie naar integers want ik moest weten hoeveel posities verschilden.

spoiler:

Ten eerste klopt dat niet, ten tweede kan dat alsnog

Je hoeft het <aantal> veschillen niet te weten, je hoeft alleen te weten of het verschil 0, 1 of meer bits is. Als je de twee waarden met elkaar XORt, dan krijg je een int met alleen 1'en waar ze verschillen. Testen of dat 0 bits zijn, kan met x == 0. Testen of er maar 1 bit aan staat, kan met (x & (x - 1)) == 0

Het aantal bits wil je dus niet weten, maar ook daar is vaak wel een functie voor die dat terug kan geven. C++ en Rust hebben die (resp. std::pop_count(x) en x.count_ones()), maar anders kun je wel een efficiente implementatie hiervandaan halen

[.oisyn]

Day13 in Rust

Kan 'm alleen niet compilen in release want de optimizer borked met STATUS_ILLEGAL_INSTRUCTION
Maar goed, debug runt wel, in 1 ms tijd.

Uiteindelijk is de meeste tijd gaan zitten in een generieke 2d array view implementatie die je toch steeds weer nodig hebt . Eentje die ook over de kolommen kan itereren, terwijl die elementen niet contiguous in geheugen staan. Ik had geen zin om een random crate naar binnen te trekken en ik vond dit een leuke oefening.

.edit: Ok, dat was met Rust 1.72.1. Op de laatste versie, 1.74.1, compilet het wel
Time spent: 125.9µs

[ Voor 50% gewijzigd door .oisyn op 14-12-2023 00:02 ]

[DataGhost]

Corniel schreef op woensdag 13 december 2023 @ 22:35:
Op mijn werk doen er dit jaar 24 collega's mee (meer dan de helf is wel inmddels afgehaakt denk ik). Aan het eind van het jaar krijgen de besten vanuit HR ook een kleine prijs. Maar omdat de ranking nogal unfair is als er veel mensen afhaken, omdat dit mensen beloond die in wel is waar niet heel goed zijn, maar de eerste opgaven snel af hadden (lees tering vroeg opstonden). Ook kan de ranglijst dan veranderen als er mensen zich aanmelden die geen enkele puzzel afronden.

Sowieso denk ik dat het beter is als het aantal goede oplossingen gaat voor hoe snel je ze oplost. Enfin, Daar heb ik iets voor geschreven, en e.a. ook op de Tweakers lijst opgemaakt. Ik toon hier enkel de top-10.

Merk op dat de eerste 9 per onderdeel als zodanig in de colomnen zijn terug te vinden, en dat de overigen een + krijgen. (Ik zag ook de AoC-plugin voorbijkomen, een aantal van mijn collega's gebruikt die ook). Ik ga dit zeker niet elke dag doen, maar het leek me toch wel aardig het eenmalig te delen.

code:

| Pos |   Score |0102030405|0607080910|111213|  Rank | Participant         |      Last solved |
|----:|--------:|----------|----------|------|------:|---------------------|------------------|
|   1 | 26.2400 |3132222221|4411111121|111121|  1.69 | Maks Verver         | 2023-12-13 05:23 |
|   2 | 26.2384 |1211111112|1132735412|333253|  2.31 | Jasper van Merle    | 2023-12-13 05:31 |
|   3 | 26.2320 |[phone]|225422333+|2+5974|  4.77 | Jesse van Elteren   | 2023-12-13 06:01 |
|   4 | 26.2229 |79++8+4648|33233+22+8|942586|  8.27 | Michael de Kaste    | 2023-12-13 06:06 |
|   5 | 26.2221 |6855458+6+|+94+4+45++|426+9+|  8.58 | Sebastian Dehne     | 2023-12-13 06:29 |
|   6 | 26.2138 |53++++97++|57++++++++|687+12| 11.77 | janjitse            | 2023-12-13 05:24 |
|   7 | 26.2080 |++++++6553|656554++++|++8335| 14.00 | Varienaja           | 2023-12-13 06:03 |
|   8 | 26.2074 |4+++9978++|++++++++7+|7+4+48| 14.23 | Corniel Nobel       | 2023-12-13 06:16 |
|   9 | 26.2067 |++76++++++|8+++++98+7|++++++| 14.50 | Otto Erkelens       | 2023-12-13 12:37 |
|  10 | 26.2060 |+++++++++4|+++7++++9+|+997++| 14.77 | PhiliPdB            | 2023-12-13 10:11 |

Zoek je niet gewoon ordering by stars? https://adventofcode.com/...e/view/293342?order=stars

[Mugwump]

Ik vind het wedstrijdelement sowieso niet echt boeiend. Ik doe dit gewoon om eens wat met een nieuwe taal te spelen en omdat het best nuttig is om eens weer wat meer algoritmisch werk te doen, want dat doe ik echt vrijwel nooit meer.

Denk dat het ook zinvoller is om op specifieke aspecten te scoren, dus b.v. het high performance segment voor oplossingen die de snelste executietijden halen of iets dergelijks.

[Corniel]

DataGhost schreef op woensdag 13 december 2023 @ 23:56:
[...]

Zoek je niet gewoon ordering by stars? https://adventofcode.com/...e/view/293342?order=stars

Dat is in die vorm toch wat beperkter. Verder kan ik mijn mijn eigen tooling ook private lijsten delen. Het is een typisch geval van: leuk om te schrijven, en meer data.

[Soultaker]

Dag 14:
Mijn oorspronkelijke implementatie was nogal ad-hoc (code). Daarna heb ik het wat algemener gemaakt (code), maar het is jammer dat de algemene code niet per se leesbaarder is (en sowieso lastiger om te schrijven).

[Soultaker]

Corniel schreef op woensdag 13 december 2023 @ 22:35:
Merk op dat de eerste 9 per onderdeel als zodanig in de colomnen zijn terug te vinden, en dat de overigen een + krijgen. (Ik zag ook de AoC-plugin voorbijkomen, een aantal van mijn collega's gebruikt die ook). Ik ga dit zeker niet elke dag doen, maar het leek me toch wel aardig het eenmalig te delen.

code:

| Pos |   Score |0102030405|0607080910|111213|  Rank | Participant         |      Last solved |
|----:|--------:|----------|----------|------|------:|---------------------|------------------|
|   1 | 26.2400 |3132222221|4411111121|111121|  1.69 | Maks Verver         | 2023-12-13 05:23 |
|   2 | 26.2384 |1211111112|1132735412|333253|  2.31 | Jasper van Merle    | 2023-12-13 05:31 |
|   3 | 26.2320 |[phone]|225422333+|2+5974|  4.77 | Jesse van Elteren   | 2023-12-13 06:01 |
|   4 | 26.2229 |79++8+4648|33233+22+8|942586|  8.27 | Michael de Kaste    | 2023-12-13 06:06 |
|   5 | 26.2221 |6855458+6+|+94+4+45++|426+9+|  8.58 | Sebastian Dehne     | 2023-12-13 06:29 |
|   6 | 26.2138 |53++++97++|57++++++++|687+12| 11.77 | janjitse            | 2023-12-13 05:24 |
|   7 | 26.2080 |++++++6553|656554++++|++8335| 14.00 | Varienaja           | 2023-12-13 06:03 |
|   8 | 26.2074 |4+++9978++|++++++++7+|7+4+48| 14.23 | Corniel Nobel       | 2023-12-13 06:16 |
|   9 | 26.2067 |++76++++++|8+++++98+7|++++++| 14.50 | Otto Erkelens       | 2023-12-13 12:37 |
|  10 | 26.2060 |+++++++++4|+++7++++9+|+997++| 14.77 | PhiliPdB            | 2023-12-13 10:11 |

Interessant, maar de top 10 komt nu precies overeen met de top 10 op het officiële leaderboard.

Ik ben het wel met je eens dat het officiële scoresysteem wat nadelen heeft. Bijvoorbeeld dat als iemand je 1 seconde voor is op deel 1, en jij vervolgens een half uur eerder bent met deel 2, dat je dan op dezelfde score uitkomt. Of dat als je 1 dag niet meedoet je meteen 200 punten verliest (waarvan je er hooguit ~100 in kunt halen).

Hoe kom je aan die extra data per dag trouwens? Heeft de API toegang tot meer data dan beschikbaar in het leaderboard zelf getoond wordt?

[Mugwump]

Deel 1 even in een paar minuten tussendoor kunnen doen, dat was een eitje.
Deel 2 hoeft ook niet moeilijk te zijn, maar daar moet ik nog even een fatsoenlijk algoritme voor verzinnen.

[Corniel]

[quote]Soultaker schreef op donderdag 14 december 2023 @ 08:33:

Interessant, maar de top 10 komt nu precies overeen met de top 10 op het officiële leaderboard.
[/quote[

Dat is logisch, want die hebben allen alles opgelost.

Hoe kom je aan die extra data per dag trouwens? Heeft de API toegang tot meer data dan beschikbaar in het leaderboard zelf getoond wordt?

Die punten lijken heel erg op hoe het reguliere bord werkt, met die kanttekening dat mensen die geen puzzels hebben opgelost door mij niet worden meegenomen.

En in de API krijg je per puzzel de Unix Timestamp en een index. Die index is volgens mij de hoeveelste goede oplossing het is, maar dat gaat dus over alle edities. Je kan volgens mij niet mee bepalen wat iemands score op het global leaderboard is van zo'n puzzel.

[bakkerjangert]

Vandaag vond ik een leuke puzzel. Wel even vastgezeten op deel 2.

spoiler:

Ik verplaats de stenen in een numpy array. Eerst was ik vergeten te sorteren op voorste rij / kolom van de richting waarin ze rollen, waardoor de rotsen niet ver genoeg door rolden (ze stopte achter rotsen die nog niet gerold hadden die ronde).

code in python met numpy array.

[Remcoder]

spoiler:

En jaaaa, daar is de cycle detectie weer

Ik had alleen een off by one erin zitten waar ik lang naar aan het zoeken was

Ik verwacht trouwens dat we dit weekend pathfinding gaan krijgen.

[Soultaker]

Mugwump schreef op donderdag 14 december 2023 @ 06:46:
Ik vind het wedstrijdelement sowieso niet echt boeiend.

Iedereen kan het doen zoals 'ie wil natuurlijk. Ik focuste in het verleden vooral op correctheid (ik had vorig jaar in totaal 1 foute inzending, als ik het goed heb), ook omdat ik geen zin had om vroeg op te staan, maar juist daarom vond ik het voor de verandering leuk om dit jaar eens op tijd te spelen.

Denk dat het ook zinvoller is om op specifieke aspecten te scoren, dus b.v. het high performance segment voor oplossingen die de snelste executietijden halen of iets dergelijks.

Performance vind ik ook interessant; onder andere daarom post ik vaak grotere testinvoer. Maar als competitie-vorm heeft het ook weer allerlei problemen:

1. Sommige talen zijn gewoon sneller dan anderen. De snelste oplossingen zijn meestal geïmplementeerd in statisch gecompileerde talen als C/C++ of Rust, gevolgd door VM-gebaseerde talen als Java, Kotlin, C#, en dan dynamische scripttalen als JavaScript of Python. Dan verlies je al 90% van je deelnemers die geen andere taal kunnen/willen gebruiken.

2. Je moet overeenstemming hebben over de benchmark data. De AoC data is vaak vrij soft. Je kunt dan je oplossing “optimaliseren” door allerlei aannamen te doen over de invoer. Sowieso zijn de problemen vaak ondergespecificeerd. Bijvoorbeeld, mag je aannemen dat het antwoord in een 64-bit integer past of niet? Dat maakt voor de performance natuurlijk enorm veel uit.

3. Je moet overeenstemming hebben over de gebruikte hardware. Als een deelnemer AVX intrinsics gebruikt, een tweede NEON instructies, en een derde CUDA, wie heeft dan de snelste oplossing geschreven? Hetzelfde geldt voor multithreading: het is meestal simpel om een lineaire speedup te krijgen door delen van de invoer op verschillende threads te runnen, maar dan is de vraag: hoeveel cores mag je gebruiken?

4. Performance optimaliseren kost veel meer tijd. Tenslotte, de eerste oplossing die je bedenkt zal zelden de snelste zijn. De reden dat Advent of Code populair is, is dat het bite sized problemen zijn, die je meestal in een (half)uurtje op kunt lossen. Als het langer duurt haken de meeste mensen af.

Kortom, ik denk dat als je een performance-gebaseerde wedstrijd wil, je het in een andere vorm moet gieten dan Advent of Code. Je zou iets kunnen doen zoals de GoT Programming Contests die we hier vroeger (heel lang geleden) hadden, waarbij je deelnemers een week tot een maand de tijd geeft om aan één probleem te werken.

[FrankMennink]

Ik heb een oplossing, draait alleen wel in 3,5 minuten. Het duurt 225ms voor 1 shift, dus ~1 seconde voor alle 4. Zo maar even kijken hoe dat een stuk sneller kan, ik heb wel een vermoeden.

spoiler:

ik hou nu twee lijsten bij, 1 met de rocks en 1 met alle blockers (# en O die al stil liggen). Ik heb zo'n vermoeden dat het kijken of de huidige coordinaat voorkomt in deze lijst veel te lang duurt. Nu ik zie dat in deel 2 het speelveld niet verhonderdvoudigd oid is het denk ik sneller om wel een 2D array te gebruiken en daar in te werken ipv 2 lijsten

[Remcoder]

Soultaker schreef op donderdag 14 december 2023 @ 09:38:
[...]


Iedereen kan het doen zoals 'ie wil natuurlijk. Ik focuste in het verleden vooral op correctheid (ik had vorig jaar in totaal 1 foute inzending, als ik het goed heb), ook omdat ik geen zin had om vroeg op te staan, maar juist daarom vond ik het voor de verandering leuk om dit jaar eens op tijd te spelen.


[...]

Performance vind ik ook interessant; onder andere daarom post ik vaak grotere testinvoer. Maar als competitie-vorm heeft het ook weer allerlei problemen:

1. Sommige talen zijn gewoon sneller dan anderen. De snelste oplossingen zijn meestal geïmplementeerd in statisch gecompileerde talen als C/C++ of Rust, gevolgd door VM-gebaseerde talen als Java, Kotlin, C#, en dan dynamische scripttalen als JavaScript of Python. Dan verlies je al 90% van je deelnemers die geen andere taal kunnen/willen gebruiken.

2. Je moet overeenstemming hebben over de benchmark data. De AoC data is vaak vrij soft. Je kunt dan je oplossing “optimaliseren” door allerlei aannamen te doen over de invoer. Sowieso zijn de problemen vaak ondergespecificeerd. Bijvoorbeeld, mag je aannemen dat het antwoord in een 64-bit integer past of niet? Dat maakt voor de performance natuurlijk enorm veel uit.

3. Je moet overeenstemming hebben over de gebruikte hardware. Als een deelnemer AVX intrinsics gebruikt, een tweede NEON instructies, en een derde CUDA, wie heeft dan de snelste oplossing geschreven? Hetzelfde geldt voor multithreading: het is meestal simpel om een lineaire speedup te krijgen door delen van de invoer op verschillende threads te runnen, maar dan is de vraag: hoeveel cores mag je gebruiken?

4. Performance optimaliseren kost veel meer tijd. Tenslotte, de eerste oplossing die je bedenkt zal zelden de snelste zijn. De reden dat Advent of Code populair is, is dat het bite sized problemen zijn, die je meestal in een (half)uurtje op kunt lossen. Als het langer duurt haken de meeste mensen af.

Kortom, ik denk dat als je een performance-gebaseerde wedstrijd wil, je het in een andere vorm moet gieten dan Advent of Code. Je zou iets kunnen doen zoals de GoT Programming Contests die we hier vroeger (heel lang geleden) hadden, waarbij je deelnemers een week tot een maand de tijd geeft om aan één probleem te werken.

Als je op performance en algoritmiek wil focussen is de Google Code Jam ook een goede uitdaging. Die puzzels worden op hun machines gedraaid en hebben bepaalde performance constraints.

[eheijnen]

Soultaker schreef op donderdag 14 december 2023 @ 09:38:
[...]

Performance vind ik ook interessant; onder andere daarom post ik vaak grotere testinvoer. Maar als competitie-vorm heeft het ook weer allerlei problemen:

1. Sommige talen zijn gewoon sneller dan anderen. De snelste oplossingen zijn meestal geïmplementeerd in statisch gecompileerde talen als C/C++ of Rust, gevolgd door VM-gebaseerde talen als Java, Kotlin, C#, en dan dynamische scripttalen als JavaScript of Python. Dan verlies je al 90% van je deelnemers die geen andere taal kunnen/willen gebruiken.

4. Performance optimaliseren kost veel meer tijd. Tenslotte, de eerste oplossing die je bedenkt zal zelden de snelste zijn. De reden dat Advent of Code populair is, is dat het bite sized problemen zijn, die je meestal in een (half)uurtje op kunt lossen. Als het langer duurt haken de meeste mensen af.

Kortom, ik denk dat als je een performance-gebaseerde wedstrijd wil, je het in een andere vorm moet gieten dan Advent of Code. Je zou iets kunnen doen zoals de GoT Programming Contests die we hier vroeger (heel lang geleden) hadden, waarbij je deelnemers een week tot een maand de tijd geeft om aan één probleem te werken.

Vraag me af of een competitievorm wel een noodzaak is. Het ermee bezig zijn en ervan leren zou op zich al een goede motivatie zijn.

1. Oplossingen versnellen lijkt me in welke taal dan ook aan de orde of anders gezegd het kan een goede insteek zijn als er naar een oplossing wordt gekeken.

4. Vooraf zou eens een enquête gedaan kunnen worden of er interesse is voor zoiets door het jaar heen. Dat zouden enkele opdrachten kunnen zijn waarin steeds verschillende materie aan de orde kan komen. Misschien ook vast te stellen middels een vragenronde.

......

[P_Tingen]

eheijnen schreef op donderdag 14 december 2023 @ 10:10:
[...]
1. Oplossingen versnellen lijkt me in welke taal dan ook aan de orde of anders gezegd het kan een goede insteek zijn als er naar een oplossing wordt gekeken.

Hangt van de context af; ik werk met een 4GL en maak een ERP applicatie voor een productiebedrijf. In verreweg de meeste programma's is performance vrijwel geen issue; het gaat toch wel snel genoeg. Denk bv aan het opbouwen van een menu voor de gebruiker: of dat nu in 0,1 seconde of in 0,001 seconde of zelfs in 0,5 seconde gebeurt maakt geen kont uit.

Mocht een programma niet snel genoeg zijn dan is de meest verstandige en (meestal) goedkoopste oplossing een snellere computer te kopen

[Mugwump]

P_Tingen schreef op donderdag 14 december 2023 @ 10:36:
[...]

Hangt van de context af; ik werk met een 4GL en maak een ERP applicatie voor een productiebedrijf. In verreweg de meeste programma's is performance vrijwel geen issue; het gaat toch wel snel genoeg. Denk bv aan het opbouwen van een menu voor de gebruiker: of dat nu in 0,1 seconde of in 0,001 seconde of zelfs in 0,5 seconde gebeurt maakt geen kont uit.

Mocht een programma niet snel genoeg zijn dan is de meest verstandige en (meestal) goedkoopste oplossing een snellere computer te kopen

Klopt, en heel veel applicaties zijn niet compute intensief met grote sets aan data. En als er al grote sets aan data zijn, dan zitten ze vaak in databases. Dan is het eerder een kwestie van je database zo inrichten dat de informatievragen die je hebt zo efficiënt mogelijk beantwoord kunnen worden.

In het gros van de applicaties waar ik in werk is de compute tijd misschien 5% van de tijd die nodig is om van input naar output te komen. Netwerkverkeer en database zijn vooral waar de tijd in gaat zitten.

[eheijnen]

Maar als ik die twee reacties zo lees dan krijg ik het idee dat snelheid / optimeren irrelevant is.... ?

[.oisyn]

Ah de puzzel input is deze keer in het Portugees
En de vertaling naar het Nederlands lijkt vooral wat punten weg te halen.

[ Voor 42% gewijzigd door .oisyn op 14-12-2023 10:57 ]

[DataGhost]

eheijnen schreef op donderdag 14 december 2023 @ 10:53:
Maar als ik die twee reacties zo lees dan krijg ik het idee dat snelheid / optimeren irrelevant is.... ?

Hangt van je usecase af. Zoals gezegd als je iets hebt wat voornamelijk afhankelijk is van netwerkverkeer over en weer is het grotendeels irrelevant hoe snel je code is ja. Als je heel grote bewerkingen lokaal doet zonder dit soort afhankelijkheden dan wordt het veel belangrijker.

[eheijnen]

DataGhost schreef op donderdag 14 december 2023 @ 10:57:
[...]

Hangt van je usecase af. Zoals gezegd als je iets hebt wat voornamelijk afhankelijk is van netwerkverkeer over en weer is het grotendeels irrelevant hoe snel je code is ja. Als je heel grote bewerkingen lokaal doet zonder dit soort afhankelijkheden dan wordt het veel belangrijker.

Zekers...

Punt is dat het nu ergens aan vast wordt gemaakt. Jantje vind van wel en Pietje van niet, met allemaal goede argumenten. Maar of optimering een onderdeel van zulk soort opdrachten kan/zal zijn lijkt mij een onderdeel van de enquête.

Gewoon een idee om het voorstel van Soultaker in een wat ruimer jasje te steken en misschien wel tot een format te komen wat hier in het software-forum wat meer leven in de brouwerij kan brengen. Met AoC lukt dat iig elk jaar opnieuw, en dat is leuk om te zien...

[DataGhost]

Maar het is redelijk niche, AoC ook. Als je kijkt naar real-world softwareontwikkeling heeft dit er redelijk weinig mee te maken. Helemaal als je kijkt naar wat het geld ervan vindt, de focus ligt daarom meer op features dan performance. Jammer, maar zo is het nou eenmaal. Dus een wedstrijd populair krijgen is al niet enorm makkelijk, om dan ook nog een problemset te gaan verzinnen is nog iets lastiger, dat kost ontzettend veel tijd en het is heel zonde als er dan relatief weinig mee gedaan wordt. Zelfs toen ik op de uni zat en je nog helemaal niks met het bedrijfsleven te maken had, volle kracht in de algoritmische theorie zat enz, waren de jaarlijkse programmeerwedstrijden ook maar relatief rustig bezocht.

Er zijn in ieder geval al tig online judges met dit soort opdrachten die je gewoon altijd kan doen. Maar die genieten gewoon niet zoveel bekendheid als je hier niet mee bekend bent. AoC is nog relatief bekend en haalt de populariteit volgens mij vooral uit het verhaal-aspect gecombineerd met een "limited" (december) event. Ja, je kan het het hele jaar doen maar dat doen ook weinig mensen. Maar ook hier haken heel veel mensen af omdat gewoon puur de algoritmische kennis niet aanwezig is. Van de 118 op het leaderbord van dit jaar lijkt dat iedereen buiten de top50 al redelijk is afgehaakt en we zitten nog niet eens op de helft van de maand. Eenzelfde trend zie je voorgaande jaren ook.

Dus als je zoiets op wilt zetten en het ook een beetje populair wilt krijgen onder hobbyisten of normale developers die misschien de echte algoritmische kennis ontberen, maar je wilt ze wel een kans geven, zal je het toch veel meer moeten opzetten als een real-world probleem waar de focus veel minder op rauwe performance ligt. Tenminste, dat denk ik dan. Begrijp me niet verkeerd, ik vind het een leuk idee hoor, maar ik weet ook hoe moeilijk het kan zijn om er genoeg mensen enthousiast voor te krijgen dat het een beetje in verhouding staat tot het werk wat er door de organisatie ingestopt wordt.

[eheijnen]

Gegeven, dat AoC met grofweg 300.000 deelnemers van start gaat wereldwijd en dat snel afkalft onderbouwt die "desinteresse" wel. Dan blijft niet veel over als je dat naar NL terug schaalt.

[MueR]

DataGhost schreef op donderdag 14 december 2023 @ 11:28:
Maar ook hier haken heel veel mensen af omdat gewoon puur de algoritmische kennis niet aanwezig is. Van de 118 op het leaderbord van dit jaar lijkt dat iedereen buiten de top50 al redelijk is afgehaakt en we zitten nog niet eens op de helft van de maand. Eenzelfde trend zie je voorgaande jaren ook.

Voor mij is meestal de motivatie een beetje weg ergens tussen dag 15 en 20, afhankelijk van het jaar. Dan worden de puzzels doorgaans ingewikkeld genoeg dat ik ze niet meer even in een (half) uurtje kan aftikken en begint het op werk te lijken. Ik vind het leuk om te doen enzo, maar ook niet om uren er in te stoppen per dag.

[FrankMennink]

FrankMennink schreef op donderdag 14 december 2023 @ 09:56:
Ik heb een oplossing, draait alleen wel in 3,5 minuten. Het duurt 225ms voor 1 shift, dus ~1 seconde voor alle 4. Zo maar even kijken hoe dat een stuk sneller kan, ik heb wel een vermoeden.

spoiler:

ik hou nu twee lijsten bij, 1 met de rocks en 1 met alle blockers (# en O die al stil liggen). Ik heb zo'n vermoeden dat het kijken of de huidige coordinaat voorkomt in deze lijst veel te lang duurt. Nu ik zie dat in deel 2 het speelveld niet verhonderdvoudigd oid is het denk ik sneller om wel een 2D array te gebruiken en daar in te werken ipv 2 lijsten

Day 14 in Python

Aangepast naar wat ik in de spoiler had, draait nu in 1,4s. Ik vraag me af of dit nog sneller kan in Python (vast wel) of dat 1,4s indicatief is voor een goede oplossing in Python. Voor nu in ieder geval tevreden want het draait in <15 seconden

[MueR]

En voor wat betreft het hele wedstrijd stukje, ik zoek het echt niet om de wekker om half 6 te gaan zetten voor zo'n puzzel. Helemaal niet als je vervolgens tegen mensen aan het programmeren bent die al complete libraries met oplossers voor de puzzels hebben waar ze maar kleine aanpassingen voor de huidige editie voor hoeven te maken. Dan ben je met 5 minuten klaar. Tegen die tijd heb ik net drie slokken koffie genomen en het verhaaltje gelezen, want vroeg enzo.

[Soultaker]

Remcoder schreef op donderdag 14 december 2023 @ 10:03:
Als je op performance en algoritmiek wil focussen is de Google Code Jam ook een goede uitdaging. Die puzzels worden op hun machines gedraaid en hebben bepaalde performance constraints.

Alleen jammer dat die dit jaar gestopt is

Een paar goede competitive programming sites die nog over zijn, zijn https://codeforces.com/ (doe ik zo af en toe aan mee; erg goede problemen maar de focus ligt op theorie en wiskunde, waarbij AoC vaak praktischer is), https://atcoder.jp/ (zelf niet meegedaan, maar veel goeds over gehoord) en voor een wat ander soort contest, https://www.codecup.nl/ (zie ook het topic hier van @Vaan Banaan). Als er nog andere leuke contests zijn hou ik me aanbevolen.

eheijnen schreef op donderdag 14 december 2023 @ 11:14:
Gewoon een idee om het voorstel van Soultaker in een wat ruimer jasje te steken en misschien wel tot een format te komen wat hier in het software-forum wat meer leven in de brouwerij kan brengen. Met AoC lukt dat iig elk jaar opnieuw, en dat is leuk om te zien...

Ik zie er wel wat in. Maar dan graag iets ruimer dan performance optimalisatie alleen.

DataGhost schreef op donderdag 14 december 2023 @ 11:28:
Maar het is redelijk niche, AoC ook. Als je kijkt naar real-world softwareontwikkeling heeft dit er redelijk weinig mee te maken. Helemaal als je kijkt naar wat het geld ervan vindt, de focus ligt daarom meer op features dan performance. Jammer, maar zo is het nou eenmaal.

Klopt, maar ik zie dit soort uitdagingen ook meer als hobby naast het werk.

Er zijn in ieder geval al tig online judges met dit soort opdrachten die je gewoon altijd kan doen. Maar die genieten gewoon niet zoveel bekendheid als je hier niet mee bekend bent. AoC is nog relatief bekend en haalt de populariteit volgens mij vooral uit het verhaal-aspect gecombineerd met een "limited" (december) event.

Ik denkt dat het een combinatie is van laagdrempeligheid en inderdaad beperkte omvang.

Er zijn talloze online judges maar juist de grootte van de problem sets werkt intimiderend. Bijvoorbeeld CSES heeft 300 klassieke problemen, Project Euler heeft 857 problemen, en de Sphere Online Judge heeft meer dan 40.000 (!!!) problemen. Het is leuk als archief maar het moedigt niet aan om de problemen zelf op te lossen, want waar begin je überhaupt?

Ik denk dat om mensen aan te spreken, je de problemen meer behapbaar moet maken. AoC doet dat met een klein probleem elke dag. Het helpt ook dat het antwoord een getal is dat je invoert op de website; je bent dus niet gebonden aan een specifieke programmeertaal en je hoeft ook niet uit te zoeken hoe het jureringssyteem werkt.

GoT Programming Contest 1 was ook een goed voorbeeld van een behapbaar probleem: je moest dan een Tetris-AI implementeren, die gegeven een lijst met blokjes bepaalt waar die moeten vallen om de score te maximaliseren. Het is een probleem dat snel te begrijpen is en waar je redelijk makkelijk een simpele solver voor kunt schrijven, terwijl het probleem complex genoeg is dat het vrijwel onmogelijk is een optimale solver te schrijven.

[eheijnen]

Soultaker schreef op donderdag 14 december 2023 @ 12:15:
[...]
Ik zie er wel wat in. Maar dan graag iets ruimer dan performance optimalisatie alleen.
[...]

Lijkt me dat je zoiets altijd eens een paar kan keer proberen in overleg met de moderators, admins en ander personeel om te zien of het wat is (niet geschoten....). Het feit dat je al zin hebt om zoiets gewoonweg te doen en daar een groep(je) geïnteresseerden bij weet te betrekken kan al interessant zijn en wie weet groeit het nog verder uit over de tijd maar kan het ook in kleinere kring een leuke terugkerende ervaring opleveren. Dat kan natuurlijk over de meest uiteenlopende materie, aangeboden in fictieve of real-life cases. Je zoiets bv. een keer of drie per jaar doet (het moet geen sleur worden...) met misschien wel wat grotere opdrachten waar ook uitzoekwerk / een stukje studie onderdeel van kan zijn. Het een ervaring is waarbij je wat kunt opsteken.

[P_Tingen]

MueR schreef op donderdag 14 december 2023 @ 11:51:
[...]
Voor mij is meestal de motivatie een beetje weg ergens tussen dag 15 en 20, afhankelijk van het jaar. Dan worden de puzzels doorgaans ingewikkeld genoeg dat ik ze niet meer even in een (half) uurtje kan aftikken en begint het op werk te lijken. Ik vind het leuk om te doen enzo, maar ook niet om uren er in te stoppen per dag.

Hier idem. Ik vind het vooral leuk om "gekke" problemen op te lossen. Gek in de zin van dat het volledig andere dingen zijn dan waar ik me doorgaans mee bezig hou, maar als het al te algoritmisch of wiskundig wordt dan haak ik af. En ook als het gewoon te veel is. Er is werk te doen en ik probeer er een leven op na te houden.

Het allerleukste vind ik om te zien hoe anderen een probleem oplossen. Ik leer er elk jaar wel weer iets van. Helaas is er in mijn niche van 4GL erg weinig interesse om mee te doen; een dame in Belgie en een heer in Italie en nog iemand die zijn code niet deelt en dan houdt het wel op.

[KabouterSuper]

Soultaker schreef op donderdag 14 december 2023 @ 12:15:
[...]

Als er nog andere leuke contests zijn hou ik me aanbevolen.

Ik heb het vorig jaar ook een keer genoemd: als je cryptografie leuk vindt, zijn de puzzels van Dirk Rijmenants een leuke uitdaging (https://www.ciphermachinesandcryptology.com/). De bekendste is de Enigma challenge (https://www.ciphermachinesandcryptology.com/en/challenge.htm) die ik zelf een paar jaar geleden helemaal heb opgelost. Je moet hierbij tien (echte) Duitse berichten ontcijferen die ge-encrypt zijn met een Enigma machine. Hoe verder je komt in de challenge, hoe minder hints je krijgt totdat je in de laatste challenge geen hints meer krijgt. Alleen het draaien van mijn code om een oplossing te vinden duurde al 1.5 dag (en dit was al behoorlijk geoptimaliseerd).

De box challenges (https://www.ciphermachine...y.com/en/boxchallenge.htm en
https://www.ciphermachinesandcryptology.com/en/boxelite.htm) zijn ook leuk, maar echt wel erg lastig. Ik heb van de reguliere box challenge de eerste twee opgelost. Voor de derde is mijn algoritme nog niet snel genoeg....ik moet een keer gaan performance tunen. De elite challenge zijn voor mij nog een brug te ver.

Een interessante is tenslotte the crow challenge die vanaf 2010 online staat, maar pas dit jaar voor het eerste ontcijferd is (https://www.ciphermachinesandcryptology.com/en/crow.htm). Ik heb wel een idee welk encryptie algoritme gebruikt wordt, maar heb nog geen clue hoe ik dit kan ontcijferen.

Mocht dit allemaal te gemakkelijk zijn, dan kan je ook voor het echte werk gaan: Kryptos. Dit is een kunstwerk wat in 1990 bij het CIA gebouw is geplaatst. Dit kunstwerk bevat ge-encrypte berichten, die nog steeds niet allemaal ontcijferd zijn. De tekst bestaat (waarschijnljik) uit vier delen, elk met een eigen encryptie methode. Deel 1, 2 en 3 (K1, K2, K3) zijn inmiddeld gekraakt. Van deel 4 (K4) is zelfs nog niet bekend met welk algoritme dit ge-encrypt is.

[.oisyn]

Modbreak:

Misschien even een ander topic openen over andere contests?

Day14 in Rust
Time spent: 2360.5µs

Heb het mezelf misschien iets te lastig gemaakt door het met bitsets op te willen lossen. Ik vraag me af of daar überhaupt een tijdswinst in zit. (sowieso niet kwa big-O complexiteit)

[ Voor 5% gewijzigd door .oisyn op 14-12-2023 17:12 ]

[Soultaker]

Hier nog twee challenges voor dag 14: aoc-2023-day-14-challenge-1-to-2.zip

Correcte antwoorden eindigen op: ...337 (deel 1), ...438 (deel 2) voor de eerste invoer, en ...288 (deel 1), ...651 (deel 2) voor de tweede invoer.

Zelfs m'n C++ oplossing doet hier 6 seconden respectievelijk 6 minuten over.

Ik had wel een idee geïmplementeerd om de complexiteit van O(HWN) (met H, W hoogte en breedte, en N aantal iteraties voordat er een cykel gedecteerd is) terug te brengen naar O(ON) (met O het aantal boulders in de invoer), maar dat bleek voor m'n Python code leek dat niet veel sneller te zijn (tenzij ik expres data sets met extreem weinig boulders genereer, wat een beetje flauw is). Ben benieuwd of iemand een manier weet om dit efficient op te lossen!

@.oisyn ik heb geprobeerd jouw solver te runnen, maar die lijkt een harde limiet van 128 x 128 te hebben, dus die moet sowieso geüpdate worden (weet niet of dat ingewikkeld is).

[Soultaker]

.oisyn schreef op donderdag 14 december 2023 @ 17:11:
Day14 in Rust
Time spent: 2360.5µs

Heb het mezelf misschien iets te lastig gemaakt door het met bitsets op te willen lossen. Ik vraag me af of daar überhaupt een tijdswinst in zit.

Hij is ~5 keer zo snel als m'n C++ oplossing dus je doet wel iets goed Daarbij moet ik aantekenen dat std::unordered_map<> niet echt fantastische performance heeft, maar ik weet ook niet of dat de bottleneck is.

[Varienaja]

Dag 14 in Java.

De 'kleine' invoer van @Soultaker doet er al gruwelijk lang over (draait nog steeds). Dat komt door mijn zeer naïeve manier van O-tjes schuiven.

Het leuke van Advent of Code vind ik dat je allerlei slimme algoritmes oefent, waar je normaal (ik altans) niet veel mee in contact komt: Dijkstra, memoization, bottlenecks. Wat ik ook een erg goed aspect vind, is dat je het tweede deel pas te zien krijgt als deel 1 opgelost is. Dit sluit erg goed aan bij het dagelijkse leven, waar de specificatie ook altijd verandert direct nadat je dacht het probleem opgelost te hebben. Erg leuke oefening!

Edit: Mijn oplossing OOMt op de 'kleine' invoer van Soultaker. Niet alleen is mijn manier van Otjes schuiven naïef, ook is mijn representatie van de reflector dish bepaald geheugen-intensief.

[ Voor 11% gewijzigd door Varienaja op 14-12-2023 19:55 ]

[.oisyn]

Soultaker schreef op donderdag 14 december 2023 @ 18:42:
@.oisyn ik heb geprobeerd jouw solver te runnen, maar die lijkt een harde limiet van 128 x 128 te hebben, dus die moet sowieso geüpdate worden (weet niet of dat ingewikkeld is).

Niet ingewikkeld, wel werk .

Wat ik nu dus doe is ik loop over alle rijen in omgekeerde volgorde van de rolrichting (die bij mij altijd maar het noorden is omdat ik het veld steeds roteer, en dat hou ik hier ook maar even aan voor het gemak). Dan heb ik een bitmask van alle rotsen in de rij. Vanaf daar loop ik terug in de rolrichting en doe ik een AND met plekken die bezet zijn. Het resultaat is dan de rotsblokken die niet verder kunnen rollen, dus die OR ik in de bezette plekken van de regel eronder en XOR ik van de actieve rotsblokken af om de rotsen over te houden die verder kunnen bewegen, net zo lang tot ik bovenaan ben of ik geen actieve rotsen meer heb. Worst case O(H²) per cycle.

Ik had ook bedacht dat het anders kon. Als je bitmasks hebt van de kolommen, kun je efficient de bitmasks bepalen van alle tiles ten zuiden van alle # (tot aan de volgende #). Die masks AND je met je rotsen in die rij, en dan doe je een POPCNT om het aantal rotsen te bepalen die tegen die # aan zouden rollen. Dat is O(#+W) per cycle. Die +W is omdat de hele rand feitelijk een # is.

Tenslotte kun je nog van elke tile bepalen hoe ver het van daaruit naar de eerstvolgende # is in noordelijke richting, en op de plek van de # opslaan hoeveel rotsen er tegenaan liggen. Dan kun je voor elke rots in O(1) zijn eindplek bepalen, dus dat is dan O(O) per cycle.

Ik denk dat ik die laatste eens ga implementeren

Soultaker schreef op donderdag 14 december 2023 @ 18:51:
[...]

Hij is ~5 keer zo snel als m'n C++ oplossing dus je doet wel iets goed Daarbij moet ik aantekenen dat std::unordered_map<> niet echt fantastische performance heeft, maar ik weet ook niet of dat de bottleneck is.

Het verschil tussen C++'s unordered_map en Rust's HashMap is dat die laatste alles in de array opslaat met linear probing. Betere cache locality, maar rehashes zijn wat duurder omdat er meer gemoved moet worden.

Ik weet niet wat jouw key is? In mijn geval dus gewoon een Vec<u128> voor het hele veld met rotsen, da's ook niet de meest efficiente key

[ Voor 22% gewijzigd door .oisyn op 14-12-2023 20:50 ]

[MatHack]

Na een dag hard werken kostte vooral de berekening in deel 2 me veel moeite, verder was het qua logica prima te doen vandaag.

spoiler:

'k heb echt veels te lang over de index berekening in deel 2 gedaan... op een gegeven moment eerst maar eens gekeken voor de testset welke index het moest wezen. Toen ik daar op uitkwam ging de echt set nog fout (natuurlijk)... was initieel vergeten de start van de cycle af te trekken van de modulo en daarna weer op te tellen aan het eind

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

[MatHack]

Soultaker schreef op donderdag 14 december 2023 @ 18:42:
Hier nog twee challenges voor dag 14: aoc-2023-day-14-challenge-1-to-2.zip

Correcte antwoorden eindigen op: ...337 (deel 1), ...438 (deel 2) voor de eerste invoer, en ...288 (deel 1), ...651 (deel 2) voor de tweede invoer.

Voor je kleine set:
Part1: ...337
Part2: ...438

Part1 in 4,5631ms
Part2 in 25204,7335ms (~25 sec)

Nog redelijk netjes vind ik.

[Creepy]

Ik heb de afgelopen dagen niks gedaan want druk. Morgen eens kijken of ik wat in kan halen. Maar je ziet elk kaar de trend dat er een hoop mensen afhaken, check de stats van de afgelopen jaren maar eens.

[.oisyn]

.oisyn schreef op donderdag 14 december 2023 @ 20:20:
Tenslotte kun je nog van elke tile bepalen hoe ver het van daaruit naar de eerstvolgende # is in noordelijke richting, en op de plek van de # opslaan hoeveel rotsen er tegenaan liggen. Dan kun je voor elke rots in O(1) zijn eindplek bepalen, dus dat is dan O(O) per cycle.

Ik denk dat ik die laatste eens ga implementeren

Hmmm, 8511.6µs

Het vervelende is dat ik nu de positie van de rotsen als key gebruik, maar dan moet ik ze wel sorten omdat de rotsen wel hetzelfde liggen maar individueel in een andere volgorde.

Het is wel een vrij straightforward oplossing. Ik hoef de 4 richtingen ook niet eens apart van elkaar doen. Ik kan per rots opzoeken tegen welke # hij aanrolt in de N richting, dan vanuit zijn nieuwe plek meteen door naar de W richting, etc.

Wat betreft @Soultaker's testsets, de eerste vindt hij in 2,17s, de tweede in 95,88s.
Heb 'm even gepushed naar een andere branch, day14-alt: https://github.com/oisyn/...y14-alt/day14/src/main.rs

[ Voor 6% gewijzigd door .oisyn op 14-12-2023 23:00 ]

[CrossProd]

Was veel lezen vandaag maar verder simpel. Implementeren wat er gevraagd wordt en verder niet nadenken

[FCA]

Inderdaad een oefening in begrijpend lezen vandaag, en dat om 6 uur 's ochtends voor de koffie

spoiler:

Wel makkelijk uiteindelijk met Python, gegeven dat dicts tegenwoordig standaard ordered zijn. Gewoon een forward box ->dict met labels en backward label -> box map maken, en klaar is kees.

Vandaag was wel de eerste dag dit jaar dat ik een reguliere expressie gebruikte. Tot nu toe weten te vermijden (met groot plezier, gezien de issues van veel mensen met regexps op dag 1).

[ Voor 23% gewijzigd door FCA op 15-12-2023 06:43 ]

[MatHack]

Relatief simpel inderdaad, mijn grootste probleem vandaag was lezen...zowel goed lezen als veel lezen.

spoiler:

Eerst kon ik maar niet vinden over welke box deel 2 ging en toen had ik in eerste instantie ook nog de hash over de hele instructie berekend ipv over de label

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

[Dido]

MatHack schreef op vrijdag 15 december 2023 @ 06:37:

spoiler:

Eerst kon ik maar niet vinden over welke box deel 2 ging en toen had ik in eerste instantie ook nog de hash over de hele instructie berekend ipv over de label

Gelukkig, ik was niet de enige
Maar, goed te doen, en wel fijn om een dagje niet te moeilijk te hoeven doen over optimalisatie om binnen 6 uur een antwoord te vinden

[Varienaja]

Dag 15 in Java.

Ook vandaag een lollig aspect van Advent of Code wat in de dagelijkse praktijk vaak terugkomt: onleesbare (of onnodig gecompliceerde) specificaties.

[Dido]

Varienaja schreef op vrijdag 15 december 2023 @ 07:14:
Dag 15 in Java.

Ook vandaag een lollig aspect van Advent of Code wat in de dagelijkse praktijk vaak terugkomt: onleesbare (of onnodig gecompliceerde) specificaties.

Het lollige vond ik dat ik bij AoC het gevoel heb dat als de beschrijving bijna pseudo-code voorkauwt, een naieve implementatie van die pseudo-code meestal prima is voor deel 1, maar dat je bij deel 2 opeens met een runtime van duizenden jaren zit opgescheept.

Dat dat vandaag niet zo was, was een meevallertje

[Mschamp]

MatHack schreef op vrijdag 15 december 2023 @ 06:37:
Relatief simpel inderdaad, mijn grootste probleem vandaag was lezen...zowel goed lezen als veel lezen.

spoiler:

Eerst kon ik maar niet vinden over welke box deel 2 ging en toen had ik in eerste instantie ook nog de hash over de hele instructie berekend ipv over de label

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

Dat had ik ook, opdracht verschillende keren moeten lezen voor ik dat door had

[Friits]

FCA schreef op vrijdag 15 december 2023 @ 06:35:
Vandaag was wel de eerste dag dit jaar dat ik een reguliere expressie gebruikte. Tot nu toe weten te vermijden (met groot plezier, gezien de issues van veel mensen met regexps op dag 1).

Waarom dan juist vandaag wel reguliere expressies van stal gehaald?

Voor de liefhebbers nog mijn oplossing (Python).

[KabouterSuper]

Mschamp schreef op vrijdag 15 december 2023 @ 08:16:
[...]


Dat had ik ook, opdracht verschillende keren moeten lezen voor ik dat door had

Ik was wel zo slim geweest om het getal eraf te knippen, maar helaas niet het minteken en gelijkteken. Anyway, toen ik dat door had, was het zo gepiept.

[Soultaker]

.oisyn schreef op donderdag 14 december 2023 @ 22:57:
Het vervelende is dat ik nu de positie van de rotsen als key gebruik, maar dan moet ik ze wel sorten omdat de rotsen wel hetzelfde liggen maar individueel in een andere volgorde.

Je hóeft strikt genomen niet te sorteren; niet altijd tenminste. Je kunt ook een custom equality en hash functie definiëren.

Bijvoorbeeld: hash elk punt afzonderlijk, en dan neem dan de XOR van de waarden. Je moet wel een goede hash functie kiezen om collisions te vermijden. Bijvoorbeeld, (31337*x + y) is niet goed want dan heb je het probleem dat [(x1, y1), (x2, y2)] en [(x2, y1), (x1, y2)] naar hetzelfde hashen.

In de vergelijkingsfunctie kun je dan eerst de hash waarden vergelijken, en pas als die gelijk zijn sorteren. Het voordeel is dat als de hash functie een beetje goed werkt je 99% van de tijd niet hoef te sorteren.

[Remcoder]

Varienaja schreef op vrijdag 15 december 2023 @ 07:14:
Dag 15 in Java.

Ook vandaag een lollig aspect van Advent of Code wat in de dagelijkse praktijk vaak terugkomt: onleesbare (of onnodig gecompliceerde) specificaties.

spoiler:

Jouw implementatie is wel zeer afhankelijk van de exacte implementatie van de HashMap die je JVM heeftt, .entrySet() geeft een Set terug, en geen List. Een Set is niet ordered, dus je hebt geen enkele garantie dat je tussen verschillende iteraties over een Set elke keer dezelfde volgorde terugkrijgt.

Dat was voor mij de reden om juist niet voor een Map te gaan, maar een 2D array en met behulp van arrayCopy deze elke keer aanpassen.

[Varienaja]

Remcoder schreef op vrijdag 15 december 2023 @ 09:15:

spoiler:

Jouw implementatie is wel zeer afhankelijk van de exacte implementatie van de HashMap die je JVM heeftt, .entrySet() geeft een Set terug, en geen List. Een Set is niet ordered, dus je hebt geen enkele garantie dat je tussen verschillende iteraties over een Set elke keer dezelfde volgorde terugkrijgt.

Ik heb wel garantie bij het itereren. Ik heb expliciet voor een LinkedHashMap gekozen, die volgens de documentatie een welgedefiniëerde volgorde heeft. Namelijk de volgorde van inserten. De lol daarvan is, dat je niet meer hoeft na te denken over het verschil tussen overschrijven en toevoegen.

[ Voor 3% gewijzigd door Varienaja op 15-12-2023 09:21 ]

[Remcoder]

Varienaja schreef op vrijdag 15 december 2023 @ 09:19:
[...]

Ik denk van niet. Ik heb expliciet voor een LinkedHashMap gekozen, die volgens de documentatie een welgedefiniëerde volgorde heeft. Namelijk de volgorde van inserten. De lol daarvan is, dat je niet meer hoeft na te denken over het verschil tussen overschrijven en toevoegen.

Oooh ja, ik zie het.

Interessant, dat wist ik niet van de LinkedHashMap.

[.oisyn]

Day15 in Rust
Time spent: 190.6µs

Gewoon een vector, snel zat

[FrankMennink]

Day 15 in Python

Lekker begin van de dag, redelijk simpel uitvoeren wat er gevraagd wordt. Ook 5 keer door de tekst heengelezen om dit zinnetje elke keer te missen: "The result of running the HASH algorithm on the label indicates the correct box for that step". Is alweer een aantal dagen terug dat beide delen in een single submission correct zijn

[Diderikdm]

Python - dag 14

Niet de meest efficiënte oplossing denk ik.

Python - dag 15

Vond het een leuke puzzel vandaag. Voelde anders dan andere puzzels afglopen jaren.

[MadEgg]

Soultaker schreef op donderdag 14 december 2023 @ 18:42:
Hier nog twee challenges voor dag 14: aoc-2023-day-14-challenge-1-to-2.zip

Correcte antwoorden eindigen op: ...337 (deel 1), ...438 (deel 2) voor de eerste invoer, en ...288 (deel 1), ...651 (deel 2) voor de tweede invoer.

Na te veel tijd in dag 14 te steken kon ik het niet laten om deze toch ook eens te proberen. Eerst gelijk een bug: mijn code ging er vanuit dat het grid vierkant was. Dat is bij jouw sets niet het geval, dat was nog weer even pielen om het goed te krijgen. Daarna: hij komt er wel doorheen, maar het kost tijd. Deel 1: 225 seconden. Is op te wachten, maar toch.. deel 2 ga ik maar niet proberen.

[P_Tingen]

Dag 14

spoiler:

ik dacht voor deel 2 slim te zijn en te zoeken naar wanneer het patroon gaat herhalen. Ik loop door de cycli heen en bewaar de tussenresultaten. Alleen doet mijn programma er 3 seconden over om 1 roll te berekenen, dus 12 seconden voor 1 cyclus van 4 richtingen. Als dan na een paar honderd (duizend? tienduizenden?) keer die herhaling komt, duurt het me te lang.

Is dit wel de goede oplossingsrichting? En zo ja, in wat voor orde van grootte zit die herhaling?

[Varienaja]

P_Tingen schreef op vrijdag 15 december 2023 @ 12:58:
Dag 14

spoiler:

Is dit wel de goede oplossingsrichting? En zo ja, in wat voor orde van grootte zit die herhaling?

spoiler:

Ja. Ik had een cycle van 22 vanaf positie 130 ongeveer.

Maar dat kan je met de kleine voorbeeldinvoer toch vlug uitproberen?

[ Voor 10% gewijzigd door Varienaja op 15-12-2023 13:02 ]

[MatHack]

Varienaja schreef op vrijdag 15 december 2023 @ 13:02:
[...]

spoiler:

Ja. Ik had een cycle van 22 vanaf positie 130 ongeveer.

Maar dat kan je met de kleine voorbeeldinvoer toch vlug uitproberen?

spoiler:

@P_Tingen mijn set had ongeveer dezelfde orde van grootte qua cycle/positie. Maar ik zou inderdaad eerst eens met de testset proberen, daar liggen de cycle en positie allebei onder de 10.

[ Voor 4% gewijzigd door MatHack op 15-12-2023 14:02 . Reden: spoiler-tags ]