Thursday, May 24, 2012

My experiments with tic tac toe


Was writing a tic tac toe app for android recently as was familiar with the rules of the game :-).
The last time I wrote a tic tac toe game was in college time, and then most focus was on the gui design. The lousiest algorithm in the background.

One of the algorithm was to check the state of the game i.e win or draw etc. Gave it a thought this time and  made some optimization in the row, col, diagonal checks. Its mainly decided in the first nested loop if we need to check a particular column or diagonal. So, we avoid checking of columns or diagonals saving time. This makes big impact when the board size is more and a significant number of the cells are not filled.


Next time I will post the nextMove implementation, for the computer to decide its next move.

Here is the java code for the gamestate algorithm.

  int gameState(int values[][], int boardSz) {


boolean colCheckNotRequired[] = new boolean[ boardSz ];
boolean diag1CheckNotRequired = false;
boolean diag2CheckNotRequired = false;
boolean allFilled = true;


int x_count = 0;
int o_count = 0;
/* Check rows */
for (int i = 0; i < boardSz; i++) {
x_count = o_count = 0;
for (int j = 0; j < boardSz; j++) {
if(values[i][j] == x_val)x_count++;
if(values[i][j] == o_val)o_count++;
if(values[i][j] == 0)
{
colCheckNotRequired[j] = true;
if(i==j)diag1CheckNotRequired = true;
if(i + j == boardSz - 1)diag2CheckNotRequired = true;
allFilled = false;
//No need check further
break;
}
}
if(x_count == boardSz)return X_WIN;
if(o_count == boardSz)return O_WIN;
}


/* check cols */
for (int i = 0; i < boardSz; i++) {
x_count = o_count = 0;
if(colCheckNotRequired[i] == false)
{
for (int j = 0; j < boardSz; j++) {
if(values[j][i] == x_val)x_count++;
if(values[j][i] == o_val)o_count++;
//No need check further
if(values[i][j] == 0)break;
}
if(x_count == boardSz)return X_WIN;
if(o_count == boardSz)return O_WIN;
}
}

x_count = o_count = 0;
/* check diagonal 1 */
if(diag1CheckNotRequired == false)
{
for (int i = 0; i < boardSz; i++) {
if(values[i][i] == x_val)x_count++;
if(values[i][i] == o_val)o_count++;
if(values[i][i] == 0)break;
}
if(x_count == boardSz)return X_WIN;
if(o_count == boardSz)return O_WIN;
}

x_count = o_count = 0;
/* check diagonal 2 */
if( diag2CheckNotRequired == false)
{
for (int i = boardSz - 1,j = 0; i >= 0 && j < boardSz; i--,j++) {
if(values[j][i] == x_val)x_count++;
if(values[j][i] == o_val)o_count++;
if(values[j][i] == 0)break;
}
if(x_count == boardSz)return X_WIN;
if(o_count == boardSz)return O_WIN;
x_count = o_count = 0;
}


if( allFilled == true)
{
for (int i = 0; i < boardSz; i++) {
for (int j = 0; j < boardSz; j++) {
if (values[i][j] == 0) {
allFilled = false;
break;
}
}
if (allFilled == false) {
break;
}
}
}


if (allFilled)
return DRAW;


return INPROGRESS;
}


Thursday, May 17, 2012

Yet Another HashMap ...

There are several implementations of hashmaps available, this is just another implementation that I did when I  was too lazy to google for existing implementations.

This implementation is having 2 basic traits:
1. A strong hash function.
2. An efficient tree

To implement this I have used the hash implementation provided by Bob Jenkins http://burtleburtle.net/bob/hash/doobs.html

And the tree chosen is a basic red black tree implementation. 

A very simple API which enables insertion/deletion of the entries.

To insert entries:
hash_insert(void* key, uint32 key_len, void* data, uint32 data_len);

To Check if the entry is present in the table
hash_find(void* key, uint32 key_len);

To retrieve the data for a key
hash_getData(void* key, uint32 key_len, void* data, uint16* data_len)

To delete an entry
hash_deleteEntry(void* key, uint32 key_len);

Here is a sample code, to show how to use it.

#include "hashmap.h"#include
#include
#include
#define MAX_KEY_LEN 128
int main(){
      char key[MAX_KEY_LEN];
      uint16_t data;
      uint16_t dataLen;
      int i = 10000000;
      // First insert
      strcpy(key, "hello");
      data = 123;
      hash_insert((void*)key, strlen(key), &data, sizeof(data));
   
      //Lets retrieve it
      strcpy(key, "hello");
      uint16_t temp;
      hash_getData((void*)key, strlen(key), &temp, &dataLen);
      //Remove the entries
      strcpy(key, "hello");
      hash_deleteEntry((void*)key, strlen(key));
}

The default number of entries in the hashmap is defined in hashmap.h as follows

#define HASH_MAX_CAPACITY 10000000

This can be modified as per requirement.

How to Use

Just hit make in the extracted package. This generates a  library libQuickHash.so and libQuickHash.a.  There is a sample program testHash.c which can be of help. 

The compressed package is here

enjoy ...