To ostatni sprint ... a połowa twojej drużyny jest chora. Pracujesz do późna, po raz ostatni zatwierdzasz ten dzień, nie mogę się doczekać ... dlaczego światła się wyłączyły? Nie pamiętam, żeby przybył ochroniarz ... och nie! Zostawiłem klucze w domu!

Gdy grozi ci przerażenie, postanawiasz uciec .

Podsumowanie zadania

Aby dokonać ucieczki, potrzebujesz planu! Jednak wiesz, że każdy plan ma szansę zawieść, a różne plany wymagają różnych nakładów pracy.

Będąc głodnym, zmęczonym i inżynierem, postanawiasz napisać krótki program, aby określić najlepszy sposób na ucieczkę z kompleksu, równoważąc obawy dotyczące prawdopodobieństwa sukcesu i wysiłku, jaki będzie on wymagał.

Wykonujesz mapę budynku:

#######################
#                =    #
!                =    !    <-- window
#          !     =    #        (freedom!)
#################=    #
#    #           =    #
#    #           =    #
#    #           =    #
# o  !   # #  !  =    #
##|  !  ## #  !  =    #
#######################

  ^  ^           ^
  me my door     ludicrously high shelves
     (locked)    (climbable)

Aby uciec z biura, musisz przenieść się z mapy. Tutaj widzisz, że są 2 okna ( !), każde z nich doprowadzi cię do wolności, ale tylko jedno z nich jest dostępne. Definiujemy „poza mapą” jako trzymanie stóp poza granicami mapy

Typy komórek

  - 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

Komórki pierwotnie pochłonięte przez uciekiniera zabrane do pustki.

Specyfikacja działania

Do dyspozycji masz wiele możliwych działań. Są one zdefiniowane przez proste przejścia stanu z pewnym prawdopodobieństwem powodzenia liczby całkowitej. Na przykład podczas chodzenia przesuwasz uciekiniera o jedną komórkę, którą reprezentujemy za pomocą tego przejścia:

Krok

1 stp, 100%, lustro

 o.            o
 |.   -->      |
 #            #

Kropki pokazują komórki, które muszą być puste (lub możliwe do wspinaczki, ale nie stałe lub możliwe do zniszczenia), ponieważ się do nich wprowadzamy lub przez nie. 100% oznacza, że ​​masz 100% szansy na to, że nie skrzywdzisz siebie i nie zakończysz swojej śmiałej ucieczki. Wszystkie prawdopodobieństwa będą procentami całkowitymi od 1% do 100% włącznie. Pierwszy schemat pokazuje stan początkowy (stanie na czymś stałym, stojący obok pustej przestrzeni). Drugi schemat pokazuje stan terminala (przeniesiony do pustej przestrzeni). Nie ma wymagań, aby żadne nieokreślone komórki (spacje ) po lewej stronie (stan początkowy) były czymś szczególnym. Nieokreślone komórki (spacja,) po prawej stronie (stan terminalu) powinien być taki sam, jak przedtem (np. cokolwiek znajdowało się za uciekinierem lub cokolwiek, na co akurat chodzę (czy to pusta przestrzeń, czy inaczej). Zauważ, że wszystko po prawej stronie (stan terminalu) ) diagramy zmieniają tylko komórki z zniszczalnego na puste, nie mogą wystąpić żadne inne zmiany. „1 stp” oznacza, że ​​kosztuje 1 stp: definiujemy „stp” jako ilość energii wymaganą do wykonania kroku.

„lustro” oznacza, że ​​ta akcja ma dwie formy. Pokazana jest akcja „prawa”, akcja „lewa” to dokładne odbicie lustrzane, na przykład:

.o
.|
 # 

jest lustrzaną (lewą) formą

o.
|.
# 

Prawe działanie nazywa się „Prawo” (np. „Krok w prawo”) Lewe działanie nazywa się „Lewo” (np. „Krok w lewo”)

Na tych schematach uciekinier jest pokazany przez

o
|

stojąc (2 jednostki wysokości) i

%

podczas kucania (1 jednostka wysokości). Komórki, które muszą być całkowicie i zniszczalny są oznaczone ziemniaczane #. Komórki, które nie mogą być stałe ani ulegać zniszczeniu, są oznaczone kropką .. Komórki, które muszą być zniszczalne, są oznaczone hukiem !. Nowo utworzona pusta przestrzeń jest podkreślona znakiem podkreślenia _. xjest punktem odniesienia, który się nie porusza (nie istnieje, nie ma ograniczeń co do tego, czym musi być ta komórka (jak spacja )).

Uwaga: ignorujemy kwestię szybkiego zwalniania, gdy uderzysz o podłogę, i tak, w tej grze możesz wykonywać epickie skoki na drabiny)

Krok

1 stp, 100%, lustro

 o.         o
 |.  -->    |
x#        x#

Zejdź

1 stp, 100%, lustro

 =         =
 o.  -->    o
 |.         |
x=        x= 

Człapać

3 stp, 100%, lustro

 %.         %
x#   -->  x# 

Wleźć

10 stp, 95%, lustro

 o.         %
 |#  -->    #
x#        x#

Upuszczać

0 stp, 100%

 o         
 |  -->   o
x.       x|

Drop (Stand)

0 stp, 100%

 %        o
x.  -->  x|

Wspinać się

2 stp, 100%

 =        o
 o  -->   |
x|       x

Kucanie

2 stp, 100%

 o
 |  -->   %
x#       x#

Stoisko

4 stp, 100%

 .        o
 %  -->   |
x#       x#

Krótki skok

4 stp, 95%, lustro

 o..          o
 |..  -->     |
x#         x#

Długi skok

7 stp, 75%, lustro

 o...           o
 |...  -->      |
x#          x#

Wysoki skok

12 stp, 90%, lustro

 ..         o
 o.  -->    |
 |          
x#        x# 

Połóż się z powrotem!

20 stp, 80%, lustro

 o!.         _o
 |!.  -->    _|
x#         x#

Stempel

8 stp, 90%, lustro

 o!        o_
 |   -->   |
x#        x#

kopnięcie

8 stp, 85%, lustro

 o         o
 |!  -->   |_
x#        x#

Pieczęć

8 stp, 90%

 o        o
 |  -->   |
x!       x_

Plany

Plan jest sekwencją działań określonych powyżej. Na przykład:

Step Left
High Jump Left
Crouch
Shuffle Left
Shuffle Left
Stand
Long Jump Left
Put your back into it! Left
Step Left

Zwróć uwagę na włączenie kropli. Reguły powinny być ustawione tak, aby nie robić nic poza upuszczaniem, ale nadal musisz to zaplanować!

Każdy plan wymaga wymaganego wysiłku, który jest sumą wysiłków na każdym kroku. Istnieje również prawdopodobieństwo sukcesu, które jest iloczynem prawdopodobieństwa sukcesu każdego działania. Prosty przykład:

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%

„Sprawdzony przykład” mapy u góry strony można znaleźć jako istotę .

Wkład

Dane wejściowe składają się z dwóch części: liczby całkowitej oraz tablicy lub ciągu znaków.

Liczba całkowita to minimalne akceptowalne (procentowe) prawdopodobieństwo sukcesu. Należy to interpretować jako procent, więc 80 oznacza, że ​​Twój plan musi zakończyć się powodzeniem z prawdopodobieństwem nie mniejszym niż 80%.

Prawidłowa mapa to prostokąt, który zawiera stojącego uciekiniera (minimalny rozmiar 1x2) i żadnych nieokreślonych symboli. Wszystkie rzędy będą tej samej długości. Możesz zaakceptować dane wejściowe jako 1-wymiarowy ciąg rozdzielany (separator musi być pojedynczym spójnym znakiem lub jednym z par CRLF i LFCR), jako podobną tablicę 1-wymiarową lub 2-wymiarową. Jeśli wybrany format wejściowy nie wskazuje w żaden sposób szerokości lub wysokości mapy, możesz zaakceptować dla nich dodatkowe argumenty (musisz to wyraźnie podać w odpowiedzi). Możesz mieszać argumenty wiersza poleceń i standardowe dane wejściowe, jeśli ci to odpowiada (np. Mapa ze standardowego wejścia, minimalne prawdopodobieństwo sukcesu z argv). Poniżej przedstawiono przykładowe prawidłowe i nieprawidłowe mapy.

Ważny:

o
|

Ważny:

  #     #
  !   o #
  !   | #
#########

Nieprawidłowy (brak uciekiniera):

  #     #
  !     #
  !     #
#########

Nieprawidłowy (uciekinier zawsze zaczyna stać):

  #     #
  !     #
  !   % #
#########

Nieprawidłowy (nieprawidłowy symbol):

  #     #
  !  ~  #
  !     #
#########

Nieprawidłowy (nie jest to prostokąt / rzędy o różnej długości):

  #     #
  !   o #
  !   | # 
#########

Możesz założyć, że twoje dane wejściowe są prawidłowe (nie obchodzi mnie, co robi twój program, jeśli zostanie przekazane nieprawidłowe dane wejściowe).

Wydajność

Dane wyjściowe to tekst (ASCII). Może zostać zwrócony jako ciąg znaków lub wydrukowany na standardowe wyjście. Plan musi być ograniczony przez LF, CRLF lub LFCR. Podobnie, po wymaganym wysiłku musi być inny LF, CRLF lub LFCR. Przerwanie linii końcowej jest opcjonalne.

Musisz przedstawić optymalny plan wraz z wymaganym wysiłkiem lub „Nie ma nadziei!” jeśli taki plan nie istnieje. Nie musisz podawać prawdopodobieństwa sukcesu. Ten tekst może, ale nie musi, zawierać końcową linię.

Optymalny plan jest zdefiniowany jako plan (patrz wyżej) wymagający minimalnego wysiłku przy co najmniej danym prawdopodobieństwie sukcesu. Zwróć uwagę, że obliczenia prawdopodobieństwa muszą być dokładne, nie możesz zakładać, że zmiennoprzecinkowa jest wystarczająco dobra (dlatego nie oczekuję, że będziesz je wypisywać). Spróbuję zaprojektować przypadki testowe, aby rzetelnie to przetestować (jeśli zdasz je i nie podejmiesz żadnych głupich założeń, możesz uznać, że Twoje zgłoszenie jest ważne).

Format:

Required Effort: <effort>
<plan>

Na przykład dla danych wejściowych

50
  #     #
  !   o #
  !   | #
#########

Odpowiednim wyjściem byłoby:

Required Effort: 23
Step Left
Step Left
Step Left
Kick Left
Punch Left
Step Left
Step Left
Step Left
Step Left

Prawdopodobieństwo sukcesu tutaj wynosi 76,5%.

W przypadku tej samej mapy, ale z minimalnym prawdopodobieństwem sukcesu wynoszącym 80%, musiałbyś „odłożyć na bok”, co wymagałoby więcej wysiłku, ale spełniałoby kryteria prawdopodobieństwa sukcesu. Gdyby minimalne prawdopodobieństwo sukcesu było większe niż 80%, trzeba by się trochę zastanowić (albo uderzyć pięścią, albo przekopać część drzwi i przemieścić się). Gdyby minimalne prawdopodobieństwo sukcesu wynosiło 100%, musiałbyś wydrukować „Nie ma nadziei!”

Przykłady

Możliwe, że istnieje więcej niż jeden prawidłowy plan dla danych wejściowych, dane wyjściowe nie muszą być dokładnie takie, ale muszą mieć odpowiedni wymagany wysiłek i być prawidłowym planem. Możesz użyć weryfikatora, aby sprawdzić swoje rozwiązania (patrz poniżej)

Wkład:

100
o
|

Wydajność:

Required Effort: 0
Drop

Wkład:

5
# =      #
# =      !
# = !  ! !
# =#######
# =      #
# =   o  #
# = ! |  #
##########

Wydajność:

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

Wkład:

60
#########
# ! #   #
! ! ! o #
! # ! | #
#########

Wydajność:

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

Dla tej samej mapy, ale 80%, wynik powinien wynosić:

There is no hope!

Dla tej samej mapy, ale 50%, Wymagany wysiłek staje się 56 przy innym planie)

Wkład:

50
#######################
#          #     =    #
!          #     =    !
#          #     =    #
######  #####!## =### #
#=   ##       #  =    #
#=#############  =    #
#=               =    #
#= o             =    #
#!!|             =    #
#######################

Wydajność:

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

Wkład:

66
######
#  ###
#o ! !
#| ! !
### ##
######

Wydajność:

Required Effort: 37
Step Right
Put your back into it! Right
Kick Right
Crouch
Shuffle Right
Shuffle Right

Wkład:

Ten ma na celu sprawdzenie szeregu fałszywych założeń, na które można paść ofiarą, a w konsekwencji może wyglądać nieco dziwnie

30
###################
# ## # # #   #  = #
! ## #   #   #  = #
#      #   #    = #
##  ############= #
# ## #         #= #
# =  #         #= #
! =  #         #= #
# =  #         #= #
#o=  !          ==#
#|=  !           =#
#!= # ==########==#
#   #    !   !!  =#
#   #    !!  !  = #
#   # !!!!#########
#   # #           #
#   # #           #
###################

Dane wyjściowe z szansą na ograniczenie sukcesu 30:

Required Effort: 199
Long Jump Right
Put your back into it! Right
<snip>

Dane wyjściowe z szansą na ograniczenie sukcesu 32:

Required Effort: 200
Long Jump Right
Punch Right
<snip>

Używając mapy u góry jako danych wejściowych, z prawdopodobieństwem ograniczenia sukcesu 1%, powinieneś otrzymać Wymagany Wysiłek 116 (szansa na sukces ~ 32%, zajęło mi to około 20 sekund w moim programie testowym).

Kryteria zwycięstwa

To jest golfowy kod, może wygrać najkrótszy kod.

Aby kwalifikować się, Twoja funkcja lub program musi działać i być w stanie rozwiązać każdą z powyższych przypadków testowych w mniej niż 30 minut na rozsądnej maszynie. Mój solver wykonuje je w ciągu mniej niż 30 sekund. Jeśli skrypt testowy (poniżej) działa w czasie krótszym niż 30 minut, na pewno warto.

Przykładowy solver, weryfikator, skrypt testowy i przypadki testowe (z rozwiązaniami)

Kod C # dla solvera i weryfikatora rozwiązania jest dostępny tutaj jako gist . Lista zawiera również file.txt, która jest czytelną dla komputera (wystarczającą) formę opisanych powyżej działań i jest wymagana do uruchomienia programu. Wszelkie rozbieżności między tym plikiem a specyfikacją nie są zamierzone.

Gist zawiera również szereg przypadków testowych (w tym wszystkie powyższe przykłady) oraz skrypt PowerShell do automatycznego uruchomienia przesyłania przeciwko nim. Jeśli skrypt powie ci, że dany test nie powiódł się, możesz uruchomić, OfficeEscapeSolver.exe testcase<n>.txt outputFromYourProgram.txtaby zobaczyć więcej szczegółów. Przykładowe rozwiązania dla tych przypadków testowych znajdują się w innej Gist .

Cały kod jest kompletnym bałaganem (choć nie jest golfem), ale nie trzeba odejść daleko od static void Main(...)zmiany ilości wydruków (skorzystaj z tych informacji, podałem je dla twojej korzyści!).

Zaliczenie przypadku testowego niekoniecznie oznacza, że ​​wyniki są dobrze uformowane, ponieważ skrypt i weryfikator są bardzo hojne. Twoje dane wyjściowe muszą być zgodne z powyższą specyfikacją, aby przesłanie było ważne.

Jeśli uważasz, że znalazłeś błąd w rozwiązaniu lub skrypcie testowym, błąd file.txtlub podejrzany przypadek testowy, skomentuj ten post lub w inny sposób pinguj mnie na czacie SE; Prawdopodobnie nie zauważę żadnej innej próby komunikacji.

Nie dostarczę skryptu testowego w Bash ani Batch, ponieważ ich nie znam, ale chętnie dołączę tłumaczenie i napiszę wersję C #, jeśli ludzie będą chcieli.

Post Amble

Masz pytania? Nie zwlekaj, zapytaj ich już dziś!

To zadanie wymaga wysiłku , aby dać poważnym golfistom coś, w co można zatopić zęby.

Moje podziękowania dla ais523 za jego opinię na temat wejścia / wyjścia.

Mogę podać więcej przypadków testowych w pliku gist, jeśli ludzie chcą więcej (nie chcę, aby ten post stał się dłużej), lub chcą podać własne.

Perl 5, 1425 1464 1481 1469 1485 1438 bajtów

To było zabawne wyzwanie! I, szokująco, wygląda na to, że mam najkrótszy jak dotąd kod o wartości poniżej 1,5 kB! :)

Jestem całkiem pewien, że w końcu to działa. Zastosowano separator :, a dodatkowe wypełnienie składa się z dwóch rzędów u góry i jednej kolumny z każdej strony . Więc za wkład:

60
#########
# ! #   #
! ! ! o #
! # ! | #
#########

mój program przyjąłby: (Uwaga: na końcu musi być dwukropek, ale nie na początku!)

60
#########:# ! #   #:! ! ! o #:! # ! | #:#########:

Używam wyrażeń regularnych, aby tłumaczyć z jednej mapy na drugą i rozwiązywać brutalną siłą. Nie dodam jednak map do listy, jeśli mapa została już osiągnięta przy mniejszym wysiłku i większym lub równym prawdopodobieństwie. Mapy są usuwane z listy po wyczerpaniu wszystkich możliwych ruchów z tego miejsca. Program kończy się pomyślnie, gdy pasuje do wyrażenia regularnego, który pokazuje, że dotarłem do boku lub do dołu i kończy się na „Nie ma nadziei!” kiedy lista map się wyczerpie.

Niestety, sprzedano kilka bajtów dużej wydajności, więc gra w golfa jest raczej powolna;) Perl wydaje się być szczególnie bolesny.

Bez dalszego adieu

chop($P=<>,$_=<>);s/:/ : /g;$w++until/:.{$w}:/;$z=$"x$w;$_="(.{".$w--."})"for($c,$h,$i,$j);$_="$z:$z: $_$z";$n="[ =]";$d="([!#])";@s=split/,/,'Drop,Drop (Stand),Stepx,Climb offx,Shufflex,Clamber Upx,Put your back into it!x,Punchx,Kickx,Short Jumpx,Long Jumpx,High Jumpx,Crouch,Stand,Climb Up,Stamp';@c=split/,/,"o$c\\|$c$n/ \$1o\$2|,%$c$n/o\$1|,o$n$h\\|$n$h${d}/ o\$1 |\$2\$3,=${c}o$n$h\\|$n$h=/=\$1=o\$2=|\$3=,%$n$h$d/ %\$1\$2,o$n$h\\|${d}$h${d}/ %".'$1 $2$3$4,'."o!$n$i\\|!$n$i${d}/  o\$1  |\$2\$3,o!$h\\|$c$d/o \$1|\$2\$3,\\|!$h$d/| \$1\$2,o$n$n$i\\|$n$n$i${d}/  o\$1  |\$2\$3,o$n$n$n$j\\|$n$n$n$j${d}/   o\$1   |\$2\$3,$n$n${h}o$n$h\\|$c$d/ o".'$1 |$2 $3$4,'."o$c\\|$c${d}/ \$1%\$2\$3,$n$c%$c${d}/o\$1|\$2\$3,=${c}o$c\\|/o\$1|\$2=,\\|$c!/|\$1 ";eval"*$_=sub{\$Q=\"$s[$_]\";s/$c[$_]/}"for(0..15);sub M{$_=join":",map{join'',reverse split//}split/:/};push@M,[$_,0,100,$P];$B{$_}=100;@E=(0,0,1,1,3,10,20,8,8,4,7,12,2,4,2,8);@P=map{100-$_}(0,0,0,0,0,5,20,10,15,5,25,10,0,0,0,10);$z='$N=[$_,$G+0,$t,$t[3]*100,"$t[4]$Q\n"];$N->[4]=~s/x/';do{sub A{@N=@$N;if($N[2]/$N[3]>$B{$N[0]}){push@M,$N;$B{$N[0]}=$N[2]/$N[3]}};die"There is no hope!\n"if(!(@M=grep$G-$_->[1]<21,@M));$e=-1;while(++$e<@M){@t=@{$M[$e]};$m=$_=$t[0];die"Required Effort: $t[1]\n$t[4]"if(/([|%]:|:[|%])/||/[|%][^:]*$/||/^$c:[^:]*[%|]/);for$x(0..15){$_=$m;$t=$t[2]*$P[$x];if($G==$E[$x]+$t[1]and$t>=$t[3]*100){&$x;eval"$z Right/";A;$_=$m;M;&$x;M;eval"$z Left/";A;}}}}

Dla zachowania rozsądku, to samo dotyczy nowych linii i kilku komentarzy:

chop($P=<>,$_=<>); #Take input
s/:/ : /g; #Pad columns on either side so escapee can leave that way
$w++until/:.{$w}:/; #Find width
$z=$"x$w;#Setup a blank line for use in padding later
$_="(.{".$w--."})"for($c,$h,$i,$j); #Set up some generic capturing regexes for reuse
$_="$z:$z: $_$z"; #Pad the top and bottom so the escapee can leave those ways
$n="[ =]"; #Regex for nonsolid block
$d="([!#])"; #Regex for solid block
@s=split/,/,'Drop,Drop (Stand),Stepx,Climb offx,Shufflex,Clamber Upx,Put your back into it!x,Punchx,Kickx,Short Jumpx,Long Jumpx,High Jumpx,Crouch,Stand,Climb Up,Stamp'; #Movement names
@c=split/,/,"o$c\\|$c$n/ \$1o\$2|,%$c$n/o\$1|,o$n$h\\|$n$h${d}/ o\$1 |\$2\$3,=${c}o$n$h\\|$n$h=/=\$1=o\$2=|\$3=,%$n$h$d/ %\$1\$2,o$n$h\\|${d}$h${d}/ %".'$1 $2$3$4,'."o!$n$i\\|!$n$i${d}/  o\$1  |\$2\$3,o!$h\\|$c$d/o \$1|\$2\$3,\\|!$h$d/| \$1\$2,o$n$n$i\\|$n$n$i${d}/  o\$1  |\$2\$3,o$n$n$n$j\\|$n$n$n$j${d}/   o\$1   |\$2\$3,$n$n${h}o$n$h\\|$c$d/ o".'$1 |$2 $3$4,'."o$c\\|$c${d}/ \$1%\$2\$3,$n$c%$c${d}/o\$1|\$2\$3,=${c}o$c\\|/o\$1|\$2=,\\|$c!/|\$1 ";#Movement regexes
eval"*$_=sub{\$Q=\"$s[$_]\";s/$c[$_]/}"for(0..15); #Setup methods to apply regexes. Name of these methods are 0,1,2,3, etc, so we can easily call them in a loop
sub M{$_=join":",map{join'',reverse split//}split/:/}; #Method to mirror the map. All the regexes are right-moving, so the mirror effects are achieved by M;&$x;M
push@M,[$_,0,100,$P]; #Array for initial map position. Encodes: [Map,Effort value,Probability value 1,Probability value 2,Movements(initially undef)]. Two integers are used for the probability to avoid floating point (although after enough steps they overflow and are automatically converted to f.p.)
$B{$_}=100; #Hash map to hold best probability of reaching a map. A new map is never added if it requires at least as much effort and doesn't give a better probability.
@E=(0,0,1,1,3,10,20,8,8,4,7,12,2,4,2,8); #Effort values
@P=map{100-$_}(0,0,0,0,0,5,20,10,15,5,25,10,0,0,0,10); #Probability values
$z='$N=[$_,$G+0,$t,$t[3]*100,"$t[4]$Q\n"];$N->[4]=~s/x/'; #Setup map values
do{ #Loop over all efforts. Do-while loop starts at undef, which is converted to zero automatically when used in a numeric context
    sub A{@N=@$N;if($N[2]/$N[3]>$B{$N[0]}){push@M,$N;$B{$N[0]}=$N[2]/$N[3]}}; #Method to add a map to list.
    die"There is no hope!\n"if(!(@M=grep$G-$_->[1]<21,@M)); #Pares away maps that no longer can produce new maps, and prints "There is no hope!" to stderr if there are no maps left.
    $e=-1;
    while(++$e<@M){ #Loop over all maps. Note that this loops over even maps that are created during the loop
        @t=@{$M[$e]}; #Dereference info about each map
        $m=$_=$t[0]; $Setup map variables
        die"Required Effort: $t[1]\n$t[4]"if(/([|%]:|:[|%])/||/[|%][^:]*$/||/^$c:[^:]*[%|]/); #Checks if escaped, and gives message if so.
        for$x(0..15){
            $_=$m; #Put map into $_
            $t=$t[2]*$P[$x]; #Probability calculation
            if($G==$E[$x]+$t[1]and$t>=$t[3]*100){ #If effort values are right and probability is over threshold
                &$x; #Run regex
                eval"$z Right/"; #Set up map info
                A; #Add map to list @M (only if probability works out right)
                $_=$m;
                M;&$x;M; #Same thing, but mirrored now (generates movement left)
                eval"$z Left/";
                A;
            }
        }
    }
}while(++$G)

Widzę już kilka miejsc, aby oddzielić jeszcze kilka bajtów, ale nie chcę jeszcze przechodzić wszystkich testów jeszcze raz. Później! :)

Edycja: Dodano również poniżej wyściółkę, aby lepiej dopasować wyjście podczas ucieczki przez podłogę. Usunęliśmy niektóre wersje, więc kod może teraz działać szybciej!

Edycja: Nie radziłem sobie z drabinami i upadkami całkiem dobrze. Nadal nie radzi sobie dobrze z drabinami ... Próbuję to teraz naprawić.

C #, 1814 1481 1395 bajtów

Co za slog !! Naprawdę jestem z tego zadowolony!

using C=System.Console;using System.Linq;class S{string M,N="";int x,y,E,c;decimal P=1;static void Main(){int W=0,H=0,x,i,j,k,X,Y,f,m,P=int.Parse(C.ReadLine());string l,M="",B,R="There is no hope!";for(;(l=C.ReadLine())!=null;H++,M+=l)W=l.Length;x=M.IndexOf("|");var D=new[]{new S{M=M,x=x%W,y=x/W}}.ToList();for(var N=D.ToDictionary(s=>R,s=>D);D.Count>0;D.Sort((z,w)=>z.E-w.E)){S s=D[f=0];D.Remove(s);var n=N[l=s.x+s.M+s.y+s.c]=N.ContainsKey(l)?N[l]:new S[0].ToList();if(n.All(o=>o.P<s.P|o.E>s.E)){n.Add(s);X=s.x;Y=s.y;if((X|Y|-X/W-Y/H)<0){R="Required Effort: "+s.E+s.N;break;}for(var A="0110d,Step,*** * #*,0110d,Climb off,=** * =*,3310d,Shuffle,***** #*,2:1/_,Clamber Up,*** *##*,0420_,Short Jump,****  *  #**,0730K,Long Jump,*****   *   #***,0<1/Z,High Jump,  * **#*,0D20P,Put your back into it!,****! *! #**,0800Z,Punch,***!**#*,0800U,Kick,*****!#*,0001d,Drop,*** ,1001d,Drop (Stand),*** ,2200d,Crouch,***#,1400d,Stand,* *#,020/d,Climb Up,=***,0800Z,Stamp,***!".Split(',');f<26;){l=A[k=f*3%48];B=A[++k]+(f>15?" Right":f>9?"":" Left");M=A[++k];m=f++/16*2-1;var Q=s.M.ToArray();var K=s.P*l[4]>=P&s.c==l[k=0]%2;for(j=Y-3;j++<=Y;)for(i=X;i!=X+m*M.Length/4;i+=m)if((K&="==  *!!##*!*=*|*| o*o ".Contains(""+((i|j)>=0&j<H&i<W?Q[x=j*W+i]:' ')+M[k]))&M[k++]==33)Q[x]=' ';if(K)D.Add(new S{M=new string(Q),N=s.N+"\n"+B,x=X+l[2]%48*m,y=Y+l[3]-48,c=l[0]/50,E=s.E+l[1]-48,P=s.P*l[4]/100});}}}C.Write(R);}}

Wypróbuj online

Kompletny program, pobiera dane wejściowe do STDIN, dane wyjściowe do STDOUT. Zasadniczo przepisz mój oryginalny solver, używając prostej i nieefektywnie zaimplementowanej BFS, aby znaleźć optymalną ścieżkę. Jest dość szybki, nie może być dużo wolniejszy niż moja inna implementacja (chociaż tak naprawdę nie miałem tego czasu), z pewnością działa w terminie. Znaczną część kosztów stanowi tabela akcji, która jest zakodowana jako osobne wartości przecinków, które rejestrują nazwę, mapę „dopasuj / zniszcz” i inne właściwości każdej dostępnej akcji.

Zaczyna się od odczytania minimalnego prawdopodobieństwa sukcesu i mapy. Następnie lokalizuje uciekiniera, usuwa go z mapy i tworzy „stan wyszukiwania” zawierający te informacje. Następnie wykonuje BFS, który wielokrotnie sprawdza następny stan przy najmniejszym wysiłku (upewniając się, że znajdzie optymalne rozwiązanie). Przed rozwinięciem węzła porównuje wysiłek i prawdopodobieństwo sukcesu z poprzednimi węzłami z tą samą mapą i lokalizacją ucieczki i odrzuca się, jeśli już znaleziono lepszą trasę do tego stanu. Jeśli to przeżyje, dodaje się do tabeli „widzialnej”, aby później odrzucić stan. Wszystko zależy od wydajności, a bez niej czynnik rozgałęzienia byłby ogromny. Następnie sprawdza, czy uciekinier jest poza mapą. Jeśli tak, to wygrywa! Śledzi wstecz stan (każdy poprzedni stan jest rejestrowany dla każdego stanu) i buduje plan (w odwrotnej kolejności) przed wyjściem z pętli BFS. W przeciwnym razie próbuje zastosować każdą akcję i dodaje dowolne, które można zastosować dodue kolejka, przed ustawieniem tej kolejki, aby uzyskać najmniejszy wysiłek w następnej iteracji.

Sformatowany i skomentowany kod:

using C=System.Console;
using System.Linq;

// ascii
//   32
// ! 33
// = 61
// . 46
// * 42
// # 35
// | 124
// 0 48

class S // SearchState
{
    string M, // map
        N=""; // plan
    int x, // pos x
        y, // pos y
        E, // effort
        c; // crouching?
    decimal P=1; // chance (Probability)

    static void Main()
    {
        int W=0, // map width
            H=0, // map height
            x, // various temps
            i, // local x
            j, // local y
            k, // position in match/smash map
            X, // s.x
            Y, // s.y

            // action loop
            f, // T idx
            m, // A idx, action mirror (direction)

            P=int.Parse(C.ReadLine()); // probability of success constraint

        string l, // line, Act 'block' params, map hash, match pairs; all sorts!
            M="", // initial map
            B, // name of action
            R="There is no hope!"; // result string

        // read map
        for(;(l=C.ReadLine())!=null; // while there is input to read
            H++,M+=l) // increment height, and append to M
            W=l.Length; // record width

        // detect the escapee
        x=M.IndexOf("|");

        // create first state, and add it to Due list
        var D=new[]{new S{M=M,x=x%W,y=x/W}}.ToList();

        // 'seen' table, stores all the states we've been in which looked similar
        for(var N=D.ToDictionary(s=>R,s=>D); // these values are meaningless (and necessarily can't interfere), we just use it to save having to spec the type
            D.Count>0; // keep going until we run out of states to expand (-> no escape)
            D.Sort((z,w)=>z.E-w.E)) // enforce Breadth First Search
        {
            // get next State to expand, and remove it from Due
            S s=D[f=0];
            D.Remove(s);

            // retrieve or create seen list
            var n=N[l=s.x+s.M+s.y+s.c]= // store it, and cache it, l is 'hash', containing map and escapee state
                N.ContainsKey(l)? // already got a seen list for ths map?
                N[l]: // then use it!
                new S[0].ToList(); // otherwise create a new (empty) one

            // perf: only proceed if we havn't seen this map with better Effort and Chance yet
            if(n.All(o=>o.P<s.P|o.E>s.E))
            {
                // record that we have been seen
                n.Add(s);
                X=s.x;
                Y=s.y;

                if((X|Y|-X/W-Y/H)<0) // check if we our outside the bounds - this took 2.5hour to write. 1 byte.
                { // quit if both are positive or both are negative
                    // freedom
                    R="Required Effort: "+s.E+s.N;

                    // finished
                    break;
                }

                // [Crouch,Effort,dx,dy,Probability],Name,MatchSmash (first 10 are mirrors)
                // 0110d,Step,*** * #*,
                // 0110d,Climb off,=** * =*,
                // 3310d,Shuffle,***** #*,
                // 2:1/_,Clamber Up,*** *##*,
                // 0420_,Short Jump,****  *  #**,
                // 0730K,Long Jump,*****   *   #***,
                // 0<1/Z,High Jump,  * **#*,
                // 0D20P,Put your back into it!,****! *! #**,
                // 0800Z,Punch,***!**#*,
                // 0800U,Kick,*****!#*,
                // 0001d,Drop,*** ,
                // 1001d,Drop (Stand),*** ,
                // 2200d,Crouch,***#,
                // 1400d,Stand,* *#,
                // 020/d,Climb Up,=***,
                // 0800Z,Stamp,***!

                // attempt to expand this node with every action
                for(var A="0110d,Step,*** * #*,0110d,Climb off,=** * =*,3310d,Shuffle,***** #*,2:1/_,Clamber Up,*** *##*,0420_,Short Jump,****  *  #**,0730K,Long Jump,*****   *   #***,0<1/Z,High Jump,  * **#*,0D20P,Put your back into it!,****! *! #**,0800Z,Punch,***!**#*,0800U,Kick,*****!#*,0001d,Drop,*** ,1001d,Drop (Stand),*** ,2200d,Crouch,***#,1400d,Stand,* *#,020/d,Climb Up,=***,0800Z,Stamp,***!".Split(','); // Act string
                    f<26;) // read A into T // (cycle over first 10 twice, making them mirrors)  (very convieniently, 3*16==48=='0'==x!)
                {
                    // 'parse' next action
                    l=A[k=f*3%48]; // [Effort,Crouch,dx,dy,Probability]
                    B=A[++k]+(f>15?" Right":f>9?"":" Left"); // action name
                    M=A[++k]; // Match and Smash table (4x?, escapee at 0,2, #: solid, !: smashable (and is smashed), .: empty,  : don't care, =: climable)
                    //c=l[1]-48; // crouching transition (0: standing -> standing, 1: crouching -> standing, 2: standing -> crouching, 3: crouching -> crouching)
                    m=f++/16*2-1;

                    // this will be the new map
                    var Q=s.M.ToArray();

                    // K is whether we are allowed to apply this action
                    var K=s.P*l[4]>=P& // within chance limit
                        s.c==l[k=0]%2; // crouching matches

                    // compare the map to the Match/Smash map, to make sure we can apply this transform (and smash any ! we meet)
                    for(j=Y-3;j++<=Y;) // for the 4 rows
                        for(i=X;i!=X+m*M.Length/4;i+=m) // for each column (a.M has height 4, but variable width)
                            if((K&= // K still true?
                                "==  *!!##*!*=*|*| o*o ".Contains(""+ // check for an allowed pairing (cache pairing in M) (this includes the escapee, much cheaper to do this than remove him)
                                    ((i|j)>=0&j<H&i<W?Q[x=j*W+i]:' ') // we are within bounds and match, we are out of bounds (empty)
                                    +M[k])) // char from MatchSmash map
                                &M[k++]==33) // if it is destructible ('!' == 33)
                                Q[x]=' '; // then blank it out (x is necessarily set by the cell check)

                    if(K) // if K holds
                        D.Add(new S{M=new string(Q),N=s.N+"\n"+B, // assemble plan as we go (this will chew up memory, but none of the problems are big enough for it to matter)
                            x=X+l[2]%48*m,y=Y+l[3]-48,c=l[0]/50,E=s.E+l[1]-48,P=s.P*l[4]/100}); // add the resulting state to Due
                }
            }
        }

        C.Write(R);
    }
}