# project-euler / project-euler / 147 / euler-147.pl

 ``` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77``` ```#!/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"; ```