# Tri-colouring a triangular grid

Author: Shlomi Fish

https://projecteuler.net/problem=189

Consider the following configuration of 64 triangles (see the web page for the image):

We wish to colour the interior of each triangle with one of three colours: red, green or blue, so that no two neighbouring triangles have the same colour. Such a colouring shall be called valid. Here, two triangles are said to be neighbouring if they share an edge.

Note: if they only share a vertex, then they are not neighbours.

For example, here is a valid colouring of the above grid (see the web page for the image):

A colouring C' which is obtained from a colouring C by rotation or reflection is considered distinct from C unless the two are identical.

How many distinct valid colourings are there for the above configuration?

Source code: prob189-shlomif.pl

```use v6;

my %colors = ('00' => ['1','2'], '11' => ['0','2'], '22' => ['0','1'],
'01' => ['2'], '10' => ['2'],
'02' => ['1'], '20' => ['1'],
'12' => ['0'], '21' => ['0'],
);

my %l_colors = ('0' => ['1','2'], '1' => ['0','2'], '2' => ['0','1']);

sub my_find(Int \$wanted_h) returns Int {
# The start_data for \$h == 1
my \$this_seqs = {'0' => 1, '1' => 1, '2' => 1,};
my \$prev_deriveds = {
'' => {
'0' => 1,
'1' => 1,
'2' => 1,
}
};

my \$total_count;

for (1 ..^ \$wanted_h) -> \$h {
\$total_count = 0;
my \$next_deriveds = {};
my \$next_seqs = {};

for \$this_seqs.kv -> \$seq, \$seq_count {
my \$seq_ders = (\$next_deriveds{\$seq} //= {});
for (\$prev_deriveds{\$seq.substr(0, *-1)}).kv -> \$left, \$left_count {
my \$delta = \$seq_count * \$left_count;
# say "F = <{\$seq.substr(*-1) ~ \$left.substr(*-1)}>";
for %colors{\$seq.substr(*-1) ~ \$left.substr(*-1)}.values -> \$lefter_tri_color {
# say "Lefter = <\$lefter_tri_color>";
for %l_colors{\$lefter_tri_color}.values -> \$leftest_color {
# say "L = <\$left> LEST = <\$leftest_color>";
# say "delta = <\$delta> left_count = <\$left_count>";
my \$str = \$left ~ \$leftest_color;

\$total_count += \$delta;
(\$next_seqs{\$str} //= 0) += \$delta;
(\$seq_ders{\$str} //= 0) += \$left_count;
}
}
}
}

# Fill the next data.
(\$this_seqs, \$prev_deriveds) = (\$next_seqs, \$next_deriveds);
say "Count[{\$h+1}] = \$total_count";
}

return \$total_count;
}

# Test
{
say my_find(2), " should be 3*2*2*2 == 24";
}
say "Result = ", my_find(8);

```