Category Archives: Programming Gems

Today I Learned: Tail Call Elimination

Who said interviews were just about testing knowledge? In some cases, it can be a bit of a learning experience for everyone involved. Case in point, I was asked about what kind of compiler optimization may be made from the following code:

int CountOccurences(LinkedNode const * const head, int const dataToCount, int occurences)
{
	if (head == nullptr)
	{
		return occurences;
	}
	if (head->data == dataToCount)
	{
		++occurences;
	}
	return CountOccurences(head->link, dataToCount, occurences);
}

My initial reaction was that maybe the compiler would attempt to do something to our const vars on the stack, considering they never change in the function. Turns out, there is something more going on here.

Continue reading

Rubiks Cube AI Part 1 – Parity

Rubiks Cubes! I cant solve them to completetion for the life of me. But now I can just solve them using an AI.

But before jumping into heuristics, A* algorithms, and all kinds of solving. First, let us consider a random Rubiks Cube itself. Is the cube actually solveable in the first place? Can we go from the random state pictured above to a solved cube?

The answer is no. The Rubiks Cube parity has been altered!

Continue reading

Recommended Viewing: Ubisoft CppCon 2014

Checkout these two great talks from Ubisoft @ CppCon 2014 featuring multicore C++11 development and how C++ is used to develop AAA games at Ubisoft. I briefly met Nicolas Fleury and learned many tips from blurbs he’s written about good C++ practices and such. He’s very talented.

 

 

Programming a Boggle Algorithm

Recently had to figure out how to program a Boggle algorithm. Boggle is a simple board game I never had the pleasure of playing by itself, but have played plenty of related variations of. These kinds of algorithms are pretty interesting and I had a lot of fun programming different solutions. I’ll share 2 solutions.

Boggle is relatively simple. I never had the pleasure of playing by itself, but have played plenty of related variations of.

You have a square game board with dice of various letters that is n x n. The board gets shaken/randomized and a timer starts. The player scores points by finding valid words on the board that are longer than 3 characters, with longer words scoring more points. The rules are that letters have to be adjacent or diagonal to the last letter in the word to continue. And you can never repeat a letter you’ve already used, so while you can have multiple of the same letter, its the die itself you can’t return to.

I decided to tackle it in C++.

Continue reading