How to use streams to get pairs of chess Kings that threaten each other?

Question

Although the rules of chess don't allow Kings to threaten each other, this is a good geometric analogy for the real problem.

Given the following geometry

K1 [] [] [] []
K2 K3 [] [] []
[] K4 [] K5 []

the result of the required algorithm should be a data structure with the following entries: [K1, K2], [K1, K3], [K2, K3], [K2, K4], [K3, K4].

• The order inside an entry does not matter, so [Kx, Ky] is the same as [Ky, Kx].
• The entries in the data structure don't need to be ordered.
• Kings have 0 to 8 other Kings adjacent.

The following code exists:

class King {
    Point location; // Point contains x and y fields corresponding to the grid
    Point getLocation() { return location; }
}

class Square {
    Point location;
    Point getLocation() { return location; }

    King king; // null if there is no King in the square
    King getKing() { return king; }
}

and also the utility method

static List<Square> getThreatenedSquares(Point location) { ... }

which returns the 8 Squares adjacent to the given coordinates. None of the above has to be used, it's just available.

The input is Collection<King> kingsColl, containing all Kings on the board in no relevant order (it's LinkedHashMap#values()). My current non-stream algorithm, in words, iterates over all Kings, for each one it looks at all Kings which weren't already looked at, and checks for a matching condition.

List<King> kings = new ArrayList<>(kingsColl);
if (kings.size() > 1) {
    Map<King, King> conflicts = new HashMap<>();
    for (int i = 0; i < kings.size() - 1; i++) { // if the last king has a conflict, it would show up in the other king
        King k1 = kings.get(i);
        Point loc1 = k1.getLocation();
        List<Square> adj = getThreatenedSquares(loc1);
        for (int j = i + 1; j < kings.size(); j++) { // avoids duplicates Kx <-> ky
            King k2 = kings.get(j);
            Point loc2 = k2.getLocation();
            for (Square sqr : adj) {                   // check for adjacency
                if (sqr.getLocation().equals(loc2)) {
                    conflicts.put(k1, k2);
                }
            }
        }
    }
}

This algorithm is bad because it relies on indexes and requires the creation of an index-access collection, it can't be parallelized, and it makes more checks than it needs. Note that the result here is stored in a Map, but any collection of pairs is fine (Guava included).

Iv'e tried a few ideas using streams, none of which I cared to post because they were a mess (if someone isn't convinced I will post the common "what have you tried?"). Streams tend to solve the above problem because they are implementation independent. How do I achieve this algorithm using streams?

Answer 1

This is an invitation to rethink the data structures.

Your data structure is not only inefficient, it has redundancy which is a potential source of errors. You have a collection of Square object containing a position. What happens, if two Square objects in that collection have the same position? Then, a Square instance may have a reference to a King instance, which has a Point reference on its own. What, if that position mismatches the Point of the Square or even two Square instances refer to the same King instance?

Normally, you would use either, a list of locations bearing a King, e.g. Collection<Point>, or an array or list containing objects representing the presence or absence of a King, e.g. ChessPiece[][] where ChessPiece is a stateless enum though a single King instance is sufficient for the actual task.

In its simplest, you can use a single bit to denote whether the field bears a King or is empty. This allows to represent a fixed structure like an 8x8 chess board using a single long value. And the long value allows to check the constellations intrinsically, e.g.

public static void printSituation(long board) {
    System.out.println("  ABCDEFGH");
    for(int row=1, p=63; row<=8; row++) {
        System.out.print(row+" ");
        for(int col='A'; col<='H'; col++, p--) {
            System.out.print((board&(1L<<p))!=0? "K": "-");
        }
        System.out.println();
    }
}
public static void printConstellations(long board) {
    final long horizontal=board & (board<<1) & ~0x0101010101010101L,
               vertical  =board & (board<<8),
               diagonal1 =board & (board<<9) & ~0x0101010101010101L,
               diagonal2 =board & (board<<7) & ~0x8080808080808080L;
    long bit=1L<<63;
    for(int row=1; row<=8; row++) {
        for(int col='A'; col<='H'; col++, bit>>>=1) {
            if((horizontal&bit)!=0)
                System.out.printf("(%c,%d)-(%c,%d)%n", col, row, col+1, row);
            if((vertical&bit)!=0)
                System.out.printf("(%c,%d)-(%c,%d)%n", col, row, col, row+1);
            if((diagonal1&bit)!=0)
                System.out.printf("(%c,%d)-(%c,%d)%n", col, row, col+1, row+1);
            if((diagonal2&bit)!=0)
                System.out.printf("(%c,%d)-(%c,%d)%n", col, row, col-1, row+1);
        }
    }
}
public static void main(String[] args) {
    long scenario=0x80C0500000000000L;//your actual board situation
    printSituation(scenario);
    printConstellations(scenario);
}

  ABCDEFGH
1 K-------
2 KK------
3 -K-K----
4 --------
5 --------
6 --------
7 --------
8 --------
(A,1)-(A,2)
(A,1)-(B,2)
(A,2)-(B,2)
(A,2)-(B,3)
(B,2)-(B,3)

This fits into what you called “bad because it relies on indexes”, but actually, its so cheap that it would be ridiculous to ever consider parallel processing (e.g. via Stream API). Instead, if your starting point is a collection of Point instances, it would be beneficial to convert it to the long representation, perform the analysis and convert the threat constellations back to Points.

Answer 2

Here's a way to do it using streams. I think this isolates the components to create better readability. However, If you're looking for speed, it probably has to do with a better algorithm rather than using Streams.

    List<List<King>> conflicts = kings.stream()
                                      .flatMap(k1 -> subStream(kings, k1) 
                                               .map(k2 -> Arrays.asList(k1, k2)))
                                      .filter(kingPair -> threatensEachother(kingPair))
                                      .collect(Collectors.toList());
    }


private static Stream<King> subStream(List<King> kings, King k1) {
    return kings.subList(kings.indexOf(k1) + 1, kings.size()).stream();
}

private static boolean threatensEachother(List<King> kingPair) {
      List<Square> k1Squares = getThreatenedSquares(kingPair.get(0).getLocation());
      List<Square> k2Squares = getThreatenedSquares(kingPair.get(1).getLocation());
    return sqauresOverlap(k1Squares, k2Squares);
}

private static boolean squaresOverlap(List<Squares> k1Squares, List<Squares> k2Squares) {
    return k1Squares.stream()
                    .anyMatch(k1Square -> k2Squares.contains(k1Square).
}

Answer 3

UPDATE

I've created some code that does what you want without comparing indexes:

List<King> kings = new ArrayList<>(kingsColl);
Map<King,List<King>> conflicts = kings.parallelStream() //Initiating Stream API (Stream<King>)
                                .collect(Collectors.toMap( //To Map
                                         Function.identity(), //Return the king we are going through.
                                         king -> getThreatenedSquares(king.getLocation())));// Use the getThreatenedSquares function.

Then all that is needed is a small change to getThreatenedSquares which instead of returning the Squares, it returns the Kings that are threatened utilizing the getKing() method:

static List<King> getThreatenedSquares(Point location) {
    //Same Code until the end...
    List<King> toReturn = yourSquareList.parallelStream() //Initiating Stream API
                                 .map(square -> square.getKing())//Transforming Square to King.
                                 .filter(king -> king!=null)//Removing squares with no King.
                                 .collect(Collectors.toList());
    return toReturn;
}

This solution can be used for any type of "piece" since all pieces will theoretically extend a common parent, the type of which the returned list can be.

ORIGINAL ANSWER:

Your algorithm makes a lot of extra checks simply because it checks all 9 squares adjacent to the King. For the following co-ordinates:

[0,0] [0,1] [0,2]
[1,0] [1,1] [1,2]
[2,0] [2,1] [2,2]

Where [1,1] notes the point where the King is "seated", the only squares that need to be checked are [1,2], [2,0], [2,1] and [2,2] marked by X in the following snippet.

[O] [O] [O]
[O] [O] [X]
[X] [X] [X]

The reason is that you only need to "move" forward when checking since if a king was in point [1,0], [0,0], [0,1] and [0,2], your king in position [1,1] would have been found by them since they also followed the above searching pattern.

In order for the searching pattern to function correctly, the Kings must be sorted within the List based on their position on the board. Specifically, the first entry in "kings" must be the left-most, top-most seated King with top-most taking priority (For a Cartesian Plane of XY coordinates, a King seated in point [0,2] would be first in the list compared to a King seated in point [1,0]).

You can further limit the iterations your loops do by using a simple "if" before the Square loop which checks 2 conditions, if the x1-x2 and y1-y2 distances are bigger than 2, and skips the current iteration with continue; Since Kings can only move one block, there is no need to iterate over the Squares if it is impossible for the Kings to attack each other.