Springen und Laufen

18

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:

Illustration der Bewegung RRJRJRR

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:

Der Aufruf erfolgt in beiden Fällen: <test script> <my program> [arguments]zB ./test ruby jumprun.rboder ./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
Joey
quelle
@Joey Ich bekomme eine Fehlermeldung beim Versuch, test.sh mit ./test.sh perl jump.pl- ./test.sh: line 42: syntax error near unexpected token 'done', under bash 3.2.48
swilliams am
@Joey Ich habe meinen Cache geleert, neu heruntergeladen und es funktioniert jetzt großartig. Vielen Dank.
Swilliams
Betrachtet man die Lösungen, war es anscheinend wirklich zu trivial. Entschuldigung.
Joey
1
Ich nehme an, rückwärts laufen / springen ist nicht erlaubt? Wenn es so wäre, würde es Landschaften wie - - lösbar machen.
Keith Randall
Keith: Ein bisschen zu spät, um die Aufgabe zu ändern, denke ich.
Joey

Antworten:

7

Perl, 53 Zeichen

s/-...(?=(-|-...)*-$)/J/g;y/-/R/;/_/?$_="!":s/.$//

Führen Sie dies mit perl -p jumpnrun.pl. Ich habe 3 Zeichen für die -pOption gezählt, das ist der Längenunterschied zwischen perl jumpnrun.plund perl -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 .

Ventero
quelle
3

Ruby, 93 90 79 70 Zeichen

Ich 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 ;-).

puts gets.gsub(/-...(?=(-|-...)*-$)/,?J).tr(?-,?R)=~/^([JR]*)R$/?$1:?!

Es übergibt alle Testfälle des bereitgestellten Skripts.

Mehrere Zeichen im Vergleich zum vorherigen Skript gespeichert (jetzt gsubgenü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

z=gets.chop
z.chars{z.sub!(/^(-|-...)((-|-...)*-)$/){$><<($1==?-??R:?J);$2}}
z!=?-&&$><<?!

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

puts (z=gets.chop.gsub(/(-...|-)(?=(-|-...)*-$)/){$1==?-??R:?J})=~/_/??!:z.chop

in zwei

puts (z=gets.chop.gsub(/-...(?=(-|-...)*-$)/,?J).tr(?-,?R))=~/_/??!:z.chop

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.

Howard
quelle
Sie können 3 Zeichen speichern, indem Sie die letzte Zeile in ändern z!=?-&&$><<?!. Ansonsten tolle Lösung, +1!
Ventero
@Ventero Ich hatte, dass man den ersten Test nicht bestand, weil überhaupt keine Ausgabe für "-" ;-)
Howard
Hm, anscheinend hat mein PowerShell-Skript einen winzigen Fehler. Es akzeptiert anscheinend keine Eingabe für Test 2 und nicht für Test 1. Das ist ... gelinde gesagt komisch. Ich werde versuchen, das zu beheben.
Joey
Ok, das Testskript sollte repariert sein und ein tatsächlich leeres Ergebnis für Test 1 nicht länger ablehnen. Ok, jetzt sollte es repariert sein.
Joey
@Joey Danke. Nun sind es 90 ;-)
Howard
1

Perl - 71 60

$_=<>;y/-/R/;s/R...(?=(R(...)?)*R$)/J/g;print/_/?"!":s/.$//r

Nun 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 -Eund saystatt läuft print, aber dann versucht Perl, die Eingabe als Schalter zu interpretieren ... ( Unrecognized switch: -_-_-_-_-_-)

Swilliams
quelle
Die Frage besagt, dass die Eingabe auf stdin erfolgt. Wenn Sie Ihre Lösung so ändern $ARGV, dass sie statt der Verwendung von stdin von stdin liest , schlägt sie immer noch 108 Testfälle aus den Testskripten fehl.
Ventero
@Ventero Oh, hoppla ... Ich glaube, ich weiß, warum das so ist. Ich werde bald eine Lösung finden ... das ist es, was ich bekomme, wenn ich nicht alle Testfälle durchläuft ...> _>
swilliams
Nun, die Absicht der Skripte war es, es den Leuten zu ermöglichen, auf einfache Weise die Gültigkeit und Einhaltung der Spezifikation zu überprüfen :-)
Joey,
@Joey Das Problem war, dass ich es irgendwie geschafft habe, "Testskript" mit "Referenzimplementierung" zu verwechseln, bis Ventero seinen Kommentar gepostet hat :) ... das Skript ist jetzt fast repariert, aber derzeit scheitert nur 20, alle falschen Negative
swilliams
1

Python - 89 93 97 93 Zeichen

Nur weil.

import re;i=re.sub('...(?<!---)-','J',input()[1:]);print('!'if'_'in i else re.sub('-','R',i))

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

import re;i=re.sub('-...(?=(-|-...)*-$)','J',input());print('!'if'_'in i else re.sub('-','R',i))

Mit 96 Zeichen.

JAB
quelle
1
Besteht nur 728 der Testfälle. Ich habe die Testskripte aus einem bestimmten Grund dort abgelegt.
Joey
@ Joey: Sieht so aus, als hätte ich vergessen, das führende Zeichen von der Eingabe abzuschneiden. Wie dumm von mir. Es ist jetzt korrigiert.
JAB
Noch besteht nur 766/849 Testfälle.
Ventero
1

Haskell, 90 Zeichen:

Meine erste Lösung - lang, aber arbeitet in linearer Zeit mit dynamischer Programmierung. :) 150 Zeichen :

x!y="!"
q '-'=max
q c=(!)
s i=r where r=zipWith3 q i(0&'R')$3&'J';n&c="":replicate n"!"++map(c#)r
c#"!"="!"
c#s=c:s
main=interact$reverse.last.s.init

Die zweite Lösung - viel langsamer (Exponentialzeit), aber viel kürzer: 90 Zeichen

s"-\n"=""
s('-':t)=max('R'#s t)$'J'#s(drop 3 t)
s _="!"
c#"!"="!"
c#s=c:s
main=interact s
Rotsor
quelle