Build railroad tracks and cheat the government

Question

You are a railroad entrepreneur in the 19th-century United States when trains become popular because they are the most efficient means of transporting large volumes of materials by land. There is a national need for railroad tracks from the east coast through some recently colonized lands in the west.

To accommodate this need, the U.S. government is going to levy a tax to subsidize railroads. They have promised to pay money to your railroad company for each mile of track laid. Since laying tracks in hilly and mountainous regions is more expensive than laying tracks in flat land, they adjust the amount they give accordingly. That is, the government will pay

• $5,000 per mile of track laid in flat land
• $12,500 per mile of track laid in hilly land
• $20,000 per mile of track laid in mountains.

Of course, this plan does not accurately reflect how much it actually costs to lay tracks.

You have hired some cartographers to draw relief maps of the regions where you will be laying track to analyze the elevation. Here is one such map:

S12321
121234
348E96

Each digit represents one square mile of land. S is the starting point, E is the ending point. Each number represents the intensity of the elevation changes in that region.

• Land numbered 1-3 constitutes flat land.
• Land numbered 4-6 constitutes hilly land.
• Land numbered 7-9 constitutes a mountain range.

You have, through years of experience building railroad tracks, assessed that the cost of track building (in dollars) satisfies this formula:

Cost_Per_Mile = 5000 + (1500 * (Elevation_Rating - 1))

That means building on certain elevation gradients will cost you more money than the government gives, sometimes it will be profitable, and sometimes you will just break even.

For example, a mile of track on an elevation gradient of 3 costs $8,000 to build, but you only get paid $5,000 for it, so you lose $3000. In contrast, building a mile of track on an elevation gradient of 7 costs $14,000, but you get paid $20,000 for it: a $6,000 profit!

Here is an example map, as well as two different possible paths.

S29    S#9    S##
134    1#4    1##
28E    2#E    2#E

The first track costs $30,000 dollars to construct, but the government pays you $30,000 for it. You make no profit from this track.

On the other hand, the second costs $56,500 to build, but you get paid $62,500 for it. You profit $6,000 from this track.

Your goal: given a relief map, find the most profitable (or perhaps merely the least expensive) path from the start to the end. If multiple paths tie, any one of them is an acceptable solution.

Program Details

You are given text input separated with a rectangular map of numbers and one start and end point. Each number will be an integer inclusively between 1 and 9. Other than that, the input may be provided however you like, within reason.

The output should be in the same format as the input, with the numbers where track has been built replaced by a hash (#). Because of arbitrary regulations imposed by some capricious politicians, tracks can only go in horizontal or vertical paths. In other words, you can't backtrack or go diagonally.

The program should be able to solve in a reasonable amount of time (i.e. <10 minutes) for maps up to 6 rows and 6 columns.

This is a code golf challenge, so the shortest program wins.

I have an example (non-golfed) implementation.

Sample I/O

S12321
121234
348E96

S12321
######
3##E##



S73891
121234
348453
231654
97856E

S#3###
1###3#
3#####
######
#####E

Answer 1

Python, 307 chars

import os
I=os.read(0,99)
n=I.find('\n')+1
I='\0'*n+I+'\0'*n
def P(p):
 S=[]
 for d in(-n,-1,1,n):
  y=p[-1]+d
  if'E'==I[y]:S+=[(sum((int(I[v])-1)/3*75-15*int(I[v])+15for v in p[1:]),p)]
  if'0'<I[y]<':'and y not in p:S+=P(p+[y])
 return S
for i in max(P([I.find('S')]))[1][1:]:I=I[:i]+'#'+I[i+1:]
print I,

P takes a partial path p and returns all ways of extending it to reach E. Each returned path is paired with its score so max can find the best one.

Takes about 80 seconds on a 6x6 map.

Answer 2

Python: 529 482 460 bytes

My solution will not win any prizes. However, since there are only two solutions posted and I found the problem interesting, I decided to post my answer anyway.

Edit: Thanks to Howard for his recommendations. I've managed to shave a lot of my score!

import sys
N=len
def S(m,c,p=0):
 if m[c]=='E':return m,p
 if m[c]<'S':
    b=list(m);b[c]='#';m=''.join(b)
 b=[],-float('inf')
 for z in(1,-1,w,-w):
    n=c+z
    if 0<=n<N(m)and m[n]not in('S','#')and(-2<z<2)^(n/w!=c/w):
     r=S(m,n,p+(0if m[n]=='E'else(int(m[n])-1)/3*5-int(m[n])+1))
     if b[1]<r[1]:b=r
 return b
m=''
while 1:
 l=sys.stdin.readline().strip()
 if l=='':break
 w=N(l);m+=l
b,_=S(m,m.index('S'))
for i in range(0,N(b),w):print b[i:i+w]

Answer 3

Ruby, 233 characters

R=->s{o=s=~/S/m
s=~/E/m?(q=[-1,1,-N,N].map{|t|s[f=o+t]>'0'?(n=s*1
n[o]='#'
n[f]='S'
a=R[n]
a&&[a[0]-(e=s[f].to_i-1)/3*5+e,a[1]]):nil}-[nil]
q.sort!&&q[0]):[0,(n=s*1;n[o]='E'
n[$_=~/S/m]='S'
n)]}
N=1+(gets(nil)=~/$/)
$><<R[$_+$/*N][1]

A Ruby brute-force approach which runs well inside the time constraints on a 6x6 board. The input must be given on STDIN.

Examples:

S12321
121234
348E96

S#2321
1#####
3##E##    
--    
S73891
121234
348453
231654
97856E

S#####
1212##
#####3
#3####
#####E