Maze Generator

The maze is basically a X * X grid that has 1 route from the start to the end of the grid.

Here is a picture of the output of a grid with a path/route from the start to the finish.

Maze Generator
CS106B Assignment 2 Part 3

As you can see from the above there is basically one route which can be worked out if you start off with all of the grid cells being classed as blocked (e.g. all walls around the cell are there) and if you then process this grid and make it so that all of the grid cells are linkable so that there is a way around the grid to reach every cell, of course you would only have one way from start to finish.

Then all you need to do is to random check each cell wall and see if it is within the same set of chambers (set of cells that already linked) if not then delete that cell wall else check another wall. So taken from the assignment PDF file (attached) the process, in full, is

  • choose a dimension
  • generate all walls, and shuffle them
  • generate all chambers, where each chamber includes one unique cell
    1. foreach wall in randomly-ordered-walls
    2. if wall separates two chambers
    3. remove wall

I generated the walls and shuffled them by to start with create a grid of cells in a loop (for loops) which build up the horizontal and vertical cells and then go through a for loop again that loops to the size of the cells and this time randomally pick a cell to swap with another cell, this will generated the randomally list of walls to check to see if it separates two chambers.

The way that I checked to see if the wall was between two chambers was to first find the cell on the left within the chambers array (this array would be the dimension * dimension of the grid since there would be a chamber for each cell) and then see if the second cell that is linked to that wall to check is part of the same chamber as the left.

I could have used a Set which contains the method “containsAt” so could find the second cell is within the same chamber as the first, but I used a Vector array because then I could show two ways of doing the find, either using a for loop or a recursive function, I have done this below, the first is the for loop method that will search a Vector of cells (col/row) of a chamber(subChamber) to find a cell (findThisCell), the index is used with the recursive function so just disregard that at present, it will return true if it finds it, else false.

bool findCellInSubChambers(Vector<cell> &subChambers, cell findThisCell, int index)
{
	for (int mainSubSubChamber = 0; mainSubSubChamber < subChambers.size(); mainSubSubChamber++)
	{
		if (subChambers[mainSubSubChamber] == findThisCell)
		{
			return true;
		}
	}
	return false;
}

here is the recursive function that will loop through the chamber of cells (subChamber) the index is started with a value of 0 as the function definition shows below as well. What it does is to go through the array of cells within the chamber (vector array) with using the index value, if has not found at the present index within the array recall this function again with a new index value, but if the index value is higher than the size of the array then return false.

bool findCellInSubChambers(Vector<cell> &subChambers, cell findThisCell, int index =0);
// return true if the cell is within the vector of cells
bool findCellInSubChambers(Vector<cell> &subChambers, cell findThisCell, int index)
{
	if (index < subChambers.size())
	{
		if (subChambers[index] == findThisCell)
			return true;
		else 
			return findCellInSubChambers(subChambers, findThisCell, ++index);
	}
	return false;
}

I did do another for loop and recursive function for searching all of chambers for the first cell of the wall to check for as well, just for fun.

Anyway, here is the main loop code, what it does is to first find the index value of the sub chamber within the main chambers array (findCellInChambers function) which holds the value of the index within the array of chambers, if it is found (it should always be found to be honest, but to just be on the safe side), then check to see if the second cell to check (the other side of the wall) is in the same chamber as the first cell, if not, then remove the wall and add the array of cells that was attached to the second cell to the first cell chamber array, so that we can build up a list of chambers (this should finish off with a all of the chambers being linked).

Vector<wall>::Iterator wallIter = theWalls.iterator();
while (wallIter.hasNext() && (wallI < ((dimension * dimension)-1)))
{
	wall checkThisWall = wallIter.next();
 
	int firstFound = findCellInChambers(chambers, checkThisWall.one);
	if (firstFound >= 0)
	{
		if (!findCellInSubChambers(chambers[firstFound], checkThisWall.two))
		{
			wallI++;
			RemoveWall(checkThisWall);
			int found = findCellInChambers(chambers, checkThisWall.two);
			if (found >= 0)
			{
				for (int foundI = 0; foundI < chambers[found].size(); foundI++)
					chambers[firstFound].add(chambers[found][foundI]);
				chambers.removeAt(found);
			}
		}
	}
}

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

Word Ladder

This part is a word ladder.

A word ladder is when you move from one word to another with only changing 1 letter, so for example if you wanted to move from dog to bog, then you are just altering one letter (the “d” to a “b”), but if you are going from code -> data, then you would have to go through a couple of changes to get to the end word.

code -> cade -> cate -> date -> data

as you can tell we have only altered one letter at a time to move from one point of the linking words to another.

But if there is no linking words that we need to stop the program, because there is no link between the two words in that case and also if we have already used a word for a test sequence then do not use that word another for another sequence. (breath-first-searching).

So what we need to do is to have a way of finding another word with just changing one of the letters within the linking words, so, if we alter each letter within a word and make sure it is actually a word within a dictionary (and of course we have not already used that word before) then return that word as a new search pattern. This is what the below function (findNextWord) does, the parameters are word (the base word), dictionary (the dictionary to make sure that the new word is a word) and the alreadyUsed is the list of already used words.

string findNextWord(string word, Lexicon dictionary, Lexicon alreadyUsed)
{
	string newWord;
	for (int i =0; i < word.length(); i++)
	{
		newWord = word;
		for (char ch = 'a'; ch <= 'z'; ch++)
		{
			// create a new word
			newWord = newWord.replace(i,1,1, ch);
			// make sure it is a valid word and also not already used
			if (dictionary.containsWord(newWord))
				if (!alreadyUsed.containsWord(newWord))
					return newWord;
		}
	}
	return "";
}

Next since there could be allot of different words created from a 4 letter word, which in-turn would allow for different paths to take then what we need to do is to add the next word gained from the above function to the already path that we have taken and insert that into a queue (first in and first out), this queue will have all of the paths that we are testing in ordered of length to see if we are able to get to the end word. For example lets say with the code – data test, the queue may look like this after the first round, where the words are in a array

queue top
code -> cade

code -> node
code -> tode

queue bottom

so this means that we will always check to see if any of the 2 length linking paths can get to the end, and then process them in order and place the 3 length linking paths afterwards for example (we have take the code->cade from the top to process)

queue top
code -> node
code -> tode
… (other 2 length paths)
code -> cade -> cate
code -> cade -> kade

k. kade is a name, but could be in the dictionary, but you get the point, 2 length paths will be checked first and then 3 length paths until we reach the end word.

So this is how I done the it, added the start word to the queue, then looped, take off the next element, search for another word, if the next word is the end word stop, else add to the queue of searchable paths and also add to the list of already used words, below is the source code

void processMainGame(Lexicon dictionary, string startWord, string endWord)
{
	Queue<Vector<string> > theFIFO;
	Lexicon alreadyUsed;
	string nextStr;
 
	theFIFO.clear();
	Vector<string> addToQueue;
	addToQueue.add(startWord);
	// start the queue
	theFIFO.enqueue(addToQueue);
 
	while (true)
	{
		// build up a new list of items to search, or stop if empty
		if (theFIFO.size() ==0)
		{
			cout << "Nope nothing found! no ladder"<< endl;
			break;
		}
		Vector<string> newString = theFIFO.dequeue();
		while (true)
		{
			// find the next word to use
			nextStr = findNextWord(newString[newString.size()-1], dictionary, alreadyUsed);
			// the end of the search
			if (nextStr == endWord) 
			{
				cout << "FOUND ladder !!" << endl;
				foreach (string list in newString)
				{
					cout << list << " - ";
				}
				cout << endWord << endl << endl;
				return;
			} else if (nextStr != "")
			{
				// if there is another word to search with add to the end of the list
				Vector<string> addMore = newString;
				addMore.add(nextStr);
				theFIFO.enqueue(addMore);
			}
			// else if nothing left to search for stop!!
			else if (nextStr =="")
				break;
			alreadyUsed.add(nextStr);
		}
	}
}

I have attached the source code and also the PDF file of the assignment.

Random Writer (Markov)

This is to implement a Markov approach to predicting what is going to happen next with using what has happened before. For example, for handwriting, if you see the letters “TH” and there is one letter left but you are not able to read it, then you could guess it could be the letter “E”, well that is kinder the idea.

So, in this assignment what is required is to read in a file, any file story etc, and then create seeds (which is a user requested input) with the next character(s) that are linked to that seed. To understand what a seed is, lets say that we have a line of text

“Hi there, my knickname is genux, and I enjoy to do software development, in many languages and operating systems, because development is just interesting!!”

and we picked a seed length of 3, so to start with the first seed is “Hi ” <- yep there is a space there!! because it has to be a length of 3, and the next character is "t" which is what is linked to the seed value "Hi ", so from the text above with a seed length of 3 you can see that there is a seed of "ent" (within the development words for example) has two choices to make for the next character either a "," or a " " and this is the random choice of where to go after this test. If you went to " " then the new seed would be "nt " which there is only one next possible seed which is "t i" and you just carry on like this. To start with this problem, I wanted to create a mapped seeds that had attached the next characters that are linked to that seed value, so it would be a

Map<Vector<char>  > theKeys

which means that we are using a map (seed is the string key) and then a vector or char(acter(s)) that are associated with that seed. So then we need to read in the value and insert into the map, so here is the way that I am using to insert a character into vector associated with the mapped seed key. What I am doing is to start with, to see if there is already a seed within the map already, if so create a vector of values that is already associated with that seed key, either or, insert the new (insertChar) into the vector and place into the map seed key (if you use the put method if will replace the previous values associated with that key).

inline void addNewChar(Map<Vector<char> > &theKeys, string seedValue, char insertChar)
{
	Vector<char> addResults;
	if (theKeys.containsKey(seedValue))
		addResults = theKeys.get(seedValue);
	addResults.add(insertChar);
	theKeys.put(seedValue, addResults);
}

the next thing is to start with reading the seed start length from the file (the readSeedFromFile method will do that and return the string of its value), then whilst there is characters left in the file keep on reading the file whilst inserting the seed and characters into the mapped variable (Map > &theKeys).

void setupKeys(Map<Vector<char> > &theKeys, ifstream &infile, int seed)
{
	// obtain the first seed value
	string seedValue = readSeedFromFile(infile,seed);
	char newChar;
	while (!infile.eof())
	{
		newChar = nextChar(infile);
		addNewChar(theKeys, seedValue, newChar);
		seedValue = seedValue.substr(1,seedValue.length()-1) + newChar;
	}
}

So after we have read in the file, we need to find the highest seeded that has the most next characters attached to it, and this what the function below does, the foreach is a iterator that will loop through all of the seed (key) values within the Map and then find the length of the next characters.

string obtainAMaxKey(Map<Vector<char> > &theKeys)
{
	int maxSeed =0;
	string maxKey="";
	Vector<char> values;
	// iterator through the map values
	foreach (string key in theKeys)
	{
		values = theKeys.get(key);
		if (values.size() > maxSeed)
		{
			maxKey = key;
			maxSeed = values.size();
		}
	}
	return maxKey;
}

the last thing is to output the Markov, stop at a word count of 2000 or if there is no more characters attached to the last seed value. So all we do is start with the seed value from above function, then just get the Vector from the seed, then pick a random number from the length of that Vector and update the seed to the next seed. As below.

void outputMarkov(Map<Vector<char> > &theKeys, string startKey)
{
	Randomize();
	int wordCount = startKey.length(), randomKey;
	Vector<char> values;
	while (true)
	{
		if (wordCount >= 2000) break;
		values = theKeys.get(startKey);
		if (values.size() ==0) 
		{
			cout << "NO MORE KEYS"; 
			break;
		}
		randomKey = RandomInteger(0,values.size()-1);
		cout << values[randomKey];
		startKey = startKey.substr(1,startKey.length()-1) + values[randomKey];
		wordCount++;
	}
}

I have attached the zip file with also the PDF file of the requirements. It will work within visual studio 2008

Life cycle

This course is in C++ each language is great to learn with but c++ is allot more fun at times since you have direct access the memory locations of variables :).

Anyway, here is the assignment 1, life cycles, I have included the full source code in the zip file attached. Life cycle, is when you have cells within a grid and the rules are (as taken from the assignment 1 PDF file within the zip file) where the neighbours are a 3 x 3 grid around the cell in question

The simulation starts with an initial pattern of cells on the grid and computes successive generations of cells according to the following rules:

  • 1. A location that has one or fewer neighbors will be empty in the next generation. If a cell was in that location, it dies of loneliness. Sad!
  • 2. A location with two neighbors remains “stable”

Console parameters

Someone asked me the other day when you are checking the console parameters for any passing in options how come something like

if (argv[i] == "-t")

does not work, well it does make sense when you look at it, but because the “-t” is actually a char[] (a string) then this would occupy a place in memory and thus you are checking against memory locations which unless you are very very very lucky, this would never come out correct, you need to use the string compare (strcmp) function as below

#include <iostream>
#include <string.h>
 
using namespace std;
 
int main(int argc, char** argv)
{
 for (int i =0 ; i < argc; i++)
 {
// output argument that was passed in.
   cout << argv[i] << endl;
// compare with "-t" option
   if (strcmp(argv[i],"-t")==0) cout << "the -t option" << endl;
 }
 return 0;
}

and the output would be something like

./consolet -t 40
./consolet
-t
the -t option
40

iterators – external wrapping of a class

As from the previous iterator post that wraps around a class (or within it as such, since that is where the implementation is). Here I am showing how to do some external wrapping of the class.

Since I am using Linux (with the KDE GUI) with a develop environment called kDevelop I have included the files with there full source code in the above zip file.

In essence the iterator interfaces (abstract classes that make you implement the methods required to allow for the iterator to work) are as defined as

template <class T>
class iteratorInterface
{
    virtual bool hasNext() = 0;
    virtual T next() = 0;	// next will also return the value
    virtual T getValue() = 0;
};
 
template <class T>
class iteratorInterfaceBaseClass
{
     virtual T begin() = 0;
     virtual T end() = 0;
};

when the actual class that is going to have a iterator external wrapper will implement the iteratorInterfaceBaseClass interface (abstract class with pure virtual functions “virtual T begin() = 0” where the “=0” is the pure part). Here is the class that is going to have a iterator external wrapping, if you notice it also implements the iteratorInferfaceBaseClass, with the anotherStackIterator being the actual iterator for the anotherStack class.

class anotherStack : public iteratorInterfaceBaseClass<anotherStackIterator>
{
  private:
    int intArray[MAXSIZE];
    int lastAdded;
 
  public:
    anotherStack();
 
    bool addValue(int value);
    bool addValueAt(int value, int place);
 
    int returnValueAt(int place);
 
    // for the iterator, return this and also NULL basically
    anotherStackIterator begin();
    anotherStackIterator end();
};

and here is the anotherStackInterface class structure, this does the implementation of a standard (std::) iterator in a forward direction (std::forward_iterator_tag) with returning a int (eger) value.

class anotherStackIterator : public iteratorInterface<int>, public std::iterator<std::forward_iterator_tag, int>
{
  private:
      int theStackRef;
      anotherStack *theStack;
 
  public:
      anotherStackIterator(anotherStack *stackP)  : theStack(stackP) { theStackRef = 0;}
 
      bool operator==(const anotherStackIterator otherValue);
      bool operator!=(const anotherStackIterator otherValue);
      int operator++();
      int operator++(int);
 
      // as from the iteratorInterface
      bool hasNext();
      int next();
      int getValue();
};

in essence all you are doing is looping through the data that you implemented in the main class (anotherStack) how you want to, for example when you want to setup the iterator and then loop through like this

    anotherStack stacky;
    stacky.addValue(4);
    stacky.addValue(2);
    stacky.addValue(10);
 
 
    for (anotherStackIterator iter = stacky.begin(); iter!=stacky.end(); iter++)
    {
	printf("value %d\n", iter.getValue());
    }

the iterator (iter) has to implement the iter++ process, a way to increment the pointer to the next data item within the anotherStack data structure and here is how it is done

int anotherStackIterator::operator++()
{
    if (theStackRef < MAXSIZE)
      theStackRef++;
    return theStack->returnValueAt(theStackRef);
}

the theStackRef is just a integer value that holds the place within the integer array from the anotherStack class and all is what is returned a value within the data structure, but because in the loop there is a test against if the iterator value has reached the end of the array e.g. the != (not equal to) and here is the test for that

bool anotherStackIterator::operator!=(const anotherStackIterator otherValue)
{
    if (theStackRef >=MAXSIZE) 
	return false;
    if (otherValue.theStack == NULL)
	return true;
    return (theStack->returnValueAt(theStackRef) != otherValue.theStack->returnValueAt(otherValue.theStackRef));
}

the full source code is included within the zip file attached. I had fun doing this.

iterator – wrapping around a class

An iterator is when you implement a abstract way of cycling through data. I have below created a internal iterator wrapper that will allow the class to implement a iterator for that class. Below the class is kinder like a stack where you place one item at the root of the stack and then place another item in a link (next item) attached to the last node of the stack (where the last item is, be it at the root if empty)

You can create a wrapper for the class externally as well, but in this instance I am creating it internally.

To start with I have created a internal class within the stack class called a Node, the Node is the item on the stack (the data inserted in a array as such). Also I created a basic class definition at the top the class so that the rest of the class knows that there is a thing called a Node, but the implementation is below.

    // forward declaration for the class structure below.
    class Node;

As said before, there is a root node that, this is where the start of the array in essence is, and the last node, where the last inserted node as placed. On each node there is a method to return the value attached to that node and also a link to the next node on the linked list.

    class Node {
    public:
	Node(const int& val) : nextNode(NULL), nodeValue(val) {}
	int& getVal() {return(nodeValue);}
	Node* nextNode;
    private:
	int nodeValue;
    };

now we have the node class setup, which means that when we add to the stack we can now place the values added to a dynamic linked list and a way to go through them. Now we just need to add values into the stacked list.

void theStack::addValue(int valueToAdd)
{
    if (rootNode == NULL)
    {
	rootNode = new Node(valueToAdd);
	lastNode = rootNode;
    }else
    {
	Node* p = new Node(valueToAdd);
	lastNode->nextNode = p;
	lastNode =p;
    }
}

this will place the new item either at the root node or attached to the next node to the last added node and then re-sets the last node added to point to where the new node, so that when another node is added it will be added in the correct place.

Here comes the iterator part.

To start with the internal part of the class, the internal iterator wrapper as such, we use the iterator class to extend/implement the iterator functions that we have to implement for the iterator aspects to work, here I am using the forward_iterator_tag as part of the parameter to the iterator and also we are returning a int value (which is what the stack is implementing as a linked list of integers, if you want to return another type just put in what ever your return type is.

  class Iterator : public iterator<forward_iterator_tag, int>

here are function/methods of a iterator to allow the stack iterator to go through the linked list (array of integers).

  class Iterator : public iterator<forward_iterator_tag, int>
  {
    private: 
      // the intP is a integer pointer
	Node* intP;
    public:
	Iterator(Node* p) : intP(p) {}
	~Iterator() {}
 
	// assignment 
	Iterator& operator=(const Iterator& otherValue);
	// equal or not equal to
	bool operator==(const Iterator& otherValue);
	bool operator != (const Iterator& otherValue);
	// increment the pointer to the next value
	Iterator& operator++();
	// increment the pointer to the next next etc value
	Iterator& operator++(int);
 
	// return type here is a int because that is what I said at the top of the class setup
	// e.g. iterator<forward_iterator_tag, int>
	int& operator*();
   };

of course we need to know when the begin and the end of the linked list is, this is the root and the last nodes, for a iterator to know where to start and end when you are going from start to end with using a iterator style of coding. Here is a way of using the iterator to loop through the values added, below is code that setups up the stack (theStack) class with some values (5,10,3), and then using a for loop to go through the values within the linked list (this is where the iterator part comes in)

    theStack stacky;
 
    stacky.addValue(5);
    stacky.addValue(10);
    stacky.addValue(3);
 
    printf("Value in the stack was\n");
    for (theStack::Iterator theIterator= stacky.begin(); theIterator != stacky.end(); theIterator++)
    {
	// (int) wrapping the return value into a int type, *theIterator getting the pointered to value
	printf("%d\n", ((int)*theIterator));
    }

in the full source code below is the implementations of the iterator and the stack

#include <iostream>
#include <iterator>
#include <stdio.h>
 
using namespace std;
 
class theStack
{
    private:
    // forward declaration for the class structure below.
    class Node;
 
    // the pointers to the root nodes and the last node on the stack as such.
    Node* rootNode;
    Node* lastNode;
 
  public:
      theStack(): rootNode(NULL), lastNode(NULL) {}
      ~theStack() { delete rootNode; }
 
      // add objects to the DrawingObject
      void addValue(int valueToAdd);
 
 
  class Iterator : public iterator<forward_iterator_tag, int>
  {
    private: 
      // the intP is a integer pointer
	Node* intP;
    public:
	Iterator(Node* p) : intP(p) {}
	~Iterator() {}
 
	// assignment 
	Iterator& operator=(const Iterator& otherValue);
	// equal or not equal to
	bool operator==(const Iterator& otherValue);
	bool operator != (const Iterator& otherValue);
	// increment the pointer to the next value
	Iterator& operator++();
	// increment the pointer to the next next etc value
	Iterator& operator++(int);
 
	// return type here is a int because that is what I said at the top of the class setup
	// e.g. iterator<forward_iterator_tag, int>
	int& operator*();
   };
 
   // the begin and end of the iterator look up
   Iterator begin();
   Iterator end();
 
   //  here we define the Node class
  private:
    class Node {
    public:
	Node(const int& val) : nextNode(NULL), nodeValue(val) {}
	int& getVal() {return(nodeValue);}
	Node* nextNode;
    private:
	int nodeValue;
    };
 
};
 
int main(int argc, char **argv) {
    theStack stacky;
 
    stacky.addValue(5);
    stacky.addValue(10);
    stacky.addValue(3);
 
    printf("Value in the stack was\n");
    for (theStack::Iterator theIterator= stacky.begin(); theIterator != stacky.end(); theIterator++)
    {
	// (int) wrapping the return value into a int type, *theIterator getting the pointered to value
	printf("%d\n", ((int)*theIterator));
    }
    return 0;
}
 
 
void theStack::addValue(int valueToAdd)
{
    if (rootNode == NULL)
    {
	rootNode = new Node(valueToAdd);
	lastNode = rootNode;
    }else
    {
	Node* p = new Node(valueToAdd);
	lastNode->nextNode = p;
	lastNode =p;
    }
}
 
 
// the definitions of the class theStack
// Iterator class implementations 
theStack::Iterator& theStack::Iterator::operator=(const Iterator& otherValue)
{
  intP = otherValue.intP;
  return (*this);
}
 
bool theStack::Iterator::operator==(const Iterator& otherValue)
{
    return (intP == otherValue.intP);
}
 
bool theStack::Iterator::operator != (const Iterator& otherValue)
{
    return (intP != otherValue.intP);
}
 
// increment the pointer to the next value
theStack::Iterator& theStack::Iterator::operator++()
{
    if (intP != NULL)
      intP = intP->nextNode;
    return (*this);
}
 
// if the loop has a increment by more than 1 then just increment the value still by one.
// if you are implementing another stack then you could get to the next next next etc nodes
theStack::Iterator& theStack::Iterator::operator++(int)
{
    if (intP != NULL)
      intP = intP->nextNode;
    return (*this);
}
 
int& theStack::Iterator::operator*()
{
    return(intP->getVal());
}
 
theStack::Iterator theStack::begin()
{
  return(Iterator(rootNode));
}
 
theStack::Iterator theStack::end()
{
  return(Iterator(NULL));
}

Output would be

Value in the stack was
5
10
3