/
67.lua
55 lines (49 loc) · 1.25 KB
/
67.lua
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
-- result: 7273
-- 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 5
-- 2 4 6
-- 8 5 9 3
--
-- That is, 3 + 7 + 4 + 9 = 23.
--
-- Find the maximum total from top to bottom in triangle.txt (right click and 'Save Link/Target As...'), a 15K text file containing a triangle with one-hundred rows.
function justWords(str)
local t = {}
local function helper(word) table.insert(t, word) return "" end
if not str:gsub("%w+", helper):find"%S" then return t end
end
local tri = {}
local tcost = {}
local maxd = 0
function max(x, y)
if x>y then return x else return y end
end
function tallest(y, x)
if y==maxd then
return tri[y][x]
else
local tc = tcost[y]
if tc == nil then
tc = {}
tcost[y] = tc
end
local tcc = tc[x]
if tcc==nil then
tcc = tri[y][x] + max(tallest(y+1, x), tallest(y+1, x+1))
tc[x] = tcc
-- print(x, y, tcc)
end
return tcc
end
end
local line
local file=io.open("triangle67.txt", "r")
while true do
line = file:read('*line')
if line == nil then break end
maxd = maxd + 1
tri[maxd] = justWords(line)
end
print(tallest(1, 1))