# t5/simon

``````use v6;

#returns a list of all forests with depth <= \$dm \$n nodes, trees which are
#before (\$d,\$nmax,\$max)
#returns all forests of depth <= \$n
multi forests(Int \$n, 0, Int \$nmax = \$n, \$max = Inf) {[],}
multi forests(Int \$n, 1, Int \$nmax = \$n, \$max = Inf) {[[] xx \$n],}
multi forests(Int \$n, Int \$d, Int \$nmax where {\$n < \$nmax}, \$max = Inf) {forests(\$n,\$d)}
multi forests(Int \$n, Int \$d, Int \$nmax = \$n, \$max = Inf) {
return forests(\$n,\$d-1) if \$nmax < \$d;
gather {
for trees(\$nmax,\$d) Z 1..\$max -> \$tree, \$index {
for forests(\$n-\$nmax,\$d,\$nmax,\$index) -> \$forest {
take [\$tree, @\$forest];
}
}
take forests(\$n,\$d,\$nmax-1);
}
}

#returns all trees of depth \$n
multi trees(1, 1) {[],}
multi trees(Int \$n, 1) {()}
multi trees(Int \$n, 2) {[[] xx (\$n-1)],}
multi trees(Int \$n, Int \$d, Int \$nmax, \$max = Inf, \$dmax = \$d) {
(\$dmax > \$d or \$nmax > \$n) and return trees(\$n,\$d);
gather {
for trees(\$n,\$d) Z 1..\$max -> \$tree,\$i{
take \$tree;
}
}
}
multi trees(Int \$n, Int \$d) {
gather {
for \$d..\$n -> \$cn {
for trees(\$cn-1,\$d-1) Z 1..* -> \$tree,\$index {
for forests(\$n-\$cn,\$d-1,\$cn-1,\$index) -> \$forest {
take [\$tree,@\$forest];
}
}
}
}
}
sub even_trees(Int \$n) {
my \$maxd = \$n div 2;
for 2..\$maxd -> \$cd {
for ceiling(\$n/2)..(\$n-\$cd) -> \$cn {
for trees(\$cn, \$cd) Z 1..* -> \$t1, \$max {
for trees(\$n-\$cn, \$cd,\$cn,\$max,\$cd) -> \$t2 {
say represent([\$t1,@\$t2]);
}
}
}
}

}
sub odd_trees(Int \$n) {
my \$maxd = (\$n-1) div 2;
for 1..\$maxd -> \$cd {
for \$cd..(\$n-1-\$cd) -> \$cn {
for trees(\$cn, \$cd) Z 1..* -> \$t1, \$max {
for \$cd..(\$cn,(\$n-1-\$cn)).min -> \$dn {
for trees(\$dn, \$cd,\$cn,\$max) Z 1..* -> \$t2, \$max2 {
for forests(\$n-\$cn-\$dn-1,\$cd,\$n-\$cn-\$dn-1,\$max2) -> \$w {
say represent([\$t1,\$t2,@\$w]);
}
}
}
}
}
}
}
multi represent(\$tree) {
my \$rep = represent(\$tree,1)[0];
\$rep ~~ s/\-\d+\$//;
return \$rep;
}
multi represent(\$tree,Int \$n) {
return \$n,\$n+1 if \$tree.elems == 0;
my \$c = \$n+1;
my \$rep = "\$n";
for @\$tree -> \$subtree {
my (\$r,\$s) = represent(\$subtree,\$c);
\$c=\$s;
\$rep ~= "-\$r-\$n";
}
return \$rep,\$c;
}
multi MAIN(1) {say "1"}
multi MAIN(2) {say "1-2"}
multi MAIN(Int \$n) {
even_trees(\$n);
odd_trees(\$n);
}
``````

## Correctness

The program fails for `N = 8`:

``````\$ nom solutions/t5/simon 8
1-2-3-2-4-2-5-2-1-6-1-7-1-8
1-2-3-2-4-2-5-2-6-2-1-7-1-8
1-2-3-2-4-2-5-2-6-2-7-2-1-8
1-2-3-4-3-2-5-2-1-6-7-6-1-8
1-2-3-4-3-5-3-2-1-6-7-6-1-8
1-2-3-4-3-5-3-2-1-6-7-6-8-6
1-2-3-4-3-2-5-6-5-2-1-7-8-7
1-2-3-4-3-2-5-2-6-2-1-7-8-7
1-2-3-4-3-5-3-2-6-2-1-7-8-7
1-2-3-4-3-5-3-6-3-2-1-7-8-7
1-2-3-4-5-4-3-2-1-6-7-8-7-6
1-2-1-3-1-4-1-5-1-6-1-7-1-8
1-2-3-2-1-4-5-4-1-6-7-6-8-6
1-2-3-2-1-4-5-4-1-6-7-6-1-8
1-2-3-2-1-4-5-4-1-6-1-7-1-8
1-2-3-2-4-2-1-5-6-5-1-7-8-7
1-2-3-2-4-2-1-5-6-5-1-7-1-8
1-2-3-2-4-2-1-5-6-5-7-5-1-8
1-2-3-2-4-2-5-2-1-6-7-6-1-8
1-2-3-2-4-2-5-2-1-6-7-6-8-6
1-2-3-2-4-2-5-2-6-2-1-7-8-7
1-2-3-4-3-2-1-5-6-7-6-5-1-8
1-2-3-4-3-2-5-2-1-6-7-8-7-6
1-2-3-4-3-5-3-2-1-6-7-8-7-6
``````

Which corresponds to these trees:

``````   8  3      8  3   4       3   4
|  |      |   \ /         \ /
7--1--2--4   1----2     8--1--2--5
|  |      |   / \         / \
6  5      7  6   5       7   6

8  5              8     4
|  |              |     |
7--6--1--2--3--4  7--6--1--2--3--5

8        4
|        |
7--6--1--2--3--5  8--7--1--2--3--4
|
5--6

6                 6  4
|                 |  |
8--7--1--2--3--4  8--7--1--2--3--5
|
5

4
|
8--7--1--2--3--5  8--7--6--1--2--3--4--5
|
6

8   2      8              6--7
\ /       |*             |
7--1--3  7--6--1--2--3  8--1--2--3
/|\          |           |
6 5 4         4--5        4--5

7   8         4              8  4
\ /          |*             |  |
6--1--2--3  3--2--1--7--8  7--1--2--3
|              |           |
4--5           5--6        5--6

7  8  4           8  4
|  |  |           |  |
6--5--1--2--3  7--6--1--2--3
|
5

1     4              3
|     |              |
7--6--1--2--3  8--7--1--2--4
|             / \
5            6   5

5--6--7                 5
|                       |
8--1--2--3--4  8--7--6--1--2--3--4

4
|
8--7--6--1--2--3--5
``````

The two trees marked with an asterisk are isomorphic and hence duplicates. Presumably this occurs because tree traversal order isn't normalized away quite right.

## Consistency

Not much to complain about here.

## Clarity of intent

The `even_trees` and `odd_trees` routines are a bit deep, indentation-wise. It's difficult to follow what's going on in there.

## Algorithmic efficiency

Efficiency doesn't really apply since the program is incorrect.

## Idiomatic use of Perl 6

The program makes good, effective use of language features. Returning lists of values, passing around data using built-in data structures...

The two `represent` multis are really in an inner-outer relationship, and should probably have been factored to reflect that. Could declare one inside the other, for example.

## Brevity

This code doesn't waste much time getting its point across.