Commits

Shlomi Fish committed 3b5593f Merge

Merged

Comments (0)

Files changed (6)

project-euler/139/139-take1.pl

+#!/usr/bin/perl
+
+use strict;
+use warnings;
+
+=head1 DESCRIPTION
+
+Let (a, b, c) represent the three sides of a right angle triangle with integral length sides. It is possible to place four such triangles together to form a square with length c.
+
+For example, (3, 4, 5) triangles can be placed together to form a 5 by 5 square with a 1 by 1 hole in the middle and it can be seen that the 5 by 5 square can be tiled with twenty-five 1 by 1 squares.
+
+However, if (5, 12, 13) triangles were used then the hole would measure 7 by 7 and these could not be used to tile the 13 by 13 square.
+
+Given that the perimeter of the right triangle is less than one-hundred million, how many Pythagorean triangles would allow such a tiling to take place?
+=cut
+
+=head1 Keywords
+
+Pythagoras, Euler's Formula, Hypoteneuse
+
+=cut
+
+sub gcd
+{
+    my ($n, $m) = @_;
+
+    if ($m == 0)
+    {
+        return $n;
+    }
+
+    return gcd($m,$n % $m);
+}
+
+my $limit = 100_000_000;
+my $half_limit = ($limit >> 1);
+
+my $hypotenuse_lim = int($limit/2);
+
+my $major_side_limit = int($limit/2);
+
+# Euclid's formula
+my $m_limit = int(sqrt($hypotenuse_lim));
+
+my $count = 0;
+
+for my $m (2 .. $m_limit)
+{
+    if ($m % 1000 == 0)
+    {
+        print "M=$m\n";
+    }
+    my $n = ((($m & 0x1) == 0) ? 1 : 2);
+
+    N_LOOP:
+    while ($n < $m)
+    {
+        if (gcd( $m, $n ) == 1)
+        {
+            my $half_sum = $m * ($m + $n);
+            if ($half_sum > $half_limit)
+            {
+                last N_LOOP;
+            }
+
+            my ($aa, $bb, $cc) = ($m*$m-$n*$n, 2*$m*$n, $m*$m+$n*$n);
+
+            if ($cc % abs($bb-$aa) == 0)
+            {
+                $count += int( $half_limit / $half_sum );
+            }
+        }
+    }
+    continue
+    {
+        $n += 2;
+    }
+}
+
+print "Count = $count\n";
+

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

+The vertical/horizontal number of rectangles is trivial:
+
+If the rectangle dimensions are  s[x],s[y] and the board dimensions are
+b[x], b[y] then there are ( b[x] - (s[x] - 1) ) * ( b[y] - (s[y] - 1) )
+squares there of that size.
+
+Now for the diagonal rectangles:
+
+1 * 1 rectangles:
+-----------------
+
+If the diagonal rectangle is 1*1 then for C ( b = (1,1) ) = 0, and
+C(b(2,1)) = 1 , C(b(3,1)) = 2 and so C(b(n+1,1)) = n;
+
+    (C == count of 1*1 diagonals rectangles)
+
+C(b(2,2)) = 4 , C(b(2,3)) = 7 , C(b(2,4)) = 10 , C(b(2,n+2)) = 4+n*3
+
+C(b(3,3)) = 12 , C(b(3,4)) = 12+5 = 17  C(b(3,n+3)) = 12 + n*5
+
+C(b(4,4)) = C(b(3,4)) + 7 ; C(b(4,5)) = C(b(4,4)) + 7
+
+And in general:
+
+* C(b(1,1)) = 0 C(b(n+1,1)) = C(b(n,1)) + 1
+* C(b(n+1,n+1)) = C(b(n+1,n)) + 2*n+1
+* C(b(m+1>n+1,n+1)) = C(b(m, n+1)) + 2*n+1
+
+2 * 1 diagonal rectangles:
+--------------------------
+
+C(1,1) = 0 ; C(2,1) = 0 ; C(2,2) = 2 (but there are two possible directions in
+which the 2 * 1 block can be aligned so it's twice that and 4).
+
+C(2,3) = 4 ; C(2,4) = 6 ; C(2,step) = 2
+
+C(3,3) = C(2,3) + 4 ; C(3,4) = C(3,3) + 4 ; C(3,step) = 4
+
+C(4,4) = C(3,4) + 6 ; C(4,5) = C(3,4) + 6 ; C(4,step) = 6
+
+C(5,step) = 8
+
+C(6,step) = 10
+
+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
+
+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...)

project-euler/147/euler-147.pl

+#!/usr/bin/perl
+
+use strict;
+use warnings;
+
+use 5.014;
+
+use Test::More;
+
+=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 diag_rects
+{
+    my ($xx, $yy, $rect_x, $rect_y) = @_;
+
+    my $x_even_start = $rect_x;
+    my $x_even_end = (($xx<<1) - $rect_y);
+
+    if ($x_even_end < 0)
+    {
+        return;
+    }
+
+    my $y_even_end = (($yy<<1) - ($rect_x+$rect_y));
+
+    my $x_even_end_norm = ($x_even_end & (~0x1));
+    my $x_even_start_norm = round_two_up($x_even_start);
+
+    my $even_count = 0;
+    # For the even diagonals.
+    if ($x_even_end_norm >= $x_even_start_norm and $y_even_end >= 0)
+    {
+        $even_count =
+        (
+            ((($x_even_end_norm - $x_even_start_norm) >> 1) + 1)
+            * (($y_even_end >> 1)+ 1)
+        );
+    }
+
+    my $x_odd_end =
+    (($x_even_end&0x1)?$x_even_end:($x_even_end-1));
+    my $x_odd_start = ($x_even_start|0x1);
+    my $y_odd_start = 1;
+    my $y_odd_end = $y_even_end;
+
+    my $odd_count = 0;
+    if ($x_odd_end >= $x_odd_start and $y_odd_end >= $y_odd_start)
+    {
+        $odd_count =
+        ((
+                ( (($x_odd_end - $x_odd_start) >> 1) + 1)
+                * (((($y_odd_end - $y_odd_start)>>1)+1))
+            ) <<
+            0 # ($rect_x == $rect_y ? 0 : 1)
+        );
+    }
+
+    return ($even_count, $odd_count);
+}
+
+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))
+            {
+                RECT_Y:
+                foreach my $rect_y (1 .. ($yy<<1))
+                {
+                    if (my ($even_count, $odd_count) = diag_rects($xx, $yy, $rect_x, $rect_y))
+                    {
+                        $diag_sum += $even_count + $odd_count;
+                    }
+                    else
+                    {
+                        last RECT_Y;
+                    }
+                }
+            }
+        }
+    }
+
+    return {num_straight_rects => $sum, num_diag_rects => $diag_sum};
+}
+
+sub test_diag
+{
+    local $Test::Builder::Level = $Test::Builder::Level + 1;
+
+    my ($xx, $yy, $diag_x, $diag_y, $want_ret_aref, $blurb) = @_;
+
+    my @have_ret = diag_rects($xx, $yy, $diag_x, $diag_y);
+
+    is_deeply(
+        \@have_ret,
+        $want_ret_aref,
+        $blurb
+    );
+}
+
+if (1)
+{
+    test_diag(1,1,1,1, [0, 0], "1,1,1,1");
+    test_diag(2,1,1,1, [1, 0], "1,2,1,1");
+    test_diag(1,2,1,1, [0, 1], "1,2,1,1");
+    test_diag(3,1,1,1, [2, 0], "3,1,1,1");
+    test_diag(1,3,1,1, [0, 2], "1,2,1,1");
+    test_diag(4,1,1,1, [3, 0], "3,1,1,1");
+    test_diag(1,4,1,1, [0, 3], "1,2,1,1");
+    test_diag(2,2,1,1, [2, 2],  "2,2,1,1");
+    test_diag(2,2,1,2, [1, 1],  "2,2,1,2");
+
+    done_testing();
+}
+
+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";
+
+
Added
New image
+<?xml version="1.0" encoding="UTF-8" standalone="no"?>
+<!-- Created with Inkscape (http://www.inkscape.org/) -->
+
+<svg
+   xmlns:dc="http://purl.org/dc/elements/1.1/"
+   xmlns:cc="http://creativecommons.org/ns#"
+   xmlns:rdf="http://www.w3.org/1999/02/22-rdf-syntax-ns#"
+   xmlns:svg="http://www.w3.org/2000/svg"
+   xmlns="http://www.w3.org/2000/svg"
+   xmlns:sodipodi="http://sodipodi.sourceforge.net/DTD/sodipodi-0.dtd"
+   xmlns:inkscape="http://www.inkscape.org/namespaces/inkscape"
+   width="744.09448819"
+   height="1052.3622047"
+   id="svg2"
+   version="1.1"
+   inkscape:version="0.48.3.1 r9886"
+   sodipodi:docname="euler-147.svg">
+  <defs
+     id="defs4" />
+  <sodipodi:namedview
+     id="base"
+     pagecolor="#ffffff"
+     bordercolor="#666666"
+     borderopacity="1.0"
+     inkscape:pageopacity="0.0"
+     inkscape:pageshadow="2"
+     inkscape:zoom="3.959798"
+     inkscape:cx="248.48764"
+     inkscape:cy="848.96864"
+     inkscape:document-units="px"
+     inkscape:current-layer="layer1"
+     showgrid="true"
+     inkscape:window-width="829"
+     inkscape:window-height="633"
+     inkscape:window-x="0"
+     inkscape:window-y="385"
+     inkscape:window-maximized="0">
+    <inkscape:grid
+       type="xygrid"
+       id="grid2985"
+       empspacing="5"
+       visible="true"
+       enabled="true"
+       snapvisiblegridlinesonly="true"
+       units="mm"
+       spacingx="2mm"
+       spacingy="2mm" />
+  </sodipodi:namedview>
+  <metadata
+     id="metadata7">
+    <rdf:RDF>
+      <cc:Work
+         rdf:about="">
+        <dc:format>image/svg+xml</dc:format>
+        <dc:type
+           rdf:resource="http://purl.org/dc/dcmitype/StillImage" />
+        <dc:title></dc:title>
+      </cc:Work>
+    </rdf:RDF>
+  </metadata>
+  <g
+     inkscape:label="Layer 1"
+     inkscape:groupmode="layer"
+     id="layer1">
+    <g
+       id="g4654">
+      <rect
+         y="166.53542"
+         x="212.59842"
+         height="7.0866141"
+         width="7.0866141"
+         id="rect3006"
+         style="color:#000000;fill:#ffffff;fill-opacity:0.68918917999999996;stroke:#000000;stroke-width:0.5;stroke-linecap:butt;stroke-linejoin:miter;stroke-miterlimit:4;stroke-opacity:0.99547514000000004;stroke-dasharray:none;stroke-dashoffset:0;marker:none;visibility:visible;display:inline;overflow:visible;enable-background:accumulate" />
+      <path
+         inkscape:connector-curvature="0"
+         id="path4650"
+         d="m 219.68504,173.62203 -7.08661,-7.08662"
+         style="fill:none;stroke:#000000;stroke-width:0.5;stroke-linecap:butt;stroke-linejoin:miter;stroke-opacity:1;stroke-miterlimit:4;stroke-dasharray:none" />
+      <path
+         inkscape:connector-curvature="0"
+         id="path4652"
+         d="m 219.68504,166.53541 -7.08661,7.08662"
+         style="fill:none;stroke:#000000;stroke-width:0.5;stroke-linecap:butt;stroke-linejoin:miter;stroke-opacity:1;stroke-miterlimit:4;stroke-dasharray:none" />
+    </g>
+  </g>
+</svg>

project-euler/148/148.hs

+pascal_triangle_inc :: [Int] -> [Int]
+pascal_triangle_inc (x:[]) = [x,x]
+pascal_triangle_inc (x:xs) = x:((x+y) `mod` 7):ys where
+    y:ys = pascal_triangle_inc xs
+
+total_pascal :: Int -> (Int, [Int])
+total_pascal 1 = (1,[1])
+total_pascal n = let (mid_sum, prev_pascal) = total_pascal (n-1)
+                 in let this_pascal = pascal_triangle_inc prev_pascal
+                    in (mid_sum + length( filter (\x -> x /= 0) this_pascal), this_pascal)

project-euler/148/148.pl

+#!/usr/bin/perl
+
+use strict;
+use warnings;
+
+my $prev_row_count = 1;
+my $prev_row = '';
+my $next_row = '';
+
+my @mod = (map { my $y = $_; [map { ($y+$_)%7 } (0 .. 6)] } (0 .. 6));
+
+my $result_count = 0;
+# while ($row_count++ <= 1_000_000_000)
+vec($prev_row, 0, 8) = 1;
+$result_count++;
+while ($prev_row_count < 1_000_000_000)
+{
+    if ($prev_row_count % 1_000 == 0)
+    {
+        print "Reached $prev_row_count\n";
+    }
+    vec($next_row, 0, 8) = 1;
+    for my $i (1 .. $prev_row_count-1)
+    {
+        if (
+        vec($next_row, $i, 8) = $mod[vec($prev_row, $i-1, 8)][vec($prev_row, $i, 8)]
+        )
+        {
+            $result_count++;
+        }
+    }
+    vec($next_row, $prev_row_count, 8) = 1;
+    # For the two 1s on the sides of the row.
+    $result_count += 2;
+}
+continue
+{
+    $prev_row = $next_row;
+    $next_row = '';
+    $prev_row_count++;
+}
+
+print "Result count = $result_count\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.