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

Python 2 , 275 271 264 249 bajtów

• Zapisane cztery bajty zastępując -1z Hi usuwanie jednej operacji krojenia ( [:]).
• Zaoszczędzono siedem bajtów dzięki Halvardowi Hummelowi ; usunięcie kolejnej operacji dzielenia ( [:]), 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(...)).
• Jeśli nieco rozszerzysz swoją definicję prawdy i falseya , możesz pozwolić na to rozwiązanie o długości 257 bajtów . Zgłasza wyjątek ( ZeroDivisionError) po znalezieniu węża i zwraca pustą listę ( []), gdy nie można znaleźć węża, które są dwoma odrębnymi zachowaniami.
• Zaoszczędzono czternaście bajtów dzięki user202729 ; gra w golfa w dwóch głębokich kopiach
• Zapisano bajt; grał not S orw golfa do S<[1]or~ S==[]or.

lambda M,S,w,h:any(H(eval(`M`),S,w,h,x,y)for y in range(h)for x in range(w)if S[0]==M[y][x])
def H(M,S,w,h,x,y):S=M[y][x]=S[1:];return S<[1]or any(H(eval(`M`),S,w,h,x+X,y+Y)for X,Y in[(~0,0),(1,0),(0,~0),(0,1)]if~0<x+X<w>0<=y+Y<h!=S[0]==M[y+Y][x+X])

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 Hz głęboką kopią macierzy, bez kopii węża, wymiarów macierzy i pozycji dopasowania.

Kiedy Hjest wywoływany, usuwa Spierwszy wpis i ustawia wpis macierzy danej pozycji na coś innego niż "0", "1". Jeśli S„długość wynosi zero, zwraca True; 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 elementem Si - jeśli pasuje - wywołuje się rekurencyjnie.
HZwracane 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 .

JavaScript (ES6), 138 134

Nie 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 rjest nieco odwrócona, aby zaoszczędzić kilka bajtów

(m,s,w)=>[...m].some((c,p,m,r=(p,o)=>s[m[p]=r,o]&&([~w,-~w,1,-1].every(d=>m[d+=p]!=s[o]||r(d,o+1))&&(m[p]=s[o-1])))=>c==s[0]&&!r(p,1))

Mniej golfa

(m,s,w)=>(
  m=[...m],
  r= (p, o) => 
    (m[p] = -w, s[o])
    && (
         [~w, -~w, 1, -1].every( d =>
            m[d+=p] != s[o] || r(d, o+1)
         )
         && (m[p]=s[o-1])
    ),
  m.some((c,p) =>c == s[0] && !r(p,1))
)

Test

var F=
(m,s,w)=>[...m].some((c,p,m,r=(p,o)=>s[m[p]=r,o]&&([~w,-~w,1,-1].every(d=>m[d+=p]!=s[o]||r(d,o+1))&&(m[p]=s[o-1])))=>c==s[0]&&!r(p,1))

// this slightly modified version tracks the path
var Mark=
(m,s,w)=>(m=[...m]).some((c,p,m,r=(p,o)=>s[m[p]=-o,o]&&([~w,-~w,1,-1].every(d=>m[d+=p]!=s[o]||r(d,o+1))&&(m[p]=s[o-1])))=>c==s[0]&&!r(p,1))
?m.map((c,p)=>c<-1?'.───│┘└.│┐┌.│'[((m[p-1]-c)**2<2)+((m[p+1]-c)**2<2)*2+((m[p+~w]-c)**2<2)*4+((m[p-~w]-c)**2<2)*8]:c<0?'*':c).join``:''

function go()
{
  O.textContent =F(M.value, S.value, M.value.search('\n'))+'\n\n'
  +Mark(M.value, S.value, M.value.search('\n'))
}

go()

#M {width:100px; height:100px }

<textarea id=M>010101
111011
011010
011011</textarea><br>
<input id=S value='0111111100101' oninput='go()'>
<button onclick='go()'>go</button>
<pre id=O></pre>

JavaScript (ES6), 149 bajtów

(m,s,w)=>[...m].some((c,i)=>c==s[0]&&g(m,s,i),g=(m,s,i)=>!(s=s.slice(1))||[~w,-1,1,-~w].some(o=>m[o+=i]==s[0]&&g(m.slice(0,i)+' '+m.slice(i+1),s,o)))

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.

Mathematica, 180 156 141 153 138 136 136 bajtów

MemberQ[#|Table[""<>Part[Join@@#,p],{x,1##4},{y,1##4},{p,FindPath[GridGraph@{##4},x,y,#3,All]}],#2,All]&

Przykładowe dane wejściowe

[{{"1","1","1","1","1"},{"0","0","0","0","0"}},"10011001",8,5,2]

Wyjaśnienie

1. GridGraph@{##4}jest Graphobiektem 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}.
2. Iterujemy po wszystkich początkowych wierzchołkach x(ponumerowanych 1do 1##4 = width*height), wszystkich końcowych wierzchołkach yi wszystkich ścieżkach pdługości #3od xdo y.
3. Dla każdej takiej ścieżki ""<>Part[Join@@#,p]wyodrębnia odpowiednie znaki macierzy i umieszcza je w ciągu.
4. Uwzględniamy również samą macierz, której znakami są wszystkie ciągi długości 1, które można w niej znaleźć.
5. Widzimy, czy jeden z tych ciągów pasuje s, szukając na wszystkich poziomach, ponieważ jest to bardzo wielowymiarowa lista, którą zbudowaliśmy.

Uwaga: Zastąpienie #3przez {#3-1}in FindPath, 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 StringParti StringJoinpoprawnie

+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 Tableiteracji po ścieżce pozwala nam uniknąć użycia Function, a użycie MemberQ[...,s,All]pozwala nam po prostu przykleić matrycę do stołu, gdy mamy do czynienia z wężami o długości 1.

C # (.NET Core) , 346 341 336 302 297 bajtów

(m,h,w,s,l)=>{for(int y=0;y<h;y++)for(int x=0;x<w;x++)if(N(x,y,l-1))return 0<1;return 1<0;bool N(int x,int y,int p){if(p<0)return 0<1;if(y<0|x<0|y==h|x==w||m[y,x]>1||s[p]!=m[y,x])return 1<0;int g=m[y,x];m[y,x]=2;if(N(x,y-1,--p)||N(x-1,y,p)||N(x,y+1,p)||N(x+1,y,p))return 0<1;m[y,x]=g;return 1<0;}}

Wypróbuj online!

5 bajtów zaoszczędzonych dzięki golfowi pprzyrostu

5 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

(m,h,w,s,l)=>{
    // Go through every potential starting point
    for(int y=0; y<h; y++)
        for(int x=0; x<w; x++)
            if(N(x,y,l-1)) // start the recursive steps
                return 0<1; // return true if N returns true, otherwise check the next element

    return 1<0; // return false as the snake doesn't fit into the matrix

    // C#7 local function in a Func
    bool N(int x, int y, int p)
    {
        // if there is no more snake to fit return true
        if(p<0)
            return 0<1;

        // if m element has part of the snake or 
        // snake part doesn't match matrix element then return false
        if(y<0 | x<0 | y==h | x==w || m[y,x]>1 || s[p] != m[y,x])
            return 1<0;

        // hold the current matrix element
        int g=m[y,x];
        // set the current matrix element to 2 to indicate it has a part of the snake
        m[y,x]=2;

        // check each of the four neighbours and recurse down that neighbour 
        // except if they are outside the matrix
        if(N(x,y-1,--p) ||
           N(x-1,y,p) ||
           N(x,y+1,p) ||
           N(x+1,y,p))
               return 0<1; // return true if remainder of the snake fits into the matrix

        // if snake doesn't fit then set the matrix element as not having part of the snake
        m[y,x]=g;
        // return false to indicate this neighbour direction doesn't fit the snake
        return 1<0; 
    }
}

Kotlin , 413 bajtów

var x:(Array<Array<Char>>,String)->Boolean={b,s->fun f(s:String,x:Int,y:Int):Boolean{if(b[x][y]!=s[0])
return 0>1
if(s.length<2)
return 1>0
val v=b[x][y]
b[x][y]='Z'
try{return(-1..1).map{x+it}.flatMap{t->(-1..1).map{y+it}.map{t to it}}.filter{(X,Y)->(x-X)*(x-X)+(y-Y)*(y-Y)==1&&X in b.indices&&Y in b[0].indices&&f(s.substring(1),X,Y)}.any()}finally{b[x][y]=v}}
b.indices.any{x->(0..b[0].size-1).any{f(s,x,it)}}}

Upiększony

var x: (Array<Array<Char>>, String) -> Boolean = { b, s ->
    fun f(s: String, x: Int, y: Int): Boolean {
        if (b[x][y] != s[0])
            return 0 > 1
        if (s.length < 2)
            return 1 > 0
        val v = b[x][y]
        b[x][y] = 'Z'
        try {
            return (-1..1).map{ x + it }
                    .flatMap { t -> (-1..1).map{y+it}.map { t to it } }
                    .filter { (X, Y) ->
                        (x - X)*(x - X) + (y - Y)*(y - Y) == 1 &&
                                X in b.indices && Y in b[0].indices &&
                                f(s.substring(1), X, Y) }
                    .any()
        } finally {
            b[x][y] = v
        }
    }
    b.indices.any { x -> (0..b[0].size - 1).any { f(s, x, it) } }
}

Test

var x:(Array<Array<Char>>,String)->Boolean={b,s->fun f(s:String,x:Int,y:Int):Boolean{if(b[x][y]!=s[0])
return 0>1
if(s.length<2)
return 1>0
val v=b[x][y]
b[x][y]='Z'
try{return(-1..1).map{x+it}.flatMap{t->(-1..1).map{y+it}.map{t to it}}.filter{(X,Y)->(x-X)*(x-X)+(y-Y)*(y-Y)==1&&X in b.indices&&Y in b[0].indices&&f(s.substring(1),X,Y)}.any()}finally{b[x][y]=v}}
b.indices.any{x->(0..b[0].size-1).any{f(s,x,it)}}}

data class Test(val board: String, val snake: String, val output: Boolean)

val tests = listOf(
        Test("""01010
            |10101
            |01010
            |10101
            |01010""", "0101010101010101010101010", true),
        Test("""01110
            |01100
            |10010
            |10110
            |01101""", "011111000110100", true),
        Test("""0""", "0", true),
        Test("""10
            |01""", "1010", true),
        Test("""100
            |010
            |001""", "100010001", true),
        Test("""00000
            |00000
            |00000
            |00000
            |00000""", "1", false),
        Test("""10101
            |01010
            |10101
            |01010
            |10101""", "11", false),
        Test("""100
            |010
            |001""", "111", false),
        Test("""10001
            |01010
            |00100
            |01010
            |10001""", "1000100010001000101010100", false)
)

fun main(args: Array<String>) {
    tests.filter {(board, snake, expected) ->
        val boardR = board.trimMargin().lines().map { it.toCharArray().toTypedArray() }.toTypedArray()
        val result = x(boardR, snake)
        result != expected
    }.forEach { throw AssertionError(it) }
    println("Test Passed")
}