## What will we cover in this tutorial?

We will first explain and understand Tower of Hanoi programming challenge. It is one of those programming challenges that are highly liked among programmers.

• Understanding the problem is easy.
• Solving it seems difficult.
• Using recursion makes it easy and elegant to solve.

You should be one of those that masters the Tower of Hanoi.

## Step 1: Understand the Tower of Hanoi challenge

Tower of Hanoi is a mathematical game, which has three rules. Before we set the rules, let’s see how our universe looks like.

The disk all have different sizes as pictured above.

The goal is to move all the disks from on tower (rod) to another one with the following 3 rules.

1. You can only move one disk at the time.
2. You can only take the top disk and place on top of another tower (rod).
3. You cannot place a bigger disk on top of a smaller disk.

The first two rules combined means that you can only take one top disk and move it.

Say, in the above we have moved the disk 1 from the first to the second tower (rod).

After that move, we can move disk 2 or disk 1.

The third rule says, that we cannot move disk 2 on top of disk 1.

Those are the 3 rules of the game.

Now do yourself a favor and try to think how you would solve that. How do you get from here.

To here following the 3 rules.

## Step 2: Recall recursion and unleash the power of it

Recursion is a method of solving a problem where the solution depends on solutions to smaller instances of the same problem.

https://en.wikipedia.org/wiki/Recursion_(computer_science)

While that is a beautiful and perfect definition – there is still need to exemplify what that means.

A simple example is to sum up the numbers from 1 to n.

It can be a bit difficult to connect the definition of recursions to getting the sum of the integers 1 + 2+ 3 + … + (n – 1) + n.

Let’s first try to do in the iterative way.

```def summation(n):
sum = 0
for i in range(1, n + 1):
sum += i
return sum

print(summation(10))
```

While there is thing wrong with the above solution, you can turn that into a recursive function by the following.

```def summation(n):
if n == 0:
return 0
return n + summation(n - 1)

print(summation(10))
```

As you see, the problem of summing the numbers from 1 to n, is actually reversed to sum the numbers n, n – 1, n – 2, …, 1. You also notice, that it is true that the summation(n) is equal to n + summation(n – 1).

Wow, that was it. We are breaking the problem down to a problem of smaller size. Just like the definition said.

Also, notice the importance to have a base case in the function. In the above we choose for n == 0 to return 0. This ensures that the recursive calls to not continue forever (or when the Python interpreters stops due to maximum recursion depth).

Try it.

```def summation(n):
return n + summation(n - 1)

print(summation(10))
```

Well, what did we gain from making the function recursive?

Good question. The above might not be a good example of how recursion helps you. The example of Tower of Hanoi will show you the benefit. It will make your code easy and straight forward.

## Step 3: Implement Tower of Hanoi with a recursive function

Now we need to think recursive. Consider the problem again.

How can we break that down to a smaller problem?

Think backwards. Just like the summation from Step 2. What do we need to make happen if we should move disk 3 from first tower (rod) to the last tower (rod)?

Exactly. Then we can move disk 3 to the final destination.

And after that, we should move the smaller problem of the 2 disks on top fo disk 3.

Wow. That is the formula. It is all you need to know.

1. Move the smaller problem of 2 disks from first tower (rod) to second tower (rod).
2. Move the big disk from first tower (rod) to last tower (rod).
3. Move the smaller problem of 2 disks from second tower (rod) to last tower (rod).

Now we need to generalize that.

First understand that there can be any number of disks in an instance of Tower of Hanoi. This means that the problem starts with n disks. If we number the towers (rods) 0, 1, and 2.

Then we have that all n disks start on tower (rod) 0 and should end in tower (rod) 2.

Now we can break down the problem to the following. Given n disks that needs to be moved from start_tower to dest_tower (destination), using aux_tower (auxiliary).

1. Move subproblem of n – 1 disks from start_tower to aux_tower.
2. Move disk n to dest_tower.
3. Move subproblem of n – 1 disk from aux_tower to dest_tower.

See the code below.

```class Towers:
def __init__(self, disks=3):
self.disks = disks
self.towers = [[]]*3
self.towers[0] = [i for i in range(self.disks, 0, -1)]
self.towers[1] = []
self.towers[2] = []

def __str__(self):
output = ""
for i in range(self.disks, -1, -1):
for j in range(3):
if len(self.towers[j]) > i:
output += " " + str(self.towers[j][i])
else:
output += "  "
output += "\n"

return output + "-------"

def move(self, from_tower, dest_tower):
disk = self.towers[from_tower].pop()
self.towers[dest_tower].append(disk)

def solve_tower_of_hanoi(towers, n, start_tower, dest_tower, aux_tower):
# Base case - do nothing
if n == 0:
return

# Move subproblem of n - 1 disks from start_tower to aux_tower.
solve_tower_of_hanoi(towers, n - 1, start_tower, aux_tower, dest_tower)

# Move disk n to dest_tower.
towers.move(start_tower, dest_tower)
print(towers)

# Move subproblem of n - 1 disk from aux_tower to dest_tower.
solve_tower_of_hanoi(towers, n - 1, aux_tower, dest_tower, start_tower)

t = Towers()
print(t)
solve_tower_of_hanoi(t, len(t.towers), 0, 2, 1)
```

The code includes a simple print function to see the trace of the movings.

## Too fast?

Now this often seems a bit too fast. Didn’t we leave out all the subproblems?

That is the beauty of it. We actually didn’t

You tell the machine how to solve the problem using a smaller instance of the problem. This was done with the three things we did. First, move the subproblem away. Second, move the the biggest disk. Finally, move the subproblem on top of biggest disk.

How does that solve it all. See, you solve it for general n, hence, the smaller subproblems solves it by the same formula and we ensure the base case when there are no disks to move.

## What will we cover in this tutorial

Selection sort is one of the simplest sorting algorithms, which is a good algorithm to start with. While the algorithm is considered to be slow, it has the advantage of not using auxiliary space.

## Step 1: Understand the Selection Sort algorithm

The goal of sorting is to take an unsorted array of integers and sort it.

Example given below.

```[97, 29, 53, 92, 42, 36, 12, 57, 90, 76, 85, 81, 12, 61, 45, 3, 83, 34, 7, 48]

to

[3, 7, 12, 12, 29, 34, 36, 42, 45, 48, 53, 57, 61, 76, 81, 83, 85, 90, 92, 97]

```

The algorithm is the most intuitive way of sorting a list.

It works as follows.

1. Go through the list to be sorted and find the smallest element.
2. Switch the smallest element with the first position.

If you started with the following list.

```[97, 29, 53, 92, 42, 36, 12, 57, 90, 76, 85, 81, 12, 61, 45, 3, 83, 34, 7, 48]
```

You would now have this list.

```[3, 29, 53, 92, 42, 36, 12, 57, 90, 76, 85, 81, 12, 61, 45, 97, 83, 34, 7, 48]
```

Notice, that now we have the smallest element in the front of the list, we know that the second smallest element must be somewhere in the list starting from the second position all the way to the end.

Hence, you can repeat step the above 2 steps on the list excluding the first element.

This will give you the following list.

```[3, 7, 53, 92, 42, 36, 12, 57, 90, 76, 85, 81, 12, 61, 45, 97, 83, 34, 29, 48]
```

Now we have that the first two elements are sorted, while the rest of the list is not sorted.

Hence, we can repeat the two steps again on the unsorted part of the list.

If we continue this until the we reach the end of the list. This should give us a sorted list.

## Step 2: Implementation of Selection Sort

A beautiful thing about Selection Sort is that it does not use any auxiliary memory. If you are new to sorting, then this can be a big advantage if sorting large data sets.

The disadvantage of Selection Sort is the time complexity.

We will come back to that later.

The code of Selection Sort can be done in the following manner.

```def selection_sort(list_to_sort):
for i in range(len(list_to_sort)):
index_of_min_value = i
for j in range(i + 1, len(list_to_sort)):
if list_to_sort[j] < list_to_sort[index_of_min_value]:
index_of_min_value = j

list_to_sort[i], list_to_sort[index_of_min_value] = list_to_sort[index_of_min_value], list_to_sort[i]

list_to_sort = [97, 29, 53, 92, 42, 36, 12, 57, 90, 76, 85, 81, 12, 61, 45, 3, 83, 34, 7, 48]
selection_sort(list_to_sort)
print(list_to_sort)
```

This will produce the correct output.

```[3, 7, 12, 12, 29, 34, 36, 42, 45, 48, 53, 57, 61, 76, 81, 83, 85, 90, 92, 97]
```

## Step 3: The time complexity of Selection Sort algorithm

Now this is the sad part of this simple algorithm. It does not perform good. A sorting algorithm is considered efficient if it runs in O(n log(n)), which Selection Sort does not.

The simple time complexity analysis is as follows.

Assume we have a list of n unsorted integers. Then the first iteration of the list will make n – 1 comparisons, the second iteration will make n – 2 comparisons, and so forth all the way down to 1 comparison.

This is the sum of 1 to n – 1, which is found by this formula (n – 1)(n – 2)/2, which is O(n^2).

Other than that the algorithm does n swapping of numbers. This is O(n).

This combines the algorithm to O(n + n^2) = O(n^2).

## Next Step

This should wake your appetite to understand how you can make more efficient sorting.

Another good example of a simple sorting algorithm is the Insertion Sort algorithm.

For more efficient algorithm you should check out the Merge Sort algorithm.

If you want to be serious about sorting, check out my online course on the subject.

## What will we cover in this tutorial?

The key to use exceptions correct is to understand why we use them.

The best way to understand why to use exceptions is to see what happens when we do not use exceptions in our code.

After that exploration we will show how it can solve the examples with exceptions.

## Step 1: In the perfect world!

Remember those times before the exception was invented?

No? Well, of course not. It is long time ago, in a distant past in a programming language you probably have not heard about.

As an aspiring programmer, you have probably seen and heard about exceptions, but never put them to use yourself.

The best way is to create examples that can be greatly simplified with exceptions.

Let’s keep the world simple.

```def add(a, b):
return a + b

```

This would print out the result 5.

As long as the world is clean and everybody uses the function correct, there is nothing to worry about.

But what if someone calls the function with wrong types of arguments. Then the function does not do as expected.

```def add(a, b):
return a + b

```

This will print 23, which might be a bit surprising if you are not familiar with the function, and possibly how Python uses addition on strings.

So how to handle it.

## Step 2: In the real world where people do not use things as intended

As you will realize in your careers of programming, it happens that other programmers do not use your function correctly.

Why would they do that?

Maybe they don’t take the time to read the good documentation you wrote. Or maybe they are just careless and working under hard time pressure.

Even more funny, it could be you. It could be code you wrote a year ago (or less), and the documentation was not that good as you thought, hence, you use your own function incorrectly.

To continue the simple example. One way to handle wrong input without exceptions could be as follows.

```def add(a, b):
if type(a) is not int or type(b) is not int:
return None
return a + b

if result is not None:
print(result)
else:
print("Invalid input format to function add!")
```

Oh, no! What happened. Actually, your function is not that difficult to understand. It just starts by checking if the input format is as expected. If not, return an error code. As this is Python, an error code can simply be the value None.

That might seem fine. But what about the user of your function? Now the user needs to validate that the correct format of the result was returned.

This makes the code more complex. Also, the user of your function needs to know more details of how your function handles invalid input, or whatever can go wrong in your function.

The problem is, that you pass on a problem to someone else, which needs to know about the details of how your function works.

This is the opposite of decoupling. And decoupling is considered good. Easier to program, easier to change, easier to maintain, to mention a few benefits.

## Step 3: Solve it with exceptions

The core idea of exceptions is to handle the when something out of the ordinary happens from the main logic of a program.

What? Yes, the expected case in our simple function, is that the user provides integers as input. But it might happen they do not call it with integers. That is unexpected, that is something out of the ordinary, and this breaks the logic in how you would build the program.

So how should we do in the above example?

```def add(a, b):
if type(a) is not int or type(b) is not int:
raise Exception("Input format incorrect")
return a + b
```

Actually, your part of the obligations becomes easier.

How?

Because now you do not need to write complex documentation of the error return codes in your program. The documentation is kept automatically in the exception. It will even guide the user to where in the code the exception comes from.

```def add(a, b):
if type(a) is not int or type(b) is not int:
raise Exception("Input format incorrect")
return a + b

```

This would give the following result.

```Traceback (most recent call last):
File "/Users/admin/PycharmProjects/LearningSpace/test2.py", line 7, in <module>
raise Exception("Input format incorrect")
Exception: Input format incorrect
```

Which leads the user of the function to where in the code it went wrong. Then it will be easier for them to figure out what is wrong and how to fix it.

## Step 4: Try-catch from the user

It happens that the user of your function would like to handle the special case.

They now master what is going wrong, and want to inform their users of the problem.

```def add(a, b):
if type(a) is not int or type(b) is not int:
raise Exception("Input format incorrect")
return a + b

try:
except:
print("The input format is incorrect")
```

This leads to something you might not notice at first. It leads to a good easy flow in your program. It is easy to read and understand.

It is clear that this is not intended flow in the except-part of the program. Also, the normal flow in the program would be in the try-part.

It makes it easier to understand, which is the ultimate goal of a good programmer. Make your code easy to read for others. That is, including you in less than 6 months (we do forget our own code and the logic in the programs we write faster than we expect).

## What will we cover in this tutorial?

Wonder why some of these trivial questions are popular in coding interviews?

The truths is, they have a depth of hidden aspects which uncovers whether you understand the the true nature of the problem.

Often, there is no right and wrong solution. It depends. Can you answer what it depends on?

In this tutorial we will investigate the Anagram Problem.

What they are really looking for is your underlying understanding of algorithmic time complexity (big-O analysis) and your ability to improve on solutions.

This tutorial will show one example of this.

## Step 1: What is the Anagram Problem?

The first part of a coding challenge problem is to show that you understand it. Many underestimate this part and do not realize how important that is.

Often the problem statements are a bit vague, but given with some examples. It could be directly taken from wikipedia and ask you to implement it.

An anagram is a word or phrase formed by rearranging the letters of a different word or phrase.

https://en.wikipedia.org/wiki/Anagram

Or as it could be stated in you interview question: Given two strings, str_a and str_b, return whether they are an anagram of each other.

First, you need to understand the problem. Often there will be examples to show you what an anagram is.

An examples could include.

• “Listen” and “Silent”

Where you notice that the letters in LISTEN are the exact same as in SILENT, just in a different order.

What you also notice is that the lowercase and uppercase of the letters do not matter.

The definition says also phrases, hence, examples of anagrams include.

• “a gentleman” and “elegant man”
• “eleven plus two” and “twelve plus one”
• William Shakespeare” = “I am a weakish speller”

The last example is quite interesting, as it shows that the number of spaces do not seem to matter. The phrase “William Shakespeare” has 1 space, while the phrase “I am a weakish speller” has 4 spaces.

Now your part is to show that you understand it. In this case it would be good to state an input that will return True and one that will return False.

Say, “evil” and “vile” as input returns True, while “evil” and “test” will return False.

If you do not understand it, don’t worry. Imagine that you do not admit it. Then what is the best that can happen? Are you by any chance going to guess it out of the blue? Most likely not.

The best you can do is to admit it and explain as good as you can as much of what you think you understand.

## Step 2: Find edge cases and set restrictions on input

A natural next step is to consider edge cases and set restrictions. Most would jump into writing some pseudo code and try to solve it. Don’t be that type of person. Take a deep breath and remember what we said in Step 1.

What did we observe in Step 1?

1. That uppercase and lowercase is ignored when considering anagrams.
2. That the number of spaces do not matter when considering anagrams.

Now this is important to notice.

An advise is to simplify as much as possible in a job interview. But you need to tell them that you do simplify the problem.

Hence, you can say.

1. You assume that input will be all in lowercase.
2. That input will not have spaces.

Is this reasonable? Well, it simplifies your code a lot. If they want you to consider these cases, they will let you know.

The importance of this step cannot be stressed enough. Because, if you just assumes that you can restrict input and write your code, they might now you have considered theses cases.

On the other hand, if you do set it as restrictions before hand they know you have thought of it.

## Step 3: The naive solution

The next step is to make a solution. As you might not come up with the best solution first, a good way is to start with whatever comes to your mind and call it the naive solution.

It is always a good idea to write it down. This will help you get a better idea to solve it more efficient afterwards. Notice, that the restrictions you made in Step 2 comes in handy now, as you can construct an easy solution fast now.

How could a naive solution look like?

```def is_anagram_naive(str_a, str_b):
if len(str_a) != len(str_b):
return False

for c in str_a:
if c not in str_b:
return False
else:
str_b = str_b.replace(c, '', 1)
return True

print(is_anagram_naive("silent", "listen"))
print(is_anagram_naive("elevenplustwo", "twelveplusone"))
print(is_anagram_naive("anna", "anaa"))
```

The question is how does it perform?

Well, first the check of the length of the string should be in constant time, O(1). If the underlying interpreter does not have an efficient implementation, then it could be O(n) time, where n is the length of str_a and str_b.

The loop over str_a is O(n). In each loop it will check if the character c is in str_b. This check is implemented to be faster than brute force. In an job interview you are not expected to remember that. It is good enough to say O(n) in first iteration.

Then we notice that it will use n, n-1, n-2, …, 3, 2, 1 operations in total to do this test. This results to n(n-1)/2 operations, which is O(n^2) in total.

On top of that, it will use the same to replace the character c in str_b.

That means the algorithm uses O(n^2) time complexity in worst case.

## Step 3: Improving the performance

This is where it gets interesting. Now you showed you can solve the problem. The next step is to show that you can improve it.

How to get an idea?

It lies in the previous step. What is the time complexity. You need to improve on the performance. What is often better than O(n^2)?

Yes, a natural next improvement would be O(n log(n)). What algorithms do you know? Well, sorting, can that help?

What if we sort the characters and compare them in order, then they must be identical if it is an anagram. Try to sort the characters of any anagram. Example, “silent” becomes [‘e’, ‘i’, ‘l’, ‘n’, ‘s’, ‘t’], and “listen” becomes [‘e’, ‘i’, ‘l’, ‘n’, ‘s’, ‘t’], identical.

This makes sense. As they have the same characters, they must come in the same order if we have them sorted.

Let’s try.

```def is_anagram_improved(str_a, str_b):
if len(str_a) != len(str_b):
return False
list_a = list(str_a)
list_b = list(str_b)
list_a.sort()
list_b.sort()
for l1, l2 in zip(list_a, list_b):
if l1 != l2:
return False
return True
```

We start by checking if the length of the strings are the same, if not, return False, as it cannot be anagrams.

Then convert the strings to lists. It should take O(n) time. Now for the expensive step. Sorting it. This takes O(n log(n)) time.

Finally we check the characters one by one, in sorted order, if they are equal. If not, we do not have an anagram. This takes O(n) time.

That is, it uses O(n) + O(n log(n)) + O(n) = O(n log(n)) time.

You did the first improvement.

Can you do better? I know, this is annoying. But maybe we can. Let’s try.

## Step 4: Improving the code – a common pitfall

Well, you are a shark at Python. Hence you know you that the above can be made into a more Pythonic code.

You feel on fire.

Yes, this can be done smarter, you say.

```def is_anagram_pythonic_way(str_a, str_b):
return sorted(str_a) == sorted(str_b)
```

It does actually do the same and in only one line of code. Isn’t that what coding is all about. You showcase how good you are and how much you know?

Well, both yes an no.

Yes, because it does show you are familiar with coding in Python.

No, because it did not improve the algorithmic time complexity. It still runs in O(n log(n)).

So what is gained? What did you tell the interviewer?

They are looking for improvement of the algorithmic time complexity or space complexity. Hence, showing them a smarter way to write the code does not add many points to the book.

I know it feels awesome to write a one-liner that does the same, but that is not what they are looking for.

The advice is, limit your time on improving lines of code, if it does not improve the algorithmic time complexity or space complexity.

## Step 5: Improving the performance again

There is often a even better way to solve this things.

How do you get an idea to do that? Well, look at what takes time in the algorithm from Step 3. It is the sorting. Without the sorting step, you could have an algorithm in O(n) time.

Can we do something different than sorting?

What does the sorting do for us? It arranges the characters in order, repeating each character with the number of occurrences.

What if we had a table and just updated the number of occurrences of each character?

Let’s try.

```def is_anagram_further_improvements(str_a, str_b):
occurrences_a = [0]*256
occurrences_b = [0]*256
for c in str_a:
occurrences_a[ord(c)] += 1
for c in str_b:
occurrences_b[ord(c)] += 1
for i1, i2 in zip(occurrences_a, occurrences_b):
if i1 != i2:
return False
return True
```

First notice we just assume 256 characters, which is not needed for the assumption. It just simplifies some calculations of the characters. In a job interview they are not looking for the optimal final solution, just if you understand the concepts of big-O time complexity.

The initialization of the size 256 occurrences counters is independent of the size, hence O(1) time.

Then the following two for-loops take O(n) time. Finally, the last for-loop takes O(256) = O(1) time.

This is a total of O(n) time complexity of the algorithm.

See, we could do some awesome stuff together.

## Conclusion

Is this the perfect written solution? No, this is a job interview. Time is limited. It is important to show what they are looking for.

Do you understand big-O time complexity. Do you see how a simple solution can be improved?

The anagram is one of the favorite coding interview problems, because it has this natural flow of improving it. They do not expect you to remember the optimal solution. But they expect you to reason your way forward as we did in this tutorial.

## What will we cover in this tutorial?

I did them myself. When you first learn about object oriented programming, you get exited about it and want to turn everything into objects.

Very often it fails to make the code easier to maintain and understand. Yes, that is one core goal of creating object oriented programming, to make it easier to maintain and understand.

Often we just turn the traditional way of programming into objects. But that is not the point. The point is to model it in an object oriented way.

Before that, let’s just look at why we use object oriented programming.

## Step 1: Why use object oriented programming?

When introducing object oriented programming to beginners it often introduces too many concepts at once.

Simply because object oriented programming is awesome and can do so many things.

Let’s just start simple with the core of the object oriented programming idea.

We want to make your program easier to understand and maintain.

That is the goal for any programmer. Also, when it comes to object oriented programming.

Object oriented programming tries to make the link between the real world and the programming world as close as possible. We humans understand the objects in the real world better than we understand how a computer pushes bits and bytes around in the memory and CPU.

Luckily, we do not need to understand all that. We just need to understand how to program the computer through a programming language.

Object oriented programming tries to make that easier with modeling the programs with objects, which are related to the way we humans understand things.

Let’s try with a simple example of a Stack.

How would you model the above without using object oriented programming.

```stack_size = 8
stack = [None]*stack_size
top = -1 # empty stack

def pop():
global top, stack
if top == -1:
return None
else:
top -= 1
return stack[top + 1]

def push(element):
global top, stack, stack_size
if top + 1 >= stack_size:
stack += [None]*stack_size
stack_size *= 2
top += 1
stack[top] = element

def print_stack():
global top, stack, stack_size
for i in range(top + 1):
print(stack[i], '', end='')
print(" (size: " + str(stack_size) + ")")

print_stack()
for i in range(10):
push(i)
print_stack()
for i in range(8):
pop()
print_stack()
```

That is confusing code, right?

First of all, we use global variables. That makes the function calls hard to understand, as they have side effects.

This is made more confusing than necessary. It does use Python lists like an Array. That is not needed, but it is just to exemplify how difficult it is to make intuitive code if you model the world like a computer works.

## Step 2: Using object oriented programming to solve the above (first step – the less bad, but still not good solution)

First time you are asked to create stack using an object oriented approach, you will probably do it in a non intuitive way.

Say, you think of a Stack like a object. The stack is the full object.

What does a stack consists of?

Well items which are piled on top of each other, and you can take the top off.

How could that be modeled?

Often the straight forward way from a classical thinking way into the a class.

```class Stack:
def __init__(self):
self.stack_size = 8
self.stack = [None]*self.stack_size
self.top = -1 # empty stack

def pop(self):
if self.top == -1:
return None
else:
self.top -= 1
return self.stack[self.top + 1]

def push(self, element):
if self.top + 1 >= self.stack_size:
self.stack += [None]*self.stack_size
self.stack_size *= 2
self.top += 1
self.stack[self.top] = element

def print_stack(self):
for i in range(self.top + 1):
print(self.stack[i], '', end='')
print(" (size: " + str(self.stack_size) + ")")

s = Stack()
s.print_stack()
for i in range(10):
s.push(i)
s.print_stack()
for i in range(8):
s.pop()
s.print_stack()
```

If you inspect the code, it is actually the same code. Which in some ways has improved it.

1. We do not have global variables anymore. They are tied to the Stack class.
2. The function calls push and pop are also tied to the Stack class.
3. Also, when we use the Stack, it is clear from the context, as it is tied to the variable s, in this case.

So what is wrong?

Well, it is still not simple to understand what happens in the code. It takes time to understand, even with this simple code.

The functions use variables like top and assigns it to -1 if the stack is empty. It requires you to investigate pop and the constructor to understand that.

The key is to keep it simple.

So how to do that?

## Step 3: A simple way to model it

Let’s take a look at the drawing again.

A stack actually consists of object on it. Hence, the stack is the abstraction that keeps objects in a specific order.

That said, we need to model that closer, as it will be easier to understand for the reader of the code.

The objects on the stack we will call Nodes.

What characterizes a Node? It lies either on the bottom or on top of another Node.

What characterizes a Stack? It knows the top of the stack and can push and pop Nodes.

How can that be turned into code?

```class Node:
def __init__(self, element=None, next_node=None):
self.element = element
self.next_node = next_node

class Stack:
def __init__(self):
self.top = None

def push(self, element):
self.top = Node(element, self.top)

def pop(self):
element = self.top.element
self.top = self.top.next_node
return element

s = Stack()
for i in range(20):
s.push(i)
for i in range(10):
print(s.pop(), '', end='')
print()
```

How is that code? Easier to understand?

Of course, normally a Stack would as a minimum have a helper function is_empty() to return if stack is empty. That can be added easily. You see how?

```class Node:
def __init__(self, element=None, next_node=None):
self.element = element
self.next_node = next_node

class Stack:
def __init__(self):
self.top = None

def push(self, element):
self.top = Node(element, self.top)

def pop(self):
element = self.top.element
self.top = self.top.next_node
return element

def is_empty(self):
return self.top == None

s = Stack()
for i in range(20):
s.push(i)
while not s.is_empty():
print(s.pop(), '', end='')
print()
```

Do you get the sense of it now?

Model the code as closely to the reality we humans understand. It makes the code easy to read and understand. Hence, easy to maintain.

## What will we cover in this tutorial?

We will cover what a Queue is. A Queue is a data structure used by computers. It resembles a queue as we know it.

The key things a Queue should have are efficient operations for insertion (enqueue) and removal (dequeue) of the queue. In this tutorial we will understand what a is, how to represent it, and how to implement the efficient operations.

## Step 1: Understand a Queue

A Queue is like a queue in real life.

A Queue is used in computer science in many scenarios. One scenario is when a resource is shared among multiple consumers, then a Queue is set in front.

This resembles the real world, where we use queues in the grocery store, pharmacy, you name it. In all stores, where we have more consumers than registers (the resource) to serve.

A Queue serves the principle, First-in-first-out or FIFO.

A simple diagram shows the operations of a Queue.

The above queue shows the direction of the Queue and the order they have been added symbolized with the numbers 1 to 8, where 8 is about to be added.

The operations on the Queue are as follows.

• enqueue Adds an element to the back of the Queue.
• dequeue Removes the element of the front of the Queue.

Normally, a Queue would also have a function is_empty, which checks whether the Queue is empty.

## Step 2: How to represent a Queue item with an element

How do you represent the above items of the Queue?

Well, we need to be able to keep an order of the Queue. Let’s try to draw it and see what we can figure out.

Surprised? Well, the Queue goest from left to right, while the arrows between the items go from right to left.

Actually, the items of the Queue can be represented by a simple Node class.

```class Node:
def __init__(self, element=None, next_node=None):
self.element = element
self.next_node = next_node
```

This simple Node class has an element and the pointer to next_node. Hence, the next_node are the arrows in the diagram above. And the element are representing the numbers in the above diagram. Obviously, the element can contain anything.

## Step 3: Create a Queue class to represent the enqueue and dequeue operations

Let’s start in the simple.

The above suggest that if we have head and tail pointer, we can have what we need to implement a Queue data structure.

The enqueue function has the special case where the Queue is empty, otherwise it will do as follows.

• enqueue Create a new Node with the element. Point tails next_node at created Node. Then update tail to point at created Node.

Here we can implement it as follows.

```class Queue:
def __init__(self):
self.tail = None

def enqueue(self, element):
else:
node = Node(element)
self.tail.next_node = node
self.tail = node
```

The dequeue is a bit more involved.

• dequeue Get the element from the Node that head points at. If head Node and tail Node is the same (that is if it is the last Node in the Queue), then point tail and head at None. Otherwise, set the head to point at the the next_node head points at.
```class Queue:
def __init__(self):
self.tail = None

def enqueue(self, element):
else:
node = Node(element)
self.tail.next_node = node
self.tail = node

def dequeue(self):
else:
return element
```

Notice that the dequeue does fail if the Queue is empty. This is dealt with by creating a is_empty function, which returns whether the Queue is empty.

```class Queue:
def __init__(self):
self.tail = None

def enqueue(self, element):
else:
node = Node(element)
self.tail.next_node = node
self.tail = node

def dequeue(self):
else:
return element

def is_empty(self):
```

That is it.

## The full code including a string representation to enable it to be printed

See the full code below. It also contains the __str__(…) function, witch enables it to be printed. Also, how to use it.

```class Queue:
def __init__(self):
self.tail = None

def enqueue(self, element):
else:
node = Node(element)
self.tail.next_node = node
self.tail = node

def dequeue(self):
else:
return element

def is_empty(self):

def __str__(self):
return None
result = "["
while node is not None:
result += str(node.element) + " "
node = node.next_node
return result[:-1] + "]"

q = Queue()
for i in range(10):
q.enqueue(i)
while not q.is_empty():
print(q.dequeue(), '', end='')
```

The above code will result in the following output.

```[0 1 2 3 4 5 6 7 8 9]
0 1 2 3 4 5 6 7 8 9
```

## What will we cover in this tutorial?

We will learn what a Stack is and how to implement it in Python.

But why bother, when you can use a Python list as a Stack? Good question. If you understand how a Stack works, you will know when to use it to efficiently solve problems. The best way to learn something, is by trying to implement it.

Why use a Stack? Check out this tutorial on how to Solve a Maze or Find the Nearest Smallest Element Problem.

## Step 1: Understand Stack

A Stack in computer science is like a stack of plates. You can add one on top at the time. Or you can remove the top plate one by one.

A stack can have any number of items on it. In the above illustration you see the following.

1. (left) A stack with 4 elements (1, 2, 3, 4).
2. (mid) A stack of 4 elements where a fifth element is added by a push operation.
3. (right) A stack that had 5 elements, but where the last item (5) is removed by a pop operation.

That is a Stack has two vital operations push and pop. Also, these operations should be done in constant time, O(1). That is they should be done with a performance, which is independent of the size of the stack. Say, if the Stack has 2 elements, then a push (or a pop) takes the same time to execute if the Stack has 2,000,000 elements.

Notice the following with a Stack. The last item you add on the Stack is the first one to get removed. That is Last-in-first-out or LIFO.

## Step 2: How to represent a Stack item (Node) in Python code

As always, keep things simple.

How can we represent the above efficiently, such that the operations are not becoming expensive.

We only need to keep track of two things.

1. The item added before. Starting with the first item to be added to point at None.
2. A pointer to the top of the Stack (not in diagram above).

If we have that we can create a Stack. We can make the operations as follows.

• push – Find the top item of the stack using pointer from 2. Then add the new item and let it point at top item. Let stack pointer point at new item.
• pop – Remove top item. Let stack pointer point at item pointed by top item.

Hence, we need a way to represent a item. Such an item is called a Node. This Node should have two things.

1. The element it represents.
2. A pointer to the next node.

This can be turned into Python code like this.

```class Node:
def __init__(self, element=None, next_node=None):
self.element = element
self.next_node = next_node
```

This class can take the element and next_node pointer as optional arguments as constructed.

## Step 3: Creating the stack class to represent the operations push and pop

Let’s start by creating a new class Stack.

```class Stack:
def __init__(self):
self.stack = None
```

This creates an empty Stack, where we have the pointer self.stack to point at None.

To add an element can be done by adding a new Node and let it point at the current self.stack.

```class Stack:
def __init__(self):
self.stack = None

def push(self, element):
node = Node(element, self.stack)
self.stack = node
```

This works for the initial element push’ed on the Stack and for any element push’ed afterwards.

Now we need to pop the top element of the Stack.

```class Stack:
def __init__(self):
self.stack = None

def push(self, element):
node = Node(element, self.stack)
self.stack = node

def pop(self):
element = self.stack.element
self.stack = self.stack.next_node
return element
```

We need to get the element. Update the self.stack pointer to point to the element below.

Notice, we do not handle the case where the stack is empty, this will cause the pop function to fail. This is handled by adding a a is_empty function, to check whether the Stack is empty.

```class Stack:
def __init__(self):
self.stack = None

def push(self, element):
node = Node(element, self.stack)
self.stack = node

def pop(self):
element = self.stack.element
self.stack = self.stack.next_node
return element

def is_empty(self):
return self.stack == None
```

## The full code with a print function

Here the full code is provided with a way to represent the Stack as a string. That way you can print it out.

```class Node:
def __init__(self, element=None, next_node=None):
self.element = element
self.next_node = next_node

class Stack:
def __init__(self):
self.stack = None

def push(self, element):
node = Node(element, self.stack)
self.stack = node

def pop(self):
element = self.stack.element
self.stack = self.stack.next_node
return element

def is_empty(self):
return self.stack == None

def __str__(self):
if self.stack is None:
return None
node = self.stack
result = "["
while node is not None:
result += str(node.element) + " "
node = node.next_node
return result[:-1] + "]"

stack = Stack()
for i in range(10):
stack.push(i)
print(stack)
for _ in range(8):
stack.pop()
print(stack)
```

Where the example code in the end will give the following output.

```[9 8 7 6 5 4 3 2 1 0]
[1 0]
```

## What will we cover in this tutorial?

We will create a heap, or more specifically, a max-heap. A max-heap is a tree structure where the node value of every parent is greater or equal to the children.

In this tutorial we will implement a max-heap with a binary tree and use a randomized approach to keep it balanced.

You might be wondering why to make it randomized. Simply, said, to keep it simple and keep operations on average O(log(n)).

## Step 1: Recall what a max-heap is

A max-heap is a tree structure where the node value of every parent is greater or equal to the children.

A heap will have two primary functions.

1. Insert an element and still keep the max-heap structure.
2. Get and remove maximum element (the element at the root) and still keep the max-heap structure.

The goal is to be able to do these operations in O(log(n)) time.

## Step 2: Understand what a randomized algorithm can do for you

Randomized algorithms help you achieve great performance on average while keeping the algorithms simple.

To get keep the operations of a heap at worst-case O(log(n)), you need to keep the binary tree structure balanced. This requires complex ways to ensure that.

Instead, just put in the leaves in the three randomly, and you will get the same result with very high probability. Hence, you will end up with an average time of O(log(n)) for the operations.

## Step 3: Insert into a max-heap

Now to the fun part. The code.

Let’s start simple and create a Node to represent the nodes in the binary tree, which will represent the max-heap.

```class Node:
def __init__(self, element):
self.element = element
self.left = None
self.right = None
```

The node needs to be able to keep the element (which should be comparable), and a left and right child.

From the above Node class you can create an arbitrary binary tree.

The max-heap insert function can be implemented by a recursive and randomized approach in the following manner.

```import random

class Heap:
def __init__(self):

def _insert(self, element, node):
# if element is larger then node.element, switch
if element > node.element:
element, node.element = node.element, element

# check if available node
if node.left is None:
node.left = Node(element)
return
if node.right is None:
node.right = Node(element)
return

# Choose a random node (here is the randomness hidden)
if random.randint(0, 1) == 0:
self._insert(element, node.left)
else:
self._insert(element, node.right)

def insert(self, element):
else:
```

The function insert(…) checks for the special case, if there are no nodes in the binary tree so far and inserts if so. Otherwise, it will forward the call to the recursive and randomized function _insert(….), which also takes the head (root) of the tree as argument.

A recursive function in this case could be at any node, but starting from the head (root) node. It will do the same all the way down.

1. Check if element of node is smaller than element to insert. If so, switch them.
2. Check if node has a free child (left or right). If so, use it to insert new node with element and return.
3. If none of the above, choose a random child (left or right) and call recursive down.

That is it. It will most likely create a well balanced binary tree.

See example here.

```               +---------------36---------------+
+-------29-------+              +-------34-------+
+---27---+      +---20---+      +---32---+      +---33---+
+- 3-+  +-13-+  +- 6-+  +- 2-+  +-24-+  +-31-+  +-25-+  +-25-+
0   1           4              16               6
```

In simple ascii representation of the binary tree representing the max-heap. That the binary tree keeps a balance like that ensures that the insertion will be O(log(n)) on average.

## Step 4: Delete the maximum element from the heap (and return it)

Deleting the maximum element will remove the root (head) of the binary tree. Then we need to take the larger child and move it up. That obviously makes an empty space in the child below. Hence, we need to do the same operation below.

This sounds recursive, doesn’t it?

```import random

class Heap:
def __init__(self):

def _insert(self, element, node):
# if element is larger than node.element, switch
if element > node.element:
element, node.element = node.element, element

# check if available node
if node.left is None:
node.left = Node(element)
return
if node.right is None:
node.right = Node(element)
return

if random.randint(0, 1) == 0:
self._insert(element, node.left)
else:
self._insert(element, node.right)

def insert(self, element):
else:

def get_max(self):

def _delete_max(self, node):
if node.left is None and node.right is None:
return None

if node.left is None:
return node.right

if node.right is None:
return node.left

if node.right.element > node.left.element:
node.element = node.right.element
node.right = self._delete_max(node.right)
return node
else:
node.element = node.left.element
node.left = self._delete_max(node.left)
return node

def delete_max(self):
return None

return max_element
```

The delete_max function takes care of the special case where there are no elements (or nodes) in the binary tree. Then it takes the largest element and calls the recursive _delete_max(…) function with the head (root) as argument.

The _delete_max(…) function does the following.

1. Checks for special case where node has no children. If so, return None.
2. Check if one child is not there, if so return the existing child.
3. Otherwise, take the child with the larger element. Take the larger element and assign it to node (remember, we have removed the element form the calling node), and call recursive down with larger child on _delete_max(…) and assign result to larger child node.

That can be a bit confusing at first. But try it out.

This operation also only has O(log(n)) performance on average. And as elements are put randomly, then removing them in order (maximum elements), will remove elements randomly and keep the binary tree balanced on average case.

## Step 5: The full code and a simple print function of the tree

The full code can be found here.

```import random

class Node:
def __init__(self, element):
self.element = element
self.left = None
self.right = None

class Heap:
def __init__(self):

def _insert(self, element, node):
# if element is larger than node.element, switch
if element > node.element:
element, node.element = node.element, element

# check if available node
if node.left is None:
node.left = Node(element)
return
if node.right is None:
node.right = Node(element)
return

if random.randint(0, 1) == 0:
self._insert(element, node.left)
else:
self._insert(element, node.right)

def insert(self, element):
else:

def get_max(self):

def _delete_max(self, node):
if node.left is None and node.right is None:
return None

if node.left is None:
return node.right

if node.right is None:
return node.left

if node.right.element > node.left.element:
node.element = node.right.element
node.right = self._delete_max(node.right)
return node
else:
node.element = node.left.element
node.left = self._delete_max(node.left)
return node

def delete_max(self):
return None

return max_element

def _get_depth(self, node):
if node is None:
return 0
left = self._get_depth(node.left)
right = self._get_depth(node.right)
if left > right:
return 1 + left
else:
return 1 + right

def get_depth(self):

def _print_heap(self, current_level, request_level, depth, node):
characters_per_level = 4*2**depth
characters_per_node = characters_per_level // (2**(current_level + 1))
if current_level == request_level:
if node is not None:
space_fill = characters_per_node // 4 - 1
if request_level == depth - 1:
print(' '*space_fill + ' ' + ' '*space_fill + f'{node.element:2d}' + ' '*space_fill + ' ' + ' '*space_fill, end='')
else:
print(' '*space_fill + '+' + '-'*space_fill + f'{node.element:2d}' + '-'*space_fill + '+' + ' '*space_fill, end='')
else:
print(' '*characters_per_node, end='')
else:
if node is not None:
self._print_heap(current_level + 1, request_level, depth, node.left)
self._print_heap(current_level + 1, request_level, depth, node.right)
else:
self._print_heap(current_level + 1, request_level, depth, None)
self._print_heap(current_level + 1, request_level, depth, None)

def print_heap(self):
for i in range(depth):
print()
```

Notice that the print function also is recursive.

## What will we cover in this tutorial?

Given an input of a maze, how can we solve it?

That is – given an input like this the following.

```#############
S #     #   #
# #  ##   # #
# #  ## ### #
#       #   #
######### # #
#         # E
#############
```

How can we find a path through the maze starting from S and ending at E.

```#############
S.#.....#...#
#.#. ##...#.#
#.#. ## ###.#
#...    #  .#
######### #.#
#         #.E
#############
```

We will create a program that can do that in Python.

## Step 1: Reading and representing the Maze

An good representation of the maze makes it easier to understand the code. Hence, the first part is to figure out how to represent the maze.

To clarify, imagine that this maze.

```v
```

Was represented by one long string, like this.

```maze = "#############S #     #   ## #  ##   # ## #  ## ### ##       #   ########## # ##         # E#############"
```

While this is possible, if you also know the dimensions (8 rows and 13 columns), it makes things difficult to navigate in. Say, you are somewhere in the maze, and you want to see what is right above you. How do you do that?

Yes, you can do it, but it is complex.

Now image you have the following representation.

```maze = [['#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#'],
['S', ' ', '#', ' ', ' ', ' ', ' ', ' ', '#', ' ', ' ', ' ', '#'],
['#', ' ', '#', ' ', ' ', '#', '#', ' ', ' ', ' ', '#', ' ', '#'],
['#', ' ', '#', ' ', ' ', '#', '#', ' ', '#', '#', '#', ' ', '#'],
['#', ' ', ' ', ' ', ' ', ' ', ' ', ' ', '#', ' ', ' ', ' ', '#'],
['#', '#', '#', '#', '#', '#', '#', '#', '#', ' ', '#', ' ', '#'],
['#', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', '#', ' ', 'E'],
['#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#']]
```

This will make it easier to navigate in the maze.

Then maze[1][0] represents row 1 (2nd row) and column 0 (1st column), which is S.

If we assume that the maze is represented in a file, then we can read that file and convert it with the following code.

```def load_maze(file_name):
f = open(file_name)
f.close()
return maze

def convert_maze(maze):
converted_maze = []
lines = maze.splitlines()
for line in lines:
converted_maze.append(list(line))
return converted_maze

maze = convert_maze(maze)
print(maze)
```

## Step 2: Creating a print function of the maze

As you probably noticed, the print statement of the maze (print(maze)) did not do a very good job.

```[['#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#'], ['S', ' ', '#', ' ', ' ', ' ', ' ', ' ', '#', ' ', ' ', ' ', '#'], ['#', ' ', '#', ' ', ' ', '#', '#', ' ', ' ', ' ', '#', ' ', '#'], ['#', ' ', '#', ' ', ' ', '#', '#', ' ', '#', '#', '#', ' ', '#'], ['#', ' ', ' ', ' ', ' ', ' ', ' ', ' ', '#', ' ', ' ', ' ', '#'], ['#', '#', '#', '#', '#', '#', '#', '#', '#', ' ', '#', ' ', '#'], ['#', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', '#', ' ', 'E'], ['#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#']]
```

In order to be able to follow what happens in the code later on, it would be nice with a better representation of the code.

```def print_maze(maze):
for row in maze:
for item in row:
print(item, end='')
print()

print_maze(maze)
```

This will print the maze in a more human readable way.

```#############
S #     #   #
# #  ##   # #
# #  ## ### #
#       #   #
######### # #
#         # E
#############
```

## Step 3: Finding the starting point of the maze

First thing first. We need to find where we enter the maze. This is where the S is located.

We could have some assumptions here, say, that the starting point is always located on the outside borders of the maze. To make it more general, we will assume that the starting point, S, can be located anywhere in the maze.

This makes the algorithm to find it easy, but of course not effective in worst case, as we need to check all locations in the maze.

```def find_start(maze):
for row in range(len(maze)):
for col in range(len(maze[0])):
if maze[row][col] == 'S':
return row, col

start = find_start(maze)
print(start)
```

Which will go through all rows and columns one by one and check if it is the starting point. When found, it will return it immediately.

Notice, that we do assume that we have a maze with at least one row, also that the starting point exists. If not, it will not return anything.

## Step 4: Find if there is a path in the maze

This is where a stack comes in handy. If you are new to what a stack is, then check out this tutorial.

For the purpose here, we are not looking for performance, we just need the concept of a stack.

To see if there is a way through the maze, you need to check all paths. As some leads to the same points, we need to keep track of where we have been. If we reach a dead end, where we have been, we need to backtrack to the last point with options, and check them out.

Wow. That was a lot of talking. How can we understand that a bit better.

Let’s make a simple maze and see it.

```###
S E
###
```

When you are at start, S, you have (in theory) 4 possible ways to go. Up, Down, Right, Left. In the above example you can only go Right. Let’s do that, and mark the position we just left.

```###
[email protected]
###
```

Now we have marked where we have been with X and where we are with @. Then we can check all possible ways. Up, Down, Right, Left. Again we can only go Right, as Left we have already been there.

Luckily, going Right is the exit E and we are done.

Now that was a simple maze. Now how does a stack come into the picture? Well, we used it secretly and in a very simple case.

So let’s try a bit more complex case.

```#####
S # E
#   #
# # #
#####
```

Now let’s also have a stack with the positions we can visit. We will use the coordinate system as the representation of the list of lists we use to represent the maze. That means that the upper left corner is (0, 0) and the lower right corner is (5, 5) in this case.

The starting point is (1 , 0).

Now, let’s have a stack in the picture and put the staring point on that stack.

```#####
S # E
#   #
# # #
#####      stack -> (1, 0)
```

When we enter we look for points on the stack. Yes, we have one point (1, 0). Then we pop it off and check all possible positions. Up, Down, Right, Left. Only one is possible, Left, which is (1, 1). Updating where we been, then it looks like this.

```#####
X # E
#   #
# # #
#####      stack -> (1, 1)
```

Notice, that the stack changed and we marked the first point with X.

We do the same. Pop of the stack and get (1, 1) and check Up, Down, Right, Left. Only down is possible, which leaves us in (2, 1). Now the picture looks like this.

```#####
XX# E
#   #
# # #
#####      stack -> (2, 1)
```

Then we do the same. We pop of the stack and get (2, 1) and check Up, Down, Right, Left. Now we can go both Down and Right, which is (3, 1) and (2, 2), respectively. Hence, we push both of them on the stack.

```#####
XX# E
#X  #
# # #               (3, 1)
#####      stack -> (2, 2)
```

Depending on the order we put thins on stack, it will look like that.

Now we pop of the top element (3, 1) and check Up, Down, Right, Left. But there are no way to go from there, it is a dead end. Then we mark that spot and do not push anything on the stack.

```#####
XX# E
#X  #
#X# #
#####      stack -> (2, 2)
```

Now we pop (2, 2) of the stack, as this is the first possibility we have to go another way in the maze. Then check Up, Down, Right, Left. We can only go Right. After marking pushing we have.

```#####
XX# E
#XX #
#X# #
#####      stack -> (3, 2)
```

Now we can both go up and down and add that to the stack.

```#####
XX# E
#XXX#
#X# #               (3, 2)
#####      stack -> (3, 4)
```

Now we pop (3, 2) of the stack. Then we check all and see we can only go Right.

```#####
XX#XE
#XXX#
#X# #               (4, 2)
#####      stack -> (3, 4)
```

Then we pop (4, 2) of the stack and see it is the exit, E. That is just what we needed.

The stack keeps track on all the possible choices we have along the way. If we reach a dead end (also, if we have visited all around us and marked it by X), we can look at the last possible choice we skipped, which is on the top of the stack.

That actually means, that we do not need to move backwards along the road we went, we can go directly to the point on the stack. We know we can reach that point, as we have already visited a neighboring point, which is connected. Also, as we mark everything along the way, we do not go in endless loops. We only visit every point at most once.

Now, if there was no way to the exit, E, this will eventually terminate when there is no points on the stack.

## Step 5: Implementing the algorithm

The above can be made into a simple algorithm to determine whether there is a way through the maze.

The pseudo code for the algorithm could be something like this.

```stack.push(start)
while stack is not empty
location = stack.pop()

if location is marked continue to next location in loop

if location is marked as exit - return True (we found the exit)

for loc as Up, Down, Left, Right:
if loc is valid and not marked add to stack

return False (if all locations are tried (stack empty) there is not way to the exit)
```

Now let’s turn that into code.

```# This is only a helper function to see if we have a valid positino.
def is_valid_position(maze, pos_r, pos_c):
if pos_r < 0 or pos_c < 0:
return False
if pos_r >= len(maze) or pos_c >= len(maze[0]):
return False
if maze[pos_r][pos_c] in ' E':
return True
return False

def solve_maze(maze, start):
# We use a Python list as a stack - then we have push operations as append, and pop as pop.
stack = []

# Add the entry point (as a tuple)
stack.append(start)

# Go through the stack as long as there are elements
while len(stack) > 0:
pos_r, pos_c = stack.pop()

if maze[pos_r][pos_c] == 'E':
print("GOAL")
return True

if maze[pos_r][pos_c] == 'X':
continue

# Mark position as visited
maze[pos_r][pos_c] = 'X'
# Check for all possible positions and add if possible
if is_valid_position(maze, pos_r - 1, pos_c):
stack.append((pos_r - 1, pos_c))
if is_valid_position(maze, pos_r + 1, pos_c):
stack.append((pos_r + 1, pos_c))
if is_valid_position(maze, pos_r, pos_c - 1):
stack.append((pos_r, pos_c - 1))
if is_valid_position(maze, pos_r, pos_c + 1):
stack.append((pos_r, pos_c + 1))

# We didn't find a path, hence we do not need to return the path
return False
```

## The full code

Here we present the full code. It prints out the state through the processing. It expects a file called maze.txt with the maze in it. See below for a possible file content.

```def load_maze(file_name):
f = open(file_name)
f.close()
return maze

def convert_maze(maze):
converted_maze = []
lines = maze.splitlines()
for line in lines:
converted_maze.append(list(line))
return converted_maze

def print_maze(maze):
for row in maze:
for item in row:
print(item, end='')
print()

def find_start(maze):
for row in range(len(maze)):
for col in range(len(maze[0])):
if maze[row][col] == 'S':
return row, col

from time import sleep

# This is only a helper function to see if we have a valid positino.
def is_valid_position(maze, pos_r, pos_c):
if pos_r < 0 or pos_c < 0:
return False
if pos_r >= len(maze) or pos_c >= len(maze[0]):
return False
if maze[pos_r][pos_c] in ' E':
return True
return False

def solve_maze(maze, start):
# We use a Python list as a stack - then we have push operations as append, and pop as pop.
stack = []

# Add the entry point (as a tuple)
stack.append(start)

# Go through the stack as long as there are elements
while len(stack) > 0:
pos_r, pos_c = stack.pop()

print("Current position", pos_r, pos_c)

if maze[pos_r][pos_c] == 'E':
print("GOAL")
return True

if maze[pos_r][pos_c] == 'X':
continue

# Mark position as visited
maze[pos_r][pos_c] = 'X'
# Check for all possible positions and add if possible
if is_valid_position(maze, pos_r - 1, pos_c):
stack.append((pos_r - 1, pos_c))
if is_valid_position(maze, pos_r + 1, pos_c):
stack.append((pos_r + 1, pos_c))
if is_valid_position(maze, pos_r, pos_c - 1):
stack.append((pos_r, pos_c - 1))
if is_valid_position(maze, pos_r, pos_c + 1):
stack.append((pos_r, pos_c + 1))

print('Stack:' , stack)
print_maze(maze)

# We didn't find a path, hence we do not need to return the path
return False

maze = convert_maze(maze)
print_maze(maze)
start = find_start(maze)
print(start)
print(solve_maze(maze, start))
```

Then for some possible content of file maze.txt needed by the program above. To make the above code work, save the content below in a file called maze.txt in the same folder from where you run the code.

```#############
S #     #   #
# #  ##   # #
# #  ## ### #
#       #   #
######### # #
#         # E
#############
```

## Further work

The above code only answers if there is a path from S to E in the maze. It would also be interesting to print a route out. Further improvements could be finding the shortest path.

## What will we cover in this tutorial?

We will continue the work of this tutorial (Create a Moving Photo Slideshow with Weighted Transitions in OpenCV). The challenge is that construction is that we pre-load all the photos we need. The reason for that, is that loading the photos in each iteration would affect the performance of the slideshows.

The solution we present in this tutorial is to load photos in a background thread. This is not straightforward as we need to ensure the communication between the main thread and the background photo loading thread is done correctly.

The result will be similar.

## Already done so far and the challenge

In the previous tutorial we made great progress, creating a nice slideshow. The challenge was the long pre-loading time of the photos.

If we did not pre-load the photos, then we would need to load the photos in each iteration. Say, in the beginning of the loop, we would need to load the next photo. This would require disk access, which is quite slow. As the frame is updated quite often, this loading time will not let the new position of the photo to be updated for a fraction of a second (or more, depending the photo size and the speed of the processor). This will make the movement of the photo lacking and not run smoothly.

Said differently, in one thread, the processor can only make one thing at the time. When you tell the processor to load a photo, it will stop all other work in this program, and do that first, before updating the frame. As this can be a big task, it will take long time. As the program needs to update the frame continuously, to make the photo move, then this will be visible no matter when you tell the processor to load the image.

So how can we deal with this?

Using another thread to load the image. Having multiple threads will make it possible to do more than one thing at the time. If you have two threads, you can do two things at the same time.

A Python program is by default run in one thread. Hence, it can only do one thing at the time. If you need to do more than one thing at the time, you need to use threading.

Now this sound simple, but it introduces new problems.

When working with threading a lock is a good tool to know. Basically, a lock is similar to a lock. You can enter and lock the door after you, such that no one else can enter. When you are done, you can unlock the door and leave. Then someone else can enter.

This is the same principle with a lock with threading. You can take a lock, and ensure you only enter the code after the lock, if no-one else (another thread) is using the lock. Then when you are done, you release the lock.

We need a stack of photos that can load new photos when needed.

```class ImageStack:
def __init__(self, filenames, size=3):
if size > len(filenames):
raise Exception("Not enough file names")
self.size = size
self.filenames = filenames
self.stack = []
while len(self.stack) < self.size:
filename = self.filenames[random.randrange(0, len(self.filenames))]
if any(item[0] == filename for item in self.stack):
continue
self.stack.append((filename, Image(filename)))
# Lock used for accessing the stack

def get_image(self):
self.stack_lock.acquire()
filename, img = self.stack.pop()
print(f"Get image {filename} (stack size:{len(self.stack)})")
self.stack_lock.release()
return img

filename = self.filenames[random.randrange(0, len(self.filenames))]
self.stack_lock.acquire()
while any(item[0] == filename for item in self.stack):
filename = self.filenames[random.randrange(0, len(self.filenames))]
self.stack_lock.release()
img = Image(filename)
self.stack_lock.acquire()
self.stack.append((filename, img))
print(f"Add image {filename} (stack size: {len(self.stack)})")
self.stack_lock.release()
```

The above is an image stack which has two locks. One for accessing the stack and one for adding images.

The lock for stack is to ensure that only one thread is accessing the stack. Hence if we have the code.

```stack = ImageStack(filenames)
stack.get_image()
```

The code above will create an ImageStack (notice that filenames is not defined here). Then on the second line it will start a new process to add a new image. After that it will try to get an image. But here the lock comes into the picture. If the thread with add_image has acquired the stack lock, then get_image call cannot start (it will be waiting in the first line to acquire stack lock).

There are more possible situations where the lock hits in. If the 3rd line with stack.get_image acquires the stack lock before that the call to add_image reaches the lock, then add_image needs to wait until the lock is released by the stack.get_image call.

Threading is a lot of fun but you need to understand how locks work and how to avoid deadlocks.

## Full code

Below you will find the full code using a threading approach to load photos in the background.

```import cv2
import glob
import os
import random

class Image:
def __init__(self, filename, time=500, size=500):
self.filename = filename
self.size = size
self.time = time
self.shifted = 0.0
height, width, _ = img.shape
if width < height:
self.height = int(height*size/width)
self.width = size
self.img = cv2.resize(img, (self.width, self.height))
self.shift = self.height - size
self.shift_height = True
else:
self.width = int(width*size/height)
self.height = size
self.shift = self.width - size
self.img = cv2.resize(img, (self.width, self.height))
self.shift_height = False
self.delta_shift = self.shift/self.time
self.reset()

def reset(self):
if random.randint(0, 1) == 0:
self.shifted = 0.0
self.delta_shift = abs(self.delta_shift)
else:
self.shifted = self.shift
self.delta_shift = -abs(self.delta_shift)

def get_frame(self):
if self.shift_height:
roi = self.img[int(self.shifted):int(self.shifted) + self.size, :, :]
else:
roi = self.img[:, int(self.shifted):int(self.shifted) + self.size, :]
self.shifted += self.delta_shift
if self.shifted > self.shift:
self.shifted = self.shift
if self.shifted < 0:
self.shifted = 0
return roi

class ImageStack:
def __init__(self, filenames, size=3):
if size > len(filenames):
raise Exception("Not enough file names")
self.size = size
self.filenames = filenames
self.stack = []
while len(self.stack) < self.size:
filename = self.filenames[random.randrange(0, len(self.filenames))]
if any(item[0] == filename for item in self.stack):
continue
self.stack.append((filename, Image(filename)))
# Lock used for accessing the stack

def get_image(self):
self.stack_lock.acquire()
filename, img = self.stack.pop()
print(f"Get image {filename} (stack size:{len(self.stack)})")
self.stack_lock.release()
return img

filename = self.filenames[random.randrange(0, len(self.filenames))]
self.stack_lock.acquire()
while any(item[0] == filename for item in self.stack):
filename = self.filenames[random.randrange(0, len(self.filenames))]
self.stack_lock.release()
img = Image(filename)
self.stack_lock.acquire()
self.stack.append((filename, img))
print(f"Add image {filename} (stack size: {len(self.stack)})")
self.stack_lock.release()

def process():
path = "pics"
filenames = glob.glob(os.path.join(path, "*"))

buffer = ImageStack(filenames)

prev_image = buffer.get_image()
current_image = buffer.get_image()

while True:
for i in range(100):
alpha = i/100
beta = 1.0 - alpha
dst = cv2.addWeighted(current_image.get_frame(), alpha, prev_image.get_frame(), beta, 0.0)

cv2.imshow("Slide", dst)
if cv2.waitKey(1) == ord('q'):
return

for _ in range(300):
cv2.imshow("Slide", current_image.get_frame())
if cv2.waitKey(1) == ord('q'):
return

prev_image = current_image
current_image = buffer.get_image()