Baue Eisenbahnschienen und betrüge die Regierung

30

Sie sind ein Eisenbahnunternehmer in den USA des 19. Jahrhunderts, als Züge populär wurden, weil sie das effizienteste Mittel für den Transport großer Materialmengen auf dem Landweg sind. Es besteht ein nationaler Bedarf an Eisenbahnschienen von der Ostküste durch einige kürzlich kolonisierte Gebiete im Westen.

Um diesem Bedürfnis gerecht zu werden, wird die US-Regierung eine Steuer erheben, um Eisenbahnen zu subventionieren. Sie haben versprochen, für jede Meile Gleis Geld an Ihre Eisenbahngesellschaft zu zahlen. Da das Verlegen von Wegen in hügeligen und bergigen Regionen teurer ist als das Verlegen von Wegen in flachen Gebieten, passen sie die Menge an, die sie geben, entsprechend an. Das heißt, die Regierung zahlt

  • 5.000 US-Dollar pro Meile im Flachland verlegte Strecke
  • 12.500 USD pro Meile im Hügelland verlegter Strecke
  • 20.000 US-Dollar pro Meile in den Bergen verlegter Strecke.

Natürlich spiegelt dieser Plan nicht genau wider, wie viel es tatsächlich kostet, Gleise zu verlegen.

Sie haben einige Kartografen beauftragt, Reliefkarten der Regionen zu zeichnen, in denen Sie die Höhenlage analysieren möchten. Hier ist eine solche Karte:

S12321
121234
348E96

Jede Ziffer steht für eine Quadratmeile Land. Sist der Startpunkt, Eist der Endpunkt. Jede Zahl repräsentiert die Intensität der Höhenänderungen in dieser Region.

  • Das Land mit den Nummern 1-3 ist eben.
  • Das Land mit den Nummern 4-6 ist hügelig.
  • Das Land mit der Nummer 7-9 bildet eine Bergkette.

Sie haben durch jahrelange Erfahrung im Bau von Eisenbahnschienen festgestellt, dass die Kosten für den Gleisbau (in US-Dollar) diese Formel erfüllen:

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

Das bedeutet, dass das Bauen auf bestimmten Höhenunterschieden mehr Geld kostet, als die Regierung angibt, manchmal rentabel ist und manchmal nur die Gewinnschwelle überschreitet.

Zum Beispiel kostet eine Meile Strecke auf einem Höhenunterschied von 3 $ 8.000 für den Bau, aber man bekommt nur $ 5.000 dafür bezahlt, so dass man $ 3.000 verliert. Im Gegensatz dazu kostet es 14.000 US-Dollar, eine Meile auf einem Höhenunterschied von 7 zu bauen, aber dafür werden 20.000 US-Dollar bezahlt: 6.000 US-Dollar Gewinn!

Hier ist eine Beispielkarte sowie zwei verschiedene mögliche Pfade.

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

Der Bau der ersten Strecke kostet 30.000 US-Dollar, aber die Regierung zahlt 30.000 US-Dollar dafür. Sie machen keinen Gewinn aus dieser Spur.

Andererseits kostet der Bau des zweiten Modells 56.500 US-Dollar, aber dafür werden 62.500 US-Dollar bezahlt. Sie profitieren von diesem Track $ 6.000.

Ihr Ziel: Finden Sie anhand einer Reliefkarte den profitabelsten (oder vielleicht auch nur den kostengünstigsten) Weg vom Anfang bis zum Ende. Wenn mehrere Pfade gleich sind, ist einer von ihnen eine akzeptable Lösung.

Programmdetails

Sie erhalten eine Texteingabe, die durch eine rechteckige Karte mit Zahlen und einem Start- und Endpunkt getrennt ist. Jede Zahl wird eine ganze Zahl sein, die zwischen 1 und 9 liegt. Ansonsten kann die Eingabe innerhalb des vorgegebenen Rahmens nach Belieben erfolgen.

Die Ausgabe sollte dasselbe Format haben wie die Eingabe, wobei die Nummern, für die die Spur erstellt wurde, durch ein Hash ( #) ersetzt werden sollten. Wegen willkürlicher Vorschriften einiger launischer Politiker können die Wege nur horizontal oder vertikal verlaufen. Mit anderen Worten, Sie können nicht rückwärts oder diagonal fahren.

Das Programm sollte in der Lage sein, in angemessener Zeit (dh <10 Minuten) Karten mit bis zu 6 Zeilen und 6 Spalten zu lösen.

Dies ist eine Code-Golf- Herausforderung, bei der das kürzeste Programm gewinnt.

Ich habe eine Beispielimplementierung (ohne Golf) .

Beispiel-E / A

S12321
121234
348E96

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



S73891
121234
348453
231654
97856E

S#3###
1###3#
3#####
######
#####E
Peter Olson
quelle
Was ist, wenn die Ausgabe mehrdeutig ist?
FUZxxl
2
Die Ausgabe kann mehrdeutig sein, jedoch in einer Weise, bei der der Gewinn unabhängig von der Art und Weise, in der Sie ihn verfolgen, gleich ist.
Peter Olson
Ich denke, es gibt einen kleinen Fehler. Sollte das 4in 134der Beispielkarte sein 6?
18.
@JiminP Ja, das war ein Fehler beim Ändern der Nummern an einer Stelle, aber nicht an einer anderen. Es sollte jetzt behoben sein.
Peter Olson
3
Drei Jahre später schaut sich die Regierung um und fragt sich, warum all die Hügel und Berge mit Eisenbahnschienen bedeckt sind. Aber hey, die lokalen Transitbenutzer haben eine schöne Achterbahn- / Tourenfahrt bekommen - kostenlos - finanziert von der Regierung, was die Menschen glücklicher macht. Warum also? (* mit Ausnahme einiger Steigungen der 6. Klasse)
John Dvorak

Antworten:

5

Python, 307 Zeichen

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,

PNimmt einen Teilpfad pund gibt alle Möglichkeiten zurück, ihn zu erweitern, um ihn zu erreichen E. Jeder zurückgegebene Pfad wird mit seiner Punktzahl gepaart, maxum den besten zu finden.

Auf einer 6x6-Karte dauert es ungefähr 80 Sekunden.

Keith Randall
quelle
1
Sie können die zweite Ebene der Einrückungen durch Tabulatoren ersetzen, um 3 Zeichen zu sparen
Gnibbler
4

Python: 529 482 460 Bytes

Meine Lösung wird keine Preise gewinnen. Da jedoch nur zwei Lösungen veröffentlicht wurden und ich das Problem interessant fand, habe ich beschlossen, meine Antwort trotzdem zu veröffentlichen.

Edit: Danke an Howard für seine Empfehlungen. Ich habe es geschafft, viel von meiner Punktzahl zu rasieren!

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
quelle
So fängt es an. :)
Jonathan Van Matre
1
Einige kleinere Verbesserungen: Pund Mwerden jeweils nur einmal verwendet, daher ist es eine gute Idee, sie inline zu setzen (bei einem einzelnen Aufruf funktioniert dies manchmal in fast allen Fällen für zwei). m[c]!='S'kann zu m[c]<'S', auch abs(z)==1zu abs(z)<2oder sogar gekürzt werden -2<z<2.
Howard
Ihre "kleinen Verbesserungen" sparen mir 47 Bytes. Ich bearbeite meine Antwort.
Sadakatsu
3

Ruby, 233 Zeichen

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]

Ein Ruby-Brute-Force-Ansatz, der innerhalb der Zeitbeschränkungen eines 6x6-Boards funktioniert. Die Eingabe muss auf STDIN erfolgen.

Beispiele:

S12321
121234
348E96

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

S#####
1212##
#####3
#3####
#####E
Howard
quelle
@ PeterOlson Ich habe versucht, Ihrer Herausforderung zumindest ein wenig Aufmerksamkeit zu schenken ;-)
Howard