Advent of Code 2021

[Creepy]

Zo, de tijd gehad om de boel af te ronden. Deel 2 kost 18 seconden nu. Misschien later nog eens verder optimaliseren.

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

[Cranzai]

Cranzai schreef op woensdag 15 december 2021 @ 16:45:
Wie heeft zin om mee te kijken? Ik zit vast
https://github.com/Cranza...021/day15/python/day15.py
De code is nog een zootje maar dat komt door het debuggen

spoiler:

Mijn intentie was om een soort van depth-first Dijkstra algoritme te gebruiken.
Neem je uitgangspositie, ga vervolgens alle buur-coordinaten af in volgorde van groot naar klein.
Dit probeer ik recursief te doen met bijhouden van paden.

Ik krijg 3 paden als antwoord voor het voorbeeld maar allen zijn fout, ze gaan namelijk allemaal alleen rechtsaf ipv naar beneden te gaan.

Met alle deepcopy's en het spawnen van nieuwe instances ben ik volledig in de war.

Uiteindelijk nog tot dit gekomen maar daarmee ook gestrand:
https://github.com/Cranza.../day15/python/dijkstra.py

Deel A werkt prima, deel B werkt niet.

[Creepy]

Creepy schreef op woensdag 15 december 2021 @ 21:09:
Misschien later nog eens verder optimaliseren.

Ok, dat was snel. Nu 450ms voor deel 2.

spoiler:

Priority queue ipv een (Hash)Set voor het bepalen van de "kleinste" node. Wat een verschil

[TrailBlazer]

Uiteindelijk gelukt door voor het eerste Dijkstra in code te schrijven. Normaliter laat ik dat de mensen van Cisco voor me doen .
Er zit nog wel een klein dingetje in dat ik bij het voorbeeld van task2 de laatste node niet meetel in mijn costen maar in mijn puzzle input wel. Dat moet ik nog even uitzoeken.

[P_Tingen]

spoiler:

Ik lees links en rechts over Dijkstra met priority queue, maar kan er zo snel geen duidelijke uitleg van vinden. Heeft iemand een duidelijke uitleg voor mij?

[Dricus]

P_Tingen schreef op woensdag 15 december 2021 @ 21:44:

spoiler:

Ik lees links en rechts over Dijkstra met priority queue, maar kan er zo snel geen duidelijke uitleg van vinden. Heeft iemand een duidelijke uitleg voor mij?

Ik vond wikipedia vrij duidelijk:

spoiler:

Wikipedia: Dijkstra's algorithm

[P_Tingen]

Dricus schreef op woensdag 15 december 2021 @ 21:45:
[...]

Ik vond wikipedia vrij duidelijk:

spoiler:

Wikipedia: Dijkstra's algorithm

Ha, kijk aan, ik had de NL pagina wel gevonden maar daar staat het niet op

[TrailBlazer]

Was meer geluk dan wijsheid dat de uitkomsten klopten had een fuckup gemaakt ik die kopieer actie.

[Cranzai]

Nou, ik geef het op voor vandaag, deel B kan me gestolen worden.
Misschien morgen maar ff twee uur uittrekken om dezelfde code als voor A te draaien.

[gedonie]

Toch nog even dag 15 in Java gedaan.

spoiler:

Duurde even voordat ik het Dijkstra algoritme goed gebouwd had. Was al weer even geleden. En daarnaast voor opdracht 2 een soort van virtueel grid gemaakt dat waarden uitrekent als ze nodig zijn.

[ElkeBxl]

Dag 15 in Rust. Deel 2 heeft wel 45 minuten moeten runnen om resultaat uit te spugen maar het klopte wel

[Soultaker]

Ik snap niet waarom de Java/Kotlin oplossingen voor dag 15 allemaal zo traag zijn terwijl m'n Python oplossing in 500 ms draait. Is de Java priority queue slecht geoptimaliseerd ofzo? Of zit er toch een bug in het algoritme van de deelnemers die deze taal gebruiken?

Ik kan me voorstellen dat het alloceren van een heleboel kleine objecten niet super-efficient is, maar dat nadeel heeft Python op zich ook, en ik dacht dat de JVM daar juist erg goed voor geoptimaliseerd was (Python natuurlijk ook, maar het verschil zou niet groot moeten zijn).

edit:
Uit nieuwsgierigheid even m'n Python oplossing naar Java omgeschreven: behalve dat de Java broncode drie keer zo lang is (want Java), draait 'ie in 200 ms. Dat lijkt er meer op. De mensen die tientallen seconden nodig hebben doen dus toch iets verkeerd, denk ik.

edit:
Overigens kan het nog sneller door juist helemaal geen priority queue te gebruiken (~150 ms). De reden dat dat toch efficiënt is dat alle edges maximaal lengte 9 hebben dus er zijn maximaal 10 verschillende afstanden tegelijk actief. Daarmee wordt het algoritme O(4*H*W*10) i.p.v O(4*H*W*log(4*H*W)) en dat is beter (zelfs als je de constante factoren meerekent die natuurlijk niet helemaal verwaarloosbaar zijn in de praktijk).

[ Voor 57% gewijzigd door Soultaker op 16-12-2021 02:32 ]

[gedonie]

@Soultaker je conclusie klopt. Een Java implementatie van dijkstra hoeft absoluut niet zo lang te duren. Ik verwacht dat bij de meeste het mis gaat in het inlezen en omzetten in data structuren (mis in de zin dat het relatief lang duurt).

Dit viel mij namelijk ook op in mijn oplossing. Ik splits metingen in voorbereiding en algoritme uitvoer. Waarbij gemiddeld genomen het voorbereiden van opdracht 2 450ms duurt en het draaien van het algoritme 160ms.

Edit: ik heb even zitten spelen met mijn oplossing en blijkbaar is de ArrayList in Java de grootste vertragende factor. Als ik dit allemaal omzet naar normale array's dan duurt voorbereiding nog maar 290ms en algoritme uitvoer nog maar 118ms.

[ Voor 21% gewijzigd door gedonie op 16-12-2021 07:59 ]

[Dricus]

Dag 16 in Clojure

Zo, dat was even werk. Vooral goed lezen, en ervoor zorgen dat je geen bitjes overslaat. Verder was het niet heel moeilijk. Wel leuk .

[Lisper]

gedonie schreef op donderdag 16 december 2021 @ 07:52:
@Soultaker je conclusie klopt. Een Java implementatie van dijkstra hoeft absoluut niet zo lang te duren. Ik verwacht dat bij de meeste het mis gaat in het inlezen en omzetten in data structuren (mis in de zin dat het relatief lang duurt).

Ik weet niet of mensen de JVM startup tijd meerekenen of niet, maar dat is ook een factor.

Een JVM implementatie echt goed benchmarken is sowieso nog niet zo makkelijk.
De JVM past sommige optimalisaties pas toe nadat een method een X aantal keer is aangeroepen, en dat optimaliseren kost ook CPU.
Het 1x uitvoeren van het algoritme zal waarschijnlijk niet het onderste uit de kan halen.
Je zou eerst een warmup kunnen doen (bijv. N maal het algoritme runnen), en dan pas gaan meten.

Ik probeer het dit jaar in Rust te doen, voordeel daarvan is dat die wel meteen optimaliseert: ik heb net de opt-level op 3 gezet, en dan gaat de snelheid van 1 seconde naar 70ms!

[ Voor 10% gewijzigd door Lisper op 16-12-2021 10:55 ]

[MrHaas]

Dricus schreef op donderdag 16 december 2021 @ 08:41:
Dag 16 in Clojure

Zo, dat was even werk. Vooral goed lezen, en ervoor zorgen dat je geen bitjes overslaat. Verder was het niet heel moeilijk. Wel leuk .

Mweh, uiteindelijk was het wel geinig, maar vond het iets teveel op werken lijken

[Varienaja]

Ik vond vandaag het principe moeilijk uitgelegd worden. Het implementeren ging eigenlijk gemakkelijk genoeg. De requirementsanalyse was dus net echt :-D Normaal gesproken kunnen klanten hun wensen ook niet altijd begrijpelijk formuleren.

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

[P_Tingen]

Vanmorgen ook al even gelezen, nog niet mee bezig geweest. Dit soort opgaven vind ik niet zo veel aan; veel te veel lezen en veel "kunstmatige" ingewikkeldheid in de opgave.

Ik voel trouwens weer een intcode computer aankomen als ik dit zo lees.

[Creepy]

Ik heb hetzelfde ja, langer bezig met het goed kunnen parsen van het geheel dan de rest. Ben net begonnen maar eigenlijk ben ik het geneuzel al beu

[Hydra]

Dag 16 in Kotlin

Niet moeilijk, wel veel werk.

[ Voor 13% gewijzigd door Hydra op 16-12-2021 10:19 ]

[iThinkSo]

Dag 16 in Python


https://github.com/Synthe...84304cabdd/day16/day16.py

spoiler:

Goede usecase voor iterators, wel de eerste dag dat ik er een externe library bijgehaald heb (more_itertools)

[Janoz]

Het was inderdaad best veel leeswerk, maar om eerlijk te zijn valt het uiteindelijk best heel erg mee.

[Remcoder]

Dit is gewoon niet meer leuk om te doen...

[Hydra]

Soultaker schreef op donderdag 16 december 2021 @ 01:10:
Ik snap niet waarom de Java/Kotlin oplossingen voor dag 15 allemaal zo traag zijn terwijl m'n Python oplossing in 500 ms draait. Is de Java priority queue slecht geoptimaliseerd ofzo? Of zit er toch een bug in het algoritme van de deelnemers die deze taal gebruiken?

Ik denk het laatste; Java zou absoluut niet langzamer moeten zijn maar de eerste versie van Dijkstra heb ik geimplementeerd op basis van een stukje psuedocode en die was echt super slecht. De nieuwe versie is 'geoptimaliseerd' maar nog steeds op die slechte implementatie gebaseerd. Dus daar zal nog wel het e.e.a. aan verbeterd kunnen worden.

Wat denk ik ook wel meespeelt is dat mijn oplossing generiek is: ik bouw een Graph waar een generieke Dijkstra algo doorheen gaat. Dit betekent alleen wel dat er een hoop Node en Edge objecten aangemaakt worden (width * height nodes, maal 4 edges). Als je de oplossing speciek voor deze dag schrijft met een paar integer arrays, denk ik zeker dat 't een stuk sneller gaat zijn.

Voordeel dat ik weer heb is dat als er nog een keer zo'n vraag komt, ik gewoon de input om kan bouwen naar een graph en hey presto; de oplossing.

[ Voor 6% gewijzigd door Hydra op 16-12-2021 10:54 ]

[Creepy]

En klaar met dag 16. Niet heel spannend, wel veel typewerk en geneuzel.

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

[Creepy]

Soultaker schreef op donderdag 16 december 2021 @ 01:10:
Ik snap niet waarom de Java/Kotlin oplossingen voor dag 15 allemaal zo traag zijn terwijl m'n Python oplossing in 500 ms draait. Is de Java priority queue slecht geoptimaliseerd ofzo? Of zit er toch een bug in het algoritme van de deelnemers die deze taal gebruiken?

Niet alla Java oplossingen zijn zo traag he

[Cranzai]

Soultaker schreef op donderdag 16 december 2021 @ 01:10:
Ik snap niet waarom de Java/Kotlin oplossingen voor dag 15 allemaal zo traag zijn terwijl m'n Python oplossing in 500 ms draait. Is de Java priority queue slecht geoptimaliseerd ofzo? Of zit er toch een bug in het algoritme van de deelnemers die deze taal gebruiken?

Ik kan me voorstellen dat het alloceren van een heleboel kleine objecten niet super-efficient is, maar dat nadeel heeft Python op zich ook, en ik dacht dat de JVM daar juist erg goed voor geoptimaliseerd was (Python natuurlijk ook, maar het verschil zou niet groot moeten zijn).

edit:
Uit nieuwsgierigheid even m'n Python oplossing naar Java omgeschreven: behalve dat de Java broncode drie keer zo lang is (want Java), draait 'ie in 200 ms. Dat lijkt er meer op. De mensen die tientallen seconden nodig hebben doen dus toch iets verkeerd, denk ik.

edit:
Overigens kan het nog sneller door juist helemaal geen priority queue te gebruiken (~150 ms). De reden dat dat toch efficiënt is dat alle edges maximaal lengte 9 hebben dus er zijn maximaal 10 verschillende afstanden tegelijk actief. Daarmee wordt het algoritme O(4*H*W*10) i.p.v O(4*H*W*log(4*H*W)) en dat is beter (zelfs als je de constante factoren meerekent die natuurlijk niet helemaal verwaarloosbaar zijn in de praktijk).

Massive thumbs up voor jouw python implementatie, erg goed te begrijpen!
Gisteravond eindeloos geploeterd met

spoiler:

dijkstra (voor het eerst dat ik met een serieus algoritme werk)

, uiteindelijk deel A werkend gekregen. Na een nachtje slapen snap ik het idee veel beter. Alleen het implementeren van een goede queue en gebruik van andere datatypes was essentieel voor snelheid zoals jij laat zien. Om zou zelf een heapq te gaan implementeren leek me ook zo wat.

Alles net ff aangepast en in mijn eigen stijl opgeschreven maar hopelijk vat je het als een compliment op dat ik "hevig geïnspireerd" was door jouw code

[armageddon_2k1]

Drukke ochtend, dus geen tijd om eraan te werken. En toen ik de opdracht zag dacht ik al.... deze stel ik even uit voor het weekend als ik wat meer tijd heb om te lezen

[armageddon_2k1]

Hydra schreef op donderdag 16 december 2021 @ 10:53:
[...]


Ik denk het laatste; Java zou absoluut niet langzamer moeten zijn maar de eerste versie van Dijkstra heb ik geimplementeerd op basis van een stukje psuedocode en die was echt super slecht. De nieuwe versie is 'geoptimaliseerd' maar nog steeds op die slechte implementatie gebaseerd. Dus daar zal nog wel het e.e.a. aan verbeterd kunnen worden.

Wat denk ik ook wel meespeelt is dat mijn oplossing generiek is: ik bouw een Graph waar een generieke Dijkstra algo doorheen gaat. Dit betekent alleen wel dat er een hoop Node en Edge objecten aangemaakt worden (width * height nodes, maal 4 edges). Als je de oplossing speciek voor deze dag schrijft met een paar integer arrays, denk ik zeker dat 't een stuk sneller gaat zijn.

Voordeel dat ik weer heb is dat als er nog een keer zo'n vraag komt, ik gewoon de input om kan bouwen naar een graph en hey presto; de oplossing.

Wait... de slechte implementatie, is dat die van mij?

[Diderikdm]

Python dag 16

Oh wat een puzzel vond ik dit, heel veel gepriegel en allemaal net niet (kwam door mezelf)..

spoiler:

Dan maar een append method maken omdat je niet weet of je momenteel met een int of list bezig ben

^ aangepast in refactor (gelukkig)

..en nu is het spijkerschrijft

[ Voor 44% gewijzigd door Diderikdm op 16-12-2021 16:49 ]

[evanraalte]

Pff net werk dit

https://github.com/evanra...ob/master/python/day16.py dit heeft heel veel behoefte aan een refactor, maar momenteel niet zo'n zin in:)

[Remcoder]

Nou, toch werkend gekregen, o.a. door de code van @Creepy te bestuderen.

Members only:

Alleen zichtbaar voor ingelogde gebruikers. Inloggen

spoiler:

Vooral doordat ik daar zag dat je de positie van de pointer teruggaf, en de lijst van packets meegeeft als parameter om zo te laten vullen. Deel 2 daarna wel volledig op eigen houtje in elkaar gekrast

Oh wauw, ik zit nu ook in de top 10.000 van vandaag

[Janoz]

Code nog een beetje opgeschoond

https://github.com/Janoz-...com/janoz/aoc/y2021/day16

spoiler:

En net als @Remcoder had ik geen zin om de integer parser met prefix geneuzel te gebruiken en gewoon snel even de 16 gevallen uit te schrijven in een switch

[EfBe]

Day 16: https://github.com/FransB...src/AoC2021.Code/Day16.cs

spoiler:

LL(1) parsertje die gebruik maakt van een array van '0' of '1' chars, dat vond ik het makkelijkst. .NET heeft wel een BitArray class maar die heeft de onnozele eigenschap dat de bit op 0 is de least significant bit en hier wilde je dat echt niet. Verder straight forward.

Ben het zeker eens met bovenstaande posts dat deze opdracht echt niet fun was. Ik weet het zo langzamerhand wel hoe dit probleem opgelost moet worden en dan extra ingewikkelde input te moeten handlen 'omdat het anders te simpel is' maakt het niet moeilijker, maar maakt het gewoon meer werk. Naja... morgen maar hopen op een topological sort, dan ben ik weer wat sneller klaar

[ Voor 33% gewijzigd door EfBe op 16-12-2021 13:02 ]

[gedonie]

Even in de lunch toch nog maar dag 16 in Java.

spoiler:

Wat een geklooi om die sub stukken goed te krijgen zeg. En het is ook lastig om te achterhalen als het fout gaat waardoor. Gelukkig zaten er vandaag wel veel voorbeelden bij.

[Varienaja]

Lees en huiver: Java dag 16

[tarlitz]

iThinkSo schreef op donderdag 16 december 2021 @ 10:32:
Dag 16 in Python


https://github.com/Synthe...84304cabdd/day16/day16.py

spoiler:

Goede usecase voor iterators, wel de eerste dag dat ik er een externe library bijgehaald heb (more_itertools)

Mooi gedaan! Ik zat echt enorm te prutsen, toen ik zag hoe jij je data opslaat heb ik dat ook toegepast en rolde het antwoord er zo uit 😅

[Remcoder]

spoiler:

Toch maar even een print functie toegevoegd. Ik was wel benieuwd wat voor formule er nu precies uitgevoerd is. Wel interessant om te zien wat er allemaal in zit, vooral de lading geneste min/max/+/*

Aanschouw: https://pastebin.com/S5tAT5Bf

[coop]

Dag 16 in Python

Goed lezen en veel werk, maar on to the next.

[breew]

ok... ik heb denk ik ergens een stukje uitleg gemist.. maar ik loop te klooien met deze dag..

For example, here is an operator packet (hexadecimal string 38006F45291200) with length type ID 0 that contains two sub-packets:

00111000000000000110111101000101001010010001001000000000
VVVTTTILLLLLLLLLLLLLLLAAAAAAAAAAABBBBBBBBBBBBBBBB

    The three bits labeled V (001) are the packet version, 1.
    The three bits labeled T (110) are the packet type ID, 6, which means the packet is an operator.
    The bit labeled I (0) is the length type ID, which indicates that the length is a 15-bit number representing the number of bits in the sub-packets.
    The 15 bits labeled L (000000000011011) contain the length of the sub-packets in bits, 27.
    The 11 bits labeled A contain the first sub-packet, a literal value representing the number 10.
    The 16 bits labeled B contain the second sub-packet, a literal value representing the number 20.

Waarom hebben A en B hier de lengten die ze hebben (11 en 16)? IK snap dat ze samen 27 lengte moeten hebben...
maar waarom is het 11 en 16 in dit voorbeeld, en niet 9 en 18?

[Creepy]

breew schreef op donderdag 16 december 2021 @ 14:02:
ok... ik heb denk ik ergens een stukje uitleg gemist.. maar ik loop te klooien met deze dag..

For example, here is an operator packet (hexadecimal string 38006F45291200) with length type ID 0 that contains two sub-packets:

00111000000000000110111101000101001010010001001000000000
VVVTTTILLLLLLLLLLLLLLLAAAAAAAAAAABBBBBBBBBBBBBBBB

    The three bits labeled V (001) are the packet version, 1.
    The three bits labeled T (110) are the packet type ID, 6, which means the packet is an operator.
    The bit labeled I (0) is the length type ID, which indicates that the length is a 15-bit number representing the number of bits in the sub-packets.
    The 15 bits labeled L (000000000011011) contain the length of the sub-packets in bits, 27.
    The 11 bits labeled A contain the first sub-packet, a literal value representing the number 10.
    The 16 bits labeled B contain the second sub-packet, a literal value representing the number 20.

Waarom hebben A en B hier de lengten die ze hebben (11 en 16)? IK snap dat ze samen 27 lengte moeten hebben...
maar waarom is het 11 en 16 in dit voorbeeld, en niet 9 en 18?

A is een header (3 bits) + type (3 bits) + nummer (5 bits). Waarom zou dat 9 bits moeten zijn volgens jou?
Edit: ja, van die 5 bits zijn de laatste 4 het nummer zelf, de eerst geeft aan of er nog meer volgen of niet, in dit geval niet

[ Voor 4% gewijzigd door Creepy op 16-12-2021 14:06 ]

[Mschamp]

breew schreef op donderdag 16 december 2021 @ 14:02:
ok... ik heb denk ik ergens een stukje uitleg gemist.. maar ik loop te klooien met deze dag..

For example, here is an operator packet (hexadecimal string 38006F45291200) with length type ID 0 that contains two sub-packets:

00111000000000000110111101000101001010010001001000000000
VVVTTTILLLLLLLLLLLLLLLAAAAAAAAAAABBBBBBBBBBBBBBBB

    The three bits labeled V (001) are the packet version, 1.
    The three bits labeled T (110) are the packet type ID, 6, which means the packet is an operator.
    The bit labeled I (0) is the length type ID, which indicates that the length is a 15-bit number representing the number of bits in the sub-packets.
    The 15 bits labeled L (000000000011011) contain the length of the sub-packets in bits, 27.
    The 11 bits labeled A contain the first sub-packet, a literal value representing the number 10.
    The 16 bits labeled B contain the second sub-packet, a literal value representing the number 20.

Waarom hebben A en B hier de lengten die ze hebben (11 en 16)? IK snap dat ze samen 27 lengte moeten hebben...
maar waarom is het 11 en 16 in dit voorbeeld, en niet 9 en 18?

Door dit stukje:

code:

The five bits labeled A (10111) start with a 1 (not the last group, keep reading) and contain the first four bits of the number, 0111.
The five bits labeled B (11110) start with a 1 (not the last group, keep reading) and contain four more bits of the number, 1110.
The five bits labeled C (00101) start with a 0 (last group, end of packet) and contain the last four bits of the number, 0101.

Je leest in per 5 bits. De eerste zegt of je nog een groep moet inlezen, of dat het de laatste was

[Diderikdm]

breew schreef op donderdag 16 december 2021 @ 14:02:
ok... ik heb denk ik ergens een stukje uitleg gemist.. maar ik loop te klooien met deze dag..

For example, here is an operator packet (hexadecimal string 38006F45291200) with length type ID 0 that contains two sub-packets:

00111000000000000110111101000101001010010001001000000000
VVVTTTILLLLLLLLLLLLLLLAAAAAAAAAAABBBBBBBBBBBBBBBB

    The three bits labeled V (001) are the packet version, 1.
    The three bits labeled T (110) are the packet type ID, 6, which means the packet is an operator.
    The bit labeled I (0) is the length type ID, which indicates that the length is a 15-bit number representing the number of bits in the sub-packets.
    The 15 bits labeled L (000000000011011) contain the length of the sub-packets in bits, 27.
    The 11 bits labeled A contain the first sub-packet, a literal value representing the number 10.
    The 16 bits labeled B contain the second sub-packet, a literal value representing the number 20.

Waarom hebben A en B hier de lengten die ze hebben (11 en 16)? IK snap dat ze samen 27 lengte moeten hebben...
maar waarom is het 11 en 16 in dit voorbeeld, en niet 9 en 18?

spoiler:

De uitleg van type 4 dekt dit de eerste 6 bits van de 11 zijn de V en T (T=4), de 5 bits hierna beginnen met een 0 (laatste package). Voor die van 16 bits -> eerste 6 = V & T (T=4), de 5 bits hierna begint met een 1, dus niet laatste package, de 5 hierna wel met een 0, dus laatste package

[breew]

Creepy schreef op donderdag 16 december 2021 @ 14:05:
[...]

A is een header (3 bits) + type (3 bits) + nummer (5 bits). Waarom zou dat 9 moeten zijn?

duh.. ik raakte helemala de weg kwijt.. een sub-packet heeft weer een eigen version en type... ok dan.
Wat een gepriegel dit... Dacht het ff in de luchtijd op te pikken ;-)

Mschamp schreef op donderdag 16 december 2021 @ 14:06:
[...]


Door dit stukje:

code:

The five bits labeled A (10111) start with a 1 (not the last group, keep reading) and contain the first four bits of the number, 0111.
The five bits labeled B (11110) start with a 1 (not the last group, keep reading) and contain four more bits of the number, 1110.
The five bits labeled C (00101) start with a 0 (last group, end of packet) and contain the last four bits of the number, 0101.

Je leest in per 5 bits. De eerste zegt of je nog een groep moet inlezen, of dat het de laatste was

je.. hebbes tnx

[Hydra]

armageddon_2k1 schreef op donderdag 16 december 2021 @ 11:15:
Wait... de slechte implementatie, is dat die van mij?

Hmm? Nee. Ik had eergister van je gejat, niet gister

[breew]

Diderikdm schreef op donderdag 16 december 2021 @ 14:07:
[...]

spoiler:

De uitleg van type 4 dekt dit de eerste 6 bits van de 11 zijn de V en T (T=4), de 5 bits hierna beginnen met een 0 (laatste package). Voor die van 16 bits -> eerste 6 = V & T (T=4), de 5 bits hierna begint met een 1, dus niet laatste package, de 5 hierna wel met een 0, dus laatste package

[iThinkSo]

tarlitz schreef op donderdag 16 december 2021 @ 13:40:
[...]


Mooi gedaan! Ik zat echt enorm te prutsen, toen ik zag hoe jij je data opslaat heb ik dat ook toegepast en rolde het antwoord er zo uit 😅

Nu ook wel benieuwd wat je er dan uiteindelijk van gemaakt hebt

[tarlitz]

iThinkSo schreef op donderdag 16 december 2021 @ 14:14:
[...]


Nu ook wel benieuwd wat je er dan uiteindelijk van gemaakt hebt

Dit is 'm geworden ^^
https://pastebin.com/u5BKcVTA

[Devilfish]

Met deel 1 wel even lopen prutsen, ging iets mis met Enumerables, waardoor die me steeds opnieuw de eerste bits gaf. Deel 2 ging daarna gelukkig erg snel.

spoiler:

Dag 16 in C#

[Varienaja]

Soultaker schreef op donderdag 16 december 2021 @ 01:10:
Ik snap niet waarom de Java/Kotlin oplossingen voor dag 15 allemaal zo traag zijn terwijl m'n Python oplossing in 500 ms draait. Is de Java priority queue slecht geoptimaliseerd ofzo? Of zit er toch een bug in het algoritme van de deelnemers die deze taal gebruiken?

Ik vond dat ook heel verdacht. Met name omdat jouw implementatie eigenlijk alleen daarin verschilt dat je een int[][] array gebruikt en ik een HashMap<Point,Long> voor de gewichten in de grid.

Ik heb de hashCode van mijn Point veranderd, zodat ze 'unieker' zijn. Runtime 1s in plaats van 3.
HashCode van een Point construct-time berekenen ipv iedere keer opniew bij een call geeft 0,8s ipv 1.

Het is wel goed om maar weer eens met de neus op de feiten gedrukt te worden. Veel mooie datastructuren zijn niet gratis. Verre van!

[KabouterSuper]

Pfft. Het werkt. Maar ik snap mijn code nog steeds niet helemaal. Er zit ergens iets impliciets in over welk gedeelte van de string overblijft nadat ik er een operator-opdracht af heb gesloopt. Anyway, morgen weer een kans om wat mooiere code te schrijven.

[Cranzai]

Man man man, wat zijn die overblijfende nullen toch verschikkelijk irritant, ben er nog niet goed uit hoe ik die weg moet slopen. Voor de literal values is het goed te bedenken, er is immers een regel voor gegeven. Voor de operators daarentegen is het een grote chaos.

[Diderikdm]

Cranzai schreef op donderdag 16 december 2021 @ 18:48:
Man man man, wat zijn die overblijfende nullen toch verschikkelijk irritant, ben er nog niet goed uit hoe ik die weg moet slopen. Voor de literal values is het goed te bedenken, er is immers een regel voor gegeven. Voor de operators daarentegen is het een grote chaos.

spoiler:

The BITS transmission contains a single packet at its outermost layer which itself contains many other packets. The hexadecimal representation of this packet might encode a few extra 0 bits at the end; these are not part of the transmission and should be ignored.

^ Alleen de allerbuitenste BIT heeft (misschien) verloopnullen. Ik heb er ook mn hoofd op gebroken

[Dricus]

Cranzai schreef op donderdag 16 december 2021 @ 18:48:
Man man man, wat zijn die overblijfende nullen toch verschikkelijk irritant, ben er nog niet goed uit hoe ik die weg moet slopen. Voor de literal values is het goed te bedenken, er is immers een regel voor gegeven. Voor de operators daarentegen is het een grote chaos.

Maak je het jezelf niet te moeilijk?

spoiler:

Die "padding" nullen staan alleen maar helemaal aan het einde, na het "root" packet. Ze dienen alleen maar om ervoor te zorgen dat de input in een veelvoud van 4 bits (of zelfs 8?) is uit te drukken.

[Cranzai]

Dricus schreef op donderdag 16 december 2021 @ 18:52:
[...]

Maak je het jezelf niet te moeilijk?

spoiler:

Die "padding" nullen staan alleen maar helemaal aan het einde, na het "root" packet. Ze dienen alleen maar om ervoor te zorgen dat de input in een veelvoud van 4 bits (of zelfs 8?) is uit te drukken.

Grappig, deze had ik precies nodig.

spoiler:

Werk met een deque en wilde in principe een check dr op gooien te stoppen wanneer leeg.
Eigenlijk moet dat dus een check zijn wanneer er geen 1'en meer in zitten.

[Dricus]

Cranzai schreef op donderdag 16 december 2021 @ 18:54:
Grappig, deze had ik precies nodig.

spoiler:

Werk met een deque en wilde in principe een check dr op gooien te stoppen wanneer leeg.
Eigenlijk moet dat dus een check zijn wanneer er geen 1'en meer in zitten.

spoiler:

Feitelijk hoef je maar één packet te decoderen. Zodra je het root packet + zijn subpackets hebt gedecodeerd, ben je klaar. De rest van de bits kun je dan gevoeglijk negeren. Bij een recursieve oplossing, zoals de mijne, is het decoderen een kwestie van het aanroepen van één functie.

[Kazu]

Boh, ben er nu mee bezig, maar het is geen leuke puzzel. Het is geen uitdaging, gewoon door blijven uitwerken.

spoiler:

Ook een kwestie van blijven lezen. Kom er net achter dat het niet voldoende is om de versions te summen van de hoofdpackets, maar ik ook nog alle nested sub-packets door moet werken. Blegh, niet echt zin in, dus ik denk niet dat ik me kan motiveren om deze vandaag af te maken.

[DataGhost]

Dit is vooral een uitdaging van het probleem in de juiste structuur lezen, dan wordt het een "fluitje van een cent". Dit is niet zozeer algoritmisch moeilijk waarbij de code langzaam is met het resultaat uitrekenen, maar ontwerptechnisch moeilijk waarbij het maken van de code lang en moeilijk kan zijn als je een sub-optimaal ontwerp hebt. Dat is de uitdaging van vandaag.

[Daos]

Ik vond hem wel leuk om te doen. Heb van boven naar onderen de voorbeelden geimplementeerd en gaande weg zag ik steeds ruimte voor verbetering. Deel 2 werkte bovendien in 1 keer op de echte input. Dat geeft ook wel voldoening. In totaal anderhalf uur mee bezig geweest. https://github.com/gjscho...b/master/Day16/Program.cs

[Cranzai]

Lang genoeg gepuzzeld met deze opdracht, heb uiteindelijk een list van operators en een list van waardes laten printen. Vervolgens deel B maar handmatig uitgerekend, want ik moest en zal dat domme sterretje van de dag binnenhalen.

Zit met mijn huidige format waarschijnlijk dicht bij oplossing waarin ik eenvoudig de post-processing kan verwerken maar ik ben dr klaar mee.

[Reynouts]

Heb een tijdje vastgezeten door de manier waarop ik hex naar binary omzette. Daardoor werden mogelijke leading zeros weggegooid (wat toevallig ook in m'n input zat). Maar voordat ik erachter was dat dat het zou kunnen zijn...

Ben benieuwd of hier weer op verder geborduurd gaat worden!

[Creepy]

Ik heb speciaal voor dag 16 leftpad gebruikt, nu zit die bij Java gewoon in 1 grote lib (apache-commons3). maar toch voelde het een beetje vies . Ik had alleen geen zin om die zelf te schrijven.

[NickThissen]

Zucht... veel te lang vast gezeten op

spoiler:

de product package. Lekker in een loop:

running_total *= execute_packet(p)

bijhouden. En dan running_total initializeren op 0

[Janoz]

Creepy schreef op donderdag 16 december 2021 @ 22:59:
Ik heb speciaal voor dag 16 leftpad gebruikt, nu zit die bij Java gewoon in 1 grote lib (apache-commons3). maar toch voelde het een beetje vies . Ik had alleen geen zin om die zelf te schrijven.

Had ik geen zin in, ik heb gewoon een switch met 16 cases gedaan. Beetje knippen en plakken en ik was van al het gedoe af. Is nog sneller dan leftpad ook

[zwippie]

Leuk, ik heb vandaag een hoop geleerd over het parsen van bitstrings in Elixir, dat zou namelijk 'eenvoudig en snel' moeten kunnen gaan.

Eenvoudig: nee, best veel gotchas, hele avond over gedaan. Kan vast nog wel cleaner.

Snel: ja, gebenchmarkt met benchee en dag 16 a/b doen er beide minder dan 1ms over.

Pattern matching en recursie FTW! Kom maar eens in een andere taal met zo'n all-in-one function header:

code:

defp parse(<<version::3, type::3, 0::1, sub_length::15, subpacketbits::size(sub_length), rest::bitstring>>, packets) do

Counterpoint: Voor dag 15b kom ik niet verder dan het generen van een foutief antwoord in 13 seconden.

spoiler:

Dag 15 dacht ik, net als velen, op te kunnen lossen met een graph library (lui) met een a-star functie en de manhattan distance als lower bound functie. Deel 1 en alle voorbeelden doen het helemaal snel en prima, maar deel 2 geeft consequent een te laag antwoord na 13s. Ondanks veel checks zal het dan toch wel in m'n grid-multiply zitten, want: te laag. ?

[Varienaja]

Misschien vindt iemand het leuk om mijn ongecensureerde kladcode voor vandaag te zien. Opgeschoond. Java dag 17

[ Voor 5% gewijzigd door Varienaja op 17-12-2021 12:03 ]

[P_Tingen]

Varienaja schreef op vrijdag 17 december 2021 @ 06:22:
Misschien vindt iemand het leuk om mijn ongecensureerde kladcode voor vandaag te zien.
***members only***

Ik ken deel 2 nog niet maar iets zegt me dat dit daar niet voor gaat werken, deze oplossingsrichting ligt iets te veel voor de hand ben ik bang....

[MrHaas]

Varienaja schreef op vrijdag 17 december 2021 @ 06:22:
Misschien vindt iemand het leuk om mijn ongecensureerde kladcode voor vandaag te zien.
***members only***

spoiler:

Ik heb vandaag ook snel iets in elkaar gebodged met educated guess ranges om in te zoeken. Zo maar ff netter maken

[Diderikdm]

Python dag 17

spoiler:

Er zal denk ik wel een formule zijn om hier part 1 & 2 op uit te rekenen, toch gekozen voor bruteforce

Stilte voor de storm voor dit weekend?

[Mschamp]

Diderikdm schreef op vrijdag 17 december 2021 @ 08:15:
Python dag 17

spoiler:

Er zal denk ik wel een formule zijn om hier part 1 & 2 op uit te rekenen, toch gekozen voor bruteforce

Stilte voor de storm voor dit weekend?

Bij mij ging bruteforce ook, en nog behoorlijk snel.
Alleen de eerste keer een fout antwoord omdat ik niet genoeg combinaties probeerde.

Deel 2 voelde eenvoudiger dan deel 1.

[Cranzai]

Interessante opdracht,

spoiler:

numerieke integratie

zou behoorlijk in mijn straatje moeten liggen qua achtergrond. Eens ff kijken of ik dit slim aan kan pakken, vooral vanwege de unieke cut-off en de onbeperkte range aan initiële condities

[armageddon_2k1]

Dag 17 in Kotlin.

Tja, wat zal ik ervan zeggen. Verdient geen schoonheidsprijs . Ik had het wel kunnen overdenken, maar de lompe methode werkte het best.

spoiler:

Waat je nat kan gaan is als je veel alloceert. Daarom alles lazy lazy lazy gemaakt en dan gaat ie verdomde snel (~150ms). Vervolgens een educated guess van maxima en minima aan initiele condities

[Varienaja]

Ik heb m'n bruteforce opgeschoond naar reëlere waarden. In plaats van 10 miljard simulatiestappen bereken ik er nu ongeveer 350.000. Dat gaat 'iets' sneller.

[Hydra]

Dag 17 in Kotlin

Deze was vrij simpel en ik had door mijn aanpak ook meteen het antwoord voor deel 2.

[deboder]

Mijn Q2
( ik kwam zo niet op die makkelijke formule voor Q1 en had toch al een app gemaakt om te plotten )

spoiler:

[KabouterSuper]

Diderikdm schreef op vrijdag 17 december 2021 @ 08:15:
Python dag 17

spoiler:

Er zal denk ik wel een formule zijn om hier part 1 & 2 op uit te rekenen, toch gekozen voor bruteforce

Stilte voor de storm voor dit weekend?

Of na de storm van gisteren. Vandaag was een makkie.

[Remcoder]

Members only:

Alleen zichtbaar voor ingelogde gebruikers. Inloggen

spoiler:

Tsja, soms is brute force wél de beste oplossing. Ik verwacht dat er ergens wel een formule voor is.

[KabouterSuper]

Remcoder schreef op vrijdag 17 december 2021 @ 09:29:
***members only***

spoiler:

Tsja, soms is brute force wél de beste oplossing. Ik verwacht dat er ergens wel een formule voor is.

Ik betwijfel of er een gemakkelijke formule is. Je kunt de minimale en maximale horizontale snelheid wel vrij gemakkelijk bepalen.

spoiler:

minimaal: v*(v+1)/2>=kleinste x-coordinaat van target (want dit is de maximale afstand die je kunt bereiken)
maximaal: v<=grootste x-coordinaat van target (want dit wordt na 1 stap bereikt)

Wat betreft de verticale snelheid:

spoiler:

minimaal: v>=kleinste y-coordinaat (want dit wordt na 1 stap bereikt).
maximaal: als je de minimale horizontale snelheid aanhoudt en je wilt zo hoog mogelijk, dan kom je uiteindelijk weer uit op y=0 (want de y-coordinaat volgt een symmetrisch pad). Dus de volgende stap mag geen overshoot zijn, dus v<=-1*kleinste y-coordinaat

Maar binnen dit gebied weet ik niet of je nog heel veel meer kunt doen. Anyway, met deze afschattingen een antwoord in 3.5 sec.

[ Voor 6% gewijzigd door KabouterSuper op 17-12-2021 09:56 ]

[Varienaja]

KabouterSuper schreef op vrijdag 17 december 2021 @ 09:54:
Anyway, met deze afschattingen een antwoord in 3.5 sec.

spoiler:

Ah super. Nu heb je me al verraden wat de minimum snelheid voor x is, en de maximum voor y. Daar wou ik later nog op broeden.

Hiermee hoef ik nog maar iets meer dan 120.000 stappen te simuleren, alweer 3x minder dan daarnet. Mijn runtime zat al op 'onmeetbaar' weinig. (Unittest in 0.000s uitgevoerd). En nu nog 3x minder dus. Ik vind 3,5s daarom wel heel erg overdreven.

[Remcoder]

KabouterSuper schreef op vrijdag 17 december 2021 @ 09:54:
[...]

Maar binnen dit gebied weet ik niet of je nog heel veel meer kunt doen. Anyway, met deze afschattingen een antwoord in 3.5 sec.

Dat kan efficienter, op mijn laptop draai ik zelfs alle test cases van alle dagen in minder dan 3 seconden.

[armageddon_2k1]

Nu ook nog Dag 16 in Kotlin. Dag 17 al hierboven beantwoord. Gister was ik te druk om Dag 16 te doen, dus vandaag dus maar twee tegelijk.

Dag 16 was leuk en afgezien van het leeswerk makkelijk

[Creepy]

En ook klaar met dag 17. Ik wilde eerst kijken of ik hem kon benaderen ipv bruteforce, maar uiteindelijk toch gekozen voor de bruteforce method. Ik had niet verwacht dat dat zo snel zou zijn (20ms voor beide delen samen)

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

spoiler:

Begin en eind bepalen is dan wel een ding. Op gevoel gegokt en daarna aan de spoiler van @KabouterSuper gezien dat ik met mijn gok aardig in de buurt zat . En gelukkig voor de bruteforce methode gekozen zodat deel 2 bijna gratis was.

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

[Janoz]

KabouterSuper schreef op vrijdag 17 december 2021 @ 09:54:
[...]

Ik betwijfel of er een gemakkelijke formule is. Je kunt de minimale en maximale horizontale snelheid wel vrij gemakkelijk bepalen.

spoiler:

minimaal: v*(v+1)/2>=kleinste x-coordinaat van target (want dit is de maximale afstand die je kunt bereiken)
maximaal: v<=grootste x-coordinaat van target (want dit wordt na 1 stap bereikt)

Wat betreft de verticale snelheid:

spoiler:

minimaal: v>=kleinste y-coordinaat (want dit wordt na 1 stap bereikt).
maximaal: als je de minimale horizontale snelheid aanhoudt en je wilt zo hoog mogelijk, dan kom je uiteindelijk weer uit op y=0 (want de y-coordinaat volgt een symmetrisch pad). Dus de volgende stap mag geen overshoot zijn, dus v<=-1*kleinste y-coordinaat

Maar binnen dit gebied weet ik niet of je nog heel veel meer kunt doen. Anyway, met deze afschattingen een antwoord in 3.5 sec.

Volgens mij klopt hij niet helemaal

spoiler:

Ten eerste ga je er nu allen vanuit dat het target onder 0 zit. Je hebt ook nog het geval waarbij het target boven 0 zit. Daarnaast kan voor het target onder 0 de velocity 1 stap kleiner omdat je een extra stap doet om onder 0 te komen.


Ikzelf heb nu max(top, (-1*bottom)-1) waardoor ik uiteindelijk maar 420 of 32.314 simulaties hoef te doen

[Diderikdm]

spoiler:

Toch even gaan nadenken voor part 2:

De minimale vx waarde die goed is, is de eerste (n * (n+1) // 2) die tussen (minx,maxx) valt, omdat dit de eerste waarde is waarbij x binnen de range van het vlak stilvalt. Hierdoor zal er /een/ waarde voor vy zijn waardoor deze in het vlak valt.

De max vx die goed is, is maxx, omdat na 1 iteratie de uiterste rand van het vlak is bereikt

de minimale vy waarde is miny (omdat je anders per definitie onder het vlak komt)

de maximale vy waarde lijkt de zijn:

abs(miny) - 1, ofwel, gespiegeld in de x-as 1 hoger dan de hoogste y van het vlak.

Ik ga even kijken of ik hier nog iets zinnigs van kan maken verder..

[EfBe]

Day 17: https://github.com/FransB...src/AoC2021.Code/Day17.cs

spoiler:

Was nog even een gevecht tussen welke waarden ik de input moest bruteforcen, maar nadat die gezet waren was het simpel. Puzzle 2 was simpel want ik bewaarde alle trajectories al, moest 1 dingetje aanpassen (beginvalue voor Y), aangezien ik bij de top Y begon maar moest bij de bottom Y beginnen.

[ Voor 4% gewijzigd door EfBe op 17-12-2021 11:53 ]

[KabouterSuper]

Janoz schreef op vrijdag 17 december 2021 @ 11:44:
[...]

spoiler:

Ten eerste ga je er nu allen vanuit dat het target onder 0 zit. Je hebt ook nog het geval waarbij het target boven 0 zit. Daarnaast kan voor het target onder 0 de velocity 1 stap kleiner omdat je een extra stap doet om onder 0 te komen.

Het target is een trench in de oceaanbodem, dus is het niet altijd zo dat het target onder 0 zit? Als het target boven 0 zit, wordt het inderdaad iets anders.

[Janoz]

KabouterSuper schreef op vrijdag 17 december 2021 @ 11:51:
[...]

Het target is een trench in de oceaanbodem, dus is het niet altijd zo dat het target onder 0 zit? Als het target boven 0 zit, wordt het inderdaad iets anders.

Heb je een punt inderdaad, maar dan nog geld de -1 toevoeging van mij ..

Hij wordt helemaal mooi wanneer het target over de x-as ligt. Dan zijn beide antwoorden oneindig

[Diderikdm]

spoiler:

Voor alle waarden van minx <= vx <= maxx kan je er vanuit gaan dat dat betekent dat vy moet zijn: miny <= vy <= maxy -> de eerste iteratie moet namelijk in het vlak terecht komen..

^Hiervoor kan je (maxx - minx + 1) * (maxy - miny + 1) doen.

Je kunt verder alle waarden van vx skippen die: (vx < minx and vx + vx-1 > maxx). Deze gaan nooit in het vlak komen...

[KabouterSuper]

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


Heb je een punt inderdaad, maar dan nog geldt de -1 toevoeging van mij ..

Klopt helemaal. Ik was te lui om het helemaal netjes te doen.

Janoz schreef op vrijdag 17 december 2021 @ 11:53:
[...]
Hij wordt helemaal mooi wanneer het target over de x-as ligt. Dan zijn beide antwoorden oneindig

Haha, dat had ik me helemaal niet gerealiseerd.

[FrankMennink]

Dag 17 in Python

Ik helemaal blij dat ik een manier had gevonden dat ik niet brute force door alles heen hoef voor deel 1.

spoiler:

x coordinaat maakt niks uit voor deel 1, we schieten zo hoog dat we al gauw aan een verticale val bezig zijn. Zolang er maar een x is waarvoor we in ieder geval het doel bereiken.
Ook hoef je niet alle Y's door. bij een positieve start Y kom je altijd uiteindelijk op y=0 terecht. De eerst volgende stap die je richting Y doet is de start Y + 1. De voorgaande boog is maximaal als je in 1 stap direct op de uiterste Y lijn terecht komt. Hieruit volgt dat de som van de getallen 1 tot de uiterste Y lijn (positief gemaakt) de hoogst mogelijke hoogte is.

Toen kwam deel 2 en dat toch maar brute force gedaan Wel met wat limieten op de ranges waardoor deel 2 netjes in 36ms draait

[ Voor 4% gewijzigd door FrankMennink op 17-12-2021 12:25 ]

[KabouterSuper]

FrankMennink schreef op vrijdag 17 december 2021 @ 12:22:
Dag 17 in Python

Ik helemaal blij dat ik een manier had gevonden dat ik niet brute force door alles heen hoef voor deel 1.

spoiler:

x coordinaat maakt niks uit voor deel 1, we schieten zo hoog dat we al gauw aan een verticale val bezig zijn. Zolang er maar een x is waarvoor we in ieder geval het doel bereiken.
Ook hoef je niet alle Y's door. bij een positieve start Y kom je altijd uiteindelijk op y=0 terecht. De eerst volgende stap die je richting Y doet is de start Y + 1. De voorgaande boog is maximaal als je in 1 stap direct op de uiterste Y lijn terecht komt. Hieruit volgt dat de som van de getallen 1 tot de uiterste Y lijn (positief gemaakt) de hoogst mogelijke hoogte is.

Toen kwam deel 2 en dat toch maar brute force gedaan Wel met wat limieten op de ranges waardoor deel 2 netjes in 36ms draait

spoiler:

Je kunt de sommen vermijden als je gebruikt dat (disclaimer: typefouten en +/-1 foutjes):
1+2+....+n=n*(n+1)/2 (let op: ik moest n*(n-1)/2 invullen, dus er zit ergens een 0/1 dingetje in)
x*(x+1)/2>=m -> x>=math.floor((1/4+2*m)**(1/2))-1

[Diderikdm]

spoiler:

a = maxy-miny + 1
for tx in range(next((x for x in range(minx) if (x * (x+1) // 2) >= minx)), maxx + 1)[::-1]:
temp[tx] = []
x = tx
tot_x = 0
i = 0
while tot_x <= maxx and x > 0:
tot_x += x
x -= 1
i += 1
if minx <= tot_x <= maxx:
temp[tx] += [i]
tot = 0
for x in temp[tx]:
tot += ceil(a/x)
print(tx, tot)

print(temp)

Hiermee kom je al redelijk in de buurt en kan je een bulk vxen berekenen.. Totdat er getallen voor vx komen waarbij 3+ mogelijkheden zijn om in het vlak te landen (bijvoorbeeld 27 -> 27+26+25, 27+26+25+24, 27+26+25+24+23) 70 <= x <= 125), vanaf dit punt gaan snijdvlakken door het aanpassen van de vy ook meewegen..

Nu kap ik ermee, maar het lijkt alsof je alleen (op dit moment en bij mijn input) 15 vxen hoeft te bruteforcen en de rest zou je kunnen berekenen

[KabouterSuper]

Diderikdm schreef op vrijdag 17 december 2021 @ 08:15:
Python dag 17

spoiler:

Er zal denk ik wel een formule zijn om hier part 1 & 2 op uit te rekenen, toch gekozen voor bruteforce

Gaat je bepaling van h wel goed?

spoiler:

x, y, h = x + vx, y + vy, max(h,y)
is toch niet hetzelfde als:
x=x+vx
y=y+vy
h=max(h,y)
?
In mijn code hoog ik eerst y op en daarna h. Jij doet het simultaan, waardoor je met de oude y rekent als je h berekent.
Het maakt in dit geval geen fluit uit voor het antwoord, maar ik had dit verwacht:
x, y, h = x + vx, y + vy, max(h,y+vy)

[Diderikdm]

KabouterSuper schreef op vrijdag 17 december 2021 @ 12:50:
[...]

Gaat je bepaling van h wel goed?

spoiler:

x, y, h = x + vx, y + vy, max(h,y)
is toch niet hetzelfde als:
x=x+vx
y=y+vy
h=max(h,y)
?
In mijn code hoog ik eerst y op en daarna h. Jij doet het simultaan, waardoor je met de oude y rekent als je h berekent.
Het maakt in dit geval geen fluit uit voor het antwoord, maar ik had dit verwacht:
x, y, h = x + vx, y + vy, max(h,y+vy)

Scherp, inderdaad! Gelukje gehad hier dat niet direct na dit punt iets gedaan hoefde te worden

[FrankMennink]

KabouterSuper schreef op vrijdag 17 december 2021 @ 12:36:
[...]

spoiler:

Je kunt de sommen vermijden als je gebruikt dat (disclaimer: typefouten en +/-1 foutjes):
1+2+....+n=n*(n+1)/2 (let op: ik moest n*(n-1)/2 invullen, dus er zit ergens een 0/1 dingetje in)
x*(x+1)/2>=m -> x>=math.floor((1/4+2*m)**(1/2))-1

Thanks die kende ik nog niet

spoiler:

dit werkt overigens alleen als de range voor de X niet vele malen groter is dan de Y, anders zit je niet in het scenario voor de vrije val (aka x velocity = 0 wanneer je y=0 bereikt)

[bakkerjangert]

Remcoder schreef op vrijdag 17 december 2021 @ 09:29:
***members only***

spoiler:

Tsja, soms is brute force wél de beste oplossing. Ik verwacht dat er ergens wel een formule voor is.

Voor deel 1 is wel een gemakkelijke oplossing te bepalen.

spoiler:

Als ie weer naar beneden gaat komen alle positieve y-waarden nogmaals terug en dus ook y = 0. De verticale snelheid is gelijk aan startsnelheid + 1 maar dan neerwaarts in dat punt. Hoogste punt bereik je met de hoogste snelheid op dat punt. Met dat gegeven en een geven minimale y-waarde, die je een stap later moet bereiken (maximale snelheid) kun je dus makkelijk berekenen wat het antwoord is. Voor deel 2 heb ik ranges van de startwaarden berekend, en daarmee m.b.v. een yield functie een tijdtabel voor x en y opgesteld. Als een tijd zowel in de x als de y tabel voorkomt is er een match. Code in Python (ben hobbyist, vandaar nog wel wat spagheti code hier en daar; hopelijk kunnen jullie me dat vergeven )

[KabouterSuper]

Diderikdm schreef op vrijdag 17 december 2021 @ 12:49:

spoiler:

a = maxy-miny + 1
for tx in range(next((x for x in range(minx) if (x * (x+1) // 2) >= minx)), maxx + 1)[::-1]:
temp[tx] = []
x = tx
tot_x = 0
i = 0
while tot_x <= maxx and x > 0:
tot_x += x
x -= 1
i += 1
if minx <= tot_x <= maxx:
temp[tx] += [i]
tot = 0
for x in temp[tx]:
tot += ceil(a/x)
print(tx, tot)

print(temp)

Hiermee kom je al redelijk in de buurt en kan je een bulk vxen berekenen.. Totdat er getallen voor vx komen waarbij 3+ mogelijkheden zijn om in het vlak te landen (bijvoorbeeld 27 -> 27+26+25, 27+26+25+24, 27+26+25+24+23) 70 <= x <= 125), vanaf dit punt gaan snijdvlakken door het aanpassen van de vy ook meewegen..

Nu kap ik ermee, maar het lijkt alsof je alleen (op dit moment en bij mijn input) 15 vxen hoeft te bruteforcen en de rest zou je kunnen berekenen

Fraaie analyse.

spoiler:

Ik had bedacht dat je het geval voor omhoog schieten kunt vervangen door het geval dat je met dezelfde snelheid naar beneden schiet. Met vy=verticale beginsnelheid: na 2*vy+1 stappen ben je weer bij y=0, maar dan met snelheid -vy. In die tijd ben je naar rechts gegaan en is je horizontale snelheid afgenomen. Deze twee kan je exact berekenen omdat je het aantal stappen weet.

Voor het geval vy<0 kan je analytisch bepalen hoeveel tijdsstappen het duurt voordat je in de verticale range zit. Je bepaalt namelijk wanneer je voorbij de bovenkant schiet en wanneer voorbij de onderkant. Alle gehele getallen ertussen zijn potentiele oplossingen.
Voor deze tijdstippen, kan je uitzoeken voor welke vx je in de horizontale range zit.

Hiermee hoef je alleen maar over je verticale snelheden te loopen in plaats van een dubbele loop over vx en vy.

Maar ik vind het ook genoeg geweest voor vandaag.

[Cranzai]

vandaag was goed te doen, in eerste instantie mijn ranges wat te breed gekozen.
Daarna al mijn calculus bij elkaar geraapt om tot wat betere ranges te komen.
Easy peasy, lemon squeezy

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

[Devilfish]

Deel 2 was erg simpel deze keer als je de eerste niet te slim hebt opgelost Wel leuk om eens met record struct te doen ipv record types, want dat scheelt toch al gauw 30% (van 18ms naar 12ms).

spoiler:

Dag 17 in C#

[Cranzai]

Waar ik nog over zat te filosoferen, zou je ook een soort reverse oplossing kunnen maken waarbij je terug werkt van alle punten in de target area naar de origin?