More results...
Are you confident with your knowledge of key procedural programming concepts, including sequencing, selection, iteration and the use of subroutines?
You can find out more about the key terminology relevant to procedural programming using our Periodic Table of Procedural Programming Concepts.
Procedural Programming TerminologyOpen Crossword Puzzle in a New Window
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:
For instance, the morse code for letter P is . – – . as explained on this diagram:
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 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.
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
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:
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.
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:
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:
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]]
}
You can investigate here the full Python code used to implement our backtracking algorithm using a recursve function called jumpAround().
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:
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.
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)
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: 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: 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)
See below the full code for all four sorting algorithms.
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 example below uses the mid-value of the list (value in the middle position):
Here is our Python implementation of a quick sort algorithm using a recursive function. This implementation uses the mid-value as the pivot.
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:
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
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.
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:
In Python, a queue can be implemented as a simple list:
Tweak the above code to perform a breadth-first traversal of the two other binary trees provided in the above tabs.
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:
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:
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:
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:
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:
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…
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.
LMC Simulator
Logic Gates Circuits
Network Designer
Flowchart Studio
Online Python IDE