How-To Bracket all Possible Evaluations of a Binary Operator for an Arbitrary Input Length

What will we cover in this tutorial?

Consider addition of the following expression. 5 + 7 + 3. As addition is associative, the order of evaluation does not matter. Hence, we have that (5 + 7) + 3 = 5 + (7 + 3).

For an arbitrary binary operator op(x_1, x_2) -> y, you cannot assume that op(x_1, op(x_2, x_3)) = op(op(x_1, x_2), x_3). Hence, the order of evaluation of a binary operator matters.

The brackets give the order of how the expression is evaluated. Hence, if an operator takes three different inputs, a, b, or c, then we can write a(ab), to symbol it evaluated ab first, then the result of ab with a.

This tutorial will show you how to get all possible evaluations of an arbitrary length input. That is, given an input, e.g., abab, how to find a list of all possible evaluations of the input, [(a(b(ab)), (a((ba)b), (ab)(ab), ((a(ba))b), (((ab)a)b)].

Consider that for a moment. How do you program that in Python?

Step 1: Define the problem

For simplicity we assume we have a binary operator op: [a, b, c] x [a, b, c] -> [a, b, c]. The operator can take arguments op(a, b) and evaluate it and give, say, c.

To make that notation more efficient, we will write op(ab) = c. If we make an evaluation table of the operator, say, we will have the following.

opabc
accb
bacb
cbaa
Evaluation of the operator op.

Hence, we have that op(aa) = c, op(ab) = c, …, op(cc) = a.

Now notice, that this operator is not associative or commutative.

It is not commutative, as op(ab) ≠ op(ba).

And it is not associative, as op(a op(ac)) = op(ab) = c ≠ op(op(aa) c) = op(cc) = a.

Now we understand why a binary operator needs an order of evaluation. Because, the final output will depend on it.

What we want now, is given an input, e.g., aac, how many ways can you set brackets to get a different evaluation of a binary operator, [(a(ac), ((aa)c)].

Step 2: Breaking the problem down

Now we understand why the problem is important. But how do we solve it?

Breaking it down and think like a programmer.

The base case is a string of length 2, e.g., aa, which only has one possible way (aa).

Then we have the case of length 3, e.g. aac, which can be broken down into two ways ((aa)c), (a(ac). Another way to think of it, is you can break a string of length 3, into a string of length 2 + 1 or 1 + 2.

Then the case of length 4, say, aaab, that can be broken down into (((aa)a)b), ((a(aa))b), ((aa)(ab)), (a((aa)b)), (a(a(ab))). Or you could think of it like, 3 + 1, 2 + 2, 1 + 3. Wait, what does that mean?

A drawing might come in handy now.

A visualization of the way to break down the bracket problem

See, a string of length 4 can be broken down into an instance of length 1 (as the first argument to the operator) and length 3, an instance of length 2 and 2 (each as input to the operator), or of length 3 and 1 (each as input to the operator).

Hence, you break the problem recursively down.

For a string of length 5 you have the following diagram.

A string of length 5

Amazing. Now we just need to turn that into code.

Step 3: How to create a list of all possible brackets for a binary operator

Consider the diagram from last step. Then think about recursion. How do they all add up together?

Recursion, you need a base case. It could be for a string of length 2, but let’s do it for length 1 instead, as you see you want to call for length 1.

def get_all_variations(x):
    if len(x) == 1:
        return [x]

    solutions = []
    for i in range(1, len(x)):
        x1 = x[:i]
        x2 = x[i:]
        res1 = get_all_variations(x1)
        res2 = get_all_variations(x2)
        for r1 in res1:
            for r2 in res2:
                solutions.append('(' + r1 + r2 + ')')
    return solutions


res = get_all_variations('aaabc')
for r in res:
    print(r)

This shows how to create it simple with an example. The function has the base case, where it just returns the element in a string. In the general case, it breaks the string down into two non-zero length string. Then it calls recursively.

For each of the results, it appends all possible solutions together in all possible ways.

The above code gives the following output.

(a(a(a(bc))))
(a(a((ab)c)))
(a((aa)(bc)))
(a((a(ab))c))
(a(((aa)b)c))
((aa)(a(bc)))
((aa)((ab)c))
((a(aa))(bc))
(((aa)a)(bc))
((a(a(ab)))c)
((a((aa)b))c)
(((aa)(ab))c)
(((a(aa))b)c)
((((aa)a)b)c)

Conclusion

This is an amazing example of how to solve a computer science problem. The method is a general way to break down into a recursive function. Learning the skills in this tutorial is crucial to become a good problem solver in computer science.

Check if Palindrome with a Queue and a Stack in Python

What will we cover in this tutorial?

How can you check if a string is a palindrome. Obviously this can be done in various creative ways. In this tutorial we will use a Queue and a Stack to solve it.

Step 1: What is a palindrome?

A palindrome is a sequence of characters which reads the same backward as forward.

Common examples are:

  • racecar
  • madam

Where you notice that RACECAR has the same sequence of characters, whether you read it from left-to-right, or from right-to-left.

Also, palindromes are also considered with dates. Examples could be:

  • 11/11/11 11:11
  • 02/02/2020

If sentences are considered as palindrome, often the spaces, punctuation, and upper/lowercase variations are ignored. Examples could be:

  • “Madam I’m Adam”
  • “Sit on a potato pan, Otis”
  • “Able was I, ere I saw Elba.”

Step 2: A simple implementation to test palindrome

Let’s start with understanding how we can check if sequence of characters is a palindrome by using a Stack and a Queue.

If you are new to a Stack, then we can propose you read this tutorial or this.

Also, if you are not familiar with a Queue, then we propose you read this tutorial or this.

A Stack and Queue represented – elements are taken pop/dequeued from right side

When we insert into a Stack and Queue, they will be removed in opposite orders.

Wow. That is a great idea. Why not add (push and enqueue) all characters on a Stack and Queue. Say, we do that for madam.

Then they the order of removal (pop and dequeue) will give the same elements, as it is a palindrome. If it was not a palindrome, say “12345“, then the elements removed from simultaneously from the Stack and Queue would not be identical.

This leads to the following piece of code, where we have included implementations of a Queue and Stack. See this tutorial for Stack and this tutorial for a Queue, if you need explanation of the 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.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] + "]"


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

    def enqueue(self, element):
        if self.head is None:
            self.head = self.tail = Node(element)
        else:
            node = Node(element)
            self.tail.next_node = node
            self.tail = node

    def dequeue(self):
        element = self.head.element
        if self.tail == self.head:
            self.tail = self.head = None
        else:
            self.head = self.head.next_node
        return element

    def is_empty(self):
        return self.head is None

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


def is_palindrome(s):
    stack = Stack()
    queue = Queue()
    for c in s:
        stack.push(c)
        queue.enqueue(c)

    print(stack)
    print(queue)

    while not stack.is_empty():
        if stack.pop() != queue.dequeue():
            return False

    return True


print(is_palindrome("123454321"))
print(is_palindrome("racecar"))
print(is_palindrome("112"))

This would result in the following output.

[1 2 3 4 5 4 3 2 1]
[1 2 3 4 5 4 3 2 1]
True
[r a c e c a r]
[r a c e c a r]
True
[2 1 1]
[1 1 2]
False

Step 3: Make it work on for general strings

The above code does not work if we encounter a string like, “Sit on a potato pan, Otis.

One way to deal with this is to have a function in front of the is_palindrome from previous step.

This function can convert the format of a sequence of characters to the format that is_palindrome will require. This is a nice way to break down functionality in your code and not overcomplicate functions.

Let’s try that. We will rename is_palindrome to _is_palindrome, to indicate that it is not to be used.

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] + "]"


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

    def enqueue(self, element):
        if self.head is None:
            self.head = self.tail = Node(element)
        else:
            node = Node(element)
            self.tail.next_node = node
            self.tail = node

    def dequeue(self):
        element = self.head.element
        if self.tail == self.head:
            self.tail = self.head = None
        else:
            self.head = self.head.next_node
        return element

    def is_empty(self):
        return self.head is None

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


def _is_palindrome(s):
    stack = Stack()
    queue = Queue()
    for c in s:
        stack.push(c)
        queue.enqueue(c)

    print(stack)
    print(queue)

    while not stack.is_empty():
        if stack.pop() != queue.dequeue():
            return False
    return True


def is_palindrome(s):
    s = s.lower()
    r = ""
    for c in s:
        if c in "abcdefghijklmnopqrstuvwxzy1234567890":
            r += c
    return _is_palindrome(r)


print(is_palindrome("123454321"))
print(is_palindrome("racecar"))
print(is_palindrome("112"))
print(is_palindrome("Madam I'm Adam"))
print(is_palindrome("Sit on a potato pan, Otis"))
print(is_palindrome("Able was I, ere I saw Elba."))
print(is_palindrome("Able was I, where I saw Elba."))

Which will result in the following output.

[1 2 3 4 5 4 3 2 1]
[1 2 3 4 5 4 3 2 1]
True
[r a c e c a r]
[r a c e c a r]
True
[2 1 1]
[1 1 2]
False
[m a d a m i m a d a m]
[m a d a m i m a d a m]
True
[s i t o n a p o t a t o p a n o t i s]
[s i t o n a p o t a t o p a n o t i s]
True
[a b l e w a s i e r e i s a w e l b a]
[a b l e w a s i e r e i s a w e l b a]
True
[a b l e w a s i e r e h w i s a w e l b a]
[a b l e w a s i w h e r e i s a w e l b a]
False

3 Steps to Understand and Implement a Queue in Python

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.

A queue with the two operations enqueue and dequeue

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.

The structure we need to keep.

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.

Given the Nodes, we need a class Queue with a head and tail to implement the operations enqueue and dequeue

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.head = None
        self.tail = None

    def enqueue(self, element):
        if self.head is None:
            self.head = self.tail = Node(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.head = None
        self.tail = None

    def enqueue(self, element):
        if self.head is None:
            self.head = self.tail = Node(element)
        else:
            node = Node(element)
            self.tail.next_node = node
            self.tail = node

    def dequeue(self):
        element = self.head.element
        if self.tail == self.head:
            self.tail = self.head = None
        else:
            self.head = self.head.next_node
        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.head = None
        self.tail = None

    def enqueue(self, element):
        if self.head is None:
            self.head = self.tail = Node(element)
        else:
            node = Node(element)
            self.tail.next_node = node
            self.tail = node

    def dequeue(self):
        element = self.head.element
        if self.tail == self.head:
            self.tail = self.head = None
        else:
            self.head = self.head.next_node
        return element

    def is_empty(self):
        return self.head is None

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.head = None
        self.tail = None

    def enqueue(self, element):
        if self.head is None:
            self.head = self.tail = Node(element)
        else:
            node = Node(element)
            self.tail.next_node = node
            self.tail = node

    def dequeue(self):
        element = self.head.element
        if self.tail == self.head:
            self.tail = self.head = None
        else:
            self.head = self.head.next_node
        return element

    def is_empty(self):
        return self.head is None

    def __str__(self):
        if self.head is None:
            return None
        node = self.head
        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

3 Steps to Understand and Implement a Stack in Python

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.

Stack with 4 items on it, then a new item (5) is added by push operation, then the last item is removed (5) by pop.

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]

Implement a Queue using a Circular Linked List with Only One Pointer

What will we cover?

Think about the following challenge. Given a circular linked. Create a queue with constant time operations for enqueue and dequeue. Also, you can only have one pointer to the Circular Linked List.

Example of a circular linked list and a queue with only one pointer.

Consider the above diagram. How will you insert a new element? Okay, that seems easy. But how do you remove the oldest element from it? With constant time!

Yes, that is not that trivial.

Step 1: Create the node class used to represent the circular linked list

There are of course many ways to go about how to create a linked list, and more specifically a circular linked list.

Some implement the classes together, that is both the node and the linked list together. I like to split them from each other. That way, you keep things simple.

Hence, to represent the circular linked list, I suggest the following simple class for a node. Then have the logic of the circular linked list in a different class.

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

Notice, that the above Node could also be used in a linked list alone. It is a simple building block, which can be used as you please.

Step 2: Create the Queue using a circular linked list

You could create a class for a circular linked list, but we will use it closely from the queue.

The art is to create a queue with only one pointer to the circular linked list structure. The circular linked list can be represented with the Node class above.

The first operation we need is to enqueue an element in the queue. That is to insert an element in the queue.

The special case of inserting the first element, would result in a circular linked list with only one Node, which points at itself.

It is first when we insert the second element it becomes tricky. Which Node should the Queue pointer point at?

This is interesting. We need to be able to insert the element in constant time. Hence, if the queue has more element, it should not need to go all the way around the circular linked list. That makes it necessary, for us to be able to find the last element added with constant number of operations.

Also, the element in the circular linked list point in the direction the were inserted.

This results to that we need to point at the last inserted element.

Assuming in the above that the elements are inserted in the order 1, 2, 3, and 4.

Then we can insert the the elements with the following code.

class Queue:
    def __init__(self):
        self.pointer = None

    def enqueue(self, element):
        if self.pointer is None:
            node = Node(element)
            self.pointer = node
            self.pointer.next_node = node
        else:
            node = Node(element, self.pointer.next_node)
            self.pointer.next_node = node
            self.pointer = node

The code of enqueue shows first the base case, where the circular linked list is empty. Then the case where minimum one Node already exists.

Let’s follow the code of above. Before we call enqueue let’s assume it looks as follows.

First thing is to create a new Node (with the new element, below we use 5) and point it at the queues pointer next_node.

Point the queue pointers next_node at the new Node we created.

Then we update the queue pointer to point at the new Node.

That is it. We still have a circular linked list and only one pointer from the Queue. Notice, that this all happens in constant number of operations. That is, it is independent of how many Nodes are in the circular linked list. If we have 6,000 Nodes, we still only use the 3 operations described above. Hence, enqueue has a O(1) worst case run time.

Next step will see if we can dequeue correctly from the structure, while keeping it intact.

Step 3: How to dequeue from the circular linked list

This seems tricky at first.

But look at the following diagram, where we have 4 elements. They have been inserted by the enqueue function given in Step 2. The first element was 1, then 2, then 3, and finally element 4.

Hence, when we dequeue, we want to return and remove element 1. And the circular linked list should look like this afterwards.

Also, the dequeue operation should be done in constant number of operations.

Obviously, there is a special case, when we only have one element in the queue. Then we remove it and make the queue pointer point at None.

class Queue:
    # Continued...

    def dequeue(self):
        if self.pointer is None:
            return None
        if self.pointer.next_node == self.pointer:
            element = self.pointer.element
            self.pointer = None
            return element

        element = self.pointer.next_node.element
        self.pointer.next_node = self.pointer.next_node.next_node
        return element

Otherwise, we get the element from the queue pointers next_node.

Then we update the queue pointers node to point at next_node.next_node. Notice, that this will keep the structure intact. Also, we keep the dequeue function at a constant number of operations, hence, O(1).

The full code with a print queue function

Here is the full code including a representation to print the queue.

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


class Queue:
    def __init__(self):
        self.pointer = None

    def enqueue(self, element):
        if self.pointer is None:
            node = Node(element)
            self.pointer = node
            self.pointer.next_node = node
        else:
            node = Node(element, self.pointer.next_node)
            self.pointer.next_node = node
            self.pointer = node

    def dequeue(self):
        if self.pointer is None:
            return None
        if self.pointer.next_node == self.pointer:
            element = self.pointer.element
            self.pointer = None
            return element

        element = self.pointer.next_node.element
        self.pointer.next_node = self.pointer.next_node.next_node
        return element

    def __str__(self):
        if self.pointer is None:
            return "empty"
        first = self.pointer
        node = first.next_node
        result = "["
        while node != first:
            result += str(node.element) + '->'
            node = node.next_node
        return result + str(node.element) + '->...]'



queue = Queue()
for i in range(20):
    queue.enqueue(i)
    print(queue)

for _ in range(21):
    queue.dequeue()
    print(queue)

for i in range(5):
    queue.enqueue(i)
    print(queue)

The beginning of the output will be as follows.

[0->...]
[0->1->...]
[0->1->2->...]
[0->1->2->3->...]
[0->1->2->3->4->...]
[0->1->2->3->4->5->...]

Create a Max-Heap with a Randomized Algorithm in Python

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.

Example of a max-heap

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):
        self.head = None

    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):
        if self.head is None:
            self.head = Node(element)
        else:
            self._insert(element, self.head)

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):
        self.head = None

    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):
        if self.head is None:
            self.head = Node(element)
        else:
            self._insert(element, self.head)

    def get_max(self):
        return self.head.element

    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):
        if self.head is None:
            return None

        max_element = self.head.element
        self.head = self._delete_max(self.head)
        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):
        self.head = None

    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):
        if self.head is None:
            self.head = Node(element)
        else:
            self._insert(element, self.head)

    def get_max(self):
        return self.head.element

    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):
        if self.head is None:
            return None

        max_element = self.head.element
        self.head = self._delete_max(self.head)
        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):
        return self._get_depth(self.head)

    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):
        depth = self._get_depth(self.head)
        for i in range(depth):
            self._print_heap(0, i, depth, self.head)
            print()

Notice that the print function also is recursive.

Solve a Maze in Python with a Stack

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)
    maze = f.read()
    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 = load_maze("maze.txt")
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.

###
X@E
###

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':
            # Already visited
            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)
    maze = f.read()
    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':
            # Already visited
            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))


        # To follow the maze
        print('Stack:' , stack)
        print_maze(maze)


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


maze = load_maze("maze.txt")
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.

Slideshow with Loading of Photos in a Background Thread in Python

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.

Introducing threading

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
        self.stack_lock = threading.Lock()
        self.add_image_lock = threading.Lock()

    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

    def add_image(self):
        self.add_image_lock.acquire()
        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()
        self.add_image_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)
load_next_image_process = threading.Thread(target=buffer.add_image)
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
import threading


class Image:
    def __init__(self, filename, time=500, size=500):
        self.filename = filename
        self.size = size
        self.time = time
        self.shifted = 0.0
        img = cv2.imread(filename)
        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
        self.stack_lock = threading.Lock()
        self.add_image_lock = threading.Lock()

    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

    def add_image(self):
        self.add_image_lock.acquire()
        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()
        self.add_image_lock.release()


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

    buffer = ImageStack(filenames)

    prev_image = buffer.get_image()
    buffer.add_image()
    current_image = buffer.get_image()
    buffer.add_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()
        load_next_image_process = threading.Thread(target=buffer.add_image)
        load_next_image_process.start()


process()

Create a Moving Photo Slideshow with Weighted Transitions in OpenCV

What will we cover in this tutorial?

In this tutorial you will learn how to make a slideshow of your favorite photos moving across the screen with weighted transitions. This will be done in Python with OpenCV.

See the result in the video below.

Step 1: A simple approach without moving effect

If you want to build something great, start with something simple first. The reason for that is that you will learn along the way. It is difficult to understand all aspects from the beginning.

Start small. Start simple. Learn from each step.

Here we assume that you have all your favorite photos in a folder called pics. In the first run, you just want to show them on your screen one-by-one.

import cv2
import glob
import os

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

    for filename in filenames:
        print(filename)
        img = cv2.imread(filename)

        cv2.imshow("Slideshow", img)

        if cv2.waitKey(1000) == ord('q'):
            return


process()

As you will realize, this will show the photos in the size they stored. Hence, when photos change, the dimensions of the window will change as well (unless the two consecutive photos have the exact same dimensions). This will not make a good user experience. Also, if the photos dimensions are larger than your screen resolution, they will not be fully visible.

Step 2: Scaling images to fit inside the screen

We want the window size where we show the photos to have fixed size. This is not as simple as it sounds.

Image a photo has dimensions 1000 x 2000 pixels. Then the next one has 2000 x 1000. How would you scale it down? If you scale it down to 500 x 500 by default, then the objects in the images will be flatten or narrowed together.

Hence, what we do in our first attempt, is to scale it based on the dimensions. That is, a photo with dimensions 1000 x 2000 will become 500 x 1000. And a photo of dimensions 2000 x 1000 will become 1000 x 500. Then we will crop it to fit the 500 x 500 dimension. The cropping will take the middle of the photo.

import cv2
import glob
import os

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

    for filename in filenames:
        print(filename)
        img = cv2.imread(filename)

        height, width, _ = img.shape
        if width < height:
            height = int(height*500/width)
            width = 500
            img = cv2.resize(img, (width, height))
            shift = height - 500
            img = img[shift//2:-shift//2,:,:]
        else:
            width = int(width*500/height)
            height = 500
            shift = width - 500
            img = cv2.resize(img, (width, height))
            img = img[:,shift//2:-shift//2,:]

        cv2.imshow("Slideshow", img)

        if cv2.waitKey(1000) == ord('q'):
            return

process()

This gives a better experience, but not perfect.

Step 3: Make a weighted transition between image switches

To make a weighted transition we make it by adding a transition phase of the photos.

import cv2
import glob
import os
import numpy as np

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

    prev_image = np.zeros((500, 500, 3), np.uint8)
    for filename in filenames:
        print(filename)
        img = cv2.imread(filename)

        height, width, _ = img.shape
        if width < height:
            height = int(height*500/width)
            width = 500
            img = cv2.resize(img, (width, height))
            shift = height - 500
            img = img[shift//2:-shift//2,:,:]
        else:
            width = int(width*500/height)
            height = 500
            shift = width - 500
            img = cv2.resize(img, (width, height))
            img = img[:,shift//2:-shift//2,:]

        for i in range(101):
            alpha = i/100
            beta = 1.0 - alpha
            dst = cv2.addWeighted(img, alpha, prev_image, beta, 0.0)

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

        prev_image = img

        if cv2.waitKey(1000) == ord('q'):
            return

process()

Notice the prev_image variable that is needed. It is set to a black image when it enters the loop. The transition is made by using cv2.addWeighted(…) to get the effect.

Step 4: Make the photos move while showing

The idea is to let the photo move. Say, if the photo is scaled to dimension 500 x 1000. Then we want to create a view of that photo of size 500 x 500 that slides from one end to the other while it is showing.

This requires that we have a state for the photo, which stores where we are in of the current view.

For this purpose we create a class to represent a photo that keeps the current view. It also includes the resizing.

import cv2
import numpy as np
import glob
import os
import random


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

    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


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

    cnt = 0
    images = []
    for filename in filenames:
        print(filename)

        img = Image(filename)

        images.append(img)
        if cnt > 300:
            break
        cnt += 1

    prev_image = images[random.randrange(0, len(images))]
    prev_image.reset()

    while True:
        while True:
            img = images[random.randrange(0, len(images))]
            if img != prev_image:
                break
        img.reset()

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

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

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


process()

This results in a nice way where the photos slowly move through the view. It also has added some randomness. First of all, it takes a random photo. Also, the direction is set to be random.

This is a good start of having a nice slideshow of your favorite photos.

Insert Live Graph in Webcam Stream Using Webcam with OpenCV

What will we cover in this tutorial?

How to make a simple live graph that updates into a live webcam stream by using OpenCV.

The result can be seen in the video below.

Step 1: A basic webcam flow with OpenCV

If you need to install OpenCV for the first time we suggest you read this tutorial.

A normal webcam flow in Python looks like the following code.

import cv2
 
# Setup webcam camera
cap = cv2.VideoCapture(0)
# Set a smaller resolution
cap.set(cv2.CAP_PROP_FRAME_WIDTH, 640)
cap.set(cv2.CAP_PROP_FRAME_HEIGHT, 480)
 
while True:
    # Capture frame-by-frame
    _, frame = cap.read()
    frame = cv2.flip(frame, 1)
 
    cv2.imshow("Webcam", frame)
 
    if cv2.waitKey(1) == ord('q'):
        break
 
# When everything done, release the capture
cap.release()
cv2.destroyAllWindows()

This will make a live webcam stream from your webcam to a window. That is too easy not to enjoy.

Step 2: Create an object to represent the graph

There are many ways to create a graph. Here we will make an object which will have a representation of the graph. Then it will have a function to update the value and update the graph image.

class Graph:
    def __init__(self, width, height):
        self.height = height
        self.width = width
        self.graph = np.zeros((height, width, 3), np.uint8)

    def update_frame(self, value):
        if value < 0:
            value = 0
        elif value >= self.height:
            value = self.height - 1
        new_graph = np.zeros((self.height, self.width, 3), np.uint8)
        new_graph[:,:-1,:] = self.graph[:,1:,:]
        new_graph[self.height - value:,-1,:] = 255
        self.graph = new_graph

    def get_graph(self):
        return self.graph

This object is a simple object that keeps the graph as a OpenCV image (Numpy array).

The update function first verifies that the value of inside the graph size.

Then it creates a a new graph (new_graph) and copies the old values from previous graph, but shifted one position. Then it will update the new value by white color.

Step 3: Putting it all together

The Graph object created in last step needs a value. This value can be anything. Here we make a simple measure of how much movement is in the frame.

This is simply done by comparing the current frame with the previous frame. This could be done straight forward, but to minimize noise we use a gray scaled images, which we use Gaussian blur on. Then the absolute difference from last frame is used, and summing it up.

The value used to scale down is highly dependent on the settings your webcam is in. Also, if you use another resolution, then it will affect it. Hence, if the graph is all low (zero) or high (above height) then adjust this graph.update_frame(int(difference/42111)) to some other integer value in the division.

import cv2
import numpy as np


class Graph:
    def __init__(self, width, height):
        self.height = height
        self.width = width
        self.graph = np.zeros((height, width, 3), np.uint8)

    def update_frame(self, value):
        if value < 0:
            value = 0
        elif value >= self.height:
            value = self.height - 1
        new_graph = np.zeros((self.height, self.width, 3), np.uint8)
        new_graph[:,:-1,:] = self.graph[:,1:,:]
        new_graph[self.height - value:,-1,:] = 255
        self.graph = new_graph

    def get_graph(self):
        return self.graph


# Setup camera
cap = cv2.VideoCapture(0)
# Set a smaller resolution
cap.set(cv2.CAP_PROP_FRAME_WIDTH, 640)
cap.set(cv2.CAP_PROP_FRAME_HEIGHT, 480)

graph = Graph(100, 60)

prev_frame = np.zeros((480, 640), np.uint8)
while True:
    # Capture frame-by-frame
    _, frame = cap.read()
    frame = cv2.flip(frame, 1)
    frame = cv2.resize(frame, (640, 480))

    gray = cv2.cvtColor(frame, cv2.COLOR_BGR2GRAY)
    gray = cv2.GaussianBlur(gray, (25, 25), None)
    diff = cv2.absdiff(prev_frame, gray)
    difference = np.sum(diff)
    prev_frame = gray

    graph.update_frame(int(difference/42111))
    roi = frame[-70:-10, -110:-10,:]
    roi[:] = graph.get_graph()

    cv2.putText(frame, "...wanted a live graph", (20, 430), cv2.FONT_HERSHEY_PLAIN, 1.8, (200, 200, 200), 2)
    cv2.putText(frame, "...measures motion in frame", (20, 460), cv2.FONT_HERSHEY_PLAIN, 1.8, (200, 200, 200), 2)
    cv2.imshow("Webcam", frame)

    if cv2.waitKey(1) == ord('q'):
        break

# When everything done, release the capture
cap.release()
cv2.destroyAllWindows()
Exit mobile version