Commits

Shlomi Fish committed 99dcadd

More optimisations.

Comments (0)

Files changed (2)

project-euler/126/126-planning.txt

 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
 
+Sum of Series:
+==============
+
+If we have a series a[0], a[1], a[2], a[3], where a[n+1]-a[n] = b[0]+d*n,
+then a[n]-a[0] = Sum(b[0], b[0]+d, b[0]+d*2...,b[0]+d*(n-1)) =
+(b[0]+b[0]+d*(n-1))*n)/2 = n*b[0] + d * n * (n-1) / 2
+
+Therefore: a[n] = a[0] + n*b[0] + d * n * (n-1) / 2

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

 
 my @C;
 
+# Used to be:
+# <<<
 # Matches $X,$Y,$Z (where $X >= $Y >= $Z) to the cuboid array and maximal 
 # reached layer.
-my %cuboids;
+# >>>
+# Now we no longer need the $X,$Y,$Z.
+#
+# Since the counts are divisible by 2 and are kept multiplied by 2, we
+# keep their halfs.
+my @cuboids;
 
 my $max_C_n = 0;
 
-sub add_layer
-{
-    my ($key) = @_;
-
-    my $rec = $cuboids{$key};
-
-    return add_count($rec->{n} += ($rec->{d} += 8));
-}
-
 sub add_count
 {
     my ($count) = @_;
 
     if ((++$C[$count]) > $max_C_n)
     {
-        print "Found C[$count] == $C[$count]\n";
+        print "Found C[@{[$count*2]}] == $C[$count]\n";
         $max_C_n = $C[$count];
 
         if ($max_C_n == 1000)
             # ];
             #
             my $new_layer_count = 
-                (($x*$y+$x*$z+$z*$y)<<1);
+                ($x*($y+$z)+$z*$y);
 
             # We increase the depth's delta by 8 each time.
-            $cuboids{"$x,$y,$z"} =
-                { d => ((($x+$y+$z)<<2)-8), n => $new_layer_count};
+            push @cuboids, { d => ((($x+$y+$z)<<1)-4), n => $new_layer_count};
 
             add_count($new_layer_count);
         }
     }
 
     # 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))
+    foreach my $rec (@cuboids)
     {
-        if ($data->{n} < $max_layer_size)
+        while ($rec->{n} < $max_layer_size)
         {
-            push @to_update, $initial_dims;
+            add_count($rec->{n} += ($rec->{d} += 4));
         }
     }
-
-    foreach my $dims (@to_update)
-    {
-        add_layer ($dims);
-    }
 }
 continue
 {