Não deve ser confundido com Password Bishop Goodness !

Dada uma sequência, responda (verdade / falsidade ou dois valores consistentes) se ela constitui uma senha forte contra os bispos .

Uma senha é forte contra os bispos, se for uma sequência que consiste em letras (in a-h) e dígitos (in 1-8) alternados, de modo que cada par de caracteres possa ser interpretado como um quadrado em um tabuleiro de xadrez e se você colocar um peão branco em cada quadrado chamado na senha, não há como um bispo branco viajar, em qualquer número de movimentos consecutivos, de qualquer quadrado na primeira ( 1) linha a qualquer quadrado na última ( 8) linha.

Exemplos

Senhas fortes contra bispos

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

Por exemplo, a1b1c1d1e1f1g1a8b8c8d8e8f8g8corresponde à posição e b4b5d4d5f4f5g3h5corresponde à posição

Senhas fracas contra bispos

• a4c4e4g4g5d6f6e3d2b2 (bem formado, mas não forte - obrigado Jo King por este exemplo!)
• b1c1d1e1f1g1h1a8b8c8d8e8f8g8 (bem formado, mas não forte)
• h4g4f4e4c4b4a4c3 (bem formado, mas não forte)
• d4 (bem formado, mas não forte)
• b4b5d4d5f4f5g2h5 (bem formado, mas não forte)
• 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]}

Experimente online!

Retorna 1para forte e nilpara fraco. (Os +67 bytes foram usados ​​para levar em consideração "retroceder".)

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

Alguns truques que foram usados:

• Em vez do intervalo numérico 0..99, usamos o intervalo de strings'00'..'99' para que o número seja preenchido automaticamente à esquerda com 2 dígitos e estriado. Isso faz com que a verificação fora dos limites seja muito curta - corresponda à regex /[09]/.

• Dentro da função auxiliar, ao construir a lista de novas coordenadas [x-11, x-9, x+9, x+11], que, simultaneamente, atribuir z[x]a 9no processo, que passa a ser um valor truthy (marcando o quadrado visitado).

• Na última linha, queremos verificar se a matriz z[81,9]não contém 9. Fazemos isso removendo todas as instâncias de 9( z[81,9]-[9]) e solicitando o 9º elemento da matriz resultante ( [8]). Como sabemos que o array originalmente tinha 9 elementos, se algum foi removido, obteremos nil, enquanto que se todos permanecerem, obteremos o último elemento do array (o que sempre acontece 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

Experimente online!

Experimente a versão prática online! (o original pode levar 4 ^ 32 operações para verificar completamente, sugiro usar este - o mesmo número de bytes)

Não é uma solução super curta - eu não conseguia descobrir como tornar uma versão da função lambda do g menor que o próprio g.

-4 bytes graças ao Quuxplusone

+61 bytes representando retrocesso (obrigado por apontar Jo King e pelas dicas de golfe)

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

Experimente online!

Isso funciona por "preenchimento de inundação". Primeiro, criamos uma lista ade quais quadrados são adjacentes a outros quadrados, bishopwise. Em seguida, criamos um conjunto xde exclusões (com base na senha). Em seguida, inicializamos um conjunto rde quadrados alcançáveis, que começa como a primeira linha (menos as exclusões) e "repetidamente" inundamos a partir daí, 99 vezes, o que deve ser mais do que suficiente. Por fim, testamos para ver se algum dos quadrados da última linha terminou em nosso conjunto acessível. Se assim for, temos uma senha fraca! Caso contrário, temos uma senha forte.

Desvantagem, talvez desqualificante (não conheço a regra usual aqui): se a senha estiver mal formada (como "grampo correto para a bateria do cavalo"), lançamos uma exceção em vez de retornar False. Mas sempre retornamos Truese a senha for forte!

Menos 16 bytes graças a Jo King. Nós alinhamos ano local em que é usado e dobramos constantemente algumas contas.

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)

Limpo , 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))

$[]

Experimente online!

$[]é $ :: [[Int]] [Char] -> Boolcomposto com o primeiro argumento, dando \ [Char] -> Bool.

A função funciona consumindo a string dois caracteres por vez, retornando false imediatamente se a string estiver em um formato inválido assim que vir a parte inválida. Depois que a corda é processada, ela coloca um bispo em cada quadrado vazio de um lado do tabuleiro e as move de todas as maneiras possíveis 64 vezes e verifica se alguma das posições finais está na linha de destino.

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

-23 bytes graças a @Doorknob.

+42 bytes, representando retorno.

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]

Experimente online!

Eu reescrevi a maior parte disso para dar conta do retorno, acho que pode haver uma maneira mais fácil de definir o gráfico g, o Mathematica possui GraphData[{"bishop",{8,8}}]o gráfico de todos os movimentos que um bispo pode fazer em um tabuleiro de xadrez ( Bishop Graph ), mas esse gráfico inclui conexões adicionais que o vizinho diagonal mais próximo. Se alguém souber uma maneira mais curta de fazer isso, me avise. O crédito pela construção do gráfico vai para esta resposta do MathematicaSE .

Retorna Truepara senhas fortes, Falsepara senhas fracas / mal formadas. Observe que, para a maioria das senhas mal formadas, ela produz um monte de mensagens de erro e depois retorna False. Se isso não estiver de acordo com as regras, elas poderão ser suprimidas alterando f[n_]:=...para o f[n_]:=Quiet@...custo de 6 bytes.

Ungolfed:

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]

Demolir:

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

Pega um argumento de string e o divide em uma lista de strings cada uma de comprimento m.

Check[...,False]

Retorna Falsese alguma mensagem de erro for produzida, e é assim que capturamos as seqüências mal formadas (ou seja, presumimos que elas sejam bem formadas, inevitavelmente produzindo um erro abaixo da linha).

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

Pega a sequência de posições dos peões e a divide de maneira que "a2h5b"se torne {{"a","2"},{"h","5"},{"b"}}, depois LetterNumberconverterá a letra em um número ( a -> 1, etc) e FromDigitsconverterá o numeral em um número inteiro. Se a string não estiver bem formada, esta etapa produzirá um erro que será detectado pelo Checkretorno False. Esses dois números são então convertidos em um número inteiro correspondente a um quadrado no quadro.

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

Constrói o gráfico de todas as arestas diagonais do vizinho mais próximo com as posições do peão excluídas.

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

Estas são listas de vértices iniciais e finais desocupados, respectivamente

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

Loops nos vértices inicial e final, para cada par FindPath, haverá uma lista de caminhos entre eles. Se não houver caminhos entre eles, será uma lista vazia, então Length@retornará 0. Se não houver caminhos, mserá zero e retornaremos True, caso contrário, retornaremos False.