Program Flow | COMP101

This week, we’ll be expanding our understanding of what we built last week to add new features and explore some of the more advanced concepts which are fundamental to 'high-level' programming.

Looping statements

We have a few common looping constructs in programming languages. There are actually a few others, which look quite different and inspired by the 'pipeline' (|) approach I demonstrated before (streams/linq). There is also a form of iteration which doesn’t rely on loops at all - recursion, but we’ll revisit that later in the study block when we look at algorithmic strategies.

Note	Loop Walkthrough There used to be a walkthrough of how (while) loops work here, to streamline the content this has been moved, you can find it at: Walking Through Loops .

While Loops

While loops are one of the most basic forms of iteration (in theory, goto/jmp would be more primitive than a while but don’t use that). In theory you could while for everything, but there are many tasks that as programmers we do over and over again. We abstract away the parts of the loop we don’t care about to make our code less error-prone and easier to read.

Look at that first python example I showed you again. How much easier to read was the for version rather than the eventual while loop version I deconstructed it to?

For Loops

In C-family languages (C, C++, C#) we have another kind of loop which is fairly common. A loop where we start at a given value, perform a check and at the end of the loop we do some operation. - the for loop. This is actually the kind of loop I just emulated in the while loop.

for (int i=0; i<2; i++) {
    Console.WriteLine("{0:D}", i);
}

Is the same as:

int i=0; //(1)
while ( i < 2 ) { //(2)
    Console.WriteLine("{0:D}", i);
    i += 1; // (3)
}

initialisation (first bit of for loop)
condition (second bit of loop)
step (third bit of for loop)

(advanced) Actually, there is one slight difference, the while loop version i doesn’t go out of scope after the end of the loop, but I’ve already shown you how you could emulate that. Try to reproduce this behaviour as well (hint: extra brackets).

The foreach loop

There is one more kind of common loop. The foreach loop. This is the one which has the most variety in other programming languages. The concept is present but there are many different ways its written.

The general idea is that we have something we want to go through from start to finish, we want the items (in order) but we don’t actually care about the index of the item directly - just its value. We can more clearly communicate our intent to other programmers like this.

int[] numbers = new int[]{ 0, 1 };
foreach (int x in numbers ) {
    Console.WriteLine("{0:D}", i);
}
Console.WriteLine("done");

This should remind you of the python for loop. Why? Because it is the python for loop! When designing python, the developers decided that the foreach version was more useful, and chose to express for in terms of foreach.

Loops in our Codebase

Recall last week, we had a while loop in our code for our game as a last step. Hopefully this loop will make a bit more sense now.

Q Is while the most suitable kind of loop for this task?

Reveal Answer

If you don’t have lives or rounds then maybe, we want to keep asking the user about their choice infinitely until they get it right. If we have rounds then it makes more sense to use a for loop for this.

Arguably, you could use a for loop for lives. Because we’ll be modifying the value outside of the 'step' this could be confusing.

A foreach loop doesn’t make much sense as we don’t need to iterate through a collection.

Ending Iteration

Sometimes, we want the loop to end in a way that doesn’t rely on the condition being met. In my example, I recommended using break as a way to accomplish this. Let’s talk about what this does.

There are two ways in which we might want to alter iteration in the loop:

We might want to 'stop' the loop completely
We might want to 'skip' this iteration, but continue on with the next iteration of the loop

Break

The most common way to break out of a loop when the condition is not met is to use a break; statement. This will jump the program to the end of the loop, as if the condition had just been met, skipping the rest of the code.

Last week, I used this as an extension task to break out of the loop when the user got the number correct.

Continue

The other case, we can use the key word continue. This can be handy if there is some cases that you can’t skip ahead of time, but when they come up you want to be able to skip them. For example, error checking.

for (int i=0; i<10; i += 1) {
    if ( i % 2 == 0 ) {
        // number is even, ignore
        continue;
    }
    Console.WriteLine("{0:D} is odd", i);
}

Admittedly, this is a bit of a contrived example. In this case, you could just modify the step to be i += 2 and the initialisation to be int i=1 and cut the number of iterations in half. In my sample code, I avoid needing a separate loop for error checking (prompting the user for the number again) using continue.

Some programmers would argue my approach is bad form in this case (I would usually agree with them). It would make more sense to split the code into a separate function, and have a loop for just dealing with input. In fact, that’s one of the things I want you to do today. But before that, we’re going to add some loops to our code.

Adding Rounds

If you haven’t already added a loop for checking if the user has guessed the number correctly, do so now. I dropped loops on you last week at the very end because the alternative was to make you rerun the program every time you guessed. If you’ve not encountered loops before, that can be quite challenging. Hopefully, it’ll make more sense now.

As we’ve covered loops in a bit more detail, and you should have everything you need for one of the (other) extension tasks from last week. We’re going to add rounds to our game.

Example 1. Adding rounds

If your game doesn’t already, make the game work over multiple rounds:

Each time the player guesses a word correctly or runs out of lives restart the game. This is a round.
After 5 rounds, the whole game should end
Display the number of correct gussses after the 5th round

Implement this using a for loop. If you are using my code, I implemented this feature using a while loop. Convert this into a for loop.

By this point, your game should have:

The basic guessing game
- A way of choosing a target number (possibly hard coded to a specific number)
- A way of prompting the user for input
- A way of figuring out if the guessed number is correct
Lives, or at the very least a loop which asks the user to guess the number repeatedly
Rounds

Writing Functions

Last week, we used functions (methods) from other classes. This week, I want us to start thinking about how we might be able to break our own code into our own methods.

The code I have given you only makes use of one function, main, and I suspect (as I’ve not shown you any different so far) that your code probably is as well. Some people were making use of functions in their own versions last week.

There are a few reasons why we might want to split code into separate functions, the two most common are:

Increasing readability, by abstracting away behaviour in our Main method
Making our code re-usable (avoiding copy and pasting code) by putting things we do a lot in functions.

This falls into a set of techniques called refactoring. We are going to make the code easier to read/understand without actually altering what the code does.

Functions as Abstraction

Lets look at the abstraction case first. Read through your code (or mine, if you are using that). Try to identify 'blocks' of code that are responsible for doing a given task in the project.

Identify some blocks of common code in your project.

Reveal Answer

Here are some common blocks that I might identify:

Deciding what number to use
(extension) Fancy Emoji string calculations
Getting the guess from the user, and validating it
Number checking logic

Some of these are easier to split out than others. The number input part of the code is reasonably self contained, but something like the number checking logic interacts with our the rest of code in complex ways (for example, altering lives and score, breaking out of the loop).

For each of these, we need to identify what information this block of code needs to know to work, and what its output will be. For very simple functions, we usually only have one return value (actually, in C# we always have one return value, but there are other ways to 'return' values — that’s not for now though).

Heart Emojis

Here is the block of code which I’ve identified as being suitable for a function:

                    string lifeString = "";
                    for (int i = 0; i < MAX_LIVES; ++i)
                    {
                        if (i < lives)
                        {
                            lifeString += "\ud83e\udde1";
                        }
                        else
                        {
                            lifeString += "\ud83d\udc94";
                        }
                    }

I’ll walk through one of the cases I identified with you - the emoji string generation. Remember what we need for a function:

A name (MakeHearts)
What we need to know to perform this operation (arguments) - the total number of hearts and the number that are left
What the function will give us (a string containing the heart emojis)

Tip	Functions go inside classes (so this should be inside your class, but not inside your main function).

Now we can start crafting our function signature:

static string MakeHearts(int lives, int MaxLives) {
    // function body goes here
}

Functions, like most things with curley brackets, are their own scope. Arguments are bound to the function scope, they get created when the function is called and disappear at the function’s closing curley bracket. Nothing inside our Main method will be accessible inside the function. We need to pass anything we need in as arguments.

Note	In my code, `MAX_LIVES` is in the scope of the `class`, so you could avoid adding the MaxLives argument, you can already access it.

Now we can put the code we wanted to put in the function inside the function body.

static string MakeHearts(int lives, int MaxLives) {
    string lifeString = "";
    for (int i = 0; i < MaxLives; ++i) // (1)
    {
        if (i < lives)
        {
            lifeString += "\ud83e\udde1";
        }
        else
        {
            lifeString += "\ud83d\udc94";
        }
    }
    // missing line here, see below (2)
}

I’ve changed this line to use the value passed in (MaxLives) rather than the class-level MAX_LIVES
This is where we should return a value from this function

Note	Because this is its own scope, we can call the variables whatever we like. We could even use the same names as variables in other functions. They are completely separate. This catches out a lot of new programmers, and it’s why I introduced scope so early.

Returning from Functions

Recall that functions are their own scope, the lifeString variable we create inside this function will disappear when the function ends. We want to pass (return) a copy of this string to the calling function. To return a value we use the keyword return followed by the variable name we want to return.

return lifeString;

Invoking our function

Recall that to use a function, we pass in the arguments we would like in ordinary brackets (, ) after the function name. We need to store the returned value to a variable (or you could use it directly). For consistancy, I am using the old variable name. I don’t need to - I could call it anything I wanted.

    string lifeString = MakeHearts(lives, MAX_LIVES);

We now have our complete MakeHearts function. All that’s left to do is replace the code in our Main with a call to this function. Delete the code you copied out of the main method, and replace it with the method call:

while ( lives > 0 ) {
    string lifeString = MakeHearts(lives, MAX_LIVES);
    Console.Write("\t {0:S} Enter a number between 0 and {1:D}: \u25b6 ", lifeString, MAX_NUMBER);

    // and so on...

Example 2. Making More methods

Put the code for dealing with your user input handling in its own function. Remember to ask the questions I used above to help design my function signature:

What should it be called?
What does it need to know (if anything)
What should it give us back?

There is more than one correct answer for this. I would be tempted to also include my prompt in this function.

Tip	you can use `return` like you used `break` in a loop, to 'return early' from a function.

Reveal Possible Solution

Here is how I might approach that problem. I have not attempted to run this code. It probably contains errors.

It’s here to show you what I thought my approach might be, not to be used :).

int getInput(int lives) {
    // this won't change while this loop is running, so we can do it outside the loop
    string lifeString = MakeHearts(lives, MAX_LIVES);

    while( true ) {
        Console.Write("\t {0:S} Enter a number between 0 and {1:D}: \u25b6 ", lifeString, MAX_NUMBER);

        string? guessStrOpt = Console.ReadLine();
        string guessStr = guessStrOpt ?? "";

        // validation (number)
        bool valid = int.TryParse(guessStr, out guess);
        if (!valid)
        {
            Console.WriteLine("\t That was not a valid number.");
            continue;
        }

        // validation (range)
        if (!(0 <= guess && guess <= MAX_NUMBER))
        {
            Console.WriteLine("\t that is not in the valid range.");
            continue;
        }

        // we can use return rather than break, because we want to jump to the caller
        return guess;
    }
}

Functions for Reuse

Often, we’ll encounter the same problem with slightly different arguments. We can use functions to avoid duplicating copying and pasting code over and over again in different places. There aren’t many cases of this in my code for last session.

Arguably, we’ve dealt with cases where that would come up using loops. However, its something that will crop up quite a lot in programming. When we encounter it in a future lab script I’ll point it out.

Instances

All of the methods we’ve been using have been static. This is because we are not using instances yet. This idea is core to object orientation, and many of the quite interesting things that object-orientation offers.

Let’s make use of our first instance to make our game a bit more fun (assuming you’ve been using a hard-coded number).

You can think of classes like a type (int, bool, float, etc…). The class Dog would be a type, describing all the methods and properties which make sense for the concept of a Dog. Your friend’s Dog, Fluffy would be an instance of Dog.

Non-static and static methods

Static methods belong to the type, which is why we have been able to do what we’ve been doing up until now. We are describing things that belong to the concept of Guessing Game Program - with all the logic happening inside of a few methods, and nothing existing outside of them.

Non-static methods are bound to a particular instance of that type. You don’t feed() the concept of Dog, you feed() Fluffy. (I’m not sure why I didn’t use the concept of Cat, I have a great many cat pictures I could have used here).

The same is true for non-static variables which exist at the level of the class (properties). The concept of Dog isn’t brown, Fluffy is brown.

Random Numbers

Ok, why am I going on about this. Random numbers.

C# has Random class which we can use to generate random numbers. It turns out random numbers are very hard for computers to generate, so in most cases, we can simply fake it and generate numbers which look random. In reality, they are using a complicated (or sometimes quite simple) algorithm to alter some internal state and generate a new random-ish looking number.

This is state that needs to exist between function calls, and we don’t want every single random number generator to share its state. So it makes sense to use instances for random number generators.

Note	I’ve used 'state' a few times in this paragraph. Think of 'state' as a collection of variables which make up the class. The state of your game would be: the current round, the current lives remaning and the current 'real' number.

How do we create a new instance of the Random class?

Random rng = new Random();

Ah! It looks like a variable declaration of type Random! Why? Because it is! Another way of thinking about classes is to think of them as creating your own types. That’s effectively what you are doing.

The new keyword tells C# that we’d like a new instance of the class random. It may seem a bit silly to mention the class twice, there is a reason for this. It’ll come up next study block when you encounter Polymorphism and inheritance. When you create an instance you can also provide additional information — maybe you’d provide a name for a dog or something like that. Random doesn’t need you to provide any information (although you can provide the internal state it should start with, called a seed - yes that’s why Minecraft levels are described by seeds, it’s the initial state of the random number generator used for generating levels).

Anyway, now we have our random number generator, we can invoke methods on it. We can look through the documentation for what Methods exist. The documentation is quite extensive with quite a few examples.

Example 3. Add a random number generator

If you have not done so already, add a random number generator to your name for deciding what number to pick.

Arrays

I mentioned that the version of the game I had was always solvable. The algorithm I used is called binary search. You can use this recursively, but my approach for this was iterative.

Here is some example pseudocode for this approach, we’ll be looking more at pseudocode next week.

SOLVE( game ):
    SET low to be the smallest possible number
    SET high to be the biggest possible number

    WHILE Running:
        CALCULATE guess AS halfway between low and high (low + high) / 2
        PROVIDE guess TO game
        READ response FROM game

        IF response is "Too Big":
            SET high TO guess
        ELSE IF response is "Too Small":
            SET low TO guess
        ELSE
            PRINT "Correct guess?"
            PRINT guess
        END IF
    END WHILE

Example 4. Binary Search

Implement this algorithm in code so you can use it to solve your game. It does not need to be in the same project.

We half the number of possible numbers each iteration, that means that we can calculate the maximum number of steps as log2(N) where N is the number of possible numbers. Log2(100) = 6.64385618977. We can’t .6 guess, so we’ll need at most 7 attempts.

That’s in the worst case, what about solving it in less than 7 attempts?. We could figure this out analytically, but you’ve probably guessed from the title of this section (it being Arrays not Maths) that’s not what we’re going to do.

The full 'experiment' that I would like to perform requires too much refactoring for me to set as a non-extension task. But we are going to set the groundwork for it before that phase. We are going to keep track of how many guesses it took to solve the game as a histogram.

We could create a bunch of variables for this:

int NumberOfTimesOneGuess = 0;
int NumberOfTimesTwoGuesses = 0;
int NumberOfTimesThreeGuesses = 0;

But this gets silly very quickly. Instead, it would be useful to keep track of a 'block' of guesses together. We have a structure which lets us store multiple copies of a type together in memory; the array (list in python).

Creating Arrays

int[] guesses = new int[ MAX_LIVES ];

This will create a new int array, with every value set as 0 to start with. Arrays are a fixed size - you set the size when you create it and it can never change.

To update a slot (index) in an array you put the index you want to update in square brackets:

Note

code reuse and variables

You probably have noticed I had a few private static int variables in my class when I gave it to you. Why is this? I could just put 8 anywhere in the code I wanted to know about the maximum number of lives, but if I did that then I would need to change the code in many places, if I wanted to drop this to 7 (I set it at 8 so I could mess up once in the demo and still solve it). I only need to change MAX_LIVES if I wanted to do this in my version of the code. This is also the argument for functions as code reuse from earlier.

Updating Arrays

guesses[1] = guesses[1] + 1;

This will take the current contents of guesses[1] and update the value by 1. Arrays start at 0, so this will actually update the second value (not the first one).

Example 5. Histrogram of Values

Keep track of the number of guesses (might be easier to track 'lives remaining') when the round ends. Careful with how you will handle losses vs guessing on the last life.

Before the start of your rounds loop, create an array which is at least number of lives long
When the user guesses correctly, keep track of how many lives they had left
Update the array by adding one in the correct location
After the final round has been played, print out the counts in a for loop

(advanced) use the 'heart logic' code I gave you earlier and formatting strings to make it look like this, where the size of the bar is dependent on the number of guesses, assume that there will never be more than 10 guesses per 'life count'.

Histrogram of gusses:

0 [===       ] 3
1 [==        ] 2
2 [=         ] 1
7 [===       ] 3

(more advanced) Do the same, but this time don’t assume there are 10 guesses per life count - base it off the total guesses in the histogram.

(Advanced) The game that plays itself

Modify your game to rather than ask for user input, uses the binary search approach to play the game. You may need to make some of the variables which are currently local to functions be static and in the scope of the class to make this work.

To be clear. This is an advanced extension task. This is hard. It would take me a while to figure out how to refactor this code in a way that makes this work nicely. You should be able to do this just using the things we’ve covered so far, but there is a lot of reasoning involved as to how you would structure this.

Make it classy

For more of a challenge, You also could create a class to represent the game, and another for the solver. Then manage the game state and solver state using properties (instance variables). This would probably be the ideal solution, but requires some things we’ve not covered yet - you will need to conduct research on how to do this. You could also make the game playable by both your 'ai/bot solver' and human players using this approach.

Extension: Altering the Game

Here are few extension tasks for students that would like to extend the game further:

If you are feeling overwhelmed

Let the user choose the difficulty of the game, selecting a different number range (eg, easy = 0-42, medium = 0-100, hard = 0-1000)
Figure out the 'worst case' lives for each of your difficulty settings and only give the players that many lives

Hint:

float maxGuesses =  Math.round(6.3);
int maxGuessesInt = (int)maxGuesses;

If you are feeling confident

Easy Mode: rather than provide binary (lower, higher, correct) feedback, provide more complex feedback (much lower, lower, correct, higher, much higher)
At the moment, the game assumes the starting number is 0. How could you modify this game so that the starting number could be different?
Allow the user to select their lowest and highest number, if the range is invalid (eg, lowest is bigger than highest, or they are the same) ask for a new range

(advanced) If you want a challenge

Hard Mode: rather than randomly selecting the number, pick numbers which require the maximum number of guesses assuming the player is doing binary search
Restrict the range in a more complicated way (only allow even numbers, or powers or two, or similar).
Provide a few different sets of numbers (even, odd, powers of two) and let the player choose which set to use.
- Only let them provide guesses which are in the set of possible answers (the legal actions)

(advanced) Remixing the game

Remix the game to work with another dataset (eg, latitudes of capital cities). This will require storing the data in the program and choosing one at random when the program starts.

For this, it would be good to tell the players what the legal options are (eg, provide it on the prompt or give them a command to check).

Hint:

string[] cities = new string[]{"london", "paris", ...};
float[] latitudes = new float[]{51.509865, 48.864716, ...};

Additional Reading

Iteration Statements In C#