Napisz funkcję (wykorzystującą jak najmniej bajtów), która pobiera dwuwymiarową tablicę dowolnej liczby kolumn i wierszy, w której:
0
reprezentuje pusty blok,1
reprezentuje blok węża.
Funkcja musi zwracać liczbę możliwych ścieżek, które przebył wąż.
Przykład 1:
Wkład:
[
[1,1,1,1,1],
[0,0,0,0,1],
[0,0,0,0,1],
]
Wydajność: 2
W powyższym przykładzie funkcja zwróci, 2
ponieważ odpowiedź jest jedna z:
Przykład 2:
Wkład:
[
[1,1,1,1],
[0,0,1,1],
[0,0,1,1],
]
Wydajność: 6
W tym przykładzie funkcja zwróci, 6
ponieważ odpowiedź jest jedna z:
Uwaga:
Oceniając dane wejściowe, możesz założyć, że:
- Tablice reprezentujące kolumny zawsze będą miały takie same rozmiary (więc tablice są prostokątne);
- Istnieje co najmniej 1 poprawna ścieżka;
- Wąż nie może przejść przez krawędzie (co może się zdarzyć w niektórych wersjach węża);
- Wąż zawsze będzie miał co najmniej 2 bloki;
- Wąż nie może poruszać się po przekątnej;
- Ścieżki są skierowane. (więc dwie ścieżki kończące się w różnych pozycjach, ale poza tym wyglądające dokładnie tak samo, nie są tą samą ścieżką, sumują się do całości)
code-golf
grid
binary-matrix
Adelina
źródło
źródło
[[0,0,1,1],[0,0,1,1],[0,0,1,1]]
. Większość odpowiedzi daje 16, ale jedna daje 15.Odpowiedzi:
Wolfram Language (Mathematica) , 16 + 83 = 99 bajtów
Instrukcja importu biblioteki (16 bajtów):
Rzeczywista treść funkcji (83 bajty):
Wypróbuj online!
Zauważ, że w pytaniu pytaj tylko o liczbę ścieżek hamiltonowskich na wykresie.
Jednak (z jakiegoś powodu)
HamiltonianPath
funkcja tak naprawdę nie działa z ukierunkowanym wykresem ( przykład ). Użyłem więc obejścia opisanego w tym pytaniu Mathematica.SE :True
), który jest połączony ze wszystkimi innymi wierzchołkami.Wykres jest konstruowany przy użyciu
MakeGraph
(irytujące, że nie ma bezpośrednio równoważnego wbudowanego), przy użyciu funkcji boolean##||Norm[#-#2]==1&
, która zwraca,True
jeśli tylko jeden z argumentów jestTrue
lub odległość między dwoma wierzchołkami jest1
.Tr[1^x]
nie można użyć zamiastLength@x
i<2
nie można użyć zamiast==1
.HamiltonianPath
można użyć, jeśli wykres nie jest przekierowany, a ciało funkcji zajmuje 84 bajty (dokładnie 1 bajt więcej niż bieżące przesłanie):Wypróbuj online!
źródło
JavaScript (ES6),
154134 bajtówWypróbuj online!
W jaki sposób?
metoda
Zaczynając od każdej możliwej komórki, wypełniamy matrycę, usuwając wszystkie komórki po drodze. Ilekroć macierz nie zawiera więcej 1 , zwiększamy liczbę n możliwych ścieżek.
Każda ważna ścieżka jest liczona 4 razy ze względu na kierunek wybrany w ostatniej komórce, co w rzeczywistości nie ma znaczenia. Dlatego końcowy wynik to n / 4 .
Funkcja rekurencyjna
Zamiast wywoływać funkcję rekurencyjną g () z wywołania zwrotnego drugiej mapy () w ten sposób ...
... możemy zdefiniować rekurencyjnej funkcji g () bezpośrednio jako zwrotnego z mapy () :
Pomimo dość długiej formuły
y=1/y?y:Y
wymaganej do ustawienia początkowej wartości y , pozwala to zaoszczędzić 2 bajty ogółem.Skomentowany kod
źródło
Galaretka ,
1211 bajtówWypróbuj online!
Wyjaśnienie.
źródło
§ỊML
zamiast§ỊP€S
zapisać bajt - myślę, że powinien działać?§ÐṂL
który jest trochę szybszy.Python 2 ,
257246241234233227214210 bajtówWypróbuj online!
Zapisano
źródło
w
ih
Python 2, 158 bajtów
Wypróbuj online!
źródło
Haskell ,
187155 bajtówWypróbuj online!
źródło