PyTutorial: Into the Realm of the Infinite

This is the 6th in a series of posts.  If you want to go the the start, go here.

Up to this point, every little program that we wrote took some time to run, but not too much.  You can probably imagine writing a program that runs for a bit longer, by, for instance, looping on a larger list, or doing a loop within a loop within a loop within a loop....  Something like that.  But can you imagine making something that runs.... forever?

Well, usually forever isn't really what you want to achieve, what is more likely is that you want to make something run indefinitely.  For instance, say you want to make a computer game, you may want it to run until the player wants to quit.  It may take a few seconds (if it's boring), or, as I experienced once playing Civ 2, well, a few days.  Yea, it was pretty sad.  But the idea is that you want the program to run until something happens, and then quit.

Of course, at its core, a computer program is just a bunch of loops and ifs.  The for loop that I showed you thus far doesn't let you do something like this.  What you want instead, is a loop that while a condition is true, keeps looping!  In python (and many other languages), this is called, wait for it.... wait for it... a while loop!  :)

Can you figure out what that does?  Type it in and try it out!  Basically, a while loops has a condition (in our case, it's "x > 5"), and while that condition is True, the body of the loop gets executed.  Of course, in Python, the body is the part that's indented after the while:

Of course, the example above isn't very interesting because it can be written as a for loop.  In fact, whenever you can use a for loop instead of a while loop, you probably should.  But I'll go into why a bit later.  For now, I just want to you get a feel for what a while loop looks like, and how it works.

Assignment 6.1: rewrite the above while loop as a for loop.  HINT: re-read the documentation on the range function to see what you can do with it... :)

One of the built-in functions that Python has to offer is called "raw_input".   Go ahead and read about it.  Basically lets you ask the user to type something in the keyboard.  To see how you can use while loops indefinitely, check this out:

Can you follow what it does?  Type it in and see what happens!  You're probably asking yourself: why is there a "True" after the while, and what is this whole "break" business? Well, I'm glad you asked me!  :)

Remember how I said that so long as the condition in our while loop is True, then the loop keeps going?  Then what better way to make sure that it's always true, and thus have the loop goes on indefinitely, than actually giving "True" as the condition?  :)  You see, this is my way of asking Python to loop for ever and ever and ever...  Since True is always True, then the loop will always run!

But in our case, we don't actually want it to run forever, we just want it to run until someone types in "moo", right?  Well, we need to have a way to break free and get out of this endless loop of ours, right?  Well, to our convenience, Python gives us the "break" command, which tells it to forget everything and just get out of the loop already.   By the way, this also works in for loops:

See that?  What do you expect to see happen?  Type it in and try it out!

Assignment 6.2: write a for loop that prints out the numbers from 10 to 100, but let the user stop any time in the middle by typing in "foo".

 Got it?  Great!  But before we continue on with while loops, I want to introduce you to break's twin sister, continue:

Type in the above code and see what happens!  Can you figure it out?

Basically, continue tells Python to drop what it was doing in the loop's body, and keep going with the next item in the loop!  Thus in the above example, because "print a" happens after the continue in cases in which a > 3 and a < 7, it doesn't get run for them.  Whereas break tells Python to stop whatever it was doing in the loop body and exit the loop, continue tells Python to stop whatever it was doing in the loop body and keep going with the next item in the loop.  See the difference?

Continue also works in while loops.  Of course, there's no "next item" in while loops, so what it does is stop processing the body of the loop, and then go back to the start.  There, as always, it first checks if the condition is True, and if so, it continues...

Can you figure what the above does?  Can you?  Type it in!

It basically does what the previous code did, but with a while loop instead of a for loop.  Do you see how it works?  Great!

Assignment 6.3: write a while loop that keeps printing compliments (such as "you look good today") to the screen.  Of course, give the user an option to stop this whenever they had enough... :)

Do you remember that I previously mentioned that whenever you can use a for loop instead of a while loop, you probably should?  The reason for this is that the additional flexibility that while loops give you to write indefinite loops come with a hefty price:  a little subtle coding mistake can give you a loop that "gets stuck" forever.  Check out what happens when all you do is move the "a = a + 1" part of the loop body to the end of the body, like this:

Can you see the problem here?  It may not be very obvious.  Of course that's part of the problem, that it's not very obvious.  :)  Type it in and run it!  Just be prepared to go to the menu in the Python Shell, choose "Shell", and then "Restart Shell".  :)  Go ahead and do this.  Now! :)

Great!  Did you notice something odd...?  Perhaps you noticed that the program just sort of got "suck".  It didn't finish like before...  That is, you didn't get the ">>>" prompt in the end, as usual.  Why was this?  Well, welcome to the realm of the infinite!  :) You just got yourself what we call in the industry, an "endless loop".

To get a better feel for what's actually going on, move the "print a" from towards the end of the body to the very start, like so:

What do you see now?  Do you see a whole bunch of "4" getting printed to the screen?  Can you figure out why this happens?

When a equals 4 (or more specifically, when a > 3 and a < 7), the loop reaches a "continue".  Remember how continue tells Python to stop everything in the loop and go back to the beginning?  Well, it now skips over the "a = a + 1" part, and thus a remains 4 forever!   Nice, huh?

You're probably thinking to yourself: this really sucks!  And you would be right.  That really does suck.  In fact, a lonely programmer can spend endless hours wasting trying to figure out why some code like this gets stuck.  In a simple program like we have above, this may not be too bad, but you can imagine a more complicated piece of code, one with a bunch of loops and functions, and what not, and all of a sudden, the code gets stuck.  Good luck trying to figure it out.  Especially if the code is already running on some customer's computer.  Yea, that will be fun for you, I promise.  :)

Thus remember our old friend, unit testing, which should help find most of these problems.  Still, some problems may still slip though the cracks.  This is the motivation for my recommendation to use a for loop whenever possible.  Because a for loop has a set number of items that it can go through, code that uses it is usually not only more elegant, but also safer.  Safer from endless loops like the one that you saw above.

So why ever use while loops anyways, you ask?  Well, as I started the tutorial, many times you do want things to run indefinitely!  In those situations, a while loop is what you need to use.  Just make sure to test it and make sure that it always has a way to actually stop running!

A little practice

As you saw, while loops are useful when you want to make a loop run indefinitely, waiting on a user to make some sort of decision to end the loop.  But indefinitely doesn't necessarily mean waiting on a human to make some decision.  Sometimes, the number of times that the loop needs to run isn't very obvious for the programmer.  

For example, take the series of square numbers.  That is: 0*0, 1*1, 2*2, 3*3, 4*4... 

0, 1, 4, 9, 16, 25, 36, 49, 64, ...

If I asked you to write a loop that prints the first n items in this series, you can definitely use a for loop.

Assignment 6.4: write a function, call it square_n, which takes in an input parameter n, and returns the nth item in the square series.  square_n(5) returns 25, square_n(7) returns 49, etc.  You don't need a loop to solve this.  Try solving it without a loop, but then try again with a loop, just for the exercise. 

But what if instead of wanting the nth items in the series, I want a function that returns the first item in the series that is greater than a particular value?  For instance, if that value is 10, then I would want the number 16.  Or if the value is 20, I would want 25.  For 5 it would be 9, for 49 it would be 64, etc.

You can probably see that it's not clear when a particular value is reached in the series (assuming you don't have the ability to find the square root of a number, of course).  That is, you would need to loop through the items in the series for as long as it takes until you get the number that you want!  Since you don't know how long its going to take ahead of time, you need to use a while loop here!

Assignment 6.5: write a function, call it square_greater_than, that given a value n, returns the first item in the square series that is greater than n.  Remember to unit test this is various values, just to make sure it works well!! 

That wasn't easy, but it should demonstrate the value in using a while loop.  Did you get an endless loop in the process?  It happens... While loops are harder to work with than for loops, but sometimes, it's the only option you have.  Fun!

As another example, take the Fibonacci Series.  If you never hear of it, it's basically the list of numbers in which each item in the list is the sum of the two previous numbers.  Read on it on Wikipedia, it's actually kidn of neat.  By definition, it starts with 0 and 1.  Thus, the list is:

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, ...

Can you see how each item in the list is the sum of the two previous ones (for instance, 13 = 5 + 8, etc.)  Great!

Assignment 6.6: write a function, call it fib_n, which takes in an input parameter n, and returns the nth item in the Fibonacci Series. 

Of course you know what's coming up, don't you? :)

Assignment 6.7: write a function, call it fib_greater_than, that given a value n, returns the first item in the Fibonacci Series that is greater than n.

Very good.

Calling on the infinite

There's another way to do things endlessly, that that's using functions!  How is that possible? You ask.  Well, all you really need to do is have a function call itself!  In tech-speak, this is called recursion.  Check this out:

What do you think will happen?  Type it in and try it out! :)

Can you figure out how this worked?  Recursion consists of four main parts.  The first is the starting position, or initial condition in tech-speak.  In our case, it's the number 10 that we passed to x in x(10).  That's what we have to start out with.  There is also the end-condition, which tells us how this recursion is going to end.  In our case, it's the check that a < 0.  You can imagine that without a good end-condition, well, similar to a while loop, you end up with an endless recursion.  There's also the step, in which we go from one situation to another.  In our case, it's when x calls itself, but with a value one less than what it got, that is, when it called x(a-1).  Of course, there's also the part of the function that actually does something useful.  In our case, it's just printing the value in a.  Do you see that?

You can see that we basically achieved a loop, without using a loop!  Nice, huh?

Of course, using recursion to print the numbers 10...0 is a bit of overkill.  I just showed it to you so you can see how it works.  But in the above example, you're much better off using a for loop, and even a while loop is better than recursion in this case.  So when should recursion actually be used?  Well, as usual, this is a matter of elegance.  Some problems simply become clearer when recursion is used!  Usually, this is the case when you can break up a larger problem into a bunch of smaller, yet similar problems. 

Take our good old Fibonacci Series.  Do you see how each item in the series is the sum of the two previous items?  In fact, when you wrote fib_n, you did just that.  You had some for (or perhaps even a while) loop that saved the previous two values and that way calculated the next.  But can you think of a way to use recursion to achieve the same end?  That is, to write a function, fib_r, which takes in an input parameter n, and returns the nth items in the Fibonacci Series. but does so without a loop at all!  Can you achieve this by having fib_r call itself?

Think about it.

How can one do this?  Well, to get the nth value in the Fibonacci Series, what do we need to know?  We need to know the value of the n-1 item in the series, as well as the value of the n-2 item in the series.  If we had these two values, all we need to do is add them up, and that way we end up with the value of the nth item!  Easy!  Of course, we need to be careful not to end up with endless recursion!  Let's think about this in terms of what we had above:

• Initial Condition: the request for the nth item in the Fibonacci Series
• End Conditions:
• If ask for an n < 1, return None
• If ask for n == 1, return 1
• If ask for n == 2, return 1
• Step:
• Call itself to get the n-1 item
• Call itself to get the n-2 item
• Action:
• Add together the sum of the n-1 and n-2 items, and return the sum.

Now, let's put all this together into a function:

Try it out!

What's nice about recursion here is that it makes the logic of how to calculate the Fibonacci series pretty straight forward.  One disadvantage of using recursion here instead of a for loop actually has to do with performance.  Can you figure out why?  Add a print statement at the start of fib_r that prints to the screen the value of n that it is being called with, and the call the function with fib_r(7) or something.  What do you see?  Try to figure out what happens. 

Now it's your turn.  Use recursion to calculate the factorial of a number, n (that is, n! in mathematics.)  For example, 5! is 5 * 4 * 3 * 2 * 1 = 120.  

Assignment 6.8: write a function, factorial_r, which, using recursion, returns the factorial of a given number, n.

That wasn't too bad, was it?

BTW, recursion is only infinite in theory.  In practice, it's very limited.  In fact, try to write a recursive function that doesn't have an end condition.  Go ahead and try it!  If that happens, you should get some error such ash:

RuntimeError: maximum recursion depth exceeded while calling a Python object

The reason for this error is that every time you call a function, it takes up memory.  When the function returns, the memory is freed up!  Thus recursion can't really go on forever (as opposed to a while loop) because eventually memory runs out.   Python tries to give you some information about what happened by limiting the depth of recursion that it allows, and it can thus give you a clear error.  It is possible to change this limit, but then you just end up running out of memory, and get an error message like this one:

MemoryError: stack overflow

The stack is the part of the memory that is set aside specifically so functions will be able to call each other.  The heap, on the other hand, is the part of the memory that is set aside for you to store information such as lists and maps and numbers and strings.  Usually, the heap is much-much-much larger than the stack.  But you can reach that limitation as well, can you figure out how?   You can reach this limitation by writing an endless while loop that all it does is append some value to a list.  This way the list keeps growing and growing, eventually, it will take up all the available memory, and you should get some sort of memory error.  Try it!  When I did this, I got a less informative error message:

MemoryError

That was that.  :)

Usually, you won't ever reach these limitation, but it's just something to keep in mind.  If you do need to work with a lot of information, you may need to use files, which can be quite huge.  There are many ways to do this, and that's for another time, but the main disadvantage of using files is that they're slow compared to using memory.  On the other hand, files are your way of keeping information from one time the program runs to the next (imagine you want to keep a list of "high scores" to a game that you write, etc.)  I'll go into this later, but I just want you to know that you may reach these memory limitations, but that there are ways to work around those limitations as well.

I want to end this discussion of recursion with this little funny funny:

Nice Python...

Previously, I sent you to the Python website to read a little about Python's built-in functions.  Now, I want you to see some more things you can do with the language.  Again, you don't need to memorize everything, but it's good to be aware of a few things:

• Some more details on different ways you can define functions.  The topics that I find most relevant are:
• Default argument values: if no input parameter value is given, can use some predefined value instead.
• Keyword arguments: instead of giving input parameters as a comma-separated list, in which the order is very critical, can pass the input parameters as name-value pairs, similar to maps.
• Arbitrary argument lists: not super useful, but lets you define a function without specifying  exactly how many parameters it needs.
• A way to "slice" strings and lists.  Read what they have to say, but basically slicing is a way to get parts of a string or list.  Say you have the string, s, you already know how to get a particular character in it, say the 3rd, by calling s[2].  If you want the part of the string that is between the 3rd and 5th index, you call call the string like this: s[2:5].  Play with it a little and see how it works.  The same is true for lists.  The online tutorials give some examples as well.
• Some more things you can do with lists, and some new data structures such as sets.  A lot of what's in there is interesting, but some things to keep in mind as you go through it:
• Some of the things here will be completely new to you.  That's ok, I'll go over some of these stuff later, but you can just play around with their examples and see what happens.
• In one example, they use the '%' operator.  All it does is give you the remainder of a division.  For example, '11 % 3' equals 2.  That's because 11 / 3 = 3 with remainder 2.  '10 % 5' equals 0, because 10 / 5 equals 2 with no remainder.
• In another example they use the '**' operator.  That gives you some number to the power of another.  For example '3 ** 2' is 3 squared, which equals 9.  '4 ** 3' is 4 to the power of 3, which equals 64.

Play around with what looks interesting to you, just to get a feel of what you can do and how it works.

What this lesson needs is more Minesweeper!

In the previous lesson, I had you write a lot of the "core" functions that any Minesweeper game would need.  Now I want you to complete them, and actually end up with your very first Minesweeper game.  One that you will remember and treasure forever.  It's not going to look pretty (I'll show you how to do that later), but it'll actually work.  It will be a game that anyone can play!  Sure, it'll be mostly just you playing it, but it's going to be fun.  Trust me.  Well, let's get started!

A little user-interface

Anyone playing your game (that is, you), is going to want to interact with it. (duh!)  Part of that interaction is actually seeing the Minesweeper grid.  Sure, you wrote PrintGrid() in the previous lesson, but that was just for debugging purposes.  You want to be able to print the grid to the screen in a way that makes sense to the gameplay.  This means:

• Make it look as simple and elegant as possible, that is, make it look as much like a player would expect the game to look!
• A cell that no wasn't clicked on can be represented by, say, a question mark: '?'
• A cell that a player marked as flagged should be represented by, say, an asterisk: '*'
• A cell that has been clicked on, but has a mine, should be displayed as an 'X'
• A cell that has been clicked on, but has no mine, should display the number of neighbors that it has that have a mine.  Thus, this can be anywhere from the number 0 to 8.  Of course, this isn't exactly how the real game is played, but we'll get there. :)
• Anything else that you can think of

You can write the above function, call it, say, DisplayPlayerGrid(grid).  Of course, part of the requirement here is to be able to display the numbers of neighbors that contain a mine.  There are a few ways to achieve this:

One way is to write a function, say, CalculateNeighborsWithMines(), that takes in a grid, as well as the x and y coordinates of the cell you're interested in, and returns (after checking) the number of neighbors that have a mine. 

Another is to figure out in advanced how many neighbors have a mine.  This is possible because in Minesweeper, neither the grid doesn't change nor do the mines move around.  If you want to go with this approach, I recommend changing the information in each cell to include the number of neighbors.  Then, after calling AddMinesToGrid(), call another function UpdateNeighborsWithMines(), that takes in a grid, and updates each cell with the correct number of neighbors (it can use the function CalculateNeighborsWithMines() if you want.)

There are more ways to do this, and you can also make little changes to the above two approaches.  Basically, however way you want to approach this problem is fine, just make sure that it makes sense to you.

BTW, this is great function (they all are, really), for unit-testing.  It's a complicated task, but inputs and expected outputs are pretty straight forward.  So be a pro and remember to unit-test this code!! :)

Letting the player actually do stuff...

Of course, just displaying the grid isn't much of a game.  What is missing is a way for the player to affect the game.  In other words, we need some user input.  You already know about Python's raw_input() function, and this is a good place to use it! No matter what you type in, raw_input() will always return a string.  If you want to turn it into a number, you can use the int() function:
>>> x = "3"
>>> num = int(x)
>>> type(num)
>>> print num

Of course, if x isn't a string that can be converted into a number (for instance, if x is "hi"), then you'll get an error message.  I'll tell you all about how to handle such errors later, for now, just be nice and type in the kind of values that are expected.  If you're really curious, and simply can't wait for the lesson after the next, you can read all about handling such exceptions (tech-speak for errors) right here.

Let's get back to the game!

Can you think of how the game should be played?  What sort of interaction will the player have with the game?  I can imagine something like this:

• Print some welcome message and explain the rules
• Ask the user to select a grid size (or just offer one size)
• Ask the user to select the difficulty, that is, the probability that each cell will contain a mine.  (or just offer one such probability)
• In a loop:
• Show the user the player-friendly grid
• Ask the user for a desired action.  Her available choices will be:
• Flag/Unflag a position
• Check a position
• Quit the game
• Act on the player's desired action:
• If Flag/Unflag was selected:
• Ask for the x,y coordinates to update
• Update the coordinate
• If check a position was selected:
• Ask for the x,y, coordinates
• Check that coordinate
• Check to see if the game was lost or won.
• If it was lost:
• Write something sad and quit the program
• If it was on:
• Write something happy and quit the program
• If quit the game was selected, well, um... quit the game! :)

The above is called pseudo-code.  Pseudo-code is tech-speak for writing a program in a logical, yet very high-level manner.  There's no rule specifying what is "high enough", it's just supposed to be a tool to help you think and design larger programs.  Use it if it helps, don't if it doesn't. :)  

So the above pseudo-code is just what I think should happen in a normal game of Minesweeper.  If you think differently, that's fine!  Just change the pseudo-code and write whatever you what!  Heck, it's your game!! :)

Go ahead and write the entire game!!  Take the time you need, but it should be fun!  

Come back when you're done! :)

Were you able to do it?  Congratulations!  I knew you would. ;)  Now go out and celebrate!

Are you ready for a little challenge?

Remember your good old AddMinesToGrid() function?  Sure, it works, but it doesn't work exactly how real Minesweeper games do now, does it? Do you see where I'm going with this?  I had you write it so that as an input parameter, you can specify the probability that each cell will have a mine.  That's great, but not exactly what we want.  

In a real Minesweeper game, you can specify the exact number of mines that you want to have in the grid!!  Right?? Right???  Well, in order to write this correctly, you'll probably want to use a while loop.  And since I didn't teach you about while loops in the previous lesson, I didn't have you write the correct version of AddMinesToGrid() then.  But now is a good time to have you do that! :)  So go ahead, modify AddMinesToGrid() to take both a grid as input, and also a number that specifies the exact number of mines to place inside it!  Of course, they need to be placed randomly in the grid, so this is going to be a little challenging.  But I believe in you.  :)

Whew!  That was tough, wasn't it?  But it was well worth it.

And there you have it!  You have written your first real Minesweeper game!!  That's just plain awesome.  In some future lesson I'll teach you how to also make it look good.  But making the game, not matter what it looks like, is no small achievement!

Go get some rest. :)

In the next lesson, I'll introduce you to classes.  Classes are just ways to organize your program better.  In a way, they let you group together information and functions that relate to one another....  Exciting!