I’m rather obsessed with bits. All sorts of bits, at various times, but in particular, the digital bit of the Binary system. Notice the capitalization of “Binary” - it is intended. Efficient bit representations of information is purity ; ever more compact representations elegance itself, so for this post I invite you to come with me, way back to 2013, when a nice couple of bitwise operations flaunted their power and expressiveness.
It’s tough for me when a value that will only ever require N distinct states gets over represented by vastly more bits than is needed. A 4-byte integer to store a human age, a UUID, with it’s crazy 16 bytes, and the list goes on and on: we can do better! Think of the real, actual small value, arriving inside the 64-bit CPU register, and the wasteful runs of zeros. Think of it, happening billions and billions of times a second. We can only hope that somewhere along the way, things get packed in a bit to mitigate those wasted runs of zeros.
Once I read that using a short, or 2-byte database column type or variable is actually not more performant than just using a 4-byte integer. Due to the fact that the smallest addressable space is anyways 4 bytes large, it took exactly the same resources to process 4, 2 or even a 1 byte word. The exact context of that claim escapes me. I put it down to my confirmation bias, operating sub consciously, blocking it out. I like my confirmation bias working for me like that.
The back story
It was the weekend of the Google CodeJam qualifier. Having heard of it some weeks before, I planned to check out the rules properly, and do some practice problems. It never happened. Arriving home in the afternoon on the Saturday, I thought I did not have much of a chance at it due to the time constraint, but I could not help myself giving it a go anyways. So it happened. Pacing around in my flat, beer in hand, I chose this little problem to solve. It was a sort of tic-tac-toe variant, but only the board state identifier part.
Given a 4-x-4 board, determine if either player is in the winning position, or if a tie occurred. The ’T’ symbol being neutral in that it could count in either player’s favor.
Yes, you can loop over the elements or throw a Linq expression at it, but hey, we can have more fun than that, with bit masks and bit shifts. This was bit mask land, and I was in my element! For more details about the problem, visit the problem statement.
Bit boards
We choose an integer, 4 bytes, to store a bit mask of the player O, player X, how a column looks, how each of the two diagonals look and so on. We could have used a 2-byte unsigned short instead of an int, sadly we didn’t. Well, got to leave something for next time.
public static int column, diagonal1, diagonal2, fullboard;
and
int xboard = 0, oboard = 0, tboard = 0;
We assign the static patterns we’ll use for column, the two diagonals and the full board:
column = Convert.ToInt32("1000100010001", 2);
diagonal1 = Convert.ToInt32("1000010000100001", 2);
diagonal2 = Convert.ToInt32("0001001001001000", 2);
fullboard = Convert.ToInt32("1111111111111111", 2);
I’m not going to bother you with file IO, so we skip to where we set the X, O and T boards:
xboard = StringBoardToBitBoard(line, 'X');
oboard = StringBoardToBitBoard(line, 'O');
tboard = StringBoardToBitBoard(line, 'T');
Function StringBoardToBitBoard does exactly what you would imagine - it assigns a ‘1’ in the bit position if the char occurs and a ‘0’ otherwise - see below for the full program.
Decision and output
if (Won(xboard, tboard))
sw.WriteLine("Case #{0}: X won", i);
else if (Won(oboard, tboard))
sw.WriteLine("Case #{0}: O won", i);
else if (((xboard | oboard | tboard) & fullboard) == fullboard)
sw.WriteLine("Case #{0}: Draw", i);
else
sw.WriteLine("Case #{0}: Game has not completed", i);
The real magic: bitwise operators and shifts
And finally, let’s have a look at the elegant part; function Won and friends:
public static bool Won(int board, int tboard)
{
board |= tboard; // apply the T position
return LinesMatch(board) || ColumnsMatch(board) || DiagonalsMatch(board);
}
makes sense doesn’t it; you win if you have a line, a column or a diagonal.
public static bool LinesMatch(int board)
{
return board == (board | 15)
|| board == (board | (15 << 4))
|| board == (board | (15 << 8))
|| board == (board | (15 << 12));
}
You have a lines match if your board position is logical OR-ed (the ‘|’ operator) with any of the line representations, and still is equal to itself. For the 4 line representations we could have used constants, to avoid the bit shift (’<<‘) but defining them; that would be too laborious, but would probably have been better. Also, the 15 magic number in there, for the first lines representation; should really live in a constant.
In the same way, but slightly different, the columns and diagonals are checked:
public static bool ColumnsMatch(int board)
{
return
board == (board | column)
|| board == (board | (column << 1))
|| board == (board | (column << 2))
|| board == (board | (column << 3));
}
public static bool DiagonalsMatch(int board)
{
return board == (board | diagonal1)
|| board == (board | diagonal2);
}
The diagonals checking could have happened all at once, why is this possible?
Conclusion
Well, contrary to the confusion to what a casual glance of the code might evoke in you, it’s really not terribly convoluted, but possibly slightly so. The heart of the program is only one loop over the input set, while the win checking is a small constant set of finite bit operations, and bit operations can definitely be implemented as single machine instructions. It surely ran fast on the small and large inputs, and so this question I got right.
Not realizing that one only needed to get some of the problems correct in order to qualify for the actual contest, I happily shut down my computer and went to sleep. Yay, I managed to do one of the CodeJam qualifier challenges, but there were no time to do all of them! The next week when I realized my mistake, I was upset. I just had to get one or two more right and I could possibly have qualified!
Less is more. The saxophonist Jan Garbarek has been credited with his “generous use of silence”. I like that. May it be that, when people survey our code and data representations, may it be that they would reflect upon how few bits was used, or how few lines of code were written…
Full program
using System;
using System.IO;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace ConsoleApplication1
{
class Program
{
public static int column, diagonal1, diagonal2, fullboard;
static void Main(string[] args)
{
column = Convert.ToInt32("1000100010001", 2);
diagonal1 = Convert.ToInt32("1000010000100001", 2);
diagonal2 = Convert.ToInt32("0001001001001000", 2);
fullboard = Convert.ToInt32("1111111111111111", 2);
int xboard = 0, oboard = 0, tboard = 0;
try
{
string infile = "A-large.in", outfile = "A-large.out", line = "";
using (StreamReader sr = new StreamReader(infile))
{
using (StreamWriter sw = new StreamWriter(outfile))
{
int numberOfProblems = Int32.Parse(sr.ReadLine());
for (int i = 1; i <= numberOfProblems; i++)
{
line = sr.ReadLine();
line += sr.ReadLine();
line += sr.ReadLine();
line += sr.ReadLine();
xboard = StringBoardToBitBoard(line, 'X');
oboard = StringBoardToBitBoard(line, 'O');
tboard = StringBoardToBitBoard(line, 'T');
if (Won(xboard, tboard))
sw.WriteLine("Case #{0}: X won", i);
else if (Won(oboard, tboard))
sw.WriteLine("Case #{0}: O won", i);
else if (((xboard | oboard | tboard) & fullboard) == fullboard)
sw.WriteLine("Case #{0}: Draw", i);
else
sw.WriteLine("Case #{0}: Game has not completed", i);
line = sr.ReadLine();
}
}
//Console.WriteLine(line);
}
}
catch (Exception e)
{
}
}
public static bool Won(int board, int tboard)
{
board |= tboard; // apply the T position
return LinesMatch(board) || ColumnsMatch(board) || DiagonalsMatch(board);
}
public static bool LinesMatch(int board)
{
return board == (board | 15)
|| board == (board | (15 << 4))
|| board == (board | (15 << 8))
|| board == (board | (15 << 12));
}
public static bool ColumnsMatch(int board)
{
return
board == (board | column)
|| board == (board | (column << 1))
|| board == (board | (column << 2))
|| board == (board | (column << 3));
}
public static bool DiagonalsMatch(int board)
{
return board == (board | diagonal1)
|| board == (board | diagonal2);
}
public static int StringBoardToBitBoard(string stringBoard, char oneChar)
{
string bitBoard = new String(stringBoard.Select(
x => x == oneChar ? '1' : '0')
.ToArray());
return Convert.ToInt32(bitBoard, 2);
}
}
}