Buduj tory kolejowe i oszukuj rząd

30

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
Peter Olson
źródło
Co jest, jeśli wynik jest niejednoznaczny?
FUZxxl,
2
Wynik może być niejednoznaczny, ale dwuznaczny w taki sposób, że zysk jest taki sam, niezależnie od tego, jak go wyśledzisz.
Peter Olson,
Myślę, że jest mały błąd. Czy 4w 134przykładowej mapie powinna być 6?
JiminP,
@JiminP Tak, to był błąd związany ze zmianą liczb w jednym miejscu, ale nie w drugim. Należy to teraz naprawić.
Peter Olson,
3
Trzy lata później rząd rozgląda się i zaczyna zastanawiać, dlaczego wszystkie * wzgórza i góry są pokryte torami kolejowymi. Ale hej, użytkownicy lokalnego transportu publicznego mieli fajną przejażdżkę kolejką górską / wycieczkę --- za darmo --- finansowaną przez rząd, dzięki czemu ludzie są szczęśliwsi, więc po co się przejmować? (* z wyjątkiem niektórych wzgórz klasy 6)
John Dvorak

Odpowiedzi:

5

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.

Keith Randall
źródło
1
Drugi poziom wcięć możesz zastąpić tabulatorami, aby zapisać 3 znaki
gnibbler
4

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]
sadakatsu
źródło
Tak to się zaczyna. :)
Jonathan Van Matre
1
Kilka drobnych ulepszeń: Pi Msą one używane tylko raz, więc dobrym pomysłem jest wstawienie ich w to miejsce (w przypadku pojedynczego wywołania działa czasami prawie we wszystkich przypadkach dla dwóch). m[c]!='S'można skrócić m[c]<'S', również abs(z)==1do, abs(z)<2a nawet -2<z<2.
Howard
Twoje „drobne poprawki” oszczędzają mi 47 bajtów. Edytuję swoją odpowiedź.
sadakatsu
3

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
Howard
źródło
@PeterOlson Starałem się poświęcić choć trochę uwagi Twojemu wyzwaniu ;-)
Howard