Fast 15x15 bit grid BFS: breadth first search

Fast 15x15 bit grid BFS: breadth first search

Update: 06.04.2020: Mlomb found several bugs in the code with his testing. Assignment to return value was too late (after break). There was a bit shift in incorrect direction. Initialization of available was incorrect (missing a few bits: 2 * 15 != 264 - 15 * 15 hehe). Performance suffered a bit with these corrections, but still getting around 1 million. After these corrections mlomb tested the code against his own BFS implementation and validated with 0 errors of 999901 test cases.

We represent a 15x15 grid as 4 64 bit unsigned integers. The last column, 16th, and row, also 16th, should always be empty.

Each presence of anything on the map is represented as a bit set to 1 and absence of anything is the bit set to 0. To get the neighbours of current set cells we shift bits left, right, up or down and then to get both we take the union with current set cells (bitwise or). To restrict from going into unavailable cells we do intersection (bitwise and) with inversion (bitwise not) of unavailable cells. As we said the last row and column are unavailable, and also "islands" (in this case for Ocean of Code) are unavailable.

The optimization idea is to split the board into white and black cells by odd and even indices, like a chess board. In that way black cells only have white neighbours and white cells only have black neighbours.

So the first 64 bit int (index 0) contains cells where x is even and y is even, i.e white cells. The second 64 bit int (index 1) contains cells where x is odd and y is even, i.e. black cells. The third 64 bit int (index 2) contains cells where x is even and y is odd, i.e. black cells. The fourth 64 bit int (index 3) contains cells where x is odd and y is odd, i.e. white cells.

For certain 2.4 GHz servers on CodinGame you can get between 1.5 and 2 million BFSes per seconds. For the 2.2 GHz server it's around 1.3-1.4 million. On tech.io it is much slower for some reason, a few hundred k is all you get it seems.

You no longer should have to worry about whether starting cell is black or white. Code has been modified at expense of a tiny bit of performance. If you know whether your starting cell is black or white you can optimize the code to make the first expansion from black to white or white to black accordingly.