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 _
.
x
jest 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.txt
aby 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.txt
lub 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.
źródło
Odpowiedzi:
Perl 5,
142514641481146914851438 bajtówTo 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:mój program przyjąłby: (Uwaga: na końcu musi być dwukropek, ale nie na początku!)
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
Dla zachowania rozsądku, to samo dotyczy nowych linii i kilku komentarzy:
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ć.
źródło
C #,
181414811395 bajtówCo za slog !! Naprawdę jestem z tego zadowolony!
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ć do
due
kolejka, przed ustawieniem tej kolejki, aby uzyskać najmniejszy wysiłek w następnej iteracji.Sformatowany i skomentowany kod:
źródło