Yesterday I got linked to an article with interview questions for engineers and problem solvers at google including this one about tic-tac-toe.
The problem is to write a function which takes as arguments a Game of tic-tac-toe and a player, and returns whether the player has won the game. As an extension I wanted to do it in the most efficient way I could.
My first thought on reading it was that an sequence of bits could be used to store the state of the game for each player. Then the is_winner(Game, player) function would only have to test the bits for that player to see if the Xs or Os are in the right place to declare a win. As that would mean nine bits for each player, you would either need two 8 bit words each, or one each with a third shared between them to represent the extra bit.
Eventually I managed to squeeze the game into two 8-bit words which contain the state of play, but before I post and describe mine, I’ll give others the opportunity to do the same. To prevent cheating and so you know I didn’t steal your idea, make sure to save this somewhere I can’t tamper with it:
$ sha1sum tic_tac_toe.cpp