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?