Month: June 2010

JQuery

JQuery is a library API within the javascript language, the API (Application Program Interface) is classes/functions that do all of the work for you and you can access them.

Both google and Microsoft host the JQuery API for you, and all you need to do is to load in the javascript from either or server hosted setup, for google it would be this to get version 1.4.2 of the JQuery language.

<script type="text/javascript" src="http://www.google.com/jsapi"></script>
<script>
google.load("jquery", "1.4.2");
</script>
 
-- or one line
 
<script type="text/javascript" src="http://ajax.googleapis.com/ajax/libs/jquery/1.4.2/jquery.min.js"></script>

or with MS you can use

<script src="http://ajax.microsoft.com/ajax/jquery/jquery-1.4.2.min.js" type="text/javascript"></script>

once you have the JQuery API loaded you can then access the HTML document objects by using the $ symbol and act on any part of that document object that supports the functions that you want to do, e.g. a div tag would have different options for styling compared to a span tag.

The API library set is defined abit more in that link, but in whole it is a very effective and usable API library that just makes life more fun :).

For example the code below will output a mini function that will for “each” number in the first parameter (can be anything, object, letters etc) and do the function, will in this case will square the value, but the .each command is very powerful,

$.each([1,2,3], function()
{
	document.write(this * this);
});

the reason why it is very powerful is because if you want to select a group of items and then on each of them alter there elements, then you just need to use the JQuery selection process, like so

$("div").each

and this will alter all of the div’s on the web page accordlying. Shall do some more posts on JQuery API once I have a full set of examples to attached to the post.

Copying values and not content

Copying values from one variable to another is very common place and the fun starts when you start to copy the pointer address and not the actual memory associated with that address, so lets say that we have a structure with a pointer to some memory, as below

struct testCell {
       int normalInt;
       int *values;
};

then we are capable of assigning the values to both the normalInt value and also creating a place in memory for values or let it point to somewhere in memory (copy of another value ? / array etc), but it is just a pointer to memory somewhere (hopefully not NULL !!)

So if we did something like

testCell t1;
t1.normalInt = 10;
t1.values = new int(3);

all is good, the normalInt value is 10 and also the values has a new integer value of 3 from the heap memory storage space, the problem being here is that when you copy a * (pointer) variable you copy the address and not the actual memory, so if you did something like

testCell t2;
t2 = t1;

t2 will have the value of 10 in normalInt and also the values of 3 (dereferenced of course), but if you did not deference the values variable and just outputted it you would find out that the t1.values and the t2.values are the same, e.g. pointing to the same place in memory and this could have major problems if you to delete t1.values or t1 went out of scope and the compile reclaimed memory that t1 was using, thus t2.values would not be a good memory storage!!, errors would be a massive problem.

The code below demonstrates this with having the t1.values being a array and the t2 variable setting a value within the t2.values and thus altering t1.values as well.

#include <iostream>
 
using namespace std;
 
struct testCell {
       int normalInt;
       int *values;
};
 
int main()
{
   testCell test1;
   test1.values = new int[10];
       for (int i =0; i < 10; i++)
               test1.values[i] = i;
 
       cout  << "normal values of test1" << endl;
       for (int i =0; i < 10; i++)
               cout << "i " << i << "  " << test1.values[i] << endl;
 
   testCell test2 = test1;
 
       cout << "but since we copied the values of what was inside the test1 " << endl;
       cout << "then test2 values value is the same as test1 e.g. the same
pointer to memory" << endl;
       test2.values[3] = 77;
       for (int i =0; i < 10; i++)
               cout << "i " << i << "  " << test1.values[i] << endl;
 
       cout << "test 1 values value " << test1.values << endl;
       cout << "test 2 values value (the same ) " << test2.values << endl;
 
       cout << "so test 2 is actually altering the same values within test 1
!!! ERROR PROBLEMS" << endl;
       delete test1.values;
       return 0;
}

here would be the output, and as you can see the memory locations of t1.values and t2.values are the same!!!..

normal values of test1
i 0  0
i 1  1
i 2  2
i 3  3
i 4  4
i 5  5
i 6  6
i 7  7
i 8  8
i 9  9
but since we copied the values of what was inside the test1
then test2 values value is the same as test1 e.g. the same pointer to memory
i 0  0
i 1  1
i 2  2
i 3  77
i 4  4
i 5  5
i 6  6
i 7  7
i 8  8
i 9  9
test 1 values value 0xab7010
test 2 values value (the same ) 0xab7010
so test 2 is actually altering the same values within test 1 !!! ERROR PROBLEMS

Priority queues

This is all about priority queue problems with using different techniques for storing the data in a queue, the priority queue could be similar to a queue in a hospital ER ward where the people with the biggest of problems are treated first. I am finding all of the computer science course at Stanford really interesting.

But a heap implementation is similar to a binary tree where the top node is the lowest value and the further you go down each part of the tree you will find higher and higher values. As you can see the below picture, but the main thing is that the highest values may be associated on another place compared to the next highest value, but when you remove the minimum value then you place the last node from the tree to the top node and then move that down to where it should be.

Heap storage
CS106B Assignment 4 Part 2

So to insert the values, I am using a recursive funciton

void PQueue::insertValue(int heapInsert)
{
	int newElemI = heapInsert;
	// need to find out if the parent value
	if (heapInsert > 0)
	{
		// decrement the heapInsert since we start from 0.
		heapInsert--;
		// if we are at the top then make it check with the top
		if (heapInsert == 1) 
			heapInsert=0; 
		else // else goto the parent node
			heapInsert/=2;
		// if parent node is greater than the present node, then swap and go up
		if (heapValues[(heapInsert)] > heapValues[newElemI])
		{
			// swap values
			swapValues((heapInsert), newElemI);
			return insertValue(heapInsert);
		}
	}
	return;
}

where it will call itself if a swap happens e.g the parent node is higher in value than the present node that we are checking, and the way that it works out the parent node is to divide the heapInsert by 2, but of course the top 3 nodes that is a special condition and also since arrays start from 0, then we have to — (-1) from the heapinsert value to start with. The newElemI is where we are at present.

To remove the top element, we need to remove that element and replace with the last node from the array, but then move this value down into the tree depending on if the value is less higher than the lowest value beneath it, so once again I did a recursive method that will call itself if a swap occurs, we just need to test the lower left/right elements first to find the lowest value and then check against that with the parent value and if so, swap.

void PQueue::moveRootDown(int rootID)
{
	// test to see which one of the lower two are the smallest of values
	int leftValue = (rootID*2);
	int rightValue = (rootID*2)+1;
	int smallest =-1;
	if (leftValue <= heapUsedSize)
		smallest = leftValue;
	if (rightValue <= heapUsedSize)
		if (heapValues[smallest-1] > heapValues[rightValue-1])
			smallest = rightValue;
	if (smallest == -1) return;
	if (heapValues[rootID-1] > heapValues[smallest-1])
	{
		swapValues(rootID-1, smallest-1);
		moveRootDown(smallest);
	}
}

that was the main aspects again of the assignment and here is the full source code, I have included the source code and the assignment PDF file in the zip file attached

#include "pqueue.h"
#include "genlib.h"
#include <iostream>
 
/* 
heap implementation
*/
 
const int heapStart = 10;
 
PQueue::PQueue()
{
	heapSize = heapStart;
	heapValues = new int[heapStart];
	heapUsedSize = 0;
}
 
PQueue::~PQueue()
{
	delete[] heapValues;
}
 
bool PQueue::isEmpty()
{
	if (heapUsedSize == 0)
		return true;
	else
		return false;
}
 
int PQueue::size()
{
	return heapUsedSize;
}
 
void PQueue::add(int newElem)
{
	// if we are the max then double
	if (heapSize == heapUsedSize)
		doubleCapacity();
	heapValues[heapUsedSize] = newElem;
	insertValue(heapUsedSize);
	heapUsedSize++;
}
 
// newElemI = index value of the new insert
void PQueue::insertValue(int heapInsert)
{
	int newElemI = heapInsert;
	// need to find out if the parent value
	if (heapInsert > 0)
	{
		// decrement the heapInsert since we start from 0.
		heapInsert--;
		// if we are at the top then make it check with the top
		if (heapInsert == 1) 
			heapInsert=0; 
		else // else goto the parent node
			heapInsert/=2;
		// if parent node is greater than the present node, then swap and go up
		if (heapValues[(heapInsert)] > heapValues[newElemI])
		{
			// swap values
			swapValues((heapInsert), newElemI);
			return insertValue(heapInsert);
		}
	}
	return;
}
 
void PQueue::swapValues(int swap1, int swap2)
{
	int tmp = heapValues[swap1];
	heapValues[swap1] = heapValues[swap2];
	heapValues[swap2] = tmp;
}
 
void PQueue::printOut()
{
	for (int i =0; i < heapUsedSize; i++)
		cout << "i " << i  << "   " << heapValues[i] << endl;
}
 
// double the capacity of the heap size
void PQueue::doubleCapacity()
{
	int *temp = new int[heapSize*2];
	for (int i =0; i < heapSize; i++)
		temp[i] = heapValues[i];
	delete[] heapValues;
	heapValues = temp;
	heapSize *=2;
}
 
int PQueue::extractMin()
{
	if (isEmpty())
		Error("no more values");
	else
	{
		int returnValue = heapValues[0];
		heapUsedSize--;
		heapValues[0] = heapValues[heapUsedSize];
		moveRootDown(1);
		return returnValue;
	}
	return 0;
}
 
void PQueue::moveRootDown(int rootID)
{
	// test to see which one of the lower two are the smallest of values
	int leftValue = (rootID*2);
	int rightValue = (rootID*2)+1;
	int smallest =-1;
	if (leftValue <= heapUsedSize)
		smallest = leftValue;
	if (rightValue <= heapUsedSize)
		if (heapValues[smallest-1] > heapValues[rightValue-1])
			smallest = rightValue;
	if (smallest == -1) return;
	if (heapValues[rootID-1] > heapValues[smallest-1])
	{
		swapValues(rootID-1, smallest-1);
		moveRootDown(smallest);
	}
}

here is what I added to the header file for the private aspects of the class.

    // heap size = the total amount of size 
    // heap used size = the amount of used space in the heap size
    // heap values = the actual values within the heap
    int heapSize, heapUsedSize;
    int *heapValues;
 
    void doubleCapacity();
	void printOut();
	void insertValue(int heapInsert);
	void swapValues(int swap1, int swap2);
	void moveRootDown(int rootID);

Priority queues – Part 1

This is all about priority queue problems with using different techniques for storing the data in a queue, the priority queue could be similar to a queue in a hospital ER ward where the people with the biggest of problems are treated first.

So the CS106B course does two versions which use a vector and a single linked list to do and then we have to implement a chunk list and and a heap implementation, here I am going to do a chunk list and the next post will be the heap version.

So to explain what a chunk list is instead of a having just a single value within a linked list we will have a chunk of values within a block of memory and then once that chunk is filled to then create a new chunk and link to that one. So it is very similar to a linked list, but the main parts of how to store data within the chunk array (without using a vector but a array of data that we have to manage) and how to split the chunks once they reach there maximum storage capacity. It is explained in the PDF assignment attached in the zip file.

Anyway, here is the interface/header file of the priority queue that we have to implement so that if the program will use any of the different versions to store data linked list, chunk, heap, vector.

class PQueue {
  public:
    PQueue();
    ~PQueue();
    int size();
    bool isEmpty();
    void add(int elem);
    int extractMin();
private:
 // implementation dependent member variables and helper methods
};

To start with, I need to find out where the chunk to insert the value into, this would accomplished by searching the present chunks and if the inserting value is lower than highest value in that chunk then this is the chunk to insert into since they are already in sorted order then the searching process will always find the correct place to insert into. So here is how I find that highest chunk to insert into, it uses recursive technique to find the chunk

// find the highest chunk of space where newElem could be placed into the best chunk
PQueue::chunkSpace* PQueue::findHighestChunk(chunkSpace *&space, int newElem)
{
	if (space == NULL) return NULL;
	// found the previous chunk to insert into
	if (space->values[space->lastBlock-1] > newElem && space->lastBlock > 0)
			return space;
	else
	{
		chunkSpace *retPlace = findHighestChunk(space->nextBlock, newElem);
		if (retPlace == NULL)
			return space;
		else
			return retPlace;
	}
}

could have used a for loop to search thought like

for (chunkSpace *head = chunks, *pre = chunks; head != NULL; head = head->nextBlock)
{
   if (head->values[head->lastBlock-1] > newElem)
       break;
   pre = head;
}

but then you would need to check for NULLs etc so just thought that I would use recursive since it is just a nice thing :). once found the highest chunk to insert into then we can insert a value if there is space, if not then split the chunk into two and then insert the new value into the correct chunk

	if (space->lastBlock == MaxElemsPerBlock)
	{
		// split into two, divide the blocks in half and rebuild the structures
		int insertI=0;
		int div = MaxElemsPerBlock/2;
		chunkSpace *newSpace = new chunkSpace();
		// rebuild links
		newSpace->nextBlock = space->nextBlock;
		newSpace->values = new int[MaxElemsPerBlock];
		space->nextBlock = newSpace;
 
		// copy over values
		space->lastBlock -=div;
		for (int i =div; i < MaxElemsPerBlock; i++)
			newSpace->values[insertI++] = space->values[i];
		newSpace->lastBlock = div;
		// find out where to insert, new space or previous space
		if (newSpace->values[0] < newElem)
			space = newSpace;
	}

which the code above will split the present chunk into 2 and then rebuild the links and place the data from the first one (half way forwards) into the second chunk, of course we need to insert the new value into the correct chunk which is why there is a test at the end to see if the new value is greater than the second chunks first value.

Here the full source of the pqchunk.cpp which does all of the pqueue for chunks and also some have included below the bits that I added into the pqueue.h file.

#include "pqueue.h"
#include "genlib.h"
#include <iostream>
 
/* 
  chunk memory implementation
*/
 
// constant max allocation of the 
const int MaxElemsPerBlock = 4;
 
PQueue::PQueue()
{
	// setup the first instance of chunks
	chunks = new chunkSpace();
	chunks->nextBlock = NULL;
	chunks->lastBlock = 0;
	chunks->values = new int[MaxElemsPerBlock];
	theSize = 0;
}
 
PQueue::~PQueue()
{
	// deallocate the memory of the chunks
	deleteChunks(chunks);
}
 
// delete the chunks and recursive call itself to loop down the list
void PQueue::deleteChunks(chunkSpace *space)
{
	if (space == NULL) 
		return;
	else
	{
		deleteChunks(space->nextBlock);
		deleteBlock(space);
	}
}
 
void PQueue::deleteBlock(chunkSpace *space)
{
	delete[] space->values;
	delete space;
}
 
bool PQueue::isEmpty()
{
	if (theSize == 0)
		return true;
	else 
		return false;
}
 
int PQueue::size()
{
	return theSize;
}
 
void PQueue::add(int newElem)
{
	chunkSpace *space = findHighestChunk(chunks, newElem);
	// split the block if at the maxiumum of elements allowed once the insertation has taken place.
	if (space->lastBlock == MaxElemsPerBlock)
	{
		// split into two, divide the blocks in half and rebuild the structures
		int insertI=0;
		int div = MaxElemsPerBlock/2;
		chunkSpace *newSpace = new chunkSpace();
		// rebuild links
		newSpace->nextBlock = space->nextBlock;
		newSpace->values = new int[MaxElemsPerBlock];
		space->nextBlock = newSpace;
 
		// copy over values
		space->lastBlock -=div;
		for (int i =div; i < MaxElemsPerBlock; i++)
			newSpace->values[insertI++] = space->values[i];
		newSpace->lastBlock = div;
		// find out where to insert, new space or previous space
		if (newSpace->values[0] < newElem)
			space = newSpace;
	}
	insertIntoBlock(space, newElem, space->lastBlock);
	space->lastBlock++;
	theSize++;
}
 
void PQueue::insertIntoBlock(chunkSpace *space, int newElem, int blockIndex)
{
	// base case of nothing already
	if (blockIndex == 0)
	{
		space->values[0] = newElem;
		return;
	}
	if (space->values[blockIndex-1] <= newElem)
	{
		space->values[blockIndex] = newElem;
		return;
	}
	if (space->values[blockIndex-1] > newElem)
	{
		space->values[blockIndex] = space->values[blockIndex-1];
		return insertIntoBlock(space, newElem, (blockIndex-1));
	}
}
 
void PQueue::printOutBlocks(chunkSpace *block)
{
	if (block == NULL)
		return;
	else
	{
		cout << "print out block " << endl;
		for (int i =0; i < block->lastBlock; i++)
			cout << "i " << i << " value =" << block->values[i] << endl;
		printOutBlocks(block->nextBlock);
	}
}
 
// find the highest chunk of space where newElem could be placed into the best chunk
PQueue::chunkSpace* PQueue::findHighestChunk(chunkSpace *&space, int newElem)
{
	if (space == NULL) return NULL;
	// found the previous chunk to insert into
	if (space->values[space->lastBlock-1] > newElem && space->lastBlock > 0)
			return space;
	else
	{
		chunkSpace *retPlace = findHighestChunk(space->nextBlock, newElem);
		if (retPlace == NULL)
			return space;
		else
			return retPlace;
	}
}
 
int PQueue::extractMin()
{
	if (isEmpty())
		Error("no more values left");
	else
	{
		int returnValue = chunks->values[0];
		theSize--;
		for (int i =1; i < chunks->lastBlock; i++)
			chunks->values[i-1] = chunks->values[i];
		chunks->lastBlock--;
		if (chunks->lastBlock == 0)
		{
			// if chunks->nextBlock != NULL then remove this block and repoint the chunks to the nextBlock
			if (chunks->nextBlock != NULL)			
			{
				chunkSpace *old = chunks;
				chunks = chunks->nextBlock;
				deleteBlock(old);
			}
		}
		return returnValue;
	}
	return 0;
}

and here is the bits that I added to the private

   struct chunkSpace
   {
		int lastBlock;
		int *values;
		chunkSpace *nextBlock;
   };
 
   chunkSpace *chunks;
   int theSize;
 
   void deleteChunks(chunkSpace *space);
   void deleteBlock(chunkSpace *space);
   chunkSpace *findHighestChunk(chunkSpace *&space, int newElem);
   void printOutBlocks(chunkSpace *block);
   void insertIntoBlock(chunkSpace *space, int newElem, int blockIndex);

which hides my local variables as such and methods.

Linked list – recursive functions

A linked list, is basically a list of elements that have a link attached to each one to the next. So for example if you have a structure like

struct List {
     string name;
     List *next;
};

then the List has a internals of a name which is of type string, and then a link (a pointer) to the next List in the list of linked List types. I have called it a Elem in the source code below because then it may make more sense, since it is kinder a element of the whole linked list.

So to create a I wrote a function to add a element (Elem) to the list already, since we are going to be altering the list then need to pass as a reference (&) so we actually alter the main variable and not just the functions variable and it is not passed back.

struct Elem {
	string name;
	Elem *next;
};
 
// inserts a Elem into a linked list
void setUpElem(Elem * & list, Elem *addnew)
{
	addnew->next = list;
	list = addnew;
}
 
.. 
int main()
{
    Elem *elem = NULL;
    Elem newElem;
    newElem.name = "bob";
 
    setUpElem(elem, &newElem);
}

with the function call setUpElem, I am passing the address of the newElem because that is the pointer (the address memory location).

So to start with the recursive functions, lets print out all of the elements,

// just print out the top element 
void printOutElem(Elem *elem)
{
	cout << "Name : " << elem->name << endl;
}
 
// recursive loop to print them all out
void printThemAllOut(Elem *list)
{
	if (list != NULL)
	{
		printOutElem(list);
		printThemAllOut(list->next);
	}
}

printOutElem will print out the element name associated with the parameter, and the cool recursive function called printThemAllOut, which just re-calls itself with the link to the next element to print out.. just a nice little function..

The next recursive that makes allot more sense, is when you are adding a element instead to the head of the list, but in the middle, like it is sorted, then if you was using loops you would require to keep hold of the previous element so that you can insert the new element into that previous elements -> next link and re-link the inserted element -> next to the current element in the list, hopefully the code helps to understand..

void insertIntoMiddle(Elem *&elem, Elem *midElem)
{
	Elem *cur, *pre= NULL;
 
	for (cur=elem; cur != NULL; cur= cur->next)
	{
		if (cur->name > midElem->name) break;
		// store where we was
		pre = cur;
	}
 
	// place the middle next element equal to where we are in the list
	midElem->next = cur;	
	// if the previous is not null, e.g. previous was somewhere in the list
	if (pre != NULL)
		pre->next = midElem;  // update the previous link to the middle element
	else
		elem = midElem;			// else probably is empty !!.. not good.. 
}

and here is a very nice recursive function that will do the same as above but just in recursive calls to itself with passing the previous link to itself so there is no need to keep a element of the previous link, very nice and allot more easier to debug since less code.

void insertIntoMiddleRecursive(Elem *&elem, Elem *midElem)
{
	if (elem == NULL || elem->name > midElem->name)
	{
		midElem->next = elem;
		elem = midElem;
	}
	else
		insertIntoMiddleRecursive(elem->next, midElem);
}

here is the full source code

#include <string>
#include <iostream>
 
using namespace std;
 
// the element structure, the name is the name of the person
// and the next is a link to next name
struct Elem {
	string name;
	Elem *next;
};
 
// inserts a Elem into a linked list
void setUpElem(Elem * & list, Elem *addnew)
{
	addnew->next = list;
	list = addnew;
}
 
// just print out the top element 
void printOutElem(Elem *elem)
{
	cout << "Name : " << elem->name << endl;
}
 
// recursive loop to print them all out
void printThemAllOut(Elem *list)
{
	if (list != NULL)
	{
		printOutElem(list);
		printThemAllOut(list->next);
	}
}
 
// you have to keep in contact with the current and previous 
// (since that is where we need to place the new element
void insertIntoMiddle(Elem *&elem, Elem *midElem)
{
	Elem *cur, *pre= NULL;
 
	for (cur=elem; cur != NULL; cur= cur->next)
	{
		if (cur->name > midElem->name) break;
		// store where we was
		pre = cur;
	}
 
	// place the middle next element equal to where we are in the list
	midElem->next = cur;	
	// if the previous is not null, e.g. previous was somewhere in the list
	if (pre != NULL)
		pre->next = midElem;  // update the previous link to the middle element
	else
		elem = midElem;			// else probably is empty !!.. not good.. 
}
 
// a far better way of doing this is to use recursive for inserting
// since the parameter is the previous link :)
// this is just a far nicer way of doing the above function
void insertIntoMiddleRecursive(Elem *&elem, Elem *midElem)
{
	if (elem == NULL || elem->name > midElem->name)
	{
		midElem->next = elem;
		elem = midElem;
	}
	else
		insertIntoMiddleRecursive(elem->next, midElem);
}
 
int main()
{
	Elem *elem = NULL;
 
	Elem newElem;
	newElem.name = "steve";
	setUpElem(elem, &newElem);
	Elem nextElem;
	nextElem.name = "genux";
	setUpElem(elem, &nextElem);
 
	printThemAllOut(elem);
 
	// now lets insert into the middle of the linked list
	Elem midElem;
	midElem.name = "henry";
	insertIntoMiddle(elem, &midElem);
 
	cout << "after the insert of \"henry\" into the middle" << endl;
	printThemAllOut(elem);
 
	Elem newMidElem;
	newMidElem.name = "janet";
	insertIntoMiddleRecursive(elem, &newMidElem);
 
	cout << "after the insert of \"janet\" into the middle - using recursive :) " << endl;
	printThemAllOut(elem);
 
 
 
    return 0;
}

and here is the output

Name : genux
Name : steve
after the insert of "henry" into the middle
Name : genux
Name : henry
Name : steve
after the insert of "janet" into the middle - using recursive :)
Name : genux
Name : henry
Name : janet
Name : steve

Boggle

This is all about recursive problems and this is the main problem!.. a boggle which is when you have a 4*4 grid of letters and you need to find letter within it.

The PDF within the zip file attached explains more in more detail, but the main basics of the game is that you setup a grid with random letters (in the assignment you could also take in user input to build up the grid from that, or there was a file of 16 dice with there set characters on them). And then once the grid is built up to then find words within that grid, you can use any letters from within that letter that you are at within a 3*3 grid around it (if possible e.g. no sides) but you cannot re-use any letters that you have already used.

In this assignment it was to use recursive functions to solve the problem of finding words, from the computer point of view, it should find all of the words within the grid, but the human point of view (whom goes first) tries to find all of the words within the grid and the recursive function should make sure that there is a possible combination of that word within the grid.

Both of the functions are very similar, here is the human version, in this version we only need to make sure that the word to find (findThis) is within the grid of characters, below this is a example of the grid. The parameters are what to find (findThis) the board to search (theBoard) the route taken to find this word (theRoute) and the later 3 are internal maintenance of recursive calling, alreadyFound is the word already found (could have used the theRoute, but though it would be nice to another string) and also the point of where we are, placeY placeX.

So to start with the base case is if we have found the string to find, findThis, if not, then if we have just started the search (alreadyFound is empty) then find the first letter within the grid, once found it then re-call the function to find the other letters using the place where we found the first letter (and next and next letters), so once we have found the first letter the already found string is not empty, so search around the letter (not itself) within a 3*3 grid. Most of the bits inside of the code is filling in the route path and also updating the already found string.

bool findUsersWord(string findThis, Grid<char> &theBoard, Vector<cell> &theRoute, string alreadyFound, int placeY, int placeX)
{  
  // need to find the findThis  base case
  if (findThis == alreadyFound)
    return true;
  // need to find the first letter within the board and then progress around that.
  if (alreadyFound.empty())
  {
    for (int rows = 0; rows < theBoard.numRows(); rows++)
      for (int cols = 0; cols < theBoard.numCols(); cols++)
        // find the each character within the 
        if (theBoard[rows][cols] == findThis[0])
        {
          alreadyFound = findThis[0];
          cell newR;
          newR.row = rows;
          newR.col = cols;
          theRoute.add(newR);
          if (findUsersWord(findThis, theBoard, theRoute, alreadyFound, rows, cols))
            return true;
          else
            // clear out the found Board 
            theRoute.clear();
        }
  }
  else
  {
    // try and find the next letters within the area around the base letter
    // spin around the letter 3 * 3 grid
    for (int y= (placeY > 0 ? placeY-1: placeY); y <=(placeY == (theBoard.numRows()-1) ? placeY : placeY+1);y++)
      for (int x=(placeX > 0 ? placeX-1: placeX); x<=(placeX == (theBoard.numCols()-1) ? placeX : placeX+1); x++)
        if ((theBoard[y][x] == findThis[alreadyFound.length()]) && (!(y==placeY && x ==placeX)))
          // already used letter
          if (!placeAlreadyUsed(y,x,theRoute))
          {
            alreadyFound += findThis[alreadyFound.length()];
            cell newR;
            newR.row = y;
            newR.col = x;
            theRoute.add(newR);
            if (findUsersWord(findThis, theBoard,theRoute, alreadyFound, y, x))
              return true;
            else
            {
              if (alreadyFound.length() > 1)
                alreadyFound = alreadyFound.substr(0, alreadyFound.length()-1);
              theRoute.removeAt(theRoute.size()-1);
            }
          }
    return false;
  }
  return false;
}

Here is a example of the output of the grid, with the words highlighted “MALT” with each position within the word where it was linked together, e.g M is the first letter thus there is a number 1 within the image on the M.

Boggle - Highlighted words
CS106B Assignment 2 Part 3

and here is the computer hammering me !!.. he found allot more words than what I did.

Boggle - computer won
CS106B Assignment 2 Part 3

I did do the extensions, so that you can also use the mouse as a input to build up the word to search for by clicking on the characters and also displaying route path of the word was found in the grid.

Also added in some sound to the program, so if the human picks a word that is not in the dictionary/grid then comes back with a sound. I did implement the converting the letter to “Q” to “QU” for the human input to give myself abit more chance!! :).. but could have added to the computer recursive function because just needed to call the function

string addQU(string theStr)
{
	int findI =0;
	while (true)
	{
		findI = theStr.find("Q", findI);
		if (findI >= 0)
			theStr = theStr.replace(findI,1,"QU");
		if (findI == -1)
			return theStr;
		findI++;
	}
}

Also I did the mouse input, so that it will take a mouse position and find the appropriate letter on the grid, does some maths to find the top left position on the grid and then how far the mouse is from that, then the letters on the grid are 0.5 in size, so divide the distance from there and you get the position.

char getMouseWord(Grid<char> &theBoard, int dimension)
{
	double x = GetMouseX();
	double y = GetMouseY();
	// get the start point
	x -= 1.93;
	y -= 3.1;
	y *= -1;
	int row = (int)(y / 0.5);
	int col = (int)(x / 0.5);
	if ((row < dimension) && (col < dimension))
		return theBoard[row][col];
	else
		return NULL;
}

Here is the computers recursive function, it is very similar to the humans version, but it will search for possible words with the grid and using the startY/startX so that we do not restart the search from point 0,0 on the grid, but where we was last, makes it allot more quicker!!!.

// returns a new word found on the grid, if able to 
string findComputersWord(Grid<char> &theBoard, Lexicon alreadyFoundWords, Lexicon dictionary, Vector<cell> &theRoute, int startY, int startX, string alreadyFound, int placeY, int placeX)
{  
  if (alreadyFound.length() >= MIN_WORD_COUNT)
    if (dictionary.containsWord(alreadyFound))
      if (!alreadyFoundWords.containsWord(alreadyFound))
        return alreadyFound;
  // need to find the first letter within the board and then progress around that.
  if (alreadyFound.empty())
  {
    for (int rows = startY; rows < theBoard.numRows(); rows++)
      for (int cols = startX; cols < theBoard.numCols(); cols++)
        // find the each character within the 
        {
          alreadyFound = theBoard[rows][cols];
          cell newR;
          newR.row = rows;
          newR.col = cols;
          theRoute.add(newR);
          string newWord = findComputersWord(theBoard,alreadyFoundWords, dictionary,theRoute, startY, startX, alreadyFound, rows, cols);
          if (newWord.length() > 0)
            return newWord;
          else
          {
            // clear out the found Board 
            theRoute.clear();
          }
        }
  }
  else
  {
    // try and find the next letters within the area around the base letter
    // spin around the letter 3 * 3 grid
    for (int y= (placeY > 0 ? placeY-1: placeY); y <=(placeY == (theBoard.numRows()-1) ? placeY : placeY+1);y++)
      for (int x=(placeX > 0 ? placeX-1: placeX); x<=(placeX == (theBoard.numCols()-1) ? placeX : placeX+1); x++)
      {
        if (!(y==placeY && x ==placeX))
        {
          // already used letter
          if (!placeAlreadyUsed(y,x,theRoute))
          {
            alreadyFound += theBoard[y][x];
            cell newR;
            newR.row = y;
            newR.col = x;
            theRoute.add(newR);
            if (dictionary.containsPrefix(alreadyFound))
            {
              string newWord = findComputersWord(theBoard, alreadyFoundWords, dictionary,theRoute,startY, startX, alreadyFound, y, x);
              if (newWord.length() > 1)
                return newWord;
              else
              {
                if (theRoute.size() > 0)
                  theRoute.removeAt(theRoute.size()-1);
              }
            }else
            {
              if (theRoute.size() > 0)
                theRoute.removeAt(theRoute.size()-1);
            }
            // if this new line of attack does not work out, clear the foundboard and also the alreadyfound variables.
            if (alreadyFound.length() > 0)
              alreadyFound = alreadyFound.substr(0, alreadyFound.length()-1);
          }
        }
      }
  }
  return "";
}

I have included the source code and the PDF file of the assignment within the attached zip file, it works in Visual Studio 2008.

Warm up recursive problems

This is all about recursive problems and the part 1 of this assignment is warm up problems.

There are two warm up problems, one is Balancing parentheses and the second is Evaluating expressions, so lets start with the Balancing parentheses.

Balancing parentheses

To make sure that a there is opening and closing brackets within a string, the three brackets that we need to search for is {}, () and [] and if they are present in the string basically remove them and then recheck the string until it reaches “” (a empty state). If there is a non empty state of the string then return false, which means that the string is not balanced, here is a example taken from the assignment PDF file,

For example, the string “[(){}]” is shown to be balanced by the following chain of calls:
IsBalanced(“[(){}]”)
IsBalanced(“[{}]”)
IsBalanced(“[]”)
IsBalanced(“”) true

and here is the recursive code that I did come up with, the start is the empty string (str.size() == 0), else it tries to find the any one of the three strings in a for loop (breaks from the for loop if found) and if one is found then recall the IsBalanced function.

bool IsBalanced(string str)
{
	int strPos=-1;
	if (str.size() == 0)
		return true;
	string findStr[] = {"()", "[]", "{}"};
	for (int i =0; i < 3; i++)
	{
		strPos = str.find(findStr[i]);
		if (strPos >=0) 
			break;
	}
	if (strPos >=0)
		return IsBalanced(str.substr(0, strPos) + str.substr(strPos+2));	
	return false;
}

Evaluating expressions

Evaluating expressions is when you have a mathematical equation that you need to equate, so for example as taken from the PDF assignment file

EvalInfixExp(“3”) = 3
EvalInfixExp(“(4 + 8)”) = 12
EvalInfixExp(“(25 – (2 * 10))”) = 5

Where the EvalInfixExp is the function that we call recursive, the way that I thought about this is that if there is no spaces then return the value (e.g. base case) and if there is no brackets in the string then it must be a maths query, which get the two values and the mathematical function (/,+,-,*) and equate them returning that value, but then if there is a “(” at the start, since all equations are valid, then equate inside that ( .. ) brackets, but if there is any ( … ) inside that main ( … ) then figure them out first, which is why I using the first_last_of “(” function to find the the end ( .. ) to equate and then the associated “)”, which in turn we just need to recall the function EvalInfixExp to figure out the value inside the string.

To think about it, what is happening is that is works from the inside to the out finding the values of the ( .. ) to reinsert them back into the string (the result of them that is), so in the end all we do is equate the last mathematical equation.

Here is the cpp recursive function.

int EvalInfixExp(string expString)
{
	// so if the first character is ( then do else do other
	int brackPos1, brackPos2, returnValue =0;
	// try and find the outter ()
	if (expString[0] == '(')
	{
		brackPos1 = expString.find_last_of("(");
		brackPos2 = expString.find_first_of(")", brackPos1);
		// find the value within the () and replace with the new value
		if (brackPos1 >= 0 && brackPos2 >=0)
		{
			brackPos1++;
			returnValue = EvalInfixExp(expString.substr(brackPos1, brackPos2 - brackPos1));
			// need to replace the () with the value 
			brackPos1--;
			expString.replace(brackPos1, brackPos2 - (brackPos1-1), IntegerToString(returnValue));
		}
		return EvalInfixExp(expString);
	}
	else
	{	// find out the actual value of the maths function
		if (expString.find_first_of(" ") < 0 || expString.find_first_of(" ") > expString.size())
			return StringToInteger(expString);
		Scanner theExpScanner;
		theExpScanner.setInput(expString);
		theExpScanner.setSpaceOption(theExpScanner.IgnoreSpaces);
		int firstValue = StringToInteger(theExpScanner.nextToken());
		string op = theExpScanner.nextToken();
		string last;
		while (theExpScanner.hasMoreTokens())
			last += theExpScanner.nextToken();
		int secondValue = StringToInteger(last);
		if (op == "+")
			returnValue = firstValue + secondValue;
		if (op == "-")
			returnValue = firstValue - secondValue;
		if (op == "*")
			returnValue = firstValue * secondValue;
		if (op == "/")
			returnValue = firstValue / secondValue;
		return returnValue;
	}
}

I have attached the full source code and also the PDF assignment code.