Commits

Shlomi Fish committed 5ba74d6

Add more to Euler #147.

Comments (0)

Files changed (2)

project-euler/147/euler-147-analysis.txt

 
 C(n,step) = n-1 * 2
 
+2* 2 diagonal rectangles:
+-------------------------
 
+C(1,1) = 0 ; C(2,1) = 0 ; C(2,2) = 1
+
+C(2,3) = C(2,2)+1 ; C(2,4) = C(2,3) + 1 ; C(2,step) = 1
+
+C(3,3) = C(2,3) + 3 ; C(3,4) = C(3,3) + 3 ; C(3,step) = 3
+
+C(4,4) = C(3,4) + 5 ; C(4,step) = 5
+
+C(5,step) = 7
+
+C(6,step) = 9
+
+C(n,step) = n*2-3;
+
+1*3 diagonal rectangles:
+------------------------
+
+C(1,1) = 0 ; C(2,1) = 0; C(2,2) = 0
+
+C(2,3) = 1 (in each direction - so 2 * 1 overall)
+
+C(2,4) = C(2,3) + 1 ; C(2,step) = 1
+
+C(3,3) = C(2,3) + 3 ; C(3,step)  = 3
+
+C(4,4) = C(3,4) + 5 ; C(4,step) = 5
+
+C(n,step) = n*2-3
+
+

project-euler/147/euler-147.pl

+#!/usr/bin/perl
+
+use strict;
+use warnings;
+
+use 5.014;
+
+=head1 DESCRIPTION
+
+In a 3x2 cross-hatched grid, a total of 37 different rectangles could be
+situated within that grid as indicated in the sketch.
+
+There are 5 grids smaller than 3x2, vertical and horizontal dimensions being
+important, i.e. 1x1, 2x1, 3x1, 1x2 and 2x2. If each of them is cross-hatched,
+the following number of different rectangles could be situated within those
+smaller grids:
+
+1x1: 1 2x1: 4 3x1: 8 1x2: 4 2x2: 18
+
+Adding those to the 37 of the 3x2 grid, a total of 72 different rectangles
+could be situated within 3x2 and smaller grids.
+
+How many different rectangles could be situated within 47x43 and smaller grids?
+
+=cut
+
+# A 4-dimensional cache:
+# 0 - board large dim.
+# 1 - board small dim.
+# 2 - rect large dim.
+# 3 - rect large dim.
+# Each value is:
+# {
+my @Cache;
+
+sub get_unique_rects
+{
+    # $x >= $y >= $rect_x , $rect_y
+    my ($x, $y, $rect_x, $rect_y) = @_;
+
+    my $struct = ($Cache[$x][$y][$rect_x][$rect_y] //= {});
+
+    # No longer needed because calculated directly in get_total_rects()
+    # my $unique_num_straight = ($x-$rect_x+1) * ($y-$rect_y+1);
+    # $struct->{unique_num_straight} = $unique_num_straight;
+    #
+
+
+
+    return $struct;
+}
+
+sub get_total_rects
+{
+    my ($x, $y) = @_;
+
+    my $sum = 0;
+
+    foreach my $xx (1 .. $x)
+    {
+        foreach my $yy (1 .. $y)
+        {
+            $sum += $xx * $yy * ($x - $xx + 1) * ($y - $yy + 1);
+        }
+    }
+
+    return {num_straight_rects => $sum};
+}
+
+my ($x, $y) = @ARGV;
+
+# my $num_rects = get_rects(47, 43, 47, 43);
+my $num_straight_rects = get_total_rects($x, $y)->{num_straight_rects};
+
+print "Straight Rects = $num_straight_rects\n";
+
+