Morse Code using a Binary Tree

Posted on November 30, 2021 by Administrator Posted in Computer Science, Python - Advanced, Python Challenges, Solved Challenges

The Morse Code was designed to quickly transfer messages using a series of “dots (.)” and “dashes (-)”. Morse code was named after Samuel Morse, one of the inventors of the telegraph.

The International Morse Code includes the 26 letters of the alphabet (there is no distinction between lowercase and uppercase characters), the 10 Arabic numerals (digits from 0 to 9) and a few punctuation and arithmetic signs such as +, -, = etc.

Each character consists of a series of 1 to 5 dots or dashes (also called “dits” and “dahs”). The code was designed taking into consideration the frequency of each character in the English language so that most frequent characters such as E and T consist of just 1 dot or dash (E = “.”, T = “–”) whereas less frequent characters may include 4 to 5 dots or dashes (e.g. Q = “– – . –” and J = “. – – –”)

Click on the above picture to open it in a new window.

To find out the morse code for each character of the International Morse Code, we can use the following binary tree. Starting at the root of the tree, the succession of branches connecting the root node to the required character gives us the morse code for this character considering that:

a left branch corresponds to a dot (.)
a right branch corresponds to a dash (–)

For instance, the morse code for letter P is . – – . as explained on this diagram:

Video Tutorial

Morse Code encoder using a Binary Tree

The following code is using a binary tree data structure to store the more code binary tree.

It then uses the tree to convert a message into morse code by locating each character in the message within the tree and working out the morse code equivalent for each character.

In the code below, our binary tree only includes the first four levels, needed to code all 26 letters of the alphabet.

Your Challenge

Your task consists of completing the above program to take a user input in morse code, and use the binary tree to decode the message one character at a time.

Solution...

The solution for this challenge is available to full members!
Find out how to become a member:
➤ Members' Area

Tagged with: Binary Tree

Computer Hardware Crossword

Posted on November 29, 2021 by Administrator Posted in A Level Concepts, A Level Quiz, Computer Hardware, Computer Science, Computing Concepts, Computing Terminology Quiz, Crosswords, GCSE Concepts, GCSE Quiz, Solved Challenges

A computer system consists of hardware and software. The hardware components are the physical components of the computer system whereas software refers to the programs that run on and control the computer hardware.

Some of the hardware components can be found inside the main unit/case of the computer, whereas some external peripherals can be externally plugged in. There are four main types of hardware components: input devices, output devices, processing components (including the CPU and GPU), and storage devices.

Are you confident with your knowledge of computer hardware? Can you identify the purpose and characteristics of the main hardware components of a computer system? Complete these crossword to test your knowledge!
Computer Hardware CrosswordOpen Crossword Puzzle in a New Window
Computer Hardware CrosswordOpen Crossword Puzzle in a New Window

Solution...

The solution for this challenge is available to full members!
Find out how to become a member:
➤ Members' Area

Tagged with: Quiz

Connect Flow (Backtracking Algorithm)

Posted on November 28, 2021 by Administrator Posted in A Level Concepts, Algorithms, Computer Science, Computing Concepts, Python - Advanced, Python Challenges

The aim of this challenge was to write a recursive backtracking algorithm to solve a connect flow puzzle. The aim of the game is to connect all the pairs of dots of the same colours, positioned on a 2D grid, using continuous lines. The connection lines cannot cross over each other.

Here is a fully solved connect flow grid:

In order to try to reduce the number of steps (backtracks) needed by the algorithm to solve this puzzle we have applied the following heuristics:

Start the puzzle by calculating the taxicab distance between each pair of nodes of the same colour. Use this information to prioritise the nodes with a shorter distance. For instance on the gird above, the algorithm will focus on the brown, purple and pink lines first as these are more likely going to be connected by a short line.
When investigating a path between two dots, at each step the algorithm can investigate 4 directions (Top, Right, Bottom, Left). The algorithm prioritises directions that would reduce the taxicab distance between the next position and the end point. (e.g. going to the right first if the end point is to the right of the current position).

Python Code

Here is the full Python code for our backtracking algorithm. Our first option is not implementing the two heuristic strategies mentioned above, whereas our second option is based on these heuristic strategies.

Solution #1: Without heuristicsSolution #2: With basic heuristics

Tagged with: Backtracking

Frog Puzzle (Backtracking Algorithm)

Posted on November 22, 2021 by Administrator Posted in Algorithms, Computer Science, Computing Concepts, Python - Advanced, Python Challenges

This challenge is based on this Frog puzzle board game.

At the start of the game several green frogs and one red frog are positioned on the board/pond on different waterlilies based on a given configuration. (The game comes with a set of cards, each card describing one different configuration / puzzle to solve).

Here is an example of initial configuration:

The aim of this game is to remove all the green frogs from the board/pond so that only the red frog remains on the board. A frog is removed from the board when it falls off its waterlily. This happens when another frog hops above its head:

When a frog is on a waterlily, it can jump over adjacent waterlilies only when:

There is another green frog on the adjacent waterlily,
The waterlily where the frog would land is empty.

The aim of this programming challenge was to design and implement an algorithm to search for a solution to this puzzle using a trial-and-error approach. This can be done in Python using a backtracking algorithm which will identify the possible moves on the board, and try these moves until it either finds a solution (only one red frog remains on the board) or reaches a dead end (when several frogs are left on the board but can no longer jump around). If after moving frogs around a dead end, is met, the algorithm will backtrack to previous moves to try alternative possible moves.

The possible moves a frog can do depend on its position on the board as well as the position of other frogs. For instance, here are two different diagrams to show potential moves of a frog placed on the top-left waterlily (0) or on the central waterlily (6):

By investigating all the possible moves from each waterlily we can construct a weighted graph where:

The nodes of the graph are the thirteen waterlilies (0 to 12),
The weight for each edge of the graph is number of the waterlily that is being jumped over.

This approach results in the following weighted graph:

In Python, a graph can be stored as a dictionary of lists. Each key of the dictionary represents a node, the value associated to each key is a list of edges. Each edge will contain a sub-list of two values: the node/waterlily being reached and the waterlily being jumped over (the weight of the edge).

Here is how the above graph is implemented in Python:

#The graph representing all the potential jumps a frog can do
pond = {0:[[2,1],[6,3],[10,5]],
        1:[[5,3],[11,6],[7,4]],
        2:[[0,1],[6,4],[12,7]],
        3:[[9,6]],
        4:[[8,6]],
        5:[[1,3],[7,6],[11,8]],
        6:[[0,3],[2,4],[12,9],[10,8]],
        7:[[1,4],[5,6],[11,9]],
        8:[[4,6]],
        9:[[3,6]],
        10:[[0,5],[6,8],[12,11]],
        11:[[5,8],[1,6],[7,9]],
        12:[[10,11],[6,9],[2,7]]
       }

Python Code

You can investigate here the full Python code used to implement our backtracking algorithm using a recursve function called jumpAround().

A step further…

Could a similar approach be used to solve a game of solitaire?
Could a similar approach be used to implement an AI for a player play a game of draughts against the computer?

Tagged with: Backtracking, Graph

Insertion, Bubble, Merge and Quick Sort Algorithms

Posted on November 20, 2021 by Administrator Posted in A Level Concepts, Algorithms, Algorithms (GCSE), Computer Science, Computing Concepts, Python - Advanced, Python Challenges

In computer science, sorting algorithms are used to sort the elements of a data sets in numerical or alphabetical order. In this blog post will investigate the Python code used to implement 4 of the most frequently used sorting algorithms:

Insertion Sort
Bubble Sort
Merge Sort
Quick Sort

We will implement the first two algorithm using nested loops. (Iterative algorithms) whereas the Merge sort and Quick sort algorithms will be based on using recursive functions to implement the divide-and-conquer approach these algorithms are based on.

Insertion SortBubble SortMerge SortQuick Sort

Insertion Sort Algorithm

def insertionSort(list):
  #Iterate through each value of the list
  for i in range(1,len(list)):
    pointer = i
    
    #Slide value on the left to insert it in postion
    while list[pointer]<list[pointer-1] and pointer>0:
      #Swap values with the previous value...
      tmp=list[pointer]
      list[pointer]=list[pointer-1]
      list[pointer-1] = tmp
      
      pointer = pointer - 1
   
    #Print list at the end of each iteration
    print(list)

Bubble Sort Algorithm

def bubbleSort(list):
  counter = len(list)-1
  sorted=False
  
  #The Bubble sort stops iterating if it did not perform any "swap" in the previous iteration.
  while sorted==False:
    sorted=True
    for pointer in range(0,counter):
      if list[pointer]>list[pointer+1]:
        #Swap values with the next value...
        tmp = list[pointer]
        list[pointer] = list[pointer+1]
        list[pointer+1] = tmp
        sorted=False
    #Print list at the end of each iteration
    print(list)  
    counter-=1

Merge Sort Algorithm

#Merge Sort: A divide-and-conquer algorithm implemented using a recursive function!
def mergeSort(list):
  midPointer = len(list) // 2
  
  leftList = list[0:midPointer]
  rightList = list[midPointer:len(list)]
  
  if len(leftList)>2: 
    leftList = mergeSort(leftList)
  else:
    if len(leftList)==2:
      if leftList[0]>leftList[1]:
        tmp = leftList[0]
        leftList[0] = leftList[1]
        leftList[1] = tmp
       
  if len(rightList)>2: 
    rightList = mergeSort(rightList)
  else:
    if len(rightList)==2:
      if rightList[0]>rightList[1]:
        tmp = rightList[0]
        rightList[0] = rightList[1]
        rightList[1] = tmp
        

  #Merge left and right...'
  leftPointer = 0
  rightPointer = 0
  sortedList=[]
  while leftPointer<len(leftList) and rightPointer<len(rightList):
    if leftList[leftPointer] < rightList[rightPointer]:
       sortedList.append(leftList[leftPointer])
       leftPointer += 1
    else:   
       sortedList.append(rightList[rightPointer])
       rightPointer += 1
  
  while leftPointer<len(leftList):
    sortedList.append(leftList[leftPointer])
    leftPointer+=1
  while rightPointer<len(rightList):
    sortedList.append(rightList[rightPointer])
    rightPointer+=1
    
  return sortedList

Quick Sort Algorithm

#Quick Sort: Another divide-and-conquer algorithm implemented using a recursive function!
def quickSort(list, leftPointer, rightPointer):
  # Use the mid value as the pivot
  pivotPointer = leftPointer + ((rightPointer-leftPointer) // 2)
  
  # Alternative approach: use the first value as the pivot
  #pivotPointer = leftPointer
  
  # Alternative approach: use the last value as the pivot
  #pivotPointer = rightPointer
  
  print("Pivot: " + str(list[pivotPointer]))
  left_Pointer = leftPointer
  right_Pointer = rightPointer
  
  while leftPointer<rightPointer:
    #Find the next value to swap (left side of the pivot)
    while list[leftPointer]<=list[pivotPointer] and leftPointer<pivotPointer:
      leftPointer = leftPointer+1
      
    #Find the next value to swap (right side of the pivot)
    while list[rightPointer]>=list[pivotPointer] and rightPointer>pivotPointer:
      rightPointer = rightPointer-1  
    
    if leftPointer<rightPointer:  
      #Swap both values 
      tmp = list[leftPointer]
      list[leftPointer] = list[rightPointer]
      list[rightPointer] = tmp
      #Has the pivot moved?
      if leftPointer == pivotPointer:
        pivotPointer = rightPointer
      elif rightPointer == pivotPointer:
        pivotPointer = leftPointer
  
  print(list)
  # Let's implement the double recursion to quick sort both sub lists on the left and the right of the pivot Pointer
  if pivotPointer-1-left_Pointer>=1: #Stop the recursion if there is only on value left in the sublist to sort
    quickSort(list,left_Pointer,pivotPointer-1)
  if right_Pointer - (pivotPointer+1)>=1: #Stop the recursion if there is only on value left in the sublist to sort
    quickSort(list,pivotPointer+1,right_Pointer)

Full Python Code

See below the full code for all four sorting algorithms.

Tagged with: Sorting Algorithms

Quick Sort Algorithm

Posted on November 19, 2021 by Administrator Posted in A Level Concepts, Algorithms, Computer Science, Computing Concepts, Python - Advanced, Python Challenges

The quick sort algorithm is a divide-and-conquer algorithm that can be implemented using a recursive function. The following graphic explains the different steps of a quick sort algorithm.

Note, that the quick sort algorithm starts by identifying a pivot. Depending on the implementation, this pivot can be one of the following three values:

The first value of the list of values to be sorted,
The mid-value of the list,
The last value of the list.

The example below uses the mid-value of the list (value in the middle position):

Python Code

Here is our Python implementation of a quick sort algorithm using a recursive function. This implementation uses the mid-value as the pivot.

Tagged with: Sorting Algorithms

Breadth-First Traversal of a Binary Tree

Posted on November 16, 2021 by Administrator Posted in A Level Concepts, Algorithms, Computer Science, Computing Concepts, Python - Advanced, Python Challenges

A tree is a complex data structure used to store data (nodes) in a “parent/child” relationship. The top node of a tree (the node with no parent) is called the root. Each node of a tree can have 0, 1 or several child nodes. In a Binary Tree, each node can have a maximum of two child nodes.

The Breadth-First Traversal of a tree is used to read all the values of a tree, one level at a time, from the top level (root node) to the bottom level:

In this blog post will first:

Investigate how to use Python to create a binary tree data structure,
Use our binary tree data structure to initialise different binary trees,
Use an algorithm to implement a breadth-first traversal of our tree,

Using a Node Class to create a Binary Tree

The following Python code is all what’s needed to create a Node/Tree structure.

#A class to implement a Node / Tree
class Node:
  def __init__(self, value, left=None, right=None):
    self.value = value
    self.left = left
    self.right = right

Initialising the values of a Binary Tree

Binary Tree #1Binary Tree #2Binary Tree #3

In order to initialise the above Binary Tree (Tree #1) we will need the following Python code:

tree = Node(47)  #The root node of our binary tree
tree.left = Node(36)
tree.right = Node(66)

tree.left.left = Node(25)
tree.left.right = Node(39)
tree.left.right.left = Node(38)
tree.left.right.right = Node(42)

tree.right.left = Node(63)
tree.right.left.right = Node(64)
tree.right.right = Node(68)

Note that we have included other trees (#2 and #3) for you to initialise in Python for testing purposes.

Breadth-First Traversal of a Binary Tree

In order to implement a Breadth-First Traversal of a Binary Tree, we will need to use a queue data structure and we will base our algorithm on the following steps:

Initialise the queue by enqueuing the root node of the tree to traverse
While the queue is not empty:

Dequeue a node from the queue,
Output the value of this node,
Enqueue the left and right node of this node to the queue.

In Python, a queue can be implemented as a simple list:

Enqueuing an element to a list is done using the following instruction:
list.append(element)
Dequeuing an element from a list is done by removing its first element using the following instruction:
node = list.pop(0)
Checking if a queue is empty can be done by checking if the length of the list is equal to 0:
if len(list)==0:

Full Python code for the Breadth-First Traversal of a Binary Tree

Your Task:

Tweak the above code to perform a breadth-first traversal of the two other binary trees provided in the above tabs.

Rush Hour Backtracking Algorithm

Posted on November 14, 2021 by Administrator Posted in Algorithms, Computer Science, Python - Advanced, Python Challenges

In this challenge we will implement a backtracking algorithm to solve a game of Rush Hour using a trial and error approach. We will also investigate the need to apply some basic heuristics to improve our algorithm and avoid a situation of stack overflow, a common issue with recursive/backtracking algorithms when there are too many paths to investigate!

First, you will need to be familiar with the rules of the Rush Hour game. You can find out more about this game on this page.

The goal of the game is to get the red car out of the parking bay through the exit of the board (on the right hand side of the 6×6 board). To do so the player has to move the other vehicles out of its way by sliding them either vertically or horizontally depending on the orientation of the vehicle. The vehicles of different colours and length (cars are 2 squares long and trucks are three squares long) are set up at the start of the game based on a given configuration). In the physical game, there are 40 different initial configurations to solve. The 40 configurations are categorised in 4 grouped based on their difficulty level: the number of moves needed to solve the puzzle. The 4 categories are: Beginner Level, Intermediate, Advanced and Expert Level!

To implement this game, we are using a 2D array/grid to represent the parking bay with all the vehicles. Each number on this array represent the colour of a vehicle. On this grid/array:

An empty square has a value 0,
The bordering walls have a value of 1.
The red car has a value of 2.
All the other colours/vehicles have a value between 3 and 14.

A backtracking algorithm is a recursive algorithm that will test potentially every possible move, one by one. To reduce the number of possibilities, a backtracking algorithm will aim to identify as soon as possible, when a move can be discarded as it will not lead to a solution. (Without the need to investigate different moves to complete the puzzle, hence saving some processing time!).

Backtracking algorithms, being recursive use a “call stack” to record/memorise the state of the variables and data structures used in the recursive function for each move in order to be able to reload them when backtracking. In this case the full copy of the 2D grid will be pushed to a the call stack for each move/call of the recursive function. Such an algorithm is hence fairly greedy in terms of system resources and when there are too many moves to investigate before reaching a solution, the code may generate a stack overflow error which would stop the execution of the code before finding a solution!

One approach to make a backtracking algorithm more effective is to apply some heuristics in the implementation of the game to try to focus first on the moves which are more likely to lead towards a solution. Our second approach is applying some basic heuristics based on the following assumptions:

If the red car can slide to the right, this should be the first move to make as it will bring the car closer to the exit gate so may be more likely to lead to a solution in less steps. (though this is not always the case, especially with “expert level” challenges)
If the red car cannot be moved to the right, the algorithm should focus on sliding other horizontal cars/trucks to the left (when possible), as this would free up spaces on the right of the grid, which could be needed to then slide vertical cars that may be obstructing the exit gate.
Then, the first set of vehicles to focus on are the vertical cars/trucks which are blocking the path for the red car to reach the exit gate. When possible these should be moved up or down. Trucks (which are 3 square long) should preferably moved down as if they are not parked alongside the bottom edge of the grid, they will block the path of the red car.

Python Implementation

Solution #1: Without heuristicsSolution #2: With basic heuristics

Without implementing any heuristics… This solution is ineffective and may lead to a stack overflow!

This time we have implemented some basic heuristics as described above. In this case, the algorithm is a lot quicker to find a working solution!

Tagged with: Backtracking

Noah’s Ark Backtracking Algorithm

Posted on November 12, 2021 by Administrator Posted in Algorithms, Computer Science, Python - Advanced, Python Challenges

In this challenge, we are going to use a backtracking algorithm to solve a puzzle game called Noah’s Ark.

First, you will need to fully understand how the game works. You can check the “How To Play” tab on this page. The game consists of trying to fill up Noah’s Ark by positioning different pieces on a grid. Each piece represents an animal. The pieces come in different shapes (to some extent similar to the shapes using in a Tetris game) and different colours. Each colour represents an animal and, for each animal, there are two pieces of different shapes. The animals are:

2 Lions (yellow),
2 Zebras (red),
2 Hippopotamus (blue),
2 Giraffes (yellow),
2 Elephants (purple).

There are just enough spaces/cells on the grid to fit all the pieces/animals. The rule is that two pieces of the same colour must be adjacent (have at least one edge in common).

The game starts with a given grid where 1,2, or 3 animals/pieces are already positioned. The player can then use a trial and error approach to position all the remaining pieces on the grid. Each puzzle (starting grid) should have a unique solution.

To implement this game in Python, we will use a 2D array to represent the ark with all its cells.

All our animals will also be stored as 2D arrays using different values to represent each colour:

A backtracking algorithm is a recursive algorithm that will test potentially every possible position of the different pieces of the game, one by one. To reduce the number of possibilities, a backtracking algorithm will try to identify as soon as possible, when an incomplete grid can be discarded as it will not lead to a solution. (Without the need to investigate different moves to complete the grid, hence saving some processing time!).

In our backtracking algorithm, we are positioning one piece at a time on the ark (the 2D grid). A soon as we place a piece on the grid, we check if the piece is in a valid position. If not we try a different position for the piece. If there is no valid position for the piece on the grid, we backtrack one step, cancelling the previous move and we then resume our search for a solution from there.

In the algorithm, an invalid position is defined as follows:

When positioning the piece, if we create an isolated blank cell, the grid can be discarded as it will be impossible to fill it in later on: All pieces in the game need a gap of at least two consecutives empty cells,
If both pieces of the selected colour (both animals of a pair) are on the grid, then we check that the two pieces are adjacent. If not, the grid is not a valid one and can be discarded.

Each puzzle to solve will always start with an initial grid with 1, 2 maybe 3 pieces already placed on the grid. Each puzzle should have a unique solution.

For this demo, we will use the following initial grid, with just one piece already in place:

Our Solution

When running this code, you can see how the algorithm is trying to find a solution by shifting different pieces on the grid, one at a time and applying a trial and error approach, backtracking a few steps when a grid cannot be solved.

The algorithm is first trying to position the second blue piece as follows:

However this position is immediately discarded as the two blue pieces are not adjacent.

The second position to be investigated is as follows:

Once again, this position is immediately discarded as the two blue pieces are not adjacent.

The third position to be investigated by the algorithm is as follows:

In this case, the two blue pieces are adjacent, however the algorithm is discarding this position too because it has generated an isolated empty space (in the top right corner of the ark).

The 4th position to be investigated is as follows:

This position is a valid position, so the algorithm can investigate it further by starting to place other pieces till it either finds a solution or backtracks to test a fifth position of the blue piece and so on…

Python Code

You can change the SPEED constant on line 3 to speed up/slow down the algorithm. We are pausing the algorithm for a few milliseconds between each move for visualisation purpose only.

Tagged with: Backtracking

Prime Factor Tree Algorithm

Posted on November 9, 2021 by Administrator Posted in A Level Concepts, Computer Science, Computing Concepts, Python - Advanced, Python Challenges

The Prime Factor Tree is a visual technique used in Maths to workout all the prime factors of a large number.

With this approach, all the leaf nodes (nodes without sub-branches) are the prime factors of the root node. For instance, with the above tree, the prime factors of 150 are 2, 3, 5 and 5 again. In other words:

150 = 2 x 3 x 5 x 5 = 2 x 3 x 5²

We have decided to create our own Prime Factor Tree Algorithm to build a binary tree structure to store all the prime factors of any given root number.

The aim of this challenge is to demonstrate one way to implement a Binary Tree Structure in Python using a very basic Node Class.

#A class to implement a Node / Tree
class Node:
  def __init__(self, value, left=None, right=None):
    self.value = value
    self.left = left
    self.right = right

With this approach, a Tree is in fact just a Node (a root Node)!
Here is how we could create a basic prime factor tree for number 10 = 2 x 5:

tree = Node(10)
tree.left = Node(2)
tree.right = Node(5)

We then added two additional methods to our Node Class:

The drawTree() method is used to draw the tree on screen. It’s based on a complex algorithm that we imported from the tree.py module.
The buildPrimeFactorTree() method is used to recursively add branches/sub-nodes to our root tree to build the Prime Factor Tree progressively.

Here is the full implementation of our Prime Factor Tree Algorithm in Python:

Tagged with: Binary Tree

Learning Zone ✕

Theory Concepts

Interactive Quizzes

GCSE Computer Science (UK)

A-Level Computer Science (UK)

Coding Challenges ✕

Python Challenges

HTML / CSS & JavaScript

LMC

SQL

Block Programming

Interactive Coding Puzzles

Online Interactive Tools ✕

Coding Tools

Design Tools

Logic Gates Circuits

Cryptography Corner

Member's Area ✕

Register/Sign Up

Get In Touch

Books Corner

Video Tutorial

Morse Code encoder using a Binary Tree

Your Challenge

Solution...

Solution...

Python Code

Python Code

A step further…

Insertion Sort Algorithm

Bubble Sort Algorithm

Merge Sort Algorithm

Quick Sort Algorithm

Full Python Code

Python Code

Using a Node Class to create a Binary Tree

Initialising the values of a Binary Tree

Breadth-First Traversal of a Binary Tree

Full Python code for the Breadth-First Traversal of a Binary Tree

Your Task:

Python Implementation

Our Solution

Python Code

Our Latest Book

Recent Posts