Advent of Code 2020

[Soultaker]

Varienaja schreef op dinsdag 22 december 2020 @ 16:17:
Heel geinig om te zien hoe erg de oplossingen van vandaag op elkaar lijken. GMTA, zullen we maar zeggen.

Komt ook omdat dit soort simulatieproblemen niet heel veel creativiteit toelaten. Het is vooral een kwestie van goed lezen en vervolgens exact implementeren wat er gevraagd wordt.

Niet mijn favoriete soort probleem, maar helaas wel veel voorkomend bij Advent of Code, hoewel het dit jaar gelukkig meevalt (tot nu toe).

[Woy]

@DRaakje Dat scheelt nog wel iets van ~16ms naar ~13ms. Als ik het voor beide handen doe is het van 1,5s naar 1,1s

[GladstoneW]

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


Probeer hem eens met deze?

code:

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

Interessante oplossing, vast sneller dan de hashfunctie die ik van het internet heb geplukt:

code:

public static int GetSequenceHashCode<T>(this IEnumerable<T> sequence)
{
      const int seed = 487;
      const int modifier = 31;

      unchecked
      {
          return sequence.Aggregate(seed, (current, item) =>
                    (current * modifier) + item.GetHashCode());
      }
}

Kleine note: jouw code alleen met getallen 0 tot en met 65535 (UInt16.MaxValue), maar dat is geen probleem met de input van vandaag!

[ Voor 3% gewijzigd door GladstoneW op 22-12-2020 16:48 ]

[Woy]

GladstoneW schreef op dinsdag 22 december 2020 @ 16:47:
[...]


Interessante oplossing, vast sneller dan de hashfunctie die ik van het internet heb geplukt:

code:

public static int GetSequenceHashCode<T>(this IEnumerable<T> sequence)
{
      const int seed = 487;
      const int modifier = 31;

      unchecked
      {
          return sequence.Aggregate(seed, (current, item) =>
                    (current * modifier) + item.GetHashCode());
      }
}

Kleine note: jouw code alleen met getallen 0 tot en met 65535 (UInt16.MaxValue), maar dat is geen probleem met de input van vandaag!

Die hashfunctie is nog een stuk sneller, wat opzich ook logisch is, want van de string moet ook weer een hash berekend worden.

Met die functie ga ik van ~13ms naar ~7ms

[GladstoneW]

Woy schreef op dinsdag 22 december 2020 @ 16:51:
[...]

Die hashfunctie is nog een stuk sneller, wat opzich ook logisch is, want van de string moet ook weer een hash berekend worden.

Met die functie ga ik van ~13ms naar ~7ms

Daar kom ik nu ook achter: ~200 ms met hashfunctie, ~450 ms met de char array. Nog steeds een stukje langzamer dan jouw code dus (maar mogelijk ligt dat aan mijn pc , maar het verschil is wel erg groot).

[Woy]

@GladstoneW
Ik had zelf overigens een vergelijkbare oplossing gebruikt, maar dat netjes in een IEqualityComparer gegoten, en dan hashfunctie

C#:

public static int GetHashCode(IEnumerable<int> input)
        {
            var hashCode = new HashCode();
            foreach (var item in input)
            {
                hashCode.Add(item);
            }

            return hashCode.ToHashCode();
        }

Maar dat is significant langzamer dan direct de hashcode gebruiken ( Al kan er in theorie natuurlijk wel een collision met hashed zijn ).

Met comparer is het bij mij ongeveer ~20ms, met puur de hashfunctie ~8ms

[donderz]

Woy schreef op dinsdag 22 december 2020 @ 16:29:
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);

Hier stop je ook als een hand die eerst player1 had nu bij player 2 zit.

GladstoneW schreef op dinsdag 22 december 2020 @ 16:47:
[...]


Interessante oplossing, vast sneller dan de hashfunctie die ik van het internet heb geplukt:

code:

public static int GetSequenceHashCode<T>(this IEnumerable<T> sequence)
{
      const int seed = 487;
      const int modifier = 31;

      unchecked
      {
          return sequence.Aggregate(seed, (current, item) =>
                    (current * modifier) + item.GetHashCode());
      }
}

Kleine note: jouw code alleen met getallen 0 tot en met 65535 (UInt16.MaxValue), maar dat is geen probleem met de input van vandaag!

Kan je hier geen false positives mee krijgen? (hash collision) Je zou dus onterecht kunnen stoppen.

[ydderf]

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


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

Thanks, dat heb ik gedaan. De tijd ging naar 1,2 sec.
Hierna de check aangepast van:

code:

 if (playedDeckP1.Any(d => d.Equals(currentDeckP1)) || playedDeckP2.Any(d => d.Equals(currentDeckP2)))

naar:

code:

 if (playedDeckP1.Contains(currentDeckP1) || playedDeckP2.Contains(currentDeckP2))

Hierna de tijd op 500 msec.
Nieuwe versie met Hashset
En ik zie dat de meeste C# oplossingen met een queue worden gedaan ipv een list. Ik wist niet van het bestaan van de queue functie, maar dat klinkt op zich wel logisch voor de wachtrij van kaarten.

[Woy]

donderz schreef op dinsdag 22 december 2020 @ 16:55:
[...]

Hier stop je ook als een hand die eerst player1 had nu bij player 2 zit.

Dat is volgens mij ook correct, want als je van hand kunt wisselen, zul je dat per definitie nog een keer doen, en dus alsnog aan de conditie voldoen.

[Varienaja]

donderz schreef op dinsdag 22 december 2020 @ 16:55:
Kan je hier geen false positives mee krijgen? (hash collision) Je zou dus onterecht kunnen stoppen.

Dat maakt toch niet uit? Iets als dit "int hashCode() { return 1;}" werkt gewoon. Niet snel, maar het werkt. Voor super performance probeer je de hashes mooi te verspreiden over het hele int-bereik. Maar collisions zijn sowieso niet uit te sluiten. Je kunt immers nooit _alle_ mogelijke objecten (zeg maar oneindig) mappen op slechts 2^32-1 integer waarden.

[Woy]

Varienaja schreef op dinsdag 22 december 2020 @ 16:59:
[...]

Dat maakt toch niet uit? Iets als dit "int hashCode() { return 1;}" werkt gewoon. Niet snel, maar het werkt. Voor super performance probeer je de hashes mooi te verspreiden over het hele in-bereik. Maar collisions zijn sowieso niet uit te sluiten. Je kunt immers nooit _alle_ mogelijke objecten (zeg maar oneindig) mappen op slechts 2^32-1 integer waarden.

Als je netjes een compare functie gebruikt wel, maar als je de hashes direct checkt gaat het wel fout als je collisions krijgt

[Varienaja]

Woy schreef op dinsdag 22 december 2020 @ 16:59:
Als je netjes een compare functie gebruikt wel, maar als je de hashes direct checkt gaat het wel fout als je collisions krijgt

Direct hashes vergelijken.. heel avontuurlijk! Maar voor een AoC puzzle altijd goed.. als het werkt :-)

[Woy]

Varienaja schreef op dinsdag 22 december 2020 @ 17:01:
[...]

Direct hashes vergelijken.. heel avontuurlijk! Maar voor een AoC puzzle altijd goed.. als het werkt :-)

Ik had inderdaad eerst een versie waar ik aan de HashSet een Comparer meegeef die netjes een hash berekend en ook een daadwerkelijke check implementeert. Daarmee kwam ik op ~20ms, als ik gewoon direct de hash in de HashSet stop kom ik op (met dezelfde hash functie) op ~8ms

De versie waar ik een string opbouw op de manier die @DRaakje aanhaalde kwam ik op ~13ms terrecht. Ik ben wel verbaasd dat de string versie toch nog niet zo'n gekke keuze is.

[ Voor 15% gewijzigd door Woy op 22-12-2020 17:03 ]

[DataGhost]

Woy schreef op dinsdag 22 december 2020 @ 16:57:
[...]

Dat is volgens mij ook correct, want als je van hand kunt wisselen, zul je dat per definitie nog een keer doen, en dus alsnog aan de conditie voldoen.

Dat hoeft niet, want in een sub-game kan je een asymmetrische tie-break hebben. Als speler 1 hand X heeft en speler 2 hand Y en ze gaan een sub-game in waarin een loop zit, wint speler 1 die ronde. Als na een aantal rondes speler 2 hand X heeft en speler 1 hand Y en ze gaan diezelfde sub-game in, wint speler 1 die nogmaals, niet speler 2. De resulterende handen zijn daarna dus niet hetzelfde als bij de eerdere keer dat ze daar waren.

[GladstoneW]

Varienaja schreef op dinsdag 22 december 2020 @ 17:01:
[...]

Direct hashes vergelijken.. heel avontuurlijk! Maar voor een AoC puzzle altijd goed.. als het werkt :-)

Ik ben wel zo avontuurlijk (maar alleen nadat ik de ster al had verdiend met code die in ~6 seconden runde).

[Woy]

DataGhost schreef op dinsdag 22 december 2020 @ 17:04:
[...]

Dat hoeft niet, want in een sub-game kan je een asymmetrische tie-break hebben. Als speler 1 hand X heeft en speler 2 hand Y en ze gaan een sub-game in waarin een loop zit, wint speler 1 die ronde. Als na een aantal rondes speler 2 hand X heeft en speler 1 hand Y en ze gaan diezelfde sub-game in, wint speler 1 die nogmaals, niet speler 2. De resulterende handen zijn daarna dus niet hetzelfde als bij de eerdere keer dat ze daar waren.

Ja, je hebt gelijk, in de input komt het blijkbaar niet voor. Maar dat is eenvoudig te omzeilen door een -1 of -2 voor/achter de sequence te zetten om aan te geven van welke speler de hand was.

[DataGhost]

Woy schreef op dinsdag 22 december 2020 @ 17:08:
[...]

Ja, je hebt gelijk, in de input komt het blijkbaar niet voor. Maar dat is eenvoudig te omzeilen door een -1 of -2 voor/achter de sequence te zetten om aan te geven van welke speler de hand was.

Dat denk ik niet. Vanwege die tie-break kan het dus ook zo zijn dat de laagste kaart boven de hoogste kaart komt, waardoor de volgorde verandert. Het lijkt me dan prima mogelijk dat je een hand X kan hebben waar een hand Y tegenover staat met een andere volgorde binnen die hand, en dus weer een andere mogelijke uitkomst.

[Woy]

DataGhost schreef op dinsdag 22 december 2020 @ 17:11:
[...]

Dat denk ik niet. Vanwege die tie-break kan het dus ook zo zijn dat de laagste kaart boven de hoogste kaart komt, waardoor de volgorde verandert. Het lijkt me dan prima mogelijk dat je een hand X kan hebben waar een hand Y tegenover staat met een andere volgorde binnen die hand, en dus weer een andere mogelijke uitkomst.

Als het feit dat een speler nooit dezelfde hand mag hebben ( en dus niet perse beide spelers exact dezelfde hand moeten hebben ), en je hand [1,2,3,4] van speler 1 representeerd als [-1,1,2,3,4] toch altijd matchen? Ik bedoel puur alleen voor de duplicate check natuurlijk.

Dat was de premise waar het eerder in het topic over ging, ik ben er nog steeds niet 100% van overtuigd dat als speler hand X heeft er inderdaad niet meerdere handen Y mogelijk zijn, al lijkt dat in de input bij mij wel het geval te zijn.

[ Voor 14% gewijzigd door Woy op 22-12-2020 17:16 ]

[DataGhost]

Woy schreef op dinsdag 22 december 2020 @ 17:15:
[...]

Als het feit dat een speler nooit dezelfde hand mag hebben ( en dus niet perse beide spelers exact dezelfde hand moeten hebben ), en je hand [1,2,3,4] van speler 1 representeerd als [-1,1,2,3,4] toch altijd matchen? Ik bedoel puur alleen voor de duplicate check natuurlijk.

Ja, maar de hand van speler 1 zegt helemaal niks over de hand van speler 2 behalve welke kaarten erin zitten. Als je op een van beide checkt (incl volgorde) is niet per se gezegd dat de andere hand de rest van de kaarten heeft in precies dezelfde volgorde als de eerste keer.

[Woy]

DataGhost schreef op dinsdag 22 december 2020 @ 17:17:
[...]

Ja, maar de hand van speler 1 zegt helemaal niks over de hand van speler 2 behalve welke kaarten erin zitten. Als je op een van beide checkt (incl volgorde) is niet per se gezegd dat de andere hand de rest van de kaarten heeft in precies dezelfde volgorde als de eerste keer.

Helemaal niks zou ik niet zeggen, maar ik ben het zeker met je eens dat ik daar geen sluitend bewijs van heb gezien. Het is puur het uitgangspunt wat eerder in het topic langs kwam, omdat de regels niet helemaal duidelijk waren, en het leek alsof beide varienten hetzelfde resultaat hebben. Bij mijn input is dat ieder geval wel waar. Ik zal de input van Ethikka eens proberen, want die geeft aan dat er wel verschil in zit.

[Woy]

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


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

Inderdaad in deze input haalt het wel uit, en bevestigd dus dat inderdaad dat de regel gewoon is dat beide handen exact gelijk moeten zijn, niet 1 van de twee handen.

[DataGhost]

Woy schreef op dinsdag 22 december 2020 @ 17:22:
[...]

Inderdaad in deze input haalt het wel uit, en bevestigd dus dat inderdaad dat de regel gewoon is dat beide handen exact gelijk moeten zijn, niet 1 van de twee handen.

Precies, daar gebeurt het behoorlijk vaak, bijvoorbeeld:

code:

Speler 1 is key:
27,43,14 | 40,32,47,2,41,22,35,26,28,19,49,18,37,23
27,43,14 | 41,32,35,2,28,22,49,26,37,19,40,18,47,23

Speler 2 is key:
37,10,50,7,41,24,46,21,47,22,40,19,28,25 | 18,36,14,45,15,30,2,48,27,38,13,31,3,43,17,49,1,33,20,29,23,44,12
28,10,37,7,50,24,41,21,46,22,47,19,40,25 | 18,36,14,45,15,30,2,48,27,38,13,31,3,43,17,49,1,33,20,29,23,44,12

Maar met mijn code maakt het niets uit als ik alleen de hand van speler 1 als key gebruik, slechts als ik alleen de hand van speler 2 als key gebruik krijg ik een verkeerde einduitkomst. Dat wil overigens niet zeggen dat je daaruit kan concluderen dat de hand van speler 1 voldoende is om loops te detecteren, er zal vast een input zijn waarbij dat niet gaat

[ Voor 8% gewijzigd door DataGhost op 22-12-2020 17:38 ]

[Anoniem: 511810]

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.

Inderdaad, ik had ook een input waar dit onderscheid tot een andere oplossing lijkt te voeren. In ieder geval duurt de iteratie meer als 50x langer, ik heb het toen maar afgekapt.

Update : toch maar even de variant met lijst1 AND lijst2 ipv lijst1 OF lijst2 afgetrapt en na bijna 20k recusies diep 'kapt' de boel eruit.

Ik vraag me af of het echt EN moet zijn zoals hierboven beargumenteerd wordt. Voor de testinput maakt het overigens absoluut niets uit....

[ Voor 13% gewijzigd door Anoniem: 511810 op 22-12-2020 19:09 ]

[Hydra]

Anoniem: 511810 schreef op dinsdag 22 december 2020 @ 17:45:
Voor de testinput maakt het overigens absoluut niets uit....

spoiler:

Dat zegt weinig helaas. Als je recursief de hele deck meegeeft in plaats van te limiteren op de lengte van het getrokken getal gaat het met de test input ook goed. Met de echte input kom je (in mijn geval) in een oneindige loop.

[Woy]

Anoniem: 511810 schreef op dinsdag 22 december 2020 @ 17:45:
[...]


Inderdaad, ik had ook een input waar dit onderscheid tot een andere oplossing lijkt te voeren. In ieder geval duurt de iteratie meer als 50x langer, ik heb het toen maar afgekapt.

Update : toch maar even de variant met lijst1 AND lijst2 ipv lijst1 OF lijst2 afgetrapt en na bijna 20k recusies diep 'kapt' de boel eruit.

Ik vraag me af of het echt EN moet zijn zoals hierboven beargumenteerd wordt. Voor de testinput maakt het overigens absoluut niets uit....

Heb je jouw input ergens beschikbaar, inclusief het juiste antwoord? De input van @Ethikka was ieder geval alleen juist als je met AND checked

[ydderf]

Anoniem: 511810 schreef op dinsdag 22 december 2020 @ 17:45:
[...]
Update : toch maar even de variant met lijst1 AND lijst2 ipv lijst1 OF lijst2 afgetrapt en na bijna 20k recusies diep 'kapt' de boel eruit.

Ik vraag me af of het echt EN moet zijn zoals hierboven beargumenteerd wordt. Voor de testinput maakt het overigens absoluut niets uit....

Heb je niet een foutje feature in je programma zitten?

spoiler:

Bij elke recursie moet je verder gaan met een kopie van je deck, waarbij de getrokken kaart niet wordt meegenomen en je net zoveel kaarten kopieert als de waarde van je getrokken kaart.
Ofwel je begint met 25 kaarten per persoon, dan zou je niet vaker als 25x diep kunnen gaan zonder dat 1 van beide spelers zonder kaarten komt te zitten

[ Voor 3% gewijzigd door ydderf op 22-12-2020 20:29 ]

[Ethikka]

Woy schreef op dinsdag 22 december 2020 @ 20:01:
[...]

Heb je jouw input ergens beschikbaar, inclusief het juiste antwoord? De input van @Ethikka was ieder geval alleen juist als je met AND checked

Checks op mijn input met OR gaan fout, maar AND of alleen checken op player 1 gaat dan wel weer goed (bij mn player 1 check in mijn initiele poging had ik waarschijnlijk ook nog last van andere bugs, who knows )

Check op alleen player 1 gaat sowieso goed voor de 5 inputs die ik tot nu toe heb geprobeert (en is behoorlijk sneller varierend van 275ms ipv 850ms tot 330ms ipv 1600ms)

[Woy]

Ethikka schreef op dinsdag 22 december 2020 @ 20:29:
[...]


Checks op mijn input met OR gaan fout, maar AND of alleen checken op player 1 gaat dan wel weer goed (bij mn player 1 check in mijn initiele poging had ik waarschijnlijk ook nog last van andere bugs, who knows )

Check op alleen player 1 gaat sowieso goed voor de 5 inputs die ik tot nu toe heb geprobeert (en is behoorlijk sneller varierend van 275ms ipv 850ms tot 330ms ipv 1600ms)

Ok, maar de beschrijving is wel "duidelijk"

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,

De apastrophe achter players maakt het een plural possessive noun, dus duidt imho beide spelers aan. Dat het met een enkele check vaak hetzelfde resultaat heeft doet daar niks aan af

[Anoniem: 511810]

Woy schreef op dinsdag 22 december 2020 @ 20:01:
[...]

Heb je jouw input ergens beschikbaar, inclusief het juiste antwoord? De input van @Ethikka was ieder geval alleen juist als je met AND checked

zeker:
Player_1=[ 50 14 10 17 38 40 3 46 39 25 18 2 41 45 7 47 36 1 30 32 8 31 12 5 28];
Player_2=[ 9 6 37 42 22 4 21 15 44 16 29 43 19 11 13 24 48 35 26 23 27 33 20 49 34];

met als uitkomst voor deel 1: 35299

en voor deel 2: 33266 (met 3855 individuele iteraties)

los van dit alles: vraag me af of er een diepere reden is om geen gelijke getallen toe te staan in de input (met bijbehorende regel uiteraard)


code staat onder dag22: https://github.com/nono-einstein

ben benieuwd of er bij jou wel iets uitkomt met de AND...

[ Voor 10% gewijzigd door Anoniem: 511810 op 22-12-2020 20:55 ]

[Anoniem: 511810]

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


Heb je niet een foutje feature in je programma zitten?

spoiler:

Bij elke recursie moet je verder gaan met een kopie van je deck, waarbij de getrokken kaart niet wordt meegenomen en je net zoveel kaarten kopieert als de waarde van je getrokken kaart.
Ofwel je begint met 25 kaarten per persoon, dan zou je niet vaker als 25x diep kunnen gaan zonder dat 1 van beide spelers zonder kaarten komt te zitten

Nee, dat feature heb ik niet.. maar dan nog, als je op de 1 of andere manier op
[1]
[n-1 n-2 n-3 n-4....1] uit zou komen kun je al 49 diep gaan...

[Woy]

Anoniem: 511810 schreef op dinsdag 22 december 2020 @ 20:52:
[...]


zeker:
Player_1=[ 50 14 10 17 38 40 3 46 39 25 18 2 41 45 7 47 36 1 30 32 8 31 12 5 28];
Player_2=[ 9 6 37 42 22 4 21 15 44 16 29 43 19 11 13 24 48 35 26 23 27 33 20 49 34];

met als uitkomst voor deel 1: 35299

en voor deel 2: 33266 (met 3855 individuele iteraties)

los van dit alles: vraag me af of er een diepere reden is om geen gelijke getallen toe te staan in de input (met bijbehorende regel uiteraard)


code staat onder dag22: https://github.com/nono-einstein

ben benieuwd of er bij jou wel iets uitkomt met de AND...

Ja bij mij komt er met AND gewoon hetzelfde antwoord uit.

[Woy]

Het is op zich ook erg logisch dat het performance verschil zo groot is, bij jouw input zou je ~1,1 miljoen keer eerder een recursion aangeven dan bij de both player situatie.

C#:

if ((player1Hands.Contains(p1Hand) || player2Hands.Contains(p2Hand)) && !bothPlayerHands.Contains(strHands))
                    _totalMismatch++;

[Woy]

Qua recursion heb ik het ook even uitgezocht, en ik ga max 7 niveaus diep.

[Anoniem: 511810]

Woy schreef op dinsdag 22 december 2020 @ 21:11:
[...]

Ja bij mij komt er met AND gewoon hetzelfde antwoord uit.

hmm,OK.
Ik ga wellicht morgen nog eens in de code duiken, afhankelijk natuurlijk van de moeilijkheidsgraad van de volgede. Maar intrigerend is het wel.
Hoelang heb je gerekend voor de AND situatie met mijn input??

[ Voor 0% gewijzigd door Anoniem: 511810 op 22-12-2020 23:23 . Reden: typo ]

[Down]

Voor vandaag het veilige C# maar weer eens omgeruild voor het niet-zo-veilige JS .

Helaas krijg ik voor deel twee voor de echte input de melding dat het antwoord te hoog is. Voor de voorbeeld input werkt het uiteraard wel, dus het zal wel aan de recursie check liggen.

Net als anderen hier de verschillende opties geprobeerd voor de check, maar dat biedt helaas geen uitkomst. Goed, nu kan ik in bed kruipen bij m'n vriendin of het even omkatten naar C#. Misschien dat ik het dan per ongeluk fix. Keuzes..

EDIT:

Deel 2 in C# geeft wel het goede antwoord. Voor m'n gevoel heb ik gewoon de JS geport naar C# (maar dan met een Queue<T> i.p.v. een array, en voor de recurse check de cast naar char gedaan zoals hier werd geopperd), maar er zal wel ergens een foutje ingeslopen zijn. Ik ga het verder ook niet debuggen, het is goed zo. Eens zien of ik nog welkom ben in bed..

[ Voor 28% gewijzigd door Down op 23-12-2020 02:07 ]

[Varienaja]

Mooi optimalisatiegeval vandaag! Even nadenken..

[armageddon_2k1]

Er zit vast een mooi handigheidje in puzzel part 2 vandaag, maar ik zie hem niet. Ik ga het even laten rusten.

spoiler:

Gewoon kwestie van juiste data-structuur kiezen (double linked-list of een soort ring-structure), maar geen zin nu om die te implementeren. M'n vermoeden is dat ik niet de standaard van Java kan gebruiken omdat je, voor het selecteren van de drie die wegmoeten, bij deze alleen op index kan werken. En je wilt juist echt op 'node' basis werken met het inserten en weghalen etc.

[ Voor 64% gewijzigd door armageddon_2k1 op 23-12-2020 09:11 ]

[Woy]

Ik heb zowel deel 1 als 2 snel geimplementeerd, maar ik denk bij deel 2 toch iets niet helemaal goed gelezen, want ik krijg het verkeerde antwoord, ook bij de testcase.

In mijn pauze nog maar eens goed lezen.

[Dricus]

Dag 23 (Kotlin)

Deze was leuk! Performance kan misschien nog wel beter. Deel 2 heeft nu zo'n 1,7 seconden nodig.

spoiler:

Ik had meteen bij part 1 voor een single linked list structuur gekozen. Daardoor hoef ik dus helemaal geen list manipulatie te doen, maar alleen wat references te wijzigen. De enige optimalisatie die ik voor deel 2 heb gedaan, was om een index te maken om snel de cup met een label te vinden.

[MerijnB]

Ik heb een paar dagen niet zoveel tijd gehad, ben nu weer aan het inhalen, nog even een verlate vraag over day 19 part 2.
Kan iemand me vertellen waarom uit het voorbeeld "babbbbaabbbbbabbbbbbaabaaabaaa" als match zou gelden? Ik vind wel een match, maar die heb ik al voordat alle rules zijn afgelopen, dat geldt dan toch niet denk ik? Heeft iemand nog een app die log kan genereren over dit voorbeeld oid?
Hier een past van mijn log.

[Woy]

Dricus schreef op woensdag 23 december 2020 @ 10:09:
Dag 23 (Kotlin)

Deze was leuk! Performance kan misschien nog wel beter. Deel 2 heeft nu zo'n 1,7 seconden nodig.

spoiler:

Ik had meteen bij part 1 voor een single linked list structuur gekozen. Daardoor hoef ik dus helemaal geen list manipulatie te doen, maar alleen wat references te wijzigen. De enige optimalisatie die ik voor deel 2 heb gedaan, was om een index te maken om snel de cup met een label te vinden.

Ik had inderdaad exact hetzelfde, ook bij deel 1 al voor de juiste structuur gekozen, en bij deel 2 een extra lookup toegevoegd.

[Woy]

Ah, nog een keer gekeken en de fout gevonden, ik had bij het bepalen van de volgende value nog een hardcoded 9 staan

[Hydra]

Yikes. Deel 1 gelukt, helaas gaat deel 2 niet op deze manier werken. Back to the drawing board.

spoiler:

Voor deel 1 gewoon een wrapper om een ArrayList gebouwd om 'em circulair te maken. Helaas gaat 'em dat niet worden voor deel 2; op dit moment gaat 'ie 60 uur doen voor 'ie resultaat heeft

[Anoniem: 511810]

Hydra schreef op woensdag 23 december 2020 @ 11:03:
Yikes. Deel 1 gelukt, helaas gaat deel 2 niet op deze manier werken. Back to the drawing board.

spoiler:

Voor deel 1 gewoon een wrapper om een ArrayList gebouwd om 'em circulair te maken. Helaas gaat 'em dat niet worden voor deel 2; op dit moment gaat 'ie 60 uur doen voor 'ie resultaat heeft

Yep, zit ik ook mee, kijken of dat slimmer kan. Bij test met 1000 iteraties kom ik op 19 seconden, dus dat wordt dan ~ 50 uur...

[Woy]

Hydra schreef op woensdag 23 december 2020 @ 11:03:
Yikes. Deel 1 gelukt, helaas gaat deel 2 niet op deze manier werken. Back to the drawing board.

spoiler:

Voor deel 1 gewoon een wrapper om een ArrayList gebouwd om 'em circulair te maken. Helaas gaat 'em dat niet worden voor deel 2; op dit moment gaat 'ie 60 uur doen voor 'ie resultaat heeft

spoiler:

Ik heb gewoon een linkedlist gepakt, en aan het begin een lookup table met alle elementen om ook random access te kunnen doen.

[Woy]

Hier mijn opgeschoonde oplossing: https://github.com/rverst.../blob/main/Y2020/Day23.cs

spoiler:

Ik heb het toch even omgeschreven naar een eigen linked list implementatie, dat ziet er wat schoner uit qua code

[DataGhost]

armageddon_2k1 schreef op woensdag 23 december 2020 @ 08:46:
Er zit vast een mooi handigheidje in puzzel part 2 vandaag, maar ik zie hem niet. Ik ga het even laten rusten.

spoiler:

Gewoon kwestie van juiste data-structuur kiezen (double linked-list of een soort ring-structure), maar geen zin nu om die te implementeren. M'n vermoeden is dat ik niet de standaard van Java kan gebruiken omdat je, voor het selecteren van de drie die wegmoeten, bij deze alleen op index kan werken. En je wilt juist echt op 'node' basis werken met het inserten en weghalen etc.

Wat er in je spoiler staat heb ik in 18 korte regeltjes python staan dus "geen zin om te implementeren", tsja...

[DataGhost]

Soultaker schreef op zondag 20 december 2020 @ 16:53:
[..]

spoiler:

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]).

Toen ik aan deel 1 van vandaag bezig was, was ik alvast vooruit aan het denken naar wat deel 2 zou kunnen zijn. Daardoor

spoiler:

heb ik gelukkig direct een linked list gemaakt maar daarnaast had ik ook gegokt dat deel 2 grotere getallen (correct) zou hebben en dat ze niet allemaal consecutive hoefden te zijn (incorrect). Voor dat laatste stuk heb ik een extra lookup-table (slookup) gemaakt in de vorm van een list met daarin gesorteerd alle nummers in de cups, en nog een lookup (rslookup) met alle nummers naar de positie in slookup. Vervolgens:
dest = cll.slookup[cll.rslookup[current.val]-1]
while dest in pickup:
    dest = cll.slookup[cll.rslookup[dest]-1]
Hier kan er uiteindelijk iets komen te staan als cll.slookup[0-1] wat automatisch wrapt naar de andere kant

[Hydra]

En bam! Tweede ster

[Woy]

Zo, nog even een korte optimalisatieslag eroverheen ( Voornamelijk geheugenallocaties verminderd tijdens de executie ), part 2 runt nu in 618ms, het is weer mooi voor vandaag.

[Dricus]

Ik heb nog een optimalisatie weten te vinden. Deel 2 duurt nu ongeveer 1 seconde gemiddeld. Toch 700ms winst ten opzichte van de vorige versie.

spoiler:

De index die ik eerst maakte was een map van een label naar een cup. Dit is nu een array. De index in de array is dan het label. Een array lookup is dus behoorlijk wat sneller dan een map lookup .

[Hydra]

Dag 23 in Kotlin.

spoiler:

Met de bijbehorende LinkedList die nodig is voor deel 2. Ik heb 'em herbruikbaar gemaakt; zal vast nog wel eens terug gaan komen.

Misschien later nog wat optimalisaties (zoals Dricus net meldde) doorvoeren, nu eerst ff gezellig doen

[Hydra]

Dricus schreef op woensdag 23 december 2020 @ 10:09:
Dag 23 (Kotlin)

spoiler:

Nice die tail recursion. Was zelf niet op 't idee gekomen!

[Dricus]

Hydra schreef op woensdag 23 december 2020 @ 12:43:

spoiler:

Nice die tail recursion. Was zelf niet op 't idee gekomen!

spoiler:

Thanks! Linked lists (oftewel Wikipedia: cons) werken heel lekker in combinatie met recursion . Twee van de 3 tailrec functies blijken trouwens helemaal niet nodig te zijn zie ik nu. Meteen maar even opgeschoond.

[Hydra]

Dricus schreef op woensdag 23 december 2020 @ 12:53:

spoiler:

Thanks! Linked lists (oftewel Wikipedia: cons) werken heel lekker in combinatie met recursion . Twee van de 3 tailrec functies blijken trouwens helemaal niet nodig te zijn zie ik nu. Meteen maar even opgeschoond.

spoiler:

Ja goeie. Hoewel ik het wel weet, was ik hier niet echt op 't idee gekomen. Ik dacht in deel 1 ook weg te komen zonder een eigen LinkedList implementatie maar door gewoon een ArrayList te gebruiken en deze circulair te gebruiken. Bij nader inzien is het met een circulaire LinkedList eigenlijk ook veel simpeler. Ik heb 'em ook generiek gemaakt zodat 'ie later opnieuw te gebruiken is. Wie weet de komende dagen

[Soultaker]

DataGhost schreef op woensdag 23 december 2020 @ 11:45:

code:

dest = cll.slookup[cll.rslookup[dest] - 1]

Okee, toegegeven dat is een geldig voorbeeld Maar als je expres wil wrappen is het een kleine moeite om het zo te schrijven:

code:

dest = cll.slookup[(cll.rslookup[dest] - 1) % len(cll.slookup)]

Explicit is better than implicit (bron).

En trouwens, het is ook lelijk dat het omgekeerde niet kan:

code:

dest = cll.slookup[cll.rslookup[dest] + 1]

zou gewoon een IndexError gegeven. Je kan mij niet vertellen dat dat consistent is.

[ Voor 17% gewijzigd door Soultaker op 23-12-2020 13:30 ]

[Soultaker]

Oplossing voor dag 23 in Python die in een halve seconde loopt.

spoiler:

Ik zie dat veel mensen een expliciete linked list gemaakt hebben, maar dat is voor dit probleem helemaal niet nodig: je kunt de cirkel implementeren met een eenvoudige integer array. Veel simpeler én sneller.

[Dricus]

Soultaker schreef op woensdag 23 december 2020 @ 13:58:
Oplossing voor dag 23 in Python die in een halve seconde loopt.

spoiler:

Ik zie dat veel mensen een expliciete linked list gemaakt hebben, maar dat is voor dit probleem helemaal niet nodig: je kunt de cirkel implementeren met een eenvoudige integer array. Veel simpeler én sneller.

spoiler:

Ik had precies zo'n oplossing in Kotlin geïmplementeerd, maar die was significant langzamer dan de expliciete linked list. Misschien deed ik nog iets niet handig, ik weet het niet meer. Ik ga misschien nog wel even kijken wat de performance is als ik jouw implementatie naar Kotlin port.

[Woy]

Ik had nog een ingeving om het een flink stuk sneller te maken, door puur gebruik te maken van value types zonder references ( Buiten de lookup zelf ), dat is aanzienlijk sneller, nu in 247ms voor part2

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

[Soultaker]

Dricus schreef op woensdag 23 december 2020 @ 14:10:

spoiler:

Ik had precies zo'n oplossing in Kotlin geïmplementeerd, maar die was significant langzamer dan de expliciete linked list. Misschien deed ik nog iets niet handig, ik weet het niet meer.

Mogelijk een ArrayList<Integer> gebruikt in plaats van een primitieve int array? In het eerste geval kan boxing/unboxing je een hoop performance kosten (al kun je dat ook vermijden als je zorgvuldig code). In het tweede geval kan ik me eigenlijk niet voorstellen dat het trager is.

[Woy]

Soultaker schreef op woensdag 23 december 2020 @ 13:58:
Oplossing voor dag 23 in Python die in een halve seconde loopt.

spoiler:

Ik zie dat veel mensen een expliciete linked list gemaakt hebben, maar dat is voor dit probleem helemaal niet nodig: je kunt de cirkel implementeren met een eenvoudige integer array. Veel simpeler én sneller.

spoiler:

Ja mijn oplossing is nu vergelijkbaar, hoewel ik een array met een struct met twee ints heb, die overhead van de struct zou er inderdaad nog uit kunnen, maar ik vermoed dat het niet heel veel winst op zal leveren qua execution time

[Varienaja]

Dag 23.

spoiler:

Ik had onderdeel A met een LinkedList gedaan. Voor onderdeel B was de .indexOf() aanroep natuurlijk te traag, want O(n). Dus de boel omgeschreven naar een ad-hoc zelfgeknutselde LinkedList met lookup-array.

Ik heb lang gekeken of ik voor B niet toch de LinkedList van Java kon gebruiken, door bijvoorbeeld een Array van ListIterators te bewaren voor de snelle lookup. Maar dat feest ging niet door, omdat ze dan allemaal in paniek raken en ConcurrentModificationExceptions gooien. Ik heb er nog over nagedacht om de node(int) methode te overschrijven, maar vond het ook zo lelijk om dan een complete kopie van java.util.LinkedList te maken, zodat ik de package-protected methode kan overschrijven door een lookup ipv een sequential scan.

Ik heb dus de ad-hoc LinkedList maar laten zitten in de opgeschoonde code.

[Anoniem: 511810]

Hier loop ik toch tegen de limieten van een geinterpreteerde taal (Matlab) aan...
versie met copy lijsten : 56 uur (schatting
versie met indexering voor linking en lookup. toch nog ~90 seconden. al wel niet heel veel sneller gaan met matlab, maar houd me aanbevolen...

[armageddon_2k1]

DataGhost schreef op woensdag 23 december 2020 @ 11:45:
[...]

Wat er in je spoiler staat heb ik in 18 korte regeltjes python staan dus "geen zin om te implementeren", tsja...

Dag 23 in Kotlin

Dat weet ik Maar ik had geen zin om nog verder achter de computer te zitten.

Doet er 11 sec over. Mijn shortcut is niet erg snel denk ik. Ach pech.

[ Voor 19% gewijzigd door armageddon_2k1 op 23-12-2020 15:45 ]

[Dricus]

Soultaker schreef op woensdag 23 december 2020 @ 14:20:
Mogelijk een ArrayList<Integer> gebruikt in plaats van een primitieve int array? In het eerste geval kan boxing/unboxing je een hoop performance kosten (al kun je dat ook vermijden als je zorgvuldig code). In het tweede geval kan ik me eigenlijk niet voorstellen dat het trager is.

Je hebt helemaal gelijk! Ik gebruikte Array<Int>. Nu ik een native int array gebruik (IntArray) is het veel sneller: ±220 milliseconden .

[armageddon_2k1]

Zo, ik ben ook van 11 sec naar 200ms gegaan.

IntArray in Kotlin ftw!

Weer wat geleerd

Wat wel fucking vervelend is is dat m’n IntelliJ besloten heeft helemaal naar de klote te gaan. Autocomplete, errors, allemaal supertraag of helemaal fout, waardoor code kloppen geen lolletje is.

Binnenkort m’n Mac maar eens opnieuw installeren wat ik van plan was.

[ Voor 59% gewijzigd door armageddon_2k1 op 23-12-2020 16:06 ]

[ydderf]

Hmmm, vandaag gaat deel 2 iets boven mijn kennis niveau om een redelijke performance te krijgen. Zegmaar dat je de tijd beter in uren kunt uitdrukken dan in msec.
Eerste opdracht lekker simpel met int array gedaan. Daarna deel twee omgezet naar een List met de onderstaande logica.

spoiler:

De eerste vier waardes onthouden en verwijderen. Waarde twee t/m vier op de juiste plek tussenvoegen en de eerste waarde weer achteraan toevoegen.

En een hashtable kan je hiervoor niet gebruiken als ik het goed begrijp, aangezien deze geen gegarandeerde volgorde heeft.

[Woy]

@ydderf

spoiler:

het is goed mogelijk om data in meerdere datastructuren tegelijk zetten. Mijn eerste versie had voor de daadwerkelijke Cups een LinkedList structuur, die is handig omdat je daar elementen kunt toevoegen/verwijderen zonder dat je alle andere elementen moet herordenen zoals in bijvoorbeeld een array.

Daarnaast had ik een dictionary om snel aan de hand van een value de juiste LinkedListNode op te zoeken.

Op deze manier gebruik je meerdere datastructuren voor hun sterke eigenschappen.

Zoals @Soultaker opmerkt is het echter ook mogelijk om met een enkele array van integers op te lossen. De index van de array is het element, de value is de verwijzing naar het volgende element.

[ Voor 7% gewijzigd door Woy op 23-12-2020 18:50 ]

[ydderf]

Het idee achter de oplossing van Soultaker is me duidelijk en met de eerste opzet komt de tijd al onder de twee seconde. Helaas alleen het antwoord nog niet goed, dus dat word morgen nog ff puzzelen...

[ZieglerNichols]

Anoniem: 511810 schreef op woensdag 23 december 2020 @ 15:13:
Hier loop ik toch tegen de limieten van een geinterpreteerde taal (Matlab) aan...
versie met copy lijsten : 56 uur (schatting
versie met indexering voor linking en lookup. toch nog ~90 seconden. al wel niet heel veel sneller gaan met matlab, maar houd me aanbevolen...

Ik had de limieten van Matlab ook al snel door voor deel 2, dus ben maar naar Python geswitched. Matlab is geweldig voor snel testen van code en voor de eerste 2 weken van AoC. Daarna beginnen de nadelen van geïnterpreteerde talen sneller duidelijk te worden. Toch begin ik altijd met Matlab voor AoC.

[StefanLemmens]

Het is toch vooral een kwestie van het probleem juist aan te pakken. In LabVIEW heb ik geen List of iets dergelijks maar met 1 array van integers slaag ik er toch in om de juiste uitkomst te bekomen in 380 msec.

[armageddon_2k1]

@ZieglerNichols @Anoniem: 511810 Python is ook een interpreted language.

Dat MatLab traag is heeft niet direct heel veel te maken met interpreted of niet, maar meer waar het voor geoptimaliseerd is. Voor matrix-calculaties worden onderliggend gewoon de BLAS en LAPACK libraries aangewend.

Dus als je je probleem in mooie matrix / vector oplossingen kan schrijven is het bloedje snel.
Daarnaast zie ik op Reddit meer dan genoeg oplossingen in MatLab die snel zijn

[ Voor 10% gewijzigd door armageddon_2k1 op 23-12-2020 21:04 ]

[ZieglerNichols]

armageddon_2k1 schreef op woensdag 23 december 2020 @ 21:03:
@ZieglerNichols @Anoniem: 511810 Python is ook een interpreted language.

Dat MatLab traag is heeft niet direct heel veel te maken met interpreted of niet, maar meer waar het voor geoptimaliseerd is. Voor matrix-calculaties worden onderliggend gewoon de BLAS en LAPACK libraries aangewend.

Dus als je je probleem in mooie matrix / vector oplossingen kan schrijven is het bloedje snel.
Daarnaast zie ik op Reddit meer dan genoeg oplossingen in MatLab die snel zijn

Ja, dat is waar. Ik denk dat de opdracht voor vandaag wat lastiger is te doen met een mooie matrix-oplossing, maar voor de meeste andere dagen was Matlab zeer goed te doen.

Ik zag nu net ook dat Matlab enige ondersteuning heeft voor een linked List. Geen idee hoe snel dat is, maar het kan dus wel.

[Anoniem: 511810]

ZieglerNichols schreef op woensdag 23 december 2020 @ 21:13:
[...]


Ja, dat is waar. Ik denk dat de opdracht voor vandaag wat lastiger is te doen met een mooie matrix-oplossing, maar voor de meeste andere dagen was Matlab zeer goed te doen.

Ik zag nu net ook dat Matlab enige ondersteuning heeft voor een linked List. Geen idee hoe snel dat is, maar het kan dus wel.

Ik heb een array van 1e6x4 gebruikt:

spoiler:

1e vector de startwaardes van de lijst
2e vector een verwijzing naar het volgende element
3e vector de index van de array zelf (al is deze niet per se nodig..)
4e vector de uitkomst van sort(array(:,1), zodat ik direct naar een waarde kan springen

vreemd genoeg kost deze oplossing met een double array de helft van de tijd als exact dezelfde code met int32 arrays en variabelen ?!?!

met de profiler gekeken wat eruit springt en dat is een any() operatie op een vector van de drie waardes waarmee de kaartwaarde-1 vergeleken moet worden. Kan het omschrijven naar () && () && () (met dus voorwaardelijke berekening) maar dat zal niet heel veel opschieten. (misschien 10% sneller.
Ik verwacht dat het opsplitsen van de 1e6x4 in 4x 1e6 (dus losse) verctoren wel iets zou kunnen helpen, maar ik verbaas me er dan wel over dat een Python oplossing zoveel sneller kan zijn (of ik heb toch ergens nog een voor de hand liggende optimalisatie niet gezien...)

[DataGhost]

armageddon_2k1 schreef op woensdag 23 december 2020 @ 21:03:
@ZieglerNichols @Anoniem: 511810 Python is ook een interpreted language.

Dat MatLab traag is heeft niet direct heel veel te maken met interpreted of niet, maar meer waar het voor geoptimaliseerd is. Voor matrix-calculaties worden onderliggend gewoon de BLAS en LAPACK libraries aangewend.

Dus als je je probleem in mooie matrix / vector oplossingen kan schrijven is het bloedje snel.
Daarnaast zie ik op Reddit meer dan genoeg oplossingen in MatLab die snel zijn

Python wordt wel eerst omgezet in bytecode en dat wordt uitgevoerd, dus puur interpreted is het ook weer niet. Dan heb je ook nog PyPy, wat er een JIT compiler overheen gooit. Mijn python-oplossing is nu in 2.3 sec klaar met de standaard python-runtime, met PyPy duurt het nog maar 410ms. Ter vergelijking, mijn oplossing in C++ (eigenlijk alleen maar C) heeft 150ms nodig dus dat is in vergelijking behoorlijk goed.

Verder helemaal met je verhaal eens, dus @ZieglerNichols het hangt er helemaal van af wat voor datastructuren je gebruikt voor de taal en eventueel zelfs interpreter die je gebruikt. Alles wat native al doet wat je wilt is waarschijnlijk veel sneller geïmplementeerd dan wanneer je het zelf moet schrijven in de taal waarin je bezig bent. Maar de manier van implementatie maakt daarbij ook nog veel uit. Zo heb ik op mijn 9 jaar oude laptop de volgende looptijden:

spoiler:

python3 met een list: 6.8s
python3 met een array: 5.7s
pypy3 met een list: 1.0s
pypy3 met een array: 3.0s

Ze doen allemaal exact hetzelfde maar gebruiken een andere interpreter, en daarbij is te zien dat de implementatie van de datastructuren dusdanig verschillend is dat performancewinst voor de ene een performanceverlies voor de andere betekent. En beide datastructuren zijn native, maar hebben toch verschillende performance. Dus dat iets op een manier werkt wil niet zeggen dat er geen andere manier is die hetzelfde kan, maar sneller. Je weet alleen nog niet hoe. Een native linkedlist zou zomaar een hoop performance voor je kunnen schelen, maar dat is niet de enige oplossing.

[ Voor 4% gewijzigd door DataGhost op 23-12-2020 21:59 ]

[ZieglerNichols]

Het leuke aan AoC vind ik dat AoC oplossingen niet hetzelfde doel hebben als productie-code genereren. Daarom kan Matlab soms veel tijd besparen. Veel bugs in AoC hebben bijvoorbeeld te maken met type overflow, omdat dit in productie code belangrijk is, maar daar heb ik in Matlab niks mee te maken. Ik definieer een variabele x, zonder type, en daar kan alles in. Ik weet dat dit in praktijk soms problemen kan geven, maar voor AoC werkt het goed!

[Dido]

Weer de eerste gold star hier vandaag

spoiler:

Hoeveelste game of life is dit? Volgens mij minmaal de derde... achteraf voelt het alsof een generieke game-of-life simulator de moeite waard was geweest
De eerder gebruikte taktiek om voor alle actieve tiles alle neigbours te markeren in plaats van voor elke mogelijke cel zijn actieve neighbours te tellen had ik al eerder ingezet en maakt het leven hier ook weer een stuk simpeler

[Varienaja]

spoiler:

Deze link https://www.redblobgames.com/grids/hexagons/ had ik nog van een vorige AoC. Het kostte me enige moeite om te ontdekken waarom mijn aantal zwarte tegels zo snel groeide. Ik rekende eerst naïef met 26 (3D ) buren in plaats van 6...

[Dido]

Varienaja schreef op donderdag 24 december 2020 @ 07:54:

spoiler:

Deze link https://www.redblobgames.com/grids/hexagons/ had ik nog van een vorige AoC. Het kostte me enige moeite om te ontdekken waarom mijn aantal zwarte tegels zo snel groeide. Ik rekende eerst naïef met 26 (3D ) buren in plaats van 6...

spoiler:

Overengineering
Ik heb mijn grid trouwens heel simpel gehouden door op de x-as altijd +/- 2 te doen, en in de andere vier richtingen zowel z als x met 1 op te schuiven. Dat levert de facto ook hexagons op, met "gaten" in de rijen. Verder was dit daardoor maar 75% procent van het werk tov vierkante cells (6 richtingen tegenover 8 ).
Enige bugje vandaag zat in een voorbereidende stap in dele 1. Ik verving eerst alle "nw" door "a", "ne" door "b", enzovoort, zodat ik daarna simpeler kon parsen. Door een copy/paste foutje verving ik echter twee keer dezelfde richting, wat voor heel vage antwoorden zorgde

[Varienaja]

Dido schreef op donderdag 24 december 2020 @ 08:02:

spoiler:

Enige bugje vandaag zat in een voorbereidende stap in dele 1. Ik verving eerst alle "nw" door "a", "ne" door "b", enzovoort, zodat ik daarna simpeler kon parsen. Door een copy/paste foutje verving ik echter twee keer dezelfde richting, wat voor heel vage antwoorden zorgde

O dat zijn vervelende situaties. Vooral als je, zoals ik, in de gauwigheid geen code bouwt om te visualiseren wat er eigenlijk aan de hand is.

[armageddon_2k1]

Dag 24 in Kotlin

Wel nog aardstraag voor Part 2 (24 sec). Moet even kijken hoe dat komt.
Was wel erg leuk! Niet echt moeilijk overigens, had het in 1x typen meteen goed.

EDIT:
Wederom een simpele wijziging van collection gaat ie van 24 sec naar 400ms.

[ Voor 18% gewijzigd door armageddon_2k1 op 24-12-2020 09:17 ]

[eamelink]

De eerste 80% was zo'n beetje de puzzel oplossen. De tweede 80% was ontdekken dat 'nul of meer dan twee' niet hetzelfde is als 'alles behalve één'

[Hydra]

Pfoe. Best ff mee bezig geweest. Eerst in deel 1 een denkfout en toen toch maar een fatsoenlijk hex grid geimplementeerd. Daarna in deel 2 nog een tijdje vastgezeten:

spoiler:

Je moet de 'border' steeds verder uitbreiden als je een hashmap gebruikt, en dat had ik over 't hoofd gezien.

Anyway; Dag 24 in Kotlin. Wel voor mijn opschoonrondje; heb ik pas vanavond tijd voor.

[armageddon_2k1]

Valt me wel op dat ik de laatste week overschakel van voornamelijk functioneel naar imperatief. Simpele while loops en assignments. Dat lijkt vaak ordegroottes sneller te zijn, volgens mij omdat Kotlin geen goede persistent collections heeft. In Scala kan ik me herinneren dat het vaak niet zo traag was.

Maar misschien heb ik gewoon te weinig FP ervaring.

[Woy]

Deze was weer erg eenvoudig, alleen in deel 2 las ik even verkeerd. Bij de eerste regel las ik het alsof de tiles black zouden blijven, maar ze moesten juist naar wit gedraaid worden.

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

[Dricus]

Dag 24 (Kotlin)

Deze was heel goed te doen. En inderdaad de derde game of life variant. Deze vond ik wel wat leuker dan de vorige, vanwege het hexagonal grid wat je moet maken.

De performance is nog abominabel, met 8,5 seconden voor deel 2. Ik ga nog even zelf kijken of ik wat slimmigheidjes verzinnen kan om dat beter te krijgen, voordat ik naar andere code ga kijken .

@armageddon_2k1 Dat doe ik inderdaad ook. Het klopt volgens mij dat Kotlin geen goede persistent collections heeft. De immutable varianten gebruiken voor zover ik gezien heb allemaal een copy-on-write strategie om een nieuwe collection te maken op basis van een bestaande + een wijziging. En da's niet zo efficiënt .

[Woy]

@armageddon_2k1 ik wissel een beetje tussen functioneel en imperatief, op zich zie ik niet hele grote performance verschillen als de aanpak hetzelfde is. Imperatief kan het meestal net iets snell omdat je vaak wat geheugen allocaties kunt voorkomen.

Het is een beetje afhankelijk van het probleem wat ik kies, vandaag weer wat meer functioneel, maar ook niet volledig, want de loop van 100 vind ik makkelijk lezen als daadwerkelijk loop.

[Dricus]

Woy schreef op donderdag 24 december 2020 @ 09:30:
@armageddon_2k1 ik wissel een beetje tussen functioneel en imperatief, op zich zie ik niet hele grote performance verschillen als de aanpak hetzelfde is. Imperatief kan het meestal net iets snell omdat je vaak wat geheugen allocaties kunt voorkomen.

Het is een beetje afhankelijk van het probleem wat ik kies, vandaag weer wat meer functioneel, maar ook niet volledig, want de loop van 100 vind ik makkelijk lezen als daadwerkelijk loop.

Het gaat hier vooral om het al-dan-niet gebruik maken van immutable/persistent collections. Bij échte FP talen (Scala, Clojure, etc) zijn die efficiënt geïmplementeerd met RRB trees en HAMTs. Kotlin heeft wel immutable collections, maar die zijn niet gemaakt om met echte functional style code gebruikt te worden.

[Woy]

Dricus schreef op donderdag 24 december 2020 @ 09:35:
[...]

Het gaat hier vooral om het al-dan-niet gebruik maken van immutable/persistent collections. Bij échte FP talen (Scala, Clojure, etc) zijn die efficiënt geïmplementeerd met RRB trees en HAMTs. Kotlin heeft wel immutable collections, maar die zijn niet gemaakt om met echte functional style code gebruikt te worden.

Tuurlijk dat werkt zeker mee, maar imperatief mapt gewoon directer naar de daadwerkelijke executie op de processor. Functioneel krijg je er toch een extra stuk abstractie overheen, die natuurlijk grotendeels/geheel weg-geoptimaliseerd kan worden door de compiler/runtime. Het zal zeker geen ordes van grootte schelen, maar ik heb het idee dat je voor de allerhoogste performance met imperatief toch net iets beter zit. Daar zou ik in productie code bijna nooit voor die reden voor kiezen, want leesbaarheid/onderhoudbaarheid en implementatie snelheid is in 99% van de gevallen gewoon veel belangrijker.

In bijvoorbeeld C#, maar waarschijnlijk ook Kotlin zal je voor het loopen over een enumeratie een extra object en dus memory allocatie hebben, met een for-loop heb je alleen een stack-allocatie van je iteratie counter.

[ Voor 9% gewijzigd door Woy op 24-12-2020 09:52 ]

[eamelink]

Dricus schreef op donderdag 24 december 2020 @ 09:35:
Het gaat hier vooral om het al-dan-niet gebruik maken van immutable/persistent collections. Bij échte FP talen (Scala, Clojure, etc) zijn die efficiënt geïmplementeerd met RRB trees en HAMTs. Kotlin heeft wel immutable collections, maar die zijn niet gemaakt om met echte functional style code gebruikt te worden.

Hmm, dat verbaast me. Ik heb de afgelopen tien jaar voornamelijk Scala geprogrammeerd, met zo af en toe een flinke hap Java. Kotlin heeft me nooit echt getrokken; hoewel het is een significant en strict betere Java is, vind ik de verbetering te beperkt om de voordelen van Java los te laten. Scala vind ik aantrekkelijk als veel expressievere taal op de JVM.

Is het gebruikelijk om bijvoorbeeld de (immutable) Eclipse Collections te gebruiken met Kotlin? Ik vind ze wel aantrekkelijk (ook in Java), maar toch gebruik ik ze zelden vanwege de mismatch tussen het overweldigende gebruik van de standaardlib collecties in Java overal en deze collecties.

Maar voor zulke standalone puzzeltjes zou het wel geschikt zijn

[Mschamp]

Day 24 C#
Veel te lang bezig geweest voor ik door had dat ik een probleem had met de 0.

[FrankMennink]

Dag 24 in Python

spoiler:

Leuke variant op de game of life's die we eerder hebben gezien. Daardoor beide delen in 1 keer kunnen submitten. Ook hier alleen de relevante (zwarte tegels) coordinaten opgeslagen in een set en voor deel 2 alle neighbours van de zwarte tiles gepakt als set van mogelijke tiles die flippen.

Code runt in 2.9s. Kan vast sneller, maar ik vind t prima zo

[ydderf]

Dag 23 deel 2 zojuist ook afgerond. Ofja, eigenlijk had ik hem gisteren al afgerond, maar mijn antwoord werd niet goed bevonden. Totdat me vanmorgen opviel dat mijn antwoord wel heel erg op het antwoord van het voorbeeld leek
Op naar dag 24....

[Dido]

ydderf schreef op donderdag 24 december 2020 @ 11:18:
Dag 23 deel 2 zojuist ook afgerond. Ofja, eigenlijk had ik hem gisteren al afgerond, maar mijn antwoord werd niet goed bevonden. Totdat me vanmorgen opviel dat mijn antwoord wel heel erg op het antwoord van het voorbeeld leek
Op naar dag 24....

Dat heb ik ook gehad ja. 's Ochtends met een brakke harses zitten debuggen tot je met de voorbeeldinput het gezochte antwoord vindt, drie keer controleren, en dan dat antwoord op de site invoeren.

En dan natuurlijk opnieuw gaan zitten debuggen met nog maar een kop koffie

[Dricus]

Zo, ik heb de 8,5 seconden terug weten te brengen naar 280 milliseconden.

spoiler:

Ik houd een set bij van coördinaten van zwarte tiles en een 2D array van het hele grid voor snelle lookup. De set van zwarte tiles + het grid gebruik ik om te kijken welke zwarte tiles er wit moeten worden. In plaats van het hele grid door te akkeren voor de witte tiles, maak ik op basis van de witte neighbors van de set van zwarte tiles een lijst van witte tiles die zwart moeten worden. Volg je het nog? De code is duidelijker denk ik .

[Anoniem: 511810]

spoiler:

Oplossingin matlab gedaan, als 'grid' een staggered grid gebruikt zodat ik de standaard functies (convolute) kan gebruiken:
[...1 0 1 0 1 0 1...
...0 1 0 1 0 1 0 etc.
de kernel is dan
kernel=[0 1 0 1 0; ...
1 0 0 0 1; ...
0 1 0 1 0;];

run time 1.15 s

[Woy]

Dricus schreef op donderdag 24 december 2020 @ 12:32:
Zo, ik heb de 8,5 seconden terug weten te brengen naar 280 milliseconden.

spoiler:

Ik houd een set bij van coördinaten van zwarte tiles en een 2D array van het hele grid voor snelle lookup. De set van zwarte tiles + het grid gebruik ik om te kijken welke zwarte tiles er wit moeten worden. In plaats van het hele grid door te akkeren voor de witte tiles, maak ik op basis van de witte neighbors van de set van zwarte tiles een lijst van witte tiles die zwart moeten worden. Volg je het nog? De code is duidelijker denk ik .

spoiler:

Hoezo hou je uberhaupt een grid bij? Ik loop gewoon door de lijst van zwarte tiles van de vorige heen, en bereken daar een adjacency map door. Alle tiles die in de hasmap van de vorige turn zitten en 1 of 2 keer voorkomen, of niet in de vorige map voorkomen en 2 keer voorkomen zijn de nieuwe tiles.

Runtime is bij mij ~150 ms, en valt nog wel wat te optimaliseren.

[Asgardian]

Je kan je functie om aanliggende cellen op te zoeken cachen, misschien dat dat nog iets scheelt?

[Woy]

@Asgardian ik heb wel een lijst van de deltas vanaf een cel, maar welke cellen je moet opzoeken verschilt elke dag weer. Plus op zich is het optellen van een delta bij een coordinaat niet zo'n zware operatie ( twee optellingen ).

[Woy]

Ik heb mijn oplossing even omgeschreven naar een imperatieve oplossing, en zit nu op de 65ms, het algoritme is verder niet veranderd. De fuctionlere versie was ook nog wel wat te optimaliseren overigens.