Fooled by complexity

And that fool would be me. After realising that HyperSeq is lazy, I managed to simplify the code in my last post.

sub needle(int \b) {
    sub is-pentagon($c is raw) { (1+sqrt(1+24*$c))%%6 }
    sub P($n is raw) { $n*(3*$n-1) div 2 }

    loop (my int $s = 1; $s < b; $s++) {
        my \bp = P(b);
        my \sp = P($s);
        if is-pentagon(bp + sp) && is-pentagon(bp - sp) {
            return |(b, $s);
        }
    }
}

sub infix:<notnilor>(\maybenil, \alternative) {
    maybenil =:= Nil ?? alternative !! maybenil
}

say (^∞).hyper(:batch(8), :degree(16)).map({.&needle notnilor Empty }).head;

The sub needle transforms its argument or returns Nil. By turning Nil into Empty, any call to .head will skip all values that where not a hit. At least for strongly CPU-bound tasks, which allow for small batch sizes, .hyper doesn’t overshoot much.

my atomicint $steps;
say (^∞).hyper(:batch(8), :degree(16)).map({$steps⚛++; .&needle notnilor Empty }).head;
say $steps;

# OUTPUT: (2167 1020)
          2246

Right now, almost all task are CPU-bound. Once Rakudo has learned to produce better bytecode being able to stop sibling threads will become desirable.

UPDATE

lizmat suggested to simplify the code further by replacing .&needle notnilor Empty with $_ with .&needle. This works because when with doesn’t fire, it returns Empty. That I did not know. It is specced and also applies to if. I filed the ENODOC under #4017. As it seems, we need to be careful not to run out of space on the interwebs by completing Raku’s docs.

Manual hypering

Nemokosch was unhappy with the performance of a literal translation from Python. So he asked for advice in #raku-beginner. (The logger is missing messages. Authorities have been informed.) This lead to many suggestions, none of which helped much. As such, I was forced to play our Get out of Jail Free (card).

use v6.*;

sub is-pentagon($c is raw) { (1+sqrt(1+24*$c))%%6 }

sub P($n is raw) { $n*(3*$n-1) div 2 }
my atomicint $bail = 0;
(^∞).hyper(:batch(64)).map( -> \b {
    last if $bail;
    for (1..^b) -> \s {
        my \bp = P(b);
        my \sp = P(s);
        if is-pentagon(bp + sp) && is-pentagon(bp - sp) {
            say [b, s];
            $bail⚛++;
            say now - BEGIN now;
            last;
        }
    }
});

This is a rather strange use for .hyper as we don’t collect the resulting list. Also, last doesn’t quite work on a HyperSeq. Jnthn is confident this is a fixable problem. Sadly, I don’t have the patience to wait.

my \integers = Channel.new;

start for (^∞).batch(46) { try integers.send($_); }

my @promises;
for ^($*KERNEL.cpu-cores - 1) {
    my atomicint $bail = 0;
    with integers {
        @promises.push: start {
            loop { integers.receive.map( -> \b {
                    last if $bail;
                    for (1..^b) -> \s {
my \integers = Channel.new;

start {
    for (^5000).batch(46) { try integers.send($_); }
    integers.close;
}

my @promises;
for ^($*KERNEL.cpu-cores - 1) {
    my atomicint $bail = 0;
    with integers {
        @promises.push: start {
            my $result = Empty;
            loop {
                integers.receive.map( -> \b {
                    for (1..^b) -> \s {
                        last if $bail;
                        my \bp = P(b);
                        my \sp = P(s);
                        if is-pentagon(bp + sp) && is-pentagon(bp - sp) {
                            $bail⚛++;
                            $result = |(b, s);
                            integers.close;
                        }
                    }
                });
                CATCH { when X::Channel::ReceiveOnClosed { last } }
            }

            $result;
        };
    }
}

say @promises».result;

The idea is simple. I pipe the list in chunks into a Channel and start a bunch of threads. Those threads look for the needle and signal each other via an atomicint that it’s time to go home. By defaulting to Empty in the result value of the start-block, I eliminate all return values of threads that didn’t find the value of interest.

Let’s generalise this a little.

use MONKEY;
augment class HyperSeq {
    multi method find(&needle, :$first!, :$take-result!) {
        my \chan = Channel.new;

        my @promises;
        for ^(self.configuration.degree - 1) {
            my $p = Promise.new;
            start {
                my $result = Empty;
                BAIL: loop {
                    for chan.receive {
                        $result = .&needle;
                        unless $result =:= Nil {
                            chan.close;
                            $p.keep($result);
                            last BAIL;
                        }
                    }

                    CATCH { when X::Channel::ReceiveOnClosed { say 'bail'; last } }
                }

                for @promises {
                    .keep(Empty) unless .status ~~ Kept;
                }
            };
            @promises.push: $p;
        }

        await start {
            for self.batch(self.configuration.degree) { chan.send($_); }
            chan.close;
            CATCH { when X::Channel::SendOnClosed { } }
        }

        @promises».result.head;
    }
}

sub needle(\b) {
    for (1..^b) -> \s {
        my \bp = P(b);
        my \sp = P(s);
        if is-pentagon(bp + sp) && is-pentagon(bp - sp) {
            return |(b, s);
        }
    }
}

say (^∞).hyper(:46batch).find(&needle, :first, :take-result);

By using the Channel to indicate that one of the threads is done, I don’t need the atomicint any more and the &needle is using Nil for something useful. This is now faster then the original Python implementation — with 16 cores on full steam. And that is very promising. Once we got single thread performance under control, we won’t even see the competition in the rear mirror.

I do have the feeling that our hyper/race-facilities do lack some algorithms. If you know other languages that have them, please plunder and pillage away. YARRRR!

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.

MONKEY-SEE-NO-CROSSPRODUCT

The challenge of the week is screaming: “Nest all the loops!”. I don’t like being yelled at, so I refuse to use any nested for/while/loop. The rules don’t require to put the two sub-challenges into separate files, so I won’t.

#! /usr/bin/env raku

use v6.d;

multi sub MAIN($divisors = 8, $? where $*PROGRAM-NAME.contains('-141-1')) {
    sub has-m-divisors($m, $n) {
        (1..∞).grep({ last if $_ > $n; $n %% $_ ?? (last if $++ ≥ $m; True) !! False })[^∞].elems == $m;
    }
    put (1..∞).grep(&has-m-divisors.assuming($divisors))[^10];
}

multi sub MAIN($m, $n where $*PROGRAM-NAME.contains('-141-2')) {
    use MONKEY-SEE-NO-EVAL;

    sub bind($o, Str $method-name) {
        sub (|c) { $o."$method-name"(|c) }
    }

    sub is-same-order(@l) {
        my @indices = @l.map(bind($m, 'index'));
        @indices ~~ @indices.sort;
    }

    say [$m, $n];
    my @a = $m.comb;
    my $expr = ('@a' xx @a).join(' X, '); # I can haz RakuAST macro plox?
    my @digits = (EVAL $expr)».unique.grep(-> @l { @l < @a && is-same-order(@l) }).sort(*.elems)».join.unique».Int;
    say @digits.grep: * %% $n;
}

multi sub MAIN($? where $*PROGRAM-NAME.contains('-141-2')) {
    for (1234, 2; 768, 4) -> [$m, $n] {
        MAIN($m, $n);
    }
}

To be able to run the 2nd task, ln -s pwc-141-1.raku pwc-141-2.raku is required. Since we can’t have a bare where-clause (yet), we need the optional positional in the MAINs.

Task one basically builds an infinite list of integers that have 8 divisors and then shows the first 10 of those. This is done by iterating to infinity and bailing as early as possible, if the condition of having 8 divisors is net or we get beyond the to be checked value. Since grep wants arity of 1, we use .assuming to please it.

The 2nd task is attacked (appropriate wording, as it took me 3 hours of struggle to get it done) in a similar fashion. First we build all possible combinations of an n-places integer. This would be done with an expression like @a xx @a ... $n where $n is the number of places. I don’t think we got such a construct in Raku so I had to macro it in with EVAL (also, it made a good blog title). We then proceed with eliminating all combinations that are forbidden by the task. First we weed out repetition with ».unique. Next we only take integers that are shorter then the original integer and don’t have the same order. We sort the result list by number of digits to make it pretty. At this point the digits are still represented as a list. We change that by forcing them into a Str via ».join and remove duplicates and turn them into Ints (not strictly necessary). Now we fulfil the last condition of divisibility by $n.

The sub is-same-order was where I spend the most time. And you can tell by how short it is. The idea is simple. We build a list of indices by walking the places of the number we want to check against the original integer. If the indices are all ascending, the order is the same. And we can tell by checking if those are already numerically sorted.

I’m not happy with using bind. This is another spot where Raku won’t allow functional programming to integrate well with OO. I’m gonna ask Santa if he can make &$m.index DWIM.

UPDATE

As perryprog kindly pointed out on IRC, there is sub cross, what makes the EVAL redundant.

my @digits = cross(@a xx +@a)».unique.grep(-> @l { @l < @a && is-same-order(@l) }).sort(*.elems)».join.unique».Int;

However, I think we can all agree that there is no immediate need to surrender a good blog post title.

Symmetric code

While reading Arne`s solution for Challenge #140.2, I spotted a nested simple loop.

for 1 .. $i -> $ii                                               # [3]
{
  for 1 .. $j -> $jj                                             # [3]
  {
    @result.push: $ii * $jj;                                     # [4]
  }
}

In Raku-land, we don’t really need simple loops. Often we can .map or use a hyper operator. I had the nagging feeling this is also the case for simple nested loop. A good night’s sleep later I remembered that “X” marks the spot.

The cross-product-operator X is implemented with 2 nesting loops and returns a list of lists. In Raku we construct lists with infix:<,>.

use Test;
is-deeply ((1,2) X, (3,4)), ((1,2) X (3,4)), 'yep!';

So we are actually calling X,. If we replace infix:<,> with infix:<*>, we get what Arne did without the temporary container.

for [2, 3, 4; 3, 3, 6; 200, 300, 40; 0, 0, 0] -> [$i, $j, $k] {
    put ((1..$i) X* (1..$j)).sort[$k - 1];

    CATCH { when X::OutOfRange { warn „Sorry, I can't find position $k in the multiplication table of $i and $j.“ } }
}

I wonder if there are more cases, where we could look at the implementation of a high-level language feature, to spot places worthy of replacing wordy code with a single operator call.

Leaky Rakudo

Yesterday the discord-bridge-bot refused to perform its 2nd job: EVAL All The Things! The EVALing is done via shell-out and requires a fair bit of RAM (Rakudo is equally slim then Santa). After about 3 weeks the fairly simple bot had grown from about halve a GB to one and a halve – while mostly waiting for the intertubes to deliver small pieces of text. I complained on IRC and was advised to take heap snapshots. Since I didn’t know how to make heaps of snapshots, I had to take timo’s directions towards use Telemetry. As snap(:heap) wasn’t willing to surrender the filename of the snapshot (I want to compress the file, it is going to get big over time) I had a look at the source. I also requested a change to Rakudo so I don’t have to hunt down the filename, which was fulfilled by lizmat 22 minutes later. Since you may not have a very recent Rakudo, the following snipped might be useful.

    multi sub postfix:<minute>(Numeric() \seconds) { seconds * 60 }
    multi sub postfix:<minutes>(Numeric() \seconds) { seconds * 60 }
    multi sub postfix:<hour>(Numeric() \seconds) { seconds * 3600 }
    multi sub postfix:<hours>(Numeric() \seconds) { seconds * 3600 }
    multi sub postfix:<day>(Numeric() \seconds) { seconds * 86400 }
    multi sub postfix:<days>(Numeric() \seconds) { seconds * 86400 }

    start react whenever Supply.interval(1day) {
        note ‚taking snapshot‘;
        use Perl6::Compiler:from<NQP>;
        sub compress(Str() $file-name) { run «lz4 -BD --rm -qf $file-name» }

        my $filename = 'raku-bot-' ~ now.DateTime.&{ .yyyy-mm-dd ~ '-' ~ .hh-mm-ss } ~ '.mvmheap';
        Perl6::Compiler.profiler-snapshot(kind => "heap", filename => $filename<>);
        $filename.&compress or warn(‚compression failed‘);

        note ‚done‘;
    }

If you got a long running MoarVM process, please consider to check if it slowly fills all RAM and provide the snapshots to #rakudev.

2nd class join

For challenge #137.1 we are looking for long years. We can implement the algorithm as described in Wikipedia (and ignore that Dateish got .week-number to have a reason for showing off with junctions).

multi sub infix:«|,»(\left, \right) is equiv(&infix:<Z>) { |left, |right }

say (1900..2100).grep({ Date.new(.Int, 1, 1).day-of-week | Date.new(.Int, 12, 31).day-of-week == 4 });

# OUTPUT: 1903 1908 1914 1920 1925 1931 1936 1942 1948 1953 1959 1964 1970 1976 1981 1987 1992 1998 2004 2009 2015 2020 2026 2032 2037 2043 2048 2054 2060 2065 2071 2076 2082 2088 2093 2099

The output doesn’t look too nice. It would be better to group the years in column.

put ( (1900..2100).grep({ Date.new(.Int, 1, 1).day-of-week | Date.new(.Int, 12, 31).day-of-week == 4 }) Z (' ' xx 7 |, $?NL) |xx ∞ ).flat.head(*-1).join('');

# OUTPUT: 1903 1908 1914 1920 1925 1931 1936 1942
          1948 1953 1959 1964 1970 1976 1981 1987
          1992 1998 2004 2009 2015 2020 2026 2032
          2037 2043 2048 2054 2060 2065 2071 2076
          2082 2088 2093 2099

That is pretty long and convoluted. The reason why I need Z with an infinite list and have to remove the last redundant element (either a newline or space) is that .join isn’t all that smart. Let’s build a smarter function.

multi sub smart-join(Seq:D \separator, *@l --> Str:D) {
    my $ret;
    my $sep-it = separator.iterator;
    my $list-it = @l.iterator;

    loop {
        my $e := $list-it.pull-one;
        last if $e =:= IterationEnd;

        $ret ~= $e;
        $ret ~= $sep-it.pull-one if $list-it.bool-only;
    }

    $ret
}

multi sub infix:«|xx»(Mu \left, Mu \right) is equiv(&infix:<xx>) { (left xx right).flat }

1900..2100
==> grep({ Date.new(.Int, 1, 1).day-of-week | Date.new(.Int, 12, 31).day-of-week == 4 })
==> smart-join( (' ' xx 7 |, $?NL) |xx ∞ )
==> say();

Now we can use (the sadly under-used) feed operator. The lazy list that is generating the alternating separators might be a bit slow. If we go functional the code, both for smart-join and the alternator, gets simpler.

multi sub smart-join(&separators, *@l --> Str:D) {
    my $ret;

    while @l {
        $ret ~= @l.shift;
        $ret ~= separators if +@l;
    }

    $ret
}

1900..2100
==> grep({ Date.new(.Int, 1, 1).day-of-week | Date.new(.Int, 12, 31).day-of-week == 4 })
==> smart-join({ ++$ %% 8 ?? $?NL !! ' '})
==> say();

Right now there is no easy way to add this as a module because sub join is not a multi. Since we use Z with such infinite lists quite often, I believe a proper functional way in CORE could not hurt. Raku does support functional programming in many places but some subs are still 2nd class citizen. It may be reasonable to make a list so I can hand it over to Santa.

UPDATE:

As lizmat noted, sub join is a multi already. So there is room for a module.

Should it mutate or not? YES!

On Discord Hydrazer was looking for a list concatenation operator. That leaves the question if it should mutate like Array.push or return a new list of Slips.

sub infix:«|<<»(\a, \e) {
    Proxy.new(FETCH => method { |a, |e },
              STORE => method (\e) {})
              but role { method sink { a.push: e } };
}

my @a = 1,2,3;
@a |<< 4;
dd @a;
my @b = @a |<< 5;
dd @a, @b;

In sink-context returning a new list would not make sense. With a Proxy that provides a sink-method we can answer the question with “YES!”.

This made me wonder if Proxy should have the optional argument SINK. Right now there is no way to define containers in pure Raku. Even with subclassing we would have to decent into nqp-land. As newdisp has shown, it tends to be quite brittle to make modules depend on use nqp;`.