Advent of Code 2022

[.oisyn]

Jern_97 schreef op vrijdag 9 december 2022 @ 19:29:
[...]

Toevallig zin om uit te leggen hoe je te werk gaat om dit probleem enigzins te parallelliseren?
Ik heb echt totaal geen idee...

spoiler:

In principe kun je op een willekeurige plek in de input stream beginnen, er zijn bij bepaalde moves wel garanties te maken waar de tail zich dan moet bevinden. Het enige wat je niet weet is waar je bent tov het begin, dus als het eerste deel is aangekomen waar het tweede deel is begonnen kun je de resultaten aan elkaar knopen. Zo kunnen meerdere threads dus hun eigen deel voor hun rekening nemen.

[Varienaja]

MatHack schreef op vrijdag 9 december 2022 @ 18:49:
Heb je het hier over dag 9? Want zo geheugen intensief is dag 9 toch niet? Ik heb maar 8GB in de VM waar ik in zit te werken en had geen enkele geheugenprobleem met jouw grote set (10M lines) in C#.

Interessant. Mijn code verschilt eigenlijk niet echt van de jouwe, maar 16GB geheugen is gewoon te weinig voor mijn implementatie. Wel raar, want het enige dat ik nodig heb zijn 100-200 miljoen coordinaten in een Set. Als een coordinaat in een Set 20 Byte neemt, dan zou je met 20*200 = 4G geheugen klaar moeten zijn. Klaarblijkelijk neemt de JVM wat meer. Ik bedoel maar: als het niet 20 Byte is, maar 80 dan zit je al aan 16GB...

[Soultaker]

MatHack schreef op vrijdag 9 december 2022 @ 18:49:
Heb je het hier over dag 9? Want zo geheugen intensief is dag 9 toch niet? Ik heb maar 8GB in de VM waar ik in zit te werken en had geen enkele geheugenprobleem met jouw grote set (10M lines) in C#.

Het hangt er erg vanaf welke datastructuren je gebruikt en of de voor de hand liggende standaarddatastructuren een beetje efficiënt geïmplementeerd zijn.

Bijvoorbeeld, als je in Python integers in een set gooit, dan heeft dat behoorlijk wat overhead:

$ /usr/bin/time -v python3 -c 'set(range(10_000_000))' |& grep 'Maximum resident set size'
	Maximum resident set size (kbytes): 584304

Dus een set met 10 miljoen integers (waarden < 1 miljard dus passen makkelijk in 32 bits) kost al 571 MB, of 58 bytes per integer!

En paren van integers, wat een natuurlijke representatie is voor dit probleem:

$ /usr/bin/time -v python3 -c 'set(zip(range(10_000_000), range(10_000_000)))' |& grep 'Maximum resident set size'
	Maximum resident set size (kbytes): 1525612

1489 MB, of 156 bytes per paar! Op die manier kun je in 8 GB dus slechts ~55 miljoen elementen kwijt, en als je de antwoorden van large-2 gezien hebt, dan snap je dat je met deze aanpak met Python in de problemen komt.

Ik vermoed dat b.v. een HashMap<> in Java ook niet enorm efficient is. In C++ met std::unordered_set<> was het ook niet fantastisch (alloceert een apart object per paar).

En als je beide delen tegelijk probeert op te lossen verdubbel je benodigde hoeveelheid geheugen ook nog eens (bijna).

[Soultaker]

Jern_97 schreef op vrijdag 9 december 2022 @ 19:29:
Toevallig zin om uit te leggen hoe je te werk gaat om dit probleem enigzins te parallelliseren?
Ik heb echt totaal geen idee...

Okee, hier komen veel spoilers

spoiler:

Het viel me op dat het simuleren van de bewegingen helemaal niet zo traag is. In mijn implementatie met absl::flat_hash_set doet de 44 MB dataset er ruim een minuut over, maar input lezen met scanf() duurt maar 1,3 s, en simuleren zónder de punten op te slaan 5,3 s extra, wat betekent dat ruim 60 seconde of ~90% van de tijd wordt besteed aan niets anders dan het updaten van die stomme hash table.

Vandaar dat ik begon met een single-threaded implementatie waarbij ik de punten die ik tijden de simulatie tegenkom niet in een hash table stop, maar in een vector. Op het eind sorteer ik de vectors en tel ik de unieke waarden. In theorie zou dat trager moeten zijn: O(N log N) voor het sorteren i.p.v. O(N) voor de hash set, maar in de praktijk blijkt het meer dan twee keer zo snel (mogelijk omdat sorteren veel meer locality of reference heeft dan hash table access).

In mijn laatste versie probeer ik het sorteren en dedupliceren parallel te doen met het simuleren. De code is nog erg lelijk: ik buffer een paar megabyte aan data en start dan een aparte thread om de data alvast te sorteren. Vervolgens bouw ik een stack van gesorteerde arrays en probeer ik lijsten van gelijke grootte online te mergen á la merge sort.

Er valt nog wel het een ander aan te verbeteren maar dit is al zeer veelbelovend.

[Soultaker]

.oisyn schreef op vrijdag 9 december 2022 @ 19:53:

spoiler:

In principe kun je op een willekeurige plek in de input stream beginnen, er zijn bij bepaalde moves wel garanties te maken waar de tail zich dan moet bevinden. Het enige wat je niet weet is waar je bent tov het begin, dus als het eerste deel is aangekomen waar het tweede deel is begonnen kun je de resultaten aan elkaar knopen. Zo kunnen meerdere threads dus hun eigen deel voor hun rekening nemen.

Ook een goed idee. Dat had ik nog niet verzonnen.

Ik had wel een andere manier bedacht om de simulatie te versnellen tot een paar memory lookups zonder loops:

spoiler:

Je kunt de simulatie reduceren tot een state machine.

Vervolgens kun je dan per state de positie van de staart opslaan relatief aan de kop. Voor elke beweging moet je dan de positie van de kop updaten (dat is triviaal) en de state transitie uitvoeren (state = table[state][direction]).

Aangezien er negen knopen zijn (de kop niet meegeteld) die elk op negen verschillende posities kunnen liggen ten opzichte van hun voorgang is het totaal aantal states 9⁹ = 387,420,489. Als je voor elke state 20 bytes opslaat (4 × 4 bytes voor transities, plus ~1 byte voor de positie van de staart, rond af naar boven) kost die tabel een kleine 8 GB. Die kun je van te voren berekenen en dan in het geheugen mappen.

[Creepy]

Dag 9 deel 1 af, deel 2 bijna. Maar laat begonnen vandaag en ff geen zin om het af te ronden. Komt van het weekend wel.

spoiler:

Head kan je direct berekenen. Tail dan stap voor stap laten volgen. Daarvan nog een loopje maken zodat de hele tail stap voor stap blijft volgen voor deel 2. Bijna klaar.... Had eerst een loop om elk onderdeel van de tail naar het einde te laten gaan en dan pas het volgende deel maar dat gaat logischerwijs niet werken.

[Cranzai]

Creepy schreef op vrijdag 9 december 2022 @ 22:06:
Dag 9 deel 1 af, deel 2 bijna. Maar laat begonnen vandaag en ff geen zin om het af te ronden. Komt van het weekend wel.

spoiler:

Head kan je direct berekenen. Tail dan stap voor stap laten volgen. Daarvan nog een loopje maken zodat de hele tail stap voor stap blijft volgen voor deel 2. Bijna klaar.... Had eerst een loop om elk onderdeel van de tail naar het einde te laten gaan en dan pas het volgende deel maar dat gaat logischerwijs niet werken.

Wij kunnen elkaar de hand schudden, deel 1 vlot in elkaar, de aanpassing naar deel 2 gaat niet helemaal tof, morgen verder

[Brilsmurfffje]

Cranzai schreef op vrijdag 9 december 2022 @ 22:19:
[...]


Wij kunnen elkaar de hand schudden, deel 1 vlot in elkaar, de aanpassing naar deel 2 gaat niet helemaal tof, morgen verder

spoiler:

toevallig voor deel 1 de tail de head direct laten volgen? Dat had ik wel, maar die aanpak werkt niet helmaal lekker door voor deel 2 want daar pakt het touw de korste weg

[MueR]

Ik ga morgen wel een keer aan dag 9 beginnen. Vandaag na een kwartier een meeting en sindsdien hectiek, dus te afgestompt (eigenlijk net als gisteren)

[.oisyn]

Soultaker schreef op vrijdag 9 december 2022 @ 20:54:

spoiler:

Aangezien er negen knopen zijn (de kop niet meegeteld) die elk op negen verschillende posities kunnen liggen ten opzichte van hun voorgang is het totaal aantal states 9⁹ = 387,420,489. Als je voor elke state 20 bytes opslaat (4 × 4 bytes voor transities, plus ~1 byte voor de positie van de staart, rond af naar boven) kost die tabel een kleine 8 GB. Die kun je van te voren berekenen en dan in het geheugen mappen.

Ik durf de weddenschap wel aan dat dat helemaal niet sneller is. Een kleine tabel past in de L1 cache, bij zo'n enorme tabel ben je continu tegen cache misses aan het vechten. Dan beter 9 iteraties over iets wat in een handjevol cachelines past

Mijn eerste poging:

===[ input.txt ]==========
Time: 424us (load:33us, sim:194us, sort:196us)
2545

===[ aoc_2022_day09_large-1.txt ]==========
Time: 914.038us (load:37us, sim:257.906us, sort:656.093us)
14108518

===[ aoc_2022_day09_large-2.txt ]==========
Time: 9.803.152us (load:64us, sim:2.295.402us, sort:7.507.685us)
139740182

(dit zijn part2 tijden, part1 is maar marginaal sneller)

.edit: Dit is al een stuk rapper . Nog steeds singlethreaded, maar een andere datastructuur om bij te houden welke cells je al gehad hebt. Kost wel 2GB mem in die grootste file. En minder geschikt voor de normale puzzel input vanwege de extra overhead dus die wordt langzamer (de simtijd gaat omhoog, maar de sort is niet meer nodig, en bij die laatste ligt de bottleneck bij de grote inputs).

===[ input.txt ]==========
Time: 2.254us (load:42us, sim:2.211us, sort:0us)
2545

===[ aoc_2022_day09_large-1.txt ]==========
Time: 328.476us (load:38us, sim:328.437us, sort:0us)
14108518

===[ aoc_2022_day09_large-2.txt ]==========
Time: 3.189.763us (load:49us, sim:3.189.713us, sort:0us)
139740182

[ Voor 24% gewijzigd door .oisyn op 10-12-2022 04:43 ]

[MrHaas]

Dag 10 is niet m'n favoriete soort puzzel.

spoiler:

Weer slecht gelezen: register start op 1 .

Verder voor deel 2 de 240 cycle values precalculaten en dan pas er doorheen lopen om te renderen maakte het eitje.

[ Voor 35% gewijzigd door MrHaas op 10-12-2022 06:35 ]

[Varienaja]

Pwaah eerste dag dat ik de test-input niet gebruikt heb om er zeker van te zijn dat mijn programma enigszins foutvrij is. Spannend! Ik had wel even moeite te snappen

spoiler:

hoe die sprite precies werkt

.

Dag 10 in Java

[Dricus]

Dag 10 - Kotlin

Leuke puzzel weer! Ik heb er best lang over gedaan, omdat ik eerst een langdradige imperatieve oplossing probeerde te schrijven, waarmee het lastig was om...

spoiler:

... het verschil tussen "during a cycle" en "after a cycle" goed werkend te krijgen.

Toen ben ik maar opnieuw begonnen met een functional-style oplossing, en toen "klikte" het, en werd alles ineens veel makkelijker! De uiteindelijke oplossing is 20 regels code. Ik ben best tevreden .

[TrailBlazer]

het zal wel aan mijn zwaar verkouden hoofd liggen maar ik kan geen chocola maken van task2 vandaag

[MatHack]

Dag 10 in C#

Was ff zoeken, maar toen had ik eindelijk een oplossingsrichting waar ik mee kon leven (voornamelijk om dezelfde redenen die @Dricus ook aangeeft in zijn spoiler). Toen alleen nog in deel 2:

spoiler:

Stoeien met one-off errors, heerlijk dat cycle en position niet gelijk lopen...

En copy-paste van het antwoord van deel 2 ging niet echt, dus moest nog opletten wat ik invoerde ook (n.a.v. reacties gisteren)

[arnold_m]

Ik heb vandaag langer over deel 1 gedaan dan over deel 2.

spoiler:

Dat kwam vooral doordat het lang duurde voor ik in de gaten had dat de noop niet herkend werd doordat de '\n' ook in mijn gelezen regel stond.

[Remcoder]

MatHack schreef op zaterdag 10 december 2022 @ 08:34:
Dag 10 in C#

Was ff zoeken, maar toen had ik eindelijk een oplossingsrichting waar ik mee kon leven (voornamelijk om dezelfde redenen die @Dricus ook aangeeft in zijn spoiler). Toen alleen nog in deel 2:

spoiler:

Stoeien met one-off errors, heerlijk dat cycle en position niet gelijk lopen...

En copy-paste van het antwoord van deel 2 ging niet echt, dus moest nog opletten wat ik invoerde ook (n.a.v. reacties gisteren)

spoiler:

Hij gebruikt al sinds het begin dezelfde font om de characters te tekenen, dus ik heb inmiddels een Screen class gemaakt waar op getekend kan worden en die daarna kan zeggen wat er precies op staat.

Of als het bogus data is, zoals voorkomt bij de voorbeelden, kan die ook de output printen en kan ik die visueel verifieren in mijn test.

[Diderikdm]

Prima dag vandaag! Iets zegt me dat we dit soort puzzel vaker gaan zien dit jaar.

Dag 10 - Python

[Litpho]

Een hashmap met cycle/x-waardes (end of cycle) en een methode die daar een max waarde uit haalt (dus je vraagt om 20 en er is geen 20 dat hij 19 teruggeeft met de aanname dat dat dan halverwege een addx zat). Niet heel netjes en als part 2 een 3-cycle instructie had toegevoegd had het ook redesign nodig gehad, maar het levert de juiste antwoorden in een eindige tijd.

Dag 10 - Rust

spoiler:

Een Screenreader voor dit soort input is een goed idee en met volgende AoC's in gedachten geen slechte investering

[FrankMennink]

Dag 10 in Python

Code ziet er uit of t makkelijker kan (wat ook vast het geval is), maar dat is een zorg voor later.

[RangedNeedles]

TrailBlazer schreef op zaterdag 10 december 2022 @ 08:30:
het zal wel aan mijn zwaar verkouden hoofd liggen maar ik kan geen chocola maken van task2 vandaag

Ik heb geen verkoudheid en snap het deel van wanneer ik nu wel en niet een pixel moet blitten ook totaal niet

[BernardV]

RangedNeedles schreef op zaterdag 10 december 2022 @ 11:29:
[...]


Ik heb geen verkoudheid en snap het deel van wanneer ik nu wel en niet een pixel moet blitten ook totaal niet

spoiler:

Je print een pixel wanneer je cycle modulo 40 binnen een range van maximaal 1 van x ligt.
pseudo:
pixel = absolute(x - (cycle%40)) < 2 ? '#' : '.'

Dan dien je nog wel rekening te houden met de rij waar je de pixel print.

[Soultaker]

.oisyn schreef op zaterdag 10 december 2022 @ 03:26:
Ik durf de weddenschap wel aan dat dat helemaal niet sneller is. Een kleine tabel past in de L1 cache, bij zo'n enorme tabel ben je continu tegen cache misses aan het vechten. Dan beter 9 iteraties over iets wat in een handjevol cachelines past

Daar was ik al bang voor, vandaar dat ik er maar geen werk van gemaakt heb. Maar het hangt wel een beetje van je invoer af: het kan zijn dat je access niet volledig random is (b.v. als je meer dan 9 stappen in dezelfde richting doet, blijf je altijd in dezelfde toestand; dit kun je trouwens ook gebruiken om je reguliere algoritme te versnellen).

.edit: Dit is al een stuk rapper . Nog steeds singlethreaded, maar een andere datastructuur om bij te houden welke cells je al gehad hebt. Kost wel 2GB mem in die grootste file.

Nice Wat voor data structuur is dat/staat je code ergens? Doe je een soort van counting sort misschien? (Alle bezochte posities markeren met bits en dan aantal 1-bits tellen; vereist wel dat je de 2D array representeert om een manier dat je niet alle lege ruimte expliciet representeert).

[ Voor 8% gewijzigd door Soultaker op 10-12-2022 11:39 ]

[YoToP]

FrankMennink schreef op zaterdag 10 december 2022 @ 10:54:
Dag 10 in Python

Code ziet er uit of t makkelijker kan (wat ook vast het geval is), maar dat is een zorg voor later.

Het is voor mij wel goed leesbaar zo. Ik heb gelijk even mijn eigen code gerefactored met wat trucjes in jouw code. thnx

Oh voor de output van deel twee:

spoiler:

Ik heb gebruik gemaakt van chr(9608) = █. Is voor mij leesbaarder, ik zag het echt niet met al die #

[.oisyn]

Soultaker schreef op zaterdag 10 december 2022 @ 11:38:
[...]

Nice Wat voor data structuur is dat/staat je code ergens? Doe je een soort van counting sort misschien? (Alle bezochte posities markeren met bits en dan aantal 1-bits tellen; vereist wel dat je de 2D array representeert om een manier dat je niet alle lege ruimte expliciet representeert).

Sparse bitset . Code staat op mijn github. De bitset is 4 levels aan pages van 64k entries. Ik combineer een (x, y) coordinaat tot een enkele 64 bits index, waarbij ik de bytes van x en y interleave voor betere locality. Alles tussen (0,0) en (255,255) komt dus in dezelfde level 0 page terecht.

Er is nog wel wat ruimte voor optimalisaties, hoor. Veel low hanging fruit nog, zoals idd langere moves die geen state changes meer introduceren, een early out als een parent knot niet beweegt, een 4-entry cache voor level 0 pages zodat ik die niet elke keer hoef op te zoeken, en dan heb ik het nog niet eens gehad over parallellisatie.

Het is jammer dat de opdrachten zo snel op elkaar volgen, iedereen is alweer vertrokken naar een ander probleem

[ Voor 24% gewijzigd door .oisyn op 10-12-2022 12:03 ]

[_mike_]

Rust

spoiler:

een 2-cycle add kan je ook zien als een 1-cycle noop + een 1-cycle add

[tarlitz]

Oef, ik heb part 2 wel 10x gelezen voordat ik hem snapte, maar daarna was het een vrij simpele aanpassing aan part 1 om hem goed te krijgen. Er zit alleen nog een bugje in m'n display waarbij de 1ste kolom aan het eind staat

_mike_ schreef op zaterdag 10 december 2022 @ 12:06:
Rust

spoiler:

een 2-cycle add kan je ook zien als een 1-cycle noop + een 1-cycle add

Dit trucje wilde ik ook nog toepassen, ik denk dat het mijn implementatie wat makkelijker maakt!

Als ik morgen wat meer tijd heb maar even afmaken 😅

[Diderikdm]

tarlitz schreef op zaterdag 10 december 2022 @ 12:15:
Oef, ik heb part 2 wel 10x gelezen voordat ik hem snapte, maar daarna was het een vrij simpele aanpassing aan part 1 om hem goed te krijgen. Er zit alleen nog een bugje in m'n display waarbij de 1ste kolom aan het eind staat


[...]


Dit trucje wilde ik ook nog toepassen, ik denk dat het mijn implementatie wat makkelijker maakt!

Als ik morgen wat meer tijd heb maar even afmaken 😅

spoiler:

Is je eerste row 40 of 41 lang?

[Creepy]

Zo, dag 9 ook af. Even terug naar de tekentafel voor deel 2 omdat ik deel 1 iets te slim had willen oplossen. Ach ja.. En eroverheen lezen dat je sowieso diagonaal beweegt als het vorige stuk niet recht er naast ligt helpt ook niet mee.

https://github.com/CodeEn...er/aoc/aoc2022/Day09.java

Zo maar eens aan vandaag beginnen.

[ Voor 19% gewijzigd door Creepy op 10-12-2022 12:50 ]

[armageddon_2k1]

En.... Dag 10 in Kotlin.

Was weer prima te doen. Na een 5 of wat AOC's te doen heb je wel je handigheidjes. En de Kotlin Stdlib is zo lekker uitgebreid met collections.

[CMG]

Vandaag was leuk; op het eind nog even een

spoiler:

OCR engine geschreven zodat de code ook echt het antwoord kan geven

voor deel 2😊 linkje met screenshot/code | video

[ Voor 13% gewijzigd door CMG op 10-12-2022 13:09 ]

[eheijnen]

.oisyn schreef op zaterdag 10 december 2022 @ 11:57:
[...]
Het is jammer dat de opdrachten zo snel op elkaar volgen, iedereen is alweer vertrokken naar een ander probleem

Misschien interessant om na de AoC (door het jaar heen of zo) een of enkele opdrachten eruit te halen endaarmee aan de slag te gaan zoals jullie dat nu doen en die eens goed uitdiepen...

[Cranzai]

Dag 9 na een nachtje slapen ook kunnen oplossen,
Dag 10 ook gefixt

[Creepy]

En dag 10 hier ook weer gefixt. Die was weer erg eenvoudig.
https://github.com/CodeEn...er/aoc/aoc2022/Day10.java

[Soultaker]

.oisyn schreef op zaterdag 10 december 2022 @ 11:57:
Sparse bitset . Code staat op mijn github. De bitset is 4 levels aan pages van 64k entries.[/url]

Heel nice die bitset implementatie! Compileert zelfs nog op mijn CPU en is idd. erg snel: ongeveer 3,7s voor de large-2 (slechts ~15% trager dan op jouw CPU, interessant genoeg).

Ik zie dat je wel een transitie-tabel hebt geïmplementeerd maar dan voor maar 1 stap. In theorie zou je het ook kunnen doen voor 2 of meer stappen tegelijk, afhankelijk van hoeveel er in je cache past (b.v. 3 stappen is 26 KB, denk ik).

Ook interessant te zien dat je de lookup tables volledige at compiletime genereert; ik wist niet dat constexpr functies gewoon loops en variable assignments kunnen bevatten, blijkbaar loop ik nog een paar C++-versies achter.

edit:
Ik had voor de grap de early out geïmplementeerd. Dat leek voor de grote data set ~5% snelheidswinst op te leveren, maar voor de officiële wordt het juist trager. Dat is vreemd want mijn grote set bevat relatief veel minder stappen die de early-out gebruiken (~15% voor mijn data set, ~85% voor de officiële dataset) dus ik had verwacht dat het precies omgekeerd zou zijn.

Geen idee wat daar precies gebeurt; misschien hebben de extra conditionals een negatief effect op de gegenereerde code binnen de loop.

Het is jammer dat de opdrachten zo snel op elkaar volgen, iedereen is alweer vertrokken naar een ander probleem

Voor dag 10 hoef je daar niet bang voor te zijn, daar lijkt me vrij weinig interessants aan te optimaliseren (ik heb er dan ook geen grote set voor gepost).

[ Voor 20% gewijzigd door Soultaker op 10-12-2022 14:50 ]

[Marcj]

armageddon_2k1 schreef op zaterdag 10 december 2022 @ 12:49:
En.... Dag 10 in Kotlin.

Was weer prima te doen. Na een 5 of wat AOC's te doen heb je wel je handigheidjes. En de Kotlin Stdlib is zo lekker uitgebreid met collections.

Toch grappig hoe ik bijna op dezelfde code ben gekomen en toch de code er anders uit ziet. Net weer andere functies gekozen om het mee te doen: https://github.com/marcde...jonge/advent2022/Day10.kt

[MueR]

Dag 9 kan ik nog wel wat aan verbeteren.. Dag 10 was makkelijk.

[TrailBlazer]

Day 10 in Python
kan vast wel wat netter en efficienter alleen niet zo veel eer aan te behalen imho

[Daos]

TrailBlazer schreef op zaterdag 10 december 2022 @ 16:43:
kan vast wel wat netter en efficienter alleen niet zo veel eer aan te behalen imho

Het idee is dat je over meerdere dagen een processor-simulator bouwt. Over een paar dagen komen er wat instructies bij en een paar dagen daarna nog eens totdat je uiteindelijk een geavanceerde processor hebt met een stuk of 10 instructies compleet met branches/jumps. De eerste keer dat we zoiets moesten bouwen zat alles in 1 dag gepropt en dat was best veel werk. De laatste jaren is het over meerdere dagen uitgesmeerd.

[MueR]

MueR schreef op zaterdag 10 december 2022 @ 16:34:
Dag 9 kan ik nog wel wat aan verbeteren.. Dag 10 was makkelijk.

Zo dan, even de pecl package voor Data Structures installeren en dag 9 gaat van 1.8s rekentijd naar 25ms. Daar kan ik mee leven.

[TrailBlazer]

Ik moet wel zeggen dat het me dit jaar een stuk beter af gaat dan de vorige twee jaar. Mijn code ziet er een stuk netter uit so far.

[Remcoder]

Daos schreef op zaterdag 10 december 2022 @ 17:09:
[...]


Het idee is dat je over meerdere dagen een processor-simulator bouwt. Over een paar dagen komen er wat instructies bij en een paar dagen daarna nog eens totdat je uiteindelijk een geavanceerde processor hebt met een stuk of 10 instructies compleet met branches/jumps. De eerste keer dat we zoiets moesten bouwen zat alles in 1 dag gepropt en dat was best veel werk. De laatste jaren is het over meerdere dagen uitgesmeerd.

Dat was alleen het geval in 2019, toen moesten we de beruchte intcode computer bouwen.

Alle andere jaren kregen we over het algemeen maar 1 a 2 opdrachten met een instructieset om te implementeren.

Waarbij in de begin jaren de opdracht vooral was om het algoritme te analyseren en zelf efficiënter te schrijven wilde je klaar zijn voor de heat death van het universum.

[.oisyn]

Soultaker schreef op zaterdag 10 december 2022 @ 14:43:
Ik zie dat je wel een transitie-tabel hebt geïmplementeerd maar dan voor maar 1 stap. In theorie zou je het ook kunnen doen voor 2 of meer stappen tegelijk, afhankelijk van hoeveel er in je cache past (b.v. 3 stappen is 26 KB, denk ik).

Klopt ja, dat wil ik ook nog proberen. Maar zolang ik niet alle 9 tegelijk doe heb ik wel 9 (eigenlijk state transities. 3 Stappen tegelijk past al niet meer in een char, al zou ik ervoor kunnen kiezen om ofwel dx/dy ofwel moveDir er niet in te stoppen, want die zeggen eigenlijk hetzelfde. De berekening is by 4 bytes idd 4*9ⁿ⁺¹ met n het aantal gecombineerde statetransities.

Ook interessant te zien dat je de lookup tables volledige at compiletime genereert; ik wist niet dat constexpr functies gewoon loops en variable assignments kunnen bevatten, blijkbaar loop ik nog een paar C++-versies achter.

Ja heerlijk he . In C++23 is zelfs het grootste gedeelte van <math.h> ook constexpr. Vanaf C++20 kun je ook gewoon objecten alloceren "op de heap", zolang je ze maar weer delete. Dus je kunt ook gewoon iets als een std::vector gebruiken in een constexpr-gevalueerde context

Ik had voor de grap de early out geïmplementeerd. Dat leek voor de grote data set ~5% snelheidswinst op te leveren, maar voor de officiële wordt het juist trager. Dat is vreemd want mijn grote set bevat relatief veel minder stappen die de early-out gebruiken (~15% voor mijn data set, ~85% voor de officiële dataset) dus ik had verwacht dat het precies omgekeerd zou zijn.

Bij mij is die early out echt een enorme kostenpost. Hij gaat van 2,8s op de grootste dataset naar 4,2s . Ik
heb net eens naar het verschil in assembly zitten kijken, en zonder de early out wordt de loop volledig geunrolled en zit er geen enkele branch in. Met early out wordt het gewoon een daadwerkelijke loop. MSVC++ heeft geen force-unroll directive helaas, ben wel benieuwd hoe een unrolled loop met early out zou performen.

Ik zat weer eens door Intel intrinsics guide te bladeren en ik vond daar _pdep_u64 (PDEP). Prachtige instructie, daarmee kun je de bits van een getal uit elkaar trekken aan de hand van een control bit pattern (_pext_u64 (PEXT) doet precies het tegenovergestelde). Een pattern als 0b010101010101... insert allemaal 0 bits (bit 0 blijft op z'n plek, bit 1 gaat naar bit 2, bit 2 naar bit 4, bit 3 naar bit 6, etc). Daarmee kan ik het x- en y-coordinaat dus per bit interleaven ipv per byte, elke cacheline wordt daarmee effectief een blokje van 8x8 in mijn grid (ipv dat elke verandering in y een andere cacheline opleverde). Daarmee ging mijn running time van 3.0s naar 2.8s

.edit: 2.6s met 4-entry bitset page cache.

[Soultaker]

.oisyn schreef op zaterdag 10 december 2022 @ 22:16:
3 Stappen tegelijk past al niet meer in een char, al zou ik ervoor kunnen kiezen om ofwel dx/dy ofwel moveDir er niet in te stoppen, want die zeggen eigenlijk hetzelfde.

Ik had bedacht dat je de dx/dy in 1 byte kunt packen (b.v. met een bit field, 4 bits elk), dan kun je nog steeds vrij snel rap uitpakken en heb je twee bytes voor nextState. Merk op dat je nextState en moveDir élke iteratie nodig hebt en dx/dy alleen aan het eind van de lus, maximaal 1 keer dus, dus lijkt me dat je die als eerste inpakt.

Bij mij is die early out echt een enorme kostenpost. Hij gaat van 2,8s op de grootste dataset naar 4,2s . Ik
heb net eens naar het verschil in assembly zitten kijken, en zonder de early out wordt de loop volledig geunrolled en zit er geen enkele branch in. Met early out wordt het gewoon een daadwerkelijke loop. MSVC++ heeft geen force-unroll directive helaas, ben wel benieuwd hoe een unrolled loop met early out zou performen.

Dat is toch niet zo moeilijk te testen?

C++:

#define LOOP_BODY(k) \
    { \
        auto& state = knotStates[k]; \
        lastMove = States[state][d]; \
        state = lastMove.nextState; \
        d = lastMove.moveDir; \
        if (d == None) goto done; \
    }
LOOP_BODY(0)
LOOP_BODY(1)
LOOP_BODY(2)
LOOP_BODY(3)
LOOP_BODY(4)
LOOP_BODY(5)
LOOP_BODY(6)
LOOP_BODY(7)
LOOP_BODY(8)
#undef LOOP_BODY
    x += lastMove.dx;
    y += lastMove.dy;
    numCells += grid.Set(x, y);
done:

Waarschijnlijk kun jij wel een mooiere permanente oplossing verzinnen met template-metaprogramming als het de moeite waard blijkt te zijn.

Of kun je deze patch eens proberen? Met clang levert dat iets van 15% winst op!

[ Voor 4% gewijzigd door Soultaker op 10-12-2022 23:21 ]

[tarlitz]

Diderikdm schreef op zaterdag 10 december 2022 @ 12:29:
[...]

spoiler:

Is je eerste row 40 of 41 lang?

spoiler:

Nee, bedankt voor het meedenken. Ik had de cycle op 1 gestart, maar ik had de modulus daar niet goed op aangepast. Daarom kreeg ik '-1' als pixel ipv 39 aan het eind van elke rij waardoor alles verschoven leek.

[SPee]

Ik ben de afgelopen opdrachten wel veel bezig geweest met "off by one" problemen

Ik had verwacht hier sneller doorheen te zijn, maar het heeft me een volle dag gekost.
Maar gelukkig ben ik weer bij.

[.oisyn]

Soultaker schreef op zaterdag 10 december 2022 @ 22:55:
[...]

Ik had bedacht dat je de dx/dy in 1 byte kunt packen (b.v. met een bit field, 4 bits elk), dan kun je nog steeds vrij snel rap uitpakken en heb je twee bytes voor nextState. Merk op dat je nextState en moveDir élke iteratie nodig hebt en dx/dy alleen aan het eind van de lus, maximaal 1 keer dus, dus lijkt me dat je die als eerste inpakt.

Bitfields to the rescue. Dit heeft geen noemenswaardige impact op de performance.

C++:

struct Move
{
    uint nextState : 24;
    uint moveDir : 4;
    int dx : 2;
    int dy : 2;
};

Ruimte voor 16,7 miljoen states

En constexpr is awesome

C++:

template<int A, int B>
constexpr auto CombineStates(StateArray<A> a, StateArray<B> b)
{
    StateArray<A * B> result;

    for (int i = 0; i < A; i++)
    {
        for (int j = 0; j < B; j++)
        {
            for (int d = 0; d < 9; d++)
            {
                auto move = a[i][d];
                auto newa = move.nextState;
                auto newd = move.moveDir;

                move = b[j][newd];              
                auto newb = move.nextState;

                move.nextState = newa * B + newb;
                result[i * B + j][d] = move;
            }
        }
    }

    return result;
}

constexpr auto DoubleStates = CombineStates(States, States);
constexpr auto TripleStates = CombineStates(DoubleStates, States);

Of kun je deze patch eens proberen? Met clang levert dat iets van 15% winst op!

MSVC++ genereert daar dezelfde code als de "structurele" oplossing met de check in de for conditie. En dus geen loop unroll.

.edit: met 4xDoubleState+1xSingleState naar 1.8s.
met 3xTripleState naar 1.5s.
2xQuad+Single ook 1.5s. Niet zo gek, want dat zijn nog steeds 3 state transities. Compiletijden beginnen nu wel toe te nemen

Ok voor PentaStates moest ik het aantal constexpr eval steps verhogen anders slikte de compiler het niet .
1.4s wel . Maar 26s om de source te compilen

.edit: Met een iets handigere bitpacking (movestate 16 bits, movedir 8 bits) performt de 3x TripleState en handmatige unroll met early out trouwens ook met 1.4s. Dus ik denk dat ik het daar op hou.

[ Voor 20% gewijzigd door .oisyn op 11-12-2022 01:57 ]

[Gropah]

Part 1 van vandaag ging best steady, maar met deel 2 was ik te veel tijd kwijt.

Ik dacht dat het

spoiler:

een simpele one line change van delen door 3 naar module product van delers moest zijn. Ik had er geen rekening mee gehouden dat het dan alsnog zo kan zijn, dat het niet in een int past. Dus ik heel veel code nalopen en wijzigingen proberen. Om 3 kwartier later na een hint van iemand toch maar eens te checken op overflow issues. Toen was het in een minuut klaar.

Ik vond hem wel weer grappig. Ik ben eigenlijk vooral benieuwd of we morgen de CPU van gisteren terug gaan zien.

[Varienaja]

Ja het is weer zondag hoor!

OMG @ invoer
OMG @ expressies parsen

spoiler:

OMG @ long te klein
OMG @ BigInteger te traag

Dag 11 in Java https://github.com/varien...tofcode2022/Puzzle11.java.

[armageddon_2k1]

Tja, de moeilijkheid van AOC wordt toch vaak in het parsen gestopt.... moet even zin maken voor vandaag.

[Janoz]

armageddon_2k1 schreef op zondag 11 december 2022 @ 08:35:
Tja, de moeilijkheid van AOC wordt toch vaak in het parsen gestopt.... moet even zin maken voor vandaag.

tbh vond ik het parsen vandaag best simpel. Ja, het lijkt veel tekst, maar als je in alle input kijkt dan valt de variatie heel erg mee.

[armageddon_2k1]

Janoz schreef op zondag 11 december 2022 @ 08:39:
[...]

tbh vond ik het parsen vandaag best simpel. Ja, het lijkt veel tekst, maar als je in alle input kijkt dan valt de variatie heel erg mee.

Oh, ja dat is zeker waar :-)

[eheijnen]

Woendag gehaktdag....
Zondag Parsedag....

[MatHack]

Dag 11 in C#

spoiler:

Had gelukkig vrij snel door dat het probleem number overflows was, dus voor deel 1 alles omgezet naar long en dat werkte. Voor deel 2 eerst nog de BigInteger van C# geprobeerd, maar die is traaaaaag, zoals @Varienaja voor Java ook al opmerkte. Ik wist zeker dat ik een trucje miste, dus ff gespiekt in de oplossing van @jmerle (dank!), en toen kon ik mezelf wel voor mijn kop slaan... simpele wiskunde natuurlijk.

[armageddon_2k1]

Dag 11 in Kotlin

Ik zou willen dat ik er niet zo ingestonken was....

spoiler:

De test-values waren allemaal priem-getallen, dat zette me wel aan het denken...

[ Voor 22% gewijzigd door armageddon_2k1 op 11-12-2022 10:39 ]

[MrHaas]

Leuke puzzel, maar

spoiler:

zat nu te denken of je het kan oplossen voor een arbitrair aantal ronden: volgens mij kan je een item representeren als (monkey index, value % M) waar bij M de lcm is van de test values. Aangezien het aantal states eindig is (aantal monkeys * M), heeft elk item een bepaalde frequentie. Je moet dan alleen nog voor 1 cycle van een item bijhouden hoe vaak ie elke monkey bezoekt.

Klopt mijn redenering?

[Diderikdm]

Niet al te duidelijke code, 1.5s runtime, dus kan nog wel wat verbeteren. Wel een geinige puzzel. Deel twee deed me een beetje denken aan 2020 dag 13 waarna ik wel een hint had.

spoiler:

Chinese Remainder Theorem

Dag 11 - Python

[armageddon_2k1]

MrHaas schreef op zondag 11 december 2022 @ 10:50:
Leuke puzzel, maar

spoiler:

zat nu te denken of je het kan oplossen voor een arbitrair aantal ronden: volgens mij kan je een item representeren als (monkey index, value % M) waar bij M de lcm is van de test values. Aangezien het aantal states eindig is (aantal monkeys * M), heeft elk item een bepaalde frequentie. Je moet dan alleen nog voor 1 cycle van een item bijhouden hoe vaak ie elke monkey bezoekt.

Klopt mijn redenering?

Zou best kunnen. Probeer het eens uit te werken met een heel klein aantal testvalues en lage waardes ervan. Bv, 3,5,7. Dat is nog doable

[Cranzai]

Diderikdm schreef op zondag 11 december 2022 @ 11:28:
Niet al te duidelijke code, 1.5s runtime, dus kan nog wel wat verbeteren. Wel een geinige puzzel. Deel twee deed me een beetje denken aan 2020 dag 13 waarna ik wel een hint had.

spoiler:

Chinese Remainder Theorem

Dag 11 - Python

Zonder die hint was het me niet gelukt, thanks

[Marcj]

Day 11 - Kotlin

Ik had eerst een poging in BigIntegers, maar na een paar seconden runtime realiseerde ik me dat ik met een andere oplossing moest komen. Deze doet beide delen nu in 20ms, dus ben daar wel weer blij mee

[Creepy]

Dag 11 ook weer af. Dat was wel ff nadenken voor deel 2

spoiler:

Eerst lopen rommelen met de modulo van de deler van de huidige monkey, maar dat werkte logischerwijs niet. Daarna nog even gedacht aan de deler van de monkey waar het naar toe moet. Duurde even voordat ik op de oplossing uitkwam om alle delers maar met elkaar te vermenigvuldigen en zo maar 1 getal te hebben voor de modulo.

[MrHaas]

armageddon_2k1 schreef op zondag 11 december 2022 @ 11:29:
[...]


Zou best kunnen. Probeer het eens uit te werken met een heel klein aantal testvalues en lage waardes ervan. Bv, 3,5,7. Dat is nog doable

Yes, het is gelukt. Smerige code, maar het werkt. Kan nu binnen 100ms uitkomst bepalen voor elk willekeurig aantal rondes.

[Soultaker]

.oisyn schreef op zondag 11 december 2022 @ 01:20:
Met een iets handigere bitpacking (movestate 16 bits, movedir 8 bits)

Dit zei ik al hè

Waarschijnlijk is de optimale layout zoiets:

C:

struct {
  unsigned nextState : 16;
  int dr : 4;
  int dc : 4;
  unsigned nextDir : 8;
}

Zodat je nextState kunt berekenen met 1 AND instructie, nextDir met 1 SHIFT instructie, en de minst-gebruikte dr/dc met 1 SHIFT + 1 AND elk. Maar laten we wel zijn, het verschil is minimaal.

performt de 3x TripleState en handmatige unroll met early out trouwens ook met 1.4s. Dus ik denk dat ik het daar op hou.

Nice! Ik vind 3×3 ook het meest natuurlijke voor dit probleem.

Kun je de laatste versie eens naar Github pushen btw?

Varienaja schreef op zondag 11 december 2022 @ 08:12:

spoiler:

OMG @ long te klein
OMG @ BigInteger te traag

spoiler:

Ik had hetzelfde; 10,000 ronden × 36 items is toch niet zo veel? Waarom duurt de simulatie zo lang?

[ Voor 19% gewijzigd door Soultaker op 11-12-2022 14:24 . Reden: Mogelijke spoiler voor deel 2 getagd. ]

[Dricus]

Dag 11 - Kotlin

Pff, echt véél te lang vastgezeten op een totaal verkeerd spoor.

spoiler:

Ik had al meteen door dat er een overflow probleem was. Alleen ik kon er maar niet opkomen hoe je de tussenwaardes kon "modulo-en" om de overflow te voorkomen. En dat terwijl het niet de eerste keer is dat AoC een dergelijke puzzel heeft..

[Soultaker]

Diderikdm schreef op zondag 11 december 2022 @ 11:28:

spoiler:

Chinese Remainder Theorem

Volgens mij zeg jij dit elk jaar wanneer je

spoiler:

kleinste gemene veelvoud (least common multiple)

bedoelt. De twee zijn wel aan elkaar gerelateerd maar wat jij noemt is veel ingewikkelder en hier helemaal niet nodig.

[Dricus]

Soultaker schreef op zondag 11 december 2022 @ 14:09:
[...]

Volgens mij zeg jij dit elk jaar wanneer je

spoiler:

kleinste gemene veelvoud (least common multiple)

bedoelt. De twee zijn wel aan elkaar gerelateerd maar wat jij noemt is veel ingewikkelder en hier helemaal niet nodig.

spoiler:

En least common multiple is ook niet eens nodig, je kunt gewoon alle "divisible by" getallen met elkaar vermenigvuldigen. Alleen schaalt dat natuurlijk niet met het aantal apen en de hoogte van de "divisible by" getallen.

[Soultaker]

Dricus schreef op zondag 11 december 2022 @ 14:16:

spoiler:

En least common multiple is ook niet eens nodig, je kunt gewoon alle "divisible by" getallen met elkaar vermenigvuldigen. Alleen schaalt dat natuurlijk niet met het aantal apen en de hoogte van de "divisible by" getallen.

Je hebt gelijk en nu je het zegt valt het me pas op dat (in mijn invoer tenminste)

spoiler:

alle delers priemgetallen zijn, dus het product is gelijk aan het kleinste gemene veelvoud.

.

[Soultaker]

MrHaas schreef op zondag 11 december 2022 @ 13:18:
Yes, het is gelukt. Smerige code, maar het werkt. Kan nu binnen 100ms uitkomst bepalen voor elk willekeurig aantal rondes.

Grappig genoeg wordt deel 1 daarmee moeilijker dan deel 2.

[Diderikdm]

Soultaker schreef op zondag 11 december 2022 @ 14:09:
[...]

Volgens mij zeg jij dit elk jaar wanneer je

spoiler:

kleinste gemene veelvoud (least common multiple)

bedoelt. De twee zijn wel aan elkaar gerelateerd maar wat jij noemt is veel ingewikkelder en hier helemaal niet nodig.

Old habits die hard hoewel de hint voor mij wel was wat ik zei, heb ik het inderdaad niet op die manier opgelost, maar de quick and dirty-variant.

[Dricus]

Soultaker schreef op zondag 11 december 2022 @ 14:35:
[...]

Je hebt gelijk en nu je het zegt valt het me pas op dat (in mijn invoer tenminste)

spoiler:

alle delers priemgetallen zijn, dus het product is gelijk aan het kleinste gemene veelvoud.

.

spoiler:

Dat viel me bij mijn input ook op inderdaad. En toen begon ik te stoeien met ontbinden in priemfactoren van de worry levels, en liep ik helemaal vast

[_mike_]

Rust

runt deel1 en deel2 samen in 4.5 ms.

[MueR]

Dag 11 in PHP
Deel 2 is wat traag met ~130ms.

[gedonie]

Ik had gisteren even geen tijd, dus vandaag maar dag 10 en dag 11 in Java opgelost.

Moet zeggen dat dag 10 een makkelijke was, maar voor dag 11 was ik in dezelfde valkuil getrapt als een aantal andere in het forum.

spoiler:

Na een paar keer proberen met eerst longs en daarna BigInteger erachter komen dat BigInteger gewoon echt niet gaat werken toch maar een andere wiskundige oplossing gezocht.

[SPee]

Ik heb daarvoor ook een hulplijn nodig gehad
Ik zat verkeerd te denken

spoiler:

modulo 100 of ander 10-tal of bij true de division zelf

[tarlitz]

spoiler:

Leuke opdracht vandaag, goed te doen en tweede deel was toch weer een wmb klassieke aoc twist. Ik had in eerste instantie eval gebruikt voor de oplossing. Dit ging prima in ~6 seconden met Python, maar ik was toch verbaast over de vele reacties hier over oplossingen in een paar honderd ms. Toch maar even de `Operation` geparst. Nu loopt mijn oplossing ook lekker vlot (200 ms)! Had eigenlijk niet gedacht dat het zó veel zou schelen (factor 20), maar verbaast me eigenlijk ook niet.

[.oisyn]

Soultaker schreef op zondag 11 december 2022 @ 13:38:
Zodat je nextState kunt berekenen met 1 AND instructie, nextDir met 1 SHIFT instructie

Als ze word of byte aligned zijn dan kunnen ze gewoon worden geladen met een word of byte-sized read met zero extension, dus het maakt niet zo heel veel uit waar in de struct ze staan.

Kun je de laatste versie eens naar Github pushen btw?

Dacht dat ik al dat had gedaan. Nu alsnog

[Cranzai]

Nou vroeg ik mij af, het wiskundige trucje vandaag, is dat iets dat bij informatica opleidingen vaker voorbij komt of is het iets dat je toevallig moest weten?

Als scheikundige kende ik het in ieder geval niet

[TrailBlazer]

Cranzai schreef op zondag 11 december 2022 @ 17:50:
Nou vroeg ik mij af, het wiskundige trucje vandaag, is dat iets dat bij informatica opleidingen vaker voorbij komt of is het iets dat je toevallig moest weten?

Als scheikundige kende ik het in ieder geval niet

Dat vraag ik me ook af inderdaad. Heb wel HTS werktuigbouw gedaan (soort van) maar dit nooit bij wiskunde gehad.

[.oisyn]

Het is wel iets dat bij informaticaopleidingen naar voren komt omdat het belangrijk is in cryptografie.

[Soultaker]

...en hash functies, hash tables, caching, load balancing, sharding...

[ Voor 7% gewijzigd door Soultaker op 11-12-2022 18:48 ]

[Soultaker]

deleted

[ Voor 100% gewijzigd door Soultaker op 11-12-2022 19:35 ]

[Litpho]

Vandaag sowieso meerdere malen van mijn computer weggeweest, maar alsnog veel te lang lopen staren op de fout in deel 2.

Dag 11 - Rust

spoiler:

Uiteindelijk bleek ik de divisors van de echte input (als zelf berekende constante) te gebruiken tegen de testinput en dat gaat voor de eerste 20 ronden goed maar begint af te wijken bij ronde 1000. Met de interrupties er bij heb ik daar langer op gestaard dan me lief is.

[.oisyn]

Soultaker schreef op zondag 11 december 2022 @ 18:48:
...en hash functies, hash tables, caching, load balancing, sharding...

Priemgetallen ja, maar getaltheorie wat minder.

[Remcoder]

.oisyn schreef op zondag 11 december 2022 @ 18:35:
Het is wel iets dat bij informaticaopleidingen naar voren komt omdat het belangrijk is in cryptografie.

Dat is dan iets recents, 10-15 jaar geleden kwam dit nog niet voor op het HBO.

Op de universiteit was cryptografie een keuzevak, dus kon je ook de opleiding doorlopen zonder getal theorie.

[.oisyn]

Remcoder schreef op zondag 11 december 2022 @ 19:35:
[...]

Dat is dan iets recents, 10-15 jaar geleden kwam dit nog niet voor op het HBO.

Of misschien is niet elke HBO gelijk? .
* .oisyn is afgestudeerd in 2004. Hogeschool van Utrecht.

[Cranzai]

Ah kijk, is dus wel "programmeurs kennis".
Blijkt maar weer dat ik "scientist first, programmer second" ben (niet dat informatici geen wetenschappers zijn)

[Gropah]

Cranzai schreef op zondag 11 december 2022 @ 17:50:
Nou vroeg ik mij af, het wiskundige trucje vandaag, is dat iets dat bij informatica opleidingen vaker voorbij komt of is het iets dat je toevallig moest weten?

Als scheikundige kende ik het in ieder geval niet

Dit kwam op mijn universiteit in het eerste programmeervak aan bod. Dat vak word gevolgd door alle informatica en kunstmatige intelligentie studenten, plus een deel van wiskunde, econometrie, natuurkunde, scheikunde en sterrenkunde.

[Cranzai]

Gropah schreef op zondag 11 december 2022 @ 20:01:
[...]


Dit kwam op mijn universiteit in het eerste programmeervak aan bod. Dat vak word gevolgd door alle informatica en kunstmatige intelligentie studenten, plus een deel van wiskunde, econometrie, natuurkunde, scheikunde en sterrenkunde.

Oh kijk aan, mag ik vragen welke uni dat was?
(Zelf een alumnus van de RUG)

[MatHack]

Bij mij op het HBO is dat 20 jaar geleden lichtelijk behandeld, maar heb het de afgelopen 20 jaar niet echt gebruikt tijdens mijn werk, dus dan valt dat soort kennis ook deels weg. Ben nu bezig om met een master bezig te gaan, mogelijk komt het daar weer terug, haha.

[ Voor 19% gewijzigd door MatHack op 11-12-2022 20:05 ]

[Remcoder]

.oisyn schreef op zondag 11 december 2022 @ 19:36:
[...]

Of misschien is niet elke HBO gelijk? .
* .oisyn is afgestudeerd in 2004. Hogeschool van Utrecht.

Andersom geldt dat dan ook voor jouw statement

[.oisyn]

Remcoder schreef op zondag 11 december 2022 @ 20:10:
[...]

Andersom geldt dat dan ook voor jouw statement

Maar ik zei toch niet dat het bij élke opleiding naar voren kwam?

[P_Tingen]

Cranzai schreef op zondag 11 december 2022 @ 17:50:
Nou vroeg ik mij af, het wiskundige trucje vandaag, is dat iets dat bij informatica opleidingen vaker voorbij komt of is het iets dat je toevallig moest weten?

Als scheikundige kende ik het in ieder geval niet

Ik heb bedrijfskundige informatica gestudeerd maar ik kende het ook alleen van voorgaande AoC jaren. En bij AoC is het ook het enige waar ik het toepas 😁

(afgestudeerd in 1994...)

[ Voor 3% gewijzigd door P_Tingen op 11-12-2022 20:22 ]

[Gropah]

Cranzai schreef op zondag 11 december 2022 @ 20:02:
[...]


Oh kijk aan, mag ik vragen welke uni dat was?
(Zelf een alumnus van de RUG)

Diezelfde

For context; degene die dat vak geeft is nogal fan van wiskunde bij opdrachten. Krijg je getallen die je makkelijk kan controleren. Maar hij weet niet helemaal wat het niveau van de middelbare school is. En vind niet dat een klein beetje extra wiskunde een probleem moet zijn.

[Thorwing]

zelfs al kende je 'het trucje' niet, is het best logisch te redeneren. Het is alsof je gaat klagen dat je het Dijkstra algoritme niet kent bij een toekomstige opgave (wat zeker gaat komen). Dit bedoel ik niet lullig natuurlijk. Ik had er ook moeite mee vandaag aangezien ik het ook niet wist. Programmeer puzzles vragen nou eenmaal wat logisch inzicht waar we allemaal wat moeite mee hebben om 6 uur s'ochtends natuurlijk.

[farlane]

.oisyn schreef op zondag 11 december 2022 @ 01:20:
[...]

Soultaker schreef op zondag 11 december 2022 @ 13:38:
[...]

Ik zit te genieten van jullie discussies in jullie alternate reality trouwens. Ga zo door

C++ is hier een dying craft valt me op trouwens....

[ Voor 8% gewijzigd door farlane op 11-12-2022 20:49 ]

[Soultaker]

Okee, een extra uitdaging voor dag 11. Meer apen! Meer artikelen!

aoc_2022_day11_large-1.txt (12 KB), som van de cijfers van de antwoorden: 21, 72.

aoc_2022_day11_large-2.txt (135 KB), som van de cijfers van de antwoorden: 48, 60.

Hint: ik heb de inputs zo ontworpen dat je in principe géén big integer library nodig voor deze problemen (wel 64-bits integers), behalve misschien voor large-2 deel 1, afhankelijk van hoe je het aanpakt.

[tarlitz]

Thorwing schreef op zondag 11 december 2022 @ 20:39:
zelfs al kende je 'het trucje' niet, is het best logisch te redeneren. Het is alsof je gaat klagen dat je het Dijkstra algoritme niet kent bij een toekomstige opgave (wat zeker gaat komen). Dit bedoel ik niet lullig natuurlijk. Ik had er ook moeite mee vandaag aangezien ik het ook niet wist. Programmeer puzzles vragen nou eenmaal wat logisch inzicht waar we allemaal wat moeite mee hebben om 6 uur s'ochtends natuurlijk.

Ja, maar ik ken dijkstra ook helemaal niet. Net als @Cranzai heb ik een scheikunde achtergrond en is advent of code echt de eerste keer dat ik zulk soort algoritmes tegen kom. Laat staan dat ik dat voor een aoc puzzel ga implementeren. Dan gebruik ik een library. Anders worden dat soort opdrachten erg lastig.

Ik vind deze discussie daarom wel extra interessant, want ik sta echt versteld van wat ik allemaal zie qua oplossingen. En blijkbaar komt dit dus wél voorbij in de informatica opleidingen. Dit is goed om te weten voor mijn eigen zelfwaarde 😅

Dat trucje van vandaag zou ik zelf nooit opgekomen zijn als ik het niet vorig jaar ook al tegengekomen was. Dat vind ik ook het leuke van aoc. Zeker met opdrachten als deze leer ik veel van de oplossingen die voorbij komen.

[Thorwing]

tarlitz schreef op zondag 11 december 2022 @ 20:53:
[...]
Ja, maar ik ken dijkstra ook helemaal niet. Net als @Cranzai heb ik een scheikunde achtergrond en is advent of code echt de eerste keer dat ik zulk soort algoritmes tegen kom.

Dat trucje van vandaag zou ik zelf nooit opgekomen zijn als ik het niet vorig jaar ook al tegengekomen was. Dat vind ik ook het leuke van aoc.

Ik vind het altijd wel gaaf om andere opleidingen dit te zien doen, het was ook zeker geen sneer. Maar de leidraad van AoC is dat zonder programmeer of wiskundige achtergrond, je nog logisch kan redeneren hoe je er komt. Natuurlijk gaat dit vééél langer duren zonder voorkennis, dus ik blaam je helemaal niet als je googled. Kunnen googlen is het hele idee van een programmeur zijn dus je bent al een top programmeur als je dat kan haha.

In de latere dagen ga je redeneren en dingen doen en kom je erna achter dat dit eigenlijk "memoization" of "dijkstra" of wat dan ook is. Met voorkennis kun je dit altijd sneller aangezien er dan meteen een lampje gaat branden.

[Cranzai]

Gropah schreef op zondag 11 december 2022 @ 20:32:
[...]


Diezelfde

For context; degene die dat vak geeft is nogal fan van wiskunde bij opdrachten. Krijg je getallen die je makkelijk kan controleren. Maar hij weet niet helemaal wat het niveau van de middelbare school is. En vind niet dat een klein beetje extra wiskunde een probleem moet zijn.

Hmmm, dan ben ik dat vak niet tegengekomen, tenzij het een vak in C was? Kan ook zijn dat het de scheikundige technologen waren die dat vak volgden? Die hebben net een ander curriculum

Zelf in de richting theoretische chemie gegaan

[Cranzai]

Thorwing schreef op zondag 11 december 2022 @ 20:39:
zelfs al kende je 'het trucje' niet, is het best logisch te redeneren. Het is alsof je gaat klagen dat je het Dijkstra algoritme niet kent bij een toekomstige opgave (wat zeker gaat komen). Dit bedoel ik niet lullig natuurlijk. Ik had er ook moeite mee vandaag aangezien ik het ook niet wist. Programmeer puzzles vragen nou eenmaal wat logisch inzicht waar we allemaal wat moeite mee hebben om 6 uur s'ochtends natuurlijk.

Mwoah ja nee weet ik niet, Dijkstra kwam ik vorig jaar ook voor het eerst tegen idd. Toen liep ik ook helemaal vast qua redenaties totdat ik die hint kreeg.

Met deze heb ik nog geprobeerd met de test van de aap aan de slag te gaan maar dat werkte niet. Deze oplossing had ik zo 123 niet direct bedacht