project-euler / 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 2-dimensional cache.
# $Rects_Coefficients_Cache[$rect_x][$rect_y] = { min => $min, offset => $offset};
# Formula for step is calculated at 2*$board_dim + $offset
my @Rects_Coefficients_Cache;

# A 4-dimensional cache:
# 0 - board large dim.
# 1 - board small dim.
# 2 - rect large dim.
# 3 - rect large dim.
# Each value is:
# {
#

# Cache for the boards:
# $Boards_Cache[$board_x][$board_y] = { 'num_unique' => , 'rects' => \@rects, }
# rects is:
# $rects[$rect_x][$rect_y]
my @Boards_Cache;

sub get_unique_rects
{
    # $x >= $y >= $rect_x , $rect_y
    my ($x, $y, $rect_x, $rect_y) = @_;

    my $board_struct = ($Boards_Cache[$x][$y] //= +{});

    if (! defined($board_struct->{num_unique}))
    {
        # Calculate the unique rectangles.
        $board_struct->{rects} //= [];
    }

    return $board_struct;
}

sub round_two_up
{
    my ($n) = @_;
    return (($n&0x1) ? $n+1 : $n);
}

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);
        }
    }

    my $diag_sum = 0;

    foreach my $xx (1 .. $x)
    {
        foreach my $yy (1 .. $y)
        {
            foreach my $rect_x (1 .. ($xx<<1))
            {
                foreach my $rect_y (1 .. ($yy<<1))
                {
                    my $x_even_start = $rect_x;
                    my $x_even_end = (($xx<<1) - $rect_y);

                    my $y_even_end = (($yy<<1) - ($rect_x+$rect_y));

                    # For the even diagonals.
                    if ($x_even_end > $x_even_start and $y_even_end > 0)
                    {
                        $diag_sum +=
                        (((($x_even_end&(~0x1)) - round_two_up($x_even_start)
                        >> 1 ) * ($y_even_end >> 1)) <<
                            ($rect_x == $rect_y ? 0 : 1)
                        );
                        $diag_sum +=
                        (((((($x_even_end&0x1)?$x_even_end:$x_even_end-1) - ($x_even_start|0x1))
                        >> 1 ) * (($y_even_end >> 1) - 1)) <<
                            ($rect_x == $rect_y ? 0 : 1)
                        );
                    }

                }
            }
        }
    }

    return {num_straight_rects => $sum, num_diag_rects => $diag_sum};
}

my ($x, $y) = @ARGV;

# my $num_rects = get_rects(47, 43, 47, 43);
my $rects_struct = get_total_rects($x, $y);
my $num_straight_rects = $rects_struct->{num_straight_rects};
my $num_diag_rects = $rects_struct->{num_diag_rects};

print "Straight Rects = $num_straight_rects\n";
print "Diag Rects = $num_diag_rects\n";
print "Total sum = " , $num_straight_rects + $num_diag_rects, "\n";
Tip: Filter by directory path e.g. /media app.js to search for public/media/app.js.
Tip: Use camelCasing e.g. ProjME to search for ProjectModifiedEvent.java.
Tip: Filter by extension type e.g. /repo .js to search for all .js files in the /repo directory.
Tip: Separate your search with spaces e.g. /ssh pom.xml to search for src/ssh/pom.xml.
Tip: Use ↑ and ↓ arrow keys to navigate and return to view the file.
Tip: You can also navigate files with Ctrl+j (next) and Ctrl+k (previous) and view the file with Ctrl+o.
Tip: You can also navigate files with Alt+j (next) and Alt+k (previous) and view the file with Alt+o.