¡No debe confundirse con la contraseña Bishop Goodness !

Dada una cadena, responda (verdadero / falso o dos valores consistentes) si constituye una contraseña fuerte contra los obispos .

Una contraseña es segura contra los obispos si es una cadena que consiste en alternar letras (in a-h) y dígitos (in 1-8) de modo que cada par de caracteres se pueda interpretar como un cuadrado en un tablero de ajedrez, y si coloca un peón blanco en cada cuadrado llamado en la contraseña, entonces no hay forma de que un alfil blanco viaje, en cualquier número de movimientos consecutivos, desde cualquier casilla en la primera 1fila ( ) a cualquier casilla en la última 8fila ( ).

Ejemplos

Contraseñas seguras contra los obispos

• a1b1c1d1e1f1g1h1
• a8b8c8d8e8f8g8h8
• a1b2c3d4d5f5f4g3g4h2b5
• h4g4f4e4c4b4a4c3e3
• a1b1c1d1e1f1g1a8b8c8d8e8f8g8
• b4b5d4d5f4f5g3h5

Por ejemplo, a1b1c1d1e1f1g1a8b8c8d8e8f8g8corresponde a la posición y b4b5d4d5f4f5g3h5corresponde a la posición

Contraseñas débiles contra los obispos

• a4c4e4g4g5d6f6e3d2b2 (bien formado pero no fuerte, ¡gracias Jo King por este ejemplo!)
• b1c1d1e1f1g1h1a8b8c8d8e8f8g8 (bien formado pero no fuerte)
• h4g4f4e4c4b4a4c3 (bien formado pero no fuerte)
• d4 (bien formado pero no fuerte)
• b4b5d4d5f4f5g2h5 (bien formado pero no fuerte)
• correct horse battery staple (mal formado)
• 1a1b1c1d1e1f1g8a8b8c8d8e8f8g (mal formado)
• a (mal formado)
• aa (mal formado)

Ruby, 115 182 163 bytes

->s{z=('00'..'99').map{|x|x=~/[09]/||s[(x[1].ord+48).chr+x[0]]};(11..18).map &g=->x{z[x]||[x-11,x-9,x+z[x]=9,x+11].map(&g)};s=~/^([a-h][1-8])*$/&&(z[81,9]-[9])[8]}

Pruébalo en línea!

Retornos 1para fuertes y nilpara débiles. (Los +67 bytes fueron para tener en cuenta el "retroceso").

->s{
 z=                             # this is the board
 ('00'..'99').map{|x|           # coordinates are described as y*10 + x
  x=~/[09]/||                   # truthy if out of bounds...
  s[(x[1].ord+48).chr+x[0]]     # ...or impassable
 }                              # now only the passable squares are falsey
 (11..18).map                   # for each x position at y=1,
  &g=->x{                       # call helper function on that square
   z[x]||                       # if the square is passable (i.e. falsey),
    [x-11,x-9,x+z[x]=9,x+11]    # mark it impassable by setting to 9 (truthy)
     .map(&g)                   # call helper recursively for each neighbor
  }
 s=~/^([a-h][1-8])*$/           # make sure the input was valid,
 &&(z[81,9]-[9])[8]             # and check that the last row was never reached
}

Algunos trucos que se usaron:

• En lugar del rango numérico 0..99, usamos el rango de cadena'00'..'99' para que el número se rellene automáticamente a la izquierda a 2 dígitos y se stringifique. Esto hace que la comprobación fuera de los límites sea muy corta: coincide con la expresión regular /[09]/.

• Dentro de la función auxiliar, mientras que la construcción de la lista de las nuevas coordenadas [x-11, x-9, x+9, x+11], que al mismo tiempo asignamos z[x]a 9en el proceso, que pasa a ser un valor Truthy (marcando la casilla visitado).

• En la última línea, queremos comprobar que la matriz z[81,9]no contiene 9. Hacemos esto eliminando todas las instancias de 9( z[81,9]-[9]), luego preguntando por el noveno elemento de la matriz resultante ( [8]). Como sabemos que la matriz originalmente tenía 9 elementos, si se eliminó alguno, obtendremos nil, mientras que si todos permanecieron, obtendremos el último elemento de la matriz (que siempre es 1).

Python 2 , 330 318 313 309 370 bytes

import numpy as n
b=n.ones([8,8])
q=r=1
s=input()
l=len(s)
def g(x,y=0,p=0):
    if b[y,x]and p<32:
        if y<7:
            if x<7:
                g(x+1,y+1,p+1)
                if y:g(x+1,y-1,p+1)
            if x:
                g(x-1,y+1,p+1)
                if y:g(x-1,y-1,p+1)
        else:global q;q=0
for i in range(l/2):
    x=ord(s[2*i])-97;y=ord(s[2*i+1])-49
    if y>8or y<0 or l%2or x>8or x<0:r=0
    if r:b[7-y,x]=0
map(g,range(8))
print q&r

Pruébalo en línea!

¡Prueba la versión práctica en línea! (el original puede tomar 4 ^ 32 operaciones para verificar completamente, sugiero usar este - el mismo número de bytes)

No es una solución súper corta: no pude descubrir cómo hacer que una versión de la función lambda de g sea más corta que g.

-4 bytes gracias a Quuxplusone

+61 bytes que representan el retroceso (gracias por señalar eso a Jo King y por los consejos de golf)

Pitón 2 , 490 476 474

def f(p):
 a=[set(ord(c)-33 for c in s)for s in"* )+ *, +- ,. -/ .0 / \"2 !#13 \"$24 #%35 $&46 %'57 &(68 '7 *: )+9; *,:< +-;= ,.<> -/=? .0>@ /? 2B 13AC 24BD 35CE 46DF 57EG 68FH 7G :J 9;IK :<JL ;=KM <>LN =?MO >@NP ?O BR ACQS BDRT CESU DFTV EGUW FHVX GW JZ IKY[ JLZ\\ KM[] LN\\^ MO]_ NP^` O_ R QS RT SU TV UW VX W".split()];x=set((ord(p[i+1])-49)*8+ord(p[i])-97 for i in range(0,len(p),2))
 r=set(range(8))-x
 for i in range(99):r=set().union(*[a[c]for c in r])-x
 return all(c<56 for c in r)

Pruébalo en línea!

Esto funciona por "inundación de relleno". Primero creamos una lista ade qué cuadrados son adyacentes a qué otros cuadrados, en sentido obvio. Luego creamos un conjunto xde exclusiones (basadas en la contraseña). Luego inicializamos un conjuntor de cuadrados alcanzables, que comienza como la primera fila (menos cualquier exclusión), y repetidamente "inundamos" hacia afuera desde allí, 99 veces, lo que debería ser más que suficiente. Finalmente, probamos para ver si alguno de los cuadrados en la última fila terminó en nuestro conjunto accesible. Si es así, ¡tenemos una contraseña débil! Si no, tenemos una contraseña segura.

Desventaja, tal vez descalificante (no sé la regla habitual aquí): si la contraseña está mal formada (como "grapa de batería de caballo correcta"), lanzamos una excepción en lugar de devolverla False. ¡Pero siempre devolvemos Truesi la contraseña es segura!

Menos 16 bytes gracias a Jo King. Nos alineamos aen el único lugar donde se usa, y doblamos constantemente algunas matemáticas.

def f(p):
 x=set(ord(p[i])-489+8*ord(p[i+1])for i in range(0,len(p),2));r=set(range(8))-x
 for i in[1]*99:r=set().union(*[[set(ord(k)-33for k in s)for s in"* )+ *, +- ,. -/ .0 / \"2 !#13 \"$24 #%35 $&46 %'57 &(68 '7 *: )+9; *,:< +-;= ,.<> -/=? .0>@ /? 2B 13AC 24BD 35CE 46DF 57EG 68FH 7G :J 9;IK :<JL ;=KM <>LN =?MO >@NP ?O BR ACQS BDRT CESU DFTV EGUW FHVX GW JZ IKY[ JLZ\\ KM[] LN\\^ MO]_ NP^` O_ R QS RT SU TV UW VX W".split()][c]for c in r])-x
 return all(c<56for c in r)

Limpio , 285 bytes

import StdEnv,Data.List
$_[_]=1<0
$a[x,y:l]=case[[u,v]\\u<-[0..7],v<-[0..7]|u==toInt x-97&&v==toInt y-49]of[p]= $[p:a]l;_=1<0
$a _=all(\[_,y]=y<7)(iter 64(nub o\e=e++[k\\[u,v]<-e,p<-[-1,1],q<-[-1,1],k<-[[abs(u+p),abs(v+q)]]|all((<>)k)a&&all((>)8)k])(difference[[e,0]\\e<-[0..7]]a))

$[]

Pruébalo en línea!

$[]se $ :: [[Int]] [Char] -> Boolcompone con el primer argumento, dando \ [Char] -> Bool.

La función funciona al consumir la cadena de dos caracteres a la vez, devolviendo inmediatamente falso si la cadena está en un formato no válido tan pronto como ve la parte no válida. Una vez que la cadena ha sido procesada, coloca un alfil en cada casilla vacía a un lado del tablero y los mueve de todas las formas posibles 64 veces y comprueba si alguna de las posiciones finales está en la fila objetivo.

Wolfram Language (Mathematica) , 339 316 358 353 345 bytes

-23 bytes gracias a @Doorknob.

+42 bytes que representan el retroceso.

p[m_]:=StringPartition[#,m]&;l=Range@8;f[n_]:=Check[w=(8#2+#1-8)&@@@({LetterNumber@#,FromDigits@#2}&@@@(p@1/@p[UpTo@2]@n));g=Graph[Sort/@UndirectedEdge@@@Position[Outer[EuclideanDistance@##&,#,#,1],N@Sqrt@2]&@GraphEmbedding@GridGraph@{8,8}//Union]~VertexDelete~w;c:=#~Complement~w&;m=0;Do[m+=Length@FindPath[g,i,j],{i,c@l},{j,c[l+56]}];m==0,0>1]

Pruébalo en línea!

Reescribí la mayor parte de esto para dar cuenta del retroceso, creo que puede haber una manera más fácil de definir el gráfico g, Mathematica tiene GraphData[{"bishop",{8,8}}]cuál es el gráfico de todos los movimientos que un obispo puede hacer en un tablero de ajedrez ( Bishop Graph ), pero este gráfico incluye conexiones adicionales que el vecino diagonal más cercano. Si alguien conoce una forma más corta de hacerlo, hágamelo saber. El crédito por la construcción del gráfico corresponde a esta respuesta de MathematicaSE .

Devoluciones Truepara contraseñas seguras, Falsepara contraseñas débiles / mal formadas. Tenga en cuenta que para la mayoría de las contraseñas mal formadas producirá un montón de mensajes de error y luego regresará False. Si esto no está en línea con las reglas, se pueden suprimir cambiando f[n_]:=...a un f[n_]:=Quiet@...costo de 6 bytes.

Sin golf:

p[m_] := StringPartition[#, m] &;

f[n_] :=
 Check[
  w = (8 #2 + #1 - 
       8) & @@@ ({LetterNumber@#, FromDigits@#2} & @@@ (p@1 /@ 
        p[UpTo@2]@n));
  r = GridGraph[{8, 8}];
  g = Graph[Sort /@ UndirectedEdge @@@
             Position[Outer[EuclideanDistance@## &, #, #, 1],N@Sqrt@2] &@
              GraphEmbedding@r // Union]~VertexDelete~w;
  s = Complement[{1,2,3,4,5,6,7,8},w];
  e = Complement[{57,58,59,60,61,62,63,64},w];
  m = 0;
  Do[m += Length@FindPath[g, i, j], {i, s}, {j, e}];
  If[m == 0,True,False]
  , False]

Descompostura:

p[m_]:=StringPartition[#,m]& 

Toma un argumento de cadena y lo divide en una lista de cadenas cada una de longitud m.

Check[...,False]

Devuelve Falsesi se producen mensajes de error, que es la forma en que captamos las cadenas mal formadas (es decir, supongamos que están bien formadas, lo que inevitablemente produce un error en la línea).

(8*#2 + #1 - 8) & @@@ ({LetterNumber@#, FromDigits@#2} & @@@ (p@1 /@ 
        p[UpTo@2]@n));

Toma la cadena de posiciones de peón y la divide de tal manera que se "a2h5b"convierte {{"a","2"},{"h","5"},{"b"}}, luego LetterNumberconvierte la letra en un número ( a -> 1, etc.) y FromDigitsconvierte el número en un entero. Si la cadena no está bien formada, este paso producirá un error que será atrapado al Checkregresar False. Estos dos números se convierten en un número entero correspondiente a un cuadrado en el tablero.

r = GridGraph[{8, 8}];
g = Graph[
     Sort /@ UndirectedEdge @@@ 
          Position[Outer[EuclideanDistance@## &, #, #, 1], 
           N@Sqrt@2] &@GraphEmbedding@r // Union]~VertexDelete~w;

Construye el gráfico de todos los bordes diagonales del vecino más cercano con las posiciones de peón eliminadas.

s = Complement[{1,2,3,4,5,6,7,8},w];
e = Complement[{57,58,59,60,61,62,63,64},w];

Estas son listas de vértices iniciales y finales desocupados respectivamente

m=0
Do[m += Length@FindPath[g, i, j], {i, s}, {j, e}];
If[m == 0,True,False]

Recorre los vértices iniciales y finales, para cada par FindPathhabrá una lista de caminos entre ellos. Si no hay caminos entre ellos, será una lista vacía, por lo que Length@regresa 0. Si no hay rutas en absoluto, mserá cero, y volveremos True, de lo contrario regresaremos False.