26
\$\begingroup\$

Let an 8x8 chessboard be represented by any two distinct values, with one value being an empty square and the other being a queen. In the following examples, I use 0s as the empty squares and 1s as queens. For example:

Queens on a chessboard

is given by

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

Consider the number of pairs of queens that are attacking each that are at least one square away (as a reminder, queens attack orthogonally and diagonally). In the above example, the following incredible ugly diagram shows all these pairs as arrows.

Attacking queens

There are 43 pairs found above giving the following test case:

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

Challenge

Write a program that, given a board state represented by two distinct values, outputs the number of pairs of queens that attack each other with at least one square in between them.

  • You may input in whatever format is most convenient that uses two values to represent the empty squares and queens, e.g., a string of 64 "."s for empty squares and "Q"s for queens by rows from bottom to top, an 8x8 matrix of booleans, a list of list of integers 0 and 1 etc, as long as it is explained in your solution
  • Output is an integer
  • Standard I/O methods apply and standard loopholes forbidden
  • This is code golf so shortest answer in bytes wins

Test cases:

Using the 0 and 1 format, with 0 being empty squares and 1 being queens:

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
\$\endgroup\$
  • \$\begingroup\$ I should have asked before posting my 2nd version: are 254 for a queen and 0 for an empty square acceptable input values? \$\endgroup\$ – Arnauld May 6 '18 at 14:15
  • \$\begingroup\$ @Arnauld You may input in whatever format is most convenient that uses two values to represent the empty squares and queens. So that's fine for sure \$\endgroup\$ – JMigst May 6 '18 at 15:00
  • \$\begingroup\$ Thanks. I asked because I think this rule might be a bit too permissive if taken literally. I could ask to pass a string containing most of the JS code for queens and just evaluate that in the program. (But it may be prevented by a default loophole. I'm not sure.) \$\endgroup\$ – Arnauld May 6 '18 at 15:09
14
\$\begingroup\$

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

Try it online!

Explanation

We take the input as a string of 64 characters '0' or '1'. Using step slices, we cast four "lines of sight" from every queen we encounter. For example, when i = 10 and d = 7, marking the queen as ♥ and the tiles selected by b[i+d::d] as █:

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

Clearly, we don't actually want vision to wrap around the board like this. So we compute how far away the edge of the board is in each direction, and view the tiles at b[i+d::d][:…].

For each tile-direction pair we count:

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

This will fail whenever

  • c is not a queen; or
  • the queen this ray sees is too close (find returns 0); or
  • this ray sees no queen (find returns −1).

Each pair of queens is only checked once, since rays are always casted forward in reading order, from an "earlier" queen to a "later" one.

\$\endgroup\$
10
\$\begingroup\$

JavaScript (ES7), 86 bytes

Takes input as an array of 64 integers with 254 for a queen and 0 for an empty square.

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

Try it online!

This version abuses arithmetic underflow to get a stop condition in the recursive part.


JavaScript (ES7), 89 bytes

Takes input as an array of 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

Try it online!

How?

We recursively call a named callback function of map() to walk through the squares in a given direction. Although we don't really need the content of the third parameter of the callback (the array map() was called upon), we indirectly use it nonetheless to know whether it is the first iteration or not.

arr.map(function callback(currentValue[, index[, array]])

This is the x variable in the code.

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
\$\endgroup\$
8
\$\begingroup\$

Snails, 14 bytes

A
rdaa7\1\0+\1

Try it online!

Input is the 0/1 format, without spaces within lines.

Snails was created for a 2D pattern matching language design PPCG challenge. Most importantly, it by default outputs the number of matches found, which is perfect for this challenge.


A sets the "all paths" option, so that if a queen is in multiple pairs, each of those pairs would generate a match.

rdaa7 sets the match direction to S, SE, E, and NE. Setting to all directions (z) would cause double counting.

\1\0+\1 matches a 1, then one or more 0s, then another 1.

\$\endgroup\$
6
\$\begingroup\$

APL (Dyalog Classic), 41 39 32 bytes

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

Try it online!

≠⍨ is "not equal to itself" - an 8x8 all-zero matrix

⊢,≠⍨,⌽,≠⍨ - if the original matrix is ABC..., this expression returns:

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⍴ reshapes it from 8x32 to 8x31, reusing the elements in row-major order:

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

⊢,⍉, prepends the original matrix and its transpose (extra spaces for clarity):

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⍪ adds 0s on top and compares using < every element against the element below it, so we get a 1 for the leading 1 in every vertical group of 1s, and we get 0s everywhere else

+⌿-⌈⌿ the sums by column minus the maxima by column - we compute the number of gaps between the 1-groups in every column, 0 if there are none

+/ sum

\$\endgroup\$
5
\$\begingroup\$

Jelly, 22 20 bytes

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

Try it online!

\$\endgroup\$
  • \$\begingroup\$ How does this work? \$\endgroup\$ – lirtosiast Nov 27 '18 at 9:59
  • \$\begingroup\$ @lirtosiast I don't remember... \$\endgroup\$ – user202729 Nov 27 '18 at 10:10
  • \$\begingroup\$ @lirtosiast The first link counts number of pairs in 1D, the second link takes the sum of the first link over all lines in the table. \$\endgroup\$ – user202729 Nov 27 '18 at 10:12
3
\$\begingroup\$

Retina 0.8.2, 60 58 bytes

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

Try it online! Takes input as 8 comma-separated 8-character binary strings, but the header converts the provided format for you. Explanation:

1
¶1$';___¶

Create all of the substrings of the board starting at a queen. Suffix a marker value to each substring. Edit: Saved 2 bytes by leaving some garbage strings behind; these are effectively ignored.

_
$n$%`7$*_

Split each marker up into an inclusive range, and add 7 to the non-zero elements.

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

Delete every run of characters that equals the length of the marker. This is equivalent to finding each east, southwest, south or southeast ray from each queen.

m`^10+1

Count all the rays that pass through at least one empty square before meeting another queen.

\$\endgroup\$
3
\$\begingroup\$

JavaScript (ES6) + SnakeEx, 38 bytes

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

Takes input in the form '10111000\n10101011\n10101101\n01010100\n01100101\n10001000\n01000111\n01110101'. Turns out, SnakeEx can still be used outside of its original challenge!

\$\endgroup\$
2
\$\begingroup\$

K (ngn/k), 45 bytes

{+/0|-1++/0|-':x,'+x,+8 31#,/+x,a,(|x),a:0*x}

Try it online!

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.