Coder Dojo! -- Tracing Through Code

Coding, that thing that lets us humans give a series of instructions to a computer that can be translated into a low-level, machine-readable language, where the only limit is your imagination! Through numerous trial and error, every program and application goes through numerous 'builds' and compilations, carried out each time a fresh build is required. Before all that nitty gritty however, it is vital for any aspiring programmer to learn the subtle art of "tracing"

'Tracing! What, you mean like drawing over something?!'

No, not quite, my friend. Tracing, in a computer context, is when, after you look at a snippet of code, you try and determine on paper the result produced by that piece of code after it is carried out by the program at run-time. It's possible that this 'technique' goes by several names, but we've called it 'tracing' here or 'stepping through the program.'

Basically, it's like working out a maths problem.

'Rightttt....So what's the point of this topic, then?'

I'm glad you asked! In a nutshell, every month I shall post here part of a computer program, and all you have to do is work out, on paper, what value it will output to the user at run-time! Whilst you may use a compiler to see what value the code outputs if you wish, you must show how you arrived at a given value, be it on paper or digital art.

Bear in mind that I'm far from a competent programmer myself (still an undergraduate, after all), so please forgive me if the code snippets I post contain syntax errors and whatnot.

I shall largely be posting code snippets done in C++, but will branch out to C#/Java (near enough the same thing, anyway) and possibly a few legacy languages too as I myself become more familiar with those languages. Maybe even the dreaded assembly language, simply for kicks, heheh.

I will permit members asking questions about certain aspects of posted code snippets, but again I must ask that any member who wants to make an attempt at tracing through the code must post an image of how they arrived at a value.

Now....Onto the code!

 

Code Snippet #1;
Language; C++
Recursion

Spoiler

//Functions called in main
Mystery(5);
Rose(7);
Cabin(20);

//Recursive functions
int Mystery(int n)
{
if (n == 1)
return 1;
else
return n + Mystery(n - 1);
}

int Rose(int n)
{
if (n == 0)
return 1;
else
return n * Rose(n - 1);
}

int Cabin(int n)
{
if (n == 1)
return 0;
else
return Cabin(n / 2) + 1;
}

 

Ah. Apologies! I'm not very good at explaining stuff...

Basically what I'm looking for is the console output of the code. But, instead of just running it through a compiler and let a machine do the number crunching for you, I want you step through the program on paper. I guess I really should've given a value that is passed to each code snippet...whoops.

All right, please allow me to rephrase things; What do you get when you pass the following values to the functions given above;

Mystery(5)
Rose(7)
Cabin(20)

 

I must admit, that was a great trace you've done, @[member="Fantasma"] ! Don't worry, I'm not too concerned about semantics. You can give wordy explains or you can use pseudo code, I don't mind.

Yup, I can confirm that those are the correct results, well done!

Yeah, the recursion for 'Cabin' is daaaamn tricky (I myself do not get it 100%). But from what I understand... in the return statement, outside of the call to itself, because we're only asking for a 1 back, the function, when it hits the unwinding stage it counts every recursive call to itself, and returns that value. So that's 1+1+1+1 = 4. We can see this in practice if we slip in a print command in the non-base case, 'else' part of the function, before recursion commences;


else
{
cout << n << endl;
return Cabin(n / 2) + 1;
}

Console output;


Well, I guess I'll leave this thread open for suggestions for future coding samples. So fire away, guys!

 

Oh, like make a scripting language version of this? Sure, go ahead! I'd love to see that happen, go right ahead.

As for the next coding snippet I'll post here, I am looking around, so no worries there. I might do something with tracing through a Towers Of Hanoi problem next.

 

That's great to hear. But, before this thread inadvertently turns into a chat thread, I'm gonna lock it for now.

Alternatively, why don't one of you create a topic about Programming? Maybe talk about what projects you're working on, ask any q's you might have. I won't have a problem with it, as long as your posts are meaningful and, naturally, abide by the rules.

 

Welcome back, everyone! Today I'll be sharing a new coding snippet, so I hope you enjoy it!

Code Snippet #2;
Language; C++
Towers Of Hanoi
For those of you who saw the 2011 "Rise of the Planet of the Apes" film, you might have seen this technique being used to test the intelligence of the apes. (Though in the film it was called "Lucas' Tower"). The towers stem from an ancient Brahmin tale that says the life of the universe is defined in terms of the time it will take a group of monks (working continuously) to move a set of 64 gold disks, all of different diameters, from one pole to another. There are however specific rules about how the transfer should be done, and they alone causes such a trivial project to take a long time to complete.

So you have three 'towers', essentially, with a certain number of disks stacked on the first tower on the left. The aim is to stack them all again, in the exact same order, on tower 3, the last tower on the right. The tower in the middle, tower 2, can be used to temporarily stack disks. How many moves does it take to accomplish this, bearing these rules in mind?

Towers of Hanoi Rules (PLEASE familiarise yourself with these, if you do not already know then!)

Spoiler

1. Only one disk may be moved at a time.
2. A third pole may be used for temporary storage of disks.
3. No disk should ever be placed on top of a disk of smaller diameter.
4. The disks are arranged on the original pole initially with the largest disk on the bottom, the second largest disk on top of it, and so on. The smallest disk ends up being on top of the stack.

Now that the preamble is out of the way, walk me through how you'd move 4 disks, using the following implementation file.

Spoiler

/*TowersOfHanoi.cpp*/

#include <iostream>
using namespace std;

void Hanoi (int n,int start, int finish, int temp);

int _tmain(int argc, _TCHAR* argv[])
{
int disks = 4;

cout << "\n Towers of Hanoi: Solving a problem of size "
<< disks << endl;
Hanoi (disks, 1, 3, 2);
return 0;
}

void Hanoi (int n,
int start, int finish, int temp)
{
if ( n == 1)
cout << "Move top disk from pole "
<< start << " to top of pole " << finish << endl;
else
{
Hanoi (n-1, start, temp, finish);

cout << "Move top disk from pole "
<< start << " to top of pole " << finish << endl;
Hanoi (n-1, temp, finish, start);
}
}

As a side activity, I've also decided to include something else for y'all to do. The following message has been encrypted with a Caesar Cipher. I want you to decrypt the Ciphertext and show me the plaintext. Have fun!

Spoiler

OCDIBN OCVO BJ WPHK DI OCZ IDBCO
NCJPGY IJO MZVGGT BDQZ JIZ V AMDBCO
DO'N OCZ CJGZ DI ZVXC ZVM
OCVO GZON DI OCZ AZVM
OCVO VIY OCZ VWNZIXZ JA GDBCO!

 

@[member="Steamlined"] Verrrry impressive work! (heck, the way you decipher is way neater than mine, actually!) Yup, you've decrypted the message successfully. (Though it appears you left out the last too words. )

Hah, tenacious, I see!

How about the rest of you? @[member="Fantasma"] , @[member="Kouhai"] ? Anyone else wanna take on the code snippet? Don't be shy now.

 

@[member="Fantasma"] Fair enough. That's fine. Anyone else? One than one can try their hand at tracing through the code.

 

@[member="Kouhai"] That's another great solution! And yep, that's the message. It never struck me to make a program to encrypt a message. Hmm. Food for thought.

I've also amended the Towers Of Hanoi code a teeny bit. So if you want to see what message your compiler throws out once you run the code, be my guest.

 

@[member="Kouhai"] I tend to flip-flop between two. Visual Studio Professional versions 2012 and 2013. I mainly use the 2013 version, whereas a lot of my older projects were done in 2012.

 

Well, it's been a while, but here's something new for y'all to trace through!

Up now; Quicksort

Here's a problem that's been annoying me for the past week or so.

So then, to business;

You've got an unsorted array[8] of integers;

13


48


38


18


45


4


43


55


...Which we want to apply a QuickSort function to;

Spoiler

void QuickSort (ItemType values[], int first, int last)
{
int splitPt1, splitPt2;
if (first < last)
{
Split(values, first, last, splitPt1, splitPt2);
QuickSort(values, first, splitPt2);
QuickSort(values, splitPt1, last);
}
}

You'll notice that the QuickSort function in turn calls a Spilt function...

Spoiler

void Split(ItemType values[], int first, int last,
int& splitPt1, int& splitPt2)
{
Itemtype splitVal = values[(first+last)/2],t;
int i = first, j = last;
while (values < splitVal) i++;
while (values[j] > splitVal) j--;
while (i < j)
{
t = values; values = values[j]; values[j] = t;
i++; j--;
while (values < splitVal) i++;
while (values[j] > splitVal) j--;
}
if (i == j)
{
i++; j--;
}
splitPt1 = i;
splitPt2 = j;
}

So get to tracing, folks! Gonna be a tough one for sure.