Advent of Code 2021

[Diderikdm]

Python dag 10

Vond deze zelf wat pittiger. Dat kwam vooral door mezelf, want was eerst veel te complex bezig

spoiler:

met recursive substrings, bleek helemaal niet nodig als je vanaf de closing characters terugwerkt

[Hydra]

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.

Grappig dat je daarover begonnen bent trouwens, ik had die hele personal stats page nooit gezien

Heb tot nu toe voor iedere oplossing voor deel 2 nog een hogere ranking dan deel 1.

Vind het ook wel leuk dat je goed kan zien hoeveel tijd er zit tussen je completion van deel 1 en deel 2. Als je zo diep in die code zit, vliegt de tijd echt voorbij. Ik had bijvoorbeeld echt niet verwacht dat er vandaag tussen 1 en 2 nog 17 minuten zat. Voelde als 5.

[iThinkSo]

Janoz schreef op vrijdag 10 december 2021 @ 07:34:
[...]

spoiler:

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

Haha same

[KabouterSuper]

Wat een hel. 's Ochtends in het donker op een laptopje kloten met haakjes. Ik heb een compleet uur van mijn leven verspeeld door twee soorten haakjes door elkaar te halen bij de scoring. Bij de testinput maakte dat niet uit, bij mijn echte input wel. Uiteindelijk een hele groffe parser gebouwd om de boel te checken:

spoiler:

10000 keer (),{},<> en [] vervangen door ''

maar ook die gaf hetzelfde antwoord. Dus uiteindelijk eerst gedouched en toen bedacht dat het wel aan de scoring moest liggen. Deel 2 was toen wel heel gemakkelijk omdat ik al heel veel extra data beschikbaar had.

[iThinkSo]

Voor de rest een beetje een flauwe opdracht m.i.

Dit is iets wat iedereen met een informatica-achtergrond al honderd keer gezien heeft (ook in precies deze context vaak, dit is een schoolvoorbeeld van

spoiler:

een context-free grammar

), en dus zo kan uittypen maar volgens mij voor de wat meer "self-taught" mensen nog best wel lastig kan zijn.

[coop]

Dag 10 in Python

Lekker dagje vandaag.

[Varienaja]

iThinkSo schreef op vrijdag 10 december 2021 @ 08:55:

spoiler:

een context-free grammar

Ik zou eerder zeggen

spoiler:

Stack

.

[Hydra]

iThinkSo schreef op vrijdag 10 december 2021 @ 08:55:
Dit is iets wat iedereen met een informatica-achtergrond al honderd keer gezien heeft

En een van de doelen van AoC is juist ook om een breder publiek kennis te laten maken met deze concepten. Oftewel; een heel erg geslaagde opdracht

[TrailBlazer]

spoiler:

Wel handig om de lijst even te sorten voor je de middelste pakt. Verder niet moeilijk met een stack idd

[armageddon_2k1]

iThinkSo schreef op vrijdag 10 december 2021 @ 08:55:
Voor de rest een beetje een flauwe opdracht m.i.

Dit is iets wat iedereen met een informatica-achtergrond al honderd keer gezien heeft (ook in precies deze context vaak, dit is een schoolvoorbeeld van

spoiler:

een context-free grammar

), en dus zo kan uittypen maar volgens mij voor de wat meer "self-taught" mensen nog best wel lastig kan zijn.

Zo, tikkeltje arrogant.
Ik ben volledig self-taught en hij was vrij simpel. Niet alleen bij informatica leer je de skills om logica puzzels op te lossen hoor.

Edit: en zo moeilijk is context free grammar nou ook weer niet om te bevatten. Beetje hetzelfde als dat ik claim dat differentiaalvergelijkingen een eitje zijn voor mij maar voor zelfgeschoolde mensen per definitie moeilijker.

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

[Diderikdm]

armageddon_2k1 schreef op vrijdag 10 december 2021 @ 09:34:
[...]


Zo, lekker aan het gate keepen?
Ik ben volledig self-taught en hij was vrij simpel. Niet alleen bij informatica leer je de skills om logica puzzels op te lossen hoor.

Ook volledig self-taught hier. Ondanks dat veel van deze puzzels inderdaad met pure logica te kraken zijn snap ik iThinkSo ook wel. Als de techniek waarmee je deze puzzel oplost met de paplepel is ingegoten binnen een opleiding/elders kan je in theorie zo een oplossing uit je mouw schudden.

Ik zie dat ik door dit kennishiaat de puzzel op een andere manier heb opgelost dan

spoiler:

context-free grammar / stack

, echter vind ik het heel leerzaam om te zien hoe anderen dit hebben opgelost en zie ik deze les om in de toekomst te integreren in mijn aanpak van soortgelijke problemen.

[FrankMennink]

Dag 10 in Python

Beide delen in 1 keer. Ik heb een onderbuikgevoel dat er een corner case moet zijn voor de code waarbij de identificatie van incomplete of corrupt niet helemaal lekker loopt, maar ik kan m niet bedenken en de uitkomst is goed

[Singelaar]

armageddon_2k1 schreef op vrijdag 10 december 2021 @ 09:34:
[...]


Zo, tikkeltje arrogant.
Ik ben volledig self-taught en hij was vrij simpel. Niet alleen bij informatica leer je de skills om logica puzzels op te lossen hoor.

Ik ben ook self-taught. Het geeft mij juist zelf vertrouwen te zien dat ik dit soort dingen weet op te lossen die andere tijdens een studie doorgrond hebben. -> Maar ik ben misschien dan ook weer wat arrogant

Waar ik overigens altijd wel heel erg stuk op ga zijn opdrachten die recursie vragen. Heeft iemand een website met oefeningen waarbij ik daar eens wat over kan leren? Ik zou dat graag door krijgen.

[Tjmen]

armageddon_2k1 schreef op vrijdag 10 december 2021 @ 09:34:
[...]


Zo, tikkeltje arrogant.
Ik ben volledig self-taught en hij was vrij simpel. Niet alleen bij informatica leer je de skills om logica puzzels op te lossen hoor.

Ik geloof niet dat iThinkSo het arrogant bedoelt. De opdracht is 'simpel' als je het principe van een

spoiler:

Stack

kent. Ik ben ook self-taught en ben blij dat ik het concept

spoiler:

Stack

ben tegen gekomen tijdens het hobby-en. Zo niet, had ik waarschijnlijk veel meer moeite gehad met deze opdacht.

[ Voor 3% gewijzigd door Tjmen op 10-12-2021 09:48 . Reden: Spoilers ]

[Creepy]

https://github.com/CodeEn...er/aoc/aoc2021/Day10.java

spoiler:

Opgelost met een stack zoals een hoop anderen. Dan is de oplossing vrij simpel. Ik wens iedereen die parsers met regexen bouwt veel sterkte

Hydra schreef op vrijdag 10 december 2021 @ 09:28:
En een van de doelen van AoC is juist ook om een breder publiek kennis te laten maken met deze concepten. Oftewel; een heel erg geslaagde opdracht

Precies dit.

[ Voor 34% gewijzigd door Creepy op 10-12-2021 09:56 ]

[Hydra]

Singelaar schreef op vrijdag 10 december 2021 @ 09:45:
Waar ik overigens altijd wel heel erg stuk op ga zijn opdrachten die recursie vragen. Heeft iemand een website met oefeningen waarbij ik daar eens wat over kan leren? Ik zou dat graag door krijgen.

Wat mij opvalt is dat oefeningen voor recursie vaak met relatief complexe dingen beginnen, zoals Fibonacci etc., die vrij ver van je belevingswereld afliggen als beginner.

Begin eerst gewoon met iets als "maak een lijst van 0 tot en met 10", maar zonder loops te gebruiken. Een andere; reverse de String "Hello, World!" maar dan zonder loops. Want recursie is niks anders dan een loop crearen door functies zichzelf aan te laten roepen.

Als je dat lukt, ga dan voor iets dat wat moeilijker is: print van een directory alle files en subdirectors met files in een 'tree' output. Als je dat lukt; gefeliciteerd: je hebt een depth-first search gebouwd

[ Voor 5% gewijzigd door Hydra op 10-12-2021 10:01 ]

[Varienaja]

In other news
25137 / 21 = 1197
1197 / 21 = 57
57 / 21 = 2,7.. niet 3. WAAROM??

[Diderikdm]

Singelaar schreef op vrijdag 10 december 2021 @ 09:45:
[...]


Ik ben ook self-taught. Het geeft mij juist zelf vertrouwen te zien dat ik dit soort dingen weet op te lossen die andere tijdens een studie doorgrond hebben. -> Maar ik ben misschien dan ook weer wat arrogant

Waar ik overigens altijd wel heel erg stuk op ga zijn opdrachten die recursie vragen. Heeft iemand een website met oefeningen waarbij ik daar eens wat over kan leren? Ik zou dat graag door krijgen.

Recursie (heel platgeslagen):

je hebt een heel grote dataset met veel te veel info om in een keer (overzichtelijk) op te lossen (kan ook op andere manieren )

Stel je hebt een stamboom:

.................A
.................|
.....B-------C----------D
.....| ........ |........ .... |
E-----F...G---H .....I----J


Wat je met recursion kan doen is een functie schrijven:

Geef me alle waarden van x terug

Als je dan de functie aanroept voor x=A, kijg je [B,C,D] terug.

Vervolgens kan je dezelfde functie aanroepen voor x=B ([E,F]), x=C ([G, H]), x=D([I,J]), en zo kan je tot je maximale recursiediepte (meestal rond de 1000) door de diepte in.

Ofwel, je roept dezelfde functie telkens aan om dieper de stamboom in te duiken en steeds met een kleinere (gesprecialiseerdere) dataset hetzelfde te doen tot je iets vindt wat voor jouw probleem interessant is.

Stel in bovenstaande stamboom:

E = 1
F = 2
G = 3
H = 4
I = 5
J = 1

En de vraag is: van dataset A, vind alle kinderen die de waarde 1 hebben.

Dan kan je vanaf A naar B, C en E, en zo steeds verder de diepte in om uiteindelijk een waarde van 1 te vinden (E en J).

Vervolgens kan je in je recursive functie ook iets toevoegen als:

Als waarde == 1: voeg toe aan een lijst/dict/whatever buiten deze functie (of geef het terug aan de vorige iteratie((recursion_result = recusive(x)) en ga door met de volgende waarde voor x.

Vervolgens, als je alle kinderen van alle stamboom-members bent afgegaan, heb je een resultaat over alle waarden die 1 zijn (in dit geval 2)


Je kan ook bijvoorbeeld een getal zichzelf laten vermenigvuldigen totdat een bepaalde waarde is bereikt (dit hoeft niet recursief, maar het kan wel)


verder zijn er een veeltal sites te vinden met een goede uitleg (zoals https://www.geeksforgeeks.org/recursion/)

[Varienaja]

Quicksort is ook een mooi voorbeeld van recursie:

Stap A: lijst met 1 element ? klaar, anders neem element uit ongesorteerde lijst
Stap B: maak lijst van items kleiner en een lijst van items groter dan dit element
Stap C: doe Stap A nog eens voor de kleintjes en de groten

[Singelaar]

Hydra schreef op vrijdag 10 december 2021 @ 10:00:
[...]


Wat mij opvalt is dat oefeningen voor recursie vaak met relatief complexe dingen beginnen, zoals Fibonacci etc., die vrij ver van je belevingswereld afliggen als beginner.

Begin eerst gewoon met iets als "maak een lijst van 0 tot en met 10", maar zonder loops te gebruiken. Een andere; reverse de String "Hello, World!" maar dan zonder loops. Want recursie is niks anders dan een loop crearen door functies zichzelf aan te laten roepen.

Als je dat lukt, ga dan voor iets dat wat moeilijker is: print van een directory alle files en subdirectors met files in een 'tree' output. Als je dat lukt; gefeliciteerd: je hebt een depth-first search gebouwd

Dank je wel! Die zal ik eens oppakken.
Ik begrijp (best goed) het idee. Maar ik heb er te weinig mee gewerkt, dus zie ik niet goed waar ik het toe kan passen. En als ik het gebruik (dan zie ik dus echt geen andere oplossing ) dan kost het opstellen van de recursie me erg veel moeite.
Dus volgens mij moet ik gewoon wat meer oefening hebben, zodat het makkelijker uit mijn hoofd op het scherm komt.

[Hydra]

Singelaar schreef op vrijdag 10 december 2021 @ 10:13:
Dus volgens mij moet ik gewoon wat meer oefening hebben, zodat het makkelijker uit mijn hoofd op het scherm komt.

Oh, dat sowieso hoor. Het is vooral een kwestie van veel doen. Veel AoC doen maakt je ook gewoon beter in het herkennen van de oplossingsrichtingen.

[Remcoder]

En ook weer lekker vlot opgelost

Members only:

Alleen zichtbaar voor ingelogde gebruikers. Inloggen

spoiler:

Alleen de fout gemaakt door voor deel 2 geen longs maar ints te gebruiken. Mijn antwoord was te laag...

[Hydra]

Remcoder schreef op vrijdag 10 december 2021 @ 10:14:

spoiler:

Alleen de fout gemaakt door voor deel 2 geen longs maar ints te gebruiken. Mijn antwoord was te laag...

spoiler:

Ja, dat is ook wel een typische AoC gotcha. Als je ergens vermenigvuldigingen doet, gewoon altijd longs gebruiken. Dit wordt vrijwel altijd met opzet gedaan om je te dwingen 64bits ints te gebruiken in je antwoord.

[Remcoder]

Hydra schreef op vrijdag 10 december 2021 @ 10:30:
[...]

spoiler:

Ja, dat is ook wel een typische AoC gotcha. Als je ergens vermenigvuldigingen doet, gewoon altijd longs gebruiken. Dit wordt vrijwel altijd met opzet gedaan om je te dwingen 64bits ints te gebruiken in je antwoord.

spoiler:

Ja, ik ben gewoon eigenwijs en begin standaard met een int.

[gedonie]

Dag 10 in Java. Was vandaag een makkelijke opdracht.

[KabouterSuper]

De "I never like stacks, functions and recursion anyway"-solution in python:

spoiler:

import io
from functools import reduce
file="C:\\Users\\martenk\\Desktop\\Wiskunde\\Advent of Code\\2021\\day 10 input.txt"
dbrackets={'(': 1, ')': 3, '[': 2, ']': 57, '{': 3, '}': 1197, '<': 4, '>': 25137}
ascore=[]
for dd in [d for d in io.open(file, "r", encoding="utf-8").read().split('\n') if d!='']:
~prevlen=len(dd)+1
~while prevlen>len(dd):
~~prevlen=len(dd)
~~~for b in range(0,len(dbrackets),2):
~~~~dd=dd.replace(''.join(dbrackets.keys())[b:b+2],'')
~try:
~~ascore.append(('error',reduce(lambda a, b: 5*a+b,[dbrackets[d] for d in dd[next(i for i,c in enumerate(dd) if c in ''.join(dbrackets.keys())[1::2])]])))
~except StopIteration:
~~ascore.append(('incomplete',reduce(lambda a, b: 5*a+b,[dbrackets[d] for d in dd[::-1]])))
print(sum([f[1] for f in ascore if f[0]=='error']))
print(sorted([f[1] for f in ascore if f[0]=='incomplete'])[int((len([f[1] for f in ascore if f[0]=='incomplete'])-1)/2)])

Met excuus dat de spoilertags de indents vernachelen, dus dat ik van de indents tildes heb gemaakt.
Uitleg:

spoiler:

Ik vervang eerst alle (),[],<>,{} totdat het niet meer kan
Dan zoek ik de index van een rechterhaakje.Rrechterhaakjes=''.join(dbrackets.keys())[1::2]), de index is next(i for i,c in enumerate(dd) if c in ....)
~krijgt deze iets terug, dan tag ik de regel met error en pass ik dd[index] naar een score functie reduce(lambda a, b: 5*a+b,...) wetende dat ik maar 1 karakter ernaar toe pass.
~krijg ik niets terug (StopIteration exception), dan tag ik de regel met incomplete en pass de opgeschoonde regel naar dezelfde score functie.
Tenslotte veeg ik de errors en incompletes bij elkaar (de eerste met een sum, van de tweede pak ik de middelste).

[ Voor 28% gewijzigd door KabouterSuper op 10-12-2021 11:18 ]

[Cranzai]

In het begin even wat moeite om nou te snappen wat bedoeld wordt met een incomplete line, uiteindelijk maar gewoon begonnen te pielen met mijn bedachte strategie en toen rolde ook een criterion er uit voor het bepalen van een incomplete lijn.

Deel A en deel B dus eigenlijk met dezelfde code kunnen doen met een ander "sausje" output processing.

https://github.com/Cranza...021/day10/python/day10.py

[DataGhost]

Okee daar zijn er weer een paar, in een soort van oplopende moeilijkheidsgraad.
Up 1, bzipped
Up 2, bzipped
Up 3, bzipped
Up 4, bzipped - deze conflicteert in principe op een subtiele manier met de probleemomschrijving, maar ik vond het wel een leuke extra testcase die makkelijk op te lossen is. Deze is te doen zonder de eventuele aanpassingen die voor up3 nodig zijn.
Antwoorden (denk ik)

[ Voor 5% gewijzigd door DataGhost op 10-12-2021 11:33 ]

[armageddon_2k1]

@Singelaar Ik kan Functional Programming Principles in Scala aanraden op Coursera. Het is even wennen maar daar leerde ik recursie (en immutable persistent datastructures) pas echt goed.

Voor mij is het ook echt wennen geweest en ik kan het nu redelijk, maar gebruik het nog niet altijd. Het is namelijk iets anders dan hoe ik normaal denk. Grofgezegd denk normaal na over de algemene oplossing en los daarna de edge cases op. Met een recursieve functie denk ik eerst aan de edge cases (lijst is leeg, lijst heeft maar 1 element, etc etc) en bouw vanuit daar weer op.

En language syntax helpt enorm voor me. Match/when clauses is iets waar Scala in uitblinkt en dit soort dingen heel veel makkelijker worden.

[EfBe]

Leuke opdracht, wel veel typen
https://github.com/FransB...src/AoC2021.Code/Day10.cs

spoiler:

stackbased parser gebouwd voor dit taaltje, wat bij puzzle 2 goed van pas kwam

armageddon_2k1 schreef op vrijdag 10 december 2021 @ 09:34:
Zo, tikkeltje arrogant.
Ik ben volledig self-taught en hij was vrij simpel. Niet alleen bij informatica leer je de skills om logica puzzels op te lossen hoor.

Edit: en zo moeilijk is context free grammar nou ook weer niet om te bevatten. Beetje hetzelfde als dat ik claim dat differentiaalvergelijkingen een eitje zijn voor mij maar voor zelfgeschoolde mensen per definitie moeilijker.

Nee, maar als je nooit een

spoiler:

stackbased parser, of een LR(n) parser generator

gemaakt hebt, of ervan gehoord hebt, dan ga je niet 1 2 3 in die hoek zoeken en is het al snel lastig.

[ Voor 61% gewijzigd door EfBe op 10-12-2021 11:34 ]

[armageddon_2k1]

@EfBe

spoiler:

Allemaal nooit gedaan, en een stack was het eerste wat in me opkwam te gebruiken. Dus tja. Het is ook geen parser probleem, ook al impliceert de opdracht het, maar gewoon een “je moet de laatste bijhouden”-probleem. Dat een parser toevallig de superset is van dat laatste probleem maakt niet dat je toevallig parsers gestudeerd moet hebben om efficiënt tot een oplossing te komen.

Het probleem is absoluut niet uniek voor parsers. En impliceren dat je toevallig Informatica gestudeerd moet hebben om het niet lastig te krijgen voor DIT probleem is vrij kortzichtig.

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

[Diderikdm]

armageddon_2k1 schreef op vrijdag 10 december 2021 @ 11:38:
@EfBe

spoiler:

Allemaal nooit gedaan, en een stack was het eerste wat in me opkwam te gebruiken. Dus tja. Het is ook geen parser probleem, ook al impliceert de opdracht het, maar gewoon een “je moet de laatste bijhouden”-probleem. Dat een parser toevallig de superset is van dat laatste probleem maakt niet dat je toevallig parsers gestudeerd moet hebben om efficiënt tot een oplossing te komen.

Het probleem is absoluut niet uniek voor parsers. En impliceren dat je toevallig Informatica gestudeerd moet hebben om het niet lastig te krijgen voor DIT probleem is vrij kortzichtig.

spoiler:

Zoals ik het zie gaat het toch om:

* Dit probleem is makkelijk als je informatica hebt gestudeerd

en niet om:

* Dit probleem is per definitie moeilijk als je geen informatica hebt gestudeerd

?

[armageddon_2k1]

Diderikdm schreef op vrijdag 10 december 2021 @ 11:46:
[...]

spoiler:

Zoals ik het zie gaat het toch om:

* Dit probleem is makkelijk als je informatica hebt gestudeerd

en niet om:

* Dit probleem is per definitie moeilijk als je geen informatica hebt gestudeerd

?

Lees de eerste reactie maar waar ik op reageerde. Als self-taught zou het moeilijker zijn omdat je kennis mist. Dus dat laatste.

Maar ik ga er al teveel op in en lees er misschien teveel in. Eigenlijk is het een non issue en dit topic moet gewoon lekker over oplossingen praten gaan

[Cranzai]

armageddon_2k1 schreef op vrijdag 10 december 2021 @ 11:38:
@EfBe

spoiler:

Allemaal nooit gedaan, en een stack was het eerste wat in me opkwam te gebruiken. Dus tja. Het is ook geen parser probleem, ook al impliceert de opdracht het, maar gewoon een “je moet de laatste bijhouden”-probleem. Dat een parser toevallig de superset is van dat laatste probleem maakt niet dat je toevallig parsers gestudeerd moet hebben om efficiënt tot een oplossing te komen.

Het probleem is absoluut niet uniek voor parsers. En impliceren dat je toevallig Informatica gestudeerd moet hebben om het niet lastig te krijgen voor DIT probleem is vrij kortzichtig.

spoiler:

Met mijn ochtendkop kon ik in ieder geval niet bedenken dat het een "je moet de laatste bijhouden"-probleem is, voorkennis van stacks had er waarschijnlijk toe geleid dat ik die gebruikt had ipv mijn recursieve oplossing.

[armageddon_2k1]

Cranzai schreef op vrijdag 10 december 2021 @ 11:50:
[...]

spoiler:

Met mijn ochtendkop kon ik in ieder geval niet bedenken dat het een "je moet de laatste bijhouden"-probleem is, voorkennis van stacks had er waarschijnlijk toe geleid dat ik die gebruikt had ipv mijn recursieve oplossing.

Je hebt een oplossing toch?
Én je hebt weer iets geleerd en daar gaat het uiteindelijk om.

[Diderikdm]

armageddon_2k1 schreef op vrijdag 10 december 2021 @ 11:49:
[...]


Lees de eerste reactie maar waar ik op reageerde. Als self-taught zou het moeilijker zijn omdat je kennis mist. Dus dat laatste.

Maar ik ga er al teveel op in. Eigenlijk is het een non issue en dit topic moet gewoon lekker over oplossingen praten gaan

Yes precies, ik zie:

volgens mij voor de wat meer "self-taught" mensen nog best wel lastig kan zijn.

Als optioneel, en ik denk dat daar ook een punt in zit. Het kan lastiger zijn als je bepaalde technieken nog niet kent/onder de knie hebt.

Eigenlijk is het een non issue en dit topic moet gewoon lekker over oplossingen praten gaan

Eens

[DataGhost]

Dat is allemaal gewoon inzicht wat je moet hebben en dat krijg je alleen maar door veel van dit soort problemen op te lossen. Je kan nog zoveel informatica studeren en alle verschillende datastructuren en hun beoogde gebruik in theorie langs zien komen, als je er in de praktijk nooit iets mee doet zal je er ook dan niet aan denken. Op dezelfde manier heb je als self-taught programmeur dezelfde documentatie tot je beschikking, inclusief alle datastructuren die bij je gebruikte programmeertaal meekomen en de looptijden van de operaties daarop. Alleen in de praktijk gebruik je ze gewoon niet zo vaak, dus dan blijft de parate kennis ook achter. Net zo hard bij informatici.
Dit probleem is op meerdere manieren in lineaire tijd op te lossen (ook zonder recursie) en daarbij is de nu veelvoudig in spoilers geroepen datastructuur niet de enige mogelijkheid waarmee dat kan. Edit: zo heeft @YoToP dat net mooi gedaan hieronder andere datastructuur maar het komt uiteindelijk op hetzelfde neer.

[ Voor 30% gewijzigd door DataGhost op 10-12-2021 11:58 ]

[EfBe]

@Diderikdm snapt het Met dit soort tests is het net als met domme interview vragen: als je het ziet hoe het moet, omdat je het al eerder gezien hebt, of het algoritme kent, dan is het uitprogrammeren en klaar, wellicht wat nadenken, maar dat is het wel. Wanneer je het nog nooit gezien hebt en je moet het algoritme verzinnen 'on-the-spot', gaat het geheid tijd kosten en wellicht veel. En dat is toch wel wat jammer, want mensen die toevallig geen CS degree hebben en/of veel met bepaalde algoritmen bezig zijn, zullen het lastiger hebben dan anderen, die die kennis paraat hebben.

Maar goed, de mensen die vroeg opstaan 's ochtends hebben ook een voordeel tov nerds zoals ik die om 10 uur eens gaan kijken wat de puzzle van de dag is dus, er is altijd wel wat

[Janoz]

Singelaar schreef op vrijdag 10 december 2021 @ 09:45:
Waar ik overigens altijd wel heel erg stuk op ga zijn opdrachten die recursie vragen.

De enige knop die in je hoofd om moet is dat je tijdens het schrijven van de functie er al vanuit mag gaan dat hij af is en werkt (de recursie). Daarna moet je zorgen dat hij in ieder geval ook een keer onafhankelijk het antwoord moet weten (stop conditie).

Geen idee of ik het duidelijker kan maken met een voorbeeld, maar ik wil het toch eens proberen

Stel je wilt weten hoe vaak a in b past (de standaard 'deel' operator). Je maakt een functie:

code:

int deel(int a,int b)

Hoe vaak past a in b? Geen idee. Maar als we 1x a uit b halen dan weten we dat hij er in ieder geval 1x minder in past:

code:

int deel(int a, int b) {
  return 1 + deel(a, b-a);
}

Dit stopt natuurlijk nooit omdat er toch een keer moet komen dat we het antwoord helemaal zelf weten. Laten we daarvoor het meest simpele geval pakken. Als b kleiner is dan a, dan past het er 0x in.

code:

int deel(int a, int b) {
  if (b < a) return 0;
  return 1 + deel(a, b-a);
}

Klaar

Het voordeel van recursie is dat je je probleem makkelijker kunt compartimenteren. Je bent echt een deel probleempje aan het oplossen.

[YoToP]

Leuke puzzel! minder frustratie dan gisteren maar wel een uitdaging.

spoiler:

https://github.com/YoToP/AoC-2021/blob/main/10/p1.py
https://github.com/YoToP/AoC-2021/blob/main/10/p2.py

@DataGhost
alle datasets totaal(via unittest) binnen 5 sec. Bedankt voor de extra puzzels

[DataGhost]

Janoz schreef op vrijdag 10 december 2021 @ 11:53:
[...]

De enige knop die in je hoofd om moet is dat je tijdens het schrijven van de functie er al vanuit mag gaan dat hij af is en werkt (de recursie). Daarna moet je zorgen dat hij in ieder geval ook een keer onafhankelijk het antwoord moet weten (stop conditie).

Wat hierbij ook heel erg kan helpen om die knop om te zetten, is de code eerst gewoon in normaal Nederlands/Engels/whatever te schrijven zodat je eerst het hele concept duidelijk hebt, alvorens het te vertalen naar programmacode.

[P_Tingen]

Janoz schreef op vrijdag 10 december 2021 @ 11:53:
[...]

De enige knop die in je hoofd om moet is dat je tijdens het schrijven van de functie er al vanuit mag gaan dat hij af is en werkt (de recursie). Daarna moet je zorgen dat hij in ieder geval ook een keer onafhankelijk het antwoord moet weten (stop conditie).

Geen idee of ik het duidelijker kan maken met een voorbeeld, maar ik wil het toch eens proberen

Stel je wilt weten hoe vaak a in b past (de standaard 'deel' operator). Je maakt een functie:

code:

int deel(int a,int b)

Hoe vaak past a in b? Geen idee. Maar als we 1x a uit b halen dan weten we dat hij er in ieder geval 1x minder in past:

code:

int deel(int a, int b) {
  return 1 + deel(a, b-a);
}

Dit stopt natuurlijk nooit omdat er toch een keer moet komen dat we het antwoord helemaal zelf weten. Laten we daarvoor het meest simpele geval pakken. Als b kleiner is dan a, dan past het er 0x in.

code:

int deel(int a, int b) {
  if (b < a) return 0;
  return 1 + deel(a, b-a);
}

Klaar

Het voordeel van recursie is dat je je probleem makkelijker kunt compartimenteren. Je bent echt een deel probleempje aan het oplossen.

Mooie uitleg!

[armageddon_2k1]

EfBe schreef op vrijdag 10 december 2021 @ 11:52:…Wanneer je het nog nooit gezien hebt en je moet het algoritme verzinnen 'on-the-spot', gaat het geheid tijd kosten en wellicht veel. En dat is toch wel wat jammer, want mensen die toevallig geen CS degree hebben en/of veel met bepaalde algoritmen bezig zijn, zullen het lastiger hebben dan anderen, die die kennis paraat hebben.

Maar ik vind het juist leuk om een algoritme te bedenken dat werkt, daarna naar anderen te kijken en erachter te komen wat de algemene geaccepteerde oplossing is. Dan kan ik leren begrijpen waarom die nou juist beter is en ik begrijp het domein en de oplossing al waardoor het leren van nieuwe theorie makkelijk is vanwege de context die je al hebt.

Maar mijn vermoeden is dat iedereen wat anders zoekt in de uitdagingen

[ Voor 5% gewijzigd door armageddon_2k1 op 10-12-2021 12:33 ]

[MueR]

Zo, ook weer door dagje 10 heen. Deze was best makkelijk eigenlijk..

Members only:

Alleen zichtbaar voor ingelogde gebruikers. Inloggen

[MueR]

Creepy schreef op vrijdag 10 december 2021 @ 09:48:

spoiler:

Opgelost met een stack zoals een hoop anderen. Dan is de oplossing vrij simpel. Ik wens iedereen die parsers met regexen bouwt veel sterkte

spoiler:

Some people, when confronted with a problem, think "I know, I'll use regular expressions." Now they have two problems.

[KabouterSuper]

DataGhost schreef op vrijdag 10 december 2021 @ 11:17:
Okee daar zijn er weer een paar, in een soort van oplopende moeilijkheidsgraad.
Up 1, bzipped
Up 2, bzipped
Up 3, bzipped
Up 4, bzipped - deze conflicteert in principe op een subtiele manier met de probleemomschrijving, maar ik vond het wel een leuke extra testcase die makkelijk op te lossen is. Deze is te doen zonder de eventuele aanpassingen die voor up3 nodig zijn.
Antwoorden (denk ik)

Mooi gedaan weer. Alles hetzelfde in luttele seconden. De up4 gaf bij mij eerst een foutmelding, dus ik weet nu ook hoe ik een reduce een initial value moet geven.

[Creepy]

MueR schreef op vrijdag 10 december 2021 @ 12:44:
[...]

spoiler:

Some people, when confronted with a problem, think "I know, I'll use regular expressions." Now they have two problems.

Bekijk mijn signature nog eens

[DataGhost]

KabouterSuper schreef op vrijdag 10 december 2021 @ 12:54:
[...]

Mooi gedaan weer. Alles hetzelfde in luttele seconden. De up4 gaf bij mij eerst een foutmelding, dus ik weet nu ook hoe ik een reduce een initial value moet geven.

Hm, heb je je code aangepast ten opzichte van je eerdere post? Wat vind je "luttele" seconden? Up2 is nu namelijk al een minuut bezig zonder uitkomst
Edit: na een drie kwartier nog steeds bezig. Het moet bijna wel andere code zijn dan, wat jij draait

[ Voor 11% gewijzigd door DataGhost op 10-12-2021 13:53 ]

[MaNDaRK]

Pffff, ik kwam er dus niet meer uit in C#, dus maar terug gegaan naar Python

Ik denk een leesbare oplossing voor part 1 & 2.

[MueR]

DataGhost schreef op vrijdag 10 december 2021 @ 11:17:
Okee daar zijn er weer een paar, in een soort van oplopende moeilijkheidsgraad.
Up 1, bzipped
Up 2, bzipped
Up 3, bzipped
Up 4, bzipped - deze conflicteert in principe op een subtiele manier met de probleemomschrijving, maar ik vond het wel een leuke extra testcase die makkelijk op te lossen is. Deze is te doen zonder de eventuele aanpassingen die voor up3 nodig zijn.
Antwoorden (denk ik)

Poeh, dan wordt ie wel ineens wat traag van ~6ms naar 5 seconden. Maar nog steeds not bad.

[ydderf]

Dag 10 in C#
Ik moest eerst even goed kijken wat nu eigenlijk het verschil tussen een incomplete regel en een corrupte regel was.
Daarna voor de eerste keer dit jaar toch maar geprobeerd om er iets van een Regex in te gooien.

[Hydra]

Creepy schreef op vrijdag 10 december 2021 @ 12:56:
Bekijk mijn signature nog eens

Kevlin Henney. Live gezien op een Keynote ooit en groot fan sindsdien.

[KabouterSuper]

DataGhost schreef op vrijdag 10 december 2021 @ 13:01:
[...]

Hm, heb je je code aangepast ten opzichte van je eerdere post? Wat vind je "luttele" seconden? Up2 is nu namelijk al een minuut bezig zonder uitkomst
Edit: na een drie kwartier nog steeds bezig. Het moet bijna wel andere code zijn dan, wat jij draait

Scherpe opmerking. De code die ik gepost had is inderdaad niet helemaal de code dit ik gebruikt heb voor jouw datasets. Ik was vanochtend begonnen met een stack, maar die gaf een foute uitkomst. Toen gefrusteerd deze oplossing zonder stacks gebouwd (de replace), maar die gaf dezelfde uitkomst. Vervolgens kwam ik erachter dat ik wat haakjes had verwisseld, dus dat was de reden dat mijn score fout was.
Maar om door jouw testsets heen te komen had ik een oorspronkelijk stukje code weer tevoorschijn getoverd (aangezien de replace veel te traag was voor jouw datasets).

spoiler:

This should do the trick. In plaats van de 5 regels vanaf prevlen=..., dit stukje erin zetten:
stack=[]
leftbrackets=''.join(dbrackets.keys())[0::2]
rightbrackets=''.join(dbrackets.keys())[1::2]
for d in dd:
stack.append(d)
if d in (rightbrackets):
if rightbrackets.index(d)==leftbrackets.index(stack[-2]):
stack.pop()
stack.pop()
else:
break
dd=''.join(stack)

Ik draai verder pypy (op windows) voor de tijdsintensieve programmaatjes, dat scheelt vaak een factor 8 qua snelheid. Maar ik heb numpy op pypy nog niet aan de praat gekregen, dus ik kan nog niet alles op pypy draaien.

[zwippie]

DataGhost schreef op vrijdag 10 december 2021 @ 11:17:
Okee daar zijn er weer een paar, in een soort van oplopende moeilijkheidsgraad.
Up 1, bzipped
Up 2, bzipped
Up 3, bzipped
Up 4, bzipped - deze conflicteert in principe op een subtiele manier met de probleemomschrijving, maar ik vond het wel een leuke extra testcase die makkelijk op te lossen is. Deze is te doen zonder de eventuele aanpassingen die voor up3 nodig zijn.
Antwoorden (denk ik)

Wellicht opvallend (of juist niet): al je input files draaien bij mij voor zowel dag 1 als 2 allemaal in precies 1.2s (per stuk).

spoiler:

Voor up4 moest ik een case toevoegen voor `:valid` input. Die moest dan wel een nul score krijgen om dezelfde uitvoer als jij te retourneren.

[coop]

Hier geen aanpassingen hoeven doen en alle 4 de ups van @DataGhost werken, en geven dezelfde antwoorden als hij krijgt. Up 1 in ~1s voor zowel A als B, voor 2,3,4 is A ~1s en B ~1.6s. Ter vergelijking, mijn input voor A duurt 1 ms en B duurt 1.7ms.

[DataGhost]

zwippie schreef op vrijdag 10 december 2021 @ 15:45:
[...]

Wellicht opvallend (of juist niet): al je input files draaien bij mij voor zowel dag 1 als 2 allemaal in precies 1.2s (per stuk).

spoiler:

Voor up4 moest ik een case toevoegen voor `:valid` input. Die moest dan wel een nul score krijgen om dezelfde uitvoer als jij te retourneren.

Alle inputs zijn even groot, dus als je algoritme lineair is en de rekentijd per stap voor beide delen ongeveer gelijk is, zal het ongeveer even lang duren.

[iThinkSo]

armageddon_2k1 schreef op vrijdag 10 december 2021 @ 09:34:
[...]


Zo, tikkeltje arrogant.
Ik ben volledig self-taught en hij was vrij simpel. Niet alleen bij informatica leer je de skills om logica puzzels op te lossen hoor.

Edit: en zo moeilijk is context free grammar nou ook weer niet om te bevatten. Beetje hetzelfde als dat ik claim dat differentiaalvergelijkingen een eitje zijn voor mij maar voor zelfgeschoolde mensen per definitie moeilijker.

spoiler:

Sorry, was zo niet bedoeld. Wat ik bedoelde was dat dit voorbeeld (of met 1 soort haakje) altijd het eerste voorbeeld is een taal die niet regulier is maar wel context-vrij. Bij de meeste andere puzzels zit er nog een sausje omheen dat het niet altijd direct duidelijk is wat nou de juiste oplossing is, wat hier niet gedaan is. Dat was waar ik op doelde.

[Varienaja]

DataGhost schreef op vrijdag 10 december 2021 @ 11:17:
Okee daar zijn er weer een paar, in een soort van oplopende moeilijkheidsgraad.

Alle inputs duren bij mij ongeveer 500ms. De vierde input is vuil hoor.

[zwippie]

DataGhost schreef op vrijdag 10 december 2021 @ 15:55:
[...]

Alle inputs zijn even groot, dus als je algoritme lineair is en de rekentijd per stap voor beide delen ongeveer gelijk is, zal het ongeveer even lang duren.

Dat is het inderdaad. Ik zie pas net dat ze even groot zijn.

[KabouterSuper]

Varienaja schreef op vrijdag 10 december 2021 @ 15:59:
[...]

Alle inputs duren bij mij ongeveer 500ms. De vierde input is vuil hoor.

Ik heb inmiddels weer recursie- en stackvrije oplossing. Om een stack te vervangen door een string moet je wel een paar trucs uithalen, omdat het te duur is om bij elk teken een stringmanipulatie te doen. Maar met een slimme pointer kom je een eind. Mocht je interesse hebben, laat het even weten. Draaitijd is overigens een seconde of 10 per input van @DataGhost, dus veul langzamer dan @Varienaja

[ Voor 3% gewijzigd door KabouterSuper op 10-12-2021 16:17 ]

[Dricus]

Dag 10 in Clojure

Veel te lang mee bezig geweest. Totale mental block. Dit probleem heb ik al minstens een keer of 5 eerder opgelost, maar ik kon gewoon niet op het algoritme komen.

Na deel 1 was deel 2 gelukkig vrij makkelijk toe te voegen.

[armageddon_2k1]

Even wat anders en een beetje spuit 11: Year 2015 in Kotlin vandaag afgemaakt!

Was er deze zomer mee begonnen, vastgelopen op Dag 22, laatst een ingeving en afgemaakt.

[Kazu]

spoiler:

Classic stack usecase, inderdaad. Ook wel lekker, een dagje eentje die je er zo uit klopt

M'n vriendin heeft er ook lucht van gekregen, en die wil sinds 2 dagen ook meekijken. Alleen dat zorgt ervoor dat ik er alleen aan kan werken als we allebei tijd hebben. Wat er ongeveer op neerkomt dat ik 's ochtends bij het ontbijt deel 1 eruit kan kloppen, en dan richting de avond pas deel 2. Dus dat zorgt wel voor een impact op m'n leaderbord score

DataGhost schreef op vrijdag 10 december 2021 @ 11:17:
Okee daar zijn er weer een paar, in een soort van oplopende moeilijkheidsgraad.
Up 1, bzipped
Up 2, bzipped
Up 3, bzipped
Up 4, bzipped - deze conflicteert in principe op een subtiele manier met de probleemomschrijving, maar ik vond het wel een leuke extra testcase die makkelijk op te lossen is. Deze is te doen zonder de eventuele aanpassingen die voor up3 nodig zijn.
Antwoorden (denk ik)

Ik heb even m'n input reader moeten aanpassen, omdat Go's bufio.Scanner standaard een token size heeft van 64k per line, wat duidelijk niet genoeg is

spoiler:

1 en 2 allebei correct opgelost in 650 ms. Vanaf 3 heb ik int64 nodig, en dan moet ik een custom sort implementeren, en daar heb ik nu ff geen zin in

[ShitHappens]

Zo, be ook door dag 10 heen Eigenlijk best goed op eigen houtje gelukt, behalve dat ik van hier de tip heb opgepikt

spoiler:

om afgesloten paren eerst weg te filteren, alvorens het illegale karakter te zoeken

.

Maar hoewel part1 in 19ms gaat en part2 in 4ms, loopt 'ie knap vast al op up1 dus zal de rest maar niet doen Vind 't mooi zo

[ Voor 22% gewijzigd door ShitHappens op 10-12-2021 19:43 ]

[martyw]

Was ook eerst in de recursie gedoken, toen nog even in regexes afgedwaald, maar uiteindelijk zoals velen ook op de stack uitgekomen
https://github.com/martyw/AOC2021/blob/main/day10.py

[DataGhost]

Kazu schreef op vrijdag 10 december 2021 @ 18:04:

spoiler:

Classic stack usecase, inderdaad. Ook wel lekker, een dagje eentje die je er zo uit klopt

M'n vriendin heeft er ook lucht van gekregen, en die wil sinds 2 dagen ook meekijken. Alleen dat zorgt ervoor dat ik er alleen aan kan werken als we allebei tijd hebben. Wat er ongeveer op neerkomt dat ik 's ochtends bij het ontbijt deel 1 eruit kan kloppen, en dan richting de avond pas deel 2. Dus dat zorgt wel voor een impact op m'n leaderbord score


[...]

Ik heb even m'n input reader moeten aanpassen, omdat Go's bufio.Scanner standaard een token size heeft van 64k per line, wat duidelijk niet genoeg is

spoiler:

1 en 2 allebei correct opgelost in 650 ms. Vanaf 3 heb ik int64 nodig, en dan moet ik een custom sort implementeren, en daar heb ik nu ff geen zin in

spoiler:

Ik hoop eigenlijk dat je ondertussen standaard al int64 gebruikt. Voor up3 zijn die in ieder geval te klein, daar heb ik op gelet

[martyw]

DataGhost schreef op vrijdag 10 december 2021 @ 20:58:
[...]

spoiler:

Ik hoop eigenlijk dat je ondertussen standaard al int64 gebruikt. Voor up3 zijn die in ieder geval te klein, daar heb ik op gelet

Heb jouw tests ff gedraaid, ik denk dat je antwoorden kloppen

code:

martyw@zijn-Corei5-11500:~/code/AOC2021$ ./day10.py -f aoc-2021-day10-up1.txt 
26448
14841
*** Run time: 1634 ms
martyw@zijn-Corei5-11500:~/code/AOC2021$ ./day10.py -f aoc-2021-day10-up2.txt 
51474
15282
*** Run time: 1583 ms
martyw@zijn-Corei5-11500:~/code/AOC2021$ ./day10.py -f aoc-2021-day10-up3.txt 
26340
217388346164004118353258362
*** Run time: 1589 ms
martyw@zijn-Corei5-11500:~/code/AOC2021$ ./day10.py -f aoc-2021-day10-up4.txt 
1314
187232
*** Run time: 1655 ms

[ Voor 4% gewijzigd door martyw op 10-12-2021 21:07 ]

[Kazu]

DataGhost schreef op vrijdag 10 december 2021 @ 20:58:
[...]

spoiler:

Ik hoop eigenlijk dat je ondertussen standaard al int64 gebruikt. Voor up3 zijn die in ieder geval te klein, daar heb ik op gelet

spoiler:

Nah, net als iemand anders ook al zei, ben ik ook eigenwijs en gebruik ik int totdat ik het vermoeden heb dat ik richting int64 moet. Een aantal native functies in Go hebben geen support voor int64 (zoals de sort package), dus om mijzelf de moeite te sparen probeer ik het eerst met int32. Tot nu toe ben ik er nog niet echt door gepakt, gelukkig

[DataGhost]

Kazu schreef op vrijdag 10 december 2021 @ 21:19:
[...]

spoiler:

Nah, net als iemand anders ook al zei, ben ik ook eigenwijs en gebruik ik int totdat ik het vermoeden heb dat ik richting int64 moet. Een aantal native functies in Go hebben geen support voor int64 (zoals de sort package), dus om mijzelf de moeite te sparen probeer ik het eerst met int32. Tot nu toe ben ik er nog niet echt door gepakt, gelukkig

Ja ik heb ooit een beetje met Go gedaan en dat was een van de eerste dingen waar ik me over verbaasde. Gelukkig ben ik er ook nog niet echt door gepakt! Door Go dus brrrr....

[TrailBlazer]

spoiler:

Ik las op reddit iemand de input meteen had vervangen door aAbBcCdD omdat hij gek werd van zijn IDE die er elke keer paartjes van maakte. Kan je wel mooi kunnen vergelijken met char.upper() oid
Ik heb er ook nog naar gekeken of de ascii waarde van de paartjes misschien maar 1 verschilden maar helaas.

[Soultaker]

DataGhost schreef op vrijdag 10 december 2021 @ 11:17:
Okee daar zijn er weer een paar, in een soort van oplopende moeilijkheidsgraad.
Up 4, bzipped - deze conflicteert in principe op een subtiele manier met de probleemomschrijving, maar ik vond het wel een leuke extra testcase die makkelijk op te lossen is.

Wat was de afwijking nu precies? Het lijkt erop dat er 4 incomplete strings in zitten, maar dan is het antwoord voor deel 2 ongedefinieerd. Misschien mis ik wat.

[P_Tingen]

Ik doe ook meestal eerst met gewone integers, dat zit in mijn shortcuts en is in de dagelijkse praktijk in >99% van de gevallen afdoende. Als ik met een opgave tegen een grens aan loop, is het ook binnen een minuut gefixt: zoek-en-vervang INTEGER door INT64 en door maar weer

[Dricus]

Soultaker schreef op vrijdag 10 december 2021 @ 22:49:
[...]

Wat was de afwijking nu precies? Het lijkt erop dat er 4 incomplete strings in zitten, maar dan is het antwoord voor deel 2 ongedefinieerd. Misschien mis ik wat.

spoiler:

Een regel waarin én geen fouten zitten, én geen autocompletion nodig is.

[martyw]

Dricus schreef op vrijdag 10 december 2021 @ 23:17:
[...]

spoiler:

Een regel waarin én geen fouten zitten, én geen autocompletion nodig is.

spoiler:

Dan levert je som functie toch gewoon 0 over de de lege string?

[DataGhost]

martyw schreef op vrijdag 10 december 2021 @ 23:46:
[...]

spoiler:

Dan levert je som functie toch gewoon 0 over de de lege string?

spoiler:

Sommige mensen returnen 0 bij een corrupted line en als je die eruit filtert gaat de bepaling van het midden opeens mis bij een correcte line met score 0. Leeg is 'ie niet trouwens, hij is gewoon syntactisch correct.

spoiler:

Mijn solveInstance(line) wordt namelijk voor elke line apart aangeroepen, de resultaten worden in een lijst verzameld, die wordt door transform(vals) gehaald en dan komt het antwoord eruit rollen. Dus het hangt af van de structuur van je oplossing. Als je gewoon alles in een loopje binnen dezelfde functie doet en elk resultaat direct in de respectievelijke resultaat-lijsten stopt heb je dat probleem niet inderdaad.

Members only:

Alleen zichtbaar voor ingelogde gebruikers. Inloggen

[ Voor 43% gewijzigd door DataGhost op 10-12-2021 23:58 ]

[martyw]

DataGhost schreef op vrijdag 10 december 2021 @ 23:49:
[...]

spoiler:

Sommige mensen returnen 0 bij een corrupted line en als je die eruit filtert gaat de bepaling van het midden opeens mis bij een correcte line met score 0.

Tja, dat is een gevaarlijke praktijk, waardes veronderstellen die 'toch niet voorkomen' als return gebruiken...

[DataGhost]

martyw schreef op vrijdag 10 december 2021 @ 23:54:
[...]

Tja, dat is een gevaarlijke praktijk, waardes veronderstellen die 'toch niet voorkomen' als return gebruiken...

Daarom ook de test

[DataGhost]

Soultaker schreef op vrijdag 10 december 2021 @ 22:49:
[...]

Wat was de afwijking nu precies? Het lijkt erop dat er 4 incomplete strings in zitten, maar dan is het antwoord voor deel 2 ongedefinieerd. Misschien mis ik wat.

Naast wat hierboven al gezegd is ietsjes dieper: het conflict zit dus helemaal aan het begin van de probleemomschrijving, waar staat dat

spoiler:

ze allemaal fout zijn.

Als je die voorwaarde laat vallen, klopt mijn input verder helemaal aan de omschrijving van het probleem.

spoiler:

Bij deel twee staat "Now, discard the corrupted lines. The remaining lines are incomplete.", die incomplete kan je opvatten als de betekenis van het woord "incomplete", dwz niet volledig, of je kan het opvatten als een definitie "incomplete" waarvan het enige criterium is dat de regel niet corrupt is (want die heb je net weggegooid), ook al ontbreekt er verder technisch gezien niks op die regel

Interessant trouwens, jij hebt nog weer een andere aanpak waardoor dat inderdaad misgaat. Strikt genomen

spoiler:

is er gewoon een regel in je code overbodig. Het eindresultaat zal toch hetzelfde zijn bij input die volledig aan het probleem voldoet, en die had dan direct mijn laatste testcase goed meegepakt.

[ Voor 13% gewijzigd door DataGhost op 11-12-2021 00:12 ]

[Soultaker]

Dricus schreef op vrijdag 10 december 2021 @ 23:17:

spoiler:

Een regel waarin én geen fouten zitten, én geen autocompletion nodig is.

Maar wacht eens even. Dat handel ik nu juist goed af, daarom kom ik op 4 incomplete resultaten:

code:

     1  corrupted
     2  incomplete
     3  corrupted
     4  corrupted
     5  incomplete
     6  incomplete
     7  nothing
     8  incomplete
     9  corrupted

Dus dan is het antwoord ongedefinieerd. Zou deze testset niet juist de oplossingen die geen onderscheid maken tussen incompleet en correct moeten afstraffen?

edit:
Aha, ik snap dat je het probleem zo zou kunnen lezen dat het impliceert dat alles regels die niet "corrupted" zijn als "incomplete" beschouwd moeten worden, en dan moet je de regel die ik als "geen van beide" heb gelabeled als incompleet beschouwen en dus een score van 0 toekennen. Okee, dat kan inderdaad, maar het is een beetje flauw.

[ Voor 21% gewijzigd door Soultaker op 11-12-2021 06:01 ]

[Varienaja]

Oef, wat kan er weer veel mis gaan. Maar ik ben opgelucht dat ik 'm al heb, en dat ik niet de halve zaterdag bezig ben. Het viel uiteindelijk mee.

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

[ Voor 28% gewijzigd door Varienaja op 11-12-2021 06:51 ]

[MrHaas]

Lezen was inderdaad weer de grootste uitdaging op de vroege ochtend. Gelukkig zaten er veel voorbeelden bij.

spoiler:

BFS gebruikt om elke stap te berekenen: https://github.com/arjand...ain/python/11/solution.py

[dcm360]

Lezen was deze keer het issue niet bij mij, code schrijven die ook daadwerkelijk doet wat ik wil daarentegen... Het duurde ruim te veel tijd in de debugger voordat ik er achter kwam dat mijn functie voor aangrenzende vakjes er maar 4 gaf in plaats van 8, gevolgd door wat wat gepruts omdat ik in mijn originele opzet flitsen kon missen.

[armageddon_2k1]

Dag 11 in Kotlin

Lezen was het issue niet zo. Ik wilde alleen teveel dingen hergebruiken van andere code en die was toch niet algemeen genoeg.

spoiler:

Ik ging de mist in met het feit dat ik bepaalde dat de energy == 10 moet zijn om te flashen, maar het was meer energy > 9 && !hasFlashed

Ik begin wel te merken dat simpele helper immutable data-class (die vaak lokale en afgeleide state van een enkel element bijhoudt, in dit geval de octopus) en sequences (lazy collections) echt wel heel lekker werken voor me.

Zeker sequences zorgen ervoor dat je de update-operatie netjes beschreven hebt, maar nog niks kwa aggregatie of collectie hebt gedaan. Dat maakt dat ik part 1 en part 2 vaak heel goed dezelfde sequence kan hergebruiken.

[Hydra]

Dag 11 in Kotlin

Deel 1 had ik een stukje gemist, deel 2 was een eitje.

spoiler:

In deel 1 had ik in eerste instantie gemist dat alles wat geflashed is, op 0 moet. Met die fix werkte het opeens prima. Deel 2 was heel erg simpel t.o.v. deel 1. Ik hield toch al een set met geflashte punten bij, dus dan gewoon kijken of de size daarvan even groot was als de size van de grid was genoeg.

En een visualization:

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

[ElkeBxl]

Dag 11 in Rust

Ging vlot Voor eerste keer structs aan het gebruiken, ook al had ik perfect tuples kunnen gebruiken. Maar ideaal om eraan te wennen in deze puzzel en eens wat meer van Rust te leren.

[Mschamp]

Dag 11 in C#

Ging vlot, deel 2 zat eigenlijk al verwerkt in hoe ik deel 1 aangepakt had. Enkel de lus-voorwaarde aanpassen

[Dricus]

Dag 11 in Clojure

Ging niet echt vlot. Ik merk dat ik nog wat handigheid mis met functioneel denken om voor dit soort puzzels een functionele oplossing te bedenken. Daarnaast had ik een hele domme bug, waar ik veel tijd mee kwijt was.

spoiler:

Ik gebruik een 1-dimensionale "array" om het grid in bij te houden. Om de neighbors van een octopus te bepalen is het nodig dat je weet of hij helemaal links of helemaal rechts zit. Allemaal niet moeilijk met een handige modulo check op de index. Maar dan moet je voor de rechterzijde wel "index % 10 == 9" gebruiken, en niet "index % 9 == 0" .

Al met al ben ik wel blij met het resultaat. Het was weer een leerzame ochtend .

[torx]

Ik doe dit jaar voor het eerst mee (ik wil ook de eerdere jaren alsnog doen). En voor de fun ook maar een visualisatie gemaakt:

[EfBe]

Dag 11. https://github.com/FransB...src/AoC2021.Code/Day11.cs
Puzzle 2 gebruteforced (als in: geen slimme oplossing bedacht). Het kan nog wat sneller omdat mn puzzle2 checker eigenlijk redundant is, maar boeiend, het is zaterdag

spoiler:

heb nog wel even zitten staren naar de output van de verschillende steps om te kijken of ik een patroon kon ontdekken in puzzle 2, want ik vreesde dat de gewenste state wel eens erg lang op zich kon laten wachten, maar zag het niet en het bleek achteraf ook niet nodig

[ Voor 36% gewijzigd door EfBe op 11-12-2021 11:03 ]

[DataGhost]

Ik heb de opdracht niet goed genoeg gelezen dus mijn algoritme is snel maar dikke vette overkill

spoiler:

want de grootte van de grid ligt vast.

Dus ik kan ook wel weer wat "langzame" input maken maar dat voldoet dan niet aan de probleemomschrijving.
Edit: hm, dat is misschien toch lastiger dan ik dacht, de input heeft een bepaalde vorm voor deel 2.

[ Voor 19% gewijzigd door DataGhost op 11-12-2021 11:47 ]

[Cranzai]

Leuke opdracht vandaag, veel flashbacks naar vorige dus misschien iets te lang nagedacht voordat ik ben begonnen met schrijven.

https://github.com/Cranza...021/day11/python/day11.py

spoiler:

Terugkerend probleem dat ik altijd heb met logica en wiskunde is dat ik altijd linksom denk waar anderen rechtsom denken, ik doe dan ook eerst alle 9's wegwerken voordat ik de overall +1 doe. Bij gevolg reset ik na flashes ook op -1 ipv 1.

Alles in een numpy array gezet omdat ik hoopte daar wat slimmigheidjes mee te kunnen doen, dat viel op zich tegen. Wel wat quality of life features kunnen gebruiken zoals np.where en np.add. Maak elke step een "totFlash" matrix die ik vervolgens bij de originele (waarin geflashte op 0/-1 staan) optel.

Op zich genoeg ideëen tot herschrijven naar een kortere oplossing met nested lists maar voor nu ben ik tevreden en de oplossing is me snel genoeg (thans ik moest tot 788 voor mijn antwoord bij deel B en dat was te doen).

[ Voor 6% gewijzigd door Cranzai op 11-12-2021 11:28 ]

[Remcoder]

Mmh, dit was wel erg makkelijk voor dag 11 én een zaterdag.

Members only:

Alleen zichtbaar voor ingelogde gebruikers. Inloggen

spoiler:

Doordat ik voor deel 1 al de functionaliteit had geschreven om het aantal flashes in elke ronde te bepalen kon ik die dus inderdaad heel eenvoudig hergebruiken voor deel 2, en daar gewoon kijken wanneer het aantal flashes gelijk is aan het aantal octopi

[Creepy]

Relatief eenvoudig idd. Echt een opdracht voor de zaterdag ochtend met een bakje koffie
https://github.com/CodeEn...er/aoc/aoc2021/Day11.java

spoiler:

Deel 2 was een eitje omdat ik per step toch al bijhield hoeveel er flashten

Misschien nog eens kijken of ik wat for (nested)loops kan ombouwen naar streams..

[ Voor 17% gewijzigd door Creepy op 11-12-2021 11:42 ]

[Diderikdm]

Python dag 11

Ik vond deze wel meevallen voor een zaterdag-puzzel misschien bewaren ze het grote geschut voor aankomend weekend.

[ Voor 35% gewijzigd door Diderikdm op 11-12-2021 12:55 ]

[Verwijderd]

Deze was echt makkelijk, zeker deel 2

spoiler:

aangezien ik een filter2 transformatie in matlab deed totdat er geen nieuwe flashes voor de betreffende stap bijkwamen hoefde ik alleen de som van het masker te vergelijken metde grootte van het input veld. Gelukkig was het aantal stappen klein genoeg dat ik de visualisatie van stap 1 gewoon aan kon laten staan..

Ben benieuwd of dataghost met een input van 10x10 komt waarbij de eerste simultaneous flash 1e9 iteraties na begin komt

[YoToP]

DataGhost schreef op zaterdag 11 december 2021 @ 11:20:
Ik heb de opdracht niet goed genoeg gelezen dus mijn algoritme is snel maar dikke vette overkill

spoiler:

want de grootte van de grid ligt vast.

Dus ik kan ook wel weer wat "langzame" input maken maar dat voldoet dan niet aan de probleemomschrijving.
Edit: hm, dat is misschien toch lastiger dan ik dacht, de input heeft een bepaalde vorm voor deel 2.

Komt er niet altijd een keer dat de octo's tegelijk flashen?
ik heb wat random waarde aangepast en en er komt een antwoord uit. ding blijf niet voor eeuwig loopen.. :?edit:okee misschien wel
12x12 lukt bij deel2 nog.

spoiler:

13x13 lukt ineens niet meer binnen 1 miljoen loops

en mijn inzendingen:

spoiler:

https://github.com/YoToP/AoC-2021/blob/main/11/p1.py
https://github.com/YoToP/AoC-2021/blob/main/11/p2.py

[ Voor 16% gewijzigd door YoToP op 11-12-2021 13:26 ]

[DataGhost]

Verwijderd schreef op zaterdag 11 december 2021 @ 13:04:
Deze was echt makkelijk, zeker deel 2

spoiler:

aangezien ik een filter2 transformatie in matlab deed totdat er geen nieuwe flashes voor de betreffende stap bijkwamen hoefde ik alleen de som van het masker te vergelijken metde grootte van het input veld. Gelukkig was het aantal stappen klein genoeg dat ik de visualisatie van stap 1 gewoon aan kon laten staan..

Ben benieuwd of dataghost met een input van 10x10 komt waarbij de eerste simultaneous flash 1e9 iteraties na begin komt

Met wat ik nu geprobeerd heb komt de eerste volledige flash eigenlijk altijd of binnen zo'n 500 stappen, of niet. Tenminste, na een paar miljoen iteraties vond ik het inderdaad wel genoeg en drukte ik op ctrl+c. Ik heb vandaag net niet genoeg zin om hier formules voor op te gaan stellen om zo'n invoer te construeren. Ik heb wel een 100x100 en 1000x1000 gemaakt waar de iets minder optimale algoritmes zich hard op zullen verslikken, maar ook daarbij termineert deel 2 niet binnen redelijke tijd (if at all) dus dat lijken me ook geen geweldige testcases.

Sowieso komen we zachtjes aan in het gedeelte van AoC waar de AoC-input verkeerde algoritmes zelf al harder en harder gaat afstraffen, dus ik verwacht dat ik voor nog maximaal een paar dagen inputs ga bouwen, daarna heeft iedereen toch al vrijwel dezelfde oplossing en gaan hardware en micro-optimalisaties een te grote rol spelen om algoritmisch nog interessant te zijn.

[DataGhost]

YoToP schreef op zaterdag 11 december 2021 @ 13:09:
[...]


Komt er niet altijd een keer dat de octo's tegelijk flashen?
ik heb wat random waarde aangepast en en er komt een antwoord uit. ding blijf niet voor eeuwig loopen..

Ik vermoed dat dat gegarandeerd is ja, maar daar heb ik geen bewijs voor. Je kan stiekem een parallel zien met Conway van vorig jaar en daarbij was terminatie niet gegarandeerd, dus die mogelijkheid houd ik ook nog open. In ieder geval zijn er 10¹⁰⁰ mogelijke grids dus ik verwacht ook dat voor heel veel grids het aantal stappen in de orde van dat getal komt, en dat is veel. Als je een paar random waardes aanpast blijft de grid grotendeels hetzelfde aan die die je al had dus het aantal stappen zal waarschijnlijk niet heel hard toenemen, maar ik genereerde gewoon random grids die dus vaker niet dan wel snel termineren.

[Diderikdm]

YoToP schreef op zaterdag 11 december 2021 @ 13:09:
[...]


Komt er niet altijd een keer dat de octo's tegelijk flashen?
ik heb wat random waarde aangepast en en er komt een antwoord uit. ding blijf niet voor eeuwig loopen.. :?edit:okee misschien wel
12x12 lukt bij deel2 nog.

spoiler:

13x13 lukt ineens niet meer binnen 1 miljoen loops

en mijn inzendingen:

spoiler:

https://github.com/YoToP/AoC-2021/blob/main/11/p1.py
https://github.com/YoToP/AoC-2021/blob/main/11/p2.py

spoiler:

Ik vermoed wel dat ze ooit inderdaad tegelijk gaan flashen. Dit is denk ik omdat:

Elke octo heeft standaard 1/10 kans om te flashen. Voor elke neighbour komt hier 1/10 bij

hiernaast wordt geen onderscheid gemaakt tussen de waardes range(10, 19) waarop een flashende octo op terecht kan komen en worden deze terug geset op 0.

Ik denk dat als je hier een algoritme op zou loslaten (welke ook rekening met de beginwaarden zou houden), je op een manier wel zou kunnen berekenen wanneer (9/10e kans voor octo's in het midden, 6/10e kans voor octos aan de rand en 4/10e voor octo's in de hoek) de octo's alignen met elkaar. Als de regel 10+ -> 0 anders zou zijn zou dit niet opgaan denk ik..

Disclaimer: ik ga dit algoritme niet maken maar denk wel dat het mogelijk is.
Disclaimer 2: 9/10, 6/10 en 4/10 zullen waarschijnlijk/misschien wel net andere waarden zijn dan simpel 1/10 + (1/10 * neighbours)

[ Voor 7% gewijzigd door Diderikdm op 11-12-2021 13:54 ]

[DataGhost]

Volgens mij is dit een tegenvoorbeeld:

code:

4570000064
5700000006
7000000000
0000000000
0000000000
0000000000
0000000000
0000000000
8000000000
6800000007