Es ist der letzte Sprint ... und die Hälfte Ihres Teams ist krank. Sie arbeiten spät dran, machen gerade Ihr letztes Commit für den Tag und freuen sich auf ... warum haben Sie die Lichter ausgeschaltet? Ich erinnere mich nicht an den Sicherheitsmann, der vorbeikam ... oh nein! Ich habe meine Schlüssel zu Hause gelassen!
Als der Schrecken der Situation einsetzt, entscheiden Sie, dass Sie fliehen werden .
Aufgabenübersicht
Um deine Flucht zu bewirken, brauchst du einen Plan! Sie wissen jedoch, dass jeder Plan scheitern kann und dass unterschiedliche Pläne unterschiedliche Anstrengungen erfordern.
Da Sie hungrig, müde und ein Ingenieur sind, schreiben Sie ein kurzes Programm, um herauszufinden, wie Sie dem Komplex am besten entkommen können. Dabei müssen Sie die Erfolgsaussichten und den erforderlichen Aufwand in Einklang bringen.
Sie machen eine Karte des Gebäudes:
#######################
# = #
! = ! <-- window
# ! = # (freedom!)
#################= #
# # = #
# # = #
# # = #
# o ! # # ! = #
##| ! ## # ! = #
#######################
^ ^ ^
me my door ludicrously high shelves
(locked) (climbable)
Um dem Büro zu entkommen, müssen Sie sich von der Karte entfernen. Hier sehen Sie 2 Fenster ( !
), eines würde Sie in die Freiheit führen, aber nur eines davon ist zugänglich. Wir definieren "außerhalb der Karte", wenn Sie Ihre Füße außerhalb der Kartengrenzen haben
Zelltypen
- empty, you can be here (i.e. the escapee can consume this cell)
# - solid (your desk, your in-tray), you can't be here, but you can stand on it
! - destructible, (co-worker's desk, door, window), you can't be here until you smash it first (turning it into an empty cell)
= - climbable, (fire ladder, filing cabinet, etc.), you can be here
Die Zellen, die ursprünglich vom Flüchtling verbraucht wurden, gelten als leer.
Aktionsspezifikationen
Sie haben eine Reihe von möglichen Aktionen zur Verfügung. Diese werden durch einfache Zustandsübergänge mit einer ganzzahligen Erfolgswahrscheinlichkeit definiert. Zum Beispiel bewegen Sie zum Gehen die Eskapee-Zelle um eine Zelle, die wir mit diesem Übergang darstellen:
Schritt
1 St., 100%, Spiegel
o. o
|. --> |
# #
Die Punkte zeigen Zellen, die leer sein müssen (oder kletterbar, aber nicht fest oder zerstörbar sein dürfen), weil wir uns hinein oder hindurch bewegen. Die 100% bedeuten, dass Sie eine 100% ige Chance haben, sich nicht zu verletzen und Ihre gewagte Flucht zu beenden. Alle Wahrscheinlichkeiten sind ganzzahlige Prozentsätze zwischen 1% und einschließlich 100%. Das erste Diagramm zeigt den Ausgangszustand (auf etwas Festem stehend, neben einem leeren Raum stehend). Das zweite Diagramm zeigt den Terminalstatus (in den leeren Raum verschoben). Es ist nicht erforderlich, dass nicht spezifizierte Zellen (Leerzeichen ) auf der linken Seite (Ausgangszustand) etwas Besonderes sind. Nicht spezifizierte Zellen (Leerzeichen,
) auf der rechten Seite (Endzustand) sollte derselbe sein wie zuvor (z. B. auf was auch immer sich hinter dem Flüchtling befand oder auf was auch immer ich gerade gehe (sei es ein leerer Raum oder etwas anderes) ) Diagramme ändern nur die Zellen von zerstörbar nach leer, es können keine weiteren Änderungen auftreten. "1 STP" bedeutet, dass es 1 STP kostet: Wir definieren den "STP" als die Energiemenge, die für einen Schritt erforderlich ist.
"Spiegel" bedeutet, dass diese Aktion zwei Formen hat. Die Aktion "rechts" wird angezeigt, die Aktion "links" ist ein exakter Spiegel, zum Beispiel:
.o
.|
#
ist die Spiegelform (links) von
o.
|.
#
Die rechte Aktion heißt "Right" (zB "Step Right") Die linke Aktion heißt "Left" (zB "Step Left")
In diesen Diagrammen wird der Flüchtling durch gezeigt
o
|
im Stehen (2 Einheiten groß) und
%
beim Hocken (1 Einheit groß). Zellen, die fest oder zerstörbar sein müssen, werden durch einen Hash angezeigt #
. Zellen, die nicht fest oder zerstörbar sein dürfen, sind durch einen Punkt gekennzeichnet .
. Zellen, die zerstörbar sein müssen, werden durch einen Knall angezeigt !
. Ein neu erzeugter Leerraum wird durch einen Unterstrich angezeigt _
.
x
ist ein Referenzpunkt, der sich nicht bewegt (es gibt ihn nicht, keine Einschränkung dafür, wie diese Zelle sein muss (wie ein Leerzeichen )).
Hinweis: Wir ignorieren das Problem der schnellen Verzögerung, wenn Sie auf den Boden fallen, und ja, in diesem Spiel können Sie absolut epische Sprünge auf Leitern machen.
Schritt
1 St., 100%, Spiegel
o. o
|. --> |
x# x#
Steigen Sie aus
1 St., 100%, Spiegel
= =
o. --> o
|. |
x= x=
Mischen
3 stp, 100%, spiegel
%. %
x# --> x#
Aufsteigen
10 Stp., 95%, Spiegel
o. %
|# --> #
x# x#
Fallen
0 stp, 100%
o
| --> o
x. x|
Drop (Stehen)
0 stp, 100%
% o
x. --> x|
Hochklettern
2 stp, 100%
= o
o --> |
x| x
Hocken
2 stp, 100%
o
| --> %
x# x#
Stand
4 stp, 100%
. o
% --> |
x# x#
Kurzer Sprung
4 Stp., 95%, Spiegel
o.. o
|.. --> |
x# x#
Weitsprung
7 Stp., 75%, Spiegel
o... o
|... --> |
x# x#
Hochsprung
12 stp, 90%, Spiegel
.. o
o. --> |
|
x# x#
Setzen Sie Ihren Rücken hinein!
20 Stp., 80%, Spiegel
o!. _o
|!. --> _|
x# x#
Schlagen
8 stp, 90%, Spiegel
o! o_
| --> |
x# x#
Kick
8 Stp., 85%, Spiegel
o o
|! --> |_
x# x#
Briefmarke
8 stp, 90%
o o
| --> |
x! x_
Pläne
Ein Plan ist eine Folge der oben definierten Aktionen. Beispielsweise:
Step Left
High Jump Left
Crouch
Shuffle Left
Shuffle Left
Stand
Long Jump Left
Put your back into it! Left
Step Left
Beachten Sie die Einbeziehung der Tropfen. Die Regeln sollten so festgelegt werden, dass Sie nichts anderes tun als fallen zu lassen, aber Sie müssen immer noch planen!
Für jeden Plan ist ein Aufwand erforderlich. Dies ist die Summe des Aufwands für jeden Schritt. Es gibt auch eine Erfolgswahrscheinlichkeit, die sich aus den Erfolgswahrscheinlichkeiten jeder Aktion ergibt. Einfaches Beispiel:
Step Right: 1stp, 100%
Long Jump Right: 7stp, 75%
Step Right: 1stp, 100%
Stamp: 8stp, 90%
Drop: 0stp, 100%
Drop: 0stp, 100%
Drop: 0stp, 100%
Drop: 0stp, 100%
Step Left: 1stp, 100%
Step Left: 1stp, 100%
High Jump Left: 12stp, 90%
Effort = 1+7+1+8+1+1+12 = 31
Success Probability = 75%*90*90% = 60.75%
Ein "bearbeitetes Beispiel" für die Karte oben auf der Seite kann als Zusammenfassung angesehen werden .
Eingang
Die Eingabe besteht aus zwei Teilen, einer Ganzzahl und einem Array oder einer Zeichenfolge.
Die Ganzzahl ist Ihre minimale akzeptable (prozentuale) Erfolgswahrscheinlichkeit. Es ist als Prozentsatz zu interpretieren, also bedeutet 80, dass Ihr Plan mit einer Wahrscheinlichkeit von mindestens 80% erfolgreich sein muss.
Eine gültige Karte ist ein Rechteck, das den stehenden Eskapee (Mindestgröße 1x2) und keine nicht angegebenen Symbole enthält. Alle Zeilen sind gleich lang. Sie können Eingaben als eindimensionale, durch Trennzeichen getrennte Zeichenfolge (Trennzeichen muss ein einzelnes konsistentes Zeichen oder eines aus CRLF- und LFCR-Paaren sein) als ein ähnliches eindimensionales oder zweidimensionales Array akzeptieren. Wenn Ihr ausgewähltes Eingabeformat die Breite oder Höhe der Karte nicht in irgendeiner Weise angibt, können Sie zusätzliche Argumente dafür akzeptieren (dies müssen Sie in Ihrer Antwort klar angeben). Sie können Befehlszeilenargumente und Standardeingaben mischen, wenn dies für Sie geeignet ist (z. B. Karte von stdin, minimale Erfolgswahrscheinlichkeit von argv). Das Folgende sind gültige und ungültige Beispielkarten.
Gültig:
o
|
Gültig:
# #
! o #
! | #
#########
Ungültig (kein Flüchtling):
# #
! #
! #
#########
Ungültig (Escape beginnt immer zu stehen):
# #
! #
! % #
#########
Ungültig (ungültiges Symbol):
# #
! ~ #
! #
#########
Ungültig (kein Rechteck / Zeilen mit unterschiedlicher Länge):
# #
! o #
! | #
#########
Sie können davon ausgehen, dass Ihre Eingabe gültig ist (es ist mir egal, was Ihr Programm tut, wenn es ungültige Eingaben erhält).
Ausgabe
Die Ausgabe erfolgt in Textform (ASCII). Kann als Zeichenfolge zurückgegeben oder auf die Standardausgabe gedruckt werden. Der Plan muss durch einen LF, CRLF oder LFCR abgegrenzt werden. Ebenso muss nach dem erforderlichen Aufwand ein weiterer LF, CRLF oder LFCR vorhanden sein. Ein nachfolgender Zeilenumbruch ist optional.
Sie müssen einen optimalen Plan zusammen mit dem erforderlichen Aufwand ausgeben oder "Es gibt keine Hoffnung!" wenn kein solcher Plan existiert. Sie müssen die Erfolgswahrscheinlichkeit nicht ausgeben. Dieser Text kann einen nachgestellten Zeilenumbruch enthalten oder nicht.
Ein optimaler Plan ist definiert als ein Plan (siehe oben), der den geringsten Aufwand mit mindestens der gegebenen Erfolgswahrscheinlichkeit erfordert. Beachten Sie, dass Ihre Wahrscheinlichkeitsberechnungen genau sein müssen. Sie können davon ausgehen, dass Fließkommazahlen nicht gut genug sind (daher erwarte ich nicht, dass Sie sie ausgeben). Ich werde versuchen, Testfälle zu entwerfen, um dies fair zu testen (wenn Sie sie bestehen und keine dummen Annahmen treffen, halten Sie Ihre Einreichung möglicherweise für gültig).
Format:
Required Effort: <effort>
<plan>
Zum Beispiel für die Eingabe
50
# #
! o #
! | #
#########
Eine angemessene Ausgabe wäre:
Required Effort: 23
Step Left
Step Left
Step Left
Kick Left
Punch Left
Step Left
Step Left
Step Left
Step Left
Die Erfolgswahrscheinlichkeit liegt hier bei 76,5%.
Für die gleiche Karte, jedoch mit einer minimalen Erfolgswahrscheinlichkeit von 80%, müssten Sie "Ihren Rücken hineinlegen", was mehr Aufwand erfordert, aber die Erfolgswahrscheinlichkeitskriterien erfüllt. Wenn die minimale Erfolgswahrscheinlichkeit größer als 80% wäre, müssten Sie etwas härter nachdenken (entweder durch einen Teil der Tür schlagen oder treten und hinausschlurfen). Wenn die minimale Erfolgswahrscheinlichkeit 100% wäre, müssten Sie ausdrucken "Es gibt keine Hoffnung!"
Beispiele
Es ist möglich, dass es mehr als einen gültigen Plan für eine Eingabe gibt. Ihre Ausgabe muss nicht genau diesen entsprechen, aber den richtigen erforderlichen Aufwand haben und einen gültigen Plan haben. Sie können den Prüfer verwenden, um Ihre Lösungen zu überprüfen (siehe unten).
Eingang:
100
o
|
Ausgabe:
Required Effort: 0
Drop
Eingang:
5
# = #
# = !
# = ! ! !
# =#######
# = #
# = o #
# = ! | #
##########
Ausgabe:
Required Effort: 57
Step Left
Kick Left
Step Left
Step Left
Step Left
Climb Up
Climb Up
Climb Up
Climb Up
Climb off Right
High Jump Right
Long Jump Right
Step Right
Drop
Kick Right
Crouch
Shuffle Right
Shuffle Right
Eingang:
60
#########
# ! # #
! ! ! o #
! # ! | #
#########
Ausgabe:
Required Effort: 58
Step Left
Kick Left
Crouch
Shuffle Left
Shuffle Left
Stand
Punch Left
Clamber Up Left
Shuffle Left
Drop (Stand)
Kick Left
Crouch
Shuffle Left
Shuffle Left
Für dieselbe Karte, jedoch zu 80%, sollte die Ausgabe wie folgt lauten:
There is no hope!
Für dieselbe Karte, jedoch zu 50%, wird der erforderliche Aufwand mit einem anderen Plan zu 56.
Eingang:
50
#######################
# # = #
! # = !
# # = #
###### #####!## =### #
#= ## # = #
#=############# = #
#= = #
#= o = #
#!!| = #
#######################
Ausgabe:
Required Effort: 121
Step Right
Step Right
Step Right
Step Right
Step Right
Step Right
Step Right
Step Right
Step Right
Step Right
Step Right
Step Right
Step Right
Step Right
Climb Up
Climb Up
Climb Up
Climb Up
Climb Up
Climb Up
Climb off Right
Long Jump Left
Step Left
Step Left
Stamp
Drop
Drop
Crouch
Shuffle Left
Shuffle Left
Shuffle Left
Shuffle Left
Shuffle Left
Shuffle Left
Stand
Clamber Up Left
Stand
Clamber Up Left
Stand
Step Left
Step Left
Step Left
Step Left
Punch Left
Clamber Up Left
Shuffle Left
Eingang:
66
######
# ###
#o ! !
#| ! !
### ##
######
Ausgabe:
Required Effort: 37
Step Right
Put your back into it! Right
Kick Right
Crouch
Shuffle Right
Shuffle Right
Eingang:
Dieser soll eine Reihe falscher Annahmen überprüfen, denen man zum Opfer fallen und die folglich etwas seltsam aussehen können
30
###################
# ## # # # # = #
! ## # # # = #
# # # = #
## ############= #
# ## # #= #
# = # #= #
! = # #= #
# = # #= #
#o= ! ==#
#|= ! =#
#!= # ==########==#
# # ! !! =#
# # !! ! = #
# # !!!!#########
# # # #
# # # #
###################
Ausgabe mit Erfolgschance Einschränkung 30:
Required Effort: 199
Long Jump Right
Put your back into it! Right
<snip>
Ausgabe mit Erfolgschance-Einschränkung 32:
Required Effort: 200
Long Jump Right
Punch Right
<snip>
Wenn Sie die Karte oben als Eingabe verwenden, sollten Sie mit einer Erfolgswahrscheinlichkeit von 1% einen erforderlichen Aufwand von 116 erzielen (Erfolgschance ~ 32%, die Ausführung in meinem Testprogramm dauerte ca. 20 Sekunden).
Siegkriterien
Dies ist Code-Golf, möge der kürzeste Code gewinnen.
Um berechtigt zu sein, muss Ihre Funktion oder Ihr Programm funktionieren und in der Lage sein, jeden der oben genannten Testfälle in weniger als 30 Minuten auf einem vernünftigen Computer zu lösen. Mein Löser erledigt sie jeweils in weniger als 30 Sekunden. Wenn das Testskript (unten) in weniger als 30 Minuten ausgeführt wird, können Sie mit Sicherheit loslegen.
Beispiel Solver, Verifier, Test Script und TestCases (mit Lösungen)
C # -Code für einen Solver und Lösungsüberprüfer ist hier als Zusammenfassung verfügbar . Der Inhalt enthält auch file.txt
eine maschinenlesbare (ausreichend) Form der oben beschriebenen Aktionen, die für die Ausführung des Programms erforderlich ist. Jegliche Diskrepanz zwischen dieser Datei und der Spezifikation ist nicht beabsichtigt.
Die Übersicht enthält auch eine Reihe von Testfällen (einschließlich aller obigen Beispiele) und ein PowerShell-Skript, mit dem automatisch eine Übermittlung für diese durchgeführt wird. Wenn das Skript anzeigt, dass ein bestimmter Test fehlgeschlagen ist, können Sie OfficeEscapeSolver.exe testcase<n>.txt outputFromYourProgram.txt
weitere Details anzeigen. Beispiellösungen für diese Testfälle finden Sie in einem anderen Gist .
Der gesamte Code ist ein komplettes Durcheinander (wenn auch ungolfed), aber Sie sollten sich nicht weit von dem entfernen müssen, static void Main(...)
um die Ausgabemenge zu ändern (Sie können diese Informationen gerne verwenden, ich habe sie zu Ihrem Vorteil bereitgestellt!).
Das Bestehen eines Testfalls bedeutet nicht unbedingt, dass Ihre Ausgabe gut strukturiert ist, da das Skript und der Prüfer sehr großzügig sind. Ihre Ausgabe muss mit der obigen Spezifikation übereinstimmen, damit Ihre Einreichung gültig ist.
Wenn Sie der Meinung sind, dass Sie einen Fehler mit dem Löser oder dem Testskript, einen Fehler in file.txt
oder einen zweifelhaften Testfall gefunden haben, kommentieren Sie diesen Beitrag bitte, oder senden Sie mir auf andere Weise einen Ping-Befehl im SE-Chat. Ich werde wahrscheinlich keinen anderen Kommunikationsversuch bemerken.
Ich werde das Testskript nicht in Bash oder Batch bereitstellen, weil ich sie nicht kenne, aber ich bin froh, eine Übersetzung beizufügen und werde eine C # -Version schreiben, wenn die Leute eine wollen.
Post Amble
Haben sie Fragen? Zögern Sie nicht, fragen Sie sie noch heute!
Diese Aufgabe erfordert Anstrengung , um ernsthaften Golfern etwas zu bieten, in das sie sich hineinversetzen können.
Mein Dank geht an ais523 für sein Feedback zu Input / Output.
Ich kann mehr Testfälle in der GIST-Datei bereitstellen, wenn die Leute mehr wollen (dieser Beitrag soll nicht länger werden) oder einige von ihnen bereitstellen möchten.
quelle
Antworten:
Perl 5,
1425,1464,1481,1469,1485,1438 BytesDas war eine lustige Herausforderung! Und es sieht schockierend aus, als hätte ich den kürzesten Code mit etwas weniger als 1,5 kB! :)
Ich bin mir ziemlich sicher, dass es endlich funktioniert. Das verwendete Trennzeichen ist
:
und es gibt einen zusätzlichen Abstand von zwei Zeilen oben und einer Spalte auf jeder Seite. Also für Ihre Eingabe von:Mein Programm würde dauern: (Hinweis: Am Ende muss ein Doppelpunkt stehen, am Anfang jedoch nicht!)
Ich verwende reguläre Ausdrücke, um von einer Karte in eine andere zu übersetzen und mit roher Gewalt zu lösen. Ich füge der Liste jedoch keine Karten hinzu, wenn diese Karte bereits mit weniger Aufwand und größerer oder gleicher Wahrscheinlichkeit erreicht wurde. Karten werden aus der Liste entfernt, sobald alle möglichen Bewegungen von diesem Punkt erschöpft sind. Das Programm wird erfolgreich beendet, wenn es mit einem regulären Ausdruck übereinstimmt, der anzeigt, dass ich die Seite oder den Boden erreicht habe, und mit "Es gibt keine Hoffnung!" Endet. wenn die Liste der Karten erschöpft ist.
Leider wurde sehr viel Effizienz abgehandelt, um ein paar Bytes zu entfernen, so dass die Golf-Version ziemlich langsam ist;) Perl scheint besonders die Bewertungen als ziemlich schmerzhaft zu empfinden.
Ohne weiteres
Aus Gründen der Vernunft ist hier das Gleiche mit Zeilenumbrüchen und ein paar Kommentaren:
Ich kann bereits einige Stellen sehen, an denen ich noch ein paar Bytes wegschneiden kann, aber ich möchte noch nicht alle Tests wiederholen. Später! :)
Bearbeiten: Es wurden einige Auffüllungen hinzugefügt, um die Ausgabe beim Durchlaufen des Bodens genauer anzupassen. Einige der Auswertungen wurden entfernt, sodass der Code jetzt möglicherweise auch schneller ausgeführt wird!
Bearbeiten: Wurde nicht richtig mit Leitern und Stürzen umgegangen. Kommt mit Leitern immer noch nicht zurecht ... Ich versuche das jetzt zu beheben.
quelle
C #,
181414811395 BytesWas für ein Mist !! Ich bin jetzt wirklich ziemlich zufrieden damit!
Probieren Sie es online
Komplettes Programm, Eingabe in STDIN, Ausgabe in STDOUT. Im Wesentlichen ein Umschreiben meines ursprünglichen Lösers unter Verwendung eines einfachen und ineffizient implementierten BFS, um den optimalen Pfad zu finden. Es ist einigermaßen schnell, kann nicht viel langsamer sein als meine andere Implementierung (ich habe es allerdings nicht wirklich zeitlich festgelegt) und läuft mit Sicherheit innerhalb des Zeitlimits. Ein Großteil der Kosten entfällt auf die Aktionstabelle, die als durch Kommas getrennte Werte codiert ist, in denen der Name, die Zuordnungszuordnung (Match / Smash) und andere Eigenschaften jeder verfügbaren Aktion aufgezeichnet sind.
Es beginnt mit dem Einlesen der minimalen Erfolgswahrscheinlichkeit und der Karte. Dann findet es den Flüchtling, entfernt ihn von der Karte und erstellt einen Suchstatus, der diese Informationen enthält. Anschließend wird das BFS ausgeführt, das wiederholt mit dem geringsten Aufwand den nächsten fälligen Status überprüft (um sicherzustellen, dass eine optimale Lösung gefunden wird). Vor dem Erweitern des Knotens werden Aufwand und Erfolgswahrscheinlichkeit mit früheren Knoten mit derselben Karte und demselben Fluchtort verglichen und es wird abgelehnt, wenn bereits eine bessere Route zu diesem Status gefunden wurde. Wenn es dies überlebt, fügt es sich der Tabelle 'seen' hinzu, damit es den Status später ablehnen kann. Das ist alles für die Leistung, und ohne sie wäre der Verzweigungsfaktor enorm. Dann wird geprüft, ob der Flüchtling von der Karte entfernt ist. Wenn es so ist, dann gewinnt es! Es verfolgt den Status zurück (jeder vorherige Status wird mit jedem Status aufgezeichnet) und erstellt den Plan (in umgekehrter Reihenfolge), bevor die BFS-Schleife verlassen wird. Andernfalls wird versucht, jede Aktion anzuwenden, und es werden alle Aktionen hinzugefügt, die auf die angewendet werden können
due
Warteschlange, bevor diese Warteschlange sortiert wird, damit wir den Status mit dem geringsten Aufwand bei der nächsten Iteration erhalten.Formatierter und kommentierter Code:
quelle