Shlomi Fish avatar Shlomi Fish committed e6b9c75

Add euler-88.

Currently takes way too long.

Comments (0)

Files changed (1)

project-euler/88/euler-88.pl

+#!/usr/bin/perl
+
+use strict;
+use warnings;
+
+use integer;
+
+use List::Util qw(sum);
+
+no warnings 'recursion';
+
+sub smallest_product_n
+{
+    my ($n) = @_;
+
+    my $sum = $n;
+
+    while (1)
+    {
+        my $recurse;
+
+        $recurse = sub {
+            my ($num_left, $min_i, $prod_so_far, $sum_left) = @_;
+
+            if ($prod_so_far > $sum)
+            {
+                return;
+            }
+            # print "(num_left=$num_left, min_i=$min_i, prod_so_far=$prod_so_far, sum_left=$sum_left) Sum=$sum\n";
+
+            if ($num_left == 1)
+            {
+                return ($prod_so_far * $sum_left == $sum);
+            }
+            else
+            {
+                I_LOOP:
+                for my $i ($min_i .. $sum_left)
+                {
+                    if ($sum_left < $i * ($num_left-1))
+                    {
+                        last I_LOOP;
+                    }
+                    if ($recurse->(
+                        $num_left-1, $i, $prod_so_far*$i, $sum_left-$i
+                    ))
+                    {
+                        return 1;
+                    }
+                }
+                return;
+            }
+        };
+
+        if ($recurse->($n, 1, 1, $sum))
+        {
+            return $sum;
+        }
+    }
+    continue
+    {
+        $sum++;
+    }
+}
+
+my %numbers = 0;
+
+for my $n (2 .. 12_000)
+{
+    print "Reached $n\n";
+    $numbers{smallest_product_n($n)}++;
+}
+
+print "Sum = ", sum(keys(%numbers)), "\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.