Advent of Code 2021

[dcm360]

Bij mij is de (snelle) oplossing voor dag 19 als volgt:

spoiler:

Ik begin met een lijst van 'bekende' scanners (alleen 0 in het begin), en een lijst met overgebleven scanners. Zo lang er nog iets in de lijst met overgebleven scanners zit, doe ik het volgende

• Voor alle overgebleven scanners
• Neem alle rotaties van de overgebleven scanner*
• Voor alle eerder gevonden scanners
• Voor n-11 punten in deze rotatie van deze overgebleven scanner
• Voor n-11 punten van deze eerder gevonden scanner
• Calculeer de offset tussen de 2 punten, en kijk of er 12 overeenkomende punten zijn met deze offset
• Bij een match, voeg de scanner en de offset toe aan de gevonden scanners

Aangezien mijn originele implementatie vrij traag was, wordt de stap met * parallel uitgevoerd. Het rekent ook niet alles door, met een for-comprehension is dit een berg flatMaps over iterators met een filter er in, en ik pak het eerste element dat uit de gecombineerde iterator komt.

[MrHaas]

spoiler:

Aaaargh, had heel snel implementatie voor deel 2 maar ik had stomme bug die er voor zorgde dat de initiele score begon op de beginpositie en daar heb ik 20 minuten over gedaan om die er uit te halen

Verder was het klassiek DP-probleem waarbij ik de posities + scores + huidige rol (1-6) gebruik als input voor de functie.

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

[ Voor 32% gewijzigd door MrHaas op 21-12-2021 07:20 ]

[armageddon_2k1]

Okee, ik zie hem nog niet voor Part 2 vandaag. Part 1 was easy-peasy alleen ik gokte er even op dat part 2 hopelijk niet zo zou zijn als ie nu is. Verkeerd gegokt, en ik had het kunnen weten

[Janoz]

[ydderf]

Dag 21 deel 1 had ik snel voor elkaar. Maar deel twee snap ik ergens de omschrijving niet.

spoiler:

Je gooit de eerste keer. Daar komen drie resultaten uit (1, 2 en 3). Dit zijn dus drie nieuwe universa (is dat het juiste woord?). Je hebt elke beurt minimaal 1 punt als score (max 10).
In elk universum gooi je weer, en daar komen weer drie resultaten uit. Ofwel we hebben nu 3x3=9 universa. Deze splitsen weer tot 3x3x3=27 universa.
Als ik dan 3^21 doe, kom ik op 10.460.353.203 universa uit. Voor het gemak heb ik het om- en om- gooien fweggestreept tegen het feit dat je vaak meer dan 1 punt haalt.
Hoe komen ze dan aan zoveel universa in het voorbeeld??

[MrHaas]

ydderf schreef op dinsdag 21 december 2021 @ 09:04:
Dag 21 deel 1 had ik snel voor elkaar. Maar deel twee snap ik ergens de omschrijving niet.

spoiler:

Je gooit de eerste keer. Daar komen drie resultaten uit (1, 2 en 3). Dit zijn dus drie nieuwe universa (is dat het juiste woord?). Je hebt elke beurt minimaal 1 punt als score (max 10).
In elk universum gooi je weer, en daar komen weer drie resultaten uit. Ofwel we hebben nu 3x3=9 universa. Deze splitsen weer tot 3x3x3=27 universa.
Als ik dan 3^21 doe, kom ik op 10.460.353.203 universa uit. Voor het gemak heb ik het om- en om- gooien fweggestreept tegen het feit dat je vaak meer dan 1 punt haalt.
Hoe komen ze dan aan zoveel universa in het voorbeeld??

spoiler:

Beurt bestaat nog steeds uit 3 worpen

[Diderikdm]

Python dag 21

spoiler:

bruteforce ging niet werken voor part 2, dus besloten de kansen voor het totaal aantal vakjes per 3 worpen plat te slaan naar het aantal mogelijkheden om dat totaal per 3 worpen te gooien

Vervolgens recursief deze kansen ingegaan

[ Voor 56% gewijzigd door Diderikdm op 21-12-2021 09:45 ]

[KabouterSuper]

ydderf schreef op dinsdag 21 december 2021 @ 09:04:
Dag 21 deel 1 had ik snel voor elkaar. Maar deel twee snap ik ergens de omschrijving niet.

spoiler:

Je gooit de eerste keer. Daar komen drie resultaten uit (1, 2 en 3). Dit zijn dus drie nieuwe universa (is dat het juiste woord?). Je hebt elke beurt minimaal 1 punt als score (max 10).
In elk universum gooi je weer, en daar komen weer drie resultaten uit. Ofwel we hebben nu 3x3=9 universa. Deze splitsen weer tot 3x3x3=27 universa.
Als ik dan 3^21 doe, kom ik op 10.460.353.203 universa uit. Voor het gemak heb ik het om- en om- gooien fweggestreept tegen het feit dat je vaak meer dan 1 punt haalt.
Hoe komen ze dan aan zoveel universa in het voorbeeld??

Je speelt om en om, dus in het slechtste geval zit je op 3^21*3^20. Komt dat beter in de buurt?

[Janoz]

Zo, ook weer klaar. https://github.com/Janoz-...oc/y2021/day21/Day21.java

spoiler:

Eigenlijk voornamelijk van 2 dingen last gehad. Ik was eerst even vergeten dat je meerder dobbel permutaties hebt die dezelfde score opleveren, en dat het uitmaakt welke van de spelers aan de beurt is voor mijn cache.

Bruteforcen leek me onhaalbaar gezien de nummers. Ik had verwacht dat mijn iets efficiëntere oplossing er daarom ook nog best wel even over zou doen. Ik was dan ook verbaasd dat hij in 24ms klaar was.

[ Voor 22% gewijzigd door Janoz op 21-12-2021 10:20 ]

[ydderf]

aah, ik denk dat ik deel 2 snap.

spoiler:

je gooit met 3 dobbelstenen ipv 1 dobbelsteen per beurt. En die kunnen elk een waarde 1 of 2 of 3 hebben, Ofwel per beurt heb je al 3x3x3 mogelijke universa.
Helaas is mijn brute force oplossing nu al een hele tijd aan het draaien. Dus maar wat slimmers bedenken

[DataGhost]

FFFFFUUUUU Lekker aan het ontbijten, opdracht gelezen, ziet er redelijk simpel uit. Hmm, vermoeden wat deel 2 zou kunnen zijn. Ik dacht dus van ah, TOF! Ik ga iets slims bouwen zodat deel 2 supermakkelijk is. Alleen bleek deel 2 dus compleet niet mijn vermoeden te zijn. En ik had het niet zo'n beetje verkeerd gegokt ook niet.

Maar goed dan, upping the ante:

spoiler:

Deel 1, maar het spel eindigt als een speler een score van 100000000000000000000 behaalt.

Antwoord:

spoiler:

7499999999999999998975000000000000000035

Nu maar eens verder met deel 2 lezen en maken.

[ydderf]

Dag 21 in C# .
De oplossing voor deel 2 is deels brute force geworden met toch iets slimmigheid zodat hij met 2,5 sec het antwoord heeft. Het langste ben ik bezig geweest met het snappen van mijn denkfout in deel 2.

spoiler:

Sommige combinaties van de drie dobbelstenen leveren het zelfde totaal op. Ipv alle combinaties recursieve door te werken, werk ik alleen de mogelijke totalen door. Het resultaat vermenigvuldig ik weer met de factor hoe vaak dit totaal voor komt.

[Woy]

Ik moet vanavond ook maar eens in gaan halen, ben blijven steken op dag 8 omdat ik op vakantie was. Hoe verhouden de puzzels zich met vorig jaar qua complexiteit?

[ydderf]

@Woy ik miste je oplossingen al. Vorig jaar keek ik meestal ff bij jou hoe ik het ook kan in C#.
Voor dit jaar heb het gevoel dat ik er iets makkelijker doorheen kom dan vorig jaar.

[Varienaja]

Woy schreef op dinsdag 21 december 2021 @ 11:04:
Hoe verhouden de puzzels zich met vorig jaar qua complexiteit?

Mij lijken de puzzles ietsje gemakkelijker dan die van vorig jaar.

Vandaag was het wel uitdagend. De Chinese Reststelling en het hexagonale grid zijn dit jaar nog niet aan bod gekomen.

[Diderikdm]

Woy schreef op dinsdag 21 december 2021 @ 11:04:
Ik moet vanavond ook maar eens in gaan halen, ben blijven steken op dag 8 omdat ik op vakantie was. Hoe verhouden de puzzels zich met vorig jaar qua complexiteit?

In hoeverre hier iets uit af te leiden is weet ik niet, maar het lijkt dat voor de delta tijd voor part 2 oplossen na part 1, vorig jaar (rechts), gemiddeld iets langer heeft geduurd:

[Remcoder]

spoiler:

Vandaag is memoisation je vriend, 300 ms voor het antwoord voor deel 2

Members only:

Alleen zichtbaar voor ingelogde gebruikers. Inloggen

[ Voor 3% gewijzigd door Creepy op 21-12-2021 16:43 ]

[joppybt]

Remcoder schreef op dinsdag 21 december 2021 @ 11:44:
*snip*, spoiler.
***members only***

Dit soort hints graag in spoiler tags.

[ Voor 15% gewijzigd door Creepy op 21-12-2021 16:44 ]

[joppybt]

Vandaag zijn maar 10x10=100 startposities mogelijk.

Zouden dus een heleboel mensen dezelfde invoer hebben? Ik dacht dat iedereen eigenlijk altijd wel unieke invoer kreeg.

[bakkerjangert]

Mijn code in Python. Deel 2 runt in 30 seconden.

[dcm360]

joppybt schreef op dinsdag 21 december 2021 @ 12:00:
Vandaag zijn maar 10x10=100 startposities mogelijk.

Zouden dus een heleboel mensen dezelfde invoer hebben? Ik dacht dat iedereen eigenlijk altijd wel unieke invoer kreeg.

De invoer is zeker niet uniek. Voor enkele puzzels zit er zelfs wat rekentijd in om er zeker van te kunnen zijn dat de invoer geldig is, naast vaak ook wat rekentijd om het correcte antwoord te berekenen. Voor alle puzzels is er dus een set aan invoermogelijkheden met bekende antwoorden, waarvan je er (denk ik ogenschijnlijk) willekeurig 1 krijgt. Iedereen wat unieks geven schaalt niet zo goed naar 200k deelnemers.

[DataGhost]

MrHaas schreef op dinsdag 21 december 2021 @ 09:09:
[...]

spoiler:

Beurt bestaat nog steeds uit 3 worpen

Jezus hier heb ik ook te lang op gezeten. Minstens vier keer herschreven op verschillende manieren... bleek het de hele tijd gewoon goede code te zijn alleen dat stomme dingetje gemist

spoiler:

Omdat ik dus eigenwijs was met deel 1 heb ik daar geen enkele dobbelsteen gegooid, dus was ook het hele concept van driemaal gooien nog niet echt tegengekomen

[ Voor 19% gewijzigd door DataGhost op 21-12-2021 12:30 ]

[P_Tingen]

ydderf schreef op maandag 20 december 2021 @ 22:15:
[...]
Als ik nog tips mag geven:

spoiler:

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

Extra tip

spoiler:

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

spoiler:

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

Na een goede nacht nog eens naar gekeken en met de tips hier (en wat trial en error) er toch uitgekomen en dag 20 opgelost. Uiteindelijk wilde ik het nog weer wat netter maken maar toen kreeg ik het niet meer werkend en ik had niet de motivatie om het dan heel mooi te maken. Dus reverten en klaar is Kees.

[EfBe]

Ik blijf stackoverflow's houden in C#,

spoiler:

zelfs als ik de stopscore op 5 zet. Sigh...Ik snap dat je na iedere worp de recursie in moet, en dat na 6 recursive calls de volledige beurt over is (en na 3 recursive calls dus de beurt voor player 1) maar ik krijg de stopclause maar niet. Zit nu op depth 245 in de debugger en hij weet van geen ophouden. Al een paar uur bezig nu, dus ik geef het op.

[Remcoder]

DataGhost schreef op dinsdag 21 december 2021 @ 12:27:
[...]

Jezus hier heb ik ook te lang op gezeten. Minstens vier keer herschreven op verschillende manieren... bleek het de hele tijd gewoon goede code te zijn alleen dat stomme dingetje gemist

spoiler:

Omdat ik dus eigenwijs was met deel 1 heb ik daar geen enkele dobbelsteen gegooid, dus was ook het hele concept van driemaal gooien nog niet echt tegengekomen

Ik ben wel benieuwd naar jouw oplossing.

spoiler:

Ik had wel het idee dat je deel 1 kan bepalen zonder ook maar 1 dobbelsteenworp te gooien, met die aanpak was ik aanvankelijk ook begonnen. Voor speler 1 had ik al snel bepaald dat die altijd zou winnen, want per 10 beurten (5 voor speler 1, en 5 voor speler 2) zou speler 1 30 plekken vooruit gaan, en speler 2 25 plekken. Die 30 plekken voor speler 1 had ik dus gebruikt om het aantal beurten te bepalen tot die net geen 1000 punten zou bereiken, en hoeveel punten die dan nog nodig had om te winnen. Daarna die laatste paar punten gebruiken om te bepalen hoeveel extra beurten nog nodig waren om te winnen en dan had ik het totale aantal beurten dat gespeeld werd.

Dit kon ik dan gebruiken om voor speler 2 de eindscore te bepalen, maar hier ging ik redelijk de mist in. Uiteindelijk dan maar voor speler 2 wel de worpen simuleren, en hier leek ik aanvankelijk een goed antwoord uit te krijgen met de testcase. Helaas werkte het niet met de echte input.

Na wat verder denkwerk bedacht ik me dat er in mijn uitwerking een fout zat. Omdat ik geen zin had om het opnieuw uit te werken ben ik toch maar de worpen gaan simuleren.

Voor deel 2 verwacht ik dat er ook nog een optimalisatie mogelijk is aangezien ik nu elke keer alle 3 de worpen doe, terwijl de eindwaarde van de 3 worpen altijd tussen de 3 en de 9 ligt. Dit zou ik samen met het aantal keren dat elk getal voorkomt moeten kunnen gebruiken om zonder 3 geneste loopjes de resultaten te kunnen bepalen, maar hier zit ik ook nog te broeden op een oplossing.

[Remcoder]

EfBe schreef op dinsdag 21 december 2021 @ 13:22:
Ik blijf stackoverflow's houden in C#,

spoiler:

zelfs als ik de stopscore op 5 zet. Sigh...Ik snap dat je na iedere worp de recursie in moet, en dat na 6 recursive calls de volledige beurt over is (en na 3 recursive calls dus de beurt voor player 1) maar ik krijg de stopclause maar niet. Zit nu op depth 245 in de debugger en hij weet van geen ophouden. Al een paar uur bezig nu, dus ik geef het op.

Tip:

spoiler:

Je hoeft niet na elke worp de recursie te doen, je kan ook per speelronde (een beurt van speler 1 en speler 2) recurseren, dat scheelt je al 6 stappen per keer. Ik verwacht alleen niet dat je either way een antwoord gaat krijgen binnen een realistische tijd, maar daar zijn ook weer oplossingen voor te vinden

Zorg er eerst maar eens voor dat je geen stackoverflow krijgt

[Diderikdm]

EfBe schreef op dinsdag 21 december 2021 @ 13:22:
Ik blijf stackoverflow's houden in C#,

spoiler:

zelfs als ik de stopscore op 5 zet. Sigh...Ik snap dat je na iedere worp de recursie in moet, en dat na 6 recursive calls de volledige beurt over is (en na 3 recursive calls dus de beurt voor player 1) maar ik krijg de stopclause maar niet. Zit nu op depth 245 in de debugger en hij weet van geen ophouden. Al een paar uur bezig nu, dus ik geef het op.

spoiler:

werkt deze recursie wel als je slechts rekening houdt met 1 player?

[ydderf]

EfBe schreef op dinsdag 21 december 2021 @ 13:22:
Ik blijf stackoverflow's houden in C#,

spoiler:

zelfs als ik de stopscore op 5 zet. Sigh...Ik snap dat je na iedere worp de recursie in moet, en dat na 6 recursive calls de volledige beurt over is (en na 3 recursive calls dus de beurt voor player 1) maar ik krijg de stopclause maar niet. Zit nu op depth 245 in de debugger en hij weet van geen ophouden. Al een paar uur bezig nu, dus ik geef het op.

Ik heb het heel schematisch zo opgebouwd:

spoiler:

playGame()
{
if(score < limit)
{
winnerCount = playGame();
}
else
{
winnerCount = thisWinner;
}

return winnerCount;
}

Je stopt de recursie zodra je een winnaar hebt.

[EfBe]

@ydderf Ja dat doe ik dus ook Maar ik krijg het niet voor elkaar. Zo frustrerend. Ik lees alles soms veel te letterlijk en kom dan in de knoei met wat het dan moet zijn, dus

spoiler:

zijn er na een volledige beurt 18 (beide splitten de huidige 3 keer per worp) universa of split player 2 dus de universa die player 1 heeft gecreeerd 3 keer?

.

Geen tijd meer vandaag om hier mee door te gaan, ga aan het eind van de dag nog wel ff kijken. Dank allen voor de tips

[DataGhost]

Remcoder schreef op dinsdag 21 december 2021 @ 13:26:
[...]

Ik ben wel benieuwd naar jouw oplossing.

spoiler:

Ik had wel het idee dat je deel 1 kan bepalen zonder ook maar 1 dobbelsteenworp te gooien, met die aanpak was ik aanvankelijk ook begonnen. Voor speler 1 had ik al snel bepaald dat die altijd zou winnen, want per 10 beurten (5 voor speler 1, en 5 voor speler 2) zou speler 1 30 plekken vooruit gaan, en speler 2 25 plekken. Die 30 plekken voor speler 1 had ik dus gebruikt om het aantal beurten te bepalen tot die net geen 1000 punten zou bereiken, en hoeveel punten die dan nog nodig had om te winnen. Daarna die laatste paar punten gebruiken om te bepalen hoeveel extra beurten nog nodig waren om te winnen en dan had ik het totale aantal beurten dat gespeeld werd.

Dit kon ik dan gebruiken om voor speler 2 de eindscore te bepalen, maar hier ging ik redelijk de mist in. Uiteindelijk dan maar voor speler 2 wel de worpen simuleren, en hier leek ik aanvankelijk een goed antwoord uit te krijgen met de testcase. Helaas werkte het niet met de echte input.

Na wat verder denkwerk bedacht ik me dat er in mijn uitwerking een fout zat. Omdat ik geen zin had om het opnieuw uit te werken ben ik toch maar de worpen gaan simuleren.

Voor deel 2 verwacht ik dat er ook nog een optimalisatie mogelijk is aangezien ik nu elke keer alle 3 de worpen doe, terwijl de eindwaarde van de 3 worpen altijd tussen de 3 en de 9 ligt. Dit zou ik samen met het aantal keren dat elk getal voorkomt moeten kunnen gebruiken om zonder 3 geneste loopjes de resultaten te kunnen bepalen, maar hier zit ik ook nog te broeden op een oplossing.

Nou, de dobbelsteen is deterministisch en

spoiler:

eindig. Dan weet je dat je met steeds drie opvolgende worpen een herhaling hebt na maximaal 300 beurten.

Het geheel is echter

spoiler:

modulo 10, dus of je nou 12, 13, 13 of 1, 2, 3 gooit, maakt niet uit. Dan is je maximale herhaling opeens nog maar 30 beurten. Een duizendzijdige deterministische dobbelsteen geeft precies dezelfde resultaten.

Als je dit simuleert, moet direct opvallen dat

spoiler:

er een poepsimpele formule voor de worp in beurt X te bedenken valt. Bovendien herhaalt deze zich ondertussen nog maar elke 10 stappen

Daarmee kan je dus uitrekenen wat

spoiler:

de scores en posities zijn na X beurten vanaf een startpositie. Dit herhaalt zich ook na Y stappen. Alleen nog even zorgen dat je de beurten om en om doet voor elke speler. Omdat speler 1 altijd de even beurten en speler 2 altijd de oneven beurten heeft is dit een simpele en kleine 1D-array per speler.

Het is nu al relatief makkelijk geworden, maar je kan nog iets verder gaan,

spoiler:

in de posities is namelijk ook een herhaling te zien, een verschillende voor beide spelers maar natuurlijk met een klein gemeenschappelijk veelvoud. Bovendien is de herhaling an sich onafhankelijk van de startpositie. Daardoor zijn de posities voor de rest van de opgave volstrekt irrelevant geworden en heb je alleen nog maar de scores nodig als je die array groot genoeg maakt.

Als je dat allemaal hebt bedacht, is het nog maar een kleine stap om

spoiler:

uit te rekenen hoe vaak de hoogste score voor elke speler in de totaalscore past, en daarna zijn er nog maximaal Y ronden te doen, waarvan de scores in je eerder uitgerekende array zitten.

Op dat moment heb je het aantal ronden en kan je

spoiler:

de rest redelijk makkelijk uitrekenen op een vergelijkbare manier als waarop de scoreberekening ging. Het is nu nauwelijks complexer dan een formule geworden qua looptijd iig

Daarom duurt het bij mij ook even lang ongeacht tot welke score je wilt spelen. Dus tot 100000000000000000000 punten is ook binnen een paar milliseconden uitgerekend.

Misschien niet het superleesbaarst, en deel 2 heb ik geen zin gehad netter te maken, maar here goes:

Members only:

Alleen zichtbaar voor ingelogde gebruikers. Inloggen

[Remcoder]

EfBe schreef op dinsdag 21 december 2021 @ 13:52:
@ydderf Ja dat doe ik dus ook Maar ik krijg het niet voor elkaar. Zo frustrerend. Ik lees alles soms veel te letterlijk en kom dan in de knoei met wat het dan moet zijn, dus

spoiler:

zijn er na een volledige beurt 18 (beide splitten de huidige 3 keer per worp) universa of split player 2 dus de universa die player 1 heeft gecreeerd 3 keer?

.

Geen tijd meer vandaag om hier mee door te gaan, ga aan het eind van de dag nog wel ff kijken. Dank allen voor de tips

spoiler:

[quote]
In this case, rolling the die always splits the universe into three copies: one where the outcome of the roll was 1, one where it was 2, and one where it was 3.
[/quote]
Dus bij elke worp splitst die, niet na elke beurt. Dus na een volledige speelronde heb je 3^6=729 potentiele nieuwe universa. Uiteraard afhankelijk van of speler 1 gewonnen heeft in zijn beurt of niet.

[ydderf]

EfBe schreef op dinsdag 21 december 2021 @ 13:52:
@ydderf Ja dat doe ik dus ook Maar ik krijg het niet voor elkaar. Zo frustrerend. Ik lees alles soms veel te letterlijk en kom dan in de knoei met wat het dan moet zijn, dus

spoiler:

zijn er na een volledige beurt 18 (beide splitten de huidige 3 keer per worp) universa of split player 2 dus de universa die player 1 heeft gecreeerd 3 keer?

.

Geen tijd meer vandaag om hier mee door te gaan, ga aan het eind van de dag nog wel ff kijken. Dank allen voor de tips

Ik ken het gevoel

spoiler:

. Speler 1 gooit met drie dobbelstenen. Elke dobbelsteen splits zich in drie universa. Dus je hebt 3x3x3=27 mogelijkheden. (1,1,1 - 1,1,2 - 1,1,3 - 1,2,1 enz).
Hierna is speler 2. Deze gooit weer met drie dobbelstenen. Maar hij doet dat in alle 27 universa. Dus je hebt dan al 27x27 universa.

[armageddon_2k1]

Dag 21 in Kotlin.

Ik had echt moeite om te bedenken hoe ik dit moest doen, maar toen ik even gewandeld had was ik er snel achter. Hij draait in 200ms en zonder de truucjes van hierboven

spoiler:

Geen recursie of dynamic programming voor mij. Ik heb een CountingSet gemaakt, wat eigenlijk gewoon een set is, maar waarvan bijgehouden wordt hoeveel keren een item voorkomt. In die set worden de turns bijgehouden, welke eigenlijk gewoon (player1Pos, player2Pos, player1Score, player2Score, turn) is, waar turn in dit geval een boolean is van wie er aan de gang is.

Dan, gewoon loopen door de set en alle items eruit halen en hun volgende stappen allemaal bepalen en weer terugplaatsen in de set, maar met de count van de vorige. Dus als een turn A 12X voorkomt, dan worden z'n 27 volgende stappen ook 12x toegevoegd. Als die al bestonden in de set worden ze daaraan toegevoegd.

Als een turn 'finished' is (dus een score >= 21) dan wordt ie uit de set gehaald en in een finished CountingSet gestopt.

.

[Remcoder]

ydderf schreef op dinsdag 21 december 2021 @ 13:59:
[...]

Ik ken het gevoel

spoiler:

. Speler 1 gooit met drie dobbelstenen. Elke dobbelsteen splits zich in drie universa. Dus je hebt 3x3x3=27 mogelijkheden. (1,1,1 - 1,1,2 - 1,1,3 - 1,2,1 enz).
Hierna is speler 2. Deze gooit weer met drie dobbelstenen. Maar hij doet dat in alle 27 universa. Dus je hebt dan al 27x27 universa.

spoiler:

Vergeet niet dat als speler 1 wint, speler 2 niet meer aan de beurt komt, dus je hebt niet altijd 27x27 universa, soms "slechts" 27, of elk willekeurig veelvoud van 27 tot 27x27

[EfBe]

Ah ja, dat wordt dan dus een een massive tree waarbij je inderdaad

spoiler:

start states plus wie aan de beurt is moet onthouden wat dat oplevert voor winnaar zodat je die toestanden niet nog eens gaat berekenen. Niet zo gek dat die recursie van mij uit zn voegen loopt Maar goed, genoeg tijd aan verknoeid.

[ Voor 18% gewijzigd door EfBe op 21-12-2021 14:10 ]

[KabouterSuper]

bakkerjangert schreef op dinsdag 21 december 2021 @ 12:06:
Mijn code in Python. Deel 2 runt in 30 seconden.

Mijn python code doet het in 1 seconde.

spoiler:

Zo te zien speel jij de beurten van de spelers helemaal uit en kijkt achteraf in welke beurt dit gebeurd is.
Wat ik doe is echt om en om een beurt doen en het potje beeindigen zodra er eentje gewonnen heeft. Ik denk dat dit de grootte van de dataset behoorlijk beperkt.

Preciezer, wat ik doe is het aantal universa bijhouden middels een 4-dimensionale array, nl (space0,space1,score0,score1) met daarbij het aantal universa. Verder houd ik per speler het aantal gewonnen potjes bij (of beter gezegd: het aantal universa waar de speler gewonnen heeft).

Elke worp loop ik over mijn array posities en over een lijst met sommen van 3 worpen (1 worp heeft 3 als som, 3 hebben 4 als som, ,6 hebben 5 als som, etc).
Ik werk voor elke combinatie de spaces, scores en aantallen bij. De posities waar de score 21 of hoger is, haal ik weg en tel ik op bij de winnende universa van de speler die bezig is.

Mijn voorbeeld array met 4D coordinaten begint met 1 element (4,8,0,0) heeft maximaal 12210 elementen. Vanaf beurt 5 eindigen er potjes (dus speler 0,1,0,1 en 0).

[Janoz]

KabouterSuper schreef op dinsdag 21 december 2021 @ 14:48:
[...]

Mijn python code doet het in 1 seconde.

Een seconde? Mijne doet het in 30ms.

spoiler:

In principe gebruik ik gewoon een recursieve functie waarbij P1 aan de beurt is:

splitUniverses(Player p1, Player p2) {
__result = new LongTuple();
__Player played;
__for (int d=3; d<10; d++) {
____played = p1.moved(d);
____if (played.score >= 21) result = result.incLeft(possibilities[d]);
____else result = result.add(splitUniverses(p2,played).switched().times(possibilities[d]));
__}
__return result;
}

possibilities is een map waarin de aantal worpen staan die d als uitkomst hebben. Die 1,3,5, etc waar jij het ook over hebt.

Als P1 gewonnen heeft na de worp hoog ik het resultaat voor hem op met het aantal mogelijkheden om die score te gooien. Als P1 na zijn worp nog niet gewonnen heeft ga ik de recursie in en wissel ik dus de spelers om. Het resultaat daaruit moet ik omdraaien (wat spelers waren omgedraait) en vermenigvuldigen met hoe vaak deze situatie mogelijk is en vervolgens optellen bij het huidige resultaat tot nu toe.

Hier heb ik vervolgens eenzelfde 4D array omheen gezet zodat de berekening maar 1x gemaakt wordt voor elke permutatie van positie en score van beide spelers. Nooit meer dan 21x10x21x10 = 44100 daadwerkelijke berekeningen dus.

https://github.com/Janoz-...2021/day21/Day21.java#L49

Net voor de gein even gekeken, maar binnen een seconde rekent dit algoritme uit in hoeveel universa de speler wint wanneer de score 100 is. Ik krijg alleen nog niet het goede antwoord vanwege een overflow van mijn long. Dus ik denk niet dat ik het echte antwoord ook in een seconde krijg

[ Voor 8% gewijzigd door Janoz op 21-12-2021 15:25 ]

[ydderf]

Ik was even in de uitwerking van @Janoz aan het kijken, en bedacht me dat ik voor deel 1 niet helemaal aan de opdracht heb voldaan en toch een correct antwoord heb gekregen.

spoiler:

Bij mij blijft de dobbelsteen onder de 100, dus dat ik niks heb gemaakt om na 100 opnieuw te beginnen bij 1 heeft geen probleem gegeven.

[Creepy]

Janoz schreef op dinsdag 21 december 2021 @ 08:32:
[Afbeelding]

Precies dit dit. Ik ben nu iets meer dan een uur aan het staren en wat gerommeld met code maar ik ben er nog niet uit

spoiler:

Iets aan het doen met het bijhouden van de unieke wedstrijden (dus 2x player position en score) maar daar gaat het 1 en ander goed mis, misschien vanavond weer eens verder kijken.

[Soultaker]

ydderf schreef op dinsdag 21 december 2021 @ 15:40:

spoiler:

Bij mij blijft de dobbelsteen onder de 100, dus dat ik niks heb gemaakt om na 100 opnieuw te beginnen bij 1 heeft geen probleem gegeven.

Dit komt doordat

spoiler:

het aantal zijden op de dobbelsteen, 100, een veelvoud is van het aantal plaatsen op het bord, 10, en zowel de dobbelsteen als het bord rondlopen (na 100 komt 1 voor de dobbelsteen, na 10 komt 1 op het bord).

Bijvoorbeeld als je op plaats 7 staat, dan maakt het niet uit of je 1 of 11 of 101 of 1001 of 1234567891 gooit, je komt hoe dan ook op plaats 8 uit. Als je de wraparound voor het bord correct hebt geïmplementeerd hoef je het voor de dobbelsteen dus niet meer te doen.

[Creepy]

En dag 21 ook klaar: https://github.com/CodeEn...er/aoc/aoc2021/Day21.java

Ik had een break staan en dat had een continue moeten zijn, affijn

[Creepy]

armageddon_2k1 schreef op dinsdag 21 december 2021 @ 14:00:

spoiler:

Geen recursie of dynamic programming voor mij. Ik heb een CountingSet gemaakt, wat eigenlijk gewoon een set is, maar waarvan bijgehouden wordt hoeveel keren een item voorkomt. In die set worden de turns bijgehouden, welke eigenlijk gewoon (player1Pos, player2Pos, player1Score, player2Score, turn) is, waar turn in dit geval een boolean is van wie er aan de gang is.

Dan, gewoon loopen door de set en alle items eruit halen en hun volgende stappen allemaal bepalen en weer terugplaatsen in de set, maar met de count van de vorige. Dus als een turn A 12X voorkomt, dan worden z'n 27 volgende stappen ook 12x toegevoegd. Als die al bestonden in de set worden ze daaraan toegevoegd.

Als een turn 'finished' is (dus een score >= 21) dan wordt ie uit de set gehaald en in een finished CountingSet gestopt.

.

Ik doe hetzelfde, nu snap ik je duimpje. Thanks

[armageddon_2k1]

Creepy schreef op dinsdag 21 december 2021 @ 20:53:
[...]

Ik doe hetzelfde, nu snap ik je duimpje. Thanks

Ik stel me nu voor dat je je uren afvraagt waarom je in Gods naam een duimpje van me gekregen had

Maar je was inderdaad op het juiste pad.

[Devilfish]

Leuke game weer vandaag. Al eerder opgelost vandaag, maar wou de code nog even mooi maken en was de push vergeten te doen .

Dag 21 in C#

spoiler:

Een goede hash bedenken ging me niet heel makkelijk af, en ik in het begin ging ik nog even uit van de verkeerde startspeler Deel 2 gaat op een 4 jaar oude laptop in 160ms, ik ben tevreden .

[armageddon_2k1]

Devilfish schreef op dinsdag 21 december 2021 @ 21:28:
Leuke game weer vandaag. Al eerder opgelost vandaag, maar wou de code nog even mooi maken en was de push vergeten te doen .

Dag 21 in C#

spoiler:

Een goede hash bedenken ging me niet heel makkelijk af, en ik in het begin ging ik nog even uit van de verkeerde startspeler Deel 2 gaat op een 4 jaar oude laptop in 160ms, ik ben tevreden .

Mijn 4 jaar oude laptop is een i7 met 32GB geheugen en een 512GB SSD Is dat langzaam?

[DataGhost]

armageddon_2k1 schreef op dinsdag 21 december 2021 @ 21:41:
[...]


Mijn 4 jaar oude laptop is een i7 met 32GB geheugen en een 512GB SSD Is dat langzaam?

Mijn 11 jaar oude laptop heeft ook een i7 met 32GB geheugen en 1TB+512GB SSD. Toch is 'ie niet snel, want het is slechts een i7-2820QM.

[MrHaas]

Leuke vandaag!

spoiler:

Ik houd gevulde cuboids bij en check voor elke nieuwe regel met welke al gevulde cuboids deze overlap heeft. Die met overlap splits ik in 0-6 nieuw cuboids zodat er nooit overlaps zijn in mn lijst. Achteraf is het dan gewoon de som van alle punten in een cuboid.

Enorm verbose en snel in elkaar geflanste Python oplossing: https://github.com/arjand...ain/python/22/solution.py

[P_Tingen]

MrHaas schreef op woensdag 22 december 2021 @ 08:00:
Leuke vandaag!

spoiler:

Ik houd gevulde cuboids bij en check voor elke nieuwe regel met welke al gevulde cuboids deze overlap heeft. Die met overlap splits ik in 1-8 nieuw cuboids zodat er nooit overlaps zijn in mn lijst. Achteraf is het dan gewoon de som van alle punten in een cuboid.

Enorm verbose en snel in elkaar geflanste Python oplossing: https://github.com/arjand...ain/python/22/solution.py

spoiler:

Ja, zo'n soort oplossing had ik ook al bedacht. De tekst nodigt heel erg uit om een array aan te leggen van actieve cubes, maar dat herken ik inmiddels. Bovendien waren de coordinaten van in de 50-duizend range al een hint dat dat niet een schaalbare oplossing zou zijn. Werkt overigens waarschijnlijk prima voor deel 1.

[Asgardian28]

Ja hij was leuk vandaag en deel 2 ook echt een breinbrekertje! En een record: deel 1 in 6:06 opgelost (plek 119). Met 14 seconden sneller was het helemaal kers op de taart met top 100

spoiler:

Deel 2 ging dan wel weer minder, eerst lang moeten nadenken over de aanpak. Uiteindelijk ben ik daar tevreden over: Overlap met alle voorgaande kubussen bepalen en die dan omgekeerd toevoegen (dus uit wordt aan en aan wordt uit. Zo zit ik nooit met kubussen splitsen oid, hoef alleen overlap te bepalen.

Alleen flink wat tijd bezig geweest met een bug, m'n code nam geen overlap mee als de kubus een andere kubus helemaal omvatte (checkte alleen of de ene kubus binnen de ander lag, maar dat ging mis als de ene kubus groter is dan de andere)

Python code

[ Voor 4% gewijzigd door Asgardian28 op 22-12-2021 08:49 ]

[TrailBlazer]

Ik wist gewoon bij het oplossen van deel 1 dat ik deel2 opnieuw moest beginnen

[ydderf]

Dit is een leuke ja. Toen ik deel 1 las met het ontbijt, dacht ik dat is een makkie. Maar wanneer je hem niet met een simpele brute force wil oplossen, dan zit er nog wat meer achter. Dus ik ben nog ff aan het puzzelen....

spoiler:

De brute force is met drie for loopjes door de x-, y-, en z- range heen lopen en per coördinaat op te slaan wanneer de lamp aan moet.
Met mijn slimme manier dacht ik om te tellen hoeveel punten er in een step geactiveerd worden en hierbij te corrigeren met de overlap van de eerdere cubussen. Maar wanneer een step overlap heeft met meerdere voorgaande (die ook weer overlappen), dan moet je niet alle punten dubbel corrigeren.

Ben benieuwd wat deel twee wordt. Vermoed dat de max regio sowieso komt te vervallen, waardoor een brute force drie dagen gaat duren....

[Mschamp]

Deel 1 ging vlot. Bij deel 2 met mijn ogen open in de val gelopen

[Cranzai]

Aii, zo lekker begonnen met de kalender, helaas hebben wat serieuze werkzaamheden mij ingehaald dus nu al sinds dag 18 hem moeten laten lopen. Hopelijk dit weekend weer een paar puzzeltjes oplossen.

[P_Tingen]

Mschamp schreef op woensdag 22 december 2021 @ 09:47:
Deel 1 ging vlot. Bij deel 2 met mijn ogen open in de val gelopen

Haha, toen ik de opgave las wist ik al dat die zou komen, dus ik was al begonnen aan een iets geavanceerdere aanpak. Halverwege bedacht ik dat het misschien toch handig was om eerst in de val te springen zodat ik in ieder geval kan zien wat ik voor deel 2 moet doen. Nou ja, dat weet ik dus nu.

[Remcoder]

Ik heb inmiddels wel conceptueel in mijn hoofd wat ik moet doen, maar nu nog dat concept uit mijn hoofd en in de code krijgen...

spoiler:

Ik ben nu van plan om een lijst van cubes bij te houden die al verwerkt zijn, en dan voor elke volgende cube te kijken of die een overlap heeft met een van de andere cubes. Zo ja moet ik dan bepalen welke nieuwe cubes eruit voort komen die aan staan en die in de lijst stoppen, en de oude cuibe uit de lijst halen.Als die geen overlap heeft en een on cube is stop ik hem gewoon in de lijst, is het een off cube zonder overlap kan ik hem negeren.

[Diderikdm]

Remcoder schreef op woensdag 22 december 2021 @ 10:41:
Ik heb inmiddels wel conceptueel in mijn hoofd wat ik moet doen, maar nu nog dat concept uit mijn hoofd en in de code krijgen...

spoiler:

Ik ben nu van plan om een lijst van cubes bij te houden die al verwerkt zijn, en dan voor elke volgende cube te kijken of die een overlap heeft met een van de andere cubes. Zo ja moet ik dan bepalen welke nieuwe cubes eruit voort komen die aan staan en die in de lijst stoppen, en de oude cuibe uit de lijst halen.Als die geen overlap heeft en een on cube is stop ik hem gewoon in de lijst, is het een off cube zonder overlap kan ik hem negeren.

Dit heb ik inderdaad ook in mijn hoofd! Vanavond maar eens een poging wagen

[Creepy]

P_Tingen schreef op woensdag 22 december 2021 @ 10:33:
[...]

Haha, toen ik de opgave las wist ik al dat die zou komen, dus ik was al begonnen aan een iets geavanceerdere aanpak. Halverwege bedacht ik dat het misschien toch handig was om eerst in de val te springen zodat ik in ieder geval kan zien wat ik voor deel 2 moet doen. Nou ja, dat weet ik dus nu.

[Afbeelding]

Precies dit

Ik denk dat ik een oplossing heb, nu nog tijd vinden om hem goed uit te werken

spoiler:

Per cuboid bijhouden of het aan/uit is, en vervolgens cuboid gaan splitsen.
- Overlap in een hoek? Dan worden de 2 cuboids er 7.
- Geen overlap? Dan blijven het er 2
- Nieuwe cuboid valt volledig binnen een vorige? Dan worden de 2 cuboids er 7.
- Nieuwe cuboid valt volledig over een oude cuboid heen? Oude cuboid vervalt.

Even dat splitsen goed uitdenken

[DataGhost]

TrailBlazer schreef op woensdag 22 december 2021 @ 09:14:
Ik wist gewoon bij het oplossen van deel 1 dat ik deel2 opnieuw moest beginnen

Ik hoopte dat ik niet dezelfde "fout" zou maken als gisteren, gelukkig was de gok nu wel goed. Deel 2 enkele seconden na deel 1 goed ingestuurd

Members only:

Alleen zichtbaar voor ingelogde gebruikers. Inloggen

Direct na het oplossen van deel 1 (en voor het opsturen) heb ik wat ik dacht dat deel 2 zou zijn even laten draaien en die was ook in een paar honderd milliseconden klaar gelukkig, dus ik wist dat ik in dat opzicht goed zat. Lang geleden heb ik in een programmeerwedstrijd een enigszins vergelijkbare opgave gehad die ik uiteindelijk als enige heb opgelost (dmv bruteforce, omdat de tijdslimiet net iets te ruim stond maar dat was zeker niet de juiste aanpak en kreeg een opgetrokken wenkbrauw toegeworpen dat het toch gelukt was), ik kreeg direct flashbacks daarnaar en dacht dat ik daar niet nogmaals mee weg zou komen. De aanpak die ik nu heb gebruikt is in principe nog steeds kwadratisch in het aantal instructies maar dat was hier goed genoeg. Ik denk dat er nog snellere algoritmes mogelijk zijn maar ik vermoed dat die worst-case nog steeds kwadratisch zijn. Tenminste, ik kan inputs verzinnen die dat zijn op wat ik in m'n hoofd heb zitten.
Anyway, hij is gelukt vandaag, dus houden we het daar even op.

[ Voor 61% gewijzigd door DataGhost op 22-12-2021 11:54 ]

[Woy]

Ik heb gisteren 8, 9, 10 en 11 gedaan, maar ik merk dat ik een stuk minder zin heb om mijn oplossingen netjes te maken en te optimaliseren aangezien ik nog meerdere dagen te doen heb

Anyhow :
https://github.com/rverst.../blob/main/Y2021/Day08.cs
https://github.com/rverst.../blob/main/Y2021/Day09.cs
https://github.com/rverst.../blob/main/Y2021/Day10.cs
https://github.com/rverst.../blob/main/Y2021/Day11.cs

[ Voor 44% gewijzigd door Woy op 22-12-2021 12:13 ]

[Varienaja]

spoiler:

Balken bij elkaar optellen is hetzelfde als van elkaar aftrekken:
(1,1,1) - (10,10,10) (inhoud 1000) plus (1,1,1) - (5,5,5) (inhoud 125) --> 1000 - 125 + 125 = 1000
(1,1,1) - (10,10,10) (inhoud 1000) eraf (1,1,1) - (5,5,5) (inhoud 125) --> 1000 - 125 = 875

Omdat je overlappen maar 1x tellen moet, moet je moet dus sowieso aftrekken. Optellen moet alleen als de lampjes in de Balk 'aan' zijn.

Mijn (pseudo) code voor onderdeel 2 is dus:

foreach (Balk b : input) {
existingBalken.forEach(existingBalk.minus(b));
if (b.on) existingBalken.add(b);
}


Linkje komt later. Ik zit nu op het werk, zonder toegang tot Github.

[Janoz]

Varienaja schreef op woensdag 22 december 2021 @ 13:54:
een algoritme..

Oh, die is nice

spoiler:

In mijn oplossing ben ik al mijn blokjes op gaan knippen om ze vervolgens toe te voegen of weg te halen. In een eerste poging knipte ik alles op zodra er een collision was, maar dat was te langzaam. Bij mijn huidige oplossing wordt bij een collision maar 1 van beide opgeknipt en gedeeltelijk toegevoegd danwel verwijderd.

Maar zoals altijd blijkt bij een te langzaam algoritme is dat er teveel data onthouden wordt. Ik hoef niet te weten welke aan staan, alleen maar hoeveel.

[Remcoder]

Ik zie door de bomen het bos niet meer...

Kan iemand me een duwtje in de juiste richting geven en vertellen wat de resulterende cubes van de eerste intersectie uit het voorbeeld is?

Dan bedoel ik deze intersectie:

code:

on x=-5..47,y=-31..22,z=-19..33
on x=-44..5,y=-27..21,z=-14..35

spoiler:

Mijn algoritme neemt de eerste cube als bestaand, en de tweede cube wordt gebruikt om daar cubes af te snijden zodat er een "gat" ontstaat van het formaat van de tweede cube.

De tweede cube moet dan samen met de overige stukken van de eerste cube als nieuwe cubes toegevoegd worden aan de lijst met verwerkte cubes.

Dit uitsnijden loopt waarschijnlijk ergens fout, maar ik zie het niet meer...

[KabouterSuper]

Remcoder schreef op woensdag 22 december 2021 @ 15:04:
Ik zie door de bomen het bos niet meer...

Kan iemand me een duwtje in de juiste richting geven en vertellen wat de resulterende cubes van de eerste intersectie uit het voorbeeld is?

Dan bedoel ik deze intersectie:

code:

on x=-5..47,y=-31..22,z=-19..33
on x=-44..5,y=-27..21,z=-14..35

spoiler:

Mijn algoritme neemt de eerste cube als bestaand, en de tweede cube wordt gebruikt om daar cubes af te snijden zodat er een "gat" ontstaat van het formaat van de tweede cube.

De tweede cube moet dan samen met de overige stukken van de eerste cube als nieuwe cubes toegevoegd worden aan de lijst met verwerkte cubes.

Dit uitsnijden loopt waarschijnlijk ergens fout, maar ik zie het niet meer...

spoiler:

Intersectie is max van start coördinaten tot min van eindcoordinaten.
Dus in jouw voorbeeld: x=-5..5,y=-27,21,z=-14,33

Of bedoel je de union stiekem? Dan kan met verschillende cuboides, bijvoorbeeld:

spoiler:

x=-5..47,y=-31..22,z=-19..-15
x=-5..47,y=-31..-28,z=-14..33
x=-5..47,y=22..22,z=-14..33
x=6..47,y=-27..21,z=-14..33
x=-44..5,y=-27..21,z=-14..35

[ Voor 10% gewijzigd door KabouterSuper op 22-12-2021 15:16 ]

[Remcoder]

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

spoiler:

Intersectie is max van start coördinaten tot min van eindcoordinaten.
Dus in jouw voorbeeld: x=-5..5,y=-27,21,z=-14,33

Of bedoel je de union stiekem? Dan kan met verschillende cuboides, bijvoorbeeld:

spoiler:

x=-5..47,y=-31..22,z=-19..-15
x=-5..47,y=-31..-28,z=-14..33
x=-5..47,y=22..22,z=-14..33
x=6..47,y=-27..21,z=-14..33
x=-44..5,y=-27..21,z=-14..35

spoiler:

Waar haal je die 6 in x=6..47,y=-27..21,z=-14..33 vandaan? En de overige afwijkende getallen, 22, -28, etc...

[P_Tingen]

Remcoder schreef op woensdag 22 december 2021 @ 15:21:
[...]

spoiler:

Waar haal je die 6 in x=6..47,y=-27..21,z=-14..33 vandaan? En de overige afwijkende getallen, 22, -28, etc...

spoiler:

De grenzen van de cuboids zijn inclusief, dus als je een split ligt op een cuboid die eindigt op x = 5, dan begint de aangrenzende cuboid op x = 6

[Remcoder]

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

spoiler:

Intersectie is max van start coördinaten tot min van eindcoordinaten.
Dus in jouw voorbeeld: x=-5..5,y=-27,21,z=-14,33

Of bedoel je de union stiekem? Dan kan met verschillende cuboides, bijvoorbeeld:

spoiler:

x=-5..47,y=-31..22,z=-19..-15
x=-5..47,y=-31..-28,z=-14..33
x=-5..47,y=22..22,z=-14..33
x=6..47,y=-27..21,z=-14..33
x=-44..5,y=-27..21,z=-14..35

Ik bedoelde trouwens wat het resultaat is als je de tweede cube uit de eerste cube snijdt, welke cubes er dan uit de eerste cube voortkomen.

Ik krijg namelijk resultaten die hierop lijken.

[Soultaker]

Dag 22:

spoiler:

Ik wil de mensen die bezig zijn met balk-balk-intersectie niet ontmoedigen, maar je kunt ook simpelweg de coordinaten reduceren (e.g. {1,5,10} wordt {0,1,2}). Dat levert een oplossing op die O(N⁴) tijd en O(N³) ruimte nodig heeft, wat niet heel elegant is, maar met een invoer van 420 regels is dat haalbaar.

Python code met numpy draait in ongeveer 1,5 seconde. De variant in puur Python is een heel stuk trager (en gebruikt aanzienlijk meer geheugen!)

[Janoz]

@Remcoder

spoiler:

Ik heb mijn cubes zo gebouwd dat ze tot de max lopen, niet tot en met. Bij het inlezen heb ik er dus +1 bij gezet. Bedenk trouwens ook dat de ranges niet perse oplopen gedefinieerd zijn

[KabouterSuper]

Remcoder schreef op woensdag 22 december 2021 @ 15:45:
[...]

Ik bedoelde trouwens wat het resultaat is als je de tweede cube uit de eerste cube snijdt, welke cubes er dan uit de eerste cube voortkomen.

Ik krijg namelijk resultaten die hierop lijken.

spoiler:

De laatste in het rijtje is de tweede cube, de rest is de eerste cube die uitgesneden is. Ik snij de data cube in maximaal 6 stukken.

[ Voor 3% gewijzigd door KabouterSuper op 22-12-2021 16:25 ]

[KabouterSuper]

Dubbelpost

[ Voor 94% gewijzigd door KabouterSuper op 22-12-2021 16:24 ]

[joppybt]

Soultaker schreef op woensdag 22 december 2021 @ 15:46:
Dag 22:

spoiler:

Ik wil de mensen die bezig zijn met balk-balk-intersectie niet ontmoedigen, maar je kunt ook simpelweg de coordinaten reduceren (e.g. {1,5,10} wordt {0,1,2}). Dat levert een oplossing op die O(N⁴) tijd en O(N³) ruimte nodig heeft, wat niet heel elegant is, maar met een invoer van 420 regels is dat haalbaar.

Python code met numpy draait in ongeveer 1,5 seconde. De variant in puur Python is een heel stuk trager (en gebruikt aanzienlijk meer geheugen!)

spoiler:

Die 'simpelweg de coordinaten reduceren' opmerking kan ik totaal niet plaatsen. Wat bedoel je daar mee?

Die numpy oplossing is wel een eyeopener: het is allemaal voorbereiding en vervolgens één aanroep van de magische np.ix_ functie?

[Janoz]

KabouterSuper schreef op woensdag 22 december 2021 @ 16:21:
[...]

spoiler:

De laatste in het rijtje is de tweede cube, de rest is de eerste cube die uitgesneden is. Ik snij de data cube in maximaal 6 stukken.

spoiler:

Ik heb het mezelf lekker makkelijk gemaakt en snij de kubus in maximaal 27 stukken

[Remcoder]

KabouterSuper schreef op woensdag 22 december 2021 @ 16:21:
[...]

spoiler:

De laatste in het rijtje is de tweede cube, de rest is de eerste cube die uitgesneden is. Ik snij de data cube in maximaal 6 stukken.

spoiler:

Er zit sowieso denk ik ergens een verschil in volgorde van zijden die we afsnijden, maar ik kom op de volgende output uit:

x=-44..5,y=-27..21,z=-14..35
x=6..47,y=-31..22,z=-19..33
x=-5..5,y=-31..-28,z=-19..33
x=-5..5,y=22..22,z=-19..33
x=-5..5,y=-27..21,z=-19..-15

Zoals je ziet zit er een plat vlak in, wat dan weer niet hoort te gebeuren.

[KabouterSuper]

Janoz schreef op woensdag 22 december 2021 @ 16:53:
[...]

spoiler:

Ik heb het mezelf lekker makkelijk gemaakt en snij de kubus in maximaal 27 stukken

spoiler:

Haha, ik was te lui om dat uit te denken. Ik snij eerst de z-plakken eraf, dan de y-plakken, dan de x-plakken.

Remcoder schreef op woensdag 22 december 2021 @ 16:54:
[...]

spoiler:

Er zit sowieso denk ik ergens een verschil in volgorde van zijden die we afsnijden, maar ik kom op de volgende output uit:

x=-44..5,y=-27..21,z=-14..35
x=6..47,y=-31..22,z=-19..33
x=-5..5,y=-31..-28,z=-19..33
x=-5..5,y=22..22,z=-19..33
x=-5..5,y=-27..21,z=-19..-15

Zoals je ziet zit er een plat vlak in, wat dan weer niet hoort te gebeuren.

Dat platte vlak komt wel erg bekend voor hoor. Als de inhoud van jouw kubussen en mijn kubussen hetzelfde is, zal het wel kloppen.

[Remcoder]

KabouterSuper schreef op woensdag 22 december 2021 @ 16:59:
[...]

spoiler:

Haha, ik was te lui om dat uit te denken. Ik snij eerst de z-plakken eraf, dan de y-plakken, dan de x-plakken.

[...]

Dat platte vlak komt wel erg bekend voor hoor. Als de inhoud van jouw kubussen en mijn kubussen hetzelfde is, zal het wel kloppen.

Toch zit er ergens nog een fout in, want met de testdata kom ik al op een getal uit wat ruim 3x zoveel is...

Expected :2758514936282235
Actual :7533904187235546

[joppybt]

Janoz schreef op woensdag 22 december 2021 @ 16:53:
[...]

spoiler:

Ik heb het mezelf lekker makkelijk gemaakt en snij de kubus in maximaal 27 stukken

spoiler:

Daar begon ik ook mee maar dan heb je 27 in plaats van 6 kansen op tikfouten en off-by-one errors. Bovendien explodeerde dat nog steeds veel te hard qua performance.
Uiteindelijk toch ook maar de 6-blok variant gemaakt. Die is bij mij klaar in 33 milliseconde :-)

[Remcoder]

Wel, dinner time, daarna verder krassen.

Mocht iemand zich geroepen voelen en de bug willen vinden, mijn code staat hier, ik bied eeuwige dank voor de gouden tip!

Members only:

Alleen zichtbaar voor ingelogde gebruikers. Inloggen

[Diderikdm]

Python dag 22

drie keer in cirkels gegaan en herschreven omdat ik een typfout in een variabele over het hoofd zag

Zou hier wellicht nog wat generiekers van kunnen/willen maken..

Vond het overigens wel een leuke puzzel! Deed me wel een beetje denken aan dag 19 met 3d-scaping

[ Voor 14% gewijzigd door Diderikdm op 22-12-2021 17:48 ]

[DataGhost]

Varienaja schreef op woensdag 22 december 2021 @ 13:54:
[algo]
Linkje komt later. Ik zit nu op het werk, zonder toegang tot Github.

Euhhhh, gaat dat altijd goed? Wat geeft 'ie voor uitkomst bij

spoiler:

on x=10..12,y=10..12,z=10..12
on x=11..13,y=11..13,z=11..13
off x=9..11,y=9..11,z=9..11
off x=10..11,y=10..11,z=10..11

?

[Lisper]

Ik moet deel 1 nog oplossen, ik had de oplossing voor de puzzel van een paar jaar terug waar ze naar verwezen uit het stof gehaald, maar had daar helaas niks aan.

spoiler:

Ik ga het proberen met een tree van axis-aligned bounding boxes, waarbij ik in iedere node bij hou of de box on of off staat

[Janoz]

@joppybt & @KabouterSuper mwah

spoiler:

De 27 methode was juist een stuk makkelijker. voor elke as de 4 punten pakken en uniek sorteren. binnen 3 geneste lusjes alle blokjes tussen die vlakken maken en vervolgens kijken in welke van de originele blokken ze horen. Eigenlijk had ik dus zelfs 64 blokjes , maar doordat ik al een collision methode had kon ik simpel gelijk al de blokjes wegflikkeren die er niet bij hoorden.

Door die blokjes weer in sets te steken kon ik vervolgens heel simpel met retainAll, addAll en removeAll booleaanse operaties doen.

Ik heb iig alles maar even uit lopen programeren omdat dit zeker nog wel eens terug gaat komen ooit en ik er dan alvast een eigen lib voor heb

[KabouterSuper]

Remcoder schreef op woensdag 22 december 2021 @ 17:07:
Wel, dinner time, daarna verder krassen.

Mocht iemand zich geroepen voelen en de bug willen vinden, mijn code staat hier, ik bied eeuwige dank voor de gouden tip!


***members only***

Even snel bekeken.

Haal je je existing cube weg nadat je de nieuwe cubes hebt toegevoegd?

En klopt je doCubesOverlap wel? Wat als startx<other.startx en endx>other.endx.? Dan overlap je wel, maar dit lijkt niet uit je functie te komen.

[Varienaja]

Java dag 22

DataGhost schreef op woensdag 22 december 2021 @ 17:13:
Euhhhh, gaat dat altijd goed? Wat geeft 'ie voor uitkomst bij

spoiler:

on x=10..12,y=10..12,z=10..12
on x=11..13,y=11..13,z=11..13
off x=9..11,y=9..11,z=9..11
off x=10..11,y=10..11,z=10..11

?

38

spoiler:

Mijn redenatie is redelijk simpel: Wanneer twee Balken elkaar snijden krijg je overlap. Zijn de beide Balken 'aan', dan moet je de overlap niet dubbel tellen. Ik pas dan de bestaande Balk aan en neem er een hap uit. Als de nieuwe overlappende Balk 'uit' is, dan moet ik ook een hap uit de bestaande Balk nemen. (En de nieuwe Balk niet tellen.)

Stel je voor dat een Balk met een hap eruit nóg een overlap heeft met een derde Balk. En nog wel precies in de 'hap'. Dan stop ik een nieuwe overlap in de Balk én in de overlap die die Balk al had. De hap krijgt dus zelf weer een hap.

Nemen we liever deze input, omdat die overzichtelijker is:
on x=1..10, y=1..10, z=1..10
off x=1..5, y=1..5, z=1..5
on x=1..2, y=1..2, z=1..2

Ik begin met een 10x10x10 Balk, inhoud 1000.
Dan gaat de 5x5x5 Balk eraf. Je houdt 1000 - 125 = 875 over.
Dan komt de 2x2x2 Balk erbij. Die trek je af van de 10x10x10 Balk en van zijn hap.

De 10x10x10 is nu (1000-8) - (125-8) = 875
En we hebben de nieuwe 2x2x2 = 8
Totaal 883.

[KabouterSuper]

Janoz schreef op woensdag 22 december 2021 @ 17:43:
@joppybt & @KabouterSuper mwah

spoiler:

De 27 methode was juist een stuk makkelijker. voor elke as de 4 punten pakken en uniek sorteren. binnen 3 geneste lusjes alle blokjes tussen die vlakken maken en vervolgens kijken in welke van de originele blokken ze horen. Eigenlijk had ik dus zelfs 64 blokjes , maar doordat ik al een collision methode had kon ik simpel gelijk al de blokjes wegflikkeren die er niet bij hoorden.

Door die blokjes weer in sets te steken kon ik vervolgens heel simpel met retainAll, addAll en removeAll booleaanse operaties doen.

Ik heb iig alles maar even uit lopen programeren omdat dit zeker nog wel eens terug gaat komen ooit en ik er dan alvast een eigen lib voor heb

Het is maar wat je gemakkelijker noemt

Het voordeel van de 6 kubussen is dat het beter schaalt dan 27 (26) kubussen als er veel overlap is. Probeer maar eens 1000 kubussen die in elkaar zitten.

[DataGhost]

Varienaja schreef op woensdag 22 december 2021 @ 17:52:
Java dag 22


[...]

38

[verhaal]

Oh, maar dan doe je eigenlijk hetzelfde als wat ik (en anderen) ook doe? Ik dacht dat je bedoelde dat je

spoiler:

gewoon alleen maar per balk bijhield hoe groot 'ie was, en dat getalletje verlaagde als er een stuk balk werd uitgezet. Maar je maakt dus toch nieuwe balken.

Edit: ah ik zie je code nu. Hm. Probeer eens met van het laatste stukje wat ik postte de laatste regel een stuk of 10000 keer herhaald?

spoiler:

Die is nu 400% CPU aan het doen op mijn laptopje met nog geen antwoord na een minuut

[ Voor 18% gewijzigd door DataGhost op 22-12-2021 18:17 ]

[Janoz]

KabouterSuper schreef op woensdag 22 december 2021 @ 17:54:
[...]

Het is maar wat je gemakkelijker noemt

https://github.com/Janoz-...y2021/day22/Cube.java#L64

relatief straight forward

Het voordeel van de 6 kubussen is dat het beter schaalt dan 27 (26) kubussen als er veel overlap is. Probeer maar eens 1000 kubussen die in elkaar zitten.

Klopt, liep ik tegenaan. ik gebruikte eerst de restjes waardoor eht aantal flink opliep. Dat heb ik later aangepast door 1 van de beide cubes heel te houden. Toen was het wel werkbaar.

[Soultaker]

joppybt schreef op woensdag 22 december 2021 @ 16:48:

spoiler:

Die 'simpelweg de coordinaten reduceren' opmerking kan ik totaal niet plaatsen. Wat bedoel je daar mee?

Gedetailleerde uitleg volgt. Twee versimpelingen: ten eerste, laten we de coördinaten met het eindpunt exclusief opschrijven, dus x=[1..3] = [1,2,3] = [1..4), dat rekent makkelijker. Ten tweede: ik leg uit hoe het in 2D werkt, wat makkelijker te visualiseren is. Ik ga er vanuit dat je het zelf wel naar 3D kunt generaliseren.

spoiler:

Neem dan bijvoorbeeld de volgende input:

ON: x=[2..7) y=[1..4)
ON: x=[4..9) y=[3..6)

Dit zijn twee overlappende rechthoeken. Om het totale oppervlak te berekenen kun je gewoon een 2D bitmap nemen waarin je simpelweg elk rechthoek tekent:

. . 1 2 3 4 5 6 7 8 9
. +-------------------
1 | 0 1 1 1 1 1 0 0 0
2 | 0 1 1 1 1 1 0 0 0
3 | 0 1 1 1 1 1 1 1 0
4 | 0 0 0 1 1 1 1 1 0
5 | 0 0 0 1 1 1 1 1 0
6 | 0 0 0 1 1 1 1 1 0
7 | 0 0 0 0 0 0 0 0 0

Vervolgens tel je dan het aantal 1'en. Hetzelfde kun je natuurlijk in 3 dimensies doen, en dat werkt ook voor deel 1 (met een bitmap van 101×101×101 cellen) maar voor deel 2 wordt die bitmap natuurlijk veel te groot.

De truc is om je te beseffen dat waarden in de bitmap alleen kunnen verschillen op coördinaten die daadwerkelijk in de invoer voorkomen. De x-coordinaten in de invoer zijn 2, 4, 7, 9. De y-coordinaten zijn 1, 3, 4, 6. Dat betekent dat je aan een 4x4 bitmap genoeg hebt:

. . 2 4 7 9
. +---------
1 | 1 1 0 0
3 | 1 1 1 0
4 | 0 1 1 0
7 | 0 0 0 0

De 1 linksboven representeert dus de rechthoek x=[2..4) en y=[1..3). Alle waarden in die rechthoek moeten wel dezelfde waarde hebben want de coördinaten ertussen (x=3 of y=2) komen niet in de invoer voor.

Er is geen informatie verloren gegaan; je kunt de oorspronkelijke bitmap herleiden door rijen en kolommen te dupliceren (kolom 3 is een kopie van 2, bijvoorbeeld).

(Eigenlijk heb je zelfs aan een (4-1)x(4-1) = 3x3 matrix genoeg want de eindpunten zijn exclusief dus de laatste rij en kolom bevatten alleen nullen.)

Nu kun je op het eind niet simpelweg 1'en meer tellen; je moet voor elke cel de oppervlak van het rechthoek dat het representeert uitrekenen. De kolom [2..4) heeft breedte 4 - 2 = 2. De rij [4..7) heeft hoogte 7 - 4 = 3. En op die manier kun je voor elke cel het oppervlak uitrekenen als hoogte × breedte van de betreffende rij en kolom:

. . 2 3 2
. +----------
2 | 4 6 0 0
1 | 2 3 2 0
3 | 0 9 6 0
. | 0 0 0 0

4 + 6 + 2 + 3 + 2 + 9 + 6 = 32, wat hetzelfde is als het aantal 1en in de bitmap in het begin.

Die numpy oplossing is wel een eyeopener: het is allemaal voorbereiding en vervolgens één aanroep van de magische np.ix_ functie?

spoiler:

Wat jij voorbereiding noemt is een groot deel van het echte werk: in de for-loop worden de balkvormige gebieden gemarkeert. Daarbij doet numpy al het zware werk van het updaten van 3D subarrays. Het eindresultaat is een 3D array met 0/1 zoals hierboven.

De laatste stap is dan het berekenen van de inhoud van elke 1-cel. En daar komt de np_.ix truc van pas, wat eigenlijk een 3D outer product is (sorry, ik kan de Nederlandse term niet vinden). Feitelijk bereken ik een 3D array: inhoud[x][y][z] = lengte[x] * breedte[y] * diepte[z]

[Remcoder]

KabouterSuper schreef op woensdag 22 december 2021 @ 17:46:
[...]
En klopt je doCubesOverlap wel? Wat als startx<other.startx en endx>other.endx.? Dan overlap je wel, maar dit lijkt niet uit je functie te komen.

Held

Dat was het probleem inderdaad, die overlap miste ik.

Helaas daardoor vandaag voor deel 2 geen hogere ranking

[KabouterSuper]

Remcoder schreef op woensdag 22 december 2021 @ 19:10:
[...]

Held

Dat was het probleem inderdaad, die overlap miste ik.

De rien. Zo dicht bij de finish helpen we elkaar over de streep, toch?

[Cranzai]

Moet dag 18 nog in spoilers? Voor de zekerheid dan maar

spoiler:

Vanavond ffkes verder gepuzzeld met een binary tree. Nog niet helemaal tevreden, wil het liefste de tree in een keer opbouwen incl parent en depth maar da's vrij tricky....

Daarna nog ff goed bedenken hoe ik door de tree wil lopen.

Heb de code van DataGhost er half naast liggen maar wil het natuurlijk niet klakkeloos overnemen en wel echt begrijpen.

[Varienaja]

Bij dag 18 blijf ik het grappig vinden dat iedereen 'moeilijk' doet met trees en dergelijke. Ik doe alleen maar string-operaties. Bijna exact zoals in het voorbeeld.

[Cranzai]

Varienaja schreef op woensdag 22 december 2021 @ 20:26:
Bij dag 18 blijf ik het grappig vinden dat iedereen 'moeilijk' doet met trees en dergelijke. Ik doe alleen maar string-operaties. Bijna exact zoals in het voorbeeld.

Euhm ik heb een string versie in ontwikkeling gehad maar werd een beetje kriegel van tellen van die haakjes etc. Dat heb ik nu klaar maar om dan het juiste uit te knippen en weer in de te plakken vond ik zo'n gedoe

Edit:
Dit krabbeltje, https://github.com/Cranza...18/python/day18-string.py

[ Voor 9% gewijzigd door Cranzai op 22-12-2021 21:25 ]

[DataGhost]

Varienaja schreef op woensdag 22 december 2021 @ 20:26:
Bij dag 18 blijf ik het grappig vinden dat iedereen 'moeilijk' doet met trees en dergelijke. Ik doe alleen maar string-operaties. Bijna exact zoals in het voorbeeld.

Omdat dat niet per se de meest intuïtieve en leesbare code oplevert, het behoorlijk fragiel is, aanpassingen lastig zijn en performance vaak niet over naar huis te schrijven is. Er zijn meerdere oplossingen te bedenken, ik ben voor een boom gegaan omdat dat redelijk makkelijk redeneert en je daarmee vaste looptijden van vaak maximaal O(log n) per operatie hebt, terwijl stringmanipulaties zeer vaak naar minimaal O(n) gaan per operatie.

Er zijn zat talen waarin strings niet mutable zijn dus dat is ook een extra horde. Ik zie dat je in jouw code (disclaimer: ik gebruik nooit java) veel gebruik maakt van allerlei kopieën van strings en dat gaat echt heel snel heel diep in de papieren lopen. Het kan wel in deftige tijd met een "string" maar dan wil je het liefst alsnog een andere datastructuur gebruiken (met dezelfde representatie) die wel mutable is waardoor al die operaties een stuk goedkoper zijn. Ook handig om te weten is dat een boom met een beetje code eromheen ook gewoon in datzelfde string-formaat opgeslagen kan worden, maar dan zonder alle automatische gemakken van een boom zoals O(1) elementen invoegen en weghalen.

Deze opgave was toevallig zo "makkelijk" dat je hier nog met stringmanipulaties kon wegkomen omdat de boom altijd maar maximaal 16 elementen heeft en alle getallen maximaal 1 teken lang zijn, maar bijvoorbeeld mijn aangepaste opgave (waar de boel 16 diep mocht zitten ipv 4 diep) loopt voor geen meter omdat je dan opeens tegen 65536 elementen aan zit te kijken. Ofja, na een paar minuten crasht 'ie met een stack overflow Ook als elementen pas splitten boven de 300 ipv boven de 10 gaat dat geen makkelijke aanpassing zijn in jouw string-algoritme.

[ Voor 8% gewijzigd door DataGhost op 23-12-2021 00:55 ]

[Diderikdm]

Eerste deel met de hand opgelost vandaag, deel twee wil ik niet proberen op deze manier

[ydderf]

Gisteren deel 1 wel afgerond (brute force methode), maar deel twee kwam ik vast te zitten om mijn oplossing in mijn hoofd, om te zetten naar code. Vooral bij meerdere overlappen liep ik vast.

Voor de dag van vandaag heb ik deel 1 al opgelost zonder ook maar 1 regel te programmeren. Maar bij deel twee geeft hij dat mijn antwoord te laag is. Ik denk dat ik dat maar interpreteer als "ik heb een betere oplossing gevonden dan de maker?"
Straks maar eens kijken of ik het ook nog met een stukje code kan oplossen....

[MrHaas]

Diderikdm schreef op donderdag 23 december 2021 @ 07:58:
Eerste deel met de hand opgelost vandaag, deel twee wil ik niet proberen op deze manier

Same here en deel 2 ook, plaats 48 op global leaderboard

[Woy]

Ik heb gisteren weer 3 dagen gedaan

https://github.com/rverst.../blob/main/Y2021/Day12.cs
https://github.com/rverst.../blob/main/Y2021/Day13.cs
https://github.com/rverst.../blob/main/Y2021/Day14.cs

Bij dag 13 vind ik het toch wel wat jammer dat ik bij deel 2 niet echt de uitkomst print, maar alleen de pixels, maar had geen zin om dat om te zetten naar de daadwerkelijke characters.

Op dit tempo ga ik het helaas niet halen om op eerste kerstdag ook daadwerkelijk klaar te zijn, maar mijn doel is wel om het dit jaar nog af te kunnen ronden.

[Woy]

MrHaas schreef op donderdag 23 december 2021 @ 08:16:
[...]


Same here en deel 2 ook, plaats 48 op global leaderboard

Nice, jij gaat er dus ook echt vroeg voor zitten

[Diderikdm]

MrHaas schreef op donderdag 23 december 2021 @ 08:16:
[...]


Same here en deel 2 ook, plaats 48 op global leaderboard

Woot net ook deel twee met de hand haha

Lekker global leaderboard wel!

[ Voor 6% gewijzigd door Diderikdm op 23-12-2021 08:38 ]

[MrHaas]

Diderikdm schreef op donderdag 23 december 2021 @ 08:27:
[...]


Woot net ook deel twee met de hand haha

Lekker global leaderboard wel!

Mja, het voelt een beetje vies, maar I'll take it