Category: Languages

The programming directory

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.

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

delegates – settings function on the fly

Delegates allow a virtual method/function (static method) to be called via a link (which is the delegated variable). I have done a post before about delegates but kinder think and also have been asked how do you link one to a class and also change the delegated function due to a user input, so here goes.

I have started with setting up what type of method that I want to be associated with the delegated variable, this will be a mathematical function of either addition or subtraction with using integer values, so we need to return a integer value and also pass in two integer parameters, so a new delegated virtual method would be

public delegate int mathsOp(int value1, int value2);

and here would be a example of a method that the delegate is able to link to, because it takes 2 integer parameters and returns a integer value

public int add(int value1, int value2)
{
	return value1 + value2;
}

so we now have the delegate declaration and also a method to be able to point to, so we now need to setup the variables, one for the actual functions (MathClass that is holding the subtraction and addition methods) and also the delegated variable theMathOp that is a delegated type.

MathClass mathFunc = new MathClass();
 
mathsOp theMathOp;

to actually set the method up on the fly, you just need to tell it where you want the delegated type to point to

theMathOp = new mathsOp(mathFunc.add);

and all is needed to call the delegated type variable, well you just call it like any other method

theMathOp(inputValue1, inputValue2);

that is about it, here is the code in full that will take in some values from the user and also the user is able to choose between addition and subtraction methods

using System;
 
namespace newDelegates
{
	// a maths holding delegated function
	public delegate int mathsOp(int value1, int value2);
 
	class MathClass
	{
		// the functions to call within the class
		public int add(int value1, int value2)
		{
			return value1 + value2;
		}
 
		public int sub(int value1, int value2)
		{
			return value1 - value2;
		}
 
	}
 
	class MainClass
	{
		public static void Main (string[] args)
		{
 
			// setup the maths class which has the functions inside to call
			MathClass mathFunc = new MathClass();
 
			mathsOp theMathOp;
 
			// there is no error checking in the inputs!!
 
			Console.Write("Please enter value 1 : ");
			int inputValue1 = Convert.ToInt16(Console.ReadLine());
			Console.Write("Please enter value 2 : ");
			int inputValue2 = Convert.ToInt16(Console.ReadLine());
 
			Console.WriteLine("Please enter maths function :");
			Console.WriteLine("1 : add");
			Console.WriteLine("2 : sub");
			int mathsInputFun = Convert.ToInt16(Console.ReadLine());
			// setup the virtual function to which ever the user wants
			switch (mathsInputFun)
			{
				case 1 : 
					theMathOp = new mathsOp(mathFunc.add); 
					break;
				case 2 : 
					theMathOp = new mathsOp(mathFunc.sub); 
					break;
				default :
					Console.WriteLine("Settings to add");
					theMathOp = new mathsOp(mathFunc.add); 
					break;
			}
 
			Console.WriteLine("Value 1= " + inputValue1 + (mathsInputFun == 1 ? " + " : " - ") 
			                  + " value 2 = " + inputValue2 + " = ");
 
			// here we call the virtual function that was setup
			Console.WriteLine(theMathOp(inputValue1, inputValue2));
		}
	}
}

and below is the output of two runs of the program, one using addition and the other using subtraction

Please enter value 1 : 3
Please enter value 2 : 2
Please enter maths function :
1 : add
2 : sub
1
Value 1= 3 +  value 2 = 2 = 5
 
second run through
 
Please enter value 1 : 5
Please enter value 2 : 2
Please enter maths function :
1 : add
2 : sub
2
Value 1= 5 -  value 2 = 2 = 3

Reflection – Calling functions

With c++ you can call functions as a reference instead of the actual name, as long as the reference is linked to the function itself (I did a post about it function pointers and also within csharp delegates)

To start with, we need to sort out what function we want to use to call, I am going to pick a function that returns a value and also passes parameters (kinder covers all aspects really), so this is going to be the function

public String addsTogether(String st1, String st2)

So to start off , lets build up the parameters to pass to the function, we have two string parameters, so we need to have a array of 2 strings.

String[] passingParameters = { new String("genux"), new String("was here")};

Now we need to setup a link to the function that we want to call, we setup a class instance with using the forName (which is the function name). Also because the function takes 2 String parameters we need to setup blank classes that are both Strings in types.

Class callingClass = Class.forName("CallMethodClass");
 
Class[] callingParameters = new Class[2];
callingParameters[0] = String.class;
callingParameters[1] = String.class;

this is the main part, this is the link, we create a Method (from the java.lang.reflect package) that links to the class function/method “addsTogether” (the function at the start of this post) and also the parameters type and length (2 strings).

Method callingMethod = callingClass.getMethod("addsTogether", callingParameters);

that is about it, all we need to do is to call the function now and that is it, so we use the Method link above variables invoke method, this takes the class that the function is wrapped within and also the parameters that we want to send to the function (method and function are kinder interchangeable) and that is about it. Since the returning value is a String (and we know this) we will need to case the returning type into that by using (String) otherwise it would be a type of Object (the base object type in java)

String result = (String)callingMethod.invoke(new CallMethodClass(), passingParameters);

Here is the source code in full (Save as CallMethodClass.java if you want to compile it up)

import java.lang.reflect.Method;
 
public class CallMethodClass {
 
	// adds together the two strings with inserting a space between them
	public String addsTogether(String st1, String st2)
	{
		return st1.concat(new String(" ").concat(st2));
	}
 
	public static void main(String[] args) {
		try
		{
			String[] passingParameters = { new String("genux"), new String("was here")};
			// setup the link to the class to call
			Class callingClass = Class.forName("CallMethodClass");
			// passing parameters to the callingClass, the method has two String parameters
			Class[] callingParameters = new Class[2];
			callingParameters[0] = String.class;
			callingParameters[1] = String.class;
			// and now setup the method to call
			Method callingMethod = callingClass.getMethod("addsTogether", callingParameters);
 
			// call the method and get the return (convert to a String)
			// pass in the parameters here, when calling (invoking) the method
			String returnValue = (String)callingMethod.invoke(new CallMethodClass(), passingParameters);
 
			// and now output the result
			System.out.println("OUTPUT : "+returnValue);
		} catch (Exception e)
		{
			System.out.println(e.getMessage());
		}
	}
}

here is the output of the program

OUTPUT : genux was here

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”