Shlomi Fish avatar Shlomi Fish committed 2cfde38

Problem 91 was solved successfully.

Comments (0)

Files changed (2)

project-euler/91/Euler91.pm

 use strict;
 use warnings;
 
+use Math::GMP;
+
+use List::Util qw(min);
+
 =head1 DESCRIPTION
 
 The points P (x_(1), y_(1)) and Q (x_(2), y_(2)) are plotted at integer 
     return $x_len * $y_len;
 }
 
+=head2 Right angle at one of (x1,y1) or (x2,y2).
+
+If it's in (x1,y1) then we can flip it and get the same for (x2,y2). So
+we can calculate only for (x1,y1) and multiply by 2.
+
+If the corner is in (x1,y1), then the other corner should be at offsets
+along d(x=y1,y=x1), only we need to make sure they are coprime numbers (i.e:
+their gcd is 0).
+
+=cut
+
+sub _get_num_other_helper
+{
+    my ($x_len, $y_len) = @_;
+
+    my @limits = ($x_len, $y_len);
+
+    my @p2_limits = ($x_len, 0);
+
+    my $count = 0;
+
+    foreach my $delta_x (1 .. $limits[0])
+    {
+        DELTA_Y:
+        foreach my $delta_y (1 .. $limits[1])
+        {
+            if (Math::GMP->new($delta_y)->bgcd($delta_x) != 1)
+            {
+                next DELTA_Y;
+            }
+            my $max_p1_multi = min(int($x_len / $delta_x), int($y_len / $delta_y));
+
+            my @delta2 = ($delta_y, -$delta_x);
+            foreach my $p1_multi (1 .. $max_p1_multi)
+            {
+                my @coords = ($p1_multi * $delta_x, $p1_multi * $delta_y);
+                my $max_p2_multi = (min(
+                    map { int(($p2_limits[$_]-$coords[$_]) / $delta2[$_]) }
+                    (0 .. 1)
+                ));
+
+                # print "[@coords] $max_p2_multi\n";
+
+                $count += $max_p2_multi;
+            }
+        }
+    }
+
+    # Deal with the delta_x = 0 case
+    $count += $x_len*$y_len;
+
+    return $count;
+}
+
+sub get_num_other_triangles
+{
+    return 2 * _get_num_other_helper(@_);
+}
+
 1;
 

project-euler/91/t/91.t

 use strict;
 use warnings;
 
-use Test::More tests => 1;
+use Test::More tests => 2;
 
 use Euler91;
 
 # TEST
 is (get_num_O_right_angle_triangles(2,2), 4, "2*2 O triangles");
+
+# TEST
+is (get_num_other_triangles(2,2), 10, "2*2 O triangles");
+
+print get_num_O_right_angle_triangles(50,50)+get_num_other_triangles(50,50), "\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.