Wyzwanie
Biorąc pod uwagę macierz binarną i ciąg binarny, określ, czy ten ciąg binarny można znaleźć, zaczynając w dowolnym punkcie macierzy i poruszając się w dowolnym kierunku w dowolnym kolejnym punkcie, tworząc ciąg binarny. To znaczy, czy można znaleźć zwinięty sznurek wewnątrz matrycy?
Sznurek można złożyć tylko pod kątem 90 stopni lub 180 stopni (połączenia krawędzi; Manhattan Odległość 1) i nie może zachodzić na siebie w żadnym punkcie.
Przykład
Weźmy następujący przykład:
Matrix:
010101
111011
011010
011011
Snake: 0111111100101
To jest prawdziwy przypadek testowy. Widzimy węża złożonego w następującej pozycji:
0-1 0 1 0 1
|
1 1 1-0 1 1
| | | |
0 1 1 0-1-0
| |
0 1-1 0 1 1
Zasady
- Obowiązują standardowe luki
- Możesz wziąć długość łańcucha oraz szerokość i wysokość matrycy jako dane wejściowe, jeśli chcesz
- Możesz wziąć macierz binarną i ciąg binarny jako ciąg wieloliniowy / tablicę ciągów / ciąg połączony z nową linią / ciąg połączony z czymkolwiek innym i ciąg
- Możesz wziąć wymiary jako płaską tablicę zamiast kilku argumentów
- Twój program musi zakończyć się dla dowolnej matrycy 5 x 5 z dowolnym łańcuchem o długości do 10 w niecałą minutę
Ograniczenia
- Macierz niekoniecznie jest kwadratowa
- Ciąg nie będzie pusty
- Ciąg może mieć długość-1
- Ciąg nie będzie zawierał więcej kwadratów niż dostępnych (to znaczy,
len(string) <= width(matrix) * height(matrix)
Przypadki testowe
Prawda
01010
10101
01010
10101
01010
0101010101010101010101010
01110
01100
10010
10110
01101
011111000110100
0
0
10
01
1010
100
010
001
100010001
Falsy
00000
00000
00000
00000
00000
1
10101
01010
10101
01010
10101
11
100
010
001
111
10001
01010
00100
01010
10001
1000100010001000101010100
code-golf
decision-problem
binary-matrix
HyperNeutrino
źródło
źródło
Odpowiedzi:
Python 2 ,
275271264249 bajtów-1
zH
i usuwanie jednej operacji krojenia ([:]
).[:]
), użycie przypisania do wielu celów, aby nadać odwiedzonemu wpisowi wartośćv not in "01"
(S=S[1:];M[y][x]=H;
->S=M[y][x]=S[1:];
) i przełączenie z trójskładnikowego if / else na prosty logiczny lub (any(...)if S else 1
->not S or any(...)
).ZeroDivisionError
) po znalezieniu węża i zwraca pustą listę ([]
), gdy nie można znaleźć węża, które są dwoma odrębnymi zachowaniami.not S or
w golfa doS<[1]or
~S==[]or
.Wypróbuj online!
Wyjaśnienie
Funkcja Lambda, która przyjmuje macierz jako dwuwymiarową listę ciągów (albo
"0"
lub"1"
), wąż jako jednowymiarową listę i wymiary macierzy jako dwie liczby całkowite.Funkcja lambda przeszukuje macierz w poszukiwaniu wpisów pasujących do pierwszego elementu węża. Przy każdym znalezionym dopasowaniu wywołuje
H
z głęboką kopią macierzy, bez kopii węża, wymiarów macierzy i pozycji dopasowania.Kiedy
H
jest wywoływany, usuwaS
pierwszy wpis i ustawia wpis macierzy danej pozycji na coś innego niż"0", "1"
. JeśliS
„długość wynosi zero, zwracaTrue
; jak to się nazywa rekurencyjnie, wąż został znaleziony gdzieś w matrycy.Jeśli
S
„długość jest różna od zera, pętla przechodzi przez cztery główne kierunki, sprawdza, czy ta pozycja znajduje się w macierzy, porównuje element macierzy w tej pozycji z pierwszym elementemS
i - jeśli pasuje - wywołuje się rekurencyjnie.H
Zwracane wartości są umieszczane w ramkach stosu, zawsze sprawdzając, czy przynajmniej jedna funkcja znalazła możliwego węża.Sformatowane dane wyjściowe
Rozszerzyłem swój program, aby wyświetlał również ścieżkę, którą wąż ślizga się (jeśli taka istnieje). Używa tego samego projektu wyjścia ASCII co pytanie. Łącze TIO .
źródło
m[:]for
~>m*1for
? Może działać.JavaScript (ES6),
138134Nie różni się tak bardzo od @ Neila, ale co jeszcze może być?
Dane wejściowe: macierz jako ciąg wieloliniowy, ciąg binarny, szerokość (nie licząc nowego wiersza)
Uwaga: logika funkcji rekurencyjnej
r
jest nieco odwrócona, aby zaoszczędzić kilka bajtówMniej golfa
Test
źródło
JavaScript (ES6), 149 bajtów
Traktuje macierz jako ciąg rozdzielany znakiem nowej linii, wąż jako ciąg i szerokość (jako liczbę całkowitą). Luźno oparty na odpowiedzi @ JonathanFrech.
źródło
Mathematica,
180156141153138136 136bajtówPrzykładowe dane wejściowe
Wyjaśnienie
GridGraph@{##4}
jestGraph
obiektem dla siatki wierzchołków z sąsiadującymi wierzchołkami połączonymi krawędziami, o wymiarach{##4}
- to znaczy{#4,#5}
lub{width,height}
.x
(ponumerowanych1
do1##4 = width*height
), wszystkich końcowych wierzchołkachy
i wszystkich ścieżkachp
długości#3
odx
doy
.""<>Part[Join@@#,p]
wyodrębnia odpowiednie znaki macierzy i umieszcza je w ciągu.s
, szukając na wszystkich poziomach, ponieważ jest to bardzo wielowymiarowa lista, którą zbudowaliśmy.Uwaga: Zastąpienie
#3
przez{#3-1}
inFindPath
, abyśmy znaleźli ścieżki tylko o odpowiedniej długości, jest ogromną poprawą pod względem prędkości - ale kosztuje 4 dodatkowe bajty.-24 bajty: przyjmowanie wymiarów rzeczy jako danych wejściowych
-15 bajtów: używa
StringPart
iStringJoin
poprawnie+12 bajtów: naprawianie skrzynki o długości 1
-15 bajtów: ...
-2 bajty: przyjmowanie rozmiaru macierzy jako danych wejściowych jako tablicy
-32 bajtów: użycie
Table
iteracji po ścieżce pozwala nam uniknąć użyciaFunction
, a użycieMemberQ[...,s,All]
pozwala nam po prostu przykleić matrycę do stołu, gdy mamy do czynienia z wężami o długości 1.źródło
C # (.NET Core) ,
346341336302297 bajtówWypróbuj online!
5 bajtów zaoszczędzonych dzięki golfowi
p
przyrostu5 bajtów zaoszczędzonych poprzez pobranie długości węża i rozpoczęcie od jego ogona oraz usunięcie niepotrzebnego miejsca
34 bajty zapisane dzięki prawidłowemu odczytaniu wyzwania i zobaczeniu, że mogę wziąć wysokość i szerokość matrycy
Zapisano 5 bajtów, test pojedynczego elementu nie powiódł się, a poprawka była korzystna
Bez golfa
źródło
if(...)return true;
->return ...;
.b[y,x]
w pewnym momencie należy go zresetować. (Przepraszam również za błędną pisownię twojego imienia w mojej odpowiedzi.)if(N(x,y,0)>0)return 0<1;
; pierwszy występreturn
.Kotlin , 413 bajtów
Upiększony
Test
źródło