Maximum triangle path sum: Difference between revisions
Content added Content deleted
m (→{{header|REXX}}: added/changed whitespace and comments, simplified program, changed indentations.) |
m (→{{header|Sidef}}: replaced operator "..." with "..^") |
||
Line 1,686: | Line 1,686: | ||
Iterative solution: |
Iterative solution: |
||
<lang ruby>var sum = [0] |
<lang ruby>var sum = [0] |
||
ARGF.each { |line| |
ARGF.each { |line| |
||
var x = line.words.map{.to_i} |
var x = line.words.map{.to_i} |
||
sum = [ |
sum = [ |
||
x.first + sum.first, |
x.first + sum.first, |
||
1 .. |
1 ..^ x.len-2 -> map{|i| x[i] + [sum[i-1, i]].max}..., |
||
x.last + sum.last, |
x.last + sum.last, |
||
] |
] |
||
} |
} |
||
say sum.max |
say sum.max</lang> |
||
Recursive solution: |
Recursive solution: |
||
<lang ruby>var triangle = ARGF.slurp.lines.map{.words.map{.to_i}} |
<lang ruby>var triangle = ARGF.slurp.lines.map{.words.map{.to_i}} |
||
func max_value(i=0, j=0) is cached { |
func max_value(i=0, j=0) is cached { |
||
i == triangle.len && return 0 |
i == triangle.len && return 0 |
||
triangle[i][j] + [max_value(i+1, j), max_value(i+1, j+1)].max |
triangle[i][j] + [max_value(i+1, j), max_value(i+1, j+1)].max |
||
} |
} |
||
say max_value() |
say max_value()</lang> |
||
{{out}} |
{{out}} |
||
<pre>% sidef maxpath.sf triangle.txt |
<pre>% sidef maxpath.sf triangle.txt |