Advent of Code 2021

[MrHaas]

spoiler:

Voor deel 1 kan je simpelweg de mediaan als middelpunt pakken. Voor deel 2 zal er ook wel iets slims te verzinnen zijn, maar voor nu gebruteforced.

https://github.com/arjand...ain/python/07/solution.py

[Dricus]

Dag 7 in Clojure

Was niet moeilijk, ware het niet dat ik weer eens niet goed gelezen had en...

spoiler:

... de meest efficiënte positie als antwoord gaf, in plaats van de hoeveelheid fuel die daarvoor nodig was.

@MrHaas:

spoiler:

Dat hangt van je input af. Bij mij ging die vlieger niet op.

[Dricus]

Het is voor efficiëncy niet nodig, maar

spoiler:

Ik vroeg me af of je het zoekbereik nog kunt verkleinen door iets slims te doen met gemiddelde/mediaan/standaardafwijking. Mijn optimale positie ligt in de range (mediaan - stddev) -> (mediaan + stddev). Ik weet echter niet of dat in alle gevallen opgaat.

[MrHaas]

spoiler:

Het is eenvoudig te bewijzen toch? De tegenovergestelde in een gesorteerde lijst kosten samen altijd evenveel ongeacht het ijkpunt, alleen de mediaan is "onafhankelijk".

[Varienaja]

Dricus schreef op dinsdag 7 december 2021 @ 08:07:

spoiler:

Ik vroeg me af of je het zoekbereik nog kunt verkleinen door iets slims te doen met gemiddelde/mediaan/standaardafwijking. Mijn optimale positie ligt in de range (mediaan - stddev) -> (mediaan + stddev). Ik weet echter niet of dat in alle gevallen opgaat.

spoiler:

Ik dacht dat er ietwat CPU cycles bespaard kunnen worden als je vanaf het gemiddelde of de mediaan naar buiten werkt. En ophoudt met kosten uitrekenen als je boven het voorlopige minimum komt.

[Janoz]

Dricus schreef op dinsdag 7 december 2021 @ 08:03:
@MrHaas:

spoiler:

Dat hangt van je input af. Bij mij ging die vlieger niet op.

Dan ben ik wel benieuwd naar die input. Volgens mij klopt het gewoon wat @MrHaas zegt. Let wel, het gaat over deel 1

[ydderf]

Day 7 in C#
Deze was goed te doen. Heb niet echt een optimalisatie er in kunnen maken. Dus weer redelijk brute force oplossing geworden.

[Dricus]

Janoz schreef op dinsdag 7 december 2021 @ 08:18:
Dan ben ik wel benieuwd naar die input. Volgens mij klopt het gewoon wat @MrHaas zegt. Let wel, het gaat over deel 1

Oh, pff... Dat dat bij mij niet opging had niks te maken met dat de denkwijze fout was, maar met dat ik de vraag niet goed gelezen had. I stand corrected .

[Mschamp]

Dag 7 in C#:

Members only:

Alleen zichtbaar voor ingelogde gebruikers. Inloggen

Ook hier de brute force methode

[MrHaas]

spoiler:

Bij deel 2 krijg ik het goede antwoord als ik ipv de mediaan de mean pak, maar ik kan niet bewijzen of dit een generieke oplossing is

/edit: never mind, werkt niet op de sample input
/edit2: rekening houden met afrondingsfouten fixt het weer

[ Voor 27% gewijzigd door MrHaas op 07-12-2021 08:47 ]

[armageddon_2k1]

momania schreef op dinsdag 7 december 2021 @ 07:48:
[...]

Het is btw geen exponentiële groei

Huh?

[ydderf]

MrHaas schreef op dinsdag 7 december 2021 @ 08:42:

spoiler:

Bij deel 2 krijg ik het goede antwoord als ik ipv de mediaan de mean pak, maar ik kan niet bewijzen of dit een generieke oplossing is

/edit: never mind, werkt niet op de sample input

Mocht je nog een andere puzzel input willen proberen.

spoiler:

antwoord deel 1: 340987, deel 2: 96987874

[KabouterSuper]

Janoz schreef op dinsdag 7 december 2021 @ 08:18:
[...]


Dan ben ik wel benieuwd naar die input. Volgens mij klopt het gewoon wat @MrHaas zegt. Let wel, het gaat over deel 1

Het is niet de mediaan. In wiskundige termen moet je de least absolute deviation hebben (L1-norm)(Wikipedia: Least absolute deviations). Hier bestaat geen analytische oplossing voor. Voor de least squares deviation (L2-norm) heeft wel een analytische oplossing (het gemiddelde).

Als voorbeeld, neem maar eens een reeks met een 0 en twee 3en. De mediaan is dan 3, maar de juiste oplossing is 2. Edit: juiste oplossing is toch 3.

[MrHaas]

ydderf schreef op dinsdag 7 december 2021 @ 08:49:
[...]

Mocht je nog een andere puzzel input willen proberen.

spoiler:

antwoord deel 1: 340987, deel 2: 96987874

yes, kloppen beide met deze oplossing: https://github.com/arjand...ain/python/07/solution.py

[MrHaas]

KabouterSuper schreef op dinsdag 7 december 2021 @ 08:53:
[...]

Het is niet de mediaan. In wiskundige termen moet je de least absolute deviation hebben (L1-norm)(Wikipedia: Least absolute deviations). Hier bestaat geen analytische oplossing voor. Voor de least squares deviation (L2-norm) heeft wel een analytische oplossing (het gemiddelde).

Als voorbeeld, neem maar eens een reeks met een 0 en twee 3en. De mediaan is dan 3, maar de juiste oplossing is 2.

0 -> 2 = 2
3 -> 2 = 1
3 -> 2 = 1
totaal 4

0 -> 3 = 3
3 -> 3 = 0
3 -> 3 =0
totaal 3

[coop]

Dag 7 in Python

Vandaag was wel makkelijk.

spoiler:

De median en de mean pakken en dan stapje erboven en eronder bewegen tot de min gevonden is

[KabouterSuper]

Diderikdm schreef op dinsdag 7 december 2021 @ 07:22:
Python dag 7

Ik denk oprecht dat als ik om 6 uur was opgestaan ik op het leaderboard was gekomen haha. Het is niet de snelste code, maar beide parts in 1 regel en in 1x goed. Jammer dat ze zo vroeg online komen.

Nette oplossing. Ik heb bij deel 2 gebruikt dat ik wist wat 1+2+...+n is; dat scheelt een extra som.

[Janoz]

KabouterSuper schreef op dinsdag 7 december 2021 @ 08:53:
[...]

Het is niet de mediaan. In wiskundige termen moet je de least absolute deviation hebben (L1-norm)(Wikipedia: Least absolute deviations). Hier bestaat geen analytische oplossing voor. Voor de least squares deviation (L2-norm) heeft wel een analytische oplossing (het gemiddelde).

Als voorbeeld, neem maar eens een reeks met een 0 en twee 3en. De mediaan is dan 3, maar de juiste oplossing is 2.

Nee hoor. Bij 3 is 3 fuel nodig (0->3), maar bij 2 is 4 fuel nodig (0->2, 3->2, 3->2). De oplossing is dus toch 3.

[KabouterSuper]

MrHaas schreef op dinsdag 7 december 2021 @ 08:56:
[...]


0 -> 2 = 2
3 -> 2 = 1
3 -> 2 = 1
totaal 4

0 -> 3 = 3
3 -> 3 = 0
3 -> 3 =0
totaal 3

Janoz schreef op dinsdag 7 december 2021 @ 09:02:
[...]

Nee hoor. Bij 3 is 3 fuel nodig (0->3), maar bij 2 is 4 fuel nodig (0->2, 3->2, 3->2). De oplossing is dus toch 3.

Oeps...mijn fout. Ik ga nog even zoeken of ik een ander voorbeeld kan vinden. En ik weet nu dat ik een foutje had in mijn code.

[TrailBlazer]

Vandaag was echt makkelijk om te brute forcen. Enige minimale optimalisatie die ik voor deel2 heb gedaan

spoiler:

Even een lijst aangemaakt met alle distance en brandstof verbruik zodat ik niet 100 keer voor dezelfde afstand dan uit hoef te rekenen

[joppybt]

TrailBlazer schreef op dinsdag 7 december 2021 @ 09:25:
Vandaag was echt makkelijk om te brute forcen. Enige minimale optimalisatie die ik voor deel2 heb gedaan

spoiler:

Even een lijst aangemaakt met alle distance en brandstof verbruik zodat ik niet 100 keer voor dezelfde afstand dan uit hoef te rekenen

spoiler:

fuel = dist * (dist + 1) / 2
Daar heb je toch echt geen lookup tabel voor nodig?

[EfBe]

Was vrij simpel nadat ik doorhad wat te doen: https://github.com/FransB.../src/AoC2021.Code/Day7.cs

Puzzel 2 is wel wat traag (paar seconden) omdat ik geen slimmigheidje bedacht had voor de terugkerende berekening voor een range die wellicht al gezien is, maar boeiend verder

@joppybt ik neem aan dat dat de equivalent is voor de reeks waar je mee werkt? (is mij niet bekend,vandaar )

[TrailBlazer]

joppybt schreef op dinsdag 7 december 2021 @ 09:34:
[...]

spoiler:

fuel = dist * (dist + 1) / 2
Daar heb je toch echt geen lookup tabel voor nodig?

spoiler:

Ik bereken voor elke mogelijk eindpositie het fuel gebruik van elke krab. Ik denk dat het een keer berekenen en daarna opzoeken sneller gaat dan het voor iedere positie opnieuw uitrekenen. Maar ik test het later wel even to be sure.

[KabouterSuper]

KabouterSuper schreef op dinsdag 7 december 2021 @ 09:05:
[...]


[...]

Oeps...mijn fout. Ik ga nog even zoeken of ik een ander voorbeeld kan vinden. En ik weet nu dat ik een foutje had in mijn code (mijn loop stopte eentje te vroeg).

Ik heb even wat dingen uitgezocht. De literatuur lijkt bewust te willen vermijden om te zeggen dat de mediaan de oplossing is van het least absolute deviation probleem. Wel kan ik wat links vinden dat dit toch zo is, bijvoorbeeld https://math.stackexchang...deviations-the-ell-1-norm
Waar het in het algemeen op fout kan gaan is dat er een gebied is van oplossingen die allemaal optimaal zijn, terwijl de mediaan maar 1 getal is. Een voorbeeld hiervan is:
1,1,5,5.
De mediaan is 3, de optimale verschuiving is 1,2, 3, 4 of 5 (dus de hoeveelheid fuel is altijd hetzelfde tussen de minimale en maximale waarde).

Anyway, mediaan is dus praktisch gezien altijd de goede oplossing.
Maar genoeg getreuzeld, nu weer aan het werk.

[Hydra]

TrailBlazer schreef op dinsdag 7 december 2021 @ 09:43:

spoiler:

Ik bereken voor elke mogelijk eindpositie het fuel gebruik van elke krab. Ik denk dat het een keer berekenen en daarna opzoeken sneller gaat dan het voor iedere positie opnieuw uitrekenen. Maar ik test het later wel even to be sure.

Je onderschat een beetje hoe snel CPU's zijn in 'rekenen' Methodcalls zijn meestal 'duurder'.

[TrailBlazer]

Hydra schreef op dinsdag 7 december 2021 @ 10:01:
[...]


Je onderschat een beetje hoe snel CPU's zijn in 'rekenen' Methodcalls zijn meestal 'duurder'.

Toch duurt mijn python script zonder lookup 2 keer zo lang. Nu kan ik nog wel wat easy fixes bedenken om het sneller te doen.

[Creepy]

https://github.com/CodeEn...eer/aoc/aoc2021/Day7.java

spoiler:

Niks bruteforce hoeven doen, al snap ik dat bij deel 2 niet. Heb ik geluk? Bij mijn test input was de positie het gemiddelde naar boven afgerond, en bij de echte input het gemiddelde naar beneden afgerond. "Gewoon" afronden gaf niet in beide gevallen het goede antwoord. Maar toen gewoon van ceil(avg()) en floor(avg()) het laagste antwoord gepakt en dat is in beide gevallen prima.

Ik heb ook daarna nog een bruteforce versie gemaakt en die is ook erg snel, maar goed.

[DataGhost]

Lekker simpel vandaag, als je het truukje ziet.

Ik heb een paar oplossingen hier bekeken en ze kapot gemaakt, veel plezier:
Up 1, Up 2, Up 3. Ze zijn alledrie ruim binnen een seconde op te lossen op een laptop uit 2011.
Aangenomen dat mijn code foutloos is, de oplossingen.
Edit: Up 4, bzipped. Deze kost mij 3 resp 6 3 seconden.
Edit: Up 5, bzipped. Deze kost mij 3 resp 14 3 seconden.
Edit: omdat ik een heel dom iets niet had bedacht loopt mijn code nu ongelofelijk veel sneller. Daarom Up 6, bzipped, deze kost ook resp 3 en 3 seconden (eigenlijk zit bijna alle tijd in het inlezen van de input) en valt daarmee nog steeds binnen de criteria van AoC

En dan ook mijn code maar:

Members only:

Alleen zichtbaar voor ingelogde gebruikers. Inloggen

[ Voor 46% gewijzigd door DataGhost op 07-12-2021 14:19 ]

[DRaakje]

code:

|            Method |     Mean |     Error |    StdDev |
|------------------ |---------:|----------:|----------:|
|     SolveNoLookup | 2.153 ms | 0.0050 ms | 0.0003 ms |
| SolveCachedLookup | 2.000 ms | 0.2506 ms | 0.0137 ms |
|       SolveLookup | 1.947 ms | 0.0473 ms | 0.0026 ms |

Zit redelijk bij elkaar in de buurt (C# DotNetBenchmark)

Nu past de lookup mooi in het geheugen, maar als de input wat grotere getallen heeft, dan heb je de formule wel nodig.

[ Voor 211% gewijzigd door DRaakje op 07-12-2021 10:22 ]

[EfBe]

Creepy schreef op dinsdag 7 december 2021 @ 10:10:
https://github.com/CodeEn...eer/aoc/aoc2021/Day7.java

spoiler:

Niks bruteforce hoeven doen, al snap ik dat bij deel 2 niet. Heb ik geluk? Bij mijn test input was de positie het gemiddelde naar boven afgerond, en bij de echte input het gemiddelde naar beneden afgerond. "Gewoon" afronden gaf niet in beide gevallen het goede antwoord. Maar toen gewoon van ceil(avg()) en floor(avg()) het laagste antwoord gepakt en dat is in beide gevallen prima.

Ik heb ook daarna nog een bruteforce versie gemaakt en die is ook erg snel, maar goed.

spoiler:

Ik denk wat anderen 'bruteforce' noemen hier de n*m benadering is die jij (en ik) ook gekozen hebt, terwijl je ook kunt zeggen: bereken voor ieder mogelijke positie de fuel consumption voor iedere crab, de meest naive benadering.

Het gebruik van de formule voor de reeks ipv de reeks zelf levert een grote snelheidswinst op op .net iig puzzle 2 is nu binnen de seconde klaar.

[Creepy]

EfBe schreef op dinsdag 7 december 2021 @ 10:17:
[...]

spoiler:

Ik denk wat anderen 'bruteforce' noemen hier de n*m benadering is die jij (en ik) ook gekozen hebt, terwijl je ook kunt zeggen: bereken voor ieder mogelijke positie de fuel consumption voor iedere crab, de meest naive benadering.

spoiler:

Ik bedoelde met bruteforce idd per positie per crab alles berekenen, dat lijk ik bij een aantal ook te zien. Bij deel 1 is de positie de mediaan en bij deel 2 het gemiddelde al dan niet naar boven of beneden afgerond. Dus bij deel 2 hoef ik de boel maar voor 2 posities te berekenen. Duur van beide oplossing is in de milliseconden ipv seconden op die manier

[ Voor 5% gewijzigd door Creepy op 07-12-2021 10:32 ]

[DataGhost]

Creepy schreef op dinsdag 7 december 2021 @ 10:10:
https://github.com/CodeEn...eer/aoc/aoc2021/Day7.java

spoiler:

Niks bruteforce hoeven doen, al snap ik dat bij deel 2 niet. Heb ik geluk? Bij mijn test input was de positie het gemiddelde naar boven afgerond, en bij de echte input het gemiddelde naar beneden afgerond. "Gewoon" afronden gaf niet in beide gevallen het goede antwoord. Maar toen gewoon van ceil(avg()) en floor(avg()) het laagste antwoord gepakt en dat is in beide gevallen prima.

Ik heb ook daarna nog een bruteforce versie gemaakt en die is ook erg snel, maar goed.

Je "geluk" zal afhangen van

spoiler:

de vorm van de verdeling, gok ik zo. Bij deel 1 met de mediaan is het zeer makkelijk redeneren dat het voor een non-integer mediaan (dus even aantal elementen) niet uitmaakt of je de lage of de hoge van de twee pakt, of iets daar tussenin, omdat er evenveel elementen links en rechts zijn waarbij de extra hoeveelheden brandstof tegen elkaar weg te strepen zijn wederom omdat er evenveel elementen links en rechts zijn. Bij deel 2 hangen de kosten niet alleen af van het aantal elementen links en rechts maar ook van de afstanden, en bovendien kan het gemiddelde een arbitrair en verschillend aantal elementen links en rechts van zich hebben liggen, dus er is volgens mij niet een generieke oplossing uit te rekenen. Gelukkig is dan wel weer heel aannemelijk dat hoe verder je weg gaat van het gemiddelde, de afstand alleen maar toe kan nemen.

[TrailBlazer]

spoiler:

Ik denk dat de meest efficiente methode is om een startpunt te pakken mediaan/gemiddelde en dan naar links of rechts te bewegen. Neemt de fuel waarde toe dan moet je naar de andere kant. Als je dan op een bepaald moment weer gaat stijgen in fuel gebruik dan ben je er.

[DevWouter]

Hydra schreef op dinsdag 7 december 2021 @ 10:01:
[...]


Je onderschat een beetje hoe snel CPU's zijn in 'rekenen' Methodcalls zijn meestal 'duurder'.

Inderdaad, zeker als het allemaal in de CPU L1 of L2 cache blijft. Data ophalen uit RAM (zelfs zonder dat het gepaged is naar de HD/SSD) is dan verschrikkelijk duur.

[ShitHappens]

Ouch, pijnlijk lang vast gezeten op Part 2

spoiler:

Had snel genoeg door dat ik enkel een andere berekening nodig had voor de fuel costs. Maar kwam zelfs met de sample data te laag uit. Dubbel gecheckt dat de distance -> fuel berekening goed was, klopte ook... Bleek ik vergeten te vermenigvuldigen met het aantal krabben

[Janoz]

DataGhost schreef op dinsdag 7 december 2021 @ 10:14:
Lekker simpel vandaag, als je het truukje ziet.

Ik heb een paar oplossingen hier bekeken en ze kapot gemaakt, veel plezier:
Up 1, Up 2, Up 3. Ze zijn alledrie ruim binnen een seconde op te lossen op een laptop uit 2011.
Aangenomen dat mijn code foutloos is, de oplossingen.

En dan ook mijn code maar:

***members only***

Eerste twee even gedaan aangezien ik geen zin had hem om te bouwen naar BigIntegers. Voor de eerste hoeft ik maar 22x de score te berekenen en voor de 2e 102x. Zou nog efficiënter kunnen, maar dat scheelt misschien 2 of 3 berekeningen.

edit: Toch meer. Cache toevoegen brengt e

spoiler:

Voor deel2 doe ik de aanname dat er geen lokaal minimum is en kan ik bij elke stap 1/3 of 2/3 van de kandidaten weggooien.

TrailBlazer schreef op dinsdag 7 december 2021 @ 10:44:

spoiler:

Ik denk dat de meest efficiente methode is om een startpunt te pakken mediaan/gemiddelde en dan naar links of rechts te bewegen. Neemt de fuel waarde toe dan moet je naar de andere kant. Als je dan op een bepaald moment weer gaat stijgen in fuel gebruik dan ben je er.

Nee dus. Bij wat jij hier voorstelt heb ik 148 fuel berekeningen nodig terwijl mijn oplossing er maar 38 nodig heeft.

edit: cache toevoegen hielp. Nu nog maar 28 berekeningen.

[ Voor 22% gewijzigd door Janoz op 07-12-2021 11:36 ]

[MaNDaRK]

Hier wel bruteforce gedaan in C#.

Ik merk wel dat mijn wiskundige brein nog niet zo goed is ontwikkeld als ik zo de oplossingen hier zie

[FrankMennink]

Vandaag begonnen met deze oplossing, lekker bruteforce. Dag 7 naive solution

Uiteindelijk terecht gekomen op deze na inspiratie voor optimalisatie van joppybt

spoiler:

fuel = dist * (dist + 1) / 2

en de heerlijke onliners van Diderikdm

Dag 7 more optimized solution

Deel 2 draait in 400-500ms

[Cranzai]

spoiler:

Toen ik vanochtend de opdracht zag wist ik dat het lastig ging worden, had verwacht dat de brute force oplossing niet te doen zou zijn, al hoor ik veel dat dat dus wel kon (thans een efficiënte brute force...)

Daarom aan het googlen geslagen en de wiskundige oplossing voor deel A gevonden. Daarom was ik er van overtuigd dat er ook zoiets moet zijn voor deel B. Uiteindelijk heb je een goede brandstofkosten functie met de constraint x>=0. Maar ja das dus niet echt uit te werken verder.

Daarom voor het sterretje gecheat met de gemiddelde oplossing

Inmiddels ben ik er dus wel achter dat dit tot de linear programming problemen behoort. Als ik de tijd nog heb maar eens verdiepen in de algorithmes die daarvoor bestaan en kijken of ik er een van kan implementeren.

Stomste is dat ik de brute force wel al bedacht had maar graag een analytische oplossing wilde hebben. Toen dat niet lukte uit frustratie maar gecheat met het gemiddelde maar als ik zelf de brute force geschreven had was ik meer tevreden geweest.
Wat hebben we hier van geleerd? Valsspelen is niet leuk

[ Voor 16% gewijzigd door Cranzai op 07-12-2021 11:27 ]

[DataGhost]

Janoz schreef op dinsdag 7 december 2021 @ 11:09:
[...]


Eerste twee even gedaan aangezien ik geen zin had hem om te bouwen naar BigIntegers. Voor de eerste hoeft ik maar 22x de score te berekenen en voor de 2e 102x. Zou nog efficiënter kunnen, maar dat scheelt misschien 2 of 3 berekeningen.

spoiler:

Voor deel2 doe ik de aanname dat er geen lokaal minimum is en kan ik bij elke stap 1/3 of 2/3 van de kandidaten weggooien.

Ja dat is wel een lastige om kapot te maken binnen int64s. Toch een poging:
https://sigyn.dataghost.c...aoc-2021-day7-up4.txt.bz2 (wel even uitpakken )
Antwoorden staan in m'n antwoorden-bestandje hierboven. Dit duurde 3 en 6 seconden respectievelijk met mijn oplossing.

[Janoz]

DataGhost schreef op dinsdag 7 december 2021 @ 11:32:
[...]

Ja dat is wel een lastige om kapot te maken binnen int64s. Toch een poging:
https://sigyn.dataghost.c...aoc-2021-day7-up4.txt.bz2 (wel even uitpakken )
Antwoorden staan in m'n antwoorden-bestandje hierboven. Dit duurde 3 en 6 seconden respectievelijk met mijn oplossing.

Hoeveel elementen zijn dit? Vast meer dan maxint. Dan moet ik alsnog alles ombouwen omdat het niet meer in een standaard array past.

Ga vanavond wel even kijken. Ben ook nog aan het werk vandaag

[Remcoder]

spoiler:

Voor het eerst in mijn leven een binary search geimplementeerd

Hij is lekker snel, totale testrun van alle testcases is 89ms, en voor deel 2 heb ik even een formule uitgezocht om makkelijk te bepalen wat de sum is van alle getallen van 1 tot n

Members only:

Alleen zichtbaar voor ingelogde gebruikers. Inloggen

[DataGhost]

Janoz schreef op dinsdag 7 december 2021 @ 11:37:
[...]


Hoeveel elementen zijn dit? Vast meer dan maxint. Dan moet ik alsnog alles ombouwen omdat het niet meer in een standaard array past.

Ga vanavond wel even kijken. Ben ook nog aan het werk vandaag

Hoeveel weet ik niet precies maar uitgepakt is het 20MB input dus dat valt enorm mee

[gedonie]

Nou vandaag viel redelijk mee. Dag 7 in Java

spoiler:

Opdracht 1 was redelijk makkelijk berekent. Bij opdracht 2 liep ik in eerst in de valkuil dat het gemiddelde niet exact in integer was.

[Verwijderd]

MrHaas schreef op dinsdag 7 december 2021 @ 07:56:

spoiler:

Voor deel 1 kan je simpelweg de mediaan als middelpunt pakken. Voor deel 2 zal er ook wel iets slims te verzinnen zijn, maar voor nu gebruteforced.

https://github.com/arjand...ain/python/07/solution.py

voor deel twee:

spoiler:

Voor deel 2 kan je simpelweg het gemiddelde als middelpunt pakken.

Oh the joys of matlab: fuel=sum(floor(abs(inp-floor(mean(inp))).*(1+abs(inp-floor(mean(inp))))/2));

[ Voor 9% gewijzigd door Verwijderd op 07-12-2021 12:15 ]

[Caelorum]

Verwijderd schreef op dinsdag 7 december 2021 @ 12:10:
[...]
voor deel twee:

spoiler:

Voor deel 2 kan je simpelweg het gemiddelde als middelpunt pakken.

spoiler:

dat werkt niet altijd. Het zit er wel in de buurt.

[Janoz]

DataGhost schreef op dinsdag 7 december 2021 @ 11:32:
[...]

Ja dat is wel een lastige om kapot te maken binnen int64s. Toch een poging:
https://sigyn.dataghost.c...aoc-2021-day7-up4.txt.bz2 (wel even uitpakken )
Antwoorden staan in m'n antwoorden-bestandje hierboven. Dit duurde 3 en 6 seconden respectievelijk met mijn oplossing.

Tja, dan moet ik alsnog ombouwen naar BigIntegers aangezien de hoeveelheid fuel nogal groot is. Maar ik kan wel een educated guess maken. Ik denk dat ik maar iets van 106 fuel berekeningen nodig heb om het antwoord te krijgen. Voor part 1 is het er slechts 1, maar daar zit de grootste tijd waarschijnlijk in het inlezen en sorteren.

[Verwijderd]

Caelorum schreef op dinsdag 7 december 2021 @ 12:10:
[...]

spoiler:

dat werkt niet altijd. Het zit er wel in de buurt.

Je bedoelt dat de afronding niet altijd naar beneden is?

[DataGhost]

Janoz schreef op dinsdag 7 december 2021 @ 12:10:
[...]


Tja, dan moet ik alsnog ombouwen naar BigIntegers aangezien de hoeveelheid fuel nogal groot is. Maar ik kan wel een educated guess maken. Ik denk dat ik maar iets van 106 fuel berekeningen nodig heb om het antwoord te krijgen. Voor part 1 is het er slechts 1, maar daar zit de grootste tijd waarschijnlijk in het inlezen en sorteren.

Geen enkel getal in de input is groter dan 64 bits en de uitkomst is dat ook niet, dus dat moet prima lukken zonder extra gedoe. Daarom heb ik je algoritme op een andere manier kapot moeten maken, maar het zou moeten draaien zonder wijzigingen denk ik.
Edit: oh wacht met je search krijg je natuurlijk.... ah ja. Ja dat is lastig

spoiler:

Ik denk dat daar met een custom sum functie wel omheen te werken is als die overflows tijdens het summen detecteert. Dat maakt het wel direct al op een lelijke manier een stuk sneller bah.

Edit: mijn spoiler: nee toch niet

spoiler:

Bij overflows weet je namelijk nog niet per se welke kant je op moet binary searchen

[ Voor 22% gewijzigd door DataGhost op 07-12-2021 13:50 ]

[Janoz]

DataGhost schreef op dinsdag 7 december 2021 @ 12:17:
[...]

Geen enkel getal in de input is groter dan 64 bits en de uitkomst is dat ook niet, dus dat moet prima lukken zonder extra gedoe. Daarom heb ik je algoritme op een andere manier kapot moeten maken, maar het zou moeten draaien zonder wijzigingen denk ik.

Hmm, dan ging er iets anders mis. Het leek er op dat ik een negatief antwoord kreeg waardoor ik een overflow vermoedde. de daadwerkelijk gebruikte steps was inderdaad wel iets boven de 100.

Ik had alleen wat moeite met inlezen. Ik kreeg een parse exception dat hij ergens geen long van kon maken (iets van "10, maar kon zelf die quote in het bestand niet vinden) dus toen heb ik maar een gokje gedaan dat je die eerste paar getallen had en vervolgens 991899 keer 1-10.


Maar goed, als je echt van het gemiddelde uit kunt gaan en daar even rond gaat zoeken dan hoef je maar 2 of 3 fuel berekeningen te doen.


Ik had nog wel een brainfart om een SortedBag te implementeren (zit niet standaard in de collections van java) waarmee ik deze case, afhankelijk van de leessnelheid, weer binnen een paar ms weet op te lossen.

DataGhost schreef op dinsdag 7 december 2021 @ 12:26:
Misschien dat je het newline-teken mee probeerde te parsen?

Verrek, dat zal het zijn.

[ Voor 29% gewijzigd door Janoz op 07-12-2021 12:28 ]

[DataGhost]

Misschien dat je het newline-teken mee probeerde te parsen?

[Remcoder]

Er zit trouwens een easter egg in de input van vandaag.

Gooi je input maar eens door een intcode computer heen (mits je die hebt uiteraard)

spoiler:

Ceci n'est pas une intcode program

[iThinkSo]

Remcoder schreef op dinsdag 7 december 2021 @ 12:32:
Er zit trouwens een easter egg in de input van vandaag.

Gooi je input maar eens door een intcode computer heen (mits je die hebt uiteraard)

spoiler:

Ceci n'est pas une intcode program

AoC Cinematic Universe

[Marcj]

Ik liep iets achter, dus heb even snel dag 5, 6 en 7 gedaan. Dag 7 was weer erg makkelijk, want bruteforcen was meer dan snel genoeg. Mijn code zoekt in 45 milliseconden vanaf alle mogelijke posities de waarde.
En voor de berekening van de fuel van deel 2 ben ik gewoon op zoek gegaan naar de reeks waar deze waarden vandaan kwamen. Daarvoor hebben we de OEIS! https://oeis.org/A000217

Dag 7:

spoiler:

https://github.com/marcde...ejonge/advent2021/Day7.kt

Voor dag 6 heb ik maar een Memoize helper gemaakt in Kotlin. Verbazend effectief dit

Dag 6:

spoiler:

https://github.com/marcde...ejonge/advent2021/Day6.kt
https://github.com/marcde...dvent2021/util/Memoize.kt

Dag 5 vond ik tot nu toe het ingewikkeldste, daarvoor moest ik wat helper classes schrijven. Dan nog viel die uiteindelijk mee.

[ Voor 10% gewijzigd door Marcj op 07-12-2021 13:08 ]

[DRaakje]

Nog even zitten optimaliseren, nu met een binary search for minimale optimum. Toch bijna een 20x sneller.

code:

|      Method |        Mean |    Error |   StdDev |
|------------ |------------:|---------:|---------:|
|       Solve | 2,071.40 μs | 62.74 μs | 3.439 μs |
| SolveBinary |    97.68 μs | 64.08 μs | 3.513 μs |

C# oplossing
https://pastebin.com/00wXpWTp

[ Voor 9% gewijzigd door DRaakje op 07-12-2021 13:27 ]

[Janoz]

DataGhost schreef op dinsdag 7 december 2021 @ 11:32:
[...]

Ja dat is wel een lastige om kapot te maken binnen int64s. Toch een poging:
https://sigyn.dataghost.c...aoc-2021-day7-up4.txt.bz2 (wel even uitpakken )
Antwoorden staan in m'n antwoorden-bestandje hierboven. Dit duurde 3 en 6 seconden respectievelijk met mijn oplossing.

Toch even snel tussendoor wat in elkaar gehacked wat part1 uitrekent. Inlezen en on the fly sorteren duurt 4 seconden en vervolgens de berekening 1 ms om te komen tot: 6026783640

part2 probeer ik vanavond nog wel even.

[Woy]

Vanochtend geen tijd gehad, net in de pauze even snel een naive implementatie gemaakt,

https://github.com/rverst.../blob/main/Y2021/Day07.cs

Aangezien het ruim binnen de seconde klaar is geen zin om nog te optimaliseren.

[DataGhost]

Janoz schreef op dinsdag 7 december 2021 @ 13:26:
[...]


Toch even snel tussendoor wat in elkaar gehacked wat part1 uitrekent. Inlezen en on the fly sorteren duurt 4 seconden en vervolgens de berekening 1 ms om te komen tot: 6026783640

part2 probeer ik vanavond nog wel even.

Dat is off-by-2.... million

[KabouterSuper]

Even lopen te puzzelen. Voor part 2 kom ik een aardig eind met het vinden van een analytische oplossing:

spoiler:

De analytische oplossing van part 2 lijkt mean(data)+1/2 te zijn.
Met

n=aantal datapunten,
m=Σd_i/n

geldt namelijk dat

Σ [ (d_i)-x)*(d_i-x+1)/2]=
Σ [ (d_i)²/2-2xd_i/2+d_i/2+x²/2-x/2]=
Σ [ (d_i)²/2]-xΣd_i+Σd_i/2+n(x²/2-x/2)=
Σ [ (d_i)²/2]-xnm+nm/2 + nx²/2-nx/2

Afgeleide naar x geeft:
-mn+nx-n/2=0, ofwel x=m+1/2

Dit is overigens een variant is van de afleiding van de kleinste kwadratenoplossing (die mean(data) is).
Alleen nog even bewijzen dat afronden van deze oplossing nog steeds optimaal is.

[ Voor 9% gewijzigd door KabouterSuper op 07-12-2021 14:00 ]

[MueR]

Zo, helaas wat te weinig tijd gehad vanochtend, maar nu ook deel 2 af.

Members only:

Alleen zichtbaar voor ingelogde gebruikers. Inloggen

[Hydra]

KabouterSuper schreef op dinsdag 7 december 2021 @ 13:44:
Even lopen te puzzelen. Voor part 2 kom ik een aardig eind met het vinden van een analytische oplossing:

spoiler:

Vind het heel grappig dat je dat in een spoiler zet

[Cranzai]

Hydra schreef op dinsdag 7 december 2021 @ 15:14:
[...]


Vind het heel grappig dat je dat in een spoiler zet

Naja als er nou nog meerdere waren die aan een analytische oplossing werkten.
Ik heb het vanochtend ook geprobeerd, maar hopeloos gefaald

[ThomasG]

Ik heb gewoon voor de bruce-force optie gekozen. Maar zelfs zonder caches etc zijn deel 1 en 2 onder de 1ms. Rust iterators

[P_Tingen]

Wie oplossingen wil zien in eens een andere taal dan de usual suspects, nodig ik uit om de oplossingen in Progress 4GL te bekijken op https://github.com/patric...ntOfCode/tree/master/2021

Progress 4GL is by far voor veel van de opgaven ongeschikt maar daarom vind ik het des te leuker

[ydderf]

P_Tingen schreef op dinsdag 7 december 2021 @ 16:19:
Wie oplossingen wil zien in eens een andere taal dan de usual suspects, nodig ik uit om de oplossingen in Progress 4GL te bekijken op https://github.com/patric...ntOfCode/tree/master/2021

Progress 4GL is by far voor veel van de opgaven ongeschikt maar daarom vind ik het des te leuker

Op zich ziet het er nog begrijpbaar uit, maar ik doe het je nog niet zo even na.
P.s. Klopt bij dag 7A, regel 18? Zal denk ik wel goed gaan wanneer je laatste waarde van de input maar hoger is dan de optimale fuel positie. Maar wanneer je de 0 en 14 van positie wisselt in de testinput gaat het mis denk ik

[ Voor 3% gewijzigd door ydderf op 07-12-2021 16:59 ]

[Gilotto]

Zo, vandaag wat opdrachten afgerond (F#). (Dag 4, 5, 6 en 7)

Dag 6 part 2 is me nog niet gelukt. Ach ja, morgen weer verder kijken.

Dag 4, de bingo vond ik erg leuk om te modelleren.

[diabolofan]

Ohja, ik doe ook weer mee @Daanoz https://github.com/gercobrandwijk/AdventOfCode (TypeScript)

Dag 7 veel te lang over gedaan. In deel 1 al geprobeerd een goede oplossing te bedenken (wat niet erg lukte) omdat ik dacht dat deel 2 moeilijk zou worden (zoals sommigen hierboven ook al dachten). Uiteindelijk gewoon maar in het midden begonnen en naar links en rechts kijken of het lager wordt, wat in 30 ms lukt.

[Janoz]

DataGhost schreef op dinsdag 7 december 2021 @ 10:14:
Lekker simpel vandaag, als je het truukje ziet.

Ik heb een paar oplossingen hier bekeken en ze kapot gemaakt, veel plezier:
Up 1, Up 2, Up 3. Ze zijn alledrie ruim binnen een seconde op te lossen op een laptop uit 2011.
Aangenomen dat mijn code foutloos is, de oplossingen.
Edit: Up 4, bzipped. Deze kost mij 3 resp 6 3 seconden.
Edit: Up 5, bzipped. Deze kost mij 3 resp 14 3 seconden.
Edit: omdat ik een heel dom iets niet had bedacht loopt mijn code nu ongelofelijk veel sneller. Daarom Up 6, bzipped, deze kost ook resp 3 en 3 seconden (eigenlijk zit bijna alle tijd in het inlezen van de input) en valt daarmee nog steeds binnen de criteria van AoC

En dan ook mijn code maar:

***members only***

Zo, BigIntegers erin en nog wat handigheidjes en alle 4 de sets er doorheen:

21
22
26
Score for par 1: 528
Score for par 2: 6966

24
25
33
Score for par 1: 1000000034
Score for par 2: 454545450090909246

23
24
37
Score for par 1: 133713371337133713371337135701025744
Score for par 2: 8301087634516026860211773752514876132387981272374663196420201411352506

4635
4636
4643
Score for par 1: 6024799864
Score for par 2: 17999998152336305006


De 3 getallen zijn allemaal in ms vanaf start. Eerste is sorterend inlezen, 2e part1 3e part2. Hij deed dus het langst over up3 met 13ms en bij 4 is het vooral het inlezen (en sorteren).

De daadwerkelijke berekening en de bijbehorende SortedBag implementatie.

[P_Tingen]

ydderf schreef op dinsdag 7 december 2021 @ 16:32:
[...]

Op zich ziet het er nog begrijpbaar uit, maar ik doe het je nog niet zo even na.
P.s. Klopt bij dag 7A, regel 18? Zal denk ik wel goed gaan wanneer je laatste waarde van de input maar hoger is dan de optimale fuel positie. Maar wanneer je de 0 en 14 van positie wisselt in de testinput gaat het mis denk ik

Nee, dat was inderdaad een typo die voor deel 1 geen gevolgen had. Pas bij deel 2 kwam ik erachter.

[Verwijderd]

-

[ Voor 100% gewijzigd door Verwijderd op 05-09-2023 11:16 ]

[Caelorum]

spoiler:

@Verwijderd de input bij mij had maar 1 minimum, geen meerdere local minima, dus je kan dan simpelweg bij hrt begin beginnen en alle opvolgende posities uitrekenen totdat de cost weer oploopt. Dat scheelt al zo de helft van de berekeningen, als je het brute-forced, me een early return dus.
Je kan ook je for loop tot in het oneindige doorlopen (of een while gebruiken), want er is een minimum gegarandeert die voor het einde ligt, dus het einde hoef je niet te weten, scheelt weer een keer over de lijst lopen.

Zijn van die kleine dingetjes die het net wat beter laten peformen, ten koste van de generieke inzetbaarheid van de functie.

[YoToP]

Ik heb nog een andere manier gevonden om fuel uit te rekenen,
Mijn puzzel input en up1 geven een correcte output.
Echter up2 en up3 wijken iets af:

spoiler:

up2: p2 454545450090909248 (hoger)
up3: p2 8301087634516026391962716957517077568378727583743289891397595455029248 (lager)
https://github.com/YoToP/AoC-2021/blob/main/7/p2.py
Maar kom er niet achter waarom. Tot morgen

edit: ok up2 gaat nu goed. up3 kom ik inderdaad niet uit op hetzelfde

[ Voor 8% gewijzigd door YoToP op 08-12-2021 20:34 . Reden: update code voor up2 ]

[DataGhost]

YoToP schreef op dinsdag 7 december 2021 @ 23:32:
Ik heb nog een andere manier gevonden om fuel uit te rekenen,
Mijn puzzel input en up1 geven een correcte output.
Echter up2 en up3 wijken iets af:

spoiler:

up2: p2 454545450090909248 (hoger)
up3: p2 8301087634516026391962716957517077568378727583743289891397595455029248 (lager)
https://github.com/YoToP/AoC-2021/blob/main/7/p2.py
Maar kom er niet achter waarom. Tot morgen

Ik moest ook even kijken, maar...
Je hebt minimaal tweemaal hetzelfde probleem. Die je het eerste gaat vinden is (duh) de meest logische en die zorgt ervoor dat up2 goed gaat, daarna gaat up3 nog steeds fout omdat hetzelfde nog ergens anders misgaat. Ik gok bijna ook een derde probleem, hoewel je tegen die laatste niet aanloopt in deze testdata. Maar ik heb geen zin de wiskunde daarachter uit te rekenen nu. Waarschijnlijk klopt het gewoon.
Anyway,

spoiler:

je bent ergens niet zo precies als je denkt

spoiler:

Gelijke berekeningen hebben niet altijd gelijke uitkomsten

[Soultaker]

KabouterSuper schreef op dinsdag 7 december 2021 @ 13:44:
De analytische oplossing van part 2

spoiler:

lijkt mean(data)+1/2 te zijn,

Aannemende dat je dat resultaat rekenkundig afrondt dan kan dat niet kloppen. Ga maar na:

spoiler:

stel je hebt een reeks getallen a, b, c, .. met gemiddelde x. De oplossing zou dan x + 1/2. Dan is het antwoord van de reeks -a, -b, -c, .. logischerwijs -(x + 1/2), maar volgens dezelfde formule zou het -x + 1/2 moeten zijn. Het verschil is 1, dus zelfs na afronden kunnen die niet gelijk zijn.

De beste benadering is gewoon het gemiddelde van de getallen, zoals je al noemde, maar simpelweg rekenkundig afronden werkt niet. Voor mijn testinvoer was het gemiddelde b.v. 490.543 maar het optimale punt was 490, niet 491.

Wat je kunt doen is beide opties berekenen (naar boven en naar beneden afronden) en het minimum van de twee nemen. Mijn intuïtie is dat er niet meer relevante opties zijn, maar ik heb het niet precies bewezen.

[iThinkSo]

DataGhost schreef op dinsdag 7 december 2021 @ 10:14:
Lekker simpel vandaag, als je het truukje ziet.

Ik heb een paar oplossingen hier bekeken en ze kapot gemaakt, veel plezier:
Up 1, Up 2, Up 3. Ze zijn alledrie ruim binnen een seconde op te lossen op een laptop uit 2011.
Aangenomen dat mijn code foutloos is, de oplossingen.
Edit: Up 4, bzipped. Deze kost mij 3 resp 6 3 seconden.
Edit: Up 5, bzipped. Deze kost mij 3 resp 14 3 seconden.
Edit: omdat ik een heel dom iets niet had bedacht loopt mijn code nu ongelofelijk veel sneller. Daarom Up 6, bzipped, deze kost ook resp 3 en 3 seconden (eigenlijk zit bijna alle tijd in het inlezen van de input) en valt daarmee nog steeds binnen de criteria van AoC

En dan ook mijn code maar:

***members only***

1-3 draaien nu prima, 4 ook maar duurt ~20 seconden maar alle tijd zit in de parsing. Kan op zich wel een efficientere parser schrijven, maar denk dat het zo wel prima is

Thanks voor de extra testcases

[MrHaas]

Dit was een lijdensweg, ruim 3 kwartier over gedaan en dan was ik nog niet eens heel langzaam tov de rest.

spoiler:

Na wat puzzelen op overlaps tussen de "known digits" en de onbekenden had ik gevonden dat die overlaps uniek zijn en je dus heel makkelijk kan bepalen wat elk unknown signal is.

https://github.com/arjand...ain/python/08/solution.py

[KabouterSuper]

MrHaas schreef op woensdag 8 december 2021 @ 07:16:
Dit was een lijdensweg, ruim 3 kwartier over gedaan en dan was ik nog niet eens heel langzaam tov de rest.

spoiler:

Na wat puzzelen op overlaps tussen de "known digits" en de onbekenden had ik gevonden dat die overlaps uniek zijn en je dus heel makkelijk kan bepalen wat elk unknown signal is.

https://github.com/arjand...ain/python/08/solution.py

Ja, deze was behoorlijk pittig. Ik was allang blij dat ik antwoorden kreeg, dus daarom heb ik teveel ad hoc constructies laten zitten, zoals deze:

code:

    d=[data_right[j]+data_left[j]][0]
    if (True):
        #blah

Brrrrr.

spoiler:

@MrHaas , grappig dat je de overlaps zoveel gestructureerder hebt gedaan dan ik (hoewel het uiteindelijk op hetzelfde neerkomt).
Ik heb gewoon een ouderwetsche if-then-else gedaan op de overlap met specifieke getallen, bijv
lengte=6 en aantal overlaps met 1 is x, dan xx
lengte=6 en aantal overlaps met 4 is y, dan yy
lengte=6 anders, dan zz

[armageddon_2k1]

Potverdomme, hier heb ik veeeel te lang over gedaan.

Dag 8 in Kotlin

Hij was natuurlijk redelijk simpel, maar het duurde even voor m'n ochtendbrein eropkwam. Ben er twee uur mee bezig geweest... (wel met koffie halen, even wat werk dingen doen etc)

spoiler:

Ik heb niks met overlaps gedaan. Ik ben gewoon opties gaan bijhouden per segment en die gaan wegstrepen aan de hand van de bekende informatie die je had:
- getallen 1, 4, 7 en 8 zijn uniek (die laatste heb je geen reet aan) kwa segment aantal
- voor alle getallen komen een paar segmenten een uniek aantal keer voor (4x, 6x en 9x).

Daarna elimineren, rekening houdend met subgroep groottes. Bijvoorbeeld: Als er twee groepen zijn die allebei alleen nog maar dezelfde 2 opties hebben, dan zijn die twee opties niet meer mogelijk bij welke andere groep dan ook. Maar dan gegeneraliseerd voor elke groep grootte.

[ Voor 47% gewijzigd door armageddon_2k1 op 08-12-2021 09:23 ]

[coop]

Dag 8 in Python

Hier ook een uurtje over gedaan of zo. Niet heel schoon, maar het doet zijn werk.

spoiler:

Inderdaad eerst 1, 4, 7, 8 bepalen, daarna positie 0 bepalen (van boven naar beneden, van links naar recht tellend). Dan waarde 0, 6 en 9 (en een aantal posities) bepalen aan de hand van 4+positie 0. Dan positie 4 bepalen en dan de waarde 2, 3 en 5.

Misschien later nog even kijken of het wat efficienter kan.

[Diderikdm]

Python dag 8

Was een leuke puzzel vandaag! Hou wel van deductie.

[ Voor 40% gewijzigd door Diderikdm op 08-12-2021 10:17 ]

[Varienaja]

coop schreef op woensdag 8 december 2021 @ 09:29:
Hier ook een uurtje over gedaan of zo. Niet heel schoon, maar het doet zijn werk.

Bij mij ging het ook niet vlug. Om half 7 moest ik m'n dochter uit bed halen voor school. Tijdens het ontbijt hebben we samen op papier de oplosstrategie bepaald. Daarna heb ik redelijk vlug met ontzettend verbose code onze strategie omgezet. Ik zal zo nog even committen (zit nu op mijn thuiswerkplek, niet op m'n hobbyplek) en vanavond uitgebreid opschonen.

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

[DataGhost]

Leuk, niet heel moeilijk maar vooral wat gekloot met het netjes doen.

spoiler:

Ik heb set-operaties gebruikt, dat scheelt een hoop code. Het gaat nog net niet vanzelf

Members only:

Alleen zichtbaar voor ingelogde gebruikers. Inloggen

Geen speciale inputs vandaag, daar is het probleem te simpel voor.

[Marcj]

spoiler:

https://github.com/marcde...ejonge/advent2021/Day8.kt

Ik heb deze vergelijkbaar gedaan als een aantal anderen hier blijkbaar. Het grootste verschil is dat ik de input direct vertaal in een int, om vervolgens de vergelijkingen met bit operators doe. Hoef ik ook niet na te denken over sorteringen. En nummer 8 is altijd gecodeerd als 127 (7 bits gezet). En ik heb een hulpfunctie gemaakt om de boel wat leesbaarder te houder.

[dcm360]

Het duurde best wel een tijd voordat ik vandaag doorhad hoe deel 2 handig opgelost kon worden. Na een half uur niet helemaal de juiste kant uit werken*, lukte het me daarna vrij vlot om iets te bedenken dat wel werkt en zat de code ook zo in elkaar.

spoiler:

Net als veel andere oplossingen dus met intersecties op sets, en in zekere zin dus een herkenbare oplossing

*: Ik probeerde eerst aan de slag te gaan met de posities van alle segmenten, en als ik dat opgelost had dat weer om te zetten naar getallen. Maar de posities van de segmenten maken eigenlijk niet uit, en het duurde even voordat ik dat realiseerde.

[Remcoder]

Ik heb echt extreem verbose code geschreven vergeleken met jullie

Maar, wel een oplossing die begrijpelijk en leesbaar is, en alle testcases afrondt binnen 200ms op mijn machine. Ik doe het ervoor.

Members only:

Alleen zichtbaar voor ingelogde gebruikers. Inloggen

spoiler:

Eerst bepaal ik zoals iedereen 1, 4, 7, en 8, en daarna kan ik die gebruiken om een de overige getallen te bepalen door gebruik te maken van de juiste overlap. Ik sorteer ook alle chars in de string, want ik zag al dat de volgorde van de chars in de displaywaarde niet gelijk is aan de volgorde in de testwaarde.

[EfBe]

Wat een k*t puzzel met een erg slechte omschrijving wat te doen. Maar goed, ben op zich wel tevreden met men set based oplossing
https://github.com/FransB.../src/AoC2021.Code/Day8.cs

KabouterSuper schreef op woensdag 8 december 2021 @ 09:03:

spoiler:

@MrHaas , grappig dat je de overlaps zoveel gestructureerder hebt gedaan dan ik (hoewel het uiteindelijk op hetzelfde neerkomt).
Ik heb gewoon een ouderwetsche if-then-else gedaan op de overlap met specifieke getallen, bijv
lengte=6 en aantal overlaps met 1 is x, dan xx
lengte=6 en aantal overlaps met 4 is y, dan yy
lengte=6 anders, dan zz

spoiler:

Heh ik hetzelfde. Kwam er bij het laatste digit achter dat wanneer je de digits die je al hebt gehad uit de input haalt het testen stukken makkelijker wordt, maar ik heb totaal niet gezien dat de overlap uniek is per digit

[ Voor 63% gewijzigd door EfBe op 08-12-2021 11:52 ]

[Creepy]

Ik vond het juist weer een leuke puzzel. Duurde wel ff voordat ik wat werkbaars had, maar goed.

spoiler:

Puur deductie gebruikt, meer niet. Welk segment nu precies waar staat boeit niet zolang je per cijfer maar weet welke segmenten er gebruikt worden.

- 1,4,7,8 kan je direct bepalen zoals in deel 1 beschreven
- Van alle cijfers met 6 segmenten bevat 9 als enige alle segmenten van 4
- Dan hebben alleen 0 en 6 nog 6 segmenten. 0 bevat alle segmenten van 1
- Alleen 6 heeft nog 6 segmenten, dus die weet je ook
- Alleen 2, 3 en 5 zijn nog over. 3 bevat alle segmenten van 1.
- Alleen 2 en 5 over. 9 bevat alle segmenten van 5
- Alleen 2 nog over.

https://github.com/CodeEn...eer/aoc/aoc2021/Day8.java

[ Voor 21% gewijzigd door Creepy op 08-12-2021 12:15 ]

[DevWouter]

(dag 9)
Verdikke deze was pittig maar weer omdat ik meer complexiteit had verwacht. Uiteindelijk een goed uur bezig geweest.

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.

Toen ik bijna klaar was heb ik een analyze gedaan over de data omdat mijn else-branches nooit triggerde en toen zuchtend de code versimpeld.

spoiler:

Het zou zoveel leuker zijn geweest als er telkens één of meerdere getallen afwezig waren.

[KabouterSuper]

DataGhost schreef op woensdag 8 december 2021 @ 10:44:
Geen speciale inputs vandaag, daar is het probleem te simpel voor.

Helaas. Misschien dan een theorie-vraagje vandaag?
Er worden 7 bits gebruikt om de 10 getallen te laten zien (want 7 streepjes).
Dat is eigenlijk inefficient, want je kunt 10 getallen kwijt in 4 bits (je kunt zelfs 16 getallen kwijt in 4 bit).
Als je ervan uit gaat dat elk streepje een lampje is wat je uit en aan kunt zetten, is mijn vraag

"Kan je deze lampjes elegant aansturen met 4 bits?"

Natuurlijk kan je wat je hebt gebouwd omzetten naar binaire operatoren (de oplossing van @Diderikdm ziet er uit als een goed startpunt), maar het zou toch veel mooier moeten kunnen?

Dus de extra opdracht is:
maak een reeks binaire operatoren (AND, OR, XOR, NOT, NOR) zodanig dat elk lampje a,b,c,d,e,f en g aangestuurd kunnen worden met 4 bits.

Als slecht voorbeeld:
bit 1 schakelt cf
bit 2 schakelt bd
bit 3 schakelt a
bit 4 schakelt g
dan
1000=1
1100=4
1010=7
1111=9
maar de rest kan niet.

Overigens, ik weet de beste oplossing ook nog niet.

[armageddon_2k1]

Moet wel zeggen dat ik de uitleg het moeilijkst vond van de hele opdracht. Duurde erg lang voordat ik hem goed en wel begreep.

[armageddon_2k1]

Remcoder schreef op woensdag 8 december 2021 @ 11:37:
Ik heb echt extreem verbose code geschreven vergeleken met jullie

Maar, wel een oplossing die begrijpelijk en leesbaar is, en alle testcases afrondt binnen 200ms op mijn machine. Ik doe het ervoor.


***members only***

spoiler:

Eerst bepaal ik zoals iedereen 1, 4, 7, en 8, en daarna kan ik die gebruiken om een de overige getallen te bepalen door gebruik te maken van de juiste overlap. Ik sorteer ook alle chars in de string, want ik zag al dat de volgorde van de chars in de displaywaarde niet gelijk is aan de volgorde in de testwaarde.

Verbose is niet erg. Ik begrijp precies wat jouw code doet.

[Janoz]

KabouterSuper schreef op woensdag 8 december 2021 @ 12:22:
[...]

Helaas. Misschien dan een theorie-vraagje vandaag?
Er worden 7 bits gebruikt om de 10 getallen te laten zien (want 7 streepjes).
Dat is eigenlijk inefficient, want je kunt 10 getallen kwijt in 4 bits (je kunt zelfs 16 getallen kwijt in 4 bit).
Als je ervan uit gaat dat elk streepje een lampje is wat je uit en aan kunt zetten, is mijn vraag

"Kan je deze lampjes elegant aansturen met 4 bits?"

Natuurlijk kan je wat je hebt gebouwd omzetten naar binaire operatoren (de oplossing van @Diderikdm ziet er uit als een goed startpunt), maar het zou toch veel mooier moeten kunnen?

Dus de extra opdracht is:
maak een reeks binaire operatoren (AND, OR, XOR) zodanig dat elk lampje a,b,c,d,e,f en g aangestuurd kunnen worden met 4 bits.

Als slecht voorbeeld:
bit 1 schakelt cf
bit 2 schakelt bd
bit 3 schakelt a
bit 4 schakelt g
dan
1000=1
1100=4
1010=7
1111=9
maar de rest kan niet.

Overigens, ik weet de beste oplossing ook nog niet.

Ik weet toevallig dat exact dit of een oefenvraag, of een tentamenvraag was tijdens mijn opleiding . Maak hem dan ook gelijk voor alle 16 met ABCDEF er ook bij

[Glewellyn]

Ik doe voor de hobby dit jaar ook mee om te kijken hoe ver ik kom, maar zonder al te veel programmeerervaring ziet mijn code er een stuk lelijker uit dan het meeste dat ik hier gepost zie worden.

Members only:

Alleen zichtbaar voor ingelogde gebruikers. Inloggen

[Glewellyn]

KabouterSuper schreef op woensdag 8 december 2021 @ 12:22:
[...]

Helaas. Misschien dan een theorie-vraagje vandaag?
Er worden 7 bits gebruikt om de 10 getallen te laten zien (want 7 streepjes).
Dat is eigenlijk inefficient, want je kunt 10 getallen kwijt in 4 bits (je kunt zelfs 16 getallen kwijt in 4 bit).
Als je ervan uit gaat dat elk streepje een lampje is wat je uit en aan kunt zetten, is mijn vraag

"Kan je deze lampjes elegant aansturen met 4 bits?"

Natuurlijk kan je wat je hebt gebouwd omzetten naar binaire operatoren (de oplossing van @Diderikdm ziet er uit als een goed startpunt), maar het zou toch veel mooier moeten kunnen?

Dus de extra opdracht is:
maak een reeks binaire operatoren (AND, OR, XOR) zodanig dat elk lampje a,b,c,d,e,f en g aangestuurd kunnen worden met 4 bits.

Als slecht voorbeeld:
bit 1 schakelt cf
bit 2 schakelt bd
bit 3 schakelt a
bit 4 schakelt g
dan
1000=1
1100=4
1010=7
1111=9
maar de rest kan niet.

Overigens, ik weet de beste oplossing ook nog niet.

Ja moet kunnen.

Zoiets voor inputs 0, 1 en 2 (0000, 1000, 0100):
0000:

code:

INPUT 0 > NOR < INPUT 1
           V
          AND -------------------------> OR(segment1) 
           ^                      |----> OR(segment2)
INPUT 2 > NOR < INPUT 3           |----> OR(segment3)
                                  |----> OR(segment5)
                                  |----> OR(segment6)
                                  |----> OR(segment7)

0001:

code:

INPUT 0 > NOR < NOT < INPUT 1
           V
          AND -------------------------> OR(segment3) 
           ^                      |----> OR(segment6)
INPUT 2 > NOR < INPUT 3

0100:

code:

      INPUT 0 > NOR < INPUT 1
                 V
                AND -------------------> OR(segment1) 
                 ^                |----> OR(segment3)
INPUT 2 > NOT > NOR < INPUT 3     |----> OR(segment4)
                                  |----> OR(segment5)
                                  |----> OR(segment7)

En waar ik het heb over OR (segment X) bedenk ik aan een OR met meer dan 1 input of een setje OR poorten achter elkaar.

[Janoz]

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

De bedoeling is juist dat je 1 schema maakt waar 4 bits in gaan en 7 bits uitkomen. Niet een schema per input

[gedonie]

Na wat puzzelen dag 8 in Java toch weten op te lossen.

Ik liep redelijk lang tegen een stomme fout dat ik het korte voorbeeld pakte en daar niet het resultaat uitkwam voor het langere voorbeeld .

Hierdoor had ik voor deel 1 ook al alle benodigde code voor deel 2 geschreven blijkbaar. Die tweede had ik daarna binnen een paar minuten uitgewerkt.

[MueR]

Ook klaar met dag 8. Ben alleen nog niet helemaal tevreden.

[ Voor 14% gewijzigd door MueR op 08-12-2021 13:41 ]

[Glewellyn]

Janoz schreef op woensdag 8 december 2021 @ 13:36:
[...]


De bedoeling is juist dat je 1 schema maakt waar 4 bits in gaan en 7 bits uitkomen. Niet een schema per input

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.

[iThinkSo]

spoiler:

Met backtracking opgelost, een stuk lastiger dan gisteren in ieder geval!

https://github.com/Synthe.../blob/master/day8/day8.py

[Creepy]

KabouterSuper schreef op woensdag 8 december 2021 @ 12:22:
[...]

Helaas. Misschien dan een theorie-vraagje vandaag?
Er worden 7 bits gebruikt om de 10 getallen te laten zien (want 7 streepjes).
Dat is eigenlijk inefficient, want je kunt 10 getallen kwijt in 4 bits (je kunt zelfs 16 getallen kwijt in 4 bit).
Als je ervan uit gaat dat elk streepje een lampje is wat je uit en aan kunt zetten, is mijn vraag

"Kan je deze lampjes elegant aansturen met 4 bits?"

Natuurlijk kan je wat je hebt gebouwd omzetten naar binaire operatoren (de oplossing van @Diderikdm ziet er uit als een goed startpunt), maar het zou toch veel mooier moeten kunnen?

Dus de extra opdracht is:
maak een reeks binaire operatoren (AND, OR, XOR, NOT, NOR) zodanig dat elk lampje a,b,c,d,e,f en g aangestuurd kunnen worden met 4 bits.

Als slecht voorbeeld:
bit 1 schakelt cf
bit 2 schakelt bd
bit 3 schakelt a
bit 4 schakelt g
dan
1000=1
1100=4
1010=7
1111=9
maar de rest kan niet.

Overigens, ik weet de beste oplossing ook nog niet.

Jaren geleden exact dit moeten oplossen voor een soldeerschema maar dan met de hand op papier dus.