Year 2015

[aoc.git] / 2015 / 18.pl

diff --git a/2015/18.pl b/2015/18.pl
new file mode 100755 (executable)
index 0000000..53f2b48
--- /dev/null
+++ b/2015/18.pl
@@ -0,0 +1,43 @@
+#!/usr/bin/perl -w
+
+use v5.16;
+use strict;
+
+$; = ',';
+
+my %route;
+my %cities;
+while (<>) {
+       my ($src, $dst, $len) = /^(\w+) to (\w+) = (\d+)/;
+       $cities{$src} = $cities{$dst} = 1;
+       $route{$src,$dst} = $len;
+       $route{$dst,$src} = $len;
+}
+
+
+my $max_dist;
+sub do_perm {
+       my ($path, $dist, $rest) = @_;
+       
+       if (!@$rest) {
+               $max_dist = $dist if !$max_dist || $dist > $max_dist;
+               say "new min $max_dist";
+               return;
+       }
+       for my $i (0 .. $#$rest) {
+               my @nrest = @$rest;
+               my ($next) = splice (@nrest, $i, 1);
+               my @npath = (@$path, $next);
+               my $ndist = $dist;
+               if (@$path) {
+                       my $prev = $path->[-1];
+                       $ndist += $route{$prev,$next};
+               }
+               # say join(',', @npath), " $ndist";
+               do_perm(\@npath, $ndist, \@nrest);
+       }
+}
+
+do_perm([], 0, [ keys %cities ]);
+say $max_dist;
+