Finding maximum paths

Question

Given a square of positive, natural numbers write a program find a horizontal and a vertical path with the sum of numbers along them being maximal. A horizontal path goes from the first column to the last and has to increase its column position by one in each step. A vertical path goes from the first row to the last and has to increase its row position by one in each step. Furthermore the row position in a horizontal path may stay the same or change by one in either direction, likewise for vertical paths.

To illustrate, the following could be a valid path:

The following path would be invalid, since it steps backwards (and remains on the same row in some places):

The following path would be equally invalid, since it changes the row position by more than one in a single step:

Note: The solution should run in an acceptable amount of time.

Input

n lines of input with n space-separated positive integers each are given on standard input. 2 ≤ n ≤ 40. Every line is terminated by a line break. The numbers are small enough that the maximum sum fits in a 32-bit signed integer.

Output

The maximum sums of the horizontal and vertical paths (in that order) separated by a single space.

Sample input 1

1 2
1 2

Sample output 1

3 4

Sample input 2

1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 3 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
2 1 4 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 4 1 3 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 4 1 2 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 5 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

Sample output 2

37 35

Sample input 3

683 671 420 311 800 936
815 816 123 142 19 831
715 588 622 491 95 166
885 126 262 900 393 898
701 618 956 865 199 537
226 116 313 822 661 214

Sample output 3

4650 4799

---

For your convenience we have prepared a few test cases in bash (thanks to Ventero) and PowerShell which you can run your program through. Invocation is: <test> <command line>, so something like ./test python paths.py or ./test.ps1 paths.exe. Have fun :-)

Answer 1

GolfScript - 49 Nabb enhanced characters

51 characters
50 strictly and utterly necessary characters + 3 slackers that only did the job of 1
56 mostly redundant characters

n%{~]}%.zip{{0@+\{\.1>\3<$-1=@+}%\;}*$-1=\}2*' '@

51 solution:

n%{~]}%.zip{(\{0@+\{\.1>\3<$-1=@+}%\}%;$-1=\}2*' '@

53 solution:

n/{~]}%);.zip{(\{0@+\{\.1>\3<$-1=@+}%\}%;$-1=\}2*' '@
             a8_b9___c10___11______12 13      14_

The method works on two lines at a time, one containing the maximum sums reached at each point, and one containing the next line.

a/14: Repeat twice, once for each result.
8: Take the first line from the input and switch it behind the input array, this in now the first set of maximum sums.
b/13: Iterate over each remaining line in the array.
9: Put 0 at the beginning of the maximum sums.
c/12: Iterate over each element of the line.
10: Make a copy of the maximum sums with the first element removed.
11: Take the first 3 elements of the maximum sums, sort them and add the largest to the current element of the line.

56 solution:

n/{~]}%);.zip{1,99*\{{\.1>\3<$-1=@+}%0\+\}%;$-1=\}2*' '@
1________2___ 3____ 4______________________5_____ 6_7___

1: From input to array of arrays in 9 characters, actually it could have been done with just 1, but I broke that key so this will have to do.
2: 4 characters just to make a transposed copy.
3: Array of 99 0s in 5 characters, it could probably be done in a way smarter fashion, but I smoke too much weed to figure how.
4: Overly complicated double loop that iterate over every single element of the input and does some fuzzy logic or something like that to produce the result. Nabb will probably make something equivalent in around 3½ characters.
5: By now the result is there, inside an array that is, this silly piece of code is just there to get it out (and junk a piece of leftovers (and switch the result into place)).
6: This is a command so simple that its character count would probably be negative in an optimal solution. 7: At this point the program is really done, but due to sloppiness in the preceding code the output is in the wrong order and lacks a space, so here goes a few more bits down the drain.

Answer 2

Haskell: 314 necessary characters

import Data.Vector(fromList,generate,(!))
import List
l=fromList
x=maximum
g=generate
p a=show$x[m!i!0|i<-[0..h-1]]where{
w=length$head a;h=length$a;n=l$map l a;
m=g h$ \i->g w$ \j->n!i!j+x[k#(j+1)|k<-[i-1..i+1]];
i#j|i<0||i>=h||j>=w=0|1>0=m!i!j;}
q a=p a++' ':(p.transpose)a
main=interact$q.map(map read.words).lines

Note: this requires the module Data.Vector. I'm not sure if it's included in the Haskell platform or not.

Ungolfed version:

import Data.Vector(fromList,generate,(!))
import Data.List

-- horizontal; we use transpose for the vertical case
max_path :: [[Integer]] -> Integer
max_path numbers = maximum [m ! i ! 0 | i <- [0..h-1]] where
    w = length (head numbers)
    h = length numbers
    n = fromList $ map fromList numbers
    m = generate h $ \i -> generate w $ \j ->
        n ! i ! j + maximum [f i' (j+1) | i' <- [i-1..i+1]]
    f i j | i < 0 || i >= h || j >= w = 0
    f i j = m ! i ! j

max_paths :: [[Integer]] -> String
max_paths numbers = (show . max_path) numbers ++ " " ++
                    (show . max_path . transpose) numbers

main = interact $ max_paths . map (map read . words) . lines

This solution uses laziness, in tandem with Data.Vector, for memoization. For every point, the solution for the maximum path from it to the end is computed, then stored in the cell of Vector m and reused when needed.

Answer 3

J, 91 95

a=:".;._2(1!:1)3
c=:4 :'>./x+"1|:y,.(1|.!.0 y),._1|.!.0 y'
p=:[:>./c/
(":(p|:a),p a)1!:2(4)

I decline to do IO, lowering my score dramatically. Passes all tests in the test harness (though it only works if the input ends with a line ending, as in the test harness).

I removed the handling for Windows line endings, since Chris suggested that it wasn't necessary. The multi-platform version would have a=:".;._2 toJ(1!:1)3 as the first line.

Explanation:

• f gives the solution pair by calling p normally and with input transposed (|:).
• p takes the maximum (>./) of the row-totals from applying c between each row (c/)
• c takes two rows (x and y). It adds x to each of y, y shifted up 1 cell (1|.!.0 y), and y shifted down 1 cell (_1|.!.0 y). Then it takes the maximums of the three alternatives for each row. (>./). The rest is rank [sic] - I'm not sure if I'm doing it right.

Answer 4

Ruby 1.9, 155 characters

f=->t{(1...l=t.size).map{|a|l.times{|b|t[a][b]+=t[a-1][(b>0?b-1:0)..b+1].max}};t[-1].max};q=[*$<].map{|a|a.split.map &:to_i};puts [f[q.transpose],f[q]]*" ""

Straightforward solution that passes all testcases.

Answer 5

Haskell, 154 characters

import List
z=zipWith
f=show.maximum.foldl1(\a->z(+)$z max(tail a++[0])$z max(0:a)a)
q a=f(transpose a)++' ':f a
main=interact$q.map(map read.words).lines

---

• Edit: (155 -> 154) inlined the function folded over

Answer 6

J, ^109+10= 119 chars

y=:0".(1!:1)3
N=:%:#y
y=:y$~N,N
r=:(((1&{)(+(3>./\0,0,~]))(0&{)),2&}.)^:(<:N)
(":([:>./"1([:r|:),r)y)(1!:2)4

Run with tr:

cat << EOF | tr \\n ' ' | ./maxpath.ijs

As usual in J, most of the code is for input/output. The "actual" code is 65 characters:

r=:(((1&{)(+(3>./\0,0,~]))(0&{)),2&}.)^:(<:#y)
([:>./"1([:r|:),r)y

Passes all test cases

Answer 7

Python, 204 characters

import sys
I=sys.stdin.read()
n=I.count('\n')
A=map(int,I.split())
R=range(n)
X=lambda h,a:[a[i]+max(([0]+h)[i:i+3])for i in R]
h=v=[0]*n
for i in R:h=X(h,A[i*n:i*n+n]);v=X(v,A[i::n])
print max(v),max(h)

Answer 8

Python, 149

import sys
def f(g,t=[]):
 for r in g:t=[int(e)+max(t[i-1:i+2]+[0])for i,e in enumerate(r)]
 print max(t),
g=map(str.split,sys.stdin)
f(zip(*g)),f(g)

If I were to calculate only a vertical or horizontal shortest path,
it could be done in-place instead, saving about a third of the bytes.