Advent of Code 2023

[Remcoder]

spoiler:

Op dag 3 heb ik al mijn library van stal kunnen halen. Normaal duurt het langer tot ik daaruit iets nodig heb.

Wel deze keer voor het eerst pretty printing toegevoegd voor het vinden van de bug in mijn code.



https://github.com/remcos...er/adventofcode/Day3.java

[bakkerjangert]

Makkelijk voor mij als Engineer vandaag.

spoiler:

Je hoeft slechts 1 punt te bepalen, het andere kun je dan makkelijk berekenen.

[breew]

Afgelopen dagen druk geweest, vooral in de nachten.. Kom dan niet echt aan lekker coden toe..
En als ik wel even tijd heb, geldt vooral het volgende:


herkenbaar?
lekker laten lopen/loopen en ondertussen koffie halen

[.oisyn]

Lol @ chrome

[Soultaker]

Deel 8 was echt zo'n typische dag waarbij het probleem eigenlijk veel moeilijker is, maar als je een aantal onbezonnen aannames doet over de invoer kun je toch op het goede antwoord komen. Zoals bekend ben ik geen fan van dat soort problemen, maar ja, het hoort een beetje bij AoC.

Voorbeeld van hoe het ingewikkelder kan:

spoiler:

als je ergens midden in de eerste regel de substring "RRRR" toevoegt, geven al jullie oplossingen het verkeerde antwoord (en de mijne ook).

Wat ik dan wel weer leuk vond is om uit te vogelen hoe de invoer precies geconstrueerd is. Het is helemaal niet zo eenvoudig om met de relatief kleine invoer een grote uitvoer te garanderen. Hier is hoe het werkt:

spoiler:

Om te beginnen de string met instructies. Die lijkt random maar dat is 'ie niet: hij eindigt op "RRRR" (bij mij tenminste) en bevat verder nooit meer dan 3 R's op een rij! Toeval? Nee. Dat wordt gebruikt om een lange periode te garanderen.

De invoergraaf bestaat uit verschillende componenten: precies één voor elk begin- en eindpunt. De component bestaat uit een cykel van paren van vertices. Hier een illustratie:



(Je moet er wraparound bij denken: de uitgaande edges aan de rechterkant zijn verbonden aan de edges aan de linkerkant.)

Een paar saillante details:

1. Voor een component met een cykellengte n heb je precies 2n+1 vertices nodig (de vertices aan de rechterkant kun je copy-pasten naar behoeven).
2. De begin- en eindvertex hebben dezelfde uitgaande edges. Daardoor werkt de lcm() truc: als je het eerste eindpunt vindt op tijdstip t, dan vind je het ook weer op 2t, 3t, 4t, etc. (@KabouterSuper merkte al op dat dat niet per se zo hoeft te zijn.)
3. Vlak voor het einde zit een R-detectie sequence! Dit is wat er voor zorgt dat de lengte van de cykel wordt vermenigvuldigd met de lengte van de instructies: je kunt alleen op ZZZ terecht komen als de laatste vier instructies RRRR waren, wat alleen het geval is aan het einde van de instructies.

Deze combinatie garandeert dat het antwoord zo groot mogelijk is. Bijvoorbeeld, mijn invoer heeft een lengte van 271, en de componenten hebben cykellengtes van 79, 53, 59, 61, 71, 73. De periode voor het vinden van een einde zijn door de graafconstructie dus 271×79, 271×53, etc. en aangezien alle getallen in de invoer priemgetallen zijn, is het grootste gemene veelvoud simpelweg het product 271×79×53×59×61×71×73.

[Lisper]

Voor wie vast zit met day 8 is hier een een hint:

spoiler:

het kan helpen om de input to visualizeren.
Ik heb met graphviz een svg gemaakt van transities. (groen = start, rood = end, blauw = r, paars = l)

[torx]

DutchFakeTuber schreef op maandag 18 december 2023 @ 11:15:
Vandaag was een stuk makkelijker vergeleken met de vorige dagen:

spoiler:

Ik heb de Shoelace Formula plus Picks' Theorem gebruikt om de punten binnen de perken te bepalen.
Daarna de grenzen opgeteld door abs(vorige[rij]-huidige[rij]) + abs(vorige[kolom]-huidige[kolom]) uit te voeren op elke coördinaat.

Blijkbaar heb ik hetzelfde gedaan.

spoiler:

Om de area te bepalen voor deel 2 heb ik moeten zoeken en kwam ook op de shoelace formula uit. De randen erbij op te tellen leeg ik mij eenvoudig, maar uiteindelijk kwam ik uit op de helft van de edges plus 1. Leek mij foutgevoelig, maar tot mijn verbazing werkte het op mijn invoer. En nu kom ik er dus achter dat het pick's theorem is

Mijn graafplattegronden:

spoiler:

[P_Tingen]

^%$@^!#$!@ Ik kom niet uit deel 18a wat doe ik fout?

spoiler:

Ik heb de code van dag 10b erbij gehaald maar ook dan lukt het me niet met de odd/even rule.

Stel dat ik zo'n patroon heb:

Dan loop ik per regel er zo doorheen:

- inside := false
- do x = 1 to 7:
- als grid[x] <> grid[x - 1] dan inside = not inside
- als (grid[x] = "#") of (grid[x] = " " en inside = true) dan count++
- end

Dit gaat met de 1e regel goed, maar met de 2e niet. Waar ga ik fout?

[Soultaker]

Okee, het is technisch avond, dus voor mensen die het interessant vinden post ik een aantal hints/uitleg voor deel 2 van dag 18. Ja, je kunt het antwoord ook gewoon van Wikipedia halen, maar het is leuker als je ook begrijpt waarom het werkt. Ik heb meerdere spoilers gemaakt zodat je kunt stoppen met lezen als je het vanaf een bepaald punt verder zelf wil oplossen.

spoiler:

Als je de instructies in de invoer vertaalt naar een polygoon, dan kun je het antwoord berekenen met een simpele formule. Ik illustreer het aan de hand van een voorbeeld: R 3, D 1, R 1, D 2, L 4, U 3.
Zie de afbeelding hier:



Bij deel 1 kun je het pad tekenen in een pixel grid en dan eenvoudig tellen: er liggen 14 pixels op de rand (donkergrijs) en 5 pixels binnenin (lichtgrijs), dus het antwoord is 14 + 5 = 19. Maar pixels tellen is niet zo efficiënt als de coördinaten groot zijn, zoals bij deel 2.

spoiler:

In plaats van te kijken naar pixels, kun je het pad ook zien als een polygoon, waarvan de hoekpunten in het midden van de pixels liggen.

Het voordeel van deze representatie is dat het voor het berekenen van het oppervlak niet uitmaakt hoe groot de coördinaten zijn; alleen hoeveel hoekpunten er zijn, en dat aantal is redelijk beperkt: het aantal regels in de invoer.

De rode polygoon heeft een oppervlak van precies 11 vakjes, wat je in dit voorbeeld makkelijk met de hand kunt tellen, en in je code o.a. met de shoelace formula kunt berekenen. 11 is minder dan het werkelijke antwoord (19), en dat komt natuurlijk omdat je het deel van de rand dat buiten de polygoon valt niet hebt meegeteld. Iets preciezer: je hebt ongeveer de helft van de rand niet meegeteld (maar niet exact!) Daar moet je dus nog wat op verzinnen.

spoiler:

Om te compenseren voor de rand, kun je de helft van de lengte van elk lijnstuk bij het antwoord optellen (de helft, omdat je alleen het deel van de rand buiten de polygoon telt). Dat zijn de groene gebieden in het plaatje hieronder:



De omtrek is 14, de helft is 7. 11 + 7 = 18, en dat is nog net geen 19. Dat komt doordat je hier de zwarte vierkantjes (a, b, d, e, f) die ook op de rand liggen nog niet meegeteld hebt, en het gele vierkantje (c) juist dubbel geteld hebt (als onderdeel van lijnstuk (4,1)-(4,2) én (4,2)-(5,2)). Daar moet je ook nog voor compenseren.

spoiler:

Voor elk convex (naar binnen klappend) hoekpunt mis je een stukje van de rand met oppervlak 0,5 × 0,5 = 0,25, en voor elk concaaf (naar buiten klappend) hoekpunt tel je een gebied van 0,25 dubbel.

spoiler:

Dat kun je compenseren met een factor 0,25×(aantal convexe hoekpunten) - 0,25×(aantal concave hoekpunten). Je kunt die expliciet tellen, maar dat is niet eens nodig.

spoiler:

Het aantal convexe hoekpunten is altijd 4 meer dan het aantal concave hoekpunten. Dat kun je zo inzien: als je met de klok mee rond de polygoon loopt, sla je precies vier keer vaker rechtsaf dan linksaf. Dat komt omdat je in dezelfde oriëntatie eindigt als je begint, dus de totale rotatie moet sowieso een veelvoud van 360 zijn, en aangezien het hier om een simpele polygoon gaat (i.e., zonder zelf-intersectie) is het precies 360, niet meer of minder. Kortom, je moet netto precies 4 hoeken van 90 graden maken. 4×0,25 = 1.

Conclusie:

spoiler:

Als je bovenstaande informatie combineert is het antwoord simpelweg: oppervlak van de polygoon + (omtrek van de polygoon)/2 + 1.

En ja, dat is inderdaad precies dezelfde formule als in Pick's theorem maar die hóef je dus niet te kennen om het antwoord af te leiden voor dit probleem.

Wie z'n algoritme wil testen verwijs ik door naar mijn extra testinvoer voor dit probleem.

[P_Tingen]

MadEgg schreef op maandag 18 december 2023 @ 22:55:
[...]
Je start ziet er zo uit:

code:

     |
     |
-----J
|
|
|
L--------7

Je start ziet er zo uit. De hoek begint met `-` en daarom zal je `J` niet geteld worden als doorgang van de rand omdat `iDir` niet op 1 gezet wordt. Het startpunt gaat niet goed bij de omzetting naar J7LF.

spoiler:

Als je kijkt of er op `pos(iCol, iRow - 1)` een gat zit weet je ook dat er een doorgang is. Dan hoef je de omzetting naar J7LF ook niet te doen, en het iDir gebeuren heb je dan ook niet nodig.

[Bolukan]

spoiler: day 20-part 2

Quick analysis:
Dit suggereert 4 sub-simulaties.

[ Voor 6% gewijzigd door Bolukan op 20-12-2023 11:34 ]

[.oisyn]

spoiler:

@Bolukan Lol ik kwam hier precies hetzelfde posten



Degene met & zijn conjunctions, de rest flipflops. Een serie flipflops is natuurlijk gewoon een binaire counter.

Elke low flipt de bit. Dus de broadcast stuurt elke press een low, dus de bit van de eerste flipflop in de cirkel flipt elke keer. Elke keer dat hij naar low gaat flipt hij de volgende, dus de volgende flipt elke 2 keer, en die daarna dus weer elke 4 keer, etc.

Vervolgens zie je allemaal pijlen naar een conjunction node in het midden, maar niet voor allemaal. Als je de bitwaardes pakt van alle omliggende nodes met een pijl naar het midden, bijvoorbeeld voor die cirkel rechtsonder met &jt in het midden, dan kom je op 0b111101001111, oftewel 3919, precies de periode van een van de inputs van gf (de node voor rx). De 3919e stap zijn al die arrows naar &jt high, en dan stuurt &jt een low. Dit maakt vervolgens ook de bits die low waren high vanwege de pijlen de andere kant op, en de eerste bit, jq, krijgt ook een low dus die flipt naar low en dat propageert naar de rest dus die worden ook allemaal low. Hij reset dus de hele subgraph.

[ Voor 56% gewijzigd door .oisyn op 20-12-2023 12:33 ]

[Soultaker]

Ik had ook een plaatje gemaakt van mijn invoer, net zoals de meeste mensen, denk ik. (Waarschuwing: spoilers voor dag 20 deel 2)

spoiler:

Hier is duidelijk te zien dat de graaf uit vier componenten bestaat en dat de vier inverters in het midden allemaal tegelijk een 1 moeten produceren zodat rx 0 ontvangt.

En dan vergelijkbare analyse als @.oisyn hierboven:

spoiler:

Als je inzoomt op een component:


Dan zie je dat de flipflops een binaire counter van het aantal knopdrukken vormen. De conjunction-module (eigenlijk een NAND gate) in het midden detecteert een getal x dat bestaat uit de bits corresponderend met de binnenkomende pijlen, en reset de bits dan naar 0, met de uitgaande pijlen die precies gaan naar de andere bits én bit 0, wat precies -x is in two's complement (je kunt het ook zien als: hij zet eerst alle 0 bits op 1, en voegt dan 1 toe, waardoor alle bits overflowen naar 0; de volgorde waarin je dit doet maakt voor het resultaat niet uit).

De oplossing is dan vrij simpel:

spoiler:

Gewoon het kleinste gemene veelvoud van de perioden van de vier componenten. Aangezien de perioden toevallig allemaal priemgetallen zijn kun je ze ook gewoon vermenigvuldigen.

De timing is nog wel interessant:

spoiler:

Na de knopafdruk waarop de conjunction nodes even 0 genereren, resetten ze de bits en daarmee ook zichzelf meteen. Als je dus alleen in de rust tussen knopindrukken (nadat alle events afgehandeld zijn) checkt wat de uitvoer van de inverters is, zoals ik in eerste instantie deed, dan zul je nooit een 1 detecteren. Die toestand komt alleen eventjes in het midden van het proces voor.

[ Voor 0% gewijzigd door Soultaker op 20-12-2023 16:31 . Reden: Spelling ]

[FCA]

Pffff... op deel 2 van vandaag ben ik aardig natgegaan. Deel 1 was goed te doen, binnen een kwartier opgelost, maar deel 2....

spoiler:

Ik had het patroon snel door (na een aantal stappen gaat een kaart een 2-cykel in, en je hoeft alleen te kijken naar wanneer en waar je de eerste keer een kaart nieuw binnengaat).
Ook de subtiliteit van de "even" en de "oneven" aantal stappen goed ingezien, maar ik bleef hangen op het correct tellen van de even en oneven kaarten die in een cykel terecht waren gekomen, + tellen hoeveel er wel waren binnengegaan maar nog niet in een cykel zaten + bepalen hoeveel stappen ze in het proces zaten was een kloteklus.
Wel helemaal zelf opgelost, zonder dat werk er al te veel onder te lijden heeft gehad . En geen off-by-one errors in de eerste submissie, gewoon gelijk goed, dat geeft toch ook wel wat voldoening.
En whiteboard helemaal volgekalkt met partiele uitwerkingen, toch leuk om te doen

[Marcj]

Soultaker schreef op vrijdag 22 december 2023 @ 14:26:
[...]

Ja, dat probeer ik meestal ook.

Mijn oplossing voor Dag 21 werkt (denk ik) wel voor alle mogelijk inputs, onder een paar aannames: de invoer is een vierkant van oneven grootte, en de buitenste rand is leeg. Dit geldt zowel voor de officiële testinvoer als de voorbeeldinvoer.


[...]

We missen ook nog het implementeer-een-rare-instructie-set probleem dat er meestal bij zit, zoals de IntCode machine van 2019. Misschien komt 'ie nog!

Dat is wat ik ook altijd probeer, maar deze dag was dus mislukt wat dat betreft. Ik laat nu wel met een check zien dat de invoer niet aan mijn verwachting voldoet en stopt hij dus gewoon.

Het voordeel van mijn oplossing is wel dat hij binnen 50ms runt

[FCA]

Pfff...
Deel 1:

spoiler:

Gewoon brute force proberen, recursief met het gelopen pad bijhouden in een set. Werkt niet bijster snel, maar wel goed genoeg. Redelijk snel geimplementeerd, positie < 1000.

Deel 2 was weer een killer voor mij

spoiler:

Brute force vergelijkbaar met deel 1 (maar dus meer toegestane transities) werd hem niet binnen een minuut, dus alternatieven zoeken. Zoals al eerder opgemerkt, graafalgoritmes zijn niet mijn sterkste punt, dus dat schept geen hoge verwachtingen.

Na veel zoeken kom ik erachter dat het waarschijnlijk NP compleet is, dus ik ga zoeken naar speciale eigenschappen van de graaf. Half uurtje prutsen voor ik een fatsoenlijke plaatje van de graaf kan maken (graphviz, pygraphviz en Windows lopen niet lekker samen).
Blijkt dat de graaf uit veel a_1 <-> a_2 <-> ... <-> a_n rijen bestaat. Dat kunnen we versimpelen naar a_1 <-> a_n met gewicht n.

Recursief op de versimpelde graaf blijkt te werken. Nog steeds niet snel (het blijft brute-force), maar de graaf heeft nog maar 36 edges, dan gaat het blijkbaar net (net even gecheckt: 1.262.816 unieke paden om te checken, maar er zijn natuurlijk nog veel meer doodlopende/in zichzelf kerende paden)
BTW: mijn gereduceerde graaf:

[ Voor 18% gewijzigd door FCA op 23-12-2023 09:46 ]

[Soultaker]

FCA schreef op zaterdag 23 december 2023 @ 09:29:

spoiler:

Recursief op de versimpelde graaf blijkt te werken. Nog steeds niet snel (het blijft brute-force), maar de graaf heeft nog maar 36 edges, dan gaat het blijkbaar net (net even gecheckt: 1.262.816 unieke paden om te checken, maar er zijn natuurlijk nog veel meer doodlopende/in zichzelf kerende paden)
BTW: mijn gereduceerde graaf:
[Afbeelding]

Ik was vanochtend ook helemaal niet wakker (nu nog nauwelijks) en heb ontzettend zitten prutsen. Sterker nog, de aanpak die jij beschrijft had ik al bij deel 1 gebruikt (wat natuurlijk volslagen overkill was, dom!) en dan zou je denken: dan was deel 2 zeker makkelijk. Ja, ware het niet dat ik op de een of andere manier bedacht had dat

spoiler:

je elke edge in de graaf maar 1 keer mag bezoeken, maar elke vertex meerdere keren. Dat is een heel ander probleem!

En ook plaatjes gemaakt van de graaf:



(De kleuren geven aan of een vertex een even of oneven aantal buren heeft. Dat heb je nergens voor nodig.)

edit: de plaatjes kloppen niet eens Dit zijn de correcte versies:

Voorbeeld deel 1 / 2:


Officiële invoer deel 1 / 2:

Uiteindelijk hetzelfde gedaan als jij, maar ook een teleurstellende runtime simpelweg vanwege het grote aantal mogelijkheden. Nog even nadenken of dat efficiënter kan. Overigens is het in z'n algemeenheid wel een NP-compleet probleem.

[ Voor 23% gewijzigd door Soultaker op 23-12-2023 19:42 ]

[jeroenheijmans]

Even tussendoor met een meta-berichtje, niet aan een dag gerelateerd. Voor de liefhebbers heb ik de resultaten van mijn jaarlijkse Advent of Code Survey gepubliceerd, dit jaar 3000+ mensen die 'm hebben ingvuld dus geeft enig beeld van wat men doet en gebruikt.

• Survey resultaten:https://jeroenheijmans.github.io/advent-of-code-surveys/
• Reddit announcement: https://www.reddit.com/r/..._aoc_2023_survey_results/

Met sneak peek van de resultaten hieronder.

spoiler: Multi-select vraag: "anno 2023 what are your thoughts on AI and LLM's for Advent of Code?"

Enjoy! En succes met de laatste puzzels natuurlijk allemaal

[Bolukan]

spoiler: day 23, part 2

Dit verklaart de hoeveelheid routes tussen begin (1) en eind (36)

[ Voor 42% gewijzigd door Bolukan op 23-12-2023 21:51 ]

[.oisyn]

Ik vond dat mijn dag 23 deel 2 er wel erg lang over deed. Ik print ondertussen de tot nu toe langst gevonden route, maar daar was al een tijdje geen update op geweest. Ik doe nog niet aan pruning verder dus ik ging gewoon eens kijken of dat dan het juiste antwoord was.

"Your anwer is too high"

Wait, what?!

Soultaker schreef op zaterdag 23 december 2023 @ 10:23:
Ja, ware het niet dat ik op de een of andere manier bedacht had dat

spoiler:

je elke edge in de graaf maar 1 keer mag bezoeken, maar elke vertex meerdere keren. Dat is een heel ander probleem!

d'Oh! Ik maak dus exact dezelfde fout. Typisch dat dat niet op deel 1 van toepassing is, noch op het voorbeeld.

spoiler:

Inderdaad even niet bedacht dat alle nodes natuurlijk dezelfde tile delen. Je kunt dus niet naar dezelfde node maar dan een ander pad nemen, want die ene tile die alle paden verbindt is al belopen

spoiler:

Mijn graaf for good measure

[ Voor 66% gewijzigd door .oisyn op 24-12-2023 02:04 ]

[Bolukan]

spoiler:

Waar ik aan denk is dat je 300 lijnen in de tijd kunt tekenen die ergens een lijn die je zoekt doorkruist, waarbij het tijdstip niet belangrijk is (niet belangrijk = per vergelijking anders).
In tegenstelling tot part 1 doe je dat niet tussen die 300 vergelijkingen maar met de onbekende 301e vergelijking, waarvan je de parameters nog niet kent.

[ Voor 68% gewijzigd door Bolukan op 24-12-2023 17:29 ]

[Soultaker]

Fijne kerstdagen allemaal!

Dag 25:

spoiler: Oplossing voor dag 25

Eerst probeerde ik 'm gewoon te brute forcen: voor elke drie edges een depth-first search om de componenten te detecteren. Dat was natuurlijk veel te traag. Toen had ik code geschreven om cliques te detecteren en samen te trekken. Dat werkte uitstekend op de voorbeeldinvoer, maar de officiële invoer blijkt geen cliques groter dan 3 te hebben, dus dat bleek verspilde tijd.

Uiteindelijk heb ik het Ford-Fulkerson algoritme maar geïmplementeerd om de minimum cut in de graaf te vinden. Probleem is dat je een start- en een eindvertex moet hebben in aparte componenten, anders vind je de minimum cut niet. Ik heb dat simpelweg opgelost door in een while-loop random twee vertices te kiezen. Als de componenten ongeveer even groot zijn is de kans dat je twee goede vertices hebt ongeveer 50%. Vraag me af of dat slimmer kan.

Python code: 25-minimal.py (~150 ms) (of 25.py voor een iets leesbaardere versie).

spoiler: Alternatieve aanpak

Het viel me op dat ik het antwoord ook zonder algoritme kan vinden. Als ik de invoer converteer naar GraphViz formaat en open met Qt Visual Graph Editor, dan zijn de twee helften duidelijk te zien.



Je kunt dan simpelweg op de kritieke edges klikken om de eindpunten te identificeren, en de vertices selecteren om te zien hoe groot de componenten zijn. Het verbaasde me enigszins dat QVGE geen moeite heeft met zulke grote bestanden.

edit:
neato maakt er ook een “mooi” plaatje van:


De edges binnen de componenten zijn een grote warboel maar de drie kritieke edges tússen de componenten zijn duidelijk herkenbaar, en dat is precies de informatie die je nodig hebt Jammer dat ik dit niet meteen geprobeerd had. Had me een heleboel tijd gescheeld (al had ik het probleem ook nog écht op willen lossen).

[ Voor 12% gewijzigd door Soultaker op 25-12-2023 14:45 ]

[.oisyn]

Grappig, de puzzel van vandaag is precies iets waar ik afgelopen tijd op m'n werk mee bezig ben geweest

spoiler:

Namelijk het partitioneren van een graaf in N delen waarbij je de edge cut minimaliseert. Ik gebruik daar een library voor. Zou wel flauw zijn om die gewoon aan te slingeren

Hier trouwens een representatie van het voorbeeld waarin het op het oog direct duidelijk is welke je moet knippen.

[ Voor 43% gewijzigd door .oisyn op 25-12-2023 14:13 ]

[Soultaker]

Friits schreef op dinsdag 26 december 2023 @ 00:35:
Update: ik heb vanochtend volgens mij te ingewikkeld gedacht... wat denken jullie van de volgende aanpak:

spoiler:

We definiëren de twee componenten als S en (impliciet) G \ S. We willen dat S slechts knopen bevat zodat er exact drie zijden zijn tussen S en G \ S.

De knoop in S met de meeste buren in G \ S hoort waarschijnlijk niet thuis S, dus we verwijderen we deze uit S. Dit herhalen we tot er precies drie zijden zijn tussen de componenten.

Code

Dit werkt op de voorbeeld-input en mijn eigen input, maar het klinkt te mooi (te eenvoudig) om volledig correct te zijn... ziet iemand waar mijn denkfout zit?

Interessant idee! Het werkt vast op de officiële invoer die een bepaalde structuur heeft, maar zoals veel greedy algoritmes kan het soms een suboptimale oplossing geven.

Je had je code ook kunnen testen op mijn extra testinvoer, daar gaat 'ie op de eerste invoer al mis

spoiler:

Het deel van de logica dat correct is, is: als een knoop v in S meer dan drie verbindingen heeft met knopen in S \ G, dan hoort v niet in S thuis en kun je 'm verwijderen. Het probleem is dat het kan voorkomen dat geen enkele individuele knoop meer dan 3 verbindingen heeft, terwijl het totaal aantal verbindingen tussen S en S \ G nog wel groter dan 3 is, en dan kies je een willekeurige knoop, die mogelijk wel in S moet blijven.

Hier is een concreet tegenvoorbeeld:

a: b c d g
b: c d g
c: d e
d: f
e: f g h
f: g h
g: h

Dat ziet er zo uit:


Het is duidelijk dat de componenten A = {a, b, c, d, e, f, g} en B = {h} zijn. Als je code toevallig begint met het verwijderen van e, f en g zodat S = {a, b, c, d, h} (wat consistent is met de regels), dan zul je vervolgens h willen verwijderen: h heeft immers exact 3 verbindingen met {e, f, g}, terwijl {a, b, c, d} er elk maar 1 hebben. Dan concludeer je ten onrechte dat h niet in S thuishoort, terwijl je juist met S={h} wil eindigen. Wanneer je eenmaal zo'n fout maakt is het onmogelijk die te herstellen.

Grappig genoeg geeft je code op bovenstaande voorbeeld soms wel het goede antwoord, afhankelijk van waar je toevallig begint. Blijkbaar is het een randomized algoritme, omdat in Python de volgorde van elementen in een set() niet alleen ongedefinieerd is, maar actief gerandomized wordt, zodat elke run de volgorde anders is (wat ik me niet gerealiseerd had).