More results...

Generic selectors
Exact matches only
Search in title
Search in content
Post Type Selectors
post
page
Python IDE Dashboard

Dingbats – A Level Computer Science

Feeling confident with your A Level Computer Science terminology?

Have a go at guessing the hidden keywords or expressions represented by the following dingbats…

Dingbats 1 to 20Dingbats 21 to 40Dingbats 41 to 60Extras




Hint?

Here is a list of all the keywords used in the above dingbats, in alphabetical order

View Keywords!
AND gate
Abstract Syntax Tree
Abstraction
ALU (Arithmetic & Logic Unit)
Antivirus
Asymmetric Encryption
Bandwidth
Backtracking
Big O Notation
Binary addition
Binary left shift
Binary search
Binary search tree
Black box testing
Bluetooth speaker
Breakpoint
Breadth-first traversal
Brute force attack
Bubble sort
Clock speed
Colour depth
Comparison Operators
Control Unit
CPU
Data mining
Data visualisation
Decomposition
Defragmentation
Dictionary Coding
Divide and conquer
D-Type Flip-Flop
Dual core
File compression
Firewall
Floating point
Half-Adder
Hashing Algorithm
Hexadecimal
Indentation
Insertion sort
Instantiation
Linear search
Little Man Computer
Local Area Network
Logic error
Merge sort
Mesh topology
Multitasking
Multithreading
OOP
One-to-many Relationship
Operating System
Phishing
Pipelining
Quad core
Quick sort
Recursion
Run-length encoding
Run-time Error
Shortest path algorithm
Spider Bot
SQL Injection
Stack & Queue
Stack Overflow
Star topology
String
String concatenation
Symmetric Encryption
Syntax error
Translator
Unicode
USB key
Weighted graph
While loop
White box testing
Wide Area Network

Double Six Dice Game

2-diceIn this challenge, we will use a step by step approach to create a 2-player dice game with the following rules:

  • The first player rolls a pair of dice, and keeps rolling the dice again and again, until they roll a double six.
  • It is then the turn of the the second player. They too will roll the dice and keep doing so until they roll a double six.
  • The winner of the game is the user who rolled a double six in the smaller number of attempts.
  • The game ends on a draw if both players used the same number of attempts to roll a double six.

Python Code


So let’s tackle this Python challenge one step at a time… You will need to type your code in the code window below, using the step by step checklist provided underneath the code window.

Step by Step Checklist!

Step 1: Displaying a welcome banner

    Write some Python code using the print command to display to display a nice banner with the title of the game: “Double Six Dice Game”. Your banner could look like this:

    ___________________________
    |                          |
    |   Double Six Dice Game   |
    |__________________________|

Step 2: Retrieving the name of the first player

    Use an input command to ask for the first player to enter their name. Store this name in a variable called player1. You will have to use this variable later on, at the end of the game to display the name of the winner of the game.
Step 3: Throwing the first dice…

    Use the randint function from the random library to generate and output a random number between 1 and 6 for the first dice. Store this randomly generated number in a variable called dice1.

    Here is the Python code to generate a random number from 1 to 10:

    import random
    number=random.randint(1,10)
Step 4: Throwing the second dice…

    Re-use the code from step 3 to generate and output a second random number between 1 and 6. Store this randomly generated number in a variable called dice2.
Step 5: Carry on throwing the dice until a double six is rolled.

    You will now need to use a while loop, to repeat steps 3 and 4 for as long as player 1 doesn’t throw a double six.
Step 6: Counting the number of throws.

    Add a counter using a variable called counter1 to count the number of attempts/throws of the two dice. You will need to:

    • Initialise your counter1 variable at the start of the game to 0.
    • Increment your counter1 variable by 1 after each throw of the two dice.
    • Output the total number of attempts once a double six has been rolled.
Step 7: Player 2’s turn…

    Repeat steps 2 to 6 for player 2!
Step 8: Deciding who wins the game!

    Compare the counter of both players to display the appropriate message to end the game:

    • Player 1 wins if they have had less attempts than player 2.
    • Player 2 wins if they have had less attempts than player 1.
    • The game ends on a draw if both players have had exactly the same number of attempts to roll a double six.
unlock-access

Solution...

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

Dingbats – GCSE Computer Science

Feeling confident with your GCSE Computer Science terminology?

Have a go at guessing the hidden keywords or expressions represented by the following dingbats…

Dingbats 1 to 12Dingbats 13 to 24Dingbats 25 to 36Extras




Hint?

Here is a list of all the keywords used in the above dingbats, in alphabetical order

View Keywords!
AND gate
Abstraction
ALU (Arithmetic & Logic Unit)
Antivirus
Bandwidth
Binary addition
Binary left shift
Binary search
Bluetooth speaker
Breakpoint
Brute force attack
Bubble sort
Clock speed
Colour depth
Comparison Operators
Control Unit
CPU
Decomposition
Defragmentation
Dual core
Encryption
File compression
Firewall
Hexadecimal
Indentation
Insertion sort
Linear search
Local Area Network
Logic error
Merge sort
Mesh topology
Multitasking
Operating System
Phishing
Quad core
SQL Injection
Star topology
String
String concatenation
Syntax error
Translator
Unicode
USB key
While loop
Wide Area Network

Procedural Programming Terminology (Crossword)

crosswordAre 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

unlock-access

Solution...

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

Morse Code using a Binary Tree

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 = “. – – –”)

morse-code-binary-tree-bgClick 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:
morse-code-binary-tree-P

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.

unlock-access

Solution...

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

Computer Hardware Crossword

crosswordA 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

unlock-access

Solution...

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

Connect Flow (Backtracking Algorithm)

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:
connect-flow
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:

Frog Puzzle (Backtracking Algorithm)

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:
frog-pond-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:
frogs-and-waterlilies

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):
frog-moves

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:
frog-pond-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: ,

Insertion, Bubble, Merge and Quick Sort Algorithms

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:

Quick Sort Algorithm

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):
Quick-Sort-Algorithm

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: