Shlomi Fish avatar Shlomi Fish committed a632037

Optimisation.

Comments (0)

Files changed (1)

project-euler/152/euler-152.pl

 use v5.16;
 
 use Math::BigRat only => 'GMP';
-use List::MoreUtils qw(any uniq);
+use List::MoreUtils qw(any all uniq);
 
 
 sub slow_sq_frac
 {
     my ($to_check, $so_far, $sum) = @_;
 
-    # print "Checking: Start=@$to_check ; $sum+[@$so_far]\n";
+    print "Checking: Start=@$to_check ; $sum+[@$so_far]\n";
 
     if ($sum == $target)
     {
             }
             @new_factors
         );
-        my %new_factors_contains_lookup =
+
+        if (all { scalar(@$_) } @new_factors_contains)
+        {
+            my %new_factors_contains_lookup =
             (map { map { $_ => 1 } @$_ } @new_factors_contains);
 
-        my @factors_not_contains = (grep
-            { !exists($new_factors_contains_lookup{$_}) }
-            keys @$new_to_check
-        );
+            my @factors_not_contains = (grep
+                { !exists($new_factors_contains_lookup{$_}) }
+                keys @$new_to_check
+            );
 
-        my $iter_factors_recurse = sub {
-            my ($masks) = @_;
-            my $idx = @$masks;
+            my $iter_factors_recurse = sub {
+                my ($masks) = @_;
+                my $idx = @$masks;
 
-            if ($idx == @new_factors)
-            {
-                my @factors = sort {$a <=> $b } uniq (map {
-                    my $i = $_;
-                    @{$new_factors_contains[$i]}[grep { (($masks->[$i]>>$_)&0x1) } keys(@{$new_factors_contains[$i]})]
-                    } (0 .. $#$masks));
+                if ($idx == @new_factors)
+                {
+                    my @factors = sort {$a <=> $b } uniq (map {
+                        my $i = $_;
+                        @{$new_factors_contains[$i]}[grep { (($masks->[$i]>>$_)&0x1) } keys(@{$new_factors_contains[$i]})]
+                        } (0 .. $#$masks));
 
-                my $new_new_sum = $new_sum;
+                    my $new_new_sum = $new_sum;
 
-                foreach my $f (@factors)
-                {
-                    $new_new_sum += $sq_fracs[$new_to_check->[$f]];
+                    foreach my $f (@factors)
+                    {
+                        $new_new_sum += $sq_fracs[$new_to_check->[$f]];
+                    }
+
+                    recurse([@$new_to_check[@factors_not_contains]],
+                        [sort { $a <=> $b} @$so_far, $first, @$new_to_check[@factors]],
+                        $new_new_sum->bnorm(),
+                    );
+                    return;
                 }
 
-                recurse([@$new_to_check[@factors_not_contains]],
-                    [sort { $a <=> $b} @$so_far, $first, @$new_to_check[@factors]],
-                    $new_new_sum->bnorm(),
-                );
+                foreach my $new_mask (1 .. ((1 << @{$new_factors_contains[$idx]})-1))
+                {
+                    __SUB__->([@$masks, $new_mask]);
+                }
+
                 return;
-            }
+            };
 
-            foreach my $new_mask (1 .. ((1 << @{$new_factors_contains[$idx]})-1))
-            {
-                __SUB__->([@$masks, $new_mask]);
-            }
-
-            return;
-        };
-
-        $iter_factors_recurse->([]);
+            $iter_factors_recurse->([]);
+        }
 
         # recurse($first+1, [@$so_far, $first], $new_sum);
     }
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.