Nicht zu verwechseln mit Password Bishop Goodness !

Beantworten Sie eine Zeichenfolge (wahr / falsch oder zwei konsistente Werte), wenn es sich um ein Passwort handelt, das gegen Bischöfe sicher ist .

Ein Passwort ist gegen Bischöfe sicher, wenn es sich um eine Zeichenfolge handelt, die aus abwechselnden Buchstaben (in a-h) und Ziffern (in 1-8) besteht, sodass jedes Zeichenpaar als Quadrat auf einem Schachbrett interpretiert werden kann, und wenn Sie auf jedes genannte Quadrat einen weißen Bauern setzen Im Passwort gibt es dann keine Möglichkeit für einen weißen Läufer, in einer beliebigen Anzahl von aufeinanderfolgenden Zügen von einem beliebigen Feld in der ersten ( 1) Reihe zu einem beliebigen Feld in der letzten ( 8) Reihe zu reisen .

Beispiele

Passwörter stark gegen Bischöfe

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

Zum Beispiel a1b1c1d1e1f1g1a8b8c8d8e8f8g8entspricht der Position und b4b5d4d5f4f5g3h5entspricht der Position

Gegen Bischöfe schwache Passwörter

• a4c4e4g4g5d6f6e3d2b2 (Gut geformt, aber nicht stark - danke Jo King für dieses Beispiel!)
• b1c1d1e1f1g1h1a8b8c8d8e8f8g8 (gut geformt, aber nicht stark)
• h4g4f4e4c4b4a4c3 (gut geformt, aber nicht stark)
• d4 (gut geformt, aber nicht stark)
• b4b5d4d5f4f5g2h5 (gut geformt, aber nicht stark)
• correct horse battery staple (schlecht geformt)
• 1a1b1c1d1e1f1g8a8b8c8d8e8f8g (schlecht geformt)
• a (schlecht geformt)
• aa (schlecht geformt)

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

Probieren Sie es online!

Kehrt 1für Starke und nilfür Schwache zurück. (Die +67 Bytes wurden zur Berücksichtigung von "Backtracking" verwendet.)

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

Einige Tricks, die angewendet wurden:

• Anstelle des numerischen Bereichs 0..99wird der Zeichenfolgenbereich verwendet , '00'..'99'sodass die Zahl automatisch auf zwei Ziffern aufgefüllt und mit einem String versehen wird. Dies macht die Überprüfung außerhalb der Grenzen sehr kurz - mit Regex übereinstimmen /[09]/.

• Während [x-11, x-9, x+9, x+11]wir in der Helferfunktion die Liste der neuen Koordinaten erstellen , weisen wir sie gleichzeitig z[x]zu 9, was zufällig ein wahrer Wert ist (Markierung des besuchten Quadrats).

• In der letzten Zeile möchten wir überprüfen, dass das Array z[81,9]nicht enthält 9. Dazu entfernen wir alle Instanzen von 9( z[81,9]-[9]) und fragen nach dem 9. Element des resultierenden Arrays ( [8]). Da wir wissen, dass das Array ursprünglich 9 Elemente enthielt, erhalten wir, falls eines entfernt wurde, nildas letzte Element des Arrays (das zufällig immer vorhanden ist 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

Probieren Sie es online!

Probieren Sie die praktische Version online aus! (Das Original kann 4 ^ 32 Operationen benötigen, um vollständig zu prüfen. Ich empfehle die Verwendung derselben Anzahl von Bytes.)

Keine superkurze Lösung - ich konnte nicht herausfinden, wie man eine Lambda-Funktionsversion von g kürzer als g selbst macht.

-4 Bytes dank Quuxplusone

+61 Bytes für das Backtracking (danke für den Hinweis auf Jo King und die Golftipps)

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)

Probieren Sie es online!

Dies funktioniert durch "Überfluten". Zuerst erstellen wir eine Liste, awelche Quadrate neben welchen anderen Quadraten bischofsmäßig liegen. Dann erstellen wir eine Reihe xvon Ausschlüssen (basierend auf dem Passwort). Dann initialisieren wir einen Satz rerreichbarer Quadrate, der als erste Zeile beginnt (abzüglich etwaiger Ausschlüsse), und "fluten" von dort wiederholt 99 Mal nach außen, was mehr als genug sein sollte. Zum Schluss testen wir, ob eines der Quadrate in der letzten Reihe in unserer erreichbaren Menge gelandet ist. Wenn ja, haben wir ein schwaches Passwort! Wenn nicht, haben wir ein sicheres Passwort.

Nachteil, vielleicht Disqualifikation (ich kenne die übliche Regel hier nicht): Wenn das Passwort falsch ist (wie "richtige Batterie für Pferde"), dann werfen wir eine Ausnahme, anstatt zurückzukehren False. Wir geben aber immer zurück, Truewenn das Passwort sicher ist!

Minus 16 Bytes dank Jo King. Wir fügen aan der einen Stelle, an der es verwendet wird, eine Inline ein und falten etwas Mathematik.

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)

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

$[]

Probieren Sie es online!

$[] ist $ :: [[Int]] [Char] -> Bool mit dem ersten Argument zusammengesetzt, geben \ [Char] -> Bool.

Die Funktion verbraucht die Zeichenfolge jeweils zwei Zeichen und gibt sofort false zurück, wenn die Zeichenfolge ein ungültiges Format aufweist, sobald der ungültige Teil angezeigt wird. Sobald die Saite verarbeitet wurde, platziert sie einen Läufer auf jedes leere Feld auf einer Seite des Bretts und bewegt sie 64 Mal auf jede mögliche Weise und überprüft, ob sich eine der Endpositionen in der Zielreihe befindet.

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

-23 Bytes dank @Doorknob.

+42 Bytes für die Rückverfolgung.

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]

Probieren Sie es online!

Ich habe das meiste davon umgeschrieben, um das Zurückverfolgen zu berücksichtigen. Ich glaube, es gibt eine einfachere Möglichkeit, das Diagramm zu definieren g. Mathematica gibt GraphData[{"bishop",{8,8}}]das Diagramm aller Züge an, die ein Bischof auf einem Schachbrett ausführen kann ( Bischofs-Diagramm ). Dieses Diagramm enthält jedoch weitere Verbindungen als nächster diagonaler Nachbar. Wenn jemand einen kürzeren Weg kennt, lass es mich wissen. Diese MathematicaSE-Antwort ist für die Erstellung des Graphen verantwortlich .

Gibt Truefür starke Passwörter und Falsefür schwache / falsch geformte Passwörter zurück. Beachten Sie, dass bei den meisten falsch formulierten Passwörtern eine Reihe von Fehlermeldungen ausgegeben werden und diese dann zurückgegeben werden False. Wenn dies nicht den Regeln entspricht, können sie durch Umstellung f[n_]:=...auf f[n_]:=Quiet@...6 Byte unterdrückt werden .

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]

Nervenzusammenbruch:

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

Nimmt ein Zeichenfolgenargument und teilt es in eine Liste von Zeichenfolgen mit jeweils einer Länge auf m.

Check[...,False]

Gibt zurück, Falsewenn Fehlermeldungen erzeugt werden. Auf diese Weise werden die falsch geformten Zeichenfolgen abgefangen (dh es wird angenommen, dass sie gut geformt sind und zwangsläufig einen Fehler auf der ganzen Linie verursachen).

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

Nimmt die Folge von Bauernpositionen und teilt sie so, dass sie "a2h5b"wird {{"a","2"},{"h","5"},{"b"}}, LetterNumberkonvertiert dann den Buchstaben in eine Zahl ( a -> 1usw.) und FromDigitskonvertiert die Zahl in eine Ganzzahl. Wenn die Zeichenkette nicht richtig geformt ist, erzeugt dieser Schritt einen Fehler, der bei der CheckRückkehr abgefangen wird False. Diese beiden Zahlen werden dann in eine Ganzzahl umgewandelt, die einem Quadrat auf der Tafel entspricht.

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

Konstruiert das Diagramm aller diagonalen Kanten des nächsten Nachbarn, wobei die Bauernpositionen gelöscht werden.

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

Hierbei handelt es sich um Listen nicht belegter Start- und Endpunkte

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

Durchlaufen Sie die Start- und Endpunkte. Für jedes Paar FindPathwird eine Liste von Pfaden zwischen ihnen erstellt. Wenn es keine Pfade zwischen ihnen sind, wird es eine leere Liste, so sein Length@Rendite 0. Wenn es überhaupt keine Pfade gibt, mwird Null sein, und wir kehren zurück True, andernfalls kehren wir zurück False.