recursive Sierpinski solution

description.txt

A Sierpinski DAG looks like this:

  U
   R
  L

where U, R, and L (upper, right, and lower) are all either single nodes, or Sierpinski DAGs
of the same size.

The tricky bit is this: the topmost node of R is also the rightmost node of U, whereas L is
similarly connected to both U and R. It's easy to see with a Sierpinski DAG of size 3:

    1
    |\
    | 2
    |/|\
    3 | 4
    |\|/
    | 5
    |/
    6

1, 2, and 3 are part of U.
2, 4, and 5 are part of R.
3, 5, and 6 are part of L.

Creating U first is an easy decision. It has no dependencies.

Then we might try creating R. But 5 has 3 as a parent, and that's a node outside of R.
In fact, 3 is part of L in its role as a parent to 5. So we can't create R before L.

Thus, we start by creating L before R. But we run into the same problems: the 5 has
2 and 4 as parents. And both of these are in R, which we haven't created yet.

So we can't create L before R, and we can't create R before L. Catch 22.

The solution -- gah, I'm not even letting you mull over this before spoiling it for
you -- is to introduce a second "primitive" besides a smaller Sierpinski triangle.

We introduce a "chipped" triangle, which is just like a normal one, except that it's
lacking its bottom node (like 9 for the big triangle, or 5 for R). It's this node
that has all the dependency problems.

Now the problem reduces to creating a chipped triangle and returning the loose ends
that would've been the bottom node's parents. We can then easily create a complete
triangle by adding the bottom node ourselves, possibly with additional parents
added.

So, we get two mutually recursive functions:

* create_sierp which creates a complete triangle
* create_chipped which creates a triangle missing its bottom node

create_sierp is simple. it mostly just calls create_chipped and then adds the bottom
node.

create_chipped is a bit involved.

* It contains a base case.
* It calls create_sierp for U.
* It calls create_chipped for R.
* It calls create_chipped for L.

Between the three creation steps, it makes sure to shuttle nodes around so that all the
triangles have enough information to bind nodes to parent nodes.

As far as I can see, these parameters and return values are needed:

my ($rightmost, $bottom) = create_sierp($topmost);

my ($rightmost, $bottom_parent_1, $bottom_parent_2)
  = create_chipped($topmost, $rightmost_parent_1, $rightmost_parent_2);

Your mission, should you choose to accept it, is to make this actually work. Good luck!

solution.pl

use Test;

class Node {
    has @.parents;
}

sub dump(Node $s) {
    my %color;
    my $index = 0;
    my @result;

    sub visit(Node $n) {
        return if %color.exists($n);
        %color{$n} = "being visited";
        for $n.parents.flat -> $p {
            visit($p);
        }
        %color{$n} = ++$index;
        my $parents = $n.parents
                        ?? "(" ~ join(" ", %color{$n.parents.list}.sort) ~ ")"
                        !! "";
        push @result, $index ~ $parents;
    }

    visit($s);
    return join " ", @result;
}

sub sierp(Int $size, Node $u = Node.new) {
    if $size <= 1 {
        return $u, $u;
    }

    my ($lp1, $lp2, $r) = chipped($size, $u);
    my $l = Node.new(:parents($lp1, $lp2));

    return $l, $r;
}

sub chipped(Int $size, Node $u, $rp1?, $rp2?) {
    if $size <= 2 {
        my $r = defined($rp1) ?? Node.new(:parents($u, $rp1, $rp2))
                              !! Node.new(:parents($u));
        return $u, $r, $r;
    }

    my ($Ul, $Ur)          = sierp($size - 1, $u);
    my ($Rlp1, $Rlp2, $Rr) = chipped($size - 1, $Ur);
    my ($Llp1, $Llp2, $Lr) = chipped($size - 1, $Ul, $Rlp1, $Rlp2);

    return $Llp1, $Llp2, $Rr;
}

{
    my ($s) = sierp(1);
    is dump($s), "1", "sierp triangle of size 1";
}

{
    my ($s) = sierp(2);
    is dump($s), "1 2(1) 3(1 2)", "sierp triangle of size 2";
}

{
    my ($s) = sierp(3);
    is dump($s), "1 2(1) 3(1 2) 4(2) 5(2 3 4) 6(3 5)",
                 "sierp triangle of size 3";
}

{
    my ($s) = sierp(4);
    is dump($s), "1 2(1) 3(1 2) 4(2) 5(2 3 4) 6(3 5) 7(6) 8(6 7) 9(7) 10(7 8 9) 11(8 10)",
                 "sierp triangle of size 4";
}