Взаимно атакующие королевы

26

Пусть шахматная доска 8x8 будет представлена ​​любыми двумя различными значениями, одно из которых будет пустым квадратом, а другое - королевой. В следующих примерах я использую 0 в качестве пустых квадратов и 1 в качестве королев. Например:

Королевы на шахматной доске

дан кем-то

1 0 1 1 1 0 0 0
1 0 1 0 1 0 1 1
1 0 1 0 1 1 0 1
0 1 0 1 0 1 0 0
0 1 1 0 0 1 0 1
1 0 0 0 1 0 0 0
0 1 0 0 0 1 1 1
0 1 1 1 0 1 0 1

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

Атакующие королевы

Выше 43 пар дают следующий контрольный пример:

Input:
1 0 1 1 1 0 0 0
1 0 1 0 1 0 1 1
1 0 1 0 1 1 0 1
0 1 0 1 0 1 0 0
0 1 1 0 0 1 0 1
1 0 0 0 1 0 0 0
0 1 0 0 0 1 1 1
0 1 1 1 0 1 0 1
Output: 43

Вызов

Напишите программу, которая, учитывая состояние платы, представленное двумя различными значениями, выводит количество пар королев, которые атакуют друг друга, по крайней мере, с одним квадратом между ними.

  • Вы можете вводить в любом удобном для вас формате, который использует два значения для представления пустых квадратов и королев, например, строку размером 64 ". Для пустых квадратов и" Q "для королев по строкам снизу вверх, 8x8 матрица логических значений, список целых чисел 0 и 1 и т. д., если это объясняется в вашем решении
  • Выход является целым числом
  • Применяются стандартные методы ввода / вывода и запрещены стандартные лазейки
  • Это код гольф, поэтому самый короткий ответ в байтах выигрывает

Тестовые случаи:

Используя формат 0 и 1, где 0 - пустые квадраты, а 1 - королева:

Input:
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
Output: 0

Input:
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1
Output: 0

Input:
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 1 0 0 0 0 1 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
Output: 1

Input:
0 0 0 0 0 0 0 0
0 0 0 1 0 0 0 0
0 0 0 0 1 0 0 0
0 1 0 0 0 0 1 0
0 0 0 0 1 0 1 0
0 0 0 0 0 0 0 0
0 0 0 1 0 0 1 0
0 0 0 0 0 0 0 0
Output: 10

Input:
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1
1 1 1 1 0 1 1 1
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1
Output: 4

Input:
1 1 0 1 1 1 1 1
1 1 1 1 1 1 1 1
1 1 1 1 0 1 1 1
1 1 1 1 0 1 1 1
1 1 1 1 0 1 1 1
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1
Output: 11
JMigst
источник
Я должен был спросить перед публикацией моей второй версии: 254 для ферзя и 0 для пустого квадрата допустимые входные значения?
Арно
@Arnauld Вы можете вводить данные в любом удобном для вас формате, который использует два значения для представления пустых квадратов и королев. Так что это точно
JMigst
Спасибо. Я спросил, потому что я думаю, что это правило может быть слишком допустимым, если понимать его буквально. Я мог бы попросить передать строку, содержащую большую часть кода JS для ферзей, и просто оценить это в программе. (Но это может быть предотвращено лазейкой по умолчанию. Я не уверен.)
Арно

Ответы:

14

Python 2 , 105 байт

lambda b:sum(b[i+d::d][:(8,7-i%8,i%8)[d%8%5]].find('1')*int(c)>0for i,c in enumerate(b)for d in[1,7,8,9])

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

объяснение

Мы принимаем ввод как строку из 64 символов '0'или '1'. Используя пошаговые фрагменты, мы отбрасываем четыре «линии обзора» от каждой королевы, с которой сталкиваемся. Например, когда я = 10 и d = 7 , отмечая королеву как ♥ и плитки, выбранные b[i+d::d]как █:

1 0 1 1 1 0 0 0
1 0  0 1 0 1 1
1  1 0 1 1 0 1
 1 0 1 0 1 0 
0 1 1 0 0 1  1
1 0 0 0 1  0 0
0 1 0 0  1 1 1
0 1 1  0 1 0 1

Ясно, что на самом деле мы не хотим, чтобы видение обернулось вокруг доски таким образом Таким образом, мы вычисляем, как далеко находится край доски в каждом направлении, и видим плитки на b[i+d::d][:…].

Для каждой пары направления плитки мы считаем:

ray.find('1')*int(c)>0

Это не удастся всякий раз, когда

  • cне королева; или
  • королева, которую видит этот луч, находится слишком близко ( findвозвращает 0); или
  • этот луч не видит королеву ( findвозвращает -1).

Каждая пара ферзей проверяется только один раз, поскольку лучи всегда направляются вперед в порядке чтения, от «более ранней» королевы до «более поздней».

Линн
источник
10

JavaScript (ES7), 86 байт

Принимает входные данные в виде массива из 64 целых чисел с 254 для ферзя и 0 для пустого квадрата.

a=>[s=0,6,7,8].map(d=>a.map(g=(n,p)=>(p%8-(p+=~d)%8)**2<n%4?a[p]?s+=n&1:g(n/2,p):0))|s

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

Эта версия злоупотребляет арифметическим понижением, чтобы получить условие остановки в рекурсивной части.


JavaScript (ES7), 89 байт

Принимает ввод как массив из 64 бит.

a=>[s=0,6,7,8].map(d=>a.map(g=(n,p,x)=>(p%8-(p+=~d)%8)**2>1|p<0?0:a[p]?s+=!x&n:g(n,p)))|s

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

Как?

Мы рекурсивно вызываем именованную функцию обратного вызова, map()чтобы пройти через квадраты в заданном направлении. Хотя нам действительно не нужно содержимое третьего параметра обратного вызова ( map()был вызван массив ), тем не менее, мы косвенно используем его, чтобы узнать, является ли это первой итерацией или нет.

arr.map (обратный вызов функции (currentValue [, index [, array]])

Это переменная х в коде.

a =>                        // given the input array a[]
  [ s = 0,                  // initialize the sum s to 0
    6, 7, 8 ].map(d =>      // for each direction d in [0, 6, 7, 8]:
    a.map(g = (n, p, x) =>  //   for each square n at position p in a[]:
      (                     //     we are out of the board if:
        p % 8 -             //       - abs(p % 8 - p' % 8) is greater than 1
        (p += ~d) % 8       //         where p' = p - (d + 1)
      ) ** 2 > 1 |          //         (squaring is shorter than using Math.abs)
      p < 0 ?               //       - or p' is less than 0
        0                   //       if so, stop recursion
      :                     //     else:
        a[p] ?              //       if there's a queen on the target square:
          s +=              //         increment s if:
            !x &            //           x is undefined (this is not the 1st iteration)
            n               //           and n = 1 (there's a queen on the source square)
        :                   //       else:
          g(n, p)           //         do a recursive call to g(), with x undefined
    )                       //   end of inner map()
  ) | s                     // end of outer map(); return s
Arnauld
источник
8

Улитки , 14 байт

A
rdaa7\1\0+\1

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

Ввод в формате 0/1 без пробелов в строках.

Улитки были созданы для языкового проектирования PPCG . Самое главное, он по умолчанию выводит количество найденных совпадений, что идеально подходит для этой задачи.


A устанавливает опцию «все пути», так что если ферзь состоит из нескольких пар, каждая из этих пар будет генерировать совпадение.

rdaa7устанавливает направление совпадения на S, SE, E и NE. Установка во всех направлениях ( z) приведет к двойному счету.

\1\0+\1соответствует a 1, затем одному или нескольким 0s, затем другому 1.

TwiNight
источник
6

APL (Dyalog Classic) , 41 39 32 байта

(+/+⌿-⌈⌿)2<⌿0⍪⊢,⍉,8 31⍴⊢,≠⍨,⌽,≠⍨

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

≠⍨ «не равен самому себе» - матрица с нулевым размером 8x8

⊢,≠⍨,⌽,≠⍨- если исходная матрица есть ABC..., это выражение возвращает:

A B C D E F G H 0 0 0 0 0 0 0 0 H G F E D C B A 0 0 0 0 0 0 0 0
I J K L M N O P 0 0 0 0 0 0 0 0 P O N M L K J I 0 0 0 0 0 0 0 0
Q R S T U V W X 0 0 0 0 0 0 0 0 X W V U T S R Q 0 0 0 0 0 0 0 0
Y Z A B C D E F 0 0 0 0 0 0 0 0 F E D C B A Z Y 0 0 0 0 0 0 0 0
G H I J K L M N 0 0 0 0 0 0 0 0 N M L K J I H G 0 0 0 0 0 0 0 0
O P Q R S T U V 0 0 0 0 0 0 0 0 V U T S R Q P O 0 0 0 0 0 0 0 0
W X Y Z A B C D 0 0 0 0 0 0 0 0 D C B A Z Y X W 0 0 0 0 0 0 0 0
E F G H I J K L 0 0 0 0 0 0 0 0 L K J I H G F E 0 0 0 0 0 0 0 0

8 31⍴ изменяет его с 8x32 на 8x31, повторно используя элементы в главном порядке строк:

A B C D E F G H 0 0 0 0 0 0 0 0 H G F E D C B A 0 0 0 0 0 0 0
0 I J K L M N O P 0 0 0 0 0 0 0 0 P O N M L K J I 0 0 0 0 0 0
0 0 Q R S T U V W X 0 0 0 0 0 0 0 0 X W V U T S R Q 0 0 0 0 0
0 0 0 Y Z A B C D E F 0 0 0 0 0 0 0 0 F E D C B A Z Y 0 0 0 0
0 0 0 0 G H I J K L M N 0 0 0 0 0 0 0 0 N M L K J I H G 0 0 0
0 0 0 0 0 O P Q R S T U V 0 0 0 0 0 0 0 0 V U T S R Q P O 0 0
0 0 0 0 0 0 W X Y Z A B C D 0 0 0 0 0 0 0 0 D C B A Z Y X W 0
0 0 0 0 0 0 0 E F G H I J K L 0 0 0 0 0 0 0 0 L K J I H G F E

⊢,⍉, добавляет исходную матрицу и ее транспонирование (дополнительные пробелы для ясности):

A B C D E F G H  A I Q Y G O W E  A B C D E F G H 0 0 0 0 0 0 0 0 H G F E D C B A 0 0 0 0 0 0 0
I J K L M N O P  B J R Z H P X F  0 I J K L M N O P 0 0 0 0 0 0 0 0 P O N M L K J I 0 0 0 0 0 0
Q R S T U V W X  C K S A I Q Y G  0 0 Q R S T U V W X 0 0 0 0 0 0 0 0 X W V U T S R Q 0 0 0 0 0
Y Z A B C D E F  D L T B J R Z H  0 0 0 Y Z A B C D E F 0 0 0 0 0 0 0 0 F E D C B A Z Y 0 0 0 0
G H I J K L M N  E M U C K S A I  0 0 0 0 G H I J K L M N 0 0 0 0 0 0 0 0 N M L K J I H G 0 0 0
O P Q R S T U V  F N V D L T B J  0 0 0 0 0 O P Q R S T U V 0 0 0 0 0 0 0 0 V U T S R Q P O 0 0
W X Y Z A B C D  G O W E M U C K  0 0 0 0 0 0 W X Y Z A B C D 0 0 0 0 0 0 0 0 D C B A Z Y X W 0
E F G H I J K L  H P X F N V D L  0 0 0 0 0 0 0 E F G H I J K L 0 0 0 0 0 0 0 0 L K J I H G F E

2<⌿0⍪добавляет 0 к вершине и сравнивает, используя <каждый элемент, с элементом под ним, поэтому мы получаем 1 для ведущего 1 в каждой вертикальной группе 1, а 0 - везде

+⌿-⌈⌿ суммы по столбцам минус максимумы по столбцам - мы вычисляем количество разрывов между 1-группами в каждом столбце, 0, если их нет

+/ сумма

СПП
источник
5

Желе , 22 20 байт

t0ŒgL:2
Z,U;ŒD$€ẎÇ€S

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

user202729
источник
Как это работает?
lirtosiast
@lirtosiast Я не помню ...
user202729
@lirtosiast Первая ссылка подсчитывает количество пар в 1D, вторая ссылка принимает сумму первой ссылки по всем строкам таблицы.
user202729
3

Retina 0.8.2 , 60 58 байт

1
¶1$';___¶
_
$n$%`7$*_
(.)(?=.*;(_)*)(?<-2>.)*
$1
m`^10+1

Попробуйте онлайн! Принимает ввод как 8-символьные двоичные строки, разделенные запятыми, но заголовок преобразует предоставленный формат для вас. Объяснение:

1
¶1$';___¶

Создайте все подстроки доски, начиная с ферзя. Присвойте значение маркера каждой подстроке. Редактировать: Сохранено 2 байта, оставив несколько строк мусора; они эффективно игнорируются.

_
$n$%`7$*_

Разделите каждый маркер вверх на включающий диапазон и добавьте 7 к ненулевым элементам.

(.)(?=.*;(_)*)(?<-2>.)*
$1

Удалить каждый набор символов, равный длине маркера. Это эквивалентно нахождению каждого восточного, юго-западного, южного или юго-восточного луча от каждой королевы.

m`^10+1

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

Нил
источник
3

JavaScript (ES6) + SnakeEx , 38 байт

s=>snakeEx.run('m:<*>10+1',s).length/2

Принимает участие в форме '10111000\n10101011\n10101101\n01010100\n01100101\n10001000\n01000111\n01110101'. Оказывается, SnakeEx все еще можно использовать за пределами своего первоначального испытания!

LegionMammal978
источник