:strip_exif()/u/13818/episodebutler_60x60.gif?f=community)
Ken Thompson's famous line from V6 UNIX is equaly applicable to this post:
'You are not expected to understand this'
"The question of whether a computer can think is no more interesting than the question of whether a submarine can swim" - Edsger Dijkstra
:strip_icc():strip_exif()/u/266124/crop63d63fdf5b8e2_cropped.jpg?f=community)
"The question of whether a computer can think is no more interesting than the question of whether a submarine can swim" - Edsger Dijkstra
:strip_icc():strip_exif()/u/623148/crop5e30857d56c67_cropped.jpeg?f=community)
Ik had vandaag dat mijn eerste idee voor part A de oplossing van part B was 
Heb volgensmij wel een O(n) oplossing te pakken. Maar de oplossing kan niet meer dan 256 negens in de input aan. Draait in ongeveer 0.5ms zonder recursie.
Rust
Heb volgensmij wel een O(n) oplossing te pakken. Maar de oplossing kan niet meer dan 256 negens in de input aan. Draait in ongeveer 0.5ms zonder recursie.
Rust
[ Voor 17% gewijzigd door HannoOttens op 10-12-2024 12:01 . Reden: Duidelijkere uitleg ]
Mooi of lelijk, het is voor mij perfect (en duidelijk) om eens in te verdiepen. Zou fijn zijn om voor eens en altijd af te zijn van de recursive fouten:
[...]
Even snel een paste voor je gemaakt: *klik voor Kotlin code*. Let wel; het is verre van mooi of geoptimaliseerd.
spoiler:InputReader bevat allerlei methods om data in te lezen. In dit geval een grid van chars en daar een map van een zelf gemaakt Point class naar een char. Die Point kent ook een fourNeighbors functie voor horizontale en verticale buren. Deque is een Double Edge que, gezien kotlin geen normale queue heeft. Denk dat de rest wel redelijk vanzelf sprekend isMocht dat toch niet zo zijn, laat het weten
(al is dat hoogstwaarschijnlijk wishful thinking)
:strip_icc():strip_exif()/u/53677/2009-07-01_avatar060x060.jpg?f=community){kind=avatar}
/u/243953/crop56f55a7bcf291.png?f=community)
Alles wat recursief is kan in een while-lus. En als je je while-lus goed opzet lijkt het heel erg op je recursieve code:
[...]
Mooi of lelijk, het is voor mij perfect (en duidelijk) om eens in te verdiepen. Zou fijn zijn om voor eens en altijd af te zijn van de recursive fouten
:strip_exif()/u/11775/SoulTaker.gif?f=community)
Dat waardeer ik enorm. Ik probeer wel eens andermans oplossing te runnen om de performance te vergelijken of een bug te vinden, en het kost belachelijk veel tijd om uit te vinden:
- Hoe ik de boel kan builden (Maven? Cargo? go? sbt‽)
- Hoe ik de oplossing kan runnen (waar staan de binaries? java -classpath ...? etc.)
- Hoe ik een ander invoerbestand kan specificeren.
Daarop voortbordurend, wat vind je hiervan? Geeft wat mij betreft de symmetrie tussen deel 1 en deel 2 mooier aan. (En is ook nog aanzienlijk sneller, al weet ik dat het je daar niet om te doen is.)Vandaag paste alles weer in 10 regels
Deze kun je prima parallel draaien met rayon. Op mijn M1 Pro gaat dit best vlot
code:
1
2
3
4
5
| Executing ├── Input parsed in 2,051µs ├── Part 1 calculated in 12,563µs: 152036 ├── Part 2 calculated in 9,792µs: 8621780 └── Total time: 24,431µs |
"The question of whether a computer can think is no more interesting than the question of whether a submarine can swim" - Edsger Dijkstra
Ken Thompson's famous line from V6 UNIX is equaly applicable to this post:
'You are not expected to understand this'
Ja dat is misschien een iets betere formulering en dat was dus vorig jaar in mijn beleving meer dan nu, maar ik begon vaak ook gewoon met de naïeve brute-force implementatie voor deel 1 en dan had je met deel 2 toch wel het meeste werk.
Ik doe AoC dan ook vooral om wat ervaring met een nieuwe taal op te doen, maar ook om m'n algoritmische kennis wat op te vijzelen, want in de praktijk doe ik daar gewoon te weinig mee.
"The question of whether a computer can think is no more interesting than the question of whether a submarine can swim" - Edsger Dijkstra
Dat had bij het probleem van vandaag ook best gekund. Bijvoorbeeld door wat nu deel 2 was als deel 1 te nemen (de meeste mensen leken het probleem zo toch al te interpreteren
) en dan bij deel 2 zeggen dat je twee cijfers moet nemen om de hoogte te bepalen (dus "123456" is 1,2,3,4,5,6 in deel 1, en 12, 34, 56 in deel 2). Om alle paden van 00 tot 99 te vinden moet je dan iets slims doen zoals @Robbinb1993 in z'n oplossing doet.Als je een algoritmische uitdaging zoekt kun je m'n variant voor dag 2 proberen op te lossen. De code is best simpel (~10 regels in Python) als je eenmaal het juiste inzicht hebt.
/u/1453990/crop67501f0e3996f_cropped.png?f=community)
Mooie uitdaging. Heb hem zojuist opgelost: https://github.com/Robbin...ain/day02/day2-variant.cc. Draait de test case in 49ms op mijn PC.:
[...]
Dat had bij het probleem van vandaag ook best gekund. Bijvoorbeeld door wat nu deel 2 was als deel 1 te nemen (de meeste mensen leken het probleem zo toch al te interpreteren
[...]
Als je een algoritmische uitdaging zoekt kun je m'n variant voor dag 2 proberen op te lossen. De code is best simpel (~10 regels in Python) als je eenmaal het juiste inzicht hebt.
/u/13471/karnemelk.png?f=community)
het zal wel heel stom zijn maar ik heb deel 1 opgelost met dijkstra. Alleen een recursive oplossing voor twee kom ik weer niet uit. Ik snap nooit hoe die werken 
Iemand een leesbaar recursive voorbeeld in Python?
Iemand een leesbaar recursive voorbeeld in Python?
:
het zal wel heel stom zijn maar ik heb deel 1 opgelost met dijkstra. Alleen een recursive oplossing voor twee kom ik weer niet uit. Ik snap nooit hoe die werken
spoiler:
Hoe ik het heb opgelost: Bereken per cell het aantal mogelijke paden vanaf die cell dat oplopend is met stappen van één en eindigt bij een 9. Bereken eerst alle paden vanaf 9, dan 8, dan 7, etcetera. Voor alle 9's is dit natuurlijk 1 (begint en eindigt daar). Voor elke 8 is dit het aantal directe orthogonale buren dat een 9 is. Voor 7 is het de som van het aantal mogelijke paden van de orthogonale buren die 8 zijn. Ga zo door tot en met 0. Dit wordt ook wel dynamisch programmeren genoemd, want we maken gebruik van resultaten van een subprobleem (het aantal paden beginnend met een hoger nummer in dit geval), om het grotere probleem op te lossen. Op deze manier kan je het ook iteratief oplossen, maar zelf heb ik het recursief gedaan (ook wel top-down DP genoemd), omdat ik dat juist makkelijker vind tegenwoordig. Iteratief is vaak wel iets sneller vanwege minder function calls. En recursief kan ook stack overflow problemen geven als je te diep gaat. Dit is O(N * M), omdat je alle cellen één keer moet doorlopen en per cel de 4 buren bekijkt.
In python ziet het er dan zo uit:
Python:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
| from functools import lru_cache grid = [ "89010123", "78121874", "87430965", "96549874", "45678903", "32019012", "01329801", "10456732" ] N, M = len(grid), len(grid[0]) DX = [-1, 1, 0, 0] DY = [0, 0, -1, 1] @lru_cache(None) def solve(x, y): if grid[x][y] == '9': # Base case return 1 total_paths = 0 for dx, dy in zip(DX, DY): # Check all 4 directions nx, ny = x + dx, y + dy if 0 <= nx < N and 0 <= ny < M and int(grid[nx][ny]) == int(grid[x][y]) + 1: total_paths += solve(nx, ny) return total_paths # Compute total paths for cells starting with '0' ans_part2 = sum(solve(i, j) for i in range(N) for j in range(M) if grid[i][j] == '0') print("Total paths starting with '0':", ans_part2) |
Het kan waarschijnlijk wel compacter in Python maar ik schrijf zelf weinig Python.
[ Voor 41% gewijzigd door Robbinb1993 op 10-12-2024 19:04 ]
U riep?
e=enumerate;H={i+j*1j:c for i,r in e(open(0))for j,c in e(r)};V=[(v,v)for v in H if H[v]=='0'];[V:=[(s,v+n)for s,v in V for n in(-1j,1j,-1,1)if H.get(v+n)==h]for h in '123456789'];print(len({*V}),len(V))
Verder verveelde ik me dus heb ik deel 2 van vandaag ook even geïmplementeerd m.b.v. SciPy's convolve2d(). Even een kleine vingeroefening voordat we weer Game of Life-achtige puzzels krijgen. Voor wie benieuwd is, de code is prima leesbaar en staat hier.
:strip_icc():strip_exif()/u/12461/crop65b195553d948.jpg?f=community)
Zoals gewoonlijk komt er bij mij weer een heel ander antwoord uit (bij deel 2)
.Wat krijgen jullie bij:
0123456789 1234567898 2345678987 3456789876 4567898765 5678987654 6789876543 7898765432 8987654321 9876543210
ik 20 en 1024.
.edit: oh jezus, ik deed offset = y * height + x, en de challenge input is niet vierkant
[ Voor 6% gewijzigd door .oisyn op 11-12-2024 01:15 ]
Give a man a game and he'll have fun for a day. Teach a man to make games and he'll never have fun again.
En daarom hergebruik in een Grid type. Dat soort fouten heb ik al veel te vaak gemaakt.:
[...]
.edit: oh jezus, ik deed offset = y * height + x, en de challenge input is niet vierkant
Ik was bang dat vandaag een moeilijke zou worden en dat deel 2 echt ondoenelijk groot zou worden en we in de wiskunde moesten duiken. Maar uiteindelijk valt het mee met een standaard puzzel techniek:
Vandaag voor het eerst op tijd op, dus ben gewoon nr 1589 voor deel 2 in de wereld
spoiler:
memoization
Vandaag voor het eerst op tijd op, dus ben gewoon nr 1589 voor deel 2 in de wereld
:
Ik was bang dat vandaag een moeilijke zou worden en dat deel 2 echt ondoenelijk groot zou worden en we in de wiskunde moesten duiken. Maar uiteindelijk valt het mee met een standaard puzzel techniek:
spoiler:memoization
Vandaag voor het eerst op tijd op, dus ben gewoon nr 1589 voor deel 2 in de wereld
spoiler:
Ik memorize/cache alleen de lage values en daarmee los ik part 2 in 2 ms op.
Same here, rank 2321 want ik was wat aan het klooien met Python:
Ik was bang dat vandaag een moeilijke zou worden en dat deel 2 echt ondoenelijk groot zou worden en we in de wiskunde moesten duiken. Maar uiteindelijk valt het mee met een standaard puzzel techniek:
spoiler:memoization
Vandaag voor het eerst op tijd op, dus ben gewoon nr 1589 voor deel 2 in de wereld
spoiler:
Ik heb geen memoization gebruikt, maar wel een dict ipv een list. De volgorde van de stenen boeit me niet, dus als ik 1000 0-en heb opgeslagen reken ik die maar 1 keer uit, maar wel voor elke stap opnieuw.
* Friits begon wat laat omdat de koffie op was. Nieuw pak te snel geopend, overal koffiepoeder...
Op deze manier haal @Soultaker en @Thorwing zeker niet in op het GoT leaderboard
Maar goed, gelukkig kon ik vandaag weer redelijk nette code schrijven en mijn "fans" op Reddit tevreden houden.
Op deze manier haal @Soultaker en @Thorwing zeker niet in op het GoT leaderboard
Maar goed, gelukkig kon ik vandaag weer redelijk nette code schrijven en mijn "fans" op Reddit tevreden houden.
Hmmm, vandaag ging niet soepel, terwijl dit probleem toch eerder is langsgekomen
Best wel zitten frotten om deel 1 correct te programmeren (ik kan blijkbaar niet zomaar een element van een vector pakken en die als variabele gebruiken, als dat element geen Clone implementeert in Rust
, zelfs niet als ik expliciet clone aanroep)
En natuurlijk moet je niet, als je eerst de lengte van een getal goed hebt berekend, delen door de lengte, maar splitsen op de (helft!) van de lengte
De kerstborrel van gisteren was niet bevorderlijk voor de denkkracht in de morgen zullen we maar zeggen.
Ah, gevonden: hier deed het me erg aan denken.
spoiler:
deel 1 echt brute force, deel 2 met een hashmap die bijhoud hoeveel er van elk getal op dit moment in de lijst staan. Alles u128, maar dat is volgens mij niet eens nodig.
Best wel zitten frotten om deel 1 correct te programmeren (ik kan blijkbaar niet zomaar een element van een vector pakken en die als variabele gebruiken, als dat element geen Clone implementeert in Rust
, zelfs niet als ik expliciet clone aanroep)En natuurlijk moet je niet, als je eerst de lengte van een getal goed hebt berekend, delen door de lengte, maar splitsen op de (helft!) van de lengte
De kerstborrel van gisteren was niet bevorderlijk voor de denkkracht in de morgen zullen we maar zeggen.
Ah, gevonden: hier deed het me erg aan denken.
[ Voor 7% gewijzigd door FCA op 11-12-2024 07:57 ]
Verandert z'n sig te weinig.
Mijn grid is read-only view op een slice, dus dat kon niet
[ Voor 3% gewijzigd door .oisyn op 11-12-2024 09:04 ]
Give a man a game and he'll have fun for a day. Teach a man to make games and he'll never have fun again.
Zucht. Er gaat iets mis in deel 2, maar ik weet niet wat. Heeft iemand zijn input en zijn antwoorden voor me zodat ik kan checken?
.edit: of, alternatief, wat is het antwoord van het voorbeeld van 125 17 voor 75 stappen?
.edit: argh jezus, ik zat het antwoord van het voorbeeld in te voeren ipv die van de daadwerkelijke puzzel input
.edit: of, alternatief, wat is het antwoord van het voorbeeld van 125 17 voor 75 stappen?
.edit: argh jezus, ik zat het antwoord van het voorbeeld in te voeren ipv die van de daadwerkelijke puzzel input
Wat bedoel je precies? Heb je een stukje code?:
Best wel zitten frotten om deel 1 correct te programmeren (ik kan blijkbaar niet zomaar een element van een vector pakken en die als variabele gebruiken, als dat element geen Clone implementeert in Rust
[ Voor 16% gewijzigd door .oisyn op 11-12-2024 11:55 ]
Give a man a game and he'll have fun for a day. Teach a man to make games and he'll never have fun again.
Dag 11 ook weer klaar, in eerste instantie had ik vanochtend een oplossing die enorm veel geheugen gebruikte 
Maar al vrij snel bedacht ik mij dat deze enorm veel lijkt op de oplossing van dag 6, 2021, dus de boel omgeschreven en nu is het zo veel sneller! +- 15 msec voor deel 1 en +- 20 msec voor deel 2 :-)
Maar al vrij snel bedacht ik mij dat deze enorm veel lijkt op de oplossing van dag 6, 2021, dus de boel omgeschreven en nu is het zo veel sneller! +- 15 msec voor deel 1 en +- 20 msec voor deel 2 :-)
Hier had ik ook last van; mijn proces zat op 180 GB memory usage voordat deze werd afgebroken en ik had toen nog geen antwoord... De tips hierboven hebben mij dus ook aardig geholpen:
Dag 11 ook weer klaar, in eerste instantie had ik vanochtend een oplossing die enorm veel geheugen gebruikte
Zag de bui al hangen vandaag, dus meteen maar een oplossing gemaakt die voor beide parts zou werken!
Draait in ongeveer 1ms
Rust
Draait in ongeveer 1ms
Rust
Ik was zeker niet slim genoeg om dit meteen door te hebben. En toen ik de lengte van de input zag had ik meteen al wel door dat er iets exploderends in zou zitten.
spoiler:
Maar het omschrijven van BFS naar DFS en resultaten cachen was redelijk triviaal. Ik was meer tijd kwijt aan het herschrijven van moeilijk eigen datastructuurtje die ik had opgezet omdat ik iets anders voor deel 2 verwachtte naar longs
Heh, jouw blink() is ongeveer exact dezelfde als mijn num_stones_from_number():
Zag de bui al hangen vandaag, dus meteen maar een oplossing gemaakt die voor beide parts zou werken!
Draait in ongeveer 1ms
Rust
Nog een microoptimization, als je `if let Some(v) = mem.get(...) doet kun je in 1 keer testen of het elemement aanwezig is en die ophalen. Nu zit je effectief 2x te hashen en de lookup te doen.
1ms vind ik wel apart, ik doe er 12ms over. En dan deel ik de hashmap van deel 1 ook nog eens met die van deel 2.
Give a man a game and he'll have fun for a day. Teach a man to make games and he'll never have fun again.
Goed idee!:
[...]
Heh, jouw blink() is ongeveer exact dezelfde als mijn num_stones_from_number()
Nog een microoptimization, als je `if let Some(v) = mem.get(...) doet kun je in 1 keer testen of het elemement aanwezig is en die ophalen. Nu zit je effectief 2x te hashen en de lookup te doen.
1ms vind ik wel apart, ik doe er 12ms over. En dan deel ik de hashmap van deel 1 ook nog eens met die van deel 2.
Ik zat trouwens eerst ook rond de 12ms, tot ik de types in mijn hashmap aanpaste naar van een u64 naar een u32
@HannoOttens Oh wow, maakt dat zoveel uit? Ik was bang dat het getal op een steen boven de u32 uit zou komen, maar blijkbaar dus niet
.edit: dat is in mijn geval ook zo. Bij jou niet?
Ik was bang dat het getal op een steen boven de u32 uit zou komen, maar blijkbaar dus niet .edit: dat is in mijn geval ook zo. Bij jou niet?
[ Voor 15% gewijzigd door .oisyn op 11-12-2024 15:40 ]
Give a man a game and he'll have fun for a day. Teach a man to make games and he'll never have fun again.
@.oisyn Heb ik blijkbaar geluk mee gehad! Heb mijn sterren in ieder geval binnen.
Ik had trouwens ook een langere duration toen ik een te grote ::with_capacity deed bij mijn hashmap. Mogelijk maakt dat ook nog verschil?
Heb mijn sterren in ieder geval binnen.Ik had trouwens ook een langere duration toen ik een te grote ::with_capacity deed bij mijn hashmap. Mogelijk maakt dat ook nog verschil?
[ Voor 45% gewijzigd door HannoOttens op 11-12-2024 15:45 ]
Give a man a game and he'll have fun for a day. Teach a man to make games and he'll never have fun again.
Damn. Als ik 'm laat beginnen met een capacity van 1 dan eindigt ie met een cap van 229.376 .
Als ik 'm meteen init met die cap dan kom ik op 11ms
.edit: cap blijft hetzelfde als ik part1 en part2 hun eigen map geef.
.Als ik 'm meteen init met die cap dan kom ik op 11ms
.edit: cap blijft hetzelfde als ik part1 en part2 hun eigen map geef.
[ Voor 51% gewijzigd door .oisyn op 11-12-2024 16:38 ]
Give a man a game and he'll have fun for a day. Teach a man to make games and he'll never have fun again.
Wauw.. ik heb nog heel even zitten twijfelen of ik mijn andere machine erbij zou pakken, die 64GB heeft. Die kon mijn oude oplossing van dag 6, 2021 wel oplossen na flink wat minuten en +- 50GB:
[...]
Hier had ik ook last van; mijn proces zat op 180 GB memory usage voordat deze werd afgebroken en ik had toen nog geen antwoord... De tips hierboven hebben mij dus ook aardig geholpen
Maar aan jou opmerking te zien, was dat niet de moeite waard geweest!
180GB? Dat is bijna valsspelen:
[...]
Hier had ik ook last van; mijn proces zat op 180 GB memory usage voordat deze werd afgebroken en ik had toen nog geen antwoord... De tips hierboven hebben mij dus ook aardig geholpen
. Ik werk op 8GB waarvan er ongeveer 3GB beschikbaar is voor python.
When life gives you lemons, start a battery factory
Draai jij je oplossingen op je telefoon of zo?:
[...]
180GB? Dat is bijna valsspelen
Ken Thompson's famous line from V6 UNIX is equaly applicable to this post:
'You are not expected to understand this'
Haha, dat zou wel sneller zijn waarschijnlijk. Ik heb een sony vaio uit 2012 die maar niet kapot wil gaan (hoewel ik wel last krijg van loslatende toetsen) . En ik heb nog een reserve vaio voor extra onderdelen, dus ik ga nog wel een paar jaar vooruit kunnen met mijn laptop. Ach, dan maar geen draaitijden in micro- of nanoseconden.:
[...]
Draai jij je oplossingen op je telefoon of zo?
When life gives you lemons, start a battery factory
Deel 1 vanochtend gedaan, maar zoals verwacht was deel 2 niet te brute forcen en ik had maar 10 min voor AoC vandaag ofzo.
Dus net maar even deel twee gedaan. Dacht eerst nog aan memoization, maar simpelweg de counts voor elke waarde bijhouden in plaats van elke individuele waarde was al voldoende om het snel te doen. Nog wel wat lopen kloten met ints en longs, maar dat hoort erbij.
Dus net maar even deel twee gedaan. Dacht eerst nog aan memoization, maar simpelweg de counts voor elke waarde bijhouden in plaats van elke individuele waarde was al voldoende om het snel te doen. Nog wel wat lopen kloten met ints en longs, maar dat hoort erbij.
"The question of whether a computer can think is no more interesting than the question of whether a submarine can swim" - Edsger Dijkstra
Ik zie nog wel ruimte voor betere implementaties.
input
spoiler:
Het ding met memoization is dat je alsnog heel veel werk dubbel doet. Als je voor een resultaat hebt voor een steen met waarde 6 met nog 10 stappen over, en je komt weer een 6 tegen maar dan met 11 stappen over, dan doe je dus al die 10 stappen opnieuw. Maar als je die 10 stappen wilt gebruiken om vervolgens 1 verder te gaan, dan moet je dus ook alle resultaten gaan opslaan, en gezien de grootte van het antwoord wordt dat ondoenlijk.
Ik heb misschien wel een idee waardoor het toch kan, maar dat moet ik nog even uitwerken.
Ik heb misschien wel een idee waardoor het toch kan, maar dat moet ik nog even uitwerken.
Blijkbaar maakt het ook nogal uit wat je puzzel input je hebt. @HannoOttens heeft aan 32 bits genoeg met zijn:
Nog wel wat lopen kloten met ints en longs, maar dat hoort erbij.
input
Give a man a game and he'll have fun for a day. Teach a man to make games and he'll never have fun again.
Ik kan het niet reproduceren nu (waarschijnlijk deed ik iets anders doms fout met m'n brakke hoofd van vanochtend. Het probleem leek in ieder geval dat:
Zucht. Er gaat iets mis in deel 2, maar ik weet niet wat. Heeft iemand zijn input en zijn antwoorden voor me zodat ik kan checken?
.edit: of, alternatief, wat is het antwoord van het voorbeeld van 125 17 voor 75 stappen?
.edit: argh jezus, ik zat het antwoord van het voorbeeld in te voeren ipv die van de daadwerkelijke puzzel input
[...]
Wat bedoel je precies? Heb je een stukje code?
code:
1
2
3
4
5
| fn main() {
let x = vec![vec![0], vec![1]];
let y = x[0];
println!("{:?}", y);
} |
niet werkt:
code:
1
2
3
| 3 | let y = x[0]; | ^^^^ move occurs because value has type `Vec<i32>`, which does not implement the `Copy` trait | |
maar de suggestie:
code:
1
2
3
4
5
| fn main() {
let x = vec![vec![0], vec![1]];
let y = x[0].clone();
println!("{:?}", y);
} |
ook vanochtend niet leek te werken, maar nu wel
Verandert z'n sig te weinig.
Ik had ook wel wat ideetjes maar niets dat praktisch tot betere performance leidde.
Bijvoorbeeld, lineaire algebra:
spoiler:
Je kunt het probleem modelleren als een sparse binaire transitie-matrix waarbij elke kolom maximaal twee enen bevat, en dan kun je k iteraties berekenen in O(n^3 log k) tijd of nog iets minder als je voor sparseness optimaliseert. Het probleem is alleen dat de matrix heel groot is en de exponent (k=75) relatief klein, dus dit is netto veel trager. Deze aanpak zou handig zijn als de set van getallen klein is en het aantal iteraties groot, maar bij dit probleem is het precies andersom.
Ook heb ik geprobeerd het te modelleren als graafprobleem:
spoiler:
Als je de getallen op stenen ziet als vertices, en de transities als edges, dan kun je in theorie iets doen als de graaf ontleden in strongly connected components, dan elke component afzonderlijk simuleren. Maar het probleem is dat de componenten van de graaf nog steeds erg groot zijn.
Bijvoorbeeld als je begint bij 100, dan krijg je een graaf met 1 component met 54 vertices waaronder 0 en 1, 1 component met 1709 vertices, en 2052 componenten met 1 vertex. Het probleem is dus dat het grootste component nog steeds vrij groot is, waardoor de decompositie weinig winst oplevert.
Bijvoorbeeld als je begint bij 100, dan krijg je een graaf met 1 component met 54 vertices waaronder 0 en 1, 1 component met 1709 vertices, en 2052 componenten met 1 vertex. Het probleem is dus dat het grootste component nog steeds vrij groot is, waardoor de decompositie weinig winst oplevert.
tl;dr: Geen van mijn ideeën leidt tot een aanpak die maar in de buurt komt van de andere opties.
Als je iets ontdekt dat significant sneller is dan de memoization-aanpak lijkt me dat zeer interessant!
Hm, dat is wel heel bijzonder! Volgens mij kom je met alleen “100” als invoer al een steen met 409.526.509.568 tegen, wat ruim buiten het bereik van een 32-bits integer is. Is de invoerdata echt zo zwak? Of gaat het toevallig goed? @HannoOttens kun je eens testen wat jouw oplossing doet met 100 als invoer? (Correct antwoord voor deel 2, dus met 75 iteraties, is 15669924873442.)Blijkbaar maakt het ook nogal uit wat je puzzel input je hebt. @HannoOttens heeft aan 32 bits genoeg met zijn input
Give a man a game and he'll have fun for a day. Teach a man to make games and he'll never have fun again.
Ja ik heb al een paar keer het vermoeden gehad dat ik een ongunstige input toebedeeld had gekregen. Het was bij mij zelfs zo dat ik een Long nodig had voor de counts van de individuele getallen, niet alleen voor het totaal:
Ik zie nog wel ruimte voor betere implementaties.
spoiler:Het ding met memoization is dat je alsnog heel veel werk dubbel doet. Als je voor een resultaat hebt voor een steen met waarde 6 met nog 10 stappen over, en je komt weer een 6 tegen maar dan met 11 stappen over, dan doe je dus al die 10 stappen opnieuw. Maar als je die 10 stappen wilt gebruiken om vervolgens 1 verder te gaan, dan moet je dus ook alle resultaten gaan opslaan, en gezien de grootte van het antwoord wordt dat ondoenlijk.
Ik heb misschien wel een idee waardoor het toch kan, maar dat moet ik nog even uitwerken.
[...]
Blijkbaar maakt het ook nogal uit wat je puzzel input je hebt. @HannoOttens heeft aan 32 bits genoeg met zijn
input
"The question of whether a computer can think is no more interesting than the question of whether a submarine can swim" - Edsger Dijkstra
Ja, dat was inderdaad duidelijk. Oplossing was om niet een vector terug te geven waar ik alleen in het eerste element geinteresseerd was, maar gewoon alleen het eerste element
Verandert z'n sig te weinig.
Ja daar heb ik het ook over
Give a man a game and he'll have fun for a day. Teach a man to make games and he'll never have fun again.
/u/36698/avatar.png?f=community){kind=avatar}
Kreeg ook flashbacks naar 2021, dag 6.
Als we het trouwens hebben over crappy specs... ik develop AoC in een VM met 2CPU/8GB RAM, en draai daarbij ook nog eens de debug versie (zonder debugger attached) van de applicatie.
https://github.com/realma...de.Y2024/Solvers/Day11.cs
Als we het trouwens hebben over crappy specs... ik develop AoC in een VM met 2CPU/8GB RAM, en draai daarbij ook nog eens de debug versie (zonder debugger attached) van de applicatie.
spoiler:
Ook hier gekozen voor tellers bijhouden + een cache van transformaties. Ik heb er uiteindelijk voor gekozen om de nummers als strings op te slaan ipv int/longs, dan hoef je alleen voor stap 3 te converten, de rest kan met strings. Nav de opmerkingen hier heb ik al wel meteen gekozen om de daadwerkelijke count van een nummer als een long bij te houden.
https://github.com/realma...de.Y2024/Solvers/Day11.cs
There's no place like 127.0.0.1
Dat kan veel simpeler
spoiler:
Denk voor deel 2 aan hoekpaaltjes waar het hek tussen moet en je kunt ineens heel simpel gaan patternmatchen
Ken Thompson's famous line from V6 UNIX is equaly applicable to this post:
'You are not expected to understand this'
Pittige vandaag inderdaad.
Niet de snelste oplossing, nog eens rustig nadenken of er snellere opties zijn.
Zelfde idee gebruikt, maar kostte even, zat flink te ruzieen met de borrow checker en ander geneuzel
spoiler:
Ik wilde graag mijn region als een hashset, en natuurlijk regions kunnen afstrepen, maar dat waren teveel mutable borrows vond de Rust compiler, dus uiteindelijk flink zitten clone-en
spoiler:
Ik ben voor een handgeschreven edge detector convolutie gegaan. Door elke region gaan en dan voor elk vierkantje checken welke buren er in zitten. Dan als de buur erboven en links er niet in zitten heb je een buitenbocht, en als de buur erboven en links ervan er wel in zitten maar linksboven niet heb je een binnenbocht. Dat x4 voor de rotaties (copy-paste + correct ( 
) aanpassen voor alle rotaties. Aantal bochten = aantal rechte stukken.
Eerst ook de binnenbochten vergeten, en daarna de buitenbocht check verkeerd gedaan.
) aanpassen voor alle rotaties. Aantal bochten = aantal rechte stukken.Eerst ook de binnenbochten vergeten, en daarna de buitenbocht check verkeerd gedaan.
Niet de snelste oplossing, nog eens rustig nadenken of er snellere opties zijn.
Verandert z'n sig te weinig.
Je hebt helemaal gelijk, dat is veel simpeler. Dat verklaart ook waarom anderen zo snel waren.:
Dat kan veel simpeler
spoiler:Denk voor deel 2 aan hoekpaaltjes waar het hek tussen moet en je kunt ineens heel simpel gaan patternmatchen
Met wat puin ruimen is m'n oplossing nog wel netjes geworden, vind ik zelf: 12.py
spoiler: deel 2
Je hoeft toch maar één keer door de hele grid te gaan om alle hoekpunten van alle regions te bepalen, of ben ik nu gek? B.v. als het vakje linksboven letter x heeft en rechtsboven en linksonder niet, dan is dit een convexe hoek; als het vakje linksboven letter x heeft en rechtsboven en linksonder ook, maar rechtsonder niet, dan is dit een concave hoek. In andere gevallen is het een recht stuk of de binnenkant van een regio.
Misschien mis ik wat edge cases hoor. Ik zal het even proberen te coden...
Misschien mis ik wat edge cases hoor. Ik zal het even proberen te coden...
Ken Thompson's famous line from V6 UNIX is equaly applicable to this post:
'You are not expected to understand this'
Memory mapped files, die pages kunnen dan gewoon uit de cache komen
.edit: ok fair, nog steeds O(N/pagesize) = O(N)
[ Voor 21% gewijzigd door .oisyn op 12-12-2024 10:55 ]
Give a man a game and he'll have fun for a day. Teach a man to make games and he'll never have fun again.
:strip_icc():strip_exif()/u/140697/crop6180fb9103afa_cropped.jpg?f=community)
Dag 11, deel 2.
Omdat ik hier al gelezen had welke richting het op moest voor deel 2 (had al door dat dat recht-toe, recht-aan niet zou gaan lukken) en ik net dag 7b (Bridge Repair) had opgelost, zag ik hier een kans.
Deel 1 had ik wel 'dom' opgelost en duurde 4,4 seconde. Met een tellertje erbij zag ik al dat elke iteratie langer duurde. Deel 2 - na wat optimalisatie - is nu klaar in 2940ms en dat is denk ik het snelste wat ik kan halen in Progress 4GL. Weer eens wat anders dan die snelle tijden
https://github.com/patric...ter/2024/Day-11/day-11b.p
Omdat ik hier al gelezen had welke richting het op moest voor deel 2 (had al door dat dat recht-toe, recht-aan niet zou gaan lukken) en ik net dag 7b (Bridge Repair) had opgelost, zag ik hier een kans.
Deel 1 had ik wel 'dom' opgelost en duurde 4,4 seconde. Met een tellertje erbij zag ik al dat elke iteratie langer duurde. Deel 2 - na wat optimalisatie - is nu klaar in 2940ms en dat is denk ik het snelste wat ik kan halen in Progress 4GL. Weer eens wat anders dan die snelle tijden
https://github.com/patric...ter/2024/Day-11/day-11b.p
... en gaat over tot de orde van de dag
Oeps.. Was nog replies van gisteren aan het lezen toen ik doodleuk de spoiler over de 
Dan hoop je maar dat je zelf tot het zelfde inzicht was gekomen
Rust
spoiler:
opende hoeken tellen oplossing
Dan hoop je maar dat je zelf tot het zelfde inzicht was gekomen spoiler:
Denk dat ik wel leuke pattern matching voor mekaar heb en een simpele manier van de vlakken bij elkaar zoeken (gewoon de buren in een queue zetten en geen positie twee keer afhandelen).
Rust
@Soultaker Nog even naar de u32 vs u64 gekeken en ik zat er inderdaad naast!
Na het inleveren niet goed opgelet en er kwam doodleuk een ander antwoord uit... Omdat ik voor de performance de release build deed ook niet langer over nagedacht dat overflows dan niet meer naar voren komen
Mijn oplossing draait dan in een beschamende 15ms in plaats van de eerder geprofeteerde snelheden
Na het inleveren niet goed opgelet en er kwam doodleuk een ander antwoord uit... Omdat ik voor de performance de release build deed ook niet langer over nagedacht dat overflows dan niet meer naar voren komen
Mijn oplossing draait dan in een beschamende 15ms in plaats van de eerder geprofeteerde snelheden
Extra testdata voor dag 12: aoc-2024-day-12-challenge-1-and-2.zip
Om te benchmarken kun je combined-1.txt en combined-2.txt gebruiken. Er zitten wat extra bestanden bij die je kunt gebruiken om te debuggen als je niet het goede antwoord krijgt (de combined bestanden zijn simpelweg de andere bestanden aan elkaar geplakt). Ik heb daarvoor ook de oplossingen in de zip file gestopt. Natuurlijk is de uitdaging om de correcte antwoorden zelf te reproduceren!
Referentie-tijden (dit kan zeker veel sneller in een andere taal dan Python):
Overigens overweeg ik ook een carrière switch naar abstract kunstenaar:
Mooi hè?
Om te benchmarken kun je combined-1.txt en combined-2.txt gebruiken. Er zitten wat extra bestanden bij die je kunt gebruiken om te debuggen als je niet het goede antwoord krijgt (de combined bestanden zijn simpelweg de andere bestanden aan elkaar geplakt). Ik heb daarvoor ook de oplossingen in de zip file gestopt. Natuurlijk is de uitdaging om de correcte antwoorden zelf te reproduceren!
Referentie-tijden (dit kan zeker veel sneller in een andere taal dan Python):
$ time pypy3 solve.py < combined-1.txt ...54044 ...18790 real 0m0.626s user 0m0.565s sys 0m0.058s $ time pypy3 solve.py < combined-2.txt ...62592 ...00666 real 0m4.497s user 0m4.231s sys 0m0.253s
Overigens overweeg ik ook een carrière switch naar abstract kunstenaar:
Mooi hè?
Ken Thompson's famous line from V6 UNIX is equaly applicable to this post:
'You are not expected to understand this'
:strip_icc():strip_exif()/u/633426/crop658152b10d6b4_cropped.jpg?f=community)
Paar daagjes griep gehad.. dus vanaf dag 7 niet meer bijgewerkt.. nu vrolijk verder met dag 12..
Die viel me aardig mee.
Qua snelheid vast niet vergelijkbaar met snellere loopjes.. maar qua code wel lekker kort
Die viel me aardig mee.
Qua snelheid vast niet vergelijkbaar met snellere loopjes.. maar qua code wel lekker kort
spoiler:
DEEL1:
:strip_exif()/f/image/eDOQrIEzdqZrGbdCfWIMIDrc.png?f=user_large)
- maak een netwerk van de matrix, en behoud alleen de verbindingen tussen gelijke letters.
- de componenten in de graaf zijn de verschillende blokken
- van iedere 'letter' is de omtrek gelijk aan (4 - aantal verbindingen naar naastgelegen letters)
- sommer dit per groep, en vermenigvuldig met groetsgrootte
DEEL 2
- maak een spatial grid van vierkanten, met afmetingen van input
- haal de groepen/blokken uit het antwoord van DEEL 1
:strip_exif()/f/image/GrZ1I0vQhH7GbWtpe1ALWZnl.png?f=user_large)
- simplificeer per blok, waardoor je alleen polylijnen (=omtrek) overhoudt.
:strip_exif()/f/image/6F34rfXsSNiFu2EIUS1jOdxA.png?f=user_large)
- per blok, per polylijn, kijk uit hoeveel punten de polylijn bestaat. (aantal punten - 1) is aantal lijndelen.
- sommeer per blok, en vermenigvuldig met blokgrootte
- maak een netwerk van de matrix, en behoud alleen de verbindingen tussen gelijke letters.
- de componenten in de graaf zijn de verschillende blokken
- van iedere 'letter' is de omtrek gelijk aan (4 - aantal verbindingen naar naastgelegen letters)
- sommer dit per groep, en vermenigvuldig met groetsgrootte
DEEL 2
- maak een spatial grid van vierkanten, met afmetingen van input
- haal de groepen/blokken uit het antwoord van DEEL 1
- simplificeer per blok, waardoor je alleen polylijnen (=omtrek) overhoudt.
- per blok, per polylijn, kijk uit hoeveel punten de polylijn bestaat. (aantal punten - 1) is aantal lijndelen.
- sommeer per blok, en vermenigvuldig met blokgrootte
[ Voor 3% gewijzigd door breew op 12-12-2024 16:25 ]
Nou, het goed visualiseren van dag 8 van vorig jaar had ook veel kunnen helpen
. Maar goed, vorig jaar niet heel serieus ingedoken omdat ik toen op vakantie ging.
Ken Thompson's famous line from V6 UNIX is equaly applicable to this post:
'You are not expected to understand this'