Year 2015

[aoc.git] / 2015 / 47.pl

diff --git a/2015/47.pl b/2015/47.pl
new file mode 100755 (executable)
index 0000000..c00d3d7
--- /dev/null
+++ b/2015/47.pl
@@ -0,0 +1,44 @@
+#!/usr/bin/perl -w
+
+use v5.16;
+use strict;
+
+use List::Util qw(sum);
+chomp (my @packs = reverse <>);
+# my @packs = reverse(1 .. 5, 7 .. 11);
+my $size = sum @packs;
+$size /= 3;
+say "expect $size";
+
+my $min = @packs;
+my $minqe;
+
+sub divide {
+       my ($s1, $s2, $l1, $qe, @rest) = @_;
+       if ($s2 == $size) {
+               say "$s1 $s2 $l1 $qe";
+               if ($l1 < $min) {
+                       $min = $l1;
+                       $minqe = $qe;
+                       say "min=$min, minqe=$qe";
+               } elsif ($l1 == $min && (!$minqe || $qe < $minqe)) {
+                       $minqe = $qe;
+                       say "minqe=$qe";
+               }
+               return;
+       }
+       for my $i (0 .. $#rest) {
+               my @nr = @rest;
+               my $n = splice (@nr, $i, 1);
+               if ($s1 < $size && $s1 + $n <= $size && $l1+1 <= $min) {
+                       divide($s1+$n, 0, $l1+1, $qe*$n, @nr);
+               } elsif ($s1 == $size && $s2 < $size && $s2 + $n <= $size
+                       && ($l1 < $min || ($l1 == $min && $qe < $minqe))) {
+                       # say "l2 $s1, $s2+$n, $l1, $qe";
+                       divide($s1, $s2+$n, $l1, $qe, @nr);
+               } 
+       }
+}
+
+divide(0, 0, 0, 1, @packs);
+say $minqe;