Надежные пароли против епископов

13

Не путать с паролем епископа Боже !

Если дана строка, ответьте (истина / ложь или два непротиворечивых значения), если она представляет собой надежный пароль против епископов .

Пароль надежен против епископов, если это строка, состоящая из чередующихся букв (in a-h) и цифр (in 1-8), так что каждая пара символов может быть интерпретирована как квадрат на шахматной доске, и если вы поместите белую пешку на каждый квадрат с именем в пароле белый слон не сможет ни за какое количество последовательных ходов переместиться из любого квадрата в первой ( 1) строке в любой квадрат в последней ( 8) строке.

Примеры

Надежные пароли против епископов

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

Например, a1b1c1d1e1f1g1a8b8c8d8e8f8g8соответствует позиции Fooи b4b5d4d5f4f5g3h5соответствует позицииFoo

Слабые пароли против епископов

  • a4c4e4g4g5d6f6e3d2b2 (Хорошо сформированный, но не сильный - спасибо Джо Кинг за этот пример!)
  • b1c1d1e1f1g1h1a8b8c8d8e8f8g8 (хорошо сформированный, но не сильный)
  • h4g4f4e4c4b4a4c3 (хорошо сформированный, но не сильный)
  • d4 (хорошо сформированный, но не сильный)
  • b4b5d4d5f4f5g2h5 (хорошо сформированный, но не сильный)
  • correct horse battery staple (Плохо сформированы)
  • 1a1b1c1d1e1f1g8a8b8c8d8e8f8g (Плохо сформированы)
  • a (Плохо сформированы)
  • aa (Плохо сформированы)
Quuxplusone
источник
1
Какие цветные квадраты у епископа?
Воплощение Невежества
2
Ваш второй последний контрольный пример противоречит вашей спецификации. Вы также должны объяснить, как « каждая пара символов может быть интерпретирована как квадрат на шахматной доске ».
Лохматый
1
a1b2c3d4d5f5f4g3g4h2b5 не силен против епископов, так как епископ может добраться до h5, а затем опуститься до d1
Воплощение невежества
2
@TRITICIMAGVS, Ourous: Я уточнил, что пешки и слон белые, поэтому никому не разрешается захватывать (или приземляться, или перемещаться, или перепрыгивать) другого.
Quuxplusone
1
Кроме того, не могли бы вы добавить пример для одного из истинных тестовых случаев. Потому что я понимаю, что квадраты пароля заполнены белыми пешками, но я не понимаю, где находится белый слон. И если место это хорошо, почему она не может поехать в каждой строке 1через 8в первом тесте? Он не может перемещаться к каждому столбцу, поскольку aстолбец полностью заполнен пешками, но он может перемещаться к каждому ряду без проблем, не так ли? У меня такое чувство, что я что-то
упускаю

Ответы:

4

Рубин, 115 182 163 байта

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

Попробуйте онлайн!

Возвращает 1для сильных и nilдля слабых. (+67 байт было для учета "возврата".)

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

Несколько хитростей, которые были использованы:

  • Вместо числового диапазона 0..99мы используем диапазон строк,'00'..'99' так что число автоматически дополняется слева до 2 цифр и переводится в строку . Это делает проверку границ очень короткой - совпадение с регулярным выражением /[09]/.

  • Внутри функции - помощника, при построении списка новых координат [x-11, x-9, x+9, x+11], мы одновременно назначить z[x]для 9процесса, который , случается, значение truthy (маркировка квадрат посещаемый).

  • В последней строке мы хотим проверить, что массив z[81,9]не содержит 9. Мы делаем это, удаляя все экземпляры 9( z[81,9]-[9]), затем запрашивая 9-й элемент результирующего массива ( [8]). Поскольку мы знаем, что в массиве изначально было 9 элементов, если они были удалены, мы получим nil, тогда как, если они все остались, мы получим последний элемент массива (который всегда будет 1).

Дверная ручка
источник
2

Python 2 , 330 318 313 309 370 байт

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

Попробуйте онлайн!

Попробуйте практическую версию онлайн! (для полной проверки оригинала может потребоваться 4 ^ 32 операций, я предлагаю использовать одно и то же количество байтов)

Не очень короткое решение - я не мог понять, как сделать версию лямбда-функции g короче, чем сама g.

-4 байта благодаря Quuxplusone

+61 байт для учета возврата (спасибо за указание на это Джо Кинга и за советы по игре в гольф)

сельдь
источник
Ницца. q=r=1будет короче q=1 r=1, верно? И if r:короче чем if r>0:.
Quuxplusone
2

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)

Попробуйте онлайн!

Это работает "заливают". Сначала мы создаем список aквадратов, смежных с какими квадратами, по епископу. Затем мы создаем набор xисключений (на основе пароля). Затем мы инициализируем набор rдостижимых квадратов, который начинается как первый ряд (без каких-либо исключений), и многократно «затопляет» оттуда 99 раз, чего должно быть более чем достаточно. Наконец, мы проверяем, попали ли какие-либо квадраты в последнем ряду в наш достижимый набор. Если так, у нас слабый пароль! Если нет, у нас есть надежный пароль.

Недостаток, возможно, дисквалификация (я не знаю обычного правила здесь): если пароль неверно сформирован (например, «правильное сшивание батареи»), то вместо возврата мы выдаем исключение False. Но мы всегда возвращаем, Trueесли пароль надежный!

Минус 16 байтов благодаря Джо Кингу. Мы включаем aв одном месте, где оно используется, и постоянно складываем некоторые математические данные.

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)
Quuxplusone
источник
@ Шучу, спасибо! До двух forсекунд еще есть пробелы, которые я не мог понять, как удалить. Я обнаружил, что замена range(99)на repr(f)работает на моей локальной машине, но не на интерпретаторе tio.run ... но потом я обнаружил, что [1]*99это все равно было короче! Так что сэкономили еще 4 байта.
Quuxplusone
пробелы до двух forс, что я не мог видеть, как удалить - О! Очевидно, что Python обрабатывает 33forкак два for33токена (тогда как один токен). Сегодня я узнал. Тогда минус 2 байта.
Quuxplusone
1

Чисто , 285 байт

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

$[]

Попробуйте онлайн!

$[]составляется $ :: [[Int]] [Char] -> Boolс первым аргументом, дающим \ [Char] -> Bool.

Функция работает, потребляя строку по два символа за раз, немедленно возвращая false, если строка имеет недопустимый формат, как только она увидит недопустимую часть. Как только строка обработана, она помещает слона на каждый пустой квадрат с одной стороны доски и перемещает их всеми возможными способами 64 раза и проверяет, находится ли какая-либо из конечных позиций в целевой строке.

Οurous
источник
Кажется, неправильно вернуть Trueдля a1b1c1d1e1f1g1? Не то чтобы я что-то понял о том, как это работает. :)
Quuxplusone
2
@Quuxplusone У меня был пердеж и я думал, что белые епископы используют только белые квадраты. Я также добавил объяснение.
Οurous
1

Wolfram Language (Mathematica) , 339 316 358 353 345 байт

-23 байта благодаря @ Doorknob.

+42 байта с учетом возврата.

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]

Попробуйте онлайн!

Я переписал большую часть этого, чтобы учесть обратную реакцию, я думаю, что может быть более простой способ определить график g, у Mathematica есть GraphData[{"bishop",{8,8}}]график всех ходов, которые епископ может сделать на шахматной доске ( Bishop Graph ), но этот график включает в себя дальнейшие связи чем ближайший диагональный сосед. Если кто-нибудь знает более короткий способ сделать это, дайте мне знать. Кредит на построение графика идет на этот ответ MathematicaSE .

Возвращает Trueдля надежных паролей, Falseдля слабых / плохо сформированных паролей. Обратите внимание, что для большинства плохо сформированных паролей он выдаст кучу сообщений об ошибках, а затем вернет False. Если это не соответствует правилам, то их можно подавить, изменив стоимость f[n_]:=...до f[n_]:=Quiet@...6 байтов.

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]

Сломать:

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

Принимает строковый аргумент и разбивает его на список строк, каждая из которых имеет длину m.

Check[...,False]

Возвращает, Falseесли генерируются какие-либо сообщения об ошибках, то есть, как мы ловим неправильно сформированные строки (т.е. предполагаем, что они правильно сформированы, что неизбежно приводит к ошибке в дальнейшем).

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

Занимает последовательность позиций пешки и разделяет ее так, что "a2h5b"становится {{"a","2"},{"h","5"},{"b"}}, затем LetterNumberпреобразует букву в число ( a -> 1и т. Д.) И FromDigitsпреобразует цифру в целое число. Если строка не правильно сформирована, этот шаг приведет к ошибке, которая будет Checkвозвращена False. Эти два числа затем преобразуются в целое число, соответствующее квадрату на доске.

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]

Зацикливается на начальной и конечной вершинах, для каждой пары FindPathбудет список путей между ними. Если между ними нет путей, это будет пустой список, поэтому Length@возвращается 0. Если путей вообще нет, то mбудет ноль, и мы вернемся True, в противном случае вернемся False.

Кай
источник
Несколько советов: Trueа Falseможно 1>0и 0>1соответственно. p[1]@#&/@эквивалентно просто p@1/@. Sequence@@можно заменить на ##&@@. Вместо {LetterNumber[#[[1]]],FromDigits[#[[2]]]}&/@, вы можете использовать {LetterNumber@#,FromDigits@#2}&@@@.
Ручка двери
@ Doorknob спасибо! Кодовый гольф учит меня всему новому о Mathematica. Я все еще не на 100% понимаю p@1/@, но я вижу общую идею. Я полагаю p@1 = StringPartition[#,1]&, это немного сбивает меня с толку, я думаю, потому что pпринимает два аргумента двумя разными способами, один как m_и другой как #...&, я думаю, это просто вопрос приоритета. Это имеет смысл, хотя это p@m = p[m].
Кай
Это касается и меня! Основное изменение заключается в том, что для любой функции, fкоторая принимает один аргумент, f@#&имеет то же поведение, что и просто f- здесь, fесть p[1]. (Затем я изменил []обозначение на @, которое всегда идентично, за исключением приоритета.)
Ручка двери
@ Шучу, это обманчиво, это намного сложнее, чем я думал, учитывая также движения назад. Спасибо
Кай
@JoKing написал новый, который отвечает за возврат.
Кай