À ne pas confondre avec Password Bishop Goodness !

Étant donné une chaîne, répondez (vérité / fausse ou deux valeurs cohérentes) si elle constitue un mot de passe fort contre les évêques .

Un mot de passe est fort contre les évêques s'il s'agit d'une chaîne composée de lettres alternées (en a-h) et de chiffres (en 1-8) de sorte que chaque paire de caractères puisse être interprétée comme un carré sur un échiquier, et si vous placez un pion blanc sur chaque carré nommé dans le mot de passe, il n'y a aucun moyen pour un évêque blanc de voyager, dans n'importe quel nombre de mouvements consécutifs, de n'importe quel carré de la première ( 1) ligne à n'importe quel carré de la dernière ( 8) ligne.

Exemples

Des mots de passe forts contre les évêques

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

Par exemple, a1b1c1d1e1f1g1a8b8c8d8e8f8g8correspond à la position et b4b5d4d5f4f5g3h5correspond à la position

Des mots de passe faibles contre les évêques

• a4c4e4g4g5d6f6e3d2b2 (bien formé mais pas fort - merci Jo King pour cet exemple!)
• b1c1d1e1f1g1h1a8b8c8d8e8f8g8 (bien formé mais pas fort)
• h4g4f4e4c4b4a4c3 (bien formé mais pas fort)
• d4 (bien formé mais pas fort)
• b4b5d4d5f4f5g2h5 (bien formé mais pas fort)
• correct horse battery staple (mal formé)
• 1a1b1c1d1e1f1g8a8b8c8d8e8f8g (mal formé)
• a (mal formé)
• aa (mal formé)

Ruby, 115 182 163 octets

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

Essayez-le en ligne!

Retourne 1pour fort et nilpour faible. (Les +67 octets étaient destinés à prendre en compte le "retour en arrière".)

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

Quelques astuces qui ont été utilisées:

• Au lieu de la plage numérique 0..99, nous utilisons le plage de chaînes'00'..'99' afin que le nombre soit automatiquement rempli à gauche à 2 chiffres et stratifié. Cela rend la vérification hors limites très courte - correspondance avec l'expression régulière /[09]/.

• À l'intérieur de la fonction d'aide, tout en construisant la liste des nouvelles coordonnées [x-11, x-9, x+9, x+11], nous attribuons simultanément z[x]à 9dans le processus, qui se trouve être une valeur vraie (marquant le carré visité).

• Dans la dernière ligne, nous voulons vérifier que le tableau z[81,9]ne contient pas 9. Nous faisons cela en supprimant toutes les instances de 9( z[81,9]-[9]), puis en demandant le 9ème élément du tableau résultant ( [8]). Puisque nous savons que le tableau avait à l'origine 9 éléments, s'il en a été supprimé, nous obtiendrons nil, alors que s'ils sont tous restés, nous obtiendrons le dernier élément du tableau (qui se trouve toujours être 1).

Python 2 , 330 318 313 309 370 octets

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

Essayez-le en ligne!

Essayez la version pratique en ligne! (l'original peut prendre 4 ^ 32 opérations pour vérifier complètement, je suggère d'utiliser celui-ci - même nombre d'octets)

Pas une solution super courte - je ne pouvais pas comprendre comment rendre une version de la fonction lambda de g plus courte que g elle-même.

-4 octets grâce à Quuxplusone

+61 octets pour le retour en arrière (merci d'avoir signalé cela à Jo King et pour les conseils de golf)

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)

Essayez-le en ligne!

Cela fonctionne par "inondation". Nous créons d'abord une liste ade quels carrés sont adjacents à quels autres carrés, dans le sens de l'évêque. Ensuite, nous créons un ensemble xd'exclusions (basé sur le mot de passe). Ensuite, nous initialisons un ensemble rde carrés accessibles, qui commence comme juste la première ligne (moins toutes les exclusions), et "envahit" à plusieurs reprises à partir de là, 99 fois, ce qui devrait être plus que suffisant. Enfin, nous testons pour voir si l'un des carrés de la dernière ligne s'est retrouvé dans notre ensemble accessible. Si oui, nous avons un mot de passe faible! Sinon, nous avons un mot de passe fort.

Inconvénient, peut-être disqualifiant (je ne connais pas la règle habituelle ici): si le mot de passe est mal formé (tel que "batterie de cheval correcte"), nous lançons une exception au lieu de revenir False. Mais nous revenons toujours Truesi le mot de passe est fort!

Moins 16 octets grâce à Jo King. Nous nous alignons aau seul endroit où il est utilisé et nous multiplions constamment les mathématiques.

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)

Nettoyer , 285 octets

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

$[]

Essayez-le en ligne!

$[] est $ :: [[Int]] [Char] -> Bool composé avec le premier argument, donnant \ [Char] -> Bool.

La fonction fonctionne en consommant la chaîne deux caractères à la fois, retournant immédiatement false si la chaîne est dans un format invalide dès qu'elle voit la partie invalide. Une fois la chaîne traitée, elle place un évêque sur chaque case vide d'un côté du plateau et les déplace de toutes les manières possibles 64 fois et vérifie si l'une des positions finales se trouve dans la ligne cible.

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

-23 octets grâce à @Doorknob.

+42 octets représentant le retour en arrière.

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]

Essayez-le en ligne!

J'ai réécrit la plupart de cela pour tenir compte du retour en arrière, je pense qu'il peut y avoir un moyen plus facile de définir le graphique g, Mathematica a GraphData[{"bishop",{8,8}}]qui est le graphique de tous les mouvements qu'un évêque peut faire sur un échiquier ( Bishop Graph ), mais ce graphique comprend des connexions plus loin que le voisin diagonal le plus proche. Si quelqu'un connaît un moyen plus court de le faire, faites le moi savoir. Le mérite de la construction du graphique revient à cette réponse MathematicaSE .

Renvoie Trueles mots de passe forts, les mots de passe Falsefaibles / mal formés. Notez que pour la plupart des mots de passe mal formés, il produira un tas de messages d'erreur, puis reviendra False. Si cela n'est pas conforme aux règles, elles peuvent être supprimées en passant f[n_]:=...à f[n_]:=Quiet@...6 octets.

Non 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]

Panne:

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

Prend un argument de chaîne et le divise en une liste de chaînes de longueur chacune m.

Check[...,False]

Renvoie Falsesi des messages d'erreur sont produits, c'est ainsi que nous interceptons les chaînes mal formées (c'est-à-dire supposons qu'elles sont bien formées, produisant inévitablement une erreur sur toute la ligne).

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

Prend la chaîne de positions de pion et la divise telle qu'elle "a2h5b"devient {{"a","2"},{"h","5"},{"b"}}, puis LetterNumberconvertira la lettre en un nombre ( a -> 1, etc.) et FromDigitsconvertit le chiffre en entier. Si la chaîne n'est pas bien formée, cette étape produira une erreur qui sera interceptée en Checkretournant False. Ces deux nombres sont ensuite convertis en un entier correspondant à un carré du tableau.

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

Construit le graphique de toutes les arêtes diagonales du plus proche voisin avec les positions de pion supprimées.

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

Ce sont des listes de sommets de début et de fin inoccupés, respectivement

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

Boucles sur les sommets de début et de fin, pour chaque paire FindPathsera une liste de chemins entre eux. S'il n'y a pas de chemin entre eux, ce sera une liste vide, donc Length@retourne 0. S'il n'y a aucun chemin, alors msera zéro, et nous reviendrons True, sinon revenons False.