Shlomi Fish avatar Shlomi Fish committed ea55dea

Add the first version.

Comments (0)

Files changed (1)

project-euler/122/euler-122.pl

+#!/usr/bin/perl
+
+use strict;
+use warnings;
+
+use integer;
+
+use List::MoreUtils qw(uniq);
+use List::Util qw(min);
+
+=head1 DESCRIPTION
+
+The most naive way of computing n15 requires fourteen multiplications:
+
+n × n × ... × n = n15
+
+But using a "binary" method you can compute it in six multiplications:
+
+n × n = n2
+n2 × n2 = n4
+n4 × n4 = n8
+n8 × n4 = n12
+n12 × n2 = n14
+n14 × n = n15
+
+However it is yet possible to compute it in only five multiplications:
+
+n × n = n2
+n2 × n = n3
+n3 × n3 = n6
+n6 × n6 = n12
+n12 × n3 = n15
+
+We shall define m(k) to be the minimum number of multiplications to compute nk;
+for example m(15) = 5.
+
+For 1 ≤ k ≤ 200, find ∑ m(k).
+
+=cut
+
+my @combinations = (undef, ['']);
+
+foreach my $n (2 .. 200)
+{
+    print "Reached $n\n";
+    my %sets;
+
+    foreach my $lower (1 .. ($n>>1))
+    {
+        my $upper = $n - $lower;
+        
+        foreach my $l_set (@{$combinations[$lower]})
+        {
+            foreach my $u_set (@{$combinations[$upper]})
+            {
+                my $s = join(",", uniq(sort { $a <=> $b } (split(/,/,$l_set),split(/,/,$u_set), $n)));
+                $sets{$s}++;
+            }
+        }
+    }
+
+    $combinations[$n] = [sort { $a cmp $b } keys(%sets)];
+}
+
+my $sum = 0;
+
+foreach my $n (2 .. 200)
+{
+    $sum += min (map { scalar( my @x = split(/,/, $_)) } @{$combinations[15]});
+}
+print "Sum = $sum\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.