:strip_exif()/u/11775/SoulTaker.gif?f=community)
:strip_icc():strip_exif()/u/48567/viribox_60x60.jpg?f=community)
:strip_icc():strip_exif()/u/12461/crop65b195553d948.jpg?f=community)
===[ input.txt ]========== Time: 3,987us (load:88us, part1:3,648us, part2:250us) Part 1: 1820 Part 2: 2602 ===[ aoc_2022_day16_large-1.txt ]========== Time: 3,824,898us (load:74us, part1:3,755,070us, part2:69,753us) Part 1: 117949 Part 2: 125937 ===[ aoc_2022_day16_large-2.txt ]========== Time: 1,996,045us (load:134us, part1:1,937,136us, part2:58,775us) Part 1: 113928 Part 2: 130572 ===[ aoc_2022_day16_large-3.txt ]========== Time: 3,497,974us (load:92us, part1:3,433,461us, part2:64,420us) Part 1: 132860 Part 2: 140630 ===[ aoc_2022_day16_large-4.txt ]========== Time: 9,254,944us (load:126us, part1:9,171,140us, part2:83,677us) Part 1: 137838 Part 2: 141648 ===[ aoc_2022_day16_large-7.txt ]========== Time: 506us (load:151us, part1:329us, part2:26us) Part 1: 58361 Part 2: 52131
5 en 6 heb ik afgebroken, die finishte niet binnen 20s en vraten echt enorm veel mem. De snelheid van 7 verbaast me
..edit: heb 5 eens wat langer door laten lopen. 5 Geeft 202s+191s. 6 Runt nu.
.edit2: ik had geen zin om op 6 te wachten en het blokkeerde het linken van een nieuwe executable dus ik heb 'm gestopt. Ziekelijke algoritmische optimize voor part2 dit
. Eigenlijk exact hetzelfde trucje als ik in mijn 5-word oplossing heb gebruikt. Totale tijd van originele puzzel input nu onder de 4ms. Bovenstaande tijden zijn geupdatet (de oude part2 scores waren in de ordegrootte van secondes). Ik weet wel hoe ik part1 aan kan pakken maar weet even niet of ik daar tijd/zin in heb.
[ Voor 25% gewijzigd door .oisyn op 18-12-2022 03:31 ]
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/22283/crop5e2c64c410533.png?f=community)
: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'
Ik had 'm al :-):
Misschien even naar regel 131 kijken
Het ziet er bij jou veel netter uit, maar we doen exact hetzelfde
Siditamentis astuentis pactum.
Ken Thompson's famous line from V6 UNIX is equaly applicable to this post:
'You are not expected to understand this'
:strip_exif()/u/481248/crop59396aac2b552.gif?f=community)
/u/351643/bananatar_mini2.png?f=community)
Pff trage oplossing en zelfs daar veel te lang mee bezig geweest. Maar goed, straks even kijken naar andere oplossingen ter lering en vermaak. Ondertussen snel weer een animatie in elkaar geflanst van mijn input.
Honda CB750 Hornet :: Yamaha Fazer FZ6 SA (2011 - 2023) | F1Pool.net
Interessant om te zien hoe je algoritme wel en niet schaalt. Deel 7 heeft vooral veel valves mét positieve flow, wat voor sommige algoritmen problematisch kan zijn (b.v. als je expliciet alle permutaties probeert te enumereren), maar voor de jouwe blijkbaar geen probleem is. Nog steeds frappant dat het veel sneller is dan b.v. aoc_2022_day16_large-1.txt waarvan ik dacht dat het de makkelijkste zou zijn.:
5 en 6 heb ik afgebroken, die finishte niet binnen 20s en vraten echt enorm veel mem. De snelheid van 7 verbaast me
De conclusie is dus dat niemand aoc_2022_day16_large-5.txt en aoc_2022_day16_large-6.txt weet op te lossen?
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.
Ah sorry, dat had ik verkeerd begrepen aangezien je alleen de tijden voor deel 1 t/m 4 en 7 had gepost.
$ ./solve < ../testdata/16.in 2320 2967 Time: 396,267 us ./solve < ../extradata/aoc_2022_day16_large-1.txt ****49 ****37 Time: 403,909 us ./solve < ../extradata/aoc_2022_day16_large-2.txt ****28 ****72 Time: 421,515 us ./solve < ../extradata/aoc_2022_day16_large-3.txt ****60 ****30 Time: 402,578 us ./solve < ../extradata/aoc_2022_day16_large-4.txt ****38 ****48 Time: 401,840 us ./solve < ../extradata/aoc_2022_day16_large-5.txt ****52 ****98 Time: 4,202,541 us $ ./solve < ../extradata/aoc_2022_day16_large-6.txt ****83 ****85 Time: 44,005,616 us $ ./solve < ../extradata/aoc_2022_day16_large-7.txt ***61 ***31 Time: 17,647,197 us
De runtime hangt grotendeels af van het aantal bereikbare valves af. De complexiteit van mijn algoritme is O(V2 × 2V), worst case (met V het aantal bereikbare valves met flow_rate > 0), en doet praktisch niets om de average case sneller te maken. Dat zie je hier ook terug: ~400 ms voor alle inputs met 15 valves, 4 seconde voor die met 18 valves, en 44 seconde voor die met 21 valves.
(OK, technisch is er ook de Floyd-Warshall preprocessing die O(N3) tijd kost maar dat is niet waar de tijd 'm in zit bij deze invoer.)
[ Voor 3% gewijzigd door Soultaker op 18-12-2022 18:28 ]
:strip_icc():strip_exif()/u/341556/crop5dce11181361b.jpeg?f=community)
Haha, bastard
Ik wilde dat nog opschonen omdat ik dacht dubbel werk te doen. Ik wist helemaal niet dat er unidirectional tunnels inzaten. Het is dus meer gewoon luiheid van mijn kant dat ik dat goed doe
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.
Kleine optimize
===[ input.txt ]========== Time: 2,856us (load:82us, part1:2,521us, part2:253us) Part 1: 1802 Part 2: 2602 ===[ aoc_2022_day16_large-1.txt ]========== Time: 132,012us (load:72us, part1:65,534us, part2:66,405us) Part 1: 117949 Part 2: 125937 ===[ aoc_2022_day16_large-2.txt ]========== Time: 107,404us (load:140us, part1:52,616us, part2:54,647us) Part 1: 113928 Part 2: 130572 ===[ aoc_2022_day16_large-3.txt ]========== Time: 121,503us (load:97us, part1:60,312us, part2:61,093us) Part 1: 132244 // FOUT Part 2: 140630 ===[ aoc_2022_day16_large-4.txt ]========== Time: 121,857us (load:127us, part1:50,459us, part2:71,269us) Part 1: 137838 Part 2: 141648 ===[ aoc_2022_day16_large-5.txt ]========== Time: 3,998,695us (load:111us, part1:851,937us, part2:3,146,646us) Part 1: 148452 Part 2: 166998 ===[ aoc_2022_day16_large-6.txt ]========== Time: 25,574,942us (load:80us, part1:5,155,388us, part2:20,419,474us) Part 1: 167926 // FOUT Part 2: 194493 // FOUT ===[ aoc_2022_day16_large-7.txt ]========== Time: 591us (load:125us, part1:440us, part2:25us) Part 1: 58361 Part 2: 52131
Klopt alleen niet helemaal. Vreemd, dat betekent dat mijn pruning belangrijke paden afkapt terwijl dat helemaal niet zou moeten kunnen.
Hoe jij zo lang over large-7 doet is me een raadsel...
.edit: aaaah, denkfout.
Ik dacht, als je A->B->C->D vindt en die is "beter" dan A->C->B->D, dan hoef je die laatste nooit verder te expanden. Maar ik dacht iets te makkelijk over wat "beter" is, want er zijn twee criteria: pressure en tijd. In dit geval keek ik louter naar pressure, en prunede ik een stap die qua pressure lager was maar meer tijd overhield. Eens kijken of ik hier een enkele metric voor kan verzinnen die gegarandeerd klopt. Wat we natuurlijk sowieso kunnen stellen is dat als een permutatie slechter is in beide metrics, hij kan stoppen.
[ Voor 20% gewijzigd door .oisyn op 18-12-2022 23: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.
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.
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.
@Soultaker Ik zie het al. Het gevonden pad klopt, het getal wat ie print alleen niet . Het verschil tussen onze antwoorden is exact 4x de flowrate van AA. Ik doe tijdens part1 al voorwerk voor part2, maar omdat de tijd bij part2 4 seconden minder is moet ik de score aanpassen. Ik track de totale flowrate van de oplossing en vermenigvuldig dat met 4 en trek dat van de pressure af voor de score van part2.
Alleen AA met positieve flowrate is een special case queue entry, alleen daar vergeet ik de waarde van de totale flowrate in te vullen, dus die wordt er aan het eind ook niet afgetrokken, en eindig ik 4xAA te hoog. Heeft verder geen invloed op de timings.
. Het verschil tussen onze antwoorden is exact 4x de flowrate van AA. Ik doe tijdens part1 al voorwerk voor part2, maar omdat de tijd bij part2 4 seconden minder is moet ik de score aanpassen. Ik track de totale flowrate van de oplossing en vermenigvuldig dat met 4 en trek dat van de pressure af voor de score van part2.Alleen AA met positieve flowrate is een special case queue entry, alleen daar vergeet ik de waarde van de totale flowrate in te vullen, dus die wordt er aan het eind ook niet afgetrokken, en eindig ik 4xAA te hoog. Heeft verder geen invloed op de timings.
[ Voor 7% gewijzigd door .oisyn op 19-12-2022 00:17 ]
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.
Eindelijk heb ik ook dag 16 opgelost. Ik zat zaterdag helemaal vast, heb wel 2 uur zitten debuggen en testen en het resultaat klopte! Maar:
Deze oplossing lijkt volgens mij heel erg op die van .oisyn, maar bij mij runt hij in 320ms in Kotlin.
De grote bestanden gaan ongeveer zo:
- large-1: 862ms
- large-2: meer dan 64 items, wordt nog niet ondersteund
- large-3: 759ms
- large-4: 1710ms
- large-5: veeeeel te lang
- large-6: veeeeel te lang
- large-7: meer dan 64 items, wordt nog niet ondersteund
Heb duidelijk nog best wel wat werk te doen
spoiler:
Ik had eroverheen gelezen dat we bij AA moesten starten, ik startte bij de eerste in de lijst 
Deze oplossing lijkt volgens mij heel erg op die van .oisyn, maar bij mij runt hij in 320ms in Kotlin.
De grote bestanden gaan ongeveer zo:
- large-1: 862ms
- large-2: meer dan 64 items, wordt nog niet ondersteund
- large-3: 759ms
- large-4: 1710ms
- large-5: veeeeel te lang
- large-6: veeeeel te lang
- large-7: meer dan 64 items, wordt nog niet ondersteund
Heb duidelijk nog best wel wat werk te doen
[ Voor 25% gewijzigd door Marcj op 19-12-2022 11:00 ]
Ken Thompson's famous line from V6 UNIX is equaly applicable to this post:
'You are not expected to understand this'
Druk weekend gehad, vandaag wat tijd gehad om het e.e.a. op te poetsen.
Dag 17 - Python
Dag 18 - Python
Moet nog heel wat sleutelen aan vandaag, 16s op part1 en een uur ofzo op part2
Dag 19 - Python
Dag 17 - Python
Dag 18 - Python
Moet nog heel wat sleutelen aan vandaag, 16s op part1 en een uur ofzo op part2
Dag 19 - Python
Iedereen is bijna burned out denk ik en blij als ze weer een dag zijn doorgekomen
(als ik voor mezelf spreek iig)
/u/243953/crop56f55a7bcf291.png?f=community)
Waarschijnlijk heel erg kort door de bocht gevlogen maar runt nu beide delen in 3s:
Druk weekend gehad, vandaag wat tijd gehad om het e.e.a. op te poetsen.
Dag 17 - Python
Dag 18 - Python
Moet nog heel wat sleutelen aan vandaag, 16s op part1 en een uur ofzo op part2
Dag 19 - Python
spoiler:
makeshift berekening waarvan ik vrij zeker ben dat die te kort door de bocht is om vanaf end - 10 een evaluatie te maken of het hoogste aantal geodes nog te halen is (regel 14 - 17)
:strip_exif()/u/627282/charmander-kerst.gif?f=community)
De laatste dagen eindelijk wat tijd aan het vinden om een inhaalbeweging te starten. Zonet tot en met dag 12 opgelost in Rust:Volgende dagen heb ik wat vakantie, dan kan ik eens verder doen om mijn achterstand in te halen
Without nipples, boobs are pointless - 365 project - In mijn hoofd is het alle dagen Kerstmis - What type of bees make milk? Boobies! - What type of bees are scary? BoooOOOOOooobeees! - Cactusliefhebster
Hey @.oisyn ! Heb je toevallig wat meer uitleg over hoe jij het voor elkaar krijgt om zo snel combinaties van niet-overlappende paden kan vinden voor dag 16? Ik zit naar jouw code te kijken, maar ik zie niet in hoe dit zo snel gaat. Mijn huidige algoritme is O(n^2), maar ik weet misschien een O(n log(n)) manier (maar dit kost wat werk).:
@Soultaker Ik zie het al. Het gevonden pad klopt, het getal wat ie print alleen niet
Alleen AA met positieve flowrate is een special case queue entry, alleen daar vergeet ik de waarde van de totale flowrate in te vullen, dus die wordt er aan het eind ook niet afgetrokken, en eindig ik 4xAA te hoog. Heeft verder geen invloed op de timings.
Voor mij, in deel 2 is dit hetgeen wat veruit het langste duurt!
Het verkennen van alle paden heb ik wel een aantal leuke optimalisaties gevonden:
spoiler:
- Depth-first search bleek bij mij 2x sneller (en verkent 2x minder nodes) dan bread-first search
- Ik heb de heuristic (van maximaal mogelijke score) vervangen door het opslaan van de meest optimale tussen-paden. Dit bleek een factor 10 te schelen voor deel 1. Hier kwam ik per ongeluk doordat ik voor deel 2 de meest optimale tussenpaden wilde bewaren.
- Sorteren van uitgaande paden gebaseerd op de flowrate van die valve bleek ook nog behoorlijk te helpen.
- Ik heb de heuristic (van maximaal mogelijke score) vervangen door het opslaan van de meest optimale tussen-paden. Dit bleek een factor 10 te schelen voor deel 1. Hier kwam ik per ongeluk doordat ik voor deel 2 de meest optimale tussenpaden wilde bewaren.
- Sorteren van uitgaande paden gebaseerd op de flowrate van die valve bleek ook nog behoorlijk te helpen.
@Marj Er kloppen er wel meer niet
1a, 2a, 2b, 3a, 6a, 6b.
Het is een lookup op de onderste N ongebruikte bits. Bij mijn vorige oplossing N=1, nu N=2.
Part1 genereert een set van gebruikte valves en hun maximale score (met t<=26). Voor part2 moet je dan idd een paar zoeken zonder dat die dezelfde valves gebruiken (zo ver was jij natuurlijk ook).
Ik groepeer dan alle oplossingen op hun onderste gebruikte valve(s). Ik stel even dat N=1 voor het gemak van de uitleg. Oftewel, als je ze encodeerd als bits, dan groepeer je ze op de index van de kleinste bit die 1. De groepen kunnen niet overlappen: een oplossing uit de groep met bit-0 kan wellicht ook de valve op bit-1 gebruiken, maar die oplossing zit dan niet in de bit-1 groep want dan is bit-1 niet de kleinste gezette bit.
Al die groepen sorteer je op score, van hoog naar laag, zodat je een early out hebt. Hetzelfde doe je overigens bij de totale set.
Dan loop je over de totale set, voor elke oplossing bereken je het complement van de valves van de oplossing, en dan pak je per gezette bit de betreffende groepen van hierboven erbij. Die loop je ook allemaal af, maar je kunt stoppen als de score van de buitenste oplossing + de score van de gecomplementeerde oplossing kleiner is dan de huidige maximale score. Evenzo kun je in de buitenste loop ook stoppen als 2x de score van de buitenste oplossing kleiner is dan de maximale score (immers, om een betere score te halen zou betekenen dat er een binnenste oplossing is met een score groter dan de buitenste oplossing, maar die heb je dan al gehad als buitenste oplossing, dus dit scheelt de helft van het werk).
Voor grotere N maak je een betere voorselectie maar wordt je binnenste loop wel gecompliceerder. Waar je bij N=1 simpelweg over de bits loopt, moet je bij N=2 over alle paren van bits lopen, etc.
@Soultaker Die stomme bug die ik had bij 6b zorgt trouwens wel voor hoofdpijn. Als ik de bug fix dan prunet hij teveel mogelijkheden en krijg ik het goede antwoord er niet uit. Ik was er al bang voor dat mijn heuristiek om een pad af te kappen een beetje te kort door de bocht is.
1a, 2a, 2b, 3a, 6a, 6b
Ik heb 6b inmiddels in 4,5s
.Het is een lookup op de onderste N ongebruikte bits. Bij mijn vorige oplossing N=1, nu N=2.
Part1 genereert een set van gebruikte valves en hun maximale score (met t<=26). Voor part2 moet je dan idd een paar zoeken zonder dat die dezelfde valves gebruiken (zo ver was jij natuurlijk ook).
Ik groepeer dan alle oplossingen op hun onderste gebruikte valve(s). Ik stel even dat N=1 voor het gemak van de uitleg. Oftewel, als je ze encodeerd als bits, dan groepeer je ze op de index van de kleinste bit die 1. De groepen kunnen niet overlappen: een oplossing uit de groep met bit-0 kan wellicht ook de valve op bit-1 gebruiken, maar die oplossing zit dan niet in de bit-1 groep want dan is bit-1 niet de kleinste gezette bit.
Al die groepen sorteer je op score, van hoog naar laag, zodat je een early out hebt. Hetzelfde doe je overigens bij de totale set.
Dan loop je over de totale set, voor elke oplossing bereken je het complement van de valves van de oplossing, en dan pak je per gezette bit de betreffende groepen van hierboven erbij. Die loop je ook allemaal af, maar je kunt stoppen als de score van de buitenste oplossing + de score van de gecomplementeerde oplossing kleiner is dan de huidige maximale score. Evenzo kun je in de buitenste loop ook stoppen als 2x de score van de buitenste oplossing kleiner is dan de maximale score (immers, om een betere score te halen zou betekenen dat er een binnenste oplossing is met een score groter dan de buitenste oplossing, maar die heb je dan al gehad als buitenste oplossing, dus dit scheelt de helft van het werk).
Voor grotere N maak je een betere voorselectie maar wordt je binnenste loop wel gecompliceerder. Waar je bij N=1 simpelweg over de bits loopt, moet je bij N=2 over alle paren van bits lopen, etc.
@Soultaker Die stomme bug die ik had bij 6b zorgt trouwens wel voor hoofdpijn. Als ik de bug fix dan prunet hij teveel mogelijkheden en krijg ik het goede antwoord er niet uit. Ik was er al bang voor dat mijn heuristiek om een pad af te kappen een beetje te kort door de bocht is.
[ Voor 100% gewijzigd door .oisyn op 20-12-2022 14:42 ]
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.
large-2 is simpelweg een grotere versie van 1 (meer nodes), large-6 heeft asymmetrische paden (b.v. wel AA->BB maar niet BB->AA). Maar zoals .oisyn al opmerkte gaat het bij 1a al mis, dus ik zou daar beginnen.
Als je je code post kan ik je misschien een tip geven (maar ik beloof niets
)Wat mij betreft tellen alleen geldige optimalisaties, niet cut-offs die toevallig op de beschikbare invoer werken
Anders is natuurlijk het hek van de dam, dan kun je het optimale pad bij wijze van spreke wel hardcoden.
Duh:
Wat mij betreft tellen alleen geldige optimalisaties, niet cut-offs die toevallig op de beschikbare invoer werken
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.
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.
Heel erg bedankt voor deze input @.oisyn ! Ik heb het kunnen vinden. Het uiteindelijke probleem zat eigenlijk in het inlezen, waar een foutje in zat. Daardoor vielen er in een paar gevallen een enkele edge weg. En dit kwam niet voor in de kleinere sets. Helaas was dat ook een groot deel van de reden waarom het zo snel was 
Nou ja, wel weer een hoop geleerd in ieder geval. Voor degene die de code willen bekijken, Day16 is de oplossing, met hier de hulpfuncties voor BFS, DFS en combinaties maken.
Day 16 from day16.txt:
Part 1: 1923 in 0,027 seconds
Part 2: 2594 in 0,045 seconds
Full run in 0,111 seconds
Day 16 from day16_big-1.txt:
Part 1: 117949 in 0,230 seconds
Part 2: 125937 in 0,357 seconds
Full run in 0,631 seconds
Day 16 from day16_big-2.txt:
Part 1: 113928 in 0,267 seconds
Part 2: 130572 in 0,348 seconds
Full run in 0,678 seconds
Day 16 from day16_big-3.txt:
Part 1: 132860 in 0,166 seconds
Part 2: 140630 in 0,294 seconds
Full run in 0,507 seconds
Day 16 from day16_big-4.txt:
Part 1: 137838 in 0,403 seconds
Part 2: 141648 in 0,443 seconds
Full run in 0,894 seconds
Day 16 from day16_big-5.txt:
Part 1: 148452 in 5,716 seconds
Part 2: 166998 in 7,024 seconds
Full run in 12,787 seconds
Day 16 from day16_big-6.txt:
Part 1: 158683 in 6,397 seconds
Part 2: 181585 in 63,713 seconds
Full run in 70,157 seconds
Day 16 from day16_big-7.txt:
Part 1: 58361 in 0,004 seconds
Part 2: 52131 in 0,003 seconds
Full run in 0,097 seconds
Nou ja, wel weer een hoop geleerd in ieder geval. Voor degene die de code willen bekijken, Day16 is de oplossing, met hier de hulpfuncties voor BFS, DFS en combinaties maken.
poeh, mijn simpele oplossing (linked list + array) doet al 17 sec over de eerste. de 2e heb ik na 5 min maar gestopt
code:
1
2
3
4
| $ go run main.go Part 1: ...037 Part 2: ...357 Time: 17.88357825s |
spoiler:
De pragmatische oplossingsrichting is om ook next100, next1000, next10000, next100000, prev100, etc. toe te voegen aan de nodes van de LL. Dan is het 1x iets meer werk met parsen, daarna veel sneller heen en weer springen.
Leuke opdracht vandaag, aapjes kijken is altijd leuk 
.
.spoiler:
Deel twee heb ik numeriek opgelast; ik merkte dat de ene aap altijd hetzelfde antwoord terug gaf en dat de andere aap voor een delta +1 ok circa hetzelfde verschil aan antwoord terug gaf (in mijn geval circa +2,83... per verhoging van 1). Een loop geschreven die het verschil / delta bij mijn initiële antwoord gooit om een nieuwe guess te doen. Werkte vrij goed voor mijn input; oplossing gevonden binnen 3 iteraties, maar geen idee of het ook voor andere input werkt. Code in python.
:strip_icc():strip_exif()/u/106692/icon.jpg?f=community){kind=icon}
:
Leuke opdracht vandaag, aapjes kijken is altijd leuk
spoiler:Deel twee heb ik numeriek opgelast; ik merkte dat de ene aap altijd hetzelfde antwoord terug gaf en dat de andere aap voor een delta +1 ok circa hetzelfde verschil aan antwoord terug gaf (in mijn geval circa +2,83... per verhoging van 1). Een loop geschreven die het verschil / delta bij mijn initiële antwoord gooit om een nieuwe guess te doen. Werkte vrij goed voor mijn input; oplossing gevonden binnen 3 iteraties, maar geen idee of het ook voor andere input werkt. Code in python.
spoiler:
Je kunt het antwoord ook volledig recursief beredeneren, je weet steeds van 1 branch wat het antwoord is, vervolgens kun je de omgekeerde operatie uitvoeren en voor de andere branch weer niveau dieper kijken. Zo heb ik het in ieder geval opgelost (< 1 s in python).
Python code dag 21 deel 1 en 2
:strip_icc():strip_exif()/u/9434/b17_2.jpg?f=community)
En nu ik dan toch in de draad ben aangehaakt, wil ik graag nog mijn oplossing voor dag 19 delen.
Ik gebruik een genetisch algoritme om de oplossing te vinden. Nadat ik eerst zelf bedacht had hoe zo'n algoritme zou moeten werken, tot een oplossing gekomen, maar dat kostte wel een x aantal pogingen.
Daarna ingelezen hoe zo'n genetisch algoritme echt zou moeten werken en daar m'n code mee verbeterd. Nu vindt ie sneller (en vaker
) het juiste antwoord:
https://topaz.github.io/p...BkKO0LQ7IlIuv7br/+ARlnA==
Ik gebruik een genetisch algoritme om de oplossing te vinden. Nadat ik eerst zelf bedacht had hoe zo'n algoritme zou moeten werken, tot een oplossing gekomen, maar dat kostte wel een x aantal pogingen.
Daarna ingelezen hoe zo'n genetisch algoritme echt zou moeten werken en daar m'n code mee verbeterd. Nu vindt ie sneller (en vaker
) het juiste antwoord:https://topaz.github.io/p...BkKO0LQ7IlIuv7br/+ARlnA==
Less = more
Uuugh, al de zoveelste dag waarbij part 2 niet werkt met de echte input
Oké, gevonden! Oef... rust in het hoofd opnieuw Blijkbaar moest ik dus...
spoiler:
Mijn idee was soortgelijk aan dat van @RefleXion. Ik zoek eerst een pad van 'root' naar 'humn'. Daarna begin ik opnieuw bij root, en kijk ik welke branch ik kan/moet aanpassen, namelijk die waarin 'humn' zit.
Aangezien beide branches dezelfde waarde moeten geven, reken je dan uit wat de branch, waarin 'humn' zit, eigenlijk zou moeten teruggeven. Ga een niveautje lager en rinse en repeat.
Maar door die delingen kom ik soms een kommagetal uit. Ik had verwacht dat alles altijd netjes deelbaar zou zijn
En als ik hier dan naar sommige mensen hun (Python-)oplossingen kijk, zie ik ook dat jullie int division doen (door die // operator). Waar staat er gespecifieerd dat dit mag? Of wat mis ik nu net?
Aangezien beide branches dezelfde waarde moeten geven, reken je dan uit wat de branch, waarin 'humn' zit, eigenlijk zou moeten teruggeven. Ga een niveautje lager en rinse en repeat.
Maar door die delingen kom ik soms een kommagetal uit. Ik had verwacht dat alles altijd netjes deelbaar zou zijn
En als ik hier dan naar sommige mensen hun (Python-)oplossingen kijk, zie ik ook dat jullie int division doen (door die // operator). Waar staat er gespecifieerd dat dit mag? Of wat mis ik nu net?Oké, gevonden! Oef... rust in het hoofd opnieuw
Blijkbaar moest ik dus...spoiler:
... in het geval dat de tweede branch de 'humn'-branch is, de volgorde van m'n termen omdraaien. Best 'n domme fout wel.
[ Voor 12% gewijzigd door RangedNeedles op 21-12-2022 12:29 ]
Je hebt gelijk!:
Uuugh, al de zoveelste dag waarbij part 2 niet werkt met de echte input
spoiler:Mijn idee was soortgelijk aan dat van @RefleXion. Ik zoek eerst een pad van 'root' naar 'humn'. Daarna begin ik opnieuw bij root, en kijk ik welke branch ik kan/moet aanpassen, namelijk die waarin 'humn' zit.
Aangezien beide branches dezelfde waarde moeten geven, reken je dan uit wat de branch, waarin 'humn' zit, eigenlijk zou moeten teruggeven. Ga een niveautje lager en rinse en repeat.
Maar door die delingen kom ik soms een kommagetal uit. Ik had verwacht dat alles altijd netjes deelbaar zou zijn
spoiler:
Had bij de division monkeys gekeken naar de uitkomst, welke altijd x.0 was voor mijn input en daarom een int() eromheen gegooid, of intdiv. In theorie kan het inderdaad wel dat er kommagetallen voorkomen.. Ik heb mn code aangepast, thanks
Dag 21 was een leuk concept. Zelfde aanpak als de anderen hierboven; volgens mij is er ook niet veel anders mogelijk. Niet super moeilijk maar wel de meeste code die ik heb moeten schrijven door het implementeren van alle operators etc.
:
spoiler:Maar door die delingen kom ik soms een kommagetal uit. Ik had verwacht dat alles altijd netjes deelbaar zou zijn
spoiler:
Ik zou er nooit vanuit gaan dat het mag. Ik probeer eventuele aannamen altijd te checken in de code. Bijvoorbeeld in plaats van direct te delen kun je dit doen:
assert a % b == 0
return a // b
Het voordeel daarvan is dat als je aanname niet klopt, je een duidelijk foutmelding krijgt, in plaats van dat je domweg het verkeerde antwoord krijgt.
Als er niet-geheeltallige delingen zouden voorkomen dan zou je in Python vrij makkelijk kunnen overschakelen op Fractions, maar daar zou ik in eerste instantie niet vanuit gaan; het is vrij waarschijnlijk dat de invoer zo geconstrueerd is dat het op te lossen is met alleen gehele getallen, en dat was hier dus ook het geval.
assert a % b == 0
return a // b
Het voordeel daarvan is dat als je aanname niet klopt, je een duidelijk foutmelding krijgt, in plaats van dat je domweg het verkeerde antwoord krijgt.
Als er niet-geheeltallige delingen zouden voorkomen dan zou je in Python vrij makkelijk kunnen overschakelen op Fractions, maar daar zou ik in eerste instantie niet vanuit gaan; het is vrij waarschijnlijk dat de invoer zo geconstrueerd is dat het op te lossen is met alleen gehele getallen, en dat was hier dus ook het geval.
[ Voor 3% gewijzigd door Soultaker op 21-12-2022 14:27 ]
:strip_exif()/u/402713/crop61a8df0bd950d_cropped.gif?f=community)
Inderdaad, gewoon met // geprobeerd en het werkte, niet verder over nagedacht. Als je in mijn code de // door / vervangt werkt hij ook voor floats.:
En als ik hier dan naar sommige mensen hun (Python-)oplossingen kijk, zie ik ook dat jullie int division doen (door die // operator). Waar staat er gespecifieerd dat dit mag?
Ken Thompson's famous line from V6 UNIX is equaly applicable to this post:
'You are not expected to understand this'
/u/162933/arch_gnu.png?f=community)
Wat een slachtveld vandaag. Temeer daar de layout van het voorbeeld anders is dan de echte input. Ik heb hier een bos if-elsen waar je eng van wordt. (niks generiek geïmplementeerd, gewoon een vouwsel gemaakt en nageprogrammeerd.)
:strip_exif()/f/image/oKqeAohUElt3EkOmwf96MXQd.jpg?f=fotoalbum_large)
:no_upscale():strip_icc():fill(white):strip_exif()/f/image/oKqeAohUElt3EkOmwf96MXQd.jpg?f=user_large)
Siditamentis astuentis pactum.
spoiler:
Ik hard-code voor de voorbeeld kubus en mijn input kubus een "cubeInfo" struct met daarin de size van de kubus en voor elke kant de (x, y) van de top-left corner (in de input) + de 4 edges (per edge de target face + direction).
Daarmee kun je de 'echte' code generiek implementeren. Ik vond part 2 wel de minst leuke puzzel dit jaar omdat het veel handmatig uitzoeken vereist - het is vast mogelijk om te automatiseren, maar dat wordt me te tijdrovend...
edit: nu ik er over nadenk.. het is misschien niet eens zo moeilijk om de input te transformeren naar mijn representatie, misschien als ik vanavond tijd heb
[ Voor 13% gewijzigd door user109731 op 22-12-2022 13:11 ]
Was een leuke dag Wel veel gepriegel..
Dag 22 - Python
Wel veel gepriegel..spoiler:
Wil als ik nog tijd over hou ergens deze maand een 3d grid aan 2d coords koppelen (en vice versa). Dan zou in theorie elke variant van een uitgevouwde kubus moeten werken /denk/ ik.
Voor nu semi-hardcoded variant op basis van de vorm van de kubus uit mijn input (zie code) -> wel schaalbaar op formaat (nu 50 per kant).
Voor nu semi-hardcoded variant op basis van de vorm van de kubus uit mijn input (zie code) -> wel schaalbaar op formaat (nu 50 per kant).
Dag 22 - Python
Fijn om te zien dat ik niet de enige ben die met papier en schaar aan de slag is gegaan!
Erg lastig debuggen. Heeft even geduurd voordat ik door had dat ik mijn lokale coördinaten moest corrigeren naar totale uitgevouwen kaart.
Heb hem inmiddels af:
Dag 22 - deel 2 (Python)
spoiler:
Ik ben veel te lang bezig geweest om erachter te komen dat mijn edge detection ook rekening moest houden met de richting waarin ik aan het lopen was.
Ik kwam met mijn input blijkbaar op een hoekpunt uit waarbij ik daarna een verkeerde edge terug gaf, en daarna ging uiteraard de rest compleet de mist ging.
Nadat ik een paar stukken code van anderen vergeleken had en tijdens verschillende debug sessies niet duidelijk zag waar het nu precies mis ging viel het kwartje dat rekening houden met de richting nodig is voor de juiste edge te bepalen in een hoek.
Ik kwam met mijn input blijkbaar op een hoekpunt uit waarbij ik daarna een verkeerde edge terug gaf, en daarna ging uiteraard de rest compleet de mist ging.
Nadat ik een paar stukken code van anderen vergeleken had en tijdens verschillende debug sessies niet duidelijk zag waar het nu precies mis ging viel het kwartje dat rekening houden met de richting nodig is voor de juiste edge te bepalen in een hoek.
Held, ik snapte maar niet waarom mijn code niet het juiste antwoord gaf. Straks maar even implementeren.:
[...]
Fijn om te zien dat ik niet de enige ben die met papier en schaar aan de slag is gegaan!
Erg lastig debuggen. Heeft even geduurd voordat ik door had dat ik mijn lokale coördinaten moest corrigeren naar totale uitgevouwen kaart.
Heb hem inmiddels af:
Dag 22 - deel 2 (Python)
Dit staat nog op mn lijstje
Ken Thompson's famous line from V6 UNIX is equaly applicable to this post:
'You are not expected to understand this'
Ken Thompson's famous line from V6 UNIX is equaly applicable to this post:
'You are not expected to understand this'
Dag 23 kan je ook zo oplossen:
Nu even mentaal voorbereiden op morgen
spoiler:
Alleen de elfjes tracken in een set van coordinaten.
Werkt vaak gemakkelijker dan een lijst van lijsten of np array bijhouden met padding enzo.
Nog niet opgeschoonde code Denk dat ik vooral wat meer op het goed benoemen van m'n variabelen moet gaan letten
Werkt vaak gemakkelijker dan een lijst van lijsten of np array bijhouden met padding enzo.
Nog niet opgeschoonde code Denk dat ik vooral wat meer op het goed benoemen van m'n variabelen moet gaan letten
Nu even mentaal voorbereiden op morgen
:
[...]
Ik denk dat de meeste mensen het juist op die manier hebben opgelost
spoiler:
Zoiets heb ik dus ook gedaan, en dan gecombineerd met mijn Grid.
De lijst van elfjes gebruik ik om het volgende gewenste coördinaat te bepalen, op basis van de huidige beschikbaarheid op de Grid. Daardoor hoef ik niet voor elk elfje aan alle andere elfjes te vragen of die plek beschikbaar is, maar vraag ik dat aan mijn Grid die onderwater een HashMap gebruikt.
Per coördinaat houd ik dan een telling bij van hoeveel elfjes daarheen willen gaan. Weer gebaseerd op een HashMap.
In de move fase kijkt elk elfje dan of die de enige is die naar dat coördinaat wil en gaat erheen.
De lijst van elfjes gebruik ik om het volgende gewenste coördinaat te bepalen, op basis van de huidige beschikbaarheid op de Grid. Daardoor hoef ik niet voor elk elfje aan alle andere elfjes te vragen of die plek beschikbaar is, maar vraag ik dat aan mijn Grid die onderwater een HashMap gebruikt.
Per coördinaat houd ik dan een telling bij van hoeveel elfjes daarheen willen gaan. Weer gebaseerd op een HashMap.
In de move fase kijkt elk elfje dan of die de enige is die naar dat coördinaat wil en gaat erheen.
:strip_icc():strip_exif()/u/593726/crop5dcaa04cb6842_cropped.jpeg?f=community)
Ik vond vandaag toch best een lastige, maar vooral begrijpend lezen dan. Ik heb 4 verschillende implementaties van "Finally, at the end of the round, the first direction the Elves considered is moved to the end of the list of directions." geimplementeerd.
spoiler:
Eerst genegeerd 
, daarna per elf gekeken of ze uberhaupt probeerden te bewegen en dan de move-check order updaten, daarna per elf of ze daadwerkelijk bewogen en dan de move-check updaten, en daarna pas gerealiseerd dat ik te moeilijk dacht en dus de move-check order voor alle elven altijd hetzelfde was, maar per stap verschilde.
Ondertussen zat ik 4 dicts/hashmaps de hele tijd te updaten, wat de foutloosheid ook niet ten goede kwa
, daarna per elf gekeken of ze uberhaupt probeerden te bewegen en dan de move-check order updaten, daarna per elf of ze daadwerkelijk bewogen en dan de move-check updaten, en daarna pas gerealiseerd dat ik te moeilijk dacht en dus de move-check order voor alle elven altijd hetzelfde was, maar per stap verschilde.Ondertussen zat ik 4 dicts/hashmaps de hele tijd te updaten, wat de foutloosheid ook niet ten goede kwa
Verandert z'n sig te weinig.
:strip_icc():strip_exif()/u/633426/crop658152b10d6b4_cropped.jpg?f=community)
