30
\$\begingroup\$

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
\$\endgroup\$
  • \$\begingroup\$ What is, if the output is ambiguous? \$\endgroup\$ – FUZxxl Nov 15 '11 at 19:27
  • 2
    \$\begingroup\$ The output can be ambiguous, but ambiguous in a way where the profit is the same regardless of how you trace it. \$\endgroup\$ – Peter Olson Nov 15 '11 at 19:44
  • \$\begingroup\$ I think there's small mistake. Should 4 in 134 in the example map be 6? \$\endgroup\$ – JiminP Nov 18 '11 at 23:42
  • \$\begingroup\$ @JiminP Yes, that was a mistake from changing numbers in one place but not another. It should be fixed now. \$\endgroup\$ – Peter Olson Nov 19 '11 at 0:22
  • 3
    \$\begingroup\$ Three years later, the government looks around and starts wondering why are all* the hills and mountains covered in railroad tracks. But hey, the local transit users got a nice roller coaster / tour ride ---for free--- funded by the goverment, making the people happier, so why care? (* except for some grade-6 hills) \$\endgroup\$ – John Dvorak Mar 11 '14 at 15:18
5
\$\begingroup\$

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.

\$\endgroup\$
  • 1
    \$\begingroup\$ You can replace the second level of indents with tabs to save 3 chars \$\endgroup\$ – gnibbler Nov 24 '11 at 21:03
4
\$\begingroup\$

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]
\$\endgroup\$
  • \$\begingroup\$ That's how it starts. :) \$\endgroup\$ – Jonathan Van Matre Mar 17 '14 at 22:13
  • 1
    \$\begingroup\$ Some minor improvements: P and M are only used once each so it is a good idea to inline then (for a single invocation it works in almost all cases for two sometimes). m[c]!='S' can be shortened to m[c]<'S', also abs(z)==1 to abs(z)<2 or even -2<z<2. \$\endgroup\$ – Howard Mar 18 '14 at 7:55
  • \$\begingroup\$ Your "minor improvements" save me 47 bytes. I'm editing my answer. \$\endgroup\$ – sadakatsu Mar 18 '14 at 15:01
3
+50
\$\begingroup\$

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
\$\endgroup\$
  • \$\begingroup\$ @PeterOlson I tried to give at least a little bit of attention to your challenge ;-) \$\endgroup\$ – Howard Mar 17 '14 at 15:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.