summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorJesse Luehrs <doy@tozt.net>2009-05-14 21:30:56 -0500
committerJesse Luehrs <doy@tozt.net>2009-05-14 21:30:56 -0500
commitf37c40b2ea0471760c12f04951f5f8ee54af6bc7 (patch)
tree5a88a865fc37592a990d0ad3044133dd5813c456
parent3f2a0002b811a7c4cf27ec111bbf08395404ef5f (diff)
downloadprojecteuler-f37c40b2ea0471760c12f04951f5f8ee54af6bc7.tar.gz
projecteuler-f37c40b2ea0471760c12f04951f5f8ee54af6bc7.zip
solution to number 18
-rwxr-xr-x018.pl44
1 files changed, 44 insertions, 0 deletions
diff --git a/018.pl b/018.pl
new file mode 100755
index 0000000..6a9ec1c
--- /dev/null
+++ b/018.pl
@@ -0,0 +1,44 @@
+#!/usr/bin/perl
+use strict;
+use warnings;
+# http://tozt.net/code/Graph-Implicit/
+use Graph::Implicit;
+use List::Util qw/sum max/;
+
+my $triangle_txt = <<'TRIANGLE';
+ 75
+ 95 64
+ 17 47 82
+ 18 35 87 10
+ 20 04 82 47 65
+ 19 01 23 75 03 34
+ 88 02 77 73 07 63 67
+ 99 65 04 28 06 16 70 92
+ 41 41 26 56 83 40 80 70 33
+ 41 48 72 33 47 32 37 16 94 29
+ 53 71 44 65 25 43 91 52 97 51 14
+ 70 11 33 28 77 73 17 78 39 68 17 57
+ 91 71 52 38 17 14 91 43 58 50 27 29 48
+ 63 66 04 68 89 53 67 30 73 16 69 87 40 31
+04 62 98 27 23 09 70 98 73 93 38 53 60 04 23
+TRIANGLE
+my @triangle_lines = split /\n/, $triangle_txt;
+my @triangle = map { [split ' ', $_] } @triangle_lines;
+use DDS;
+
+my $graph = Graph::Implicit->new(sub {
+ my ($vx, $vy) = split ' ', shift;
+ return if $vx == @triangle - 1;
+ #print "$vx, $vy -> ", $vx + 1, ", $vy and ", $vx + 1, ", ", $vy + 1, "\n";
+ return ([($vx + 1) . " " . $vy, 100 - $triangle[$vx + 1][$vy]],
+ [($vx + 1) . " " . ($vy + 1), 100 - $triangle[$vx + 1][$vy + 1]]);
+});
+my ($paths, $blah) = $graph->dijkstra("0 0");
+my @paths;
+for my $i (0..14) {
+ push @paths, [Graph::Implicit::make_path($paths, "14 $i")];
+}
+my @path_values = map { [map { my ($x, $y) = split; $triangle[$x][$y] } @$_] }
+ @paths;
+my @path_sums = map { sum @$_ } @path_values;
+print max(@path_sums), "\n";