Advent of Code 2020

[Soultaker]

(Warning: off-topic post over Python syntax.)

DataGhost schreef op zondag 20 december 2020 @ 15:55:
Rechter edge:

code:

"".join([line[-1] for line in self.image])

Heerlijke feature

Het is handig om van achter te kunnen indexeren, maar ik vind het een slechte keuze om daar negatieve indices voor te gebruiken, want nu krijg je wel een IndexError als je het bereik aan de rechterkant overschrijdt, maar niet als je het aan de linkerkant overschrijdt (en omgekeerd bij a[-i]) wanneer i negatief is). Daar komen alleen maar fouten van.

De use case om a[i] te evalueren waarbij i een variabele met een negatieve waarde is, bestaat volgens mij niet (tegenvoorbeelden zijn welkom!) In de gevallen waarin i negatief is het minteken altijd al aanwezig in de broncode (in de vorm a[-1] of a[-i]).

In Python is a[i] eigenlijk syntactic sugar is voor a.__getitem__(i). Ik zou voorstellen om expressies van de vorm a[-i] op een speciale manier te parsen zodat ze vertaald worden naar a.__getitemreverse__(i) ofzoiets. Dan zou je ook direct vanaf 0 kunnen tellen zodat a[-0] het laatste element is (wat veel logischer is, want dan geldt: a[-x] == list(reversed(a))[x]).

Python:

a = [0,1,2]
a[0]  #  OK, eerste element
a[3]  # IndexError
a[-1]  # IndexError
a[-0]  # OK, laatste element
a[-(-1)]  # IndexError
a[-3]  # IndexError

Nu kun je zeggen dat het verwarrend is dat a[0] == a[(-0)] != a[-0]. Om die verwarring weg te nemen zou je ook nieuwe syntax als b.v. a[<i] of a[!i] kunnen introduceren. Dan is a[!0] + a[!1] dus b.v. de som van de laatste twee elementen. Dat heeft i.m.o. alle voordelen van het huidige systeem zonder enige van de nadelen.

[Varienaja]

Daanoz schreef op zondag 20 december 2020 @ 16:44:
Er kwamen zeer bijzondere figuren uit

Ik was vanmorgen begonnen passende stukjes aan elkaar te plakken zonder er op te letten dat de puzzel vierkant moet worden. Dat gaf ook bijzondere vormen (en frustraties natuurlijk ook).

[ZieglerNichols]

Varienaja schreef op zondag 20 december 2020 @ 16:56:
[...]
Ik was vanmorgen begonnen passende stukjes aan elkaar te plakken zonder er op te letten dat de puzzel vierkant moet worden. Dat gaf ook bijzondere vormen (en frustraties natuurlijk ook).

Ik ben er eigenlijk niet vanuit gegaan dat de puzzel vierkant moet zijn, dus mijn code zou ook moeten werken voor alle rechthoekige puzzels. Waarom zou het vierkant moeten worden?

[Woy]

Zo ik heb hem ook klaar. Ik moet eigenlijk nog wel een keer een refactor doen om het wat netter te maken, en het kan nog wel wat efficienter op sommige plekken, maar voor nu is het even prima:

https://github.com/rverst.../blob/main/Y2020/Day20.cs

Grootste fout die ik maakte was dat ik bij het printen voor debuggen precies de inverse printe, en ik dus even verbaasd was dat mijn image totaal niet overeen kwam met het voorbeeld

[Woy]

Qua performance is het op zich wel prima, al kopieer ik af en toe nog wel wat te veel

code:

|   Method | Day |       Mean |   Error |  StdDev |
|--------- |---- |-----------:|--------:|--------:|
| RunPart1 |  20 |   297.4 us | 0.91 us | 0.86 us |
| RunPart2 |  20 | 2,648.6 us | 8.62 us | 8.06 us |

[evanraalte]

Ik zit vast in het voorbeeld bij D19P2. Ik heb mijn originele programma al recursief beschreven, en ik krijg inderdaad 3 correcte oplossingen met de oude regels. Echter krijg ik 6 ipv 12 oplossingen bij de nieuwe regels. Ik heb niet het idee dat mijn recursie incorrect is, maar misschien staar ik er al te lang naar. Heeft iemand een hint voor mij?

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

[DataGhost]

evanraalte schreef op zondag 20 december 2020 @ 18:25:
Ik zit vast in het voorbeeld bij D19P2. Ik heb mijn originele programma al recursief beschreven, en ik krijg inderdaad 3 correcte oplossingen met de oude regels. Echter krijg ik 6 ipv 12 oplossingen bij de nieuwe regels. Ik heb niet het idee dat mijn recursie incorrect is, maar misschien staar ik er al te lang naar. Heeft iemand een hint voor mij?

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

Zonder naar je code te kijken denk ik

spoiler:

dat je bij een eerste match al stopt met zoeken, terwijl je daarmee verderop niet meer uitkomt.

Deze case gaat bij jou mis (alleen kijken als je er met de eerste spoiler niet uitkomt):

spoiler:

0: 1 2
1: 3 | 3 1
2: 3 4
3: "a"
4: "b"

aaab

spoiler:

Ik had eerst ook 6 ipv 12

[ydderf]

Gisteren Dag 18 afgerond. Vooral voor deel 2 een tijd aan het stoeien geweest.
Vandaag dag 19 geprobeerd. Maar bij deel 1 klopt de test input wel, maar de echte input klopt nog niet. En kwam er met debuggen nog niet uit waar het mis ging, dus maar verder gegaan met dag 20. Hier voor deel 1 het antwoord gevonden m.b.v. een shortcut, dus voor deel twee heb ik nog wat extra werk. Ben bang dat dat vandaag niet meer gaat lukken.

spoiler:

voor dag 20 deel 1, heb ik voor elke zijde van een tile een getal gemaakt en voor elke gespiegelde zijde een getal gemaakt (bineaire code omzetten naar int). En vervolgens gecontroleerd voor elke tile, hoeveel zijdes overeenkomen met zijdes van andere tiles. Alleen op de hoeken zouden er twee zijdes moet passen.
Helaas heb ik hiermee geen enkel idee hoe de rest van de tiles geplaatst moeten worden om het monster te plaatsen....

[Verwijderd]

joppybt schreef op zaterdag 19 december 2020 @ 18:04:
Ik heb deel twee uiteindelijk brute force opgelost

spoiler:

8: 42 | 42 8 kun je interpreteren als: één of meer keer 42 ('x' keer)
11: 42 31 | 42 11 31 kun je interpreteren als één of meer keer 42 ('y' keer) gevolgd door even vaak 31

Omdat 8 en 11 bij mij (en iedereen?) alleen bij stap 0 voorkomen probeer ik gewoon alle combinaties van x en y als uitgewerkte stap 0

Ik probeer dus voor stap 0 (maximaal input string lengte)
42 . 42 31
42 . 42 42 31 31
42 . 42 42 42 31 31 31
42 . 42 42 42 31 42 31 31 31
enzovoorts en dan
42 42 . 42 31
42 42 . 42 42 31 31
42 42 . 42 42 42 31 31 31
42 42 . 42 42 42 31 42 31 31 31
enzovoorts

Het is lelijk maar mijn check-routine uit deel 1 is verder gewoon ongewijzigd.

Domme vraag misschien,maar als (tot nu toe)onbekend zijnde met regexp's, vroeg ik me af waarom rule 11 geinterpreteerd mag worden zoals hierboven beschreven?
(uiteindelijk is het met dit inzicht wel gelukt om de opgave op te lossen, maar ik zag die redenatie niet...)

[Woy]

ydderf schreef op zondag 20 december 2020 @ 19:05:
Gisteren Dag 18 afgerond. Vooral voor deel 2 een tijd aan het stoeien geweest.
Vandaag dag 19 geprobeerd. Maar bij deel 1 klopt de test input wel, maar de echte input klopt nog niet. En kwam er met debuggen nog niet uit waar het mis ging, dus maar verder gegaan met dag 20. Hier voor deel 1 het antwoord gevonden m.b.v. een shortcut, dus voor deel twee heb ik nog wat extra werk. Ben bang dat dat vandaag niet meer gaat lukken.

spoiler:

voor dag 20 deel 1, heb ik voor elke zijde van een tile een getal gemaakt en voor elke gespiegelde zijde een getal gemaakt (bineaire code omzetten naar int). En vervolgens gecontroleerd voor elke tile, hoeveel zijdes overeenkomen met zijdes van andere tiles. Alleen op de hoeken zouden er twee zijdes moet passen.
Helaas heb ik hiermee geen enkel idee hoe de rest van de tiles geplaatst moeten worden om het monster te plaatsen....

spoiler:

Ik heb deel 1 ongeveer hetzelfde gedaan, met de optimalisatie dat ik van de twee ints alleen de laagste beschouw, scheelt weer extra checks en kan ik gewoon een group by gebruiken. Dat zijn dus maar 4 waardes per tile

Nadat je een hoek hebt kun je redelijk eenvoudig bepalen hoe die gedraaid moet worden. Daarna kun je gewoon een edge pakken en kijken welke tile daar op matched zoals je in 1 gedaan hebt. Dan een kwestie van bepalen hoe hij gedraaid flipped moet worden, en dan zo door voor alle tiles

[evanraalte]

@DataGhost Thanks! Dat helpt in elk geval om het probleem wat kleiner te maken.

spoiler:

je input werkt als ik 3 1 | 3 doe, maar niet bij 3 | 3 1.. Echter, ik verwerk beide kanten. een niet valide waarde zal omhoog propageren in de recursie totdat ie bij de initiele stelling komt. Waarschijnlijk maak ik nog steeds een denk fout ergens

[DataGhost]

evanraalte schreef op zondag 20 december 2020 @ 19:30:
@DataGhost Thanks! Dat helpt in elk geval om het probleem wat kleiner te maken.

spoiler:

je input werkt als ik 3 1 | 3 doe, maar niet bij 3 | 3 1.. Echter, ik verwerk beide kanten. een niet valide waarde zal omhoog propageren in de recursie totdat ie bij de initiele stelling komt. Waarschijnlijk maak ik nog steeds een denk fout ergens

spoiler:

Het probleem is denk ik niet zozeer dat een van de kanten niet valide is, maar dat 'ie juist wel valide is.

[joppybt]

Verwijderd schreef op zondag 20 december 2020 @ 19:20:
[...]
Domme vraag misschien,maar als (tot nu toe)onbekend zijnde met regexp's, vroeg ik me af waarom rule 11 geïnterpreteerd mag worden zoals hierboven beschreven?
(uiteindelijk is het met dit inzicht wel gelukt om de opgave op te lossen, maar ik zag die redenatie niet...)

spoiler:

Je hoeft hiervoor niets van regexp's te weten
11: 42 31 | 42 11 31
Dit kun je lezen als: (42 direct gevolgd door 31) OF (42, iets ertussen, 31)
Dat 'iets ertussen' is de ons bekende 11.
Als dat 'iets ertussen' de '(42 direct gevolgd door 31)' is krijg je 42 42 31 31. Enzovoorts: er wordt steeds een extra '42 31' middenin bijgeplakt.

Hmm, als ik het zo teruglees blijft het ingewikkeld. Maar hopelijk iets duidelijker.

[evanraalte]

Ik vrees dat ik het niet ga vinden, erg frustrerend . Merk dat de puzzels wel erg lastig werden de afgelopen dagen. Waarschijnljk is het een mooi moment om te stoppen (en daadwerkelijk mentale rust te nemen in de kerstvakantie ) en volgend jaar weer te proberen. In elk geval weer erg veel geleerd dit jaar

Thanks voor de hulp @DataGhost !

[Verwijderd]

joppybt schreef op zondag 20 december 2020 @ 20:26:
[...]

spoiler:

Je hoeft hiervoor niets van regexp's te weten
11: 42 31 | 42 11 31
Dit kun je lezen als: (42 direct gevolgd door 31) OF (42, iets ertussen, 31)
Dat 'iets ertussen' is de ons bekende 11.
Als dat 'iets ertussen' de '(42 direct gevolgd door 31)' is krijg je 42 42 31 31. Enzovoorts: er wordt steeds een extra '42 31' middenin bijgeplakt.

Hmm, als ik het zo teruglees blijft het ingewikkeld. Maar hopelijk iets duidelijker.

Zeker, iets duidelijker.
Deze specifieke opgave heeft me echt hoofdbrekens gekost, maar jouw post heeft me uiteindelijk geholpen, dank daarvoor.

[Verwijderd]

evanraalte schreef op zondag 20 december 2020 @ 18:25:
Ik zit vast in het voorbeeld bij D19P2. Ik heb mijn originele programma al recursief beschreven, en ik krijg inderdaad 3 correcte oplossingen met de oude regels. Echter krijg ik 6 ipv 12 oplossingen bij de nieuwe regels. Ik heb niet het idee dat mijn recursie incorrect is, maar misschien staar ik er al te lang naar. Heeft iemand een hint voor mij?

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

Ik heb hier ook heel lang op lopen kauwen en heb uiteindelijk maar eieren voor mijn geld gekozen en de oplossing ge-brute forced,na veel waardevolle input hier op het forum.

spoiler:

wat ik gedaan heb is de extra regeltjes gelaten voor wat ze zijn (niet aangepast in de input) en de zaken met het handje in elkaar geplakt voor verschillende waardes van d Dus de regexp wordt ietsin de trend van (...ab|bb...){n}(...bb|aa...){n} waarbij de {n} bepaald hoevaak BEIDEregexpen achter elkaar voor moeten komen.
Dit moet je dan tot n=49 herhalen (proefondervindelijk..) bij die n komt er geen extra hit.


new_rules=[ '(' strrep(rules{42},' ','') ')+' ...
'(' strrep(rules{42},' ','') sprintf('){%d}', loop) ...
'(' strrep(rules{31},' ','') sprintf('){%d}', loop) ] ;

het is geschreven in matlab, mocht je het geheel willen zien (niet opgeven) hoor ikhet wel.

[FrankMennink]

Dag 20 in Python
Lekker in de val getrapt van de shortcut voor deel 1 en daarna alsnog

spoiler:

de hele image op moeten bouwen

Veel werk, maar met goed opdelen van het probleem in stukken best te doen. Resulterende code is wat... lang

[Varienaja]

Mooie opgave Dag 21. Ik denk ook een goede oplossingsmethode te hebben. Maar ik vertrek zo naar kantoor. Vanavond als ik thuiskom kan ik er echt aan beginnen. Om misschien als de baas de ander kant op kijkt..

[Dido]

Varienaja schreef op maandag 21 december 2020 @ 06:45:
Mooie opgave Dag 21. Ik denk ook een goede oplossingsmethode te hebben. Maar ik vertrek zo naar kantoor. Vanavond als ik thuiskom kan ik er echt aan beginnen. Om misschien als de baas de ander kant op kijkt..

Als je er na een kop koffie aan begint moet het in 20 minuten kunnen

Het is inderdaad een leuke opdracht vandaag, maar ik zat (koffie!) bij opdracht 1 eigenlijk opdracht 2 voor te bereiden (althans, dat donkerbruine vermoeden had ik. Was ook redelijk voorspelbaar).
En inderdaad, deel twee kwam niet onverwacht

spoiler:

Deel twee was een flashback naar de tickets van dag 16. Die had ik toen in eerste instantie handmatig gedaan

Wow, ik zie net dat ik op plaats 962 sta voor deel 2 van gisteren! Helemaal blij, maar er blijken tot nu nog maar minder dan 7000 mensen te zijn die beide delen gedaan hebben. Kennelijk viel hij zwaar

[ Voor 11% gewijzigd door Dido op 21-12-2020 07:12 ]

[ElkeBxl]

Dag 20 deel 2 zal voor een andere keer zijn. Dag 21 was zoveel leuker om te doen Mijn oplossing in TypeScript kan waarschijnlijk stuk korter maar het werkt wel.

[Dricus]

Dag 21 (Kotlin)

Dit was wel heel erg makkelijk, vergeleken met de 3 voorgaande dagen.

spoiler:

Ik kon gewoon exact dezelfde benadering gebruiken als voor dag 16. Deze was eigenlijk nog makkelijker, omdat de input minder complex is.

Voor deel 2 hoefde ik alleen maar een tussenresultaat van deel 1 te sorteren en in een string te zetten. Kind kan de was doen.

[ Voor 15% gewijzigd door Dricus op 21-12-2020 08:05 ]

[ZieglerNichols]

Ik zat een uur vast vanochtend door zo'n domme fout

spoiler:

Ik matchte ergens allergenen bij ingredienten met een 'string find' i.p.v. een 'string compare' . En in mijn allergenen lijst staat zowel fish als shellfish...

[Mschamp]

Dag 21 C#
In vergelijking met gisteren was dit zeer gemakkelijk.

[dcm360]

Nou, geef mij anders maar weer een opdracht zoals gisteren... Ik heb echt geen idee wat ik moet doen, en dat heeft zich tot zover vertaald in 2 pogingen voor deel 1 die een correct antwoord geven op het voorbeeld, maar niet voor de inputfile. Zo na een goede kop koffie nog maar eens naar kijken, misschien dat ik dan wel doorkrijg wat de puzzel nu precies vraagt.

[bakkerjangert]

Vandaag was inderdaad niet zo moeilijk. Deel 1 op de uitvoerig methode opgelost, dus na deel 2 gelezen te hebben dacht ik; eitje. Toch nog een kwartier mee bezig geweest door domme foutjes en te snel lezen.

spoiler:

Eerst had ik de allergenen als antwoord gegeven; fout! --> Ah het zijn de gesorteerde ingredienten; fout! --> Ah, op volgorde van gesorteerde allergenen; nu moet het goed zijn, maar toch fout --> F***k hoe kan dat nou? Moet goed zijn! --> Verwijdert na 10 minuten met een rood hoofd de achtergebleven sort bij het samenstellen van de ingredentienen

[armageddon_2k1]

Deze was voor mij redelijk easy!
Dag 21 in Kotlin

Kan het vast netter maken, maar geen zin

Moest wel even mijn Day interface omkatten naar een Day<T1, T2> interface

[eamelink]

Dit was eenvoudig. Bij zulke opdrachten is het altijd maar afwachten of je simpelweg deterministisch kan afstrepen, of dat je zult moeten uitproberen en backtracken. De formulering van vraag één deed me vermoeden dat het tweede het geval was:

The first step is to determine which ingredients can't possibly contain any of the allergens in any food in your list.

Ik dacht; oh, misschien is de oplossing vinden wel lastig, maar is dit wél deterministisch te doen.

Maar het viel allemaal mee

[Soultaker]

Dag 21 inderdaad niet al te moeilijk, maar ik moest wel even goed nadenken voor ik het gegeven voorbeeld überhaupt begreep (op zich niet erg).

Ook is deel 1 ongeveer 95% van het hele probleem; ik geloof niet dat er een manier is om deel 1 met een shortcut op te lossen is, zoals bij dag 20 bijvoorbeeld wel mogelijk was. Dat blijkt ook uit het leaderboard: hoge ratio van gouden sterren tot zilveren sterren.

Wat betreft het oplossingsalgoritme:

spoiler:

De "wegstreep" methode (voor elk allergeen, neem de doorsnede van alle ingrediënten van producten waar dat allergeen in voorkomt, en als er één ingrediënt overblijft, heb je een allergeen-ingrediënt-paar geïdentificeerd; herhaal totdat alle allergenen geïdentificeerd zijn) werkt voor deze invoer.

Wat ik me afvraag is of het ook in z'n algemeenheid werkt. Normaal gesproken zou ik zeggen van niet (bij het oplossen van een Sudoku puzzel werkt het wegstrepen van kandidaten bijvoorbeeld ook niet altijd) maar in dit geval staat in de opgave expliciet: “Allergens aren't always marked”. Ik vermoed dat het daardoor lastig is om complexere puzzels te maken.

Is het mogelijk om een invoer te maken die een unieke oplossing heeft, die niet via de wegstreepmethode gevonden kan worden?

[Dido]

offtopic:
En dan heb je echt ff niks beters te doen en ga je aan de haal met het leaderboard... ik weet nu op welke plek ik maximaal eindig op de huidige dag, en op welke plek ik maximaal eindig als ik vanaf nu niets meer doe (en daar doe ik het niet voor, dus dat wordt toch nog 4 keer te vroeg opstaan )

Uiteraard ervan uitgaande dat ik snap hoe dat leaderboard werkt

[Gilotto]

Eindelijk dag 7 afgerond in F#.
Vooral deel 2 was voor mij een lastige opdracht.
De berekening uitschrijven hielp uiteindelijk waardoor ik er toch uit ben gekomen

Dag 8 was weer eenvoudiger

[ Voor 17% gewijzigd door Gilotto op 21-12-2020 17:20 ]

[dcm360]

Nou, dat duurde even. Ik heb nu grofweg een idee hoe deel 1 aangepakt moet worden, en ik heb een stukje code dat dat ook ongeveer doet. Toen met wat pielen er een correct antwoord uit weten te krijgen, maar waarom het zo precies werkt begrijp ik zelf ook niet.
Deel 2 was dan wel weer een eitje.

[Daos]

dcm360 schreef op maandag 21 december 2020 @ 14:43:
Nou, dat duurde even. Ik heb nu grofweg een idee hoe deel 1 aangepakt moet worden, en ik heb een stukje code dat dat ook ongeveer doet. Toen met wat pielen er een correct antwoord uit weten te krijgen, maar waarom het zo precies werkt begrijp ik zelf ook niet.
Deel 2 was dan wel weer een eitje.

Ik had eerst ook moeite om te begrijpen wat er gedaan moest worden. Het zit zo:

spoiler:

Er is een unieke mapping tussen allergeen en ingredient. 1 allergeen komt in 1 ingredient voor. Andersom heeft 1 ingredient 0 of 1 allergenen. Neem de eerste regel uit het voorbeeld:
mxmxvkd kfcds sqjhc nhms (contains dairy, fish)
1 van die vier ingredienten bevat dairy en 1 van die vier fish. De andere twee kunnen ook een allergeen bevatten (hoeft niet)

De eerste opdracht is het zoeken van die mapping en dan tellen in je invoer hoeveel ingredienten er zijn zonder allergeen.

[Woy]

Vandaag was inderdaad weer een stuk makkelijker. In dat opzicht was Part2 eigenlijk nog makkelijker dan Part1, dus ze hadden ook wel omgedraaid kunnen worden.

https://github.com/rverst.../blob/main/Y2020/Day21.cs

[ydderf]

Ook hier dag 21 gereed. Ik moest de opdracht wel eerst ff een paar keer goed doorkijken voordat ik de oplossingsrichting snapte. Daarna lukte het programmeren wel redelijk gemakkelijk. Al kom ik wel weer tot de conclusie dat mijn kennis voor het werken met List en/of Dictionary nog te beperkt is. Tenminste in mijn oplossing heb ik altijd vrij veel for loopjes terwijl ik bij andere oplossingen wat slimmere dingen zie. Dus ik denk dat ik na de kerst maar eens wat uitwerkingen naast elkaar ga leggen om te kijken of ik kan reproduceren hoe de slimmere oplossingen werken.....

[ydderf]

Yes, nog ff snel naar dag 19 gekeken en een mooi kopieerfoutje (ofja, goed gekopieerd, slecht aangepast) gevonden, waardoor part 1 een verkeerd antwoord gaf.
Todo: Dag 19 - Part 2 & Dag 20 part 2

[Woy]

@ydderf ik zie dat je voor je oplossing voor dag 21 een lijst ingredienten opbouwt, en dan aan het einde Distinct().ToList() doet, hiervoor is het makkelijker om gewoon een HashSet<T> te gebruiken, die is al gegarandeerd unique

[dcm360]

Daos schreef op maandag 21 december 2020 @ 14:57:
[...]


Ik had eerst ook moeite om te begrijpen wat er gedaan moest worden. Het zit zo:

spoiler:

Er is een unieke mapping tussen allergeen en ingredient. 1 allergeen komt in 1 ingredient voor. Andersom heeft 1 ingredient 0 of 1 allergenen. Neem de eerste regel uit het voorbeeld:
mxmxvkd kfcds sqjhc nhms (contains dairy, fish)
1 van die vier ingredienten bevat dairy en 1 van die vier fish. De andere twee kunnen ook een allergeen bevatten (hoeft niet)

De eerste opdracht is het zoeken van die mapping en dan tellen in je invoer hoeveel ingredienten er zijn zonder allergeen.

Jup, maar dan nog in code... Ondertussen ben ik er gelukkig wel uit, en heb ik in dat proces een lap code van 50 regels terug weten te brengen naar 5 regels. Als ik het nu zie denk ik ook 'dat had ik in een kwartier kunnen bedenken', maarja, dan moet eerst dat kwartje gevallen zijn. Mijn uiteindelijke oplossing

[ydderf]

@Woy, thanks! Dat zijn inderdaad van die dingen waar ik mee loop te stoeien. Uiteindelijk om ik nog steeds waar ik moet komen, maar het is niet altijd de meest slimme oplossing. Ik had eigenlijk ook niet verwacht om uberhaubt al zo ver te komen, dus wat dat betreft valt het me dan weer niet tegen

[Hydra]

Zo! Zit vanaf vandaag een paar daagjes op een eiland (niet Java of Kotlin, Ameland ) maar gelukkig tijd kunnen vinden. Vanochtend voor vertrek de opdracht gelezen en hij viel wel mee.

Dag 21 in Kotlin

spoiler:

Had in deel 1 al de oplossing zover dat ik nog maar 1 ingredient per allergen had. Dus deel 2 was toen heel simpel.

[Hydra]

dcm360 schreef op maandag 21 december 2020 @ 16:26:
maarja, dan moet eerst dat kwartje gevallen zijn.

Story of my life. Gelukkig veel tijd om na te denken gehad vandaag

[Salandur]

joppybt schreef op zaterdag 19 december 2020 @ 18:04:
Ik heb deel twee uiteindelijk brute force opgelost

spoiler:

8: 42 | 42 8 kun je interpreteren als: één of meer keer 42 ('x' keer)
11: 42 31 | 42 11 31 kun je interpreteren als één of meer keer 42 ('y' keer) gevolgd door even vaak 31

Omdat 8 en 11 bij mij (en iedereen?) alleen bij stap 0 voorkomen probeer ik gewoon alle combinaties van x en y als uitgewerkte stap 0

Ik probeer dus voor stap 0 (maximaal input string lengte)
42 . 42 31
42 . 42 42 31 31
42 . 42 42 42 31 31 31
42 . 42 42 42 31 42 31 31 31
enzovoorts en dan
42 42 . 42 31
42 42 . 42 42 31 31
42 42 . 42 42 42 31 31 31
42 42 . 42 42 42 31 42 31 31 31
enzovoorts

Het is lelijk maar mijn check-routine uit deel 1 is verder gewoon ongewijzigd.

Thanks! Deze legt precies uit welke gedachte ik mis bij mij!

[FrankMennink]

Salandur schreef op maandag 21 december 2020 @ 20:23:
[...]

Thanks! Deze legt precies uit welke gedachte ik mis bij mij!

spoiler:

Ik heb m wat minder brute froce opgelost door ipv alle mogelijkheden van 42 gevolgd door 31, eerst 42 van de voorkant van de string afgehaald tot ik geen match meer had (en geteld hoevaak), daarna zelfde voor 31. Als aantal 42 > 31, beide > 0 en de string die overblijft == "" dan is het een match.

[ Voor 3% gewijzigd door FrankMennink op 21-12-2020 21:09 ]

[Dido]

Yes! First on Tweakers vandaag \O/

spoiler:

Die infinite prevention rule koste me wel wat moeite om te begrijpen maar bleek uiteindelijk eigenlijk heel simpel. Gelukkig draaide de naieve implementatie ook nog eens in een acceptabele tijd

[Varienaja]

spoiler:

-- Round 9 (Game 1) --
Player 1's deck: 4, 9, 8, 5, 2
Player 2's deck: 3, 10, 1, 7, 6
Player 1 plays: 4
Player 2 plays: 3
Playing a sub-game to determine the winner...

=== Game 2 ===

-- Round 1 (Game 2) --
Player 1's deck: 9, 8, 5, 2
Player 2's deck: 10, 1, 7

---> Waar is kaart 6 in Player2's deck gebleven??

Laat maar..

[bakkerjangert]

Varienaja schreef op dinsdag 22 december 2020 @ 06:54:

spoiler:

-- Round 9 (Game 1) --
Player 1's deck: 4, 9, 8, 5, 2
Player 2's deck: 3, 10, 1, 7, 6
Player 1 plays: 4
Player 2 plays: 3
Playing a sub-game to determine the winner...

=== Game 2 ===

-- Round 1 (Game 2) --
Player 1's deck: 9, 8, 5, 2
Player 2's deck: 10, 1, 7

---> Waar is kaart 6 in Player2's deck gebleven??

Laat maar..

kun je dit toelichten. Dit snap ik (ook) niet.

Never mind, lezen is ook een vak . Dank je Dido, al was ik er net zelf ook achter.

spoiler:

Klopt het voorbeeld wel? Beide spelers moeten toch evenveel ten minste evenveel kaarten over hebben als de getrokken kaart om een sub-game te starten? In het voorbeeld heeft player 2 een 3 getrokken en 4 kaarten over en toch gaan ze naar een subgame?

-- Round 9 (Game 1) --
Player 1's deck: 4, 9, 8, 5, 2
Player 2's deck: 3, 10, 1, 7, 6
Player 1 plays: 4
Player 2 plays: 3
Playing a sub-game to determine the winner...

[ Voor 6% gewijzigd door bakkerjangert op 22-12-2020 07:18 ]

[Dido]

bakkerjangert schreef op dinsdag 22 december 2020 @ 07:11:
kun je dit toelichten. Dit snap ik (ook) niet.

spoiler:

Je moet genoeg kaarten hebben voor een subgame.
Dus als speler 1 een 3 trekt moet hij 3 kaarten of meer over hebben.
En als speler 2 een 4 trekt moet hij 4 kaarten of meer over hebben.
Als dat allebei waar is, speel je pas een subgame, in dit geval met een hand van 3 en een hand van 4 kaarten.

[eamelink]

Ha, dit is net als een echt bordspel; de eerste keer dat je regels leest denk je 'Wow, ingewikkeld zeg!', en dan ga je het spelen en valt het allemaal wel mee

[Varienaja]

Niet te ingewikkeld vandaag, maar zoals altijd: JE MOET SECUUR ALLES LEZEN

De onopgeruimde code voor Dag 22.

[eamelink]

Hier dag 22 in Scala (spoiler, obviously):

https://gist.github.com/e...89a270b9dd817e9ef8dbbbbce

[ZieglerNichols]

Dag 22 in Matlab: https://pastebin.com/m5Cx0974

[Woy]

Dag 22: https://github.com/rverst.../blob/main/Y2020/Day22.cs

Ik denk dat ik er op een later moment nog een keer naar ga kijken, want ben nog niet heel content met de oplossing.

[StefanLemmens]

Dag 22 deel 2 is inderdaad een kwestie van eerst goed lezen maar eens je de opgave begrijpt wel weer goed te doen. Bij deze hoe de de recursieve game er in LabVIEW uitziet. Een keertje iets anders dan al die lijnen tekst.

spoiler:

[Dricus]

Dag 22 (Kotlin)

Allemachtig, dat duurde véél langer dan nodig . Inderdaad een kwestie van HEEL GOED LEZEN!

spoiler:

De voorwaarde voor een recursie is dus dat ÉÉN SPELER dezelfde "hand" moet hebben als een vorige ronde. Ik heb me helemaal scheel gezocht naar de fout. Dat was dus dat ik de voorwaarde van recursie had geïnterpreteerd als dat beide spelers dezelfde hand moesten hebben als een vorige ronde.

[bakkerjangert]

Dricus schreef op dinsdag 22 december 2020 @ 09:26:
Dag 22 (Kotlin)

Allemachtig, dat duurde véél langer dan nodig . Inderdaad een kwestie van HEEL GOED LEZEN!

spoiler:

De voorwaarde voor een recursie is dus dat ÉÉN SPELER dezelfde "hand" moet hebben als een vorige ronde. Ik heb me helemaal scheel gezocht naar de fout. Dat was dus dat ik de voorwaarde van recursie had geïnterpreteerd als dat beide spelers dezelfde hand moesten hebben als een vorige ronde.

Grappig, ik had hem ook voor 2 spelers geimplemteerd, maar bij kwam er gewoon een antwoord uit dat nog goed was ook. Misschien heb ik geluk gehad met mijn input?

[Dricus]

bakkerjangert schreef op dinsdag 22 december 2020 @ 09:31:
Grappig, ik had hem ook voor 2 spelers geimplemteerd, maar bij kwam er gewoon een antwoord uit dat nog goed was ook. Misschien heb ik geluk gehad met mijn input?

Dat moet wel, want ik kreeg met die interpretatie een verkeerd antwoord .

[ZieglerNichols]

bakkerjangert schreef op dinsdag 22 december 2020 @ 09:31:
[...]


Grappig, ik had hem ook voor 2 spelers geimplemteerd, maar bij kwam er gewoon een antwoord uit dat nog goed was ook. Misschien heb ik geluk gehad met mijn input?

Ik controleerde ook of beide spelers een eerder geziene hand hadden, maar als ik dat nu verander naar een van hen, dan krijg ik hetzelfde antwoord, maar dan wel 10x sneller.

[eamelink]

Ik betwijfel of het mogelijk is dat één speler een eerder geziene hand heeft en de andere niet...

[armageddon_2k1]

Dag 22 in Kotlin

Deze was weer easy-peasy. Gewoon rustig lezen en een juiste data-structuur kiezen.

Dricus schreef op dinsdag 22 december 2020 @ 09:26:
Dag 22 (Kotlin)

Allemachtig, dat duurde véél langer dan nodig . Inderdaad een kwestie van HEEL GOED LEZEN!

spoiler:

De voorwaarde voor een recursie is dus dat ÉÉN SPELER dezelfde "hand" moet hebben als een vorige ronde. Ik heb me helemaal scheel gezocht naar de fout. Dat was dus dat ik de voorwaarde van recursie had geïnterpreteerd als dat beide spelers dezelfde hand moesten hebben als een vorige ronde.

Dat is vaag, zo had ik het ook geinterpreteerd. Je hebt toch de testinput om te kijken of ie in een loop beland of niet?

spoiler:

Daarnaast heeft @eamelink ook wel een punt. Het vermoeden is dat nooit 1 hand onafhankelijk nog een keer terug kan komen..... maar daar kan je waarschijnlijk 5 PhDs op laten studeren om tot een formeel antwoord te komen.

[ Voor 10% gewijzigd door armageddon_2k1 op 22-12-2020 09:57 ]

[Dricus]

eamelink schreef op dinsdag 22 december 2020 @ 09:51:
Ik betwijfel of het mogelijk is dat één speler een eerder geziene hand heeft en de andere niet...

Ja, dat komt bij mijn input 1240 keer voor.

[armageddon_2k1]

Dricus schreef op dinsdag 22 december 2020 @ 09:57:
[...]

Ja, dat komt bij mijn input 1240 keer voor.

spoiler:

Bij mij ook zoiets, maar als de andere speler dan een andere hand heeft, dan loopt het spel toch nog steeds anders? Aangezien het deterministisch is

En je schrijft dat het 'de voorwaarde is voor recursie...'. Maar het is de voorwaarde om de recursie te stoppen als beide handen al voorgekomen zijn:

"Before either player deals a card, if there was a previous round in this game that had exactly the same cards in the same order in the same players' decks"
Hier staat expliciet meervoud, dus dat interpreteer ik dat beide handen tegelijkertijd al een keer voorgekomen moeten zijn.

[ Voor 49% gewijzigd door armageddon_2k1 op 22-12-2020 10:01 ]

[Dricus]

armageddon_2k1 schreef op dinsdag 22 december 2020 @ 09:58:
Bij mij ook, maar als de andere speler dan een andere hand heeft, dan loopt het spel toch nog steeds anders?

Ja, maar dat maakt voor de regel toch niet uit? Het is een feit dat je bij een andere interpretatie een ander antwoord kan krijgen, dat is hier het punt.

[ZieglerNichols]

eamelink schreef op dinsdag 22 december 2020 @ 09:51:
Ik betwijfel of het mogelijk is dat één speler een eerder geziene hand heeft en de andere niet...

Dat lijkt me binnen 1 spel inderdaad niet mogelijk, vandaar dat ik hetzelfde antwoord krijg als ik 1 speler check of allebei.

[Hydra]

Fuck me. Dit was een oefening in "goed lezen!".

Dag 22 in Kotlin

Deel 1 was een eitje. Maar deel 2, man man man. Ik heb heel lang hier op vast gezeten:

spoiler:

"To play a sub-game of Recursive Combat, each player creates a new deck by making a copy of the next cards in their deck (the quantity of cards copied is equal to the number on the card they drew to trigger the sub-game)."

Dat bold stukje overheen gelezen dus ik gaf aan een sub-game de volledige decks mee, niet gelimiteerd aan het getal dat iemand had. Op de voorbeeldinput gaat dat gewoon goed. In de 'echte' input zit je in een eindeloze loop

Math.pow("Zucht", 10)

[eamelink]

Dricus schreef op dinsdag 22 december 2020 @ 09:57:
[...]

Ja, dat komt bij mijn input 1240 keer voor.

Bij mij ook, blijkt

Grappige is dat het spel duidelijk anders verloopt (veel korter), maar toch hetzelfde resultaat geeft, als ik check op één dezelfde hand.

Blijkbaar verandert de volgorde van winnen niet.

[armageddon_2k1]

Dricus schreef op dinsdag 22 december 2020 @ 09:59:
[...]

Ja, maar dat maakt voor de regel toch niet uit? Het is een feit dat je bij een andere interpretatie een ander antwoord kan krijgen, dat is hier het punt.

Hmm, ik heb jouw input even gepakt en kom op jouw antwoord uit met mijn interpretatie. Maar ik heb het gevoel dat ik je niet helemaal begrijp en langs je heen praat

spoiler:

"Een voorwaarde om een game te stoppen is als de combinatie van 2 handen al eerder voorgekomen is."
Dat heb ik geimplementeerd en werkt met jouw input en gebeurt 4386x in dat geval.

EDIT: Verdomd, als ik het op jouw manier implementeer is het wel 3x sneller maar met hetzelfde antwoord. Nouja.

[ Voor 7% gewijzigd door armageddon_2k1 op 22-12-2020 10:10 ]

[Hydra]

Dido schreef op dinsdag 22 december 2020 @ 06:42:
Yes! First on Tweakers vandaag \O/

dinsdag 22 december 2020 06:42

Je kunt overdrijven

[Dricus]

armageddon_2k1 schreef op dinsdag 22 december 2020 @ 10:07:
Hmm, ik heb jouw input even gepakt en kom op jouw antwoord uit met mijn interpretatie. Maar ik heb het gevoel dat ik je niet helemaal begrijp en langs je heen praat

spoiler:

"Een voorwaarde om een game te stoppen is als de combinatie van 2 handen al eerder voorgekomen is."
Dat heb ik geimplementeerd en werkt met jouw input en gebeurt 4386x in dat geval.

EDIT: Verdomd, als ik het op jouw manier implementeer is het wel 3x sneller maar met hetzelfde antwoord. Nouja.

spoiler:

De "foutieve" check die ik deed was om te kijken of beide spelers exact dezelfde hand hebben als in een eerdere ronde van die game. Dus er moest een eerdere ronde bestaan waarin beide spelers exact dezelfde hand hadden als de huidige ronde. Met deze check kwam ik op een fout antwoord uit.

De check die ik nu doe is of minimaal één van de spelers dezelfde hand heeft als in een eerdere ronde van die game. Dus er moet een eerdere ronde bestaan waarin minstens één speler dezelfde hand had als de huidige ronde. Deze check resulteerde in het juiste antwoord.

[Dido]

Hydra schreef op dinsdag 22 december 2020 @ 10:15:
dinsdag 22 december 2020 06:42

Je kunt overdrijven

Klopt, ben ik goed in. Was niet eens mijn persoonlijk snelste tijd, maar andere dagen konden anderen nog beter overdrijven, kennelijk

code:

      --------Part 1--------   --------Part 2--------
Day       Time   Rank  Score       Time   Rank  Score
 22   00:10:36   1213      0   00:40:51    897      0

[armageddon_2k1]

Dricus schreef op dinsdag 22 december 2020 @ 10:15:
[...]

spoiler:

De "foutieve" check die ik deed was om te kijken of beide spelers exact dezelfde hand hebben als in een eerdere ronde van die game. Dus er moest een eerdere ronde bestaan waarin beide spelers exact dezelfde hand hadden als de huidige ronde. Met deze check kwam ik op een fout antwoord uit.

De check die ik nu doe is of minimaal één van de spelers dezelfde hand heeft als in een eerdere ronde van die game. Dus er moet een eerdere ronde bestaan waarin minstens één speler dezelfde hand had als de huidige ronde. Deze check resulteerde in het juiste antwoord.

spoiler:

Maar die "foutieve" check doe ik ook (in een oudere versie van mijn code) en krijg ik op jouw input wel jouw goede antwoord, 33304.

Zie hier:
https://github.com/rj-cod...ding/aoc2020/Day22.kt#L25

[Hydra]

Dido schreef op dinsdag 22 december 2020 @ 10:16:
Klopt, ben ik goed in. Was niet eens mijn persoonlijk snelste tijd, maar andere dagen konden anderen nog beter overdrijven, kennelijk

code:

      --------Part 1--------   --------Part 2--------
Day       Time   Rank  Score       Time   Rank  Score
 22   00:10:36   1213      0   00:40:51    897      0

Oh nice! Ik ben volgens mij niet een keer onder de duizend gekomen.

Edit: Nope! Beste is dag 19 op pos 2300. Grappig genoeg is de een na beste Dag 20 op pos 2800, terwijl de completion time daar bijna 10 uur was. Je ziet in de globale stats ook dat HEEL veel mensen dag 20 nog niet gedaan hebben.

[ Voor 19% gewijzigd door Hydra op 22-12-2020 10:23 ]

[Dido]

Hydra schreef op dinsdag 22 december 2020 @ 10:20:
Oh nice! Ik ben volgens mij niet een keer onder de duizend gekomen.

Is me twee keer gelukt, andere keer was op dag 20 (p962). En dat met een tijd van 3 uur en 17 minuten
Deel 1 had me toen al dik twee uur gekost

Mijn snelste zilver was in 6:22 op dag 6, en dat leverde toch maar plaats 1821 op. Snelste goud was 22:03, dezelfde dag, maar dat was plek 4116.

Op zich probeer ik niet ten koste van alles zo snel mogelijk een antwoord te genereren, maar het tweakers leaderboard is wel aardig om bij te houden. Niet dat ik heel realistisch nu nog een plek kan stijgen, trouwens. Tenzij @Varienaja eens een dagje pauze neemt

[Dricus]

armageddon_2k1 schreef op dinsdag 22 december 2020 @ 10:18:

spoiler:

Maar die "foutieve" check doe ik ook (in een oudere versie van mijn code) en krijg ik op jouw input wel jouw goede antwoord, 33304.

Zie hier:
https://github.com/rj-cod...ding/aoc2020/Day22.kt#L25

spoiler:

Nou, dan snap ik er geen hout meer van. Ziehier de code die bij mijn input een fout antwoord geeft. Met deze code wordt het antwoord 30795.

[armageddon_2k1]

Dricus schreef op dinsdag 22 december 2020 @ 10:29:
[...]

spoiler:

Nou, dan snap ik er geen hout meer van. Ziehier de code die bij mijn input een fout antwoord geeft. Met deze code wordt het antwoord 30795.

spoiler:

Je concat de lists. Dat wil niet zeggen dat dat altijd een unieke key is aangezien de kaarten wisselen speler.

Ronde n:
p1 = [a, b, c, d]
p2 = [e, f, g, h]
key = [a, b, c, d, e, f, g, h]

Ronde m:
p1 = [a, b]
p2 = [c, d, e, f, g, h]
key = [a, b, c, d, e, f, g, h]

Key hetzelfde, hands niet.

[FrankMennink]

Dag 22 in Python

Leuke puzzel, zoals iedereen aangeeft, goed lezen is key.

spoiler:

Dacht een goede ingeving te hebben om de score te berekenen van een deck en te kijken of die al eerder voorkwam. Had een vermoeden dat die wel uniek zou zijn gezien de positie vermenigvuldiging. I was wrong Daarna maar de decks zelf bijgehouden, ook de aanname gedaan dat als 1 speler hetzelfde heeft, dan heeft de ander dat ook. Voor mijn input werkt dat voor zowel player1 als player2. Als ik 1 van de twee spelers check runt het in ~1s, als ik beide check runt het in ~8.5s. Weet niet of dit toeval is, maar het heeft me wel wat kopzorgen bespaard

[Dricus]

armageddon_2k1 schreef op dinsdag 22 december 2020 @ 10:32:
[...]

spoiler:

Je concat de lists. Dat wil niet zeggen dat dat altijd een unieke key is aangezien de kaarten wisselen speler.

Ronde n:
p1 = [a, b, c, d]
p2 = [e, f, g, h]
key = [a, b, c, d, e, f, g, h]

Ronde m:
p1 = [a, b]
p2 = [c, d, e, f, g, h]
key = [a, b, c, d, e, f, g, h]

Key hetzelfde, hands niet.

Verrek, je hebt gelijk! Dank voor het meedenken!

[Dido]

FrankMennink schreef op dinsdag 22 december 2020 @ 10:32:

spoiler:

Dacht een goede ingeving te hebben om de score te berekenen van een deck en te kijken of die al eerder voorkwam. Had een vermoeden dat die wel uniek zou zijn gezien de positie vermenigvuldiging. I was wrong Daarna maar de decks zelf bijgehouden, ook de aanname gedaan dat als 1 speler hetzelfde heeft, dan heeft de ander dat ook. Voor mijn input werkt dat voor zowel player1 als player2. Als ik 1 van de twee spelers check runt het in ~1s, als ik beide check runt het in ~8.5s. Weet niet of dit toeval is, maar het heeft me wel wat kopzorgen bespaard

spoiler:

Ik krijg in de volgende gevallen het juiste andtwoord;
1) Check of speler 1 een oude hand heeft.
2) Check of speler 2 een oude hand heeft.
3) Check of speler 1 een oude hand heeft OF speler 2 een oude hand heeft.
4) Check of speler 1 een oude hand heeft EN speler 2 een oude hand heeft.

4) is de meest voor de hand liggende interpretatie van de opgave, maar kennelijk is het effect van 3 hetzelfde en zijn 1, 2, 3 en 4 voor het uiteindelijke spel equivalent.

Optie 3 werkt het snelste, ondanks de noodzaak van het hashen van beiden handen. Opties 1 en 2 zijn een 15% langzamer dan 3.

En nu bedenk ik me dat het voor het spel niet uitmaaklt wie al een hand gehad heeft, dus dat het ook prima is als speler 1 een oude hand van speler 2 krijgt -> ook exit.

Dat levert me ook het goede antwoord op, maar gek genoeg zo te zien geen significante winst

[ Voor 9% gewijzigd door Dido op 22-12-2020 10:46 ]

[FrankMennink]

Dido schreef op dinsdag 22 december 2020 @ 10:38:
[...]

spoiler:

Ik krijg in de volgende gevallen het juiste andtwoord;
1) Check of speler 1 een oude hand heeft.
2) Check of speler 2 een oude hand heeft.
3) Check of speler 1 een oude hand heeft OF speler 2 een oude hand heeft.
4) Check of speler 1 een oude hand heeft EN speler 2 een oude hand heeft.

4) is de meest voor de hand liggende interpretatie van de opgave, maar kennelijk is het effect van 3 hetzelfde en zijn 1, 2, 3 en 4 voor het uiteindelijke spel equivalent.

Optie 3 werkt het snelste, ondanks de noodzaak van het hashen van beiden handen. Opties 1 en 2 zijn een 15% langzamer dan 3.

spoiler:

Interesting, ik heb voor mijn code alle opties die jij geeft getimed en ik krijg de volgende uitkomsten:
1 -> 1.1s
2 -> 1.0s
3 -> 1.3s
4 -> 8.5s

kennelijk is voor mijn implementatie/taal de check of iets in een list zit inefficienter met een grotere bak met data

[Singelaar]

Leuk dat we hier ook een enthousiaste groep puzzelaars hebben. Ik zwoeg al 3 weken eenzaam

Gingen jullie hier ook op stuk:

spoiler:

... the winning player's score is calculated from the cards they have in their original deck...
ik dacht: original, prima dan pak ik het dek waarmee we het spel starten.

Niet dus

[Dido]

Singelaar schreef op dinsdag 22 december 2020 @ 10:59:
Leuk dat we hier ook een enthousiaste groep puzzelaars hebben. Ik zwoeg al 3 weken eenzaam

Gingen jullie hier ook op stuk:

spoiler:

... the winning player's score is calculated from the cards they have in their original deck...
ik dacht: original, prima dan pak ik het dek waarmee we het spel starten.

Niet dus

spoiler:

Dat zou wel een heel snelle shortcut zijn, met 50% kans op succes...

[Singelaar]

Goed punt!

[joppybt]

eamelink schreef op dinsdag 22 december 2020 @ 09:51:
Ik betwijfel of het mogelijk is dat één speler een eerder geziene hand heeft en de andere niet...

spoiler:

De andere speler zal de rest van de kaarten hebben maar mogelijk in een andere volgorde? Ik weet niet zeker of dat kan gebeuren.

Maar bij mijn input duurt het ook 10 keer zo lang als ik eis dat *beide* spelers dezelfde kaarten hebben maar het antwoord blijft gelijk.

[Woy]

spoiler:

Grappig, dat is nog wel een optimalisatie mogelijkheid. Je hoeft dan alleen de speler met de kleinste hand te checken

[FrankMennink]

FrankMennink schreef op dinsdag 22 december 2020 @ 10:47:
[...]

spoiler:

Interesting, ik heb voor mijn code alle opties die jij geeft getimed en ik krijg de volgende uitkomsten:
1 -> 1.1s
2 -> 1.0s
3 -> 1.3s
4 -> 8.5s

kennelijk is voor mijn implementatie/taal de check of iets in een list zit inefficienter met een grotere bak met data

spoiler:

omgevormd naar set met tuples ipv list met lists, hierbij voor opties 1 en 2 een runtime van ~400ms, voor optie 3 een runtime van ~360ms. Toch weer een leuke performance winst

[Ethikka]

Dido schreef op dinsdag 22 december 2020 @ 10:38:
[...]

spoiler:

Ik krijg in de volgende gevallen het juiste andtwoord;
1) Check of speler 1 een oude hand heeft.
2) Check of speler 2 een oude hand heeft.
3) Check of speler 1 een oude hand heeft OF speler 2 een oude hand heeft.
4) Check of speler 1 een oude hand heeft EN speler 2 een oude hand heeft.

4) is de meest voor de hand liggende interpretatie van de opgave, maar kennelijk is het effect van 3 hetzelfde en zijn 1, 2, 3 en 4 voor het uiteindelijke spel equivalent.

Optie 3 werkt het snelste, ondanks de noodzaak van het hashen van beiden handen. Opties 1 en 2 zijn een 15% langzamer dan 3.

En nu bedenk ik me dat het voor het spel niet uitmaaklt wie al een hand gehad heeft, dus dat het ook prima is als speler 1 een oude hand van speler 2 krijgt -> ook exit.

Dat levert me ook het goede antwoord op, maar gek genoeg zo te zien geen significante winst

spoiler:

Ik krijg alleen in het geval van optie 4 de juiste uitkomst. Alle andere opties leveren een andere (foute) oplossing op voor mijn input. Eerder in deze thread had iemand het er over dat interpretatie 4 juist niet goed was? Dat kan ik dan niet rijmen met elkaar.

Ruim uur bezig geweest uit te vinden waarom het niet werkt (met optie 3 want zo had ik hem initieel geinterpreteerd) tot en met checken met iemand anders zijn input die hem al had gehaald. Dit leverde voor die input een goed antwoord op, maar dus niet voor mijn input.

Uiteindelijk mijn state opgeslagen volgens interpretatie 4 (met een factor 10 runtime penalty!) voordat ik een antwoord kreeg wat klopt. Omdat het met die andere input wel leek te kloppen niet echt bezig geweest met het feit dat ik misschien een andere edge-cases heb.

Voor nu ben ik blij met de 1.6 seconden runtime, misschien later nog eens kijken of het sneller kan.

[Mschamp]

Dido schreef op dinsdag 22 december 2020 @ 10:38:
[...]

spoiler:

Ik krijg in de volgende gevallen het juiste andtwoord;
1) Check of speler 1 een oude hand heeft.
2) Check of speler 2 een oude hand heeft.
3) Check of speler 1 een oude hand heeft OF speler 2 een oude hand heeft.
4) Check of speler 1 een oude hand heeft EN speler 2 een oude hand heeft.

4) is de meest voor de hand liggende interpretatie van de opgave, maar kennelijk is het effect van 3 hetzelfde en zijn 1, 2, 3 en 4 voor het uiteindelijke spel equivalent.

Optie 3 werkt het snelste, ondanks de noodzaak van het hashen van beiden handen. Opties 1 en 2 zijn een 15% langzamer dan 3.

En nu bedenk ik me dat het voor het spel niet uitmaaklt wie al een hand gehad heeft, dus dat het ook prima is als speler 1 een oude hand van speler 2 krijgt -> ook exit.

Dat levert me ook het goede antwoord op, maar gek genoeg zo te zien geen significante winst

Ik heb variant 3 geïmplementeerd en dat geeft voor voorbeeld en werkelijke input het correcte resultaat

[Dricus]

Ethikka schreef op dinsdag 22 december 2020 @ 12:45:

spoiler:

Eerder in deze thread had iemand het er over dat interpretatie 4 juist niet goed was? Dat kan ik dan niet rijmen met elkaar.

Dat was ik, en dat bleek gewoon een subtiele bug te zijn die ik over het hoofd zag.

[Reynouts]

Ethikka schreef op dinsdag 22 december 2020 @ 12:45:
[...]

spoiler:

Ik krijg alleen in het geval van optie 4 de juiste uitkomst. Alle andere opties leveren een andere (foute) oplossing op voor mijn input. Eerder in deze thread had iemand het er over dat interpretatie 4 juist niet goed was? Dat kan ik dan niet rijmen met elkaar.

Ruim uur bezig geweest uit te vinden waarom het niet werkt (met optie 3 want zo had ik hem initieel geinterpreteerd) tot en met checken met iemand anders zijn input die hem al had gehaald. Dit leverde voor die input een goed antwoord op, maar dus niet voor mijn input.

Uiteindelijk mijn state opgeslagen volgens interpretatie 4 (met een factor 10 runtime penalty!) voordat ik een antwoord kreeg wat klopt. Omdat het met die andere input wel leek te kloppen niet echt bezig geweest met het feit dat ik misschien een andere edge-cases heb.

Voor nu ben ik blij met de 1.6 seconden runtime, misschien later nog eens kijken of het sneller kan.

Interessant. Wil je je input en antwoord eens delen?

[Ethikka]

Reynouts schreef op dinsdag 22 december 2020 @ 13:26:
[...]


Interessant. Wil je je input en antwoord eens delen?

Uiteraard

spoiler:

https://bitbucket.org/eth...c/master/2020/input.day22
Antwoord deel b met interpretatie 1 t/m 3: 33490
Goede antwoord deel b: 32949

[ydderf]

Dag 22 ook afgerond. Zoals bij velen, was het moeilijkste het lezen van de opdracht van deel 2.

Net nog ff de spoilers doorgelezen, en zal ook eens kijken of het bij mij verschil maakt.

spoiler:

Wanneer ik check op beide speler exact dezelfde decks als een voorgaande ronde, dan duurt het 9,5 sec.
Check ik op één van beide spelers exact dezelfde deck als zichzelf een voorgaande ronde, dan duurt het 1,5 seconde.
Check ik op één van beide spelers exact dezelfde deck als zichzelf of de andere speler een voorgaande ronde, dan duurt het 1,8 seconde.

[ Voor 41% gewijzigd door ydderf op 22-12-2020 14:26 . Reden: spoiler toegevoegd ]

[bakkerjangert]

Mijn theorie waarom overal hetzeldfe moet uitkomen, onafhankelijk van de toetsmethode:

spoiler:

Het enige wat er gebeurt als er een loop ontstaat is dat de bovenliggende game doorgaat met player 1 als winnaar. Het maakt dus niet uit hoe je checkt voor deze loop; het resultaat is altijd hetzelfde.

-- edit --

Dit is niet waterdicht, het spel kan anders lopen als slechts op één van beide wordt getoetst, echter is de kans dan nog steeds meer dan 50% dat speler 1 wint (ofwel je zit in een loop, dan wint 1 ofwel het spel speelt uit en dan wint 1 of 2 met circa kans 0,50) en het eindresultaat dus hetzelfde is. De echte loop start als beide spelers gelijktijdig eenzelfde hand hebben.

[ Voor 38% gewijzigd door bakkerjangert op 22-12-2020 16:59 ]

[Reynouts]

bakkerjangert schreef op dinsdag 22 december 2020 @ 14:32:
Mijn theorie waarom overal hetzeldfe moet uitkomen, onafhankelijk van de toetsmethode:

spoiler:

Het enige wat er gebeurt als er een loop ontstaat is dat de bovenliggende game doorgaat met player 1 als winnaar. Het maakt dus niet uit hoe je checkt voor deze loop; het resultaat is altijd hetzelfde.

Ik weet niet of dit over hetzelfde gaat, maar volgens mij wel en dat klopt dus niet. Check de input van @Ethikka een stukje naar boven maar eens met de verschillende methodieken en wetende wat het antwoord moet zijn. Met de meeste inputs gaat het inderdaad wel goed, maar er zijn edge cases zoals die input van Ethikka.

[ydderf]

Reynouts schreef op dinsdag 22 december 2020 @ 14:48:
[...]


Ik weet niet of dit over hetzelfde gaat, maar volgens mij wel en dat klopt dus niet. Check de input van @Ethikka een stukje naar boven maar eens met de verschillende methodieken en wetende wat het antwoord moet zijn. Met de meeste inputs gaat het inderdaad wel goed, maar er zijn edge cases zoals die input van Ethikka.

spoiler:

Het kan volgens mij alleen maar een ander resultaat geven, indien je een oneindige loop denkt te detecteren, maar dit geen oneindige loop is (en dus de andere player kan winnen). Indien je maar alleen de werkelijke oneindige loops detecteerd, dan zou dit geen verschil qua uitkomst mogen geven (player 1 wint dan altijd). Het kan qua cyclustijd natuurlijk wel wat uitmaken.
Bij mij kwam bij elke testcase hetzelfde resultaat uit het spel.

Sowieso wanneer de ene speler hetzelfde deck heeft als een voorgaande ronde, dan heeft de andere speler ook hetzelfde deck als die voorgaande ronde, maar de volgorde van de kaarten kan anders zijn.
Ik heb nog even gecontroleerd, maar bij mij wordt soms een subgame afgebroken omdat één van beide spelers hetzelfde deck heeft, en soms omdat beide spelers hetzelfde deck heeft.

[Reynouts]

ydderf schreef op dinsdag 22 december 2020 @ 15:19:
[...]

spoiler:

Sowieso wanneer de ene speler hetzelfde deck heeft als een voorgaande ronde, dan heeft de andere speler ook hetzelfde deck als die voorgaande ronde, maar de volgorde van de kaarten kan anders zijn.

spoiler:

Klopt. En als de volgorde anders is, zou dat geen match op moeten leveren volgens de beschrijving.

Op naar de laatste paar dagen!

[DRaakje]

ydderf schreef op dinsdag 22 december 2020 @ 14:17:
Dag 22 ook afgerond. Zoals bij velen, was het moeilijkste het lezen van de opdracht van deel 2.

Net nog ff de spoilers doorgelezen, en zal ook eens kijken of het bij mij verschil maakt.

spoiler:

Wanneer ik check op beide speler exact dezelfde decks als een voorgaande ronde, dan duurt het 9,5 sec.
Check ik op één van beide spelers exact dezelfde deck als zichzelf een voorgaande ronde, dan duurt het 1,5 seconde.
Check ik op één van beide spelers exact dezelfde deck als zichzelf of de andere speler een voorgaande ronde, dan duurt het 1,8 seconde.

Verander je list eens in een hashset waarbij je decks controleert, die is veel sneller in opzoeken.

Hier is mijn code, ook in C#, runt in 281 ms.

https://pastebin.com/8ssqQnvW

[Varienaja]

Heel geinig om te zien hoe erg de oplossingen van vandaag op elkaar lijken. GMTA, zullen we maar zeggen.

[Woy]

Ik heb mijn solution van part 2 nu naar ~16ms, grootste change is

spoiler:

Ik check alleen de kortse hand, aangezien blijkbaar een van de twee handen checken ook altijd het juiste resultaat geeft. Ik zou niet 100% weten of er inputs mogelijk zijn waarbij dat niet klopt

Overigens grappig dat mijn implementatie met value checks langzamer is dan een string genereren en die checken, mogelijk kan ik daar nog wel wat optimalizeren.

[Woy]

Het is echt bizar hoe groot het verschil tussen deze twee regels code bij het bepalen van de recursie maakt

C#:

var strHands = String.Join(",", (deck1.Count < deck2.Count ? deck1 : deck2));

Maakt het resultaat 100* sneller dan het volgende, verder exact met dezelfde lookup

C#:

var strHands = String.Join(",", deck1) + ";" + String.Join(",", deck2);

[DRaakje]

Woy schreef op dinsdag 22 december 2020 @ 16:20:
Ik heb mijn solution van part 2 nu naar ~16ms, grootste change is

Probeer hem eens met deze?

code:

 new string(player1.Select(x => (char) x).ToArray());

[ Voor 48% gewijzigd door DRaakje op 22-12-2020 16:34 ]

[Ethikka]

bakkerjangert schreef op dinsdag 22 december 2020 @ 14:32:
Mijn theorie waarom overal hetzeldfe moet uitkomen, onafhankelijk van de toetsmethode:

spoiler:

Het enige wat er gebeurt als er een loop ontstaat is dat de bovenliggende game doorgaat met player 1 als winnaar. Het maakt dus niet uit hoe je checkt voor deze loop; het resultaat is altijd hetzelfde.

spoiler:

Het feit dat toetsmethodes 1 t/m 3 een ander resultaat oplevert als toetsmethode 4 is voor mijn input lijkt me bewijs genoeg dat deze theorie niet waterdicht is.

Een lus is alleen een lus als beide decks weer hetzelfde zijn op hetzelfde punt in de tijd, de volgorde van 1 van beide kan nog steeds anders zijn en zorgen voor winst voor speler 2. Hoewel dat achteraf gezien wel logisch is, las ik hem niet zo vanochtend. Gebrek aan koffie o.i.d.

Runtime na wat kleine optimalizaties is redelijk (965ms) maar zorgt er wel voor dat mijn "time alles" scriptje weer stukken langer duurt. De optimalizaties die ik hier zo lees werken simpelweg niet voor mijn input.

edit: WTF? toch nog eens prutsen, als ik alleen player 1 bekijk voor loop-detection werkt het wel, voor alle inputs die ik weet. Schiet mij maar lek ;-) (maar wel 965ms -> 304ms dus mij hoor je niet klagen ;-))

[ Voor 8% gewijzigd door Ethikka op 22-12-2020 16:43 ]

[Woy]

DRaakje schreef op dinsdag 22 december 2020 @ 16:30:
[...]


Probeer hem eens met deze?

code:

 new string(player1.Select(x => (char) x).ToArray());

Dat is wel een slimmere manier om equality te bepalen ja , ga ik zo even proberen