Reto

Dada una matriz binaria y una cadena binaria, determine si esa cadena binaria se puede encontrar comenzando en cualquier punto de la matriz y moviéndose en cualquier dirección en cualquier punto posterior para formar la cadena binaria. Es decir, ¿se puede encontrar la cadena doblada sin embargo dentro de la matriz?

La cadena solo se puede plegar a 90 grados o 180 grados (conexiones de borde; Manhattan Distancia 1) y no puede solaparse en ningún punto.

Ejemplo

Tomemos el siguiente ejemplo:

Matrix:

010101
111011
011010
011011

Snake: 0111111100101

Este es un caso de prueba de verdad. Podemos ver la serpiente doblada en la siguiente posición:

0-1 0 1 0 1
  |
1 1 1-0 1 1
  | | |   |
0 1 1 0-1-0
  | |
0 1-1 0 1 1

Reglas

• Se aplican lagunas estándar
• Puede tomar la longitud de la cadena y el ancho y alto de la matriz como entrada si lo desea
• Puede tomar la matriz binaria y la cadena binaria como una cadena multilínea / matriz de cadenas / cadena unida a nueva línea / cualquier otra cadena unida y una cadena
• Puede tomar las dimensiones como una matriz plana en lugar de varios argumentos
• Su programa debe finalizar para cualquier matriz de 5 x 5 con cualquier cadena de hasta 10 en menos de un minuto

Limitaciones

• La matriz no es necesariamente cuadrada
• La cadena no estará vacía.
• La cadena puede ser de longitud 1
• La cadena no contendrá más cuadrados de los disponibles (es decir, len(string) <= width(matrix) * height(matrix)

Casos de prueba

Verdad

01010
10101
01010
10101
01010

0101010101010101010101010



01110
01100
10010
10110
01101

011111000110100



0

0



10
01

1010



100
010
001

100010001

Falsa

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 bytes

• Guardado cuatro bytes mediante la sustitución -1con Hy la eliminación de una operación de rebanado ( [:]).
• Guardado siete bytes gracias a Halvard Hummel ; eliminando otra operación de corte ( [:]), usando la asignación de múltiples objetivos para dar un valor a una entrada visitada v not in "01"( S=S[1:];M[y][x]=H;-> S=M[y][x]=S[1:];) y cambiando de un ternario if / else a un simple lógico o ( any(...)if S else 1-> not S or any(...)).
• Si de alguna manera amplía su definición de veracidad y falsey , podría permitir esta solución de 257 bytes . Provoca una excepción ( ZeroDivisionError) cuando se encuentra la serpiente y devuelve una lista vacía ( []) cuando no se encuentra ninguna serpiente, que son dos comportamientos distintos.
• Guardado catorce bytes gracias a user202729 ; Golfing dos copias profundas de la matriz
• Guardado un byte; Golfed not S ora 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])

Pruébalo en línea!

Explicación

Función Lambda que toma la matriz como una lista bidimensional de cadenas (ya sea "0"o "1"), la serpiente como una lista unidimensional y las dimensiones de la matriz como dos enteros.
La función lambda busca en la matriz entradas que coincidan con el primer elemento de la serpiente. Por cada coincidencia encontrada, se llama Hcon una copia profunda de la matriz, sin copia de la serpiente, las dimensiones de la matriz y la posición de la coincidencia.

Cuando Hse llama, elimina Sla primera entrada y establece la entrada de matriz de la posición dada en algo más que "0", "1". Si S'length es cero, vuelve True; Como se llama recursivamente, la serpiente fue encontrada en algún lugar de la matriz.
Si S'la longitud no es cero, recorre las cuatro direcciones cardinales, comprueba si esa posición está en la matriz, compara el elemento de la matriz' en esa posición con el primer elemento Sy, si coincide, se llama recursivamente.
HLos valores de retorno se canalizan hacia arriba en los marcos de la pila, siempre verificando si al menos una función encontró una posible serpiente.

Salida formateada

He aumentado mi programa para que también muestre la ruta que desliza la serpiente (si hay una). Utiliza el mismo diseño de salida ASCII que la pregunta. Enlace TIO .

JavaScript (ES6), 138 134

No es tan diferente de @ Neil's, pero ¿qué más podría ser?

Entrada: matriz como una cadena de varias líneas, cadena binaria, ancho (sin contar la nueva línea)

NB: la lógica en la función recursiva restá algo invertida para guardar un par de bytes

(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))

Menos golf

(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))
)

Prueba

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 bytes

(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)))

Toma la matriz como una cadena delimitada por una nueva línea, la serpiente como una cadena y el ancho (como un entero). Basada en la respuesta de @ JonathanFrech.

Mathematica, 180 156 141 153 138 136 104 bytes

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

Entrada de ejemplo

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

Explicación

1. GridGraph@{##4}es un Graphobjeto para una cuadrícula de vértices con vértices adyacentes conectados por bordes, con dimensiones {##4}, es decir, {#4,#5}o {width,height}.
2. Nos iterar sobre todos los vértices de partida x(numeradas 1a 1##4 = width*height), todos los vértices que termina y, y todos los caminos pde longitud a lo sumo #3de xa y.
3. Para cada ruta, ""<>Part[Join@@#,p]extrae los caracteres correspondientes de la matriz y los coloca en una cadena.
4. También incluimos la matriz en sí, cuyos caracteres son todas las cadenas de longitud 1 que se pueden encontrar en ella.
5. Vemos si una de estas cadenas coincide s, buscando en todos los niveles porque esta es una lista muy multidimensional que hemos construido.

Nota: Reemplazar #3por {#3-1}in FindPath, de modo que solo encontremos rutas de exactamente la longitud correcta, es una gran mejora en términos de velocidad, pero cuesta 4 bytes más.

-24 bytes: tomar dimensiones de cosas como entrada

-15 bytes: utilizando StringParty StringJoincorrectamente

+12 bytes: arreglando el caso de longitud 1

-15 bytes: ...

-2 bytes: tomar el tamaño de la matriz como entrada como una matriz

-32 bytes: el uso Tablepara iterar sobre la ruta nos permite evitar el uso Function, y el uso MemberQ[...,s,All]nos permite pegar la matriz en la mesa cuando se trata de serpientes de longitud 1.

C # (.NET Core) , 346 341 336 302 297 bytes

(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;}}

Pruébalo en línea!

5 bytes ahorrados jugando al golf el pincremento

5 bytes guardados tomando la longitud de la serpiente y comenzando en su cola, y eliminando un espacio innecesario

34 bytes guardados leyendo el desafío correctamente y viendo que puedo ver la altura y el ancho de la matriz

5 bytes guardados, el caso de prueba de un solo elemento falló y la solución fue beneficiosa

Sin golf

(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 bytes

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)}}}

Embellecido

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) } }
}

Prueba

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")
}