Commits

Shlomi Fish committed 0e8edc6

Avoid duplicates.

  • Participants
  • Parent commits a632037

Comments (0)

Files changed (1)

File project-euler/152/euler-152.pl

 {
     my ($to_check, $so_far, $sum) = @_;
 
-    print "Checking: Start=@$to_check ; $sum+[@$so_far]\n";
+    # print "Checking: ToCheck=@$to_check ; $sum+[@$so_far]\n";
 
     if ($sum == $target)
     {
                 keys @$new_to_check
             );
 
+            my %encountered_factors;
+
             my $iter_factors_recurse = sub {
                 my ($masks) = @_;
                 my $idx = @$masks;
                         @{$new_factors_contains[$i]}[grep { (($masks->[$i]>>$_)&0x1) } keys(@{$new_factors_contains[$i]})]
                         } (0 .. $#$masks));
 
-                    my $new_new_sum = $new_sum;
+                    if (! $encountered_factors{join(',',@factors)}++)
+                    {
+                        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(),
+                        );
                     }
-
-                    recurse([@$new_to_check[@factors_not_contains]],
-                        [sort { $a <=> $b} @$so_far, $first, @$new_to_check[@factors]],
-                        $new_new_sum->bnorm(),
-                    );
                     return;
                 }