Twój przyjaciel dał ci wskazówki do najlepszej restauracji w mieście. To seria skrętów w lewo i w prawo. Niestety zapomnieli wspomnieć o tym, jak długo trzeba iść prosto między tymi turami. Na szczęście masz mapę ulic ze wszystkimi restauracjami. Może możesz dowiedzieć się, o którą restaurację chodziło?
Wkład
Mapa jest podawana jako prostokątna siatka znaków ASCII. .
Jest to droga, #
jest budynek, A
w celu Z
są różne restauracje. Zaczynasz w lewym górnym rogu, kierując się na wschód. Przykład:
.....A
.#.###
B....C
##.#.#
D....E
##F###
Instrukcje twojego przyjaciela będą podane jako (potencjalnie pusty) ciąg znaków lub lista znaków zawierających L
s i R
s.
Wydajność
Możesz przejść dowolną ścieżką, która odpowiada skrętom w lewo i w prawo w ciągu wejściowym, pod warunkiem, że zrobisz co najmniej jeden krok do przodu przed każdym z nich, a także na końcu. W szczególności oznacza to, że jeśli ciąg zaczyna się od R
, nie możesz natychmiast udać się na południe w lewej kolumnie. Oznacza to również, że nie możesz obrócić się o 180 ° na miejscu.
Nie możesz przechodzić przez budynki lub restauracje, z wyjątkiem tych, do których dotrzesz na końcu. Możesz założyć, że lewy górny róg to .
.
Powinieneś wypisać wszystkie restauracje, do których można dotrzeć z instrukcjami znajomego, w postaci ciągu lub listy.
Możesz założyć, że instrukcje doprowadzą do co najmniej jednej restauracji. Np. Singiel L
byłby nieprawidłowy dla powyższej mapy.
Kilka przykładów powyższej mapy:
<empty> A
R F
RR B,D
RL C,E
RLRL E
RLLR C
RLLL B
RLRR D
RLRRRR A,C
RLLLRLL B
Zwróć uwagę, że R
to nie osiąga B
.
Możesz napisać program lub funkcję, pobierając dane wejściowe przez STDIN (lub najbliższą alternatywę), argument wiersza poleceń lub argument funkcji i wypisując wynik przez STDOUT (lub najbliższą alternatywę), wartość zwracaną funkcji lub parametr funkcji (wyjściowej).
Obowiązują standardowe zasady gry w golfa .
Dodatkowe przypadki testowe
Oto większa mapa, dzięki uprzejmości Conora O'Briena (który nieco zmodyfikowałem):
.......Y..........................######
.####.....#.##....##..######....#.###.##
B.........#.##.#..##....##...##.#.#P...#
.#.#####..#.##..#.##....##.#....#.####.#
.#.#...C..#.##...G##..#.##.#....#.#....#
.#.#.#.#..#.####.###.#..##.#....#.#.NO.#
.#.#A#.#..#.##...F###...##.#.##.#......#
.#.###....#.##....##....##.#....###....#
.#.....##...##....##...D##........###R.#
.#.##..##...##E...##..######....####...#
.....X....#.#.....................##S.T#
###########.###########M############...#
#................................###.#.#
#.#########.########.######.#.######.#.#
#......V#.....######.IJ...........##.#.#
#########.###......ZH############L##.#.#
#########.##########.###############.#.#
####K##...##########.#....#..........#.#
####....########U......##...#######Q.#.#
#####################################W.#
A oto kilka wybranych list kierunków i ich oczekiwanych wyników:
<empty> Y
RR B
RLL Y
RLRR B,C,X
RLLLRRR G
RLRLRLRL I,Z
RLLRRRLRRLRR C,D,F,G,Y
RLRRLLRLLLRL B,C,Y
RLLRRLRRRLLLL F,M,N,O,Y
RLRRLLLRRRRLLLL F,M,Y
RLRRLRRRRRRRRRR E,F,Y
RLRRRLLLRLLRRLL M,N,O
RLLRRLRRLRLRLRRLLR E,U
RLRLLRLRRLRRRRRLRL F,G,I,Z
RLLRRLLRLLRRRLRRLLRR W
RLLLRRRLRRLLLLLRLLLLLL D,G,X
RLRLLRLRRLRLRRRLRLLLRR B,C,E,J,X
RLRLRLLLLRLRRRRRRLRLRRLR Y
RLRLRRRLRLLLLRLRRLLLLRLLRRL E,M,X
RLRLLLRRRLLLRLLRLLRLRRLRLRR B,E,F,K
RLRRRLLLLLLLLLLLLLLLRRRRLLL A,B
Pytanie bonusowe: czy istnieje wkład, który powoduje tylko I
lub tylko U
? Jeśli tak, jaka jest najkrótsza taka ścieżka?
źródło
Python 2,
180177168163161158 bajtówParametr
v
to mapa jako ciąg;o
jestLR
ciąg.Mitch Schwartz zapisał
2310partii bajtów. Dzięki!Uratowałem dwa bajty, ustawiając
O={0}
i powrocie`O`[9::5]
, co może nie być bardzo przenośny: zakłada, żehash(0) == 0
, jak sądzę, bo to powoduje, że kolejność elementówrepr(O)
będziei twórcze pocięcie tego sznurka daje mi odpowiedź.
źródło
C ++ 465
C ++ jest bardzo gadatliwy ...
Spróbuję to jeszcze bardziej skrócić. Sugestie są mile widziane.
źródło