Finding maximum paths

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.


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.


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.

Tags:

Code Golf

Recent Posts