C#

Fools ignore complexity; pragmatists suffer it; experts avoid it; CREATIVES remove it.

Saturday, August 25, 2007

Tic Tac Toe - checking winner without matrices



Recently I was interviewed for a big company, (no names here); it was an exciting and interesting interview by phone; the recruiter started asking me about linked lists, data structures, collisions trees, path finding, etc… It was strange talking about code by phone, I had never been interviewed that way before, not by phone; worst than that I was under strong medicines, I had caught a cold one night before, summarizing, that was not my day, during interview one of the questions allowed me show to recruiter exactly how I’m used to think, He asked me:

"How would you implement the rules of a Tic Tac Toe game?"

He asked me to think while telling him what I was thinking. I was under pressure and doesn’t matter how much recruiter tried to calm down it was still an interview for a big company, describing code techniques by phone, so I started answering conventional way, I meaning not the way I'm used to do, (creative way), I started creating a 3x3 matrices considering game positions, etc… suddenly some voice inside of me started screaming: “Wake up Flavio! What you are doing! that’s your opportunity to show how you think, don’t fear, don’t be conventional!” Instantly I started thinking the way as I’m used to do, I'm used to think visually first, metaphorical way second, design third and coding at last so I said to recruiter: “Forget everything you heard I would like to start again, Tic Tac Toe is a game which the rules are fixed, it never changes, you can visualize board so that, you can see results visually and map them all in any place, its about 8 possibilities of victory starting count after three choices, a bit field should work fine for that" so I suggested a bit field which would avoid matrices manipulation overhead. I felt some “what? show me the money” feeling coming from other phone line, and He asked me to tell him the code for this, by phone, He asked me to write the code in a piece of paper, or compiler, or any text editor and keep telling him what I was writing and thinking, well, I was not comfortable, I was sick and under pressure and I was not able to do the code that time, after sleep a little and wake up better here is the code.




// tictactoe.cpp : This code is only for illustrate an idea.
// 08/26/2007 by flavio.rodriguez@gmail.com

#include "stdafx.h"
#include <iostream>

#define TEST_IF_PLAYER_WIN(playerMoves, bitTest) (playerMoves&bitTest) == bitTest

using namespace std;

/*

Mapping Tic Tac Toe victory possibilities

X|X|X = 111
0|0|0 = 000
0|0|0 = 000
-----------
111000000

0|0|0 = 000
X|X|X = 111
0|0|0 = 000
-----------
000111000

0|0|0 = 000
0|0|0 = 000
X|X|X = 111
-----------
000000111

X|0|0 = 100
X|0|0 = 100
X|0|0 = 100
-----------
100100100

0|X|0 = 010
0|X|0 = 010
0|X|0 = 010
-----------
010010010

0|0|X = 001
0|0|X = 001
0|0|X = 001
-----------
001001001

X|0|0 = 100
0|X|0 = 010
0|0|X = 001
-----------
100010001

0|0|X = 001
0|X|0 = 010
X|0|0 = 100
-----------
001010100

*/

typedef struct
{
unsigned long _LD : 9; // 111000000
unsigned long _LM : 9; // 000111000
unsigned long _LU : 9; // 000000111

unsigned long _CL : 9; // 100100100
unsigned long _CM : 9; // 010010010
unsigned long _CR : 9; // 001001001

unsigned long _LR : 9; // 100010001
unsigned long _RL : 9; // 001010100

}WINNING;

int _tmain(int argc, _TCHAR* argv[])
{
WINNING win;

//The 8 victory possibilites
win._LD = 0x1C0;
win._LM = 0x38;
win._LU = 0x7;
win._CL = 0x124;
win._CM = 0x92;
win._CR = 0x49;
win._LR = 0x111;
win._RL = 0x54;

/*
* Although this code works it was made as pseudo, I mean no structure or functions,
* the objective here is just check victory
* then imagine a player called A
*/
unsigned long playerA = 0;

/*
each quad represents a position in game

| | | |
|--|--|--|
| | | |
|--|--|--|
| | | |

and here is their relative values

|1 | 2| 4|
|--|---|---|
|8 | 16| 32|
|--|---|---|
|64|128|256|
*/

/*
* Now you can simulate any player move;
* in case of two players, we should just to create a player called B
* each time player click a quad, a bit is incremented
* and that would begin to be tested after the third move, once
* before that time we don't know winner
*/

//player move - Good choice
playerA |= 64;
//play move - Good Choice
playerA |= 128;
//play move - Bad choice
playerA |= 2;
//play move - good choice you won!
playerA |= 256;

//CHECKING VICTORY
//please, FOR SURE it would be in a function
//its only to illustrate
if (TEST_IF_PLAYER_WIN( playerA, win._LD ))
cout << "WON LINE DOWN" << endl;
else if (TEST_IF_PLAYER_WIN( playerA, win._LM ))
cout << "WON LINE MIDDLE" << endl;
else if (TEST_IF_PLAYER_WIN( playerA, win._LU ))
cout << "WON LINE UP" << endl;
else if (TEST_IF_PLAYER_WIN( playerA, win._CL ))
cout << "WON COL LEFT" << endl;
else if (TEST_IF_PLAYER_WIN( playerA, win._CM ))
cout << "WON COL MIDDLE" << endl;
else if (TEST_IF_PLAYER_WIN( playerA, win._CR ))
cout << "WON COL RIGHT" << endl;
else if (TEST_IF_PLAYER_WIN( playerA, win._LR ))
cout << "WON LEFT TO RIGHT" << endl;
else if (TEST_IF_PLAYER_WIN( playerA, win._RL ))
cout << "WON RIGHT TO LEFT" << endl;

return 0;
}



Learned lessons, never to be interviewed sick!

That's it! stay creative!