Commits

Shlomi Fish committed dd31d7f Merge

Merged.

Comments (0)

Files changed (7)

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
+

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 $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))
+    );
+
+=begin foo
+    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).";
+    }
+
+=end foo
+
+=cut
+
+    $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);
+        }
+    }
+
+    return;
+}
+
+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++;
+}

project-euler/149/149-opt1.pl

+#!/usr/bin/perl
+
+=head1 DESCRIPTION
+
+Looking at the table below, it is easy to verify that the maximum possible sum
+of adjacent numbers in any direction (horizontal, vertical, diagonal or
+anti-diagonal) is 16 (= 8 + 7 + 1).  −253        2 9−651 3273 −18−4  8
+
+Now, let us repeat the search, b                                        ut on a
+much larger scale:
+
+First, generate four million pseudo-random numbers using a specific form of
+what is known as a "Lagged Fibonacci Generator":
+
+For 1 ≤ k ≤ 55, sk = [100003 − 200003k + 300007k3] (modulo 1000000) − 500000.
+For 56 ≤ k ≤ 4000000, sk = [sk−24 + sk−55 + 1000000] (modulo 1000000) − 500000.
+
+Thus, s10 = −393027 and s100 = 86613.
+
+The terms of s are then arranged in a 2000×2000 table, using the first 2000
+numbers to fill the first row (sequentially), the next 2000 numbers to fill the
+second row, and so on.
+
+Finally, find the greatest sum of (any number of) adjacent entries in any
+direction (horizontal, vertical, diagonal or anti-diagonal).
+
+=cut
+
+use strict;
+use warnings;
+
+# use integer;
+
+# use Math::BigInt "lib" => "GMP";
+
+package FiboRand;
+
+sub new
+{
+    return bless { _k => 1, _last_nums => [] }, shift;
+}
+
+# has '_k' => (isa => 'Math::BigInt', is => 'rw', default => sub { return 1; },);
+# has '_last_nums' => (isa => 'ArrayRef[Math::BigInt]', is => 'rw', default => sub { return []; },
+# traits => ['Array'], handles => { _push => 'push', _shift => 'shift',},);
+
+sub fetch
+{
+    my $self = shift;
+
+    my $k = $self->{_k};
+    my $s_k;
+
+    my $ln = $self->{_last_nums};
+
+    if ($k <= 55)
+    {
+        $s_k = (((100003 - 200003*$k + 300007*($k**3)) % 1000000) - 500000);
+    }
+    else
+    {
+        $s_k = ((($ln->[-24] + $ln->[-55] + 1000000) % 1000000) - 500000);
+        shift(@$ln);
+    }
+    push @$ln, $s_k;
+    $self->{_k}++;
+
+    return $s_k;
+}
+
+package main;
+
+# Unit test to the randomizer.
+{
+    my $rand = FiboRand->new;
+
+    if (0)
+    {
+    foreach my $k (1 .. 100)
+    {
+        print "$k = ", $rand->fetch(), "\n";
+    }
+    }
+
+    $rand = FiboRand->new;
+
+    for my $k ( 1 .. 9)
+    {
+        $rand->fetch();
+    }
+
+    if ($rand->fetch() != -393027)
+    {
+        die "Wrong s10!";
+    }
+
+    for my $k (11 .. 99)
+    {
+        $rand->fetch();
+    }
+
+    if ($rand->fetch() != 86613)
+    {
+        die "Wrong s100!";
+    }
+}
+
+package Max;
+
+use List::Util qw(max);
+
+# s = so far
+# e = ending here.
+sub new
+{
+    return bless { s => 0, e => 0 }, shift;
+}
+
+sub add
+{
+    my ($self, $n) = @_;
+ 
+    $self->{'s'} = max($self->{'s'}, ($self->{e} = max($self->{e} + $n, 0)));
+
+    return;
+}
+
+# g = get()
+sub g
+{
+    my ($self) = @_;
+
+    return $self->{'s'};
+}
+
+package main;
+
+use List::Util qw(max);
+
+my $rand = FiboRand->new;
+
+my $SIZE = 2_000;
+
+my $max_max = 0;
+my @vert_max = map { Max->new } (1 .. $SIZE);
+my @diag_max = map { Max->new } (1 .. $SIZE);
+my @anti_diag_max = map { Max->new } (1 .. $SIZE);
+
+my $diag_offset = 0;
+my $anti_diag_offset = 0;
+
+sub handle_row
+{
+    my $horiz = Max->new;
+    # First row.
+    foreach my $x (0 .. $SIZE-1)
+    {
+        my $s = $rand->fetch();
+
+        $vert_max[$x]->add($s);
+        $horiz->add($s);
+        $diag_max[($x+$diag_offset) % $SIZE]->add($s);
+        $anti_diag_max[($x+$anti_diag_offset) % $SIZE]->add($s);
+    }
+
+    $max_max = max(
+        $max_max, $horiz->g(), $diag_max[0]->g(), $anti_diag_max[-1]->g()
+    );
+
+    $diag_max[0] = Max->new;
+    $diag_offset++;
+
+    $anti_diag_max[-1] = Max->new;
+    $anti_diag_offset--;
+
+    return;
+}
+
+foreach my $y (1 .. $SIZE)
+{
+    if ($y % 100 == 0)
+    {
+        print "$y\n";
+    }
+    handle_row();
+}
+
+
+print "Result = ", max(
+    $max_max, (map { $_->g() } @vert_max, @diag_max, @anti_diag_max
+    )
+), "\n";

project-euler/149/149.pl

+#!/usr/bin/perl
+
+=head1 DESCRIPTION
+
+Looking at the table below, it is easy to verify that the maximum possible sum
+of adjacent numbers in any direction (horizontal, vertical, diagonal or
+anti-diagonal) is 16 (= 8 + 7 + 1).  −253        2 9−651 3273 −18−4  8
+
+Now, let us repeat the search, b                                        ut on a
+much larger scale:
+
+First, generate four million pseudo-random numbers using a specific form of
+what is known as a "Lagged Fibonacci Generator":
+
+For 1 ≤ k ≤ 55, sk = [100003 − 200003k + 300007k3] (modulo 1000000) − 500000.
+For 56 ≤ k ≤ 4000000, sk = [sk−24 + sk−55 + 1000000] (modulo 1000000) − 500000.
+
+Thus, s10 = −393027 and s100 = 86613.
+
+The terms of s are then arranged in a 2000×2000 table, using the first 2000
+numbers to fill the first row (sequentially), the next 2000 numbers to fill the
+second row, and so on.
+
+Finally, find the greatest sum of (any number of) adjacent entries in any
+direction (horizontal, vertical, diagonal or anti-diagonal).
+
+=cut
+
+use strict;
+use warnings;
+
+# use integer;
+
+# use Math::BigInt "lib" => "GMP";
+
+package FiboRand;
+
+sub new
+{
+    return bless { _k => 1, _last_nums => [] }, shift;
+}
+
+# has '_k' => (isa => 'Math::BigInt', is => 'rw', default => sub { return 1; },);
+# has '_last_nums' => (isa => 'ArrayRef[Math::BigInt]', is => 'rw', default => sub { return []; },
+# traits => ['Array'], handles => { _push => 'push', _shift => 'shift',},);
+
+sub fetch
+{
+    my $self = shift;
+
+    my $k = $self->{_k};
+    my $s_k;
+
+    my $ln = $self->{_last_nums};
+
+    if ($k <= 55)
+    {
+        $s_k = (((100003 - 200003*$k + 300007*($k**3)) % 1000000) - 500000);
+    }
+    else
+    {
+        $s_k = ((($ln->[-24] + $ln->[-55] + 1000000) % 1000000) - 500000);
+        shift(@$ln);
+    }
+    push @$ln, $s_k;
+    $self->{_k}++;
+
+    return $s_k;
+}
+
+package main;
+
+# Unit test to the randomizer.
+{
+    my $rand = FiboRand->new;
+
+    foreach my $k (1 .. 100)
+    {
+        print "$k = ", $rand->fetch(), "\n";
+    }
+
+    $rand = FiboRand->new;
+
+    for my $k ( 1 .. 9)
+    {
+        $rand->fetch();
+    }
+
+    if ($rand->fetch() != -393027)
+    {
+        die "Wrong s10!";
+    }
+
+    for my $k (11 .. 99)
+    {
+        $rand->fetch();
+    }
+
+    if ($rand->fetch() != 86613)
+    {
+        die "Wrong s100!";
+    }
+}
+
+package Max;
+
+sub new
+{
+    return bless { _so_far => 0, _ending_here => 0 }, shift;
+}
+
+sub _max
+{
+    my ($x, $y) = @_;
+
+    return ($x > $y) ? $x : $y;
+}
+
+sub add
+{
+    my ($self, $n) = @_;
+ 
+    $self->{_ending_here} = _max($self->{_ending_here} + $n, 0);
+    $self->{_so_far} = _max($self->{_so_far}, $self->{_ending_here});
+
+    return;
+}
+
+sub get_max
+{
+    my ($self) = @_;
+
+    return $self->{_so_far};
+}
+
+package main;
+
+my $rand = FiboRand->new;
+
+sub max
+{
+    my ($x, $y) = @_;
+
+    return ($x > $y) ? $x : $y;
+}
+
+my $SIZE = 2_000;
+
+my $horiz_max_max = 0;
+my @vert_max = map { Max->new } (1 .. $SIZE);
+my @diag_max = map { Max->new } (1 .. $SIZE);
+my @anti_diag_max = map { Max->new } (1 .. $SIZE);
+my $diag_max_max = 0;
+my $anti_diag_max_max = 0;
+
+sub handle_row
+{
+    my $horiz = Max->new;
+    # First row.
+    foreach my $x (0 .. $SIZE-1)
+    {
+        my $s = $rand->fetch();
+
+        $vert_max[$x]->add($s);
+        $horiz->add($s);
+        $diag_max[$x]->add($s);
+        $anti_diag_max[$x]->add($s);
+    }
+
+    $horiz_max_max = max($horiz_max_max, $horiz->get_max());
+
+    $diag_max_max = max($diag_max_max, $diag_max[0]->get_max());
+    shift(@diag_max);
+    push @diag_max, Max->new;
+
+    $anti_diag_max_max = max($anti_diag_max_max, $anti_diag_max[-1]->get_max());
+    pop(@anti_diag_max);
+    unshift @anti_diag_max, Max->new;
+
+    return;
+}
+
+foreach my $y (1 .. $SIZE)
+{
+    if ($y % 100 == 0)
+    {
+        print "$y\n";
+    }
+    handle_row();
+}
+
+sub multi_max
+{
+    my $aref = shift;
+
+    my $max = 0;
+
+    foreach my $n (@$aref)
+    {
+        if ($n > $max)
+        {
+            $max = $n;
+        }
+    }
+    return $max;
+}
+
+print "Result = ", multi_max(
+    [
+    $horiz_max_max, $anti_diag_max_max, $diag_max_max, (map { $_->get_max() } @vert_max, @diag_max, @anti_diag_max
+    )
+    ]
+), "\n";

project-euler/75/75-analysis.txt

  1   1         0 |  0
 -------------------------
 
+------------------------------------------
+
+If A^2 + B^2 = C^2 then so will (mA)^2 + (mB)^2 = (mC)^2
+
+------------------------------------------
+
+A^2 + B^2 = C^2 ; A+B+C <= 1,500,000

project-euler/75/75-take2.pl

+#!/usr/bin/perl
+
+use strict;
+use warnings;
+
+=head1 DESCRIPTION
+
+It turns out that 12 cm is the smallest length of wire that can be bent to form an integer sided right angle triangle in exactly one way, but there are many more examples.
+
+12 cm: (3,4,5)
+24 cm: (6,8,10)
+30 cm: (5,12,13)
+36 cm: (9,12,15)
+40 cm: (8,15,17)
+48 cm: (12,16,20)
+
+In contrast, some lengths of wire, like 20 cm, cannot be bent to form an integer sided right angle triangle, and other lengths allow more than one solution to be found; for example, using 120 cm it is possible to form exactly three different integer sided right angle triangles.
+
+120 cm: (30,40,50), (20,48,52), (24,45,51)
+
+Given that L is the length of the wire, for how many values of L ≤ 1,500,000 can exactly one integer sided right angle triangle be formed?
+
+Note: This problem has been changed recently, please check that you are using the right parameters.
+
+=cut
+
+sub gcd
+{
+    my ($n, $m) = @_;
+
+    if ($m == 0)
+    {
+        return $n;
+    }
+
+    return gcd($m,$n % $m);
+}
+
+my $limit = 1_500_000;
+
+my $verdicts = "";
+
+my $hypotenuse_lim = int($limit/2);
+
+my $major_side_limit = int($limit/2);
+
+MAJOR_SIDE:
+for my $major_side (4 .. $major_side_limit)
+{
+    if ($major_side % 100 == 0)
+    {
+        print "Maj=$major_side\n";
+    }
+    MINOR_SIDE:
+    for my $minor_side (3 .. ($major_side - 1))
+    {
+        if (gcd( $major_side , $minor_side ) != 1)
+        {
+            next MINOR_SIDE;
+        }
+
+        my $hypot_sq = $major_side * $major_side + $minor_side * $minor_side;
+
+        my $hypot = sqrt($hypot_sq);
+        if ($hypot == int($hypot))
+        {
+            my $sum = $major_side + $minor_side + $hypot;
+            
+            if ($sum > $limit)
+            {
+                last MINOR_SIDE;
+            }
+
+            my $sum_product = $sum;
+
+            while ($sum_product < $limit)
+            {
+                # Only even numbers can be sums, so we can divide the index
+                # by 2.
+                # See 75-analysis.txt
+                my $idx = ($sum_product>>1);
+                if (vec($verdicts, $idx, 2) != 2)
+                {
+                    vec($verdicts, $idx, 2)++;
+                }
+                $sum_product += $sum;
+            }
+        }
+    }
+}
+
+my $count = 0;
+foreach my $sum_idx ((12>>1) .. ($limit>>1))
+{
+    if (vec($verdicts, $sum_idx, 2) == 1)
+    {
+        $count++
+    }
+}
+
+print "Count = $count\n";
+

project-euler/75/75.pl

 use strict;
 use warnings;
 
+=head1 DESCRIPTION
+
+It turns out that 12 cm is the smallest length of wire that can be bent to form an integer sided right angle triangle in exactly one way, but there are many more examples.
+
+12 cm: (3,4,5)
+24 cm: (6,8,10)
+30 cm: (5,12,13)
+36 cm: (9,12,15)
+40 cm: (8,15,17)
+48 cm: (12,16,20)
+
+In contrast, some lengths of wire, like 20 cm, cannot be bent to form an integer sided right angle triangle, and other lengths allow more than one solution to be found; for example, using 120 cm it is possible to form exactly three different integer sided right angle triangles.
+
+120 cm: (30,40,50), (20,48,52), (24,45,51)
+
+Given that L is the length of the wire, for how many values of L ≤ 1,500,000 can exactly one integer sided right angle triangle be formed?
+
+Note: This problem has been changed recently, please check that you are using the right parameters.
+
+=cut
+
 my $limit = 1_500_000;
 
 my $verdicts = "";
 HYPO:
 for my $hypotenuse_length (5 .. $hypotenuse_lim)
 {
-    if ($hypotenuse_length & 0x1)
-    {
-        
-    }
-
     print "$hypotenuse_length\n" if (not $hypotenuse_length % 1_000);
     my $hypot_sq = $hypotenuse_length ** 2;