Commits

Shlomi Fish committed da60448

Translate the program to Perl 6/Niecza.

Runs correctly, but is slow and memory hungry.

  • Participants
  • Parent commits dc66950

Comments (0)

Files changed (1)

File project-euler/189/euler_189-2.p6

+#!/usr/bin/perl
+
+use v6;
+
+=begin pod
+
+Solution for Project Euler #189 by Shlomi Fish, L<http://www.shlomifish.org/> .
+
+Consider the following configuration of 64 triangles:
+
+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:
+
+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?
+
+=end pod
+
+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 %data = (
+        seq => {'0' => 1, '1' => 1, '2' => 1,},
+        derived =>
+        {
+            '' =>
+            {
+                '0' => 1,
+                '1' => 1,
+                '2' => 1,
+            }
+        },
+        count => 3,
+    );
+    for (1 .. $wanted_h - 1) -> $h
+    {
+        my $this_seqs = %data{'seq'};
+        my $prev_deriveds = %data{'derived'};
+
+        my $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.
+        %data =
+        (
+            seq => $next_seqs,
+            derived => $next_deriveds,
+            count => $total_count,
+        );
+        say "Count[{$h+1}] = $total_count";
+    }
+
+    return %data{'count'};
+}
+
+# Test
+{
+    say my_find(2), " should be 3*2*2*2 == 24";
+}
+say "Result[8] = ", my_find(8);