Commits

Shlomi Fish  committed b56d55e

Add take 3.

The $new_layer_count calculation is now O(1) instead of O(X*Y*Z). Still too
slow though.

  • Participants
  • Parent commits f416a2c

Comments (0)

Files changed (2)

File project-euler/126/126-planning.txt

+The problem:
+============
+
+The minimum number of cubes to cover every visible face on a cuboid measuring 3
+x 2 x 1 is twenty-two.
+
+If we then add a second layer to this solid it would require forty-six cubes to
+cover every visible face, the third layer would require seventy-eight cubes,
+and the fourth layer would require one-hundred and eighteen cubes to cover
+every visible face.
+
+However, the first layer on a cuboid measuring 5 x 1 x 1 also requires
+twenty-two cubes; similarly the first layer on cuboids measuring 5 x 3 x 1, 7 x
+2 x 1, and 11 x 1 x 1 all contain forty-six cubes.
+
+We shall define C(n) to represent the number of cuboids that contain n cubes in
+one of its layers. So C(22) = 2, C(46) = 4, C(78) = 5, and C(118) = 8.
+
+It turns out that 154 is the least value of n for which C(n) = 10.
+
+Find the least value of n for which C(n) = 1000.
+
+Thinking:
+=========
+
+We've realised that in layer of depth 'd', the cells have a delta of 
+d_x+d_y+d_z=d . Now in depth 1, the cells have a count of:
+
+2*[w_x*w_y + w_y*w_z + w_x*w_z]
+
+In depth 2, we add the following offsets - @d = (0,1,1) ; @d = (1,0,1)
+@d = (1,1,0) (as (2,0,0) and friends are already counted in the previous 
+layer). So:
+
+Total[2]-Total[1] = 4 * [ w_x + w_y + w_z ]
+
+In depth 3 and above we also have the corners:
+
+Total[3] - Total[2] = 4 * [w_x+w_y+w_z] + 8 * 1
+Total[4] - Total[3] = 4 * [w_x+w_y+w_z] + 8 * 2
+

File project-euler/126/euler-126-take3.pl

+#!/usr/bin/perl
+
+use strict;
+use warnings;
+
+use integer;
+
+use List::MoreUtils qw(any all);
+
+my @C;
+
+# Matches $X,$Y,$Z (where $X >= $Y >= $Z) to the cuboid array and maximal 
+# reached layer.
+my %cuboids;
+
+my $max_C_n = 0;
+
+sub add_layer
+{
+    my ($x_lim, $y_lim, $z_lim) = @_;
+
+    my $key = "$x_lim,$y_lim,$z_lim";
+
+    my $depth = $cuboids{$key}->{d};
+    my $old_n = $cuboids{$key}->{n};
+
+    my $expected_new_layer_count =
+       (($depth == 1)
+        ? (($x_lim*$y_lim+$x_lim*$z_lim+$z_lim*$y_lim)*2)
+        : ($old_n+($x_lim+$y_lim+$z_lim)*4 + (($depth > 1) ? 8*($depth-2) : 0))
+        );
+
+    my $new_layer_count = 0;
+
+    my $calc_dist = sub {
+        my ($x, $x_lim) = @_;
+
+        return
+            (($x < 0) ? abs($x) : ($x >= $x_lim) ? ($x-($x_lim-1)) : 0);
+    };
+
+    foreach my $x (-$depth .. $x_lim+$depth-1)
+    {
+        my $dist_x = $calc_dist->($x,$x_lim);
+
+        foreach my $y (-$depth .. $y_lim + $depth-1)
+        {
+            my $dist_y = $calc_dist->($y,$y_lim);
+
+            foreach my $z (-$depth .. $z_lim + $depth-1)
+            {
+                my $dist_z = $calc_dist->($z, $z_lim);
+
+                if ($dist_x+$dist_y+$dist_z == $depth)
+                {
+                    $new_layer_count++;
+                }
+            }
+        }
+    }
+
+    if ($new_layer_count != $expected_new_layer_count)
+    {
+       die "\$new_layer_count != \$expected_new_layer_count ==
+        $new_layer_count != $expected_new_layer_count for depth $depth
+            and ($x_lim,$y_lim,$z_lim).";
+    }
+
+    $cuboids{$key} = {d => ($depth+1), n => $new_layer_count};
+
+    if ((++$C[$new_layer_count]) > $max_C_n)
+    {
+        print "Found C[$new_layer_count] == $C[$new_layer_count]\n";
+        $max_C_n = $C[$new_layer_count];
+
+        if ($max_C_n == 1000)
+        {
+            exit(0);
+        }
+    }
+}
+
+my $max_layer_size = 1;
+
+while (1)
+{
+    for my $z (1 .. $max_layer_size)
+    {
+        Y_LOOP:
+        for my $y ($z .. $max_layer_size/$z)
+        {
+            my $x = $max_layer_size/$z/$y;
+
+            if ($x * $y * $z != $max_layer_size 
+                    or
+                $x < $y)
+            {
+                next Y_LOOP;
+            }
+
+            # print "$x,$y,$z\n";
+            my $initial_cuboid =
+                [ map { 
+                    [ map { [(1)x$z] } (1 .. $y) ]
+                    } 
+                    (1 .. $x)
+                ];
+
+            $cuboids{"$x,$y,$z"} = 
+                { d => 1, n => $max_layer_size };
+
+            add_layer($x, $y, $z);
+        }
+    }
+
+    # Now add extra layers to the existing cuboids.
+
+    # So we won't update the hash in place.
+    my @to_update;
+
+    while (my ($initial_dims, $data) = each (%cuboids))
+    {
+        if ($data->{n} < $max_layer_size)
+        {
+            push @to_update, $initial_dims;
+        }
+    }
+
+    foreach my $dims (@to_update)
+    {
+        add_layer (split(/,/, $dims));
+    }
+}
+continue
+{
+    $max_layer_size++;
+}