Advent of Code 2021

[Hydra]

Sjezus die was lastig. Hele tijd vastgezeten op deel 2 omdat ik bezig wat met een generieke oplossing ipv. het gewoon uit te schrijven. Zal vast mogelijk zijn, maar ik heb hier nu wel ff genoeg tijd ingestoken!

Dag 8 in Kotlin

[Cranzai]

Poeh was me een bevalling, ging eerst de verkeerde kant op doordat ik de instructies verkeerd gelezen had (meende dat je over alle lines een soort generieke map kon maken, bleek dus dat elke line een display was....).

https://github.com/Cranza.../2021/day8/python/day8.py
Code is verre van modulair en behoeft een goede cleanup, ware het niet dat ik daar geen tijd voor over heb.

spoiler:

Net zoals velen hier heb ik ook gebruik gemaakt van de overlap van de onbekende cijfers met de bekende, met alleen een kleine twist.

Overlap met	1	4	7	8 (=len(signal))	som
0	2	3	3	6	14
2	1	2	2	5	10
3	2	3	3	5	13
5	1	3	2	5	11
6	1	3	2	6	12
9	2	4	3	6	15

Het eerste wat ik doe is dus een dictionary "digitMap" aanmaken met daarin de characters van 1, 4, 7, 8. Vervolgens hoef ik alleen maar een enkel getal te bepalen waarmee ik elk missende getal kan identificeren.

[FrankMennink]

Begonnen met deze versie
Eerste versie Dag 8 in Python

Na wat iteraties en de gedachte dat deel 1 best in 1 regel kan is het dit geworden.

Dag 8 in Python

spoiler:

Nummers 1, 4, 7, 8 zijn makkelijk. Daarna geprobeerd to ontcijferen welke letter op welke plek staat (key).
Daarvoor is het een voor een identificeren welk streepje welke letter is, ondertussen kan je alvast wat nummers identificeren. Uiteindelijk hield ik met mijn proces 6, 3 en 5 over, daar de key overheen gelegd en ik had mn set van welk nummer welke letters bevat. Vervolgens is het een simpele kwestie van de output checken adhv de set van nummers.

Oplossing is waarschijnlijk erg omslachtig, maar laat m.i. wel netjes alle deductie stappen zien

[ Voor 5% gewijzigd door FrankMennink op 08-12-2021 14:51 ]

[P_Tingen]

DevWouter schreef op woensdag 8 december 2021 @ 12:09:
(dag 9)

spoiler:

Maar ik had ook niet in de gaten dat de input alle mogelijke waardes bevatten in een willekeurige volgorde. Dus ik was bezig om elke segment te bepalen ook in de situatie wanneer een bepaalde numeriek representatie afwezig was.

Deze vond ik inderdaad ook pittig. Ik had wel een hint nodig om de goede oplossingsrichting in te slaan, eerlijk is eerlijk, maar toen was het nog lastig.

spoiler:

Ik had ook eerst niet door dat de woorden bij de output anders geschreven konden zijn dan bij de input. Maar ik had al een OVERLAP functie gemaakt die voor mij bepaalde of de segmenten van element A overlapten met die van element B. Door de functie 2x aan te roepen kan ik bepalen of 2 cijfers gelijk zijn. De segmenten van de 0 overlappen nml wel met de 8, maar andersom niet.

Dag 8b in Progress 4GL:
https://github.com/patric...ter/2021/Day-08/day-08b.p

[TrailBlazer]

spoiler:

Wat een draak van een opdracht
1 4 7 8 zijn makkelijk

9 bepaald door 4 over alles met 6 segmenten ( 0 6 en 9) te xor’en degen die 2 segmenten overhoudt is de 9
3 bepaald met 1 door te xor’en met alles met 5 segmenten.

Enzovoort

Misschien zijn de regels generiek te maken weet niet of ik daar de moed voor heb.

[Devilfish]

Ik zat te denken aan allerlei mooie bitmasks... Dus ik kwam met mijn C# kennis uit flags en dat hielp gelukkig ook met de schrijfwijzes die soms anders waren wat betreft volgorde.

spoiler:

https://github.com/antonr...puzzles/2021/8/Program.cs

[Gilotto]

Zo, ik ben er ook uit.

Leuke opdracht!

Members only:

Alleen zichtbaar voor ingelogde gebruikers. Inloggen

spoiler:

Ik heb het gewoon uitgeschreven

// 0 = abcefg -> length = 6
// 1 = cf -> length = 2
// 2 = acdeg -> length = 5
// 3 = acdfg -> length = 5
// 4 = bcdf -> length = 4
// 5 = abdfg -> length = 5
// 6 = abdefg -> length = 6
// 7 = acf -> length = 3
// 8 = abcdefg -> length = 7
// 9 = abcdfg -> length = 6

// occurance in number
// a = 0; 2; 3; 5; 6; 7; 8; 9 -> 8x
// b = 0; 4; 5; 6; 8; 9 -> 6x
// c = 0; 1; 2; 3; 4; 7; 8; 9 -> 8x
// d = 2; 3; 4; 5; 6; 8; 9 -> 7x
// e = 0; 2; 6; 8 -> 4x
// f = 0; 1; 3; 4; 5; 6; 7; 8; 9-> 9x
// g = 0; 2; 3; 5; 6; 8; 9 -> 7x

// a = 7 - 1
// b,e,f = numberOfTimes = 6, numberOfTimes = 4,numberOfTimes = 9
// c = 1 - f
// d = 4 - bcf
// g = (numberOfTimes = 7) - d

[ Voor 4% gewijzigd door Gilotto op 08-12-2021 15:48 ]

[DataGhost]

TrailBlazer schreef op woensdag 8 december 2021 @ 15:40:

spoiler:

Wat een draak van een opdracht
1 4 7 8 zijn makkelijk

9 bepaald door 4 over alles met 6 segmenten ( 0 6 en 9) te xor’en degen die 2 segmenten overhoudt is de 9
3 bepaald met 1 door te xor’en met alles met 5 segmenten.

Enzovoort

Misschien zijn de regels generiek te maken weet niet of ik daar de moed voor heb.

spoiler:

Waarom xor?

spoiler:

Waarom niet and/or?

[TrailBlazer]

DataGhost schreef op woensdag 8 december 2021 @ 15:52:
[...]

spoiler:

Waarom xor?

spoiler:

Waarom niet and/or?

spoiler:

Omdat het werkt ik moet nu nog even gaan nadenken wat er beter/logischer kan.

[ThomasG]

spoiler:

Aangezien deel 1 ging om lengtes, vroeg ik mij af of deel 2 ook met lengtes te doen zou zijn. Dus heb ik een matrix tabel gemaakt, met de lengte, en de hoeveelheid overlap met de 1, 4, 7 en 8 (want die zijn uniek, en altijd te vinden in het linker stuk). Ik zag al snel dat ik met de 1 en 4 genoeg unieke combinaties kreeg, dus heb ik de overlap met de 7 en 8 achterwegen gelaten.

Lengte	Overlap met 1	Overlap met 4	Cijfer
2			1
3			7
4			4
5	1	2	2
5	2	3	3
5	1	3	5
6	2	3	0
6	1	3	6
6	2	4	9
7			8

Dat vervolgens in rust in een match statement (tuple van lengte, overlap met 1, overlap met 4) gestopt, en voila.

[Cranzai]

Cranzai schreef op woensdag 8 december 2021 @ 14:40:
Poeh was me een bevalling, ging eerst de verkeerde kant op doordat ik de instructies verkeerd gelezen had (meende dat je over alle lines een soort generieke map kon maken, bleek dus dat elke line een display was....).

https://github.com/Cranza.../2021/day8/python/day8.py
Code is verre van modulair en behoeft een goede cleanup, ware het niet dat ik daar geen tijd voor over heb.

spoiler:

Net zoals velen hier heb ik ook gebruik gemaakt van de overlap van de onbekende cijfers met de bekende, met alleen een kleine twist.

Overlap met	1	4	7	8 (=len(signal))	som
0	2	3	3	6	14
2	1	2	2	5	10
3	2	3	3	5	13
5	1	3	2	5	11
6	1	3	2	6	12
9	2	4	3	6	15

Het eerste wat ik doe is dus een dictionary "digitMap" aanmaken met daarin de characters van 1, 4, 7, 8. Vervolgens hoef ik alleen maar een enkel getal te bepalen waarmee ik elk missende getal kan identificeren.

Toen was er ineens wel tijd voor een rewrite (misschien wel mijn mooiste dag-uitvoering tot nu toe ):
https://github.com/Cranza.../day8/python/day8class.py

edit: kleine update om wat dubbele meuk te verwijderen (overbodige if statements)

[KabouterSuper]

Glewellyn schreef op woensdag 8 december 2021 @ 13:40:
[...]


Voor alle inputs met dezelfde naam mag je bedenken dat die aan elkaar verbonden zijn. Dus INPUT 0 in blokje 0 is fysiek hetzelfde draadje als INPUT 0 in blokje 1.

Hetzelfde geldt voor de OR poorten, OR(segment1) in blokje 0 is dezelfde OR poort als OR(segment1) in blokje 2. Maar als dat allemaal in 1 schema moet is het niet te overzien.

Het is behoorlijk wat puzzelwerk om het in een schema te krijgen, zeker als je het met de hand doet. Maar het is gelukt....kan ik eindelijk weer verder met mijn leven (tot morgen 5:59).

Code dump:

code:

from collections import defaultdict
bin_array=defaultdict()
bin_array[0]='1101'
bin_array[8]='1111'
bin_array[2]='1010'
bin_array[6]='1011'
bin_array[7]='0001'
bin_array[1]='0000'
bin_array[9]='0111'
bin_array[4]='0110'
bin_array[3]='0011'
bin_array[5]='0010'  

print('x:abcdefg')
for binid in bin_array:
    bin=bin_array[binid]
    b1,b2,b3,b4=bool(int(bin[0])),bool(int(bin[1])),bool(int(bin[2])),bool(int(bin[3]))

    #segmenten:
    a=b1 or (not(b1) and ((not(b3) and b4) or (b3 and ((b2 and b4) or (not(b2) )))))
    b=(b1 and (b2 or b4)) or (not(b1) and ( (b3 and (b2 or (not(b2) and not(b4))))))
    c=(b1 and (b2 or not(b4))) or (not(b1) and ((b3 and (b2 or b4)) or (not(b3))))
    d=b3
    e=b1 
    f=not(b1) or (b1 and b4)
    g=b1 or (not(b1) and (b3 and ((b2 and b4) or not(b2))))

    print(str(binid)+':'+str(int(a))+str(int(b))+str(int(c))+str(int(d))+str(int(e))+str(int(f))+str(int(g)))

[Dricus]

Dag 8 in Clojure

Dat was wel even puzzelen zeg...

spoiler:

Net als vele anderen heb ik dit ook met set operaties opgelost.

Het zal vast nog eenvoudiger kunnen, maar ik vond het wel mooi geweest...

[TrailBlazer]

Grootste les vandaag was toch wel langer nadenken over een goede methode en meer dingen op papier uitschrijven.

[ElkeBxl]

Eindelijk er geraakt met dag 8 in Rust. Deel 1 ging vlot maar op deel 2 vooral zitten zweten door de taal. Ik wist hoe ik het kon oplossen

spoiler:

met HashMap, HashSet en VecDeque

maar ik kreeg het niet goed neergeschreven waardoor ik steeds op errors van de borrow checker enzo botste. Duidelijk nog veel te leren in Rust

[ydderf]

Day 8 in C3 is gelukt. Deel 1 was makkelijk. Deel twee koste wat meer denkwerk over hoe het op te losssen.
Qua code is mijn oplossing behoorlijk recht-toe-recht-aan geprogrammeerd.
Mijn logica om tot een oplossing te komen:

spoiler:

-Tel hoe vaak elke letter voorkomt. Die 6x voorkomt = segment B, 4x = E, 9x = F.
-De combinatie met een lengte van drie letter bevat de A, de combinatie met een lengte van twee letters niet.
-De combinatie met een lengte van twee letters bevat C en F. F is al bekend, dus de andere is C.
-De combinatie met een lengte van vier letter bevat de BCDF. Deze zijn allemaal reeds bekend behalve de D.
-Er is nu nog een onbekende. Dit is de G.

[Dricus]

Grappig, ik heb nog een andere oplossing voor dag 8 gevonden, die ik hier volgens mij nog niet voorbij heb zien komen.

Zie mijn oplossing in Clojure.

spoiler:

Je kunt elk signal pattern en elke output value vertalen naar een string, waarbij elke letter in het pattern vertaalt wordt naar een getal dat aangeeft hoe vaak die letter in totaal in alle patterns voorkomt. De getallen in die string moeten wel gesorteerd worden. Elk getal dat in de display getoond kan worden, krijgt dan een unieke string:

0	"467889"
1	"89"
2	"47788"
3	"77889"
4	"6789"
5	"67789"
6	"467789"
7	"889"
8	"4677889"
9	"677889"

Het maakt niet uit hoe de letters geshuffled zijn, na deze vertaalslag zal elk signal pattern altijd vertaald zijn naar één van bovenstaande strings. Zet die in een hashmap en je kunt elk signal pattern naar een getal vertalen.

[Daos]

Ik heb een brute-force aanpak gekozen voor deel 2. Is in een seconde of 2-3 klaar in c#.

spoiler:

Het aantal mogelijke mappings/permutaties is maar 7! = 5040. Dat kan je makkelijk allemaal proberen en dat heb ik dus gedaan.

[iThinkSo]

Dricus schreef op woensdag 8 december 2021 @ 21:05:
Grappig, ik heb nog een andere oplossing voor dag 8 gevonden, die ik hier volgens mij nog niet voorbij heb zien komen.

Zie mijn oplossing in Clojure.

spoiler:

Je kunt elk signal pattern en elke output value vertalen naar een string, waarbij elke letter in het pattern vertaalt wordt naar een getal dat aangeeft hoe vaak die letter in totaal in alle patterns voorkomt. De getallen in die string moeten wel gesorteerd worden. Elk getal dat in de display getoond kan worden, krijgt dan een unieke string:

0	"467889"
1	"89"
2	"47788"
3	"77889"
4	"6789"
5	"67789"
6	"467789"
7	"889"
8	"4677889"
9	"677889"

Het maakt niet uit hoe de letters geshuffled zijn, na deze vertaalslag zal elk signal pattern altijd vertaald zijn naar één van bovenstaande strings. Zet die in een hashmap en je kunt elk signal pattern naar een getal vertalen.

Van deze techniek zag ik ook al een extreem gegolfde versie langskomen in een Python discord:

spoiler:

print(sum(int(''.join('4725360918'[sum(map(x[:60].count,r))//2%15%11]for r in x[60:].split()))for x in open(0)))

[ Voor 0% gewijzigd door iThinkSo op 08-12-2021 21:52 . Reden: variant -> techniek ]

[TrailBlazer]

Daos schreef op woensdag 8 december 2021 @ 21:35:
Ik heb een brute-force aanpak gekozen voor deel 2. Is in een seconde of 2-3 klaar in c#.

spoiler:

Het aantal mogelijke mappings/permutaties is maar 7! = 5040. Dat kan je makkelijk allemaal proberen en dat heb ik dus gedaan.

spoiler:

Met de bekende 7 en 1 op basis van de lengtes heb je nog maar 6! over dat scheelt nog een factor 7

[Cranzai]

iThinkSo schreef op woensdag 8 december 2021 @ 21:46:
[...]

Van deze variant zag ik ook al een extreem gegolfde versie langskomen in een Python discord:

spoiler:

print(sum(int(''.join('4725360918'[sum(map(x[:60].count,r))//2%15%11]for r in x[60:].split()))for x in open(0)))

Man man man, dit soort oplossingen
Dat heeft toch niets meer met programmeren te maken, totaal niet leesbaar/te begrijpen

Edit:
Beter verwoord, one-liners schrijven is een sport maar verre van praktisch.

[ Voor 8% gewijzigd door Cranzai op 08-12-2021 21:54 ]

[iThinkSo]

Cranzai schreef op woensdag 8 december 2021 @ 21:49:
[...]

Beter verwoord, one-liners schrijven is een sport maar verre van praktisch.

Zie het als normale sport: een bal in een goal trappen is ook niet praktisch maar je houdt er wel conditie en training aan over

Op dezelfde manier leer je door een oplossing zo kort mogelijk te maken ook vaak nieuwe dingen over je taal en stdlib die je goed kunt gebruiken in praktische problemen.

[Varienaja]

Dag 9. Zoals altijd moet je de beschrijving weer goed lezen. :-D

spoiler:

Risiko is 1 plus de diepte Alleen de 3 grootse basins bij elkaar rekenen.

[KabouterSuper]

Varienaja schreef op donderdag 9 december 2021 @ 06:40:
Dag 9. Zoals altijd moet je de beschrijving weer goed lezen. :-D

spoiler:

Risiko is 1 plus de diepte Alleen de 3 grootse basins bij elkaar rekenen.

En geen arrays van int8 maken (want input is toch tussen 0 en 9) om vervolgens die array te misbruiken door er allemaal andere getallen in te stoppen. Dat kostte mj een kwartier extra.

[Janoz]

spoiler:

Ik heb zelf nog even een tijdje nagedacht over een vervelende cornercase, maar uit de beschijving bleek deze niet voor te kunnen komen. Testsets van @DataGhost die dat geval wel hebben accepteer ik dan ook niet

8	8	8
8	7	8
8	7	8
8	8	8

[ Voor 37% gewijzigd door Janoz op 09-12-2021 07:55 ]

[MrHaas]

Varienaja schreef op donderdag 9 december 2021 @ 06:40:
Dag 9. Zoals altijd moet je de beschrijving weer goed lezen. :-D

spoiler:

Risiko is 1 plus de diepte Alleen de 3 grootse basins bij elkaar rekenen.

Haha, inderdaad,

spoiler:

ik had niet gelezen dat 9's niet meetelden. Toen ik dat doorhad werkte mn testinput, maar was gewone input fout. Kwam ik er 20 minuten later achter dat ze niet per 1 oplopend hoeven te zijn

[DevWouter]

(dag 9)

Oké fuck part 2. De kennis die je op doet over het proleem bij deel 1 is absoluut niet nodig bij deel 2.

spoiler:

Basins worden gescheiden van elkaar door 9 en niet door "9, gelijkvloers, alles hoger dan de huidge diepte +1 of een verlaging"

Zie onderstaande afbeelding: Alles wat rood is hoort ook bij je basin. Makkelijkste is als je in het plaatje op zoek gaat naar het kleinste bassin

[MrHaas]

Janoz schreef op donderdag 9 december 2021 @ 07:53:

spoiler:

Ik heb zelf nog even een tijdje nagedacht over een vervelende cornercase, maar uit de beschijving bleek deze niet voor te kunnen komen. Testsets van @DataGhost die dat geval wel hebben accepteer ik dan ook niet

spoiler:

Je moet alleen basins bereken van de lowest points zoals gedefinieerd in deel 1 toch?

[DevWouter]

MrHaas schreef op donderdag 9 december 2021 @ 08:17:
[...]

spoiler:

Je moet alleen basins bereken van de lowest points zoals gedefinieerd in deel 1 toch?

Nee, zie de spoiler in DevWouter in "Advent of Code 2021"

[Hydra]

Day 9 in Kotlin

Hoppa! Deel 2 werkte in 1 keer.

[Janoz]

MrHaas schreef op donderdag 9 december 2021 @ 08:17:
[...]

spoiler:

Je moet alleen basins bereken van de lowest points zoals gedefinieerd in deel 1 toch?

De corner case gaat over deel 1.

DevWouter schreef op donderdag 9 december 2021 @ 08:17:
(dag 9)

Oké fuck part 2. De kennis die je op doet over het proleem bij deel 1 is absoluut niet nodig bij deel 2.

Oh? Bij mij wel

spoiler:

Voor deel 2 gebruik ik een soort floodfill algoritme waarbij ik het antwoord van part 1 gebruik als startpunten waardoor ik het linerair op kan lossen.

[Mschamp]

Dag 9 in C#

Members only:

Alleen zichtbaar voor ingelogde gebruikers. Inloggen

Deel 1 ging redelijk vlot.
Deel 2 toch een tijdje mee bezig geweest.

[armageddon_2k1]

Dag 9 in Kotlin

Veel te lang over deel 1 gedaan vanwege een off-by-one error. En het ergste is dat ik niet weet hoe het komt. Ik heb gewoon Cmd+A, Del gedaan en ben opnieuw begonnen en toen was ie in 1x goed. Mijn testinput was wel goed

Deel 2 in 1x goed.

[ Voor 28% gewijzigd door armageddon_2k1 op 09-12-2021 08:43 ]

[Diderikdm]

Python dag 9

Redelijk vlot

spoiler:

recursiveness

[bakkerjangert]

Opgelsot in Python.

spoiler:

Bij mij werkt deel 2 wel met de laagste punten als berekend in deel 1. Wellicht mazzel met mijn puzzel input?

[DevWouter]

bakkerjangert schreef op donderdag 9 december 2021 @ 08:43:
Opgelsot in Python.

spoiler:

Bij mij werkt deel 2 wel met de laagste punten als berekend in deel 1. Wellicht mazzel met mijn puzzel input?

Ik denk het niet.... Jouw code lijkt gewoon correct.

spoiler:

In jouw code zie ik geen verwijzing naar het gebruik van deltas.

Mocht je het willen testen tegen mijn input: https://github.com/DevWouter/AdventOfCode/tree/main/2021/d09

Code is een puinhoop omdat ik een paar extra checks in had voor potentiele edge cases die mogelijk in de oude situatie van toepassing waren.

Part 1: 572
Part 2: 847044

[KabouterSuper]

DevWouter schreef op donderdag 9 december 2021 @ 08:18:
[...]

Nee, zie de spoiler in DevWouter in "Advent of Code 2021"

Sure?

spoiler:

Er staat:
A basin is all locations that eventually flow downward to a single low point.

Ik heb dit geinterpreteerd as "je mag de low points als startpunten gebruiken".

Daarbij

all other locations will always be part of exactly one basin,

Mijn interpretatie: als punten niet gescheiden zijn door negens, horen ze bij hetzelfde basin.

Mijn oplossing was een flooding loop:
Maak een array die leeg is. Vul de lowpoints met een volgnummer (dus elk lowpoint zijn eigen id)
Markeer alle velden met een 9
Zolang de array nog niet helemaal gevuld is:
1) Loop over de lowpoints van deel 1
als een buur<>9 al een volgnummer heeft, neem dit over
2) tel per volgnummer hoeveel velden dit volgnummer hebben

[dcm360]

Janoz schreef op donderdag 9 december 2021 @ 08:25:

Oh? Bij mij wel

spoiler:

Voor deel 2 gebruik ik een soort floodfill algoritme waarbij ik het antwoord van part 1 gebruik als startpunten waardoor ik het linerair op kan lossen.

spoiler:

Volgens mij zou een floodfill ook per definitie het juiste antwoord moeten geven. Een basin heeft altijd 1 low point, en wordt enkel begrensd door de rand en negens. Ik zat nog te denken of ik ergens moest kijken of er 'overlappende' basins zouden kunnen zijn met een floodfill vanaf een low point, maar dat lijkt volgens de uitleg niet mogelijk te zijn.

Naast dat is mijn floodfill wel een beetje brak. Ik werk een stack door om het basin te vullen, en vanaf het huidige punt zet ik altijd de buren die nog niet in het basin zitten op de stack. Daarmee kunnen punten dus wel meermaals in de stack zitten, want die was ik even vergeten te controleren bij het toevoegen

[coop]

Dag 9 in Python

Met 15ms voor deel 1 en 0.34ms voor deel 2 (inclusief deel 1 voor de laagste punten), is het waarschijnlijk niet de snelste oplossing maar voor mij prima.

spoiler:

Ik gebruik ook de input van deel 1 voor deel 2. Vanuit de laagste punten kijk ik of naastliggende punten groter, en niet 9, zijn. Voor deze punten doe ik dan hetzelfde tot er geen nieuwe punten zijn.

[iThinkSo]

KabouterSuper schreef op donderdag 9 december 2021 @ 09:33:
[...]

Sure?

spoiler:

Mijn interpretatie: als punten niet gescheiden zijn door negens, horen ze bij hetzelfde basin.

spoiler:

Dat is inderdaad een erg logische afleiding, en eentje die ik niet had gemaakt. Ik was ervanuit gegaan dat je vanuit een punt naar de laagste buur moest, dus heb geen flood fill gedaan maar een (cached) walk

[DevWouter]

KabouterSuper schreef op donderdag 9 december 2021 @ 09:33:
[...]

Sure?

spoiler:

Er staat:
A basin is all locations that eventually flow downward to a single low point.

Ik heb dit geinterpreteerd as "je mag de low points als startpunten gebruiken".

Daarbij

all other locations will always be part of exactly one basin,

Mijn interpretatie: als punten niet gescheiden zijn door negens, horen ze bij hetzelfde basin.

Mijn oplossing was een flooding loop:
Maak een array die leeg is. Vul de lowpoints met een volgnummer (dus elk lowpoint zijn eigen id)
Markeer alle velden met een 9
Zolang de array nog niet helemaal gevuld is:
1) Loop over de lowpoints van deel 1
als een buur<>9 al een volgnummer heeft, neem dit over
2) tel per volgnummer hoeveel velden dit volgnummer hebben

"Je moet alleen ..." vs "Je kan..."

De methode die je beschrijft was degene die ik ook zou gebruiken. Overigens kan je die ook zonder het antwoord van deel 1 doen.

[KabouterSuper]

iThinkSo schreef op donderdag 9 december 2021 @ 09:36:
[...]

spoiler:

Dat is inderdaad een erg logische afleiding, en eentje die ik niet had gemaakt. Ik was ervanuit gegaan dat je vanuit een punt naar de laagste buur moest, dus heb geen flood fill gedaan maar een (cached) walk

Maar ik moet @DevWouter ook gelijkgeven dat er er edge case zou kunnen bestaan die een probleem oplevert:

spoiler:

9 9 9 9 9 9 9 9
9 6 6 8 7 7 7 9
9 6 1 8 7 1 7 9
9 6 6 8 7 7 7 9
9 9 9 9 9 9 9 9

Er zijn twee low points (de enen), maar toch maar 1 basin (alles behalve de negens). Blijkbaar komt dit niet voor in de datasets, want er wordt duidelijk gezegd dat all points!=9 in maximaal 1 basin zitten. In mijn geval zouden de achten in twee basins kunnen zitten.
Maar dit is een specifiek probleem dat ik niet in het plaatje van @DevWouter terugzie.

[KabouterSuper]

DevWouter schreef op donderdag 9 december 2021 @ 09:44:
[...]


"Je moet alleen ..." vs "Je kan..."

De methode die je beschrijft was degene die ik ook zou gebruiken. Overigens kan je die ook zonder het antwoord van deel 1 doen.

Ik was er blind vanuit gegaan dat de maker deel 1 zo had geconstrueerd dat het handig was om de oplossing daarvan te gebruiken. Maar je hebt helemaal gelijk dat dat natuurlijk niet hoeft.

spoiler:

De fysische variant van het probleem is denk ik om het landschap met regen onder water te zetten tot hoogte 8.5 en dan de basins te tellen. Blijkbaar heeft de maker het probleem iets versimpeld door te zorgen dat er bij elke waterhoogte alleen basins ontstaan bij low points (dus de regen blijft niet staan in het linker basin in mijn voorbeeld). Had niet gehoeven, maar het wel gemakkelijker.

[ Voor 4% gewijzigd door KabouterSuper op 09-12-2021 09:58 ]

[Hydra]

DevWouter schreef op donderdag 9 december 2021 @ 08:17:
(dag 9)

Oké fuck part 2. De kennis die je op doet over het proleem bij deel 1 is absoluut niet nodig bij deel 2.

spoiler:

Klopt. Het is gewoon een flood-fill van alles wat niet '9' is.

[Hydra]

Janoz schreef op donderdag 9 december 2021 @ 08:25:

spoiler:

Voor deel 2 gebruik ik een soort floodfill algoritme waarbij ik het antwoord van part 1 gebruik als startpunten waardoor ik het linerair op kan lossen.

Ja, maar dat is dus helemaal niet nodig. Zie mijn implementatie.

[ Voor 15% gewijzigd door Hydra op 09-12-2021 09:57 ]

[coop]

spoiler:

Volgens mij kan je op basis van de tekst er vanuit gaan dat elk punt dat geen low-point of 9 is altijd oploopt van het low point in zijn basin naar een 9.
Een basin is namelijk opgemaakt uit alle punten die uiteindelijk naar een enkel low point 'stromen' en elk punt (geen 9s) is onderdeel van maar 1 basin.

[dcm360]

spoiler:

Volgens mij kunnen er volgens de beschrijving ook punten zijn die geen onderdeel zijn van een basin, omdat ze geen low point hebben om naar af te lopen. Dat lijkt echter ook niet voor de komen in de datasets. Meest eenvoudige voorbeeld hiervoor zou iets als '11' zijn: geen low point, dus geen basin.

[coop]

dcm360 schreef op donderdag 9 december 2021 @ 10:04:

spoiler:

Volgens mij kunnen er volgens de beschrijving ook punten zijn die geen onderdeel zijn van een basin, omdat ze geen low point hebben om naar af te lopen. Dat lijkt echter ook niet voor de komen in de datasets. Meest eenvoudige voorbeeld hiervoor zou iets als '11' zijn: geen low point, dus geen basin.

spoiler:

Ik denk dus dat dit niet kan en '11' geen mogelijke input van deze puzzel kan zijn, aangezien er specifiek staat dat elk punt niet gelijk aan 9 altijd onderdeel is van precies 1 basin. En een basin heeft altijd 1 enkel low point. Een veld met alleen 9's zou dus technisch gezien wel kunnen, maar dan is het antwoord op deel 1 en 2 altijd 0 (geen low point en geen basins)

[ Voor 9% gewijzigd door coop op 09-12-2021 10:11 ]

[Diderikdm]

spoiler:

Volgens de omschrijving van part 2 is elk punt welke lager is dan 9 automatisch een "low" point (omdat er geen waardes hoger dan 9 bestaan in deze puzzel). Om deze reden kan je er vanuit gaan dat elk punt (<9) een "low" point is. Je hoeft alleen de punten binnen de negens op te tellen. In principe maakt het dus ook niet uit of je op het laagste punt begint, of een 8. Deze vallen allemaal binnen dezelfde groep 9's

[dcm360]

coop schreef op donderdag 9 december 2021 @ 10:07:
[...]

spoiler:

Ik denk dus dat dit niet kan en '11' geen mogelijke input van deze puzzel kan zijn, aangezien er specifiek staat dat elk punt niet gelijk aan 9 altijd onderdeel is van precies 1 basin. En een basin heeft altijd 1 enkel low point. Een veld met alleen 9's zou dus technisch gezien wel kunnen, maar dan is het antwoord op deel 1 en 2 altijd 0 (geen low point en geen basins)

spoiler:

Hm, inderdaad. Dan zijn er eigenlijk niet echt edge cases in deze puzzel om rekening mee te houden.

[Janoz]

dcm360 schreef op donderdag 9 december 2021 @ 09:33:
[...]

spoiler:

Volgens mij zou een floodfill ook per definitie het juiste antwoord moeten geven. Een basin heeft altijd 1 low point, en wordt enkel begrensd door de rand en negens. Ik zat nog te denken of ik ergens moest kijken of er 'overlappende' basins zouden kunnen zijn met een floodfill vanaf een low point, maar dat lijkt volgens de uitleg niet mogelijk te zijn.

Het werkt ook gewoon met meerdere punten in hetzelfde basin. Vandaar dat ik er ook voor gekozen had. Had alleen even gemist dat er niet meer in een basin konden liggen

[Remcoder]

Deze was een doozy

Members only:

Alleen zichtbaar voor ingelogde gebruikers. Inloggen

spoiler:

Voor deel 1 zoeken naar een punt met alleen maar hogere buren, en voor deel 2 zoeken naar iets wat lager is dan een 9, vanaf dit punt alle aangrenzende punten die geen 9 zijn opvullen met een getal hoger dan 9, na het vullen kijken hoe vaak dat getal voorkomt in de grid, rinse en repeat met een ander getal tot je overal geweest bent

[FrankMennink]

Dag 9 in Python

spoiler:

Toch best nog een tijdje moeten denken over hoe deel 2 aan te pakken. Na een paar keer herlezen van de opdracht bedacht dat je met de lowest points uit deel 1 in de cardinal directions uit kan breiden tot je een 9 of de rand hit

[KabouterSuper]

Diderikdm schreef op donderdag 9 december 2021 @ 10:21:

spoiler:

Volgens de omschrijving van part 2 is elk punt welke lager is dan 9 automatisch een "low" point (omdat er geen waardes hoger dan 9 bestaan in deze puzzel). Om deze reden kan je er vanuit gaan dat elk punt (<9) een "low" point is. Je hoeft alleen de punten binnen de negens op te tellen. In principe maakt het dus ook niet uit of je op het laagste punt begint, of een 8. Deze vallen allemaal binnen dezelfde groep 9's

spoiler:

Bij mijn oplossing geef ik elk (echt) low point een identifier en verspreid ik die identifier door die bij de buren in te vullen als dat geen 9 is (waarna ik een count doe per identifier). Daarbij ga ik er wel hard van uit dat een getal<9 maar bij één low point hoort, omdat een veld anders meerdere identifiers kan krijgen (en door het algoritme krijg ik dan de eerste). Je zou het kunnen zien dat ik elk low point zijn eigen kleur geef en door te percoleren kijk welke punten die kleur krijgen. Je wilt voorkomen dat kleuren gaan mengen.

Overigens, ik vind dat je altijd mooie python code schrijft, mijn complimenten!

[Creepy]

En dag 9 https://github.com/CodeEn...eer/aoc/aoc2021/Day9.java

Veel te lang over deel 1 gedaan want ik had te snel gelezen .

spoiler:

Ik was ook diagonaal bezig

en vervolgens nog door een kronkel in mijn gedachten.

spoiler:

Bijv twee keer een 0 naast elkaar zou een lowest point moeten zijn, maar is het door de definitie in de tekst dus niet.

spoiler:

Deel 2 gewoon recursief doorzoeken met de gevonden punten uit deel 1, corner case met 2 lowest points die in 1 basin zitten was er blijkbaar niet.

Edit: o wacht, met een minimale aanpassing boeit die corner case ook niet. En done.

[ Voor 10% gewijzigd door Creepy op 09-12-2021 11:13 ]

[EfBe]

Dag 9. Leuke convolution kernel puzzle
https://github.com/FransB.../src/AoC2021.Code/Day9.cs

spoiler:

Vreesde even dat mijn recursion based oplossing een stackoverflow zou geven met de massive input, maar dat viel mee.

Marking van cellen helpt, en het zien dat 9 de grens is maakte puzzle 2 simpel. Maar als je dat niet ziet wordt het lastig...

Heb niet de punten uit puzzle 1 gebruikt voor 2, gewoon het hele array doorzoeken in 2, want je moet toch alle cellen bekijken, dus eerst alle cellen bekijken voor de laagste punten is redundant. Ik doe in feite een flood fill, met de randen en 9's als grens voor de area.

[ Voor 26% gewijzigd door EfBe op 09-12-2021 11:28 ]

[Diderikdm]

KabouterSuper schreef op donderdag 9 december 2021 @ 10:46:
[...]

spoiler:

Bij mijn oplossing geef ik elk (echt) low point een identifier en verspreid ik die identifier door die bij de buren in te vullen als dat geen 9 is (waarna ik een count doe per identifier). Daarbij ga ik er wel hard van uit dat een getal<9 maar bij één low point hoort, omdat een veld anders meerdere identifiers kan krijgen (en door het algoritme krijg ik dan de eerste). Je zou het kunnen zien dat ik elk low point zijn eigen kleur geef en door te percoleren kijk welke punten die kleur krijgen. Je wilt voorkomen dat kleuren gaan mengen.

Overigens, ik vind dat je altijd mooie python code schrijft, mijn complimenten!

spoiler:

Dank! De manier die je omschrijft zou een goede opzet zijn wil je een uiteindelijke upping the ante volumeberekening doen over de basins

[Hydra]

Zo, eindelijk tijd gehad om 'em ook nog even op te schonen.

Was wel heel erg in m'n nopjes met hoe het ging vanochtend!

spoiler:

Je merkt sterk dat als je dit vaker doet, je er ook veel beter in wordt. En waar ik gister echt lang bezig ben geweest met deel 2 (van 7 tot 9 ofzo), 'zag' ik hier de oplossing meteen. In tegenstelling tot waar deel 1 naar hint hoef je niet te simuleren ofzo, maar kan je gewoon de verschillende areas flood-fillen. En toen ook nog eens uit m'n hoofd een floodfill geschreven die in 1 keer werkte.

Ik ben van origine niet goed in dit soort dingen, dus ik ben wel blij met mezelf

Famous last words natuurlijk, ik vermoed dat de komende twee zaterdagen m'n butt weer gaan kicken

[DevWouter]

KabouterSuper schreef op donderdag 9 december 2021 @ 09:53:
[...]

Ik was er blind vanuit gegaan dat de maker deel 1 zo had geconstrueerd dat het handig was om de oplossing daarvan te gebruiken. Maar je hebt helemaal gelijk dat dat natuurlijk niet hoeft.

spoiler:

De fysische variant van het probleem is denk ik om het landschap met regen onder water te zetten tot hoogte 8.5 en dan de basins te tellen. Blijkbaar heeft de maker het probleem iets versimpeld door te zorgen dat er bij elke waterhoogte alleen basins ontstaan bij low points (dus de regen blijft niet staan in het linker basin in mijn voorbeeld). Had niet gehoeven, maar het wel gemakkelijker.

Nah, ik denk dat de maker heel goed heeft nagedacht over dit probleem. Als ik dit in een training (lab gedeelte) zou verwerken dan zou het ook een soort gelijke aanpak zijn.

spoiler:

De floodfill bestaat vaak uit een "test" en een "walker". In deel 1 leer je de test en in deel 2 leer je de walker.
Die kan je allemaal stapsgewijs oppakken waardoor de trainee telkens de fundamenten van het vorige deel kan leren.

Daarom ook mijn grote middelvinger. Een gedeelte van de logica (max-slope) wordt niet hergebruikt.

Het was toen ik het ging visualiseren toen ik zag dat er een cellur noise generator gebruikt was en ik 1+1 ging doen en snapte waarom de max-slope opeens geen requirement meer kon zijn.

[Hydra]

armageddon_2k1 schreef op donderdag 9 december 2021 @ 08:40:
Dag 9 in Kotlin

Ik kijk altijd uit naar jouw submission omdat je dingen iedere keer net iets anders aanpakt en ik toch vaak kleine kotlin dingetjes leer

Kan je wel aanraden een Point class te implementeren. Die gebruik ik zoveel dat er eelt op zit zolangzamerhand.

[ Voor 12% gewijzigd door Hydra op 09-12-2021 11:50 ]

[DataGhost]

De opdrachten worden al iets lastiger om leuke input generators voor te maken, maar het is redelijk low-effort nog wel gelukt denk ik. Up 1, bzipped Up 2, bzipped Up 3, bzipped en antwoorden (denk ik )

Edit: makkelijke oneline-testcase voor kwadratische algoritmes toegevoegd: Up 4, bzipped.

[ Voor 14% gewijzigd door DataGhost op 09-12-2021 21:05 ]

[DevWouter]

Correctie

spoiler:

Het is geen cellur noise, eerder alligator noise (een variatie op Worley ) als ik kijk naar https://docs.arnoldrenderer.com/display/A5AFCUG/Cell+Noise (scroll voorbij de tabel)

Ik begon te twijfelen toen ik het visualiseerde en een paar artifacts bij de 9 zag die ik niet kon verklaren. Dus toen nog een keer gevisualiseerd dit keer met gradients en dat leek niet op cell noise zoals ik het kende

[Glewellyn]

En hierbij mijn dagelijkse portie spaghetti.

Members only:

Alleen zichtbaar voor ingelogde gebruikers. Inloggen

[Janoz]

Als vingeroefening ook nog maar eens een implementatie voor deel 2 gemaakt waarbij ik alleen naar het punt links en het punt boven het huidige punt kijk.

[MueR]

Zo, ook dag 9 weer af.

Members only:

Alleen zichtbaar voor ingelogde gebruikers. Inloggen

[armageddon_2k1]

Hydra schreef op donderdag 9 december 2021 @ 11:46:
[...]


Ik kijk altijd uit naar jouw submission omdat je dingen iedere keer net iets anders aanpakt en ik toch vaak kleine kotlin dingetjes leer

Kan je wel aanraden een Point class te implementeren. Die gebruik ik zoveel dat er eelt op zit zolangzamerhand.

Ha, leuk om te horen. Dat heb ik ook bij jou. Heb zeker 2020 heel veel geleerd van jouw cleane code. En leer ook elke keer weer wat.

Wat betreft de Point class heb je gelijk. Ik had namelijk een Board (voor een grid) en een Point class en die gebruik ik vaker en daar had ik een off-by-1 error....En dus had ik meer tijd verloren met het hoe en waarom dan de implementatie.

Ik ga het nog opschonen in ieder geval en kijken waar die off-by-1 vandaan kwam.

P.s. Ik gebruik vaak Complexe getallen als positie, omdat je dan rotaties gratis krijgt :-) En dat is nog wel eens een dingetje met AoC.

[ Voor 14% gewijzigd door armageddon_2k1 op 09-12-2021 13:15 ]

[Dricus]

Dag 9 in Clojure

De code kan nog iets netter, maar al met al ben ik best tevreden. Bij puur functioneel programmeren moet je echt helemaal van de imperatieve mindset af en dat is toch nog steeds af en toe best lastig. Ik word er steeds beter in om een oplossing op te hakken in een serie van transformaties vanuit een startpunt. Volgens mij is dat de beste manier om dit soort problemen in een puur functionele programmeertaal zoals Clojure op te lossen. En het leidt ook nog eens tot code waarin die transformaties goed terug te lezen zijn.

[P_Tingen]

Een tijd zitten te klooien met de input. Ik lees de input als 1 bonk in en ontleed het dan op basis van scheidingstekens. In Progress 4GL zijn regels gescheiden door ~n maar kennelijk ook door een ~r (CR/LF). Die ~r haalde ik er eerst niet uit zodat mijn "regels" 1 positie te lang waren. Dat teken kon weer niet naar integer worden omgezet maar daar kreeg ik geen melding van, zodat mijn uitkomst een hele tijd niet klopte.

Ah, well, uiteindelijk wel een elegante oplossing van gemaakt.
https://github.com/patric...e/tree/master/2021/Day-09

[Varienaja]

Ik vind de persoonlijke statistieken nog best interessant. Mijn stiekeme doel is om bij deel 2 een betere Rank te hebben dan bij deel 1.
Dat is me dit jaar nog lang niet altijd gelukt. (Alleen dag 1,2,3,5,9)

[ Voor 3% gewijzigd door Varienaja op 09-12-2021 14:27 ]

[Cranzai]

Nou, poeh dag 9

spoiler:

Bewust gekozen voor een numpy array omdat deze sneller zouden moeten zijn dan nested lists.
Met halfbakken recursion
Mijn "isValley" en "bassinInspect" functies kunnen misschien nog wel gemergd worden maar voor nu vind ik het prima.

https://github.com/Cranza.../2021/day9/python/day9.py

edit:
Overigens wel echt haat dat een:
3 2 2 3
2 1 1 3
3 2 2 3

Niet als valley gerekend wordt.

[ Voor 59% gewijzigd door Cranzai op 09-12-2021 15:02 ]

[Hydra]

armageddon_2k1 schreef op donderdag 9 december 2021 @ 13:07:
P.s. Ik gebruik vaak Complexe getallen als positie, omdat je dan rotaties gratis krijgt :-) En dat is nog wel eens een dingetje met AoC.

Oh! Da's ook wel een goeie inderdaad. Ik heb wel een aantal classes (zoals Point) rotaties al ingebouwd, maar kwam er dus onlangs achter dat in een van die methodes gewoon een fout zat. Oops

[Lisper]

Dricus schreef op donderdag 9 december 2021 @ 13:20:
Dag 9 in Clojure

De code kan nog iets netter, maar al met al ben ik best tevreden. Bij puur functioneel programmeren moet je echt helemaal van de imperatieve mindset af en dat is toch nog steeds af en toe best lastig. Ik word er steeds beter in om een oplossing op te hakken in een serie van transformaties vanuit een startpunt. Volgens mij is dat de beste manier om dit soort problemen in een puur functionele programmeertaal zoals Clojure op te lossen. En het leidt ook nog eens tot code waarin die transformaties goed terug te lezen zijn.

Nice, Clojure is mijn favoriete taal, ik ben groot fan van tranformaties aan elkaar lussen met -> en ->>

Je oplossing ziet er kwa structuur goed uit. Als je de performance wil verbeteren raad ik je aan om vectors te gebruiken,
dan kun je nth (die is (O(n)) vervangen door get (O(log32(n)). Dat is voor deze dag nog niet nodig, maar in mijn ervaring worden dit soort optimalisaties belangrijker in de latere opdrachen.

Verder is die lazy-seq op regel 46 overbodig

[Dricus]

Lisper schreef op donderdag 9 december 2021 @ 15:22:
Nice, Clojure is mijn favoriete taal, ik ben groot fan van tranformaties aan elkaar lussen met -> en ->>

Vandaar ook je nickname?

Je oplossing ziet er kwa structuur goed uit.

Thanks!

Als je de performance wil verbeteren raad ik je aan om vectors te gebruiken,
dan kun je nth (die is (O(n)) vervangen door get (O(log32(n)). Dat is voor deze dag nog niet nodig, maar in mijn ervaring worden dit soort optimalisaties belangrijker in de latere opdrachen.

Ja, mee eens. Ik moet me nog wat bewuster worden van welk soort collection (seq, vec) ik waar precies gebruik.

Verder is die lazy-seq op regel 46 overbodig

Dat vermoeden had ik al.

Dankjewel voor je feedback!

[joppybt]

Varienaja schreef op donderdag 9 december 2021 @ 14:26:
Ik vind de persoonlijke statistieken nog best interessant. Mijn stiekeme doel is om bij deel 2 een betere Rank te hebben dan bij deel 1.
Dat is me dit jaar nog lang niet altijd gelukt. (Alleen dag 1,2,3,5,9)

Intrigerend. Vorig jaar had ik op 24 van de 25 dagen voor deel 2 een hogere ranking dan voor deel 1 (alleen dag 19 niet).

Ik ben echt niet bijzonder snel met deel twee (bij de latere opdrachten vaak meer dan een uur na deel 1) en zelden bij de eerste 5000 personen. Ik vraag me dus af hoe dit ranking effect kan ontstaan.

[ Voor 4% gewijzigd door joppybt op 09-12-2021 17:27 ]

[MueR]

Varienaja schreef op donderdag 9 december 2021 @ 14:26:
Ik vind de persoonlijke statistieken nog best interessant. Mijn stiekeme doel is om bij deel 2 een betere Rank te hebben dan bij deel 1.
Dat is me dit jaar nog lang niet altijd gelukt. (Alleen dag 1,2,3,5,9)

Voor mij alleen dag 7 niet.

[martyw]

https://github.com/martyw/AOC2021/blob/main/day9.py

spoiler:

Voor part 2 heb ik de laagste punten uit part 1 als startpunten voor de basins gebruikt, daarna recursief de buren langs, zolang ze groter of gelijk zijn zijn als je huidige punt zijn ze deel van het basin, bij een 9 stop je in die richting.

[TrailBlazer]

Leuke opdracht vandaag hoop dingen van geleerd mbt python. Recursieve functies had ik nog nooit gebruikt en ik begrijp immutable en mutable beter.

[iThinkSo]

Varienaja schreef op donderdag 9 december 2021 @ 14:26:
Ik vind de persoonlijke statistieken nog best interessant. Mijn stiekeme doel is om bij deel 2 een betere Rank te hebben dan bij deel 1.
Dat is me dit jaar nog lang niet altijd gelukt. (Alleen dag 1,2,3,5,9)

Voor mij alleen dag 5 niet, maar dat was omdat ik toen supervroeg wakker was, dus in de global top ~1000 zat voor beide delen

[Hydra]

Omdat het er best sexy uitziet heb ik even een animatie van m'n algorithme gemaakt: https://i.imgur.com/Q22O5Eo.gifv

(Niet als plaatje want spoiler)

[Rogier V]

Leuke opdracht vandaag. Deel 1 is eenvoudig te doen. Ik merk dat ik wel een dag nodig heb om rustig deel 2 in mijn hoofd op te lossen (ik ben niet zo snel)...als ik eenmaal een idee hebt, dan is de oplossing niet heel moeilijk.

https://github.com/rogier...er/AOC2021/Day09/Day09.fs

[Cranzai]

Hydra schreef op donderdag 9 december 2021 @ 19:06:
Omdat het er best sexy uitziet heb ik even een animatie van m'n algorithme gemaakt: https://i.imgur.com/Q22O5Eo.gifv

(Niet als plaatje want spoiler)

Damn, nice!
Ben nu heel benieuwd hoe mijn algoritme er uit zou zien. Hoe heb je dit zo gemaakt?

[Hydra]

Cranzai schreef op donderdag 9 december 2021 @ 19:23:
Ben nu heel benieuwd hoe mijn algoritme er uit zou zien. Hoe heb je dit zo gemaakt?

Hier is de code.

Heb m'n oplossing voor Dag 9 gekopieerd en van elke tussenstap wordt een image getekend. Die voeg ik dan samen met een kleine utility class tot een animated gif.

Edit: Alternatief. Deze werkt van laag naar hoog ipv gewoon de rij af te gaan: https://imgur.com/a/652z2Fd

[ Voor 7% gewijzigd door Hydra op 09-12-2021 19:41 ]

[Kazu]

Vandaag was leuk om te doen, inderdaad Zo'n beetje dezelfde oplossing bedacht als velen hier, zo te zien.

spoiler:

Ik ging qua code complexiteit in een mooie curve Ik wilde voor deel 2 voorkomen dat ik punten meerdere keren zou bezoeken, dus was een map van bezochte punten aan het bijhouden. Hierna bedacht ik me dat het veel makkelijker kon door gewoon in-place de heatmap aan te passen zodat er überhaupt geen aparte map nodig is.

Vervolgens nog 15 minuten verspild met het debuggen van m'n code, omdat de test input wel de juiste uitkomst gaf, maar de puzzel input niet. Kwam ik erachter dat ik twee keer de enalaatste (gesorteerde) basin size pakte om te vermenigvuldigen, wat bij de test input precies goed uit kwam (want twee keer 9). Lekker scherp weer Oh well, daardoor wel nog wat code kunnen strippen, dus mag niet klagen.

Members only:

Alleen zichtbaar voor ingelogde gebruikers. Inloggen

Al met al deel 2 in 0.95ms. Kan nog wel wat sneller, maar vind het wel goed zo.

[Cranzai]

Hydra schreef op donderdag 9 december 2021 @ 19:33:
[...]


Hier is de code.

Heb m'n oplossing voor Dag 9 gekopieerd en van elke tussenstap wordt een image getekend. Die voeg ik dan samen met een kleine utility class tot een animated gif.

Edit: Alternatief. Deze werkt van laag naar hoog ipv gewoon de rij af te gaan: https://imgur.com/a/652z2Fd

Chill eens ff kijken of ik dat kan implementeren.
Waarschijnlijk ziet mijn oplossing er uit zoals jouw alternatief.

[Cranzai]

Kazu schreef op donderdag 9 december 2021 @ 19:43:
Vandaag was leuk om te doen, inderdaad Zo'n beetje dezelfde oplossing bedacht als velen hier, zo te zien.

spoiler:

Ik ging qua code complexiteit in een mooie curve Ik wilde voor deel 2 voorkomen dat ik punten meerdere keren zou bezoeken, dus was een map van bezochte punten aan het bijhouden. Hierna bedacht ik me dat het veel makkelijker kon door gewoon in-place de heatmap aan te passen zodat er überhaupt geen aparte map nodig is.

Vervolgens nog 15 minuten verspild met het debuggen van m'n code, omdat de test input wel de juiste uitkomst gaf, maar de puzzel input niet. Kwam ik erachter dat ik twee keer de enalaatste (gesorteerde) basin size pakte om te vermenigvuldigen, wat bij de test input precies goed uit kwam (want twee keer 9). Lekker scherp weer Oh well, daardoor wel nog wat code kunnen strippen, dus mag niet klagen.

***members only***

Al met al deel 2 in 0.95ms. Kan nog wel wat sneller, maar vind het wel goed zo.

Goede manier van flaggen!

[P_Tingen]

Voor deel 2 kwamen de eigenschappen van een 4GL goed van pas.

spoiler:

Ik kan een db-tabel in geheugen definieren waar ik makkelijk doorheen kan zoeken. Ik stop alles in die tabel, waarbij ik de hoogte van de locatie bekijk bij het inlezen: van de locaties met hoogte 9 zet ik het bassin nr op -1, bij de rest op 9. De hoogte is daarna niet meer belangrijk.

In een lus zoeken naar de eerste in de tabel waarbij het bassin nr nog nul is. Dan roep ik een recursieve procedure aan met de coördinaten van die locatie en het bassin-nr (in eerste instantie 1). Die procedure kijkt of het punt in kwestie al ingedeeld is bij een bassin. Zo ja: terug, zo nee, jezelf aanroepen voor de locaties links, rechts, boven en onder. Als er niks meer zonder bassin nr is, de lus verlaten.

Daarna wat zoeken, sorteren en sommeren en klaar!

https://github.com/patric...ter/2021/Day-09/day-09b.p

[Varienaja]

Grappig dat iedereen de strings van de invoer ombouwt tot tweedimensionale int arrays. Ik reken direct met lines.get(y).charAt(x) Dat gaat net zo goed toch?

https://github.com/varien...tofcode2021/Puzzle09.java

[DataGhost]

Varienaja schreef op donderdag 9 december 2021 @ 20:07:
Grappig dat iedereen de strings van de invoer ombouwt tot tweedimensionale int arrays. Ik reken direct met lines.get(y).charAt(x) Dat gaat net zo goed toch?

https://github.com/varien...tofcode2021/Puzzle09.java

Dat kan natuurlijk ook, maar in redelijk wat talen moet je alsnog door een hoepeltje springen om vergelijkingen (groter/kleiner) te doen dus dan kan je er net zo goed een int van maken. En in deel 1 weet je natuurlijk nog niet wat deel 2 gaat zijn, terwijl de kans op wiskunde behoorlijk groot is dus dat kan je beter direct al goed doen. In ieder geval maakt het voor de looptijd niks uit, je kan namelijk in O(n) alles omzetten naar ints en diezelfde O(n) heb je sowieso al nodig voor het inlezen alleen al. Algoritmisch gezien wordt het er dus niet slechter van. Het verkeerde algoritme kiezen voor het daadwerkelijke uitrekenen is juist hetgene wat enige impact gaat hebben.

Sterker nog: op sommige architecturen kan het juist sneller zijn met een array van ints die memory-aligned zijn, in tegenstelling tot het ophalen van een bepaalde byte in een string, wat bijvoorbeeld een 32-bits of 64-bits read is waarna nog een shift en een and moet gebeuren om daar die ene byte uit te halen. Maar op het moment dat je naar dat soort optimalisaties gaat kijken zijn er al heftige dingen aan de hand. En ook dit doet algoritmisch gezien niks aan de looptijd, nog steeds O(n).

Edit: nou moet ik wel zeggen dat jouw algoritme stiekem kwadratisch lijkt, maar daarbij ook vermelden dat ik nauwelijks ervaring heb met java (dus de library niet ken).
Edit2: nu ik 'm draai lijkt het nog meer kwadratisch
Edit3: probeer maar met Up 4, bzipped. Antwoorden 2 en 958429

[ Voor 27% gewijzigd door DataGhost op 09-12-2021 21:06 ]

[P_Tingen]

Varienaja schreef op donderdag 9 december 2021 @ 20:07:
Grappig dat iedereen de strings van de invoer ombouwt tot tweedimensionale int arrays. Ik reken direct met lines.get(y).charAt(x) Dat gaat net zo goed toch?

https://github.com/varien...tofcode2021/Puzzle09.java

Voor deel 1 heb ik dat wel zo gedaan inderdaad (met equivalente functies dan). Voor deel 2 werd dat te traag. Progress 4GL is relatief traag met intensief gebruik van functies en voor deel twee moest ik dan wel heel veel functies aan elkaar knopen. Nu maakt de tijd niet zoveel uit voor deze opgave, maar het werd er ook niet leesbaarder van. Overigens is deel 2 in Progress 4GL nu op mijn pc in 1120 ms klaar (1,1 sec)

[ElkeBxl]

Deel 1 had ik vanochtend snel gevonden maar dan geen tijd meer gevonden voor deel 2. Nu wel afgewerkt. Mijn oplossing in Rust.

Kazu schreef op donderdag 9 december 2021 @ 19:43:

spoiler:

Vervolgens nog 15 minuten verspild met het debuggen van m'n code, omdat de test input wel de juiste uitkomst gaf, maar de puzzel input niet. Kwam ik erachter dat ik twee keer de enalaatste (gesorteerde) basin size pakte om te vermenigvuldigen, wat bij de test input precies goed uit kwam (want twee keer 9). Lekker scherp weer

Ik had exact hetzelfde voor

[tarlitz]

Superinteressant om alle verschillende oplossingen hier te zien! Ik vond deel 2 vandaag eigenlijk best makkelijk. Voor mij was het 2 regels code met:

spoiler:

scipy (https://docs.scipy.org/do.../scipy.ndimage.label.html)

.
Die oplossingen met cell voor cell de basins vullen zou ik nooit opgekomen zijn.😅

[Verwijderd]

DevWouter schreef op donderdag 9 december 2021 @ 08:55:
[...]

Ik denk het niet.... Jouw code lijkt gewoon correct.

spoiler:

In jouw code zie ik geen verwijzing naar het gebruik van deltas.

Mocht je het willen testen tegen mijn input: https://github.com/DevWouter/AdventOfCode/tree/main/2021/d09

Code is een puinhoop omdat ik een paar extra checks in had voor potentiele edge cases die mogelijk in de oude situatie van toepassing waren.

Part 1: 572
Part 2: 847044

yep, gereproduceerd met jouw input.
Ik heb het denk ik anders gedaan als wat hier tot nu toe staat:

spoiler:

Met de uitkomst van deel 1 een veld gemaakt met 0 voor de edges en randen en een oplopend nummer egbruikt voor de verschillende 'kuilen'. Daarna met een convolutie filter er in vier richtingen overheen waarbij ik na iedere iteratie de waardes die voorheen niet nul waren de oude waardes gaf. Als je dit een keer of 20 herhaalt (of checked of er geen wijzigigen in de output meer zijn) kun je simpelweg de waardes in het veld sorteren en de grootste groepen zoeken. Werkt best lekker in Matlab maar 25 regels of zo.

[diabolofan]

Ik ben ook weer bij! Gisteren in korte tijd deel 1 weten te doen, maar over deel 2 moest ik even nadenken, dus vanavond pas gemaakt samen met dag 9. Voor deze keer ben ik tevreden met mooie een trage executietijd, omdat ik even geen zin heb om te refactoren...

https://github.com/gercob...dventOfCode2021/src/day09

[Varienaja]

Weer een eitje vandaag. Maar toch had ik voor het tweede deel een slechtere ranking als voor het eerste.

https://github.com/varien...tofcode2021/Puzzle10.java

[ Voor 34% gewijzigd door Varienaja op 10-12-2021 08:23 ]

[Janoz]

Varienaja schreef op vrijdag 10 december 2021 @ 06:59:
Weer een eitje vandaag. Maar toch had ik voor het tweede deel een slechtere ranking als voor het eerste.

Afhankelijk van je aanpak bij deel 1 zou je deel 2 heel snel af moeten kunnen hebben, mits je goed leest

spoiler:

hoewel ik ook nog extra tijd verloren ben omdat ik even niet doorhad dat ik de stack achterstevoren aan het uitlezen was

[ElkeBxl]

Mijn oplossing in Rust voor dag 10.

spoiler:

Ik was die score voor de incomplete lines heel naief beginnen uitrekenen zodra er nog iets op de stack stond eens het parsen stopte, maar dan reken je natuurlijk ook een score uit voor de lijnen met een syntax error

[armageddon_2k1]

Dag 10 in Kotlin

Was lekker simpel
Ga het nog iets opschonen wellicht, maar vind het ook wel prima zo.

EDIT: en opgeschoond en wel

[ Voor 6% gewijzigd door armageddon_2k1 op 10-12-2021 09:17 ]

[Devilfish]

Een gemakkelijke vandaag, maar toch weer een halfuurtje bezig geweest.

(Dag 10 in C#)

[Hydra]

Day 10 in Kotlin

Geen moeilijke en een herhaling van eerdere challenges, maar ik vond deze wel weer erg leuk!

[ydderf]

Ik loop iets achter, maar Dag 9 in C# is gelukt. Dus het viel gisteravond niet mee om het topic door te lezen zonder de spoilers te openen. Maar ook dat is gelukt.
Deel twee was wel ff nadenken hoe dit te doen qua programmeren, maar ik denk wel een mooie oplossing gevonden te hebben. Alleen voor het zoeken naar naastgelegen posities moet ik nog een iets mooiers maken.
En aan het einde het resultaat berekenen heeft denk ik niet de schoonheidsprijs.

Vanavond maar eens naar dag 10 kijken.