# HG changeset patch # User Shlomi Fish # Date 1346079867 -10800 # Node ID 3e09e6b5b4d8762f3330c46beeddfcd70262a842 # Parent 53d03b6f8a7ca3635cca577d174e1ea0fba85e05 Add more to Euler 137. It counts the diagonal rects incorrectly though. diff --git a/project-euler/147/euler-147-analysis.txt b/project-euler/147/euler-147-analysis.txt --- a/project-euler/147/euler-147-analysis.txt +++ b/project-euler/147/euler-147-analysis.txt @@ -76,4 +76,32 @@ C(n,step) = n*2-3 +General diagonal rectangles analysis: +------------------------------------- +Since the rectangles stop at midpoint, we can treat the board as having +units of 2. The points can be either (2x, 2y) or (2x+1, 2y+1). If the origin +is point (Ox,Oy), then the dimensions of a w*h diagonal rectangle are: + +( Ox , Oy ) +( Ox - w , Oy + w ) +( Ox - w + h , Oy + w + h ) +( Ox + h , Oy + h ) + +The complete span is (w+h) * (w+h) (but the origin of the span is not at +a lattice point). + +So we need the straight square with dimensions x==[-w, h] * y==[0, w+h] + +Without loss of generality, let's assume that w >= h. + +For b[x] = 2x' ; b[y] = 2y' (board dimensions), the points for such a span +are: + +1. For even points: x==[w , 2x' - h] * y==[0, 2y'-(w+h)] +(divided by 2 and rounded down and while ignoring values beyond the board +dimensions.) + +2. For the +(1,1) points: there are (x'-1) * (y'-1) points like that. + and they follow the same rules: + (1, 3, 5...) * (1, 3, 5...) diff --git a/project-euler/147/euler-147.pl b/project-euler/147/euler-147.pl --- a/project-euler/147/euler-147.pl +++ b/project-euler/147/euler-147.pl @@ -60,6 +60,12 @@ return \$board_struct; } +sub round_two_up +{ + my (\$n) = @_; + return ((\$n&0x1) ? \$n+1 : \$n); +} + sub get_total_rects { my (\$x, \$y) = @_; @@ -74,14 +80,53 @@ } } - return {num_straight_rects => \$sum}; + 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 \$num_straight_rects = get_total_rects(\$x, \$y)->{num_straight_rects}; +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";