Finding maximum paths

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 :-)

• @Joey: Slightly altered task from one we used last year in our contest :)
– Joey
Mar 21 '11 at 16:18
• +10 for the bash test script! I wish all code golf came with such. Mar 24 '11 at 2:13
• @MtnViewMark: We try :-) Personally I hate tasks that require too much clarification after being posted and I usually write my own test scripts anyway since I need to know when an attempt to golf further introduces a regression. Also I have observed that some people tend to post plainly wrong answers. Test cases help getting everyone on the same line. Having a facility that works for every task instead of just one-off hackjobs for each task would clearly be better, but we're not quite there yet ;-)
– Joey
Mar 24 '11 at 10:20

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.

• Ahh, I just accidently assumed the input not to end with a newline. I'm surprised that it actually worked partially, that kind of stuff usually mess up a GolfScript program completely. Mar 21 '11 at 15:57
• Looks fine, although you should be using {}* instead of (\{}%.
– Nabb
Mar 23 '11 at 8:13
• Yes that makes sense, thanks. Mar 23 '11 at 14:22

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.
• Exactly, lowering your score. -1 Mar 22 '11 at 12:16
• @eBusiness: Are you sure downvoting is the right response to an incomplete solution? Mar 22 '11 at 20:01
• @Joey: Not upvoting is the other option. I was too tired to do IO at the time, but my solution is so different from the other J solution that I really wanted to post it anyhow. If there was an explicit way to mark the answer as "non-participating", or something like that, I would have. Mar 22 '11 at 20:09
• @Joey: Another reason is that down-votes are unlikely to be reversed even if the solution is fixed; the original user has to come back and change their vote. (Deleted, realized that short-circuited the discussion, and undeleted. I guess I'll shoot for the "Disciplined" badge instead.) Mar 22 '11 at 20:27
• @Jesse Millikan: We do that. No guarantees, but if you fix the issue within reasonable time most downvoters should revoke their votes. Mar 22 '11 at 21:25

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. • I guess you can strip the curly braces after your where statement, if you collapse all the definitions into one single line. Mar 21 '11 at 17:59 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.

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 • Will using zipWith3 shorten the code? Aug 24 '14 at 22:54 • I think you could replace maximum with foldl1 max , which adds characters but allows you to factor out foldl1 and max, which should save characters. Aug 24 '14 at 22:58 • maximum.foldl1, max, and max --vs-- f=foldl1;m=max;, f m.f, m, and m. -- or 20 vs. 22. So, no, it doesn't save. Aug 27 '14 at 14:55 • Right. And i just remembered the monomorphism restriction would stop writing m=max. What about zipWith3? Aug 27 '14 at 15:06 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

• So we need JB again with a solution that reduces the parsing to 10 characters? ;-)
– Joey
Mar 21 '11 at 8:52
• @Joey I'm on holiday, I barely have internet access; not much time for golfing ;-)
– J B
Mar 21 '11 at 10:02
• Can you clue me in on how you're directly running maxpath.ijs? Mar 22 '11 at 22:28
• @Jesse: In *nix put some #!/usr/bin/env jconsole on top of the file and set the executable flag. Mar 22 '11 at 22:47

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.

Python, 204 characters

import sys