Skip to content
Find file
Fetching contributors…
Cannot retrieve contributors at this time
145 lines (121 sloc) 4.04 KB
defmodule Tree do
@moduledoc """
Project Euler - Problem 67
By starting at the top of the triangle below and moving to adjacent numbers on the row below, the maximum total from top to bottom is 23.
3
7 4
2 4 6
8 5 9 3
That is, 3 + 7 + 4 + 9 = 23.
Find the maximum total from top to bottom in tree.txt, a 15K text file containing a triangle with one-hundred rows.
"""
def maximal_path([row, comparison_row | rest_rows]) do
row = reduce_row(row, comparison_row)
maximal_path([row | rest_rows])
end
def maximal_path([row]), do: List.first(row)
def from_file(filename) do
File.read!(filename)
|> String.strip
|> String.split("\n")
|> Enum.reverse
|> Enum.map(fn row ->
for num <- String.split(row, " "), do: String.to_integer(num)
end)
|> Enum.map(fn row -> append_index(row) end)
end
def reduce_row(row, comparison_row) do
for {{main, index}, {opt1, index1}, {opt2, index2}} <- pairs(row, comparison_row) do
sum1 = main + opt1
sum2 = main + opt2
if sum1 > sum2 do
{sum1, index ++ index1}
else
{sum2, index ++ index2}
end
end
end
def append_index(row) do
for {num, index} <- Enum.with_index(row) do
{num, [index]}
end
end
def pairs(row, comparison_row) do
for {num, path = [index | _]} <- comparison_row do
{{num, path}, Enum.at(row, index), Enum.at(row, index+1)}
end
end
def pretty_print(filename) do
tree = Tree.from_file(filename)
{sum, path} = Tree.maximal_path(tree)
IO.puts "maximal sum = #{sum}"
size = length(Enum.at(tree, 0))
tree
|> Enum.reverse
|> Enum.with_index
|> Enum.each(fn {row, row_index} ->
if rem(row_index, 2) == 0, do: IO.write(" ")
String.duplicate(" ", div(size - length(row), 2)) |> IO.write
(for {_, [p | _]} <- row do
if p == Enum.at(path, row_index) do
"\e[31mx"
else
"\e[32mo"
end
end)
|> Enum.join(" ")
|> IO.puts
end)
end
end
ExUnit.start
defmodule TreeTest do
use ExUnit.Case
@path Path.expand("support/tree.txt", __DIR__)
test "read file" do
tree = Tree.from_file(@path)
assert length(tree) == 100
assert Enum.at(tree, 99) == [{59, [0]}]
end
test "append index" do
assert Tree.append_index([1, 2, 3]) == [{1, [0]}, {2, [1]}, {3, [2]}]
end
test "pairs" do
row1 = [{2, [0]}, {4, [1]}, {6, [2]}]
row2 = [{8, [0]}, {5, [1]}, {9, [2]}, {3, [3]}]
assert Tree.pairs(row2, row1) == [
{{2, [0]}, {8, [0]}, {5, [1]}},
{{4, [1]}, {5, [1]}, {9, [2]}},
{{6, [2]}, {9, [2]}, {3, [3]}},
]
end
test "reduce row" do
row1 = [{30, [0]}, {11, [1]}, {85, [2]}, {31, [3]}, {34, [4]}, {71, [5]}, {13, [6]}, {48, [7]}, {05, [8]}, {14, [9]}, {44, [10]}, {03, [11]}, {19, [12]}, {67, [13]}, {23, [14]}]
row2 = [{23, [0]}, {33, [1]}, {44, [2]}, {81, [3]}, {80, [4]}, {92, [5]}, {93, [6]}, {75, [7]}, {94, [8]}, {88, [9]}, {23, [10]}, {61, [11]}, {39, [12]}, {76, [13]}, {22, [14]}, {03, [15]}]
assert Tree.reduce_row(row2, row1) == [
{63, [ 0, 1]},
{55, [ 1, 2]},
{166, [ 2, 3]},
{112, [ 3, 3]},
{126, [ 4, 5]},
{164, [ 5, 6]},
{106, [ 6, 6]},
{142, [ 7, 8]},
{99, [ 8, 8]},
{102, [ 9, 9]},
{105, [10, 11]},
{64, [11, 11]},
{95, [12, 13]},
{143, [13, 13]},
{45, [14, 14]},
]
end
test "maximal path" do
tree = Tree.from_file(@path)
{sum, path} = Tree.maximal_path(tree)
assert sum == 7273
assert path == [0, 0, 0, 1, 2, 3, 4, 4, 5, 5, 6, 6, 7, 8, 9, 10, 11, 12, 12, 12, 13, 13, 13, 14, 14, 15, 15, 16, 17, 17, 17, 18, 19, 20, 21, 22, 23, 24, 25, 25, 25, 26, 27, 27, 28, 29, 30, 31, 32, 32, 32, 32, 33, 33, 34, 35, 36, 36, 36, 36, 36, 36, 36, 37, 38, 39, 40, 41, 41, 42, 42, 42, 42, 42, 42, 42, 43, 43, 43, 44, 45, 45, 45, 45, 45, 45, 46, 46, 46, 46, 47, 47, 48, 49, 49, 50, 51, 52, 52, 53]
end
def path, do: @path
end
Tree.pretty_print(TreeTest.path)
Something went wrong with that request. Please try again.