Matthew löst gerne Rätsel. Wann immer er es schafft, einen zu lösen, springt er glücklich herum. Kürzlich er wirklich braucht , dies zu tun , wie ein Meteorschauer Krater und Löcher im Boden geöffnet hat , in dem ihm wie nicht fallen.
Sie erhalten einen Teil der Landschaft, den Matthew überqueren möchte, und kommen hoffentlich am Ende gesund an. Der Boden wird in Metern angegeben, wobei jeder Meter entweder normaler Boden oder ein Loch ist. Wenn er läuft, schafft er es, einen Meter pro Schritt zu überqueren; Die Alternative ist das Springen, das vier Meter pro Schritt überquert. Matthew beginnt ganz links auf dem ersten Grundmeter und möchte zum letzten gelangen (allerdings nicht darüber hinaus - stellen Sie sich ein endloses Loch jenseits des letzten angegebenen Meters in der Landschaft vor).
Eingang
Die Eingabe erfolgt als einzelne Zeile in der Standardeingabe, die durch einen Zeilenumbruch abgeschlossen wird. Die Linie besteht entweder aus Bindestrichen ( -
) oder Unterstrichen ( _
), die eine Boden- bzw. Lochanzeige darstellen. Eine Beispieleingabe könnte sein:
----__--___---
Die gegebene Landschaft ist mindestens eine und höchstens 30 Meter lang und beginnt immer mit dem Boden.
Ausgabe
Die Ausgabe erfolgt als Standardausgabe und stellt eine Reihe von Bewegungsbefehlen für Matthew dar, entweder run ( R
) oder jump ( J
). Wie oben erwähnt, ein
Lauf verursacht Befehl Matthew einen Meter zu laufen , während Springen ihn nach vorne genau vier Meter trägt. Für das obige Beispiel ist folgende Bewegung möglich:
RRJRJRR
was ungefähr so aussieht:
Wenn es keinen sicheren Weg durch die Landschaft gibt, sollte ein einzelnes Ausrufezeichen ( !
) gedruckt werden.
Beispieleingaben
--------
----__--___---
-_______
-_-_-_-_-_-
-
Beispielausgaben
JRRR
RRJRJRR
!
!
(Die letzte Ausgabe ist leer, da keine Bewegung erforderlich ist, aber ich denke, Markdown kann dies nicht analysieren.)
Hinweis
Es ist nur ein einziger möglicher Pfad erforderlich, sodass die Programmausgabe nicht genau mit den Beispielausgaben übereinstimmen muss. Solange eine Lösung vorliegt und jeder Bewegungsbefehl auf den Boden fährt und der letzte Zähler irgendwann erreicht ist, ist die Ausgabe gültig.
Zusätzliche Ausgabe bei Standardfehler wird ignoriert.
Gewinnbedingung
Der kürzeste Code gewinnt, wie es im Golf üblich ist. Bei einem Gleichstand gewinnt die frühere Lösung.
Testfälle
Es gibt zwei Testskripte mit identischen Testfällen:
- bash (Danke an Ventero )
- Power Shell
Der Aufruf erfolgt in beiden Fällen: <test script> <my program> [arguments]
zB ./test ruby jumprun.rb
oder ./test.ps1 ./jumprun.exe
.
Noch ein Hinweis
Diese Aufgabe war Teil eines Golfwettbewerbs an meiner Universität im Zeitraum 2011-24. Die Partituren und Sprachen unserer Teilnehmer waren wie folgt:
- 104 - Haskell
- 131 - Haskell
- 154 - C
- 170 - C
- 275 - VB.NET
- 286 - Gemeines Lisp
Unsere eigenen Lösungen waren
- 92 - Rubin
- 124 - PowerShell
quelle
./test.sh perl jump.pl
-./test.sh: line 42: syntax error near unexpected token 'done'
, under bash 3.2.48Antworten:
Perl, 53 Zeichen
Führen Sie dies mit
perl -p jumpnrun.pl
. Ich habe 3 Zeichen für die-p
Option gezählt, das ist der Längenunterschied zwischenperl jumpnrun.pl
undperl -p jumpnrun.pl
.Ich spreche nicht so fließend Perl, daher bin ich mir ziemlich sicher, dass dies weiter verkürzt werden kann. Hierbei wird ein regulärer Ausdruck verwendet, der Howards Lösung ähnelt .
quelle
Ruby,
93907970 ZeichenIch dachte, eine Regex-Lösung wäre ziemlich gut und kompakt (lassen Sie den Matcher die Arbeit erledigen). Leider haben all die Randfälle und Spezialbehandlungen dies so lange gemacht - zumindest habe ich die 100 nicht angefasst ;-).
Es übergibt alle Testfälle des bereitgestellten Skripts.
Mehrere Zeichen im Vergleich zum vorherigen Skript gespeichert (jetzt
gsub
genügt ein einziger Aufruf von ).Bearbeiten 1: Wurde geändert
puts z!=?-??!:''
,z!=?-&&$><<?!
nachdem das Testskript für Testfall 1 keine Ausgabe zugelassen hat.Edit 2: Die Vorgängerversion war
Meine ursprüngliche Idee war es, die Zeichen durch eine Look-Behind- und Look-Ahead-Strategie zu ersetzen: Das Muster war
^(?<=[RJ]*)(-|-...)(?=(-|-...)*-$)
und ich würde dann '-' durch 'R' und ansonsten durch 'J' ersetzen. Leider erlaubt Ruby keine Vorschau mit variabler Länge und eine andere Erfassungsgruppe für den ersten Teil hat den Code noch länger gemacht.Also habe ich den iterativen Ansatz gewählt: Wenn ich mit einem Schritt oder einem Sprung beginnen kann,
^(-|-...)
gefolgt von einer Reihe anderer Schritte oder Sprünge bis zur letzten Plattform,(-|-...)*-$
dann drucke ich den entsprechenden Buchstaben aus, entferne die ersten vier Zeichen und beginne von vorne. On kann sogar die Priorität zwischen RJ und JR einstellen, indem die Auswahlmöglichkeiten innerhalb des Ausdrucks umgeschaltet werden (derzeit bevorzugt RJ).Edit 3: Aufteilen der einzelnen Substitution
in zwei
gab noch ein paar Zeichen. Endlich habe ich es geschafft, dieses End-of-Line-Problem zu beseitigen, aber das kostet mich: Die Fehlererkennung kostet ein paar Zeichen mehr.
quelle
z!=?-&&$><<?!
. Ansonsten tolle Lösung, +1!Perl -
7160Nun bestehen alle Testfälle. :) Es stellte sich heraus, dass ich das letzte Zeichen zu früh entfernt habe ... und die Hälfte meines ursprünglichen regulären Ausdrucks war völlig überflüssig.
$ _ = $ ARGV [0]; y / - / R /; s / (R ... (? = R)) (R * (? = R)) / J $ 2 / g; hacken; drucken / /? "!": $ , $ /Noch eine andere Regex-Lösung besteht die 5 Testfälle in der Post.
Könnte verkürzt werden, indem man als Einzeiler mit-E
undsay
statt läuftprint
, aber dann versucht Perl, die Eingabe als Schalter zu interpretieren ... (Unrecognized switch: -_-_-_-_-_-
)quelle
$ARGV
, dass sie statt der Verwendung von stdin von stdin liest , schlägt sie immer noch 108 Testfälle aus den Testskripten fehl.Python -
89939793 ZeichenNur weil.
Schlägt jetzt nur zehn Testfälle fehl (unter Berücksichtigung der Fälle, in denen es mehrere gültige Lösungen gibt). Ich werde es später vollständig beheben.
Leiht man sich eine der Regexen aus, endet es als
Mit 96 Zeichen.
quelle
Haskell, 90 Zeichen:
Meine erste Lösung - lang, aber arbeitet in linearer Zeit mit dynamischer Programmierung. :) 150 Zeichen :
Die zweite Lösung - viel langsamer (Exponentialzeit), aber viel kürzer: 90 Zeichen
quelle