Rainhas que atacam mutuamente

26

Deixe um tabuleiro de xadrez 8x8 ser representado por quaisquer dois valores distintos, sendo um valor um quadrado vazio e o outro uma rainha. Nos exemplos a seguir, eu uso 0s como quadrados vazios e 1s como rainhas. Por exemplo:

Rainhas em um tabuleiro de xadrez

É dado por

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

Considere o número de pares de rainhas que estão atacando cada uma a pelo menos um quadrado de distância (como lembrete, as rainhas atacam ortogonal e diagonalmente). No exemplo acima, o diagrama feio incrível a seguir mostra todos esses pares como setas.

Rainhas atacantes

Existem 43 pares encontrados acima, fornecendo o seguinte caso de teste:

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

Desafio

Escreva um programa que, dado um estado da placa representado por dois valores distintos, produza o número de pares de rainhas que se atacam com pelo menos um quadrado entre elas.

  • Você pode inserir em qualquer formato que seja mais conveniente que use dois valores para representar os quadrados e rainhas vazios, por exemplo, uma sequência de 64 "." S para quadrados vazios e "Q" s para rainhas por linhas de baixo para cima, um 8x8 matriz de booleanos, uma lista de números inteiros 0 e 1 etc, contanto que seja explicado em sua solução
  • A saída é um número inteiro
  • Os métodos de E / S padrão se aplicam e as brechas padrão são proibidas
  • Este é o código de golfe, então a resposta mais curta em bytes ganha

Casos de teste:

Usando o formato 0 e 1, com 0 sendo quadrados vazios e 1 sendo rainhas:

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
code-golf chess binary-matrix JMigst
fonte
Eu deveria ter perguntado antes de postar minha segunda versão: são 254 para uma dama e 0 para um quadrado vazio valores aceitáveis ​​de entrada?
Arnauld
@ Arnauld Você pode inserir o formato que for mais conveniente, usando dois valores para representar os quadrados e rainhas vazios. Então, isso é bom, com certeza
JMigst
Obrigado. Eu perguntei, porque acho que essa regra pode ser um pouco permissiva se tomada literalmente. Eu poderia pedir para passar uma string contendo a maior parte do código JS para rainhas e apenas avaliar isso no programa. (Mas pode ser prevenida por uma brecha padrão não tenho certeza..)
Arnauld

Respostas:

14

Python 2 , 105 bytes

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

Experimente online!

Explicação

Tomamos a entrada como uma sequência de 64 caracteres '0'ou '1'. Usando fatias de passos, lançamos quatro "linhas de visão" de cada rainha que encontramos. Por exemplo, quando i = 10 e d = 7 , marcação a rainha como ♥ e as telhas seleccionados por b[i+d::d]como █:

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

Claramente, na verdade não queremos que a visão envolva esse quadro. Então calculamos a que distância a borda do quadro está em cada direção e vemos os blocos em b[i+d::d][:…].

Para cada par de direção da telha, contamos:

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

Isso falhará sempre

  • cnão é uma rainha; ou
  • a rainha que este raio vê está muito perto ( findretorna 0); ou
  • esse raio não vê rainha ( findretorna -1).

Cada par de rainhas é verificado apenas uma vez, uma vez que os raios são sempre lançados para a frente em ordem de leitura, de uma rainha "anterior" para uma "posterior".

Lynn
fonte
10

JavaScript (ES7), 86 bytes

Recebe a entrada como uma matriz de 64 números inteiros, com 254 para uma rainha e 0 para um quadrado vazio.

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

Experimente online!

Esta versão abusa do underflow aritmético para obter uma condição de parada na parte recursiva.

JavaScript (ES7), 89 bytes

Recebe a entrada como uma matriz de 64 bits.

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

Experimente online!

Quão?

Chamamos recursivamente uma função de retorno de chamada nomeada de map()para percorrer os quadrados em uma determinada direção. Embora realmente não precisemos do conteúdo do terceiro parâmetro do retorno de chamada (a matriz map()foi chamada), indiretamente, ainda assim o usamos para saber se é a primeira iteração ou não.

arr.map (retorno de chamada da função (currentValue [, index [, array]])

Essa é a variável x no código.

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
fonte
8

Caracóis , 14 bytes

A
rdaa7\1\0+\1

Experimente online!

Entrada é o formato 0/1, sem espaços dentro de linhas.

O Snails foi criado para um desafio PPCG de design de linguagem de correspondência de padrões 2D . O mais importante é que, por padrão, gera o número de correspondências encontradas, o que é perfeito para esse desafio.

A define a opção "todos os caminhos", de modo que, se uma dama estiver em vários pares, cada um desses pares gerará uma correspondência.

rdaa7define a direção da correspondência como S, SE, E e NE. Definir todas as direções ( z) causaria uma contagem dupla.

\1\0+\1corresponde a 1, depois um ou mais 0s e depois outro 1.

TwiNight
fonte
6

APL (Dyalog Classic) , 41 39 32 bytes

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

Experimente online!

≠⍨ é "diferente de si mesmo" - uma matriz 8x8 totalmente zero

⊢,≠⍨,⌽,≠⍨- se a matriz original for ABC..., esta expressão retornará:

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⍴ remodela de 8x32 para 8x31, reutilizando os elementos na ordem principal da linha:

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

⊢,⍉, precede a matriz original e sua transposição (espaços extras para maior clareza):

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⍪adiciona 0s na parte superior e compara o uso de <todos os elementos com o elemento abaixo, para obter um 1 para o 1 líder em cada grupo vertical de 1s e obter 0s em qualquer outro lugar

+⌿-⌈⌿ as somas por coluna menos os máximos por coluna - calculamos o número de lacunas entre os grupos 1 em cada coluna, 0 se não houver

+/ soma

ngn
fonte
5

Geléia , 22 20 bytes

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

Experimente online!

user202729
fonte
Como é que isso funciona?
lirtosiast
@lirtosiast Eu não me lembro ...
user202729
@lirtosiast O primeiro link conta o número de pares em 1D, o segundo link soma a soma do primeiro link em todas as linhas da tabela.
user202729
3

Retina 0.8.2 , 60 58 bytes

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

Experimente online! Recebe a entrada como 8 cadeias binárias de 8 caracteres, separadas por vírgula, mas o cabeçalho converte o formato fornecido para você. Explicação:

1
¶1$';___¶

Crie todas as substrings do tabuleiro começando em uma dama. Sufixe um valor de marcador a cada substring. Editar: salvou 2 bytes, deixando algumas seqüências de lixo para trás; estes são efetivamente ignorados.

_
$n$%`7$*_

Divida cada marcador em um intervalo inclusivo e adicione 7 aos elementos diferentes de zero.

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

Exclua todas as séries de caracteres que sejam iguais ao comprimento do marcador. Isso é equivalente a encontrar cada raio leste, sudoeste, sul ou sudeste de cada rainha.

m`^10+1

Conte todos os raios que passam por pelo menos um quadrado vazio antes de encontrar outra rainha.

Neil
fonte
3

JavaScript (ES6) + SnakeEx , 38 bytes

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

Recebe entrada no formulário '10111000\n10101011\n10101101\n01010100\n01100101\n10001000\n01000111\n01110101'. Acontece que o SnakeEx ainda pode ser usado fora do seu desafio original!

LegionMammal978
fonte