Jesteś przedsiębiorcą kolejowym w XIX-wiecznych Stanach Zjednoczonych, kiedy pociągi stają się popularne, ponieważ są najbardziej wydajnym środkiem transportu dużych ilości materiałów drogą lądową. Krajowe zapotrzebowanie na tory kolejowe ze wschodniego wybrzeża przez niektóre niedawno skolonizowane ziemie na zachodzie.

Aby zaspokoić tę potrzebę, rząd USA zamierza nałożyć podatek na subsydiowanie kolei. Obiecali, że zapłacą pieniądze twojej firmie kolejowej za każdą przejechaną trasę. Ponieważ układanie torów w pagórkowatych i górzystych regionach jest droższe niż układanie torów na płaskich terenach, dostosowują odpowiednio kwotę, którą dają. Oznacza to, że rząd zapłaci

• 5000 USD za milę toru ułożonego na płaskiej ziemi
• 12 500 $ za milę toru położonego na pagórkowatym terenie
• 20 000 $ za milę toru położonego w górach.

Oczywiście ten plan nie odzwierciedla dokładnie, ile faktycznie kosztuje układanie torów.

Zatrudniłeś niektórych kartografów, aby narysowali mapy reliefowe regionów, w których będziesz układał ścieżki do analizy wysokości. Oto jedna taka mapa:

S12321
121234
348E96

Każda cyfra reprezentuje jedną milę kwadratową ziemi. Sjest punktem początkowym, Ejest punktem końcowym. Każda liczba reprezentuje intensywność zmian wysokości w tym regionie.

• Grunty o numerach 1-3 stanowią grunty płaskie.
• Grunty o numerach 4-6 stanowią tereny pagórkowate.
• Teren o numerach 7-9 stanowi pasmo górskie.

Przez lata doświadczeń w budowaniu torów kolejowych oceniłeś, że koszt budowy torów (w dolarach) spełnia tę formułę:

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

Oznacza to, że budowanie na określonych wzniesieniach będzie cię kosztować więcej niż daje rząd, czasem będzie to opłacalne, a czasem po prostu osiągniesz próg rentowności.

Na przykład mila toru na wzniesieniu wynoszącym 3 kosztuje 8 000 USD, ale dostajesz tylko 5000 USD, więc tracisz 3000 USD. Z kolei budowanie mili toru na wzniesieniu 7 kosztuje 14 000 USD, ale dostajesz za to 20 000 USD: zysk 6000 USD!

Oto przykładowa mapa, a także dwie różne możliwe ścieżki.

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

Pierwszy utwór kosztuje 30 000 USD, ale rząd płaci za niego 30 000 USD. Nie zarabiasz na tym utworze.

Z drugiej strony drugi koszt kosztuje 56 500 USD, ale dostajesz za niego 62 500 USD. Zyskujesz 6000 $ z tego utworu.

Twój cel: mając mapę ulgi, znajdź najbardziej opłacalną (a może tylko najtańszą) ścieżkę od początku do końca. Jeśli łączy się wiele ścieżek, każda z nich jest akceptowalnym rozwiązaniem.

Szczegóły programu

Otrzymujesz wprowadzanie tekstu oddzielone prostokątną mapą liczb oraz jednym punktem początkowym i końcowym. Każda liczba będzie liczbą całkowitą włącznie z przedziału od 1 do 9. Poza tym dane wejściowe mogą być podawane w dowolny sposób, w granicach rozsądku.

Dane wyjściowe powinny być w tym samym formacie co dane wejściowe, a liczby, w których utworzono ścieżkę, zastąpiono hash ( #). Z powodu arbitralnych przepisów narzuconych przez niektórych kapryśnych polityków tory mogą iść tylko poziomymi lub pionowymi ścieżkami. Innymi słowy, nie można cofać się ani iść po przekątnej.

Program powinien być w stanie rozwiązać w rozsądnym czasie (tj. <10 minut) dla map do 6 wierszy i 6 kolumn.

Jest to wyzwanie polegające na kodzie golfowym , więc wygrywa najkrótszy program.

Mam przykładową (nie golfową) implementację .

Próbki we / wy

S12321
121234
348E96

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



S73891
121234
348453
231654
97856E

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

Python, 307 znaków

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,

Ppodąża częściową ścieżką pi zwraca wszystkie sposoby jej rozszerzenia, aby osiągnąć E. Każda zwrócona ścieżka jest łączona z wynikiem, dzięki czemu maxmożna znaleźć najlepszą.

Zajmuje około 80 sekund na mapie 6x6.

Python: 529 482 460 bajtów

Moje rozwiązanie nie wygra żadnych nagród. Ponieważ jednak opublikowano tylko dwa rozwiązania, a problem był dla mnie interesujący, i tak zdecydowałem się opublikować swoją odpowiedź.

Edycja: Podziękowania dla Howarda za jego rekomendacje. Udało mi się ogolić dużo mojego wyniku!

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]

Ruby, 233 znaków

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]

Podejście brutalnej siły Ruby, które działa dobrze wewnątrz ograniczeń czasowych na planszy 6x6. Dane wejściowe należy podać na STDIN.

Przykłady:

S12321
121234
348E96

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

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