Recursive caves

Day 12 asks to find paths in a directed cyclic graph, whereby the root and the outer most leaf are only visited once. This is basically a call-tree of a recursive function.

sub day12(:$verbose) {
    my @caves =
        <start-A start-b A-c A-b b-d A-end b-end>,
        <dc-end HN-start start-kj dc-start dc-HN LN-dc HN-end kj-sa kj-HN kj-dc>,
        <fs-end he-DX fs-he start-DX pj-DX end-zg zg-sl zg-pj pj-he RW-he fs-DX pj-RW zg-RW start-pj he-WI zg-he pj-fs start-RW>;

    my @number-of-paths;
    for @caves -> @cave {
        say ‚Cave ‘ ~ ++$ ~ ‚:‘ if $verbose;
        my %connections.append: @cave».split('-').map(-> [$a, $b] { $a => $b, $b => $a }).flat;

        my \paths = gather {
            sub walk($node, @so-far is copy, %seen is copy) {
                return if %seen{$node}:exists;
                @so-far.push: $node;
                (take @so-far; return) if $node eq 'end';

                %seen{$node} = True if $node eq $node.lc;

                .&walk(@so-far, %seen) for %connections{$node}.flat;
            }

            walk 'start', [], %()
        }

        paths.&{@number-of-paths.push(.elems); $_}.sort».join(',')».&{.say if $verbose};
    }

    printf(„There are %d paths in cave %d.\n“, |$_) for (@number-of-paths Z ++$ xx ∞);
}

There isn’t much trickery going on here. I build a list of cave networks and a Hash for each of them, where the keys are cave names and the leafs are lists of cave names. This mapping has to happen in both ways, because I can’t easily flip keys and values, if the values are lists. If you would watch the call stack, you could see that paths show up in walk($name, ...). Raku wont let us walk back the call stack to collect all the $names, so I keep my own stack in @so-far. Once the “end” cave is hit, I exfiltrate that stack with take.

This is a straight forward solution that comes with a lot of problems. The biggest problem is, that I rarely use any language features that Raku got and lesser languages don’t. After all, the purpose of AoC is to show off. Also, blogposts that state the obvious are a waste-of-time². I don’t need to write them and you don’t need to read them. So let’s have a different version of this program.

sub day12(:$verbose) {
    my @caves = <start-A start-b A-c A-b b-d A-end b-end>,
                <dc-end HN-start start-kj dc-start dc-HN LN-dc HN-end kj-sa kj-HN kj-dc>,
                <fs-end he-DX fs-he start-DX pj-DX end-zg zg-sl zg-pj pj-he RW-he fs-DX pj-RW zg-RW start-pj he-WI zg-he pj-fs start-RW>;

    my \connections = @caves.map: { Map.new: $_».split('-').map(-> [$a, $b] { $a => $b, $b => $a }).flat.classify(*.key, :as(*.value)) }

    my @number-of-paths = connections.hyper(:batch(1)).map( -> %connections {
        say ‚Cave ‘ ~ ++$ ~ ‚:‘ if $verbose;

        my \paths = gather {
            for 'start', [], %() -> $node, @so-far, %seen is copy {
                next if %seen{$node}:exists;
                @so-far.push: $node;
                (take @so-far; next) if $node eq 'end';

                %seen{$node} = True if $node eq $node.lc;

                %connections{$node}».&?BLOCK(@so-far, %seen)
            }
        }

        paths.sort».join(',')».say if $verbose;
        paths.elems
    });

    printf(„There are %d paths in cave %d.\n“, $_, ++$) for @number-of-paths;
}

The first step is to use immutable data structures where possible. Every cave is defined by its connections. Those connections can live in a Map instead of a Hash. The build-in .map returns a Seq I can bind to. By replacing for with .map that does immutable stuff, I can sneak a .hyper in. By replacing the recursive sub with a recursive &?BLOCK I finally have used a feature, that is unique to Raku (Haskell got auto-threading iteration and the dot-notation, which is equivalent to .hyper and ».).

With the two .hypers the program has not gotten slower. The overhead to setup threading does not exceed the gain in execution speed, even with very short lists. A very good sign that large cave systems would benefit greatly from modern CPUs.

It is not enough to get the presents delivered, we also want to please Santa. Don’t we, Elfs?

Lazy fishy

AoC day 6 is asking us to simulate a swarm of fish that happily reproduces every 6 days after getting mature at 8 days. My first attempt was to keep track of every single fish. For the requested 80 days, that is no problem at all. Calculating the swarm size after 256 days consumes several GB of RAM and takes halve an hour. According to Larry, laziness is a programmers virtue. All fish of the same age behave the same way. Instead of herding all the cats — I mean fish — we only need to keep track of 8 age-groups.

sub day6 {
    my @state = 3,4,3,1,2;

    my %duegroup := @state.BagHash;
    say %duegroup;

    my @swarmsize = lazy gather {
        take +@state;

        for 1..∞ -> $day {
            my $spawners = %duegroup{0};
            %duegroup{0..5} = %duegroup{1..6};
            %duegroup{6} = %duegroup{7} + $spawners;
            %duegroup{7..8} = |%duegroup{8}, |$spawners;

            take %duegroup.values.sum;
        }
    }

    say „After 80 days the Lanternfish-swarm is @swarmsize[80] fish strong.“;
    say „After 1 year the Lanternfish-swarm is @swarmsize[365] fish strong and fills the entire ocean.“;
}

I keep the age groups in a BagHash because it does the grouping by days-until-due-for-reproduction automatically. Since I want to use string interpolation at the end of the job, I keep the lazy list in a @-sigiled container.

say %duegroup; # BagHash(1 2 3(2) 4)
               #         ^left side, due in 1 day

To avoid filling it (and all RAM) up with fish-counts, I have to modify the Seq returned by gather with lazy. The result for day 0 is the number of fish in the input list. It holds the remainder of the days until reproduction. Each day we shift the not-due fish one group to the “left”. Those which would fall of the table are added to the new number of fish due in 6 days. I also add newly spawned fish at the “right” side of %duegroup.

This is quite fast. Calculating the 666463873541831246973426535180081306051344332419496097574607054518520839712550000594802691141564100111292720331357073290882244225192714184089169346685964671516187813951096262775287721663915276037319968883789316173563712342011586035522467448600678459412817531237893966744548230642659801567798572516443076828073809628951485686367299329173252460181111652453921794109579961493750750734265060027862319480301195721313855543368780410508489633987968914281286844276398056626056500195554449381491834369426013823615252815425543249358779614574848646041262235325074419121599566115743353840105721990147263874748266408772032316595776612139275667150427915327686811729436199173446975271203992586398293131887618521011755271899166531953123757885268369102417404559972744230868418598748655243343869986766661655042037984488812438348695753685017592648702268683994214491364317393963000241098774900860353154350255976660612825403755954259350777693373207214861611583733971247573753279647135857625981918122186224389736913154106660544150165044497782195798322467474545414359975280416021441868622819428265244124896732471132319475701297098131677160490677788279224281506375689792156083261660239743059289383954114360045274214222447181262304526133273574533858979412601139808464840312101529514180385599430255955781457713151780397881537813797741641230260021041504757528558567274708288004546316057088994331798567783285763677777142122893528306103449281714510452991482789242022142994359648845815232477126859520823649474552988312877187921416635399339769955646489084732858557082288490783224894412739826318984292580566158052826330786018382319598588584819781525838565470572832599454876144624825685404140533646123043106524436362093177570751086786992684152833820485100470478462777156051559248632339883918620198736118866635553334340968766645368916095695325353449774328446440853029129756875723991564302091757886533273523038336595218155455847720671360296311456615511534013669909215005974655727411796937809475695407372366543688858553164927186176284319696215869840409175116790478421050877644744904836567400465071060826920730779993325487654843921279330137019941534562291371379739094205792954311994261599649404889922657935181190550846909442988980801810457765018578868168346363395719520126080693090513623794846310221314002540928562091544035735325038582779915950068599810881238838540448661640810736257932409239805606726993593971797657644383607714015131260878806196971337351189307132698177407972017000201825640472058109196425617780979614274139677245275326428802749811532165738249568357364288460055317791819187069807360720201014895008424122335796058656382694269027483373897038315879369712516175302775491130230060194100099770983797730029371076098600606612606504496540435861780431593005821164544353917534438370844599828015624171035152767618278502384395318480104807923622283443228345020744327514580863359757880740620565938348095639936790616537599389440870787580722382958374157045847403580250327710279742970965217530007567847487846429484345115975936089086457712364194335781795515213707375354638264749379637149285715302499699088845270788017375200781914651624886714042032631270469044847919416882757592998910768135740421382562919303214988217260004008757603083768569310849111601378668903711883637090353302532077564619529097226962909371328794773406990184575492574816382339282338269302833194041280013723295140495812294249892861526693716554130318513200838212285332707704499327803950532136817920788685464177684231882161475412158613980694356704252223485876770828303281339998270153017398653147421948177553993722391032011790555781475682485164990790796034888331872104119994060864766641589486019776451094668437290051663716036351804363561485132861888879574332105755746153309513037221378820879329573100621979109181602108382778687920007027623414831325355922936046968957227262772531473235744575569740514039285285079980036544832094265112377855497790912673262704852676592069446938153092444838196960689253870134387550557038873034718392173556998819875192064045117445575414318403644736200616976079570351581324439468616174728711252055735149140658285911276621119118732662217544015753511023622959240241260159058502957488628401113683752318710676758503695635066625468822413388076887811531732302500858604790123295291538975651419944639646087856174350263884179672051458673053727846741852940783409835954103271242036038353321394729469974885235979650051711963599818288978055126149102294122957690031497952217393672252034107303994335475246886610393935909711275770573986970854143317950284989356715086562230590990839662529967681272012701505798117971299799673234803156367016061677454703877721642007114534983433005793420903432912243015821072394360443476630711401955759956596477921259921197706822024842706184998910663864226283398436784178963976789932203898475822109125115822415490069379877953461916500641360785172808758119764443455742650172841311795874542342105299546764202358136285062614258090851832551635187962587820503810490289553470001551935217902197256402696601078401640235964011992837767132544306689962788840045977817796846871328731122938775504758466277366002412258932993666859399845672862117595717765477084418344974513339885386063619148967760485644569723254386502614599760138260597586913326592541522848983986438880452374164216429025751686557474365199522842488300216635033117150699388311553631871523304932368513183793460587360209998943010954435528289373335985043693053046434862949189611789904404003996815754992741168257864648722507852978319713865174461022833619615861427774300761688047803529375954505687612634211974798691951830710730289116602338015712571919713442740921101207870031487262857757224763770493982861280180603699869281254386149365595141503324500597971840838925444811519173746205453585901612000096078377983693216681932761735871382240485236129666942296837602516410628534674249139340936564072588858508662014518396032670642171566567771092610926600132205438873264132169671839186033389009379212165494532865224738228272982628415238069291858853204890673332880170473586404742119046305516995821325630692191761607383013664301194995569003288388503364517918373684336120978256237183864578616282607689412551049174006645430791960802835367975524722469944875023083997434516051965324062562062442752116848975771006421529560299607198682335508788021748824834632380555640603831398812935629742121752733051617067038539404438447484910824885029216904840603378133010150718632314196549910940069982462107378900141797555250249935208997397711315528593375548049421047048207638162260994766052843933057072429081984043595382668008048815441886172552323834194611025394425207398796061655113529875766770335862295433937836310790356151504721463830935974879920537435613958346775599338978427292432231783451675146229944198725258442285056096897643424026441622229366580337496992870774916559942664143218462435883056138313243966685145911608280044630183828743286830275241001375308435058876588315394558530369931268118528336420931812712916773937710863132947830591511365516095582265199154128356467750260531926118525066675003071739260309498814109697189063963885209401818145157660757802363003040514869809402584304387485680818578184439487976464280610699595673895597604947155761931451857026119481521989593940428110457669252083455024257132120074023930581161863487809678476816678436527159186156678756992425278664261263708484749418357954362156298366169569952858156319404498178302520729199899572253728399089327226902089224984752734795690279882470693252940552757819062460127046586815772344470484790253458472803165221028960275008692355763601919703557459324036872353025549748290921483516876610531395817429047761411697904862224464212531048933689503710953109442732759237356189014125558693485176472400652479673164432317040092383048015713215512740516304979316443942228161330426132203218492568652429844498726935561264929505127040159441733670469017273769559892857515811651970232842902910750966526190087199111410520935729735696689765846703413417162958695721018396373977842934203382304174669594558675787121040712019812712637199564803807379998750042443634573161317032814654063703050313745228800256069546872721055397472849971261055167179148093797923385453790218673892818823567739343110029248690913982030310372481582634843912806744923808043007181815800649169469673070351509475681317040362080079281312224119391626505976590681654036842848901857111705024868826560558936251253859583929011265828395689945327820197228833561384392456298313561747748394718483542037615552580248500271438063011789566281595470199853023198605236455144377113950002829956885749726910859970467453792552668635995216864206218596950021302760671686860948660709098573433002174990465358653937153029463224102021507578668602684150574870330045407826281962883214840079596799276490894750533219984415623098428666873188029374708547890337468187414157979648817501413641552787994758913710746800642864628337671539154374549083325827751519622507300647675596156687313927874984679290918334751557320148851174268648748501598460423236243361175276493299700932350967611304127144863529443814326050641613997036999124651655030638507037387145077891922768079837374493772434405033883503075509855261373190585532568183734429126636609566437113208049191934178757873767996237864137030898595297764852947278503137535654458605086469339191811000608091947271420968592805443940823737551389579814508299891882450889085371376080695820603935358334989016914765326067944139312755088780873497628147215539231161256746277969813244329537295987450414498891042368211888806848015647664192838074523692506916539749616425352934092641915767614631974106789002780829259370945153878209885580118528965359521919939822564430178365165774801326445119698160605794516715313781273522505061346800085177272425594654595195871297893714444484654019369230684383865521835716565191711011225703873328690113338741589006004434605591923717311969482396225232141424607533639489729752857061366998628370189292803862359460211210097047097656785799422841468511247218250748712137270072150217376845512716579835863424124266409969323997884912125894710274417892440097212151006601864964501715587498027228291821527214891597929763067858211813183757227618746949153003067548837587385641297152433994877288147478924408708574787735392027870749748046058647481086754228856101011366212709560274468780106805925245692447193482596542371766911950533561804337941557402124280610123795070613547672025879877827460785101263145383763820589221812599680793379972139164978282434256491687426685791963210897737564390119822184172424646736690737001296189907293372002794718794343859271805116725046891389626435528472595260800584941078380832327387177955258248778327681468071971827524880496086353713584741373924249622400717299750258850422909328819339559616577726969888285499265108274415782048123220789084199913497296557007403128779553093784717845918745445922290732789635313425161159032772703674611865792209093078143315637983839062583178927604885804176901890074139431024521992946790674264598456993382894873782585589232909351337252085909914987029391625209523662798912738575387325882697093630889584806342086729953269904180963241778840784728451687149681183128287044178404559876211705493978607993217578576595627309177560138258393251229199363344608600791943289536916669977633214113363571738151766646583136944036255700361005501752780457860088797135268322742487795589796175524357222548619105448650889563122822300557069722234511223992337592422006595019241835160237357792597623226264796156436525000444919271143365054736760621783169117928864481337560330379337932871519758802364131406533840184638722778523503513161237577707839869894469301356642468409908038779903549303814329129368082877601350597015101443573569786660293070026290612678398529969549771340240049619685204641651940533388963319505779753820775106675393993440746877919137663894627710484952951370533558417848334983399118573772254814592641503109595203052266576628217982665280419682884629826433563359175909783893066680247809189684737319679794810962417304587378927029630140010025294071206254272147536956464176571120496356346058921327170718943074661003103039095915152587583902674312312092101412991709057528461788275313322023157444923961515073490629080814033737775390515724908613770868592505552627071392493431908003184245362798129644814275247365465174219093675867063908906790309087484038360355448865944433826848902249323340769551921362344300902654849989228061990570470320344406773081761525973310281281615015380247003600136192752901263014086146704494718707845916463576554858823406717928933268940127994564908810162906532920920224071766152344686212414339704259239442393373659788070205050074953421106903523777932561660319404315618286334884494752810138279280394839953523775430495636405722647736806105023313467826798305889070300688292676577425317590296248572229516029571842028122586867322197535500120877596981160658274166184430633768752767078804119527472092104099830927628974599431655369376640668429730717615832450226685074005759908848629013070780369003601994294137555213073407824546267230564379446839152125019696541355555784059875677483047688836017349363987435005707550300562941097489361280394538124621172777424335297196186189142985139997339712153248035313265906268750184715536312835386428661584074713111362111257299033685041830246384893597396787107620258243945962742675775172752828336415533038684107921898451917374241277659939338207690545527751158390355107462788415060406672197712718081242621431094055357466672139382347530564727892260750730970200840864797632462812548794461694757284402212145015656804330958957193444620379159129815905928250504737659678 fish strong swarm after 1000 years takes 40.345 seconds.

UPDATE:

The following version is 12.5x faster and inspired by a Haskellist.

sub day6_2 {
    my @state = 3,4,3,1,2;

    my ($a1, $a2, $a3, $a4, $a5, $a6, $a7, $a8, $a9) = @state.Bag{0..8};

    for 1..(365*1000) -> $day {
        ($a1, $a2, $a3, $a4, $a5, $a6, $a7, $a8, $a9) = ($a2, $a3, $a4, $a5, $a6, $a7, $a8 + $a1, $a9, $a1)
    }

    say [+] ($a1, $a2, $a3, $a4, $a5, $a6, $a7, $a8, $a9);
}

No wonder one can travel faster without baggage!

MAIN course

On IRC vasko asked how to handle a --verbose-flag. This is quite simple.

sub debug($level, |c) {
    say(|c) if $*VERBOSE && $*DEBUG-LEVEL ≥ $level;
}

sub MAIN(:v(:verbose($*VERBOSE)), :D(:debug-level($*DEBUG-LEVEL))) {
    debug 1, 'FYI, all is fine';
}

I can spot two pieces laying on our boilerplate. If you do a lot of shell-scripting, supporting -v and -D might be quite common. Also, every time we call debug we type a space and a comma to many.

proto sub MAIN(Bool :v(:verbose($*VERBOSE)) = False, Int :D(:debuglevel($*DEBUG-LEVEL)) = 1, |) is export {
    &debug1 = &debug.assuming(1) if $*DEBUG-LEVEL ≥ 1;
    &debug2 = &debug.assuming(2) if $*DEBUG-LEVEL ≥ 2;
    &debug3 = &debug.assuming(3) if $*DEBUG-LEVEL ≥ 3;
    &debug4 = &debug.assuming(4) if $*DEBUG-LEVEL ≥ 4;
    &debug5 = &debug.assuming(5) if $*DEBUG-LEVEL ≥ 5;
    &debug6 = &debug.assuming(6) if $*DEBUG-LEVEL ≥ 6;
    &debug7 = &debug.assuming(7) if $*DEBUG-LEVEL ≥ 7;
    &debug8 = &debug.assuming(8) if $*DEBUG-LEVEL ≥ 8;
    &debug9 = &debug.assuming(9) if $*DEBUG-LEVEL ≥ 9;

    my &*debug1 = &debug.assuming(1);

    {*}
}

sub debug($level, |c) {
    say(|c) if $*VERBOSE; # and $*DEBUG-LEVEL ≥ $level;
}

my (&debug1, &debug2, &debug3, &debug4, &debug5, &debug6, &debug7, &debug8, &debug9) X= {;};


sub EXPORT() {
    Map.new: '&debug1' => &debug1, '&debug2' => &debug2, '&debug3' => &debug3, '&debug4' => &debug4, '&debug5' => &debug5, '&debug6' => &debug6, '&debug7' => &debug7, '&debug8' => &debug8, '&debug9' => &debug9
}

This module exports a sub for each log-level. Those default to an empty block, until MAIN is called. Depending on the log-level, we rebind them to the actual sub debug with a fitting .assuming. We also wire up the dynvar $*VERBOSE. I wrote them in all caps to indicate they are constant-ish. This all works because an export of the form '&debug1' => &debug1 does export an &-sigiled container, which we can change even after sub EXPORT and the use-statement have finished their work.

use fancy-debug;

multi sub MAIN(*%_) {
    debug1 'level1';
    debug2 'level2';

    say 'i haz a done!';
}

Since we supply extra named arguments that are handled in the proto, we have to please the dispatcher with *%_. Repeating the named arguments would work too.

Thanks to vasko, I could identify dynvars in argument aliases as an ENODOC and found a way new way to remove the MAIN-course from my boilerplate.