Tic Tac Toe Bonanza

I have been staffing teams, coaching and interviewing for a long time and at multiple stages of those processes, I have always notices either about myself or my colleagues the application of some old habits.

Most recently a reader of this blog asked my opinion for an upcoming developer interview loop at a major corp. That led me to come up with a post on the subject.

In basic terms, as a developer, you should expect to go through the following cycle of r knowledge.

• Warm-Up Question(s)
• Data Structures
• Analytical Thinking
• Algorithms

In 20 years of experience that has been always an observed pattern in hiring a developer. If they don’t then doubt the company that is hiring you to be on the safe side. That usually also translates, and I can only generalize as the job description craft that flows as necessary, with the following practical questions:

1. Reverse a string, quicksort
2. Hash table, linked list, a queue of some kind
3. How much gift wrapping paper is used during holiday time?
4. Map reduce, cryptography and so on

#1 is used for jump start your brain from the panic phase to get used to the panic room, the whiteboard and your absence of saliva. If you fail that your odds are getting worst big time.

#2 Is a key assessment of your foundations about coding. That includes coding style (camel syntax vs others), ability to explain your own code as you go. Multi-tasking attitude as it is always recommended to describe what you are going to do before you do it. Time is of the essence!

#3 How do you solve problems that seem either too stupid for an interview or that seems to impossible for any conversation between humans?! The goal here is to understand how analytical you are, how many angles you evaluate and how you put your conclusions together and my favorite, in which priority order.

#4 granted that you don’t build an algorithm from scratch every other day however not every nail as an exact hammer, therefore, understand if you are a cookie-cutter man or out of the box thinker is important, when the job description requires that type of talent. Often does not and they do it anyway :-)

I always found that the best way to understand and memorize, not one or the other, that is useless to your career and your future manager, is to figure out a simple project that is fun and at same time forces those two elements to play together and crystalize knowledge in your head.

A game such Tic Tac Toe, at least for this post fits the bill perfectly. There’s always a way to the do something better and in multiple way, what I am going to share with this post is one of them, is generic but is academical vetted. It should serve you well to grasp the concept and most important lead your learning in the context of the lists made above.

We’re going to build a Tic Tac Toe game in C#, Swift and Objective-C from scratch. I will split this goal across multiple posts so I can go in details for each one of those experience.

Let’s play!

The Algorithm

The algorithm is useful for finding both a winning and a blocking move in tic-tac-toe (aka T3).

A T3 board can be represented as a magic square (a recreational math concept) where every cell is represented by a unique integer in the range 1 to 9. 

Every row, column, and diagonal sums to 15, and it is not possible to get a sum of 15 from three cells unless they share a row, column or diagonal. With this representation, a potential move is evaluated as a winning move by checking whether it produces a sum of 15 with exactly two other cells occupied by the same player.

A program can check for a block by checking whether the potential move produces a sum of 15 with exactly two other cells occupied by the opposing player.

For each player, two boolean arrays are maintained. TAKEN and PAIRS. 

Array taken keeps track of those cells occupied by each player. The number of vector in the array is 9. Each array element is initialized to false. When a player makes a move the array element corresponding to a cell that matches the same spot/number on the board is set to true.

Array pairs keep track of two-in-a-row combinations for the player. This information is represented by recording all sums consisting of two cells occupied by the player. 

This array needs to be indexed from 3 to 17 (two steps ahead) and with each element initialized to false. When a player makes a move, all resulting sums are recorded in the player’s pairs array, as in:

     for (int k=1, k<=9; k++) if (taken[k]) pairs[move + k] = true;

Many of the recorded pairs do not share the same row, column or diagonal (such as 8 and 9). Recording this information does not hurt our solution and is more efficient than incurring the overhead of testing each pair for collinearity.

In the next post, we’re going to implement the algorithm in one of the mentioned languages and platforms. In the meanwhile don’t forget to resume from your video library what actually really brought me to think about this game!!