Square Root Estimation Algorithms

Posted on February 4, 2021 by Administrator Posted in Computer Science, Python - Intermediate, Python Challenges, Solved Challenges

Calculating the square value of a number is a very straightforward
process which consists of multiplying this number by itself. For instance:

15² = 15 x 15 = 225

The reverse operation which consists of calculating the square root of a number is not so easy without using the square root function of a calculator. In this blog post we will investigate how to accurately calculate the square root of a number using Python and we will then implement and compare two methods that were used a few centuries ago to estimate the square root value of any given number:

The Babylonian Method,
The Bakhshali Method.

Exponentiation

High level programming languages such as Python have an arithmetic operator to raise a number to the power of an exponent.

In pseudocode the exponentiation operator is the ^ operator.
For instance: 3² appears as 3^2 when using pseudocode.

In Python, the exponentiation operator is **. e.g.:

# 5 to the power of 2 is 25
square = 5 ** 2
# 5 to the power of 3 is 125
cube = 5 ** 3

Square Root = To the power of half

We can easily calculate the square root of a number in a computer program using the exponentiation operator knowing that:

√x = x^½ = x^0.5

So in Python:

# Square root of 25 is...
sqrt = 25 ** 0.5

The Babylonian method

Procedures for calculating/estimating square roots have been known since at least the period of ancient Babylon in the 17th century BCE. Heron’s method (aka Babylonian method) from first century Egypt was the first ascertainable algorithm for computing square root.

This approach is based on estimating the limit of the following convergent sequence:

To implement the Babylonian method of estimating a square root we will use the following algorithm:

Python Code

Use the above flowchart to complete the code below:

The Bakhshali method

This method for finding an approximation to a square root was described in an ancient Indian mathematical manuscript called the Bakhshali manuscript. It uses a similare approach the Babylonian method using a different convergent series as described below:

Your task is to adapt your Python script to implement the Bakhshali method and compare how both series perform to estimate a square root value using a fixed number of iterations.

Solution...

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

Multimedia Library (OOP Concepts)

Posted on January 28, 2021 by Administrator Posted in Computer Science, Computing Concepts, OOP Concepts, Python - Advanced, Python Challenges

In this blog post, we will write a computer program to create and maintain a multimedia library of books, CDs and DVDs. The aim of this programming task is to demonstrate some key Object-Oriented Programming concepts such as:

Creating Classes and Objects,
Using Derived Classes (implementing Inheritance),
Using an Abstract class,
Implementing over-riding Polymorphism,
Implementing over-loading Polymorphism.

Class Diagram

This project will be based on the following class diagram:

The Library class will be used to maintain a list of items (Books, DVDs, CDs). It will have a range of methods to:

Add a new item to the list of items,
Remove an item from the list of items,
View the full list of items,
Reset/Empty the list of items,
Find out the number if items in the library.
Find out if the library is empty.

Abstract Class

The Item class is an abstract class: It will not be used to instantiate objects directly from this class. Instead, objects will be instantiated from the three derived classes Book, CD and DVD.

Inheritance

This class diagram clearly shows the inheritance relationship between the Item class and the Book, CD and DVD classes:

The Item class is the parent class (also called master class or super class)
The Book class, CD class and DVD class are the derived classes (also called sub classes or child classes).

When a class such as the Book class inherit from a parent class (Item class), it inherits all the properties and methods from the parent class. Hence a book will inherit the title and the description properties as well as the viewDescription() method from the Item class.

Additional properties and methods can be added to a derived class. For instance the Book class as its own specific properties: author and isbn.

Over-Riding Polymorphism

The viewDescritpion() method is an example of over-riding polymorphism: It has been defined in the parent Item class as an abstract method. It is then implemented differently in the derived classes Book, CD and DVD. You can check the Python code in the trinket below to see the three different implementations of the viewDescription() method in the Book, CD and DVD classes.

Over-Loading Polymorphism

We did not implement over-loading polymorphism in this example as it is not directly supported in Python. Over-loading polymorphism is used when the same method is implemented several times within a class, each time accepting a different set of parameters (either a different number of parameters, or using parameters of different data types).

For instance, we could implement over-loading polymorphism to the addItem() method of the Library class as follows:

def addItem(self, item): #the item parameter is an object (e.g. Book, CD or DVD)#
   self.items.append(item)

def addItem(self, title, description, author, isbn):
   book = Book(title, desription, author, isbn)
   self.items.append(book)

def addItem(self, title, description, artist, genre, numberOfTracks):
   cd = CD(title, desription, artist, genre, numberOfTracks)
   self.items.append(cd)

def addItem(self, title, description, director, certificate):
   dvd = DVD(title, desription, director, certificate)
   self.items.append(dvd)

You can read this article to find out how to implement overloading polymorphism in Python using the multipledispatch library.

Python Code

Here is the Python code for our multimedia library project:

Tagged with: OOP

MP3 Playlist Class

Posted on January 27, 2021 by Administrator Posted in Computer Science, OOP Concepts, Python - Intermediate, Python Challenges

The aim of this challenge is to implement a Class in Python to maintain an MP3 Playlist. This class could be used when developing the software for a music App on a smartphone or an mp3 player.

This MP3 playlist will be stored as a queue of MP3 tracks. When new tracks are being added to the playlist, they are enqueued at the end of the playlist. The key features that we will implement within this class are the ability to:

Here is the class diagram for this project:

Python Code

We have started the code used to load a mp3 playlist from a text file.
Your task is to complete this code to implement all the methods mentioned above.

Solution (Step by step)

load() & save()enqueue()remove()getNumberOfTracks()getTotalDuration()shuffle()reset()isEmpty()

The load() and save() methods are used to load a playlist from a CSV file and save it on the CSV file. The save method() will overwrite the playlist if it already exists or create a new file if the file does not exists.

Here is the code to add to the Playlist class:

def load(self):
    self.tracks = []
    print("Loading tracks from CSV file.")
    file = open(self.filename,"r")
    for line in file:
      fields = line.split(";")
      track = Track(fields[0],fields[1],int(fields[2]))
      self.tracks.append(track)    
    file.close()
    
def save(self):
    print("Saving your playlist...")
    file = open(self.filename,"w")
    for track in self.tracks:
      file.write(track.title + ";" + track.artist + ";" + str(track.duration)+ ";")
    file.close()
    print("Playlist saved!")

In the main program we can test our load() and save() methods using the following code:

from playlist import Track, Playlist

myPlaylist = Playlist("Pop Music","pop_music.csv")
myPlaylist.load()
myPlaylist.view()

#Add or remove tracks or shuffle the playlist... using the enqueue(), remove() and shuffle() methods.

myPlaylist.save()

The enqueue() method from the Playlist class is used to append a track at the end of the tracks list:

def enqueue(self, track):
    self.tracks.append(track)

You can test this code as follows:

from playlist import Track, Playlist

myPlaylist = Playlist("Pop Music","pop_music.csv")
myPlaylist.load()

newTrack = Track("Wonderwall","Oasis",245)
myPlaylist.enqueue(newTrack)
myPlaylist.view()

myPlaylist.save()

The remove() method from the Playlist class is used to remove a track from the track list:

def removeTrack(self, track):
    self.tracks.remove(track)

You can test this code as follows:

from playlist import Track, Playlist

myPlaylist = Playlist("Pop Music","pop_music.csv")
myPlaylist.load()

myPlaylist.view()
myPlaylist.removeTrack(myPlaylist.tracks[2]) #This will remove the third track from the playlist!
myPlaylist.view()

This method will return the length of the tracks list.

def getNumberOfTracks(self):
    return len(self.tracks)

To test this method:

from playlist import Track, Playlist

myPlaylist = Playlist("Pop Music","pop_music.csv")
myPlaylist.load()

numberOfTracks = myPlaylist.getNumberOfTracks()
print("This playlist has " + str(numberOfTracks) + " tracks!")

To calculate the total duration of a playlist we need to add the duration of each of its tracks.

def getTotalDuration(self):
    duration = 0
    for track in self.tracks:
      duration += track.duration
    return duration

To test this method:

from playlist import Track, Playlist

myPlaylist = Playlist("Pop Music","pop_music.csv")
myPlaylist.load()

duration = myPlaylist.getTotalDuration()
print("This playlist lasts " + str(duration) + " seconds!")

The shuffle method just needs to shuffle the list of tracks using the shuffle() function from the random library.
We will hence need to import the random library by adding the following line at the top of the playlist.py file:

import random

Then we will add the following method to the Playlist class:

def shuffle(self):
  random.shuffle(self.tracks)

In the main program we can test our shuffle method using the following code:

from playlist import Track, Playlist

myPlaylist = Playlist("Pop Music","pop_music.csv")
myPlaylist.load()

myPlaylist.shuffle()
myPlaylist.view()

To reset a playlist we just need to reset its tracks list to an empty list.

def reset(self):
  self.tracks = []

In the main program we can test our reset method using the following code:

from playlist import Track, Playlist

myPlaylist = Playlist("Pop Music","pop_music.csv")
myPlaylist.load()

myPlaylist.reset()
myPlaylist.view()

To check is a playlist is empty we can check if the length of its tracks list is equal to 0.

def isEmpty(self):
  return len(self.tracks)==0

In the main program we can test our reset method using the following code:

from playlist import Track, Playlist

myPlaylist = Playlist("Pop Music","pop_music.csv")
myPlaylist.load()

if myPlaylist.isEmpty():
   print("Your playlist is empty.")

myPlaylist.reset()

if myPlaylist.isEmpty():
   print("Your playlist is empty.")

myPlaylist.view()

Tagged with: OOP

Shopping Basket Class

Posted on January 26, 2021 by Administrator Posted in Computer Science, OOP Concepts, Python - Intermediate, Python Challenges, Solved Challenges

One of the key features of any e-commerce website is the shopping basket. It is used to let the end-users add products to their basket before proceeding to checkout.

In this Python challenge we will create a Shopping Basket class to implement the different functionalities (behaviours) such as:

To do so we will create the following two classes:

The items property of the Shopping Basket class will be a dictionary of items:quantity pairs. (The items are the keys, for each key, the quantity in the basket is the value)

Python Code

Your task

Add a new “Stock Level” property to the item class.

Update the addItem(), removeItem(), updateItem() and reset() methods of the Shopping Basket class to check the availability of the item in stock before adding/changing the desired quantity, and by updating the Stock Level property of the item class accordingly when items are added/removed from the shopping basket.

Solution...

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

Tagged with: OOP

Random Library Challenges

Posted on January 25, 2021 by Administrator Posted in Computer Science, Python - Intermediate, Python Challenges, Solved Challenges

In this blog post we will experiment using some of the key functions from the random library. Many Python games will involve some degree of “randomness” for the game to be more realistic and unpredictable. Flipping a coin, throwing a dice, shuffling a deck of cards, spawning a sprite at a random location, generating a random password are all actions that can be implemented in Python fairly easily using the random library.

So let’s first investigate the most useful functions from this library to find out how to:

Generate a random number/integer,
Generate a random letter from the alphabet,
Select a random value from a list,
Identify a random index/location from a list,
Shuffle the values from a list.

We will then apply these techniques to solve a set of mini challenges to generate the following random values:

Using the random libraryPython IDEPython Challenges

Generating a random integer:

To generate a random number between two values (e.g. between 1 and 10), you will need to use the random.randint() function:

import random
number = random.randint(1,10)
print(number)

Generating a random letter from the alphabet: (Using the ASCII code)

To generate a random letter from the alphabet we can use the ASCII code where the ASCII code for letter “A” is 65 and the ASCII code for letter “Z” is 90. To do so we will generate a random number between 65 and 90 to then retrieve the matching ASCCI character using the chr() function.

import random
ascii = random.randint(65,90)
letter = chr(ascii)
print(letter)

Generating a random letter from the alphabet: (Using the random.choice() function)

An alternative approach used to generate a random letter from the alphabet is to randomly select a character from a string using the random.choice() function.

import random
letter = random.choice("ABCDEFGHIJKLMNOPQRSTUVWXYZ")
print(letter)

Selecting a random value from a list: (using a random index)

We can randomly select a value from a list by first generating a random number between 0 and the length of the list -1. We can then use this rnadomlygenerated index to access the value from the list at the given position/index.

import random
weekdays = ["Monday","Tuesday","Wednesday","Thursday","Friday","Saturday","Sunday"]
index = random.randint(0,len(weekdays)-1)
day = weekdays[index]
print(day)

Selecting a random value from a list: (using the random.choice() function)

The random.choice() function can also be used to randomly pick a value from a list

import random
weekdays = ["Monday","Tuesday","Wednesday","Thursday","Friday","Saturday","Sunday"]
day = random.choice(weekdays)
print(day)

Shuffling list:

The random.shuffle() function is used to shuffle all the values from a list.

import random
weekdays = ["Monday","Tuesday","Wednesday","Thursday","Friday","Saturday","Sunday"]
random.shuffle(weekdays)
print(weekdays)

Adapt the code provided to complete the following challenges:

Challenge #1: Generating a random IP address:

random-ip-address
An IP address consists of 4 numbers between 0 and 255 separated by a dot. Your task is to write a Python script that generates and outputs a valid random IP address.

Challenge #2: Flipping a coin:

random-head-or-tails
Your task is to write a Python script that randomly outputs “Heads” or “Tails”.

Challenge #3: Throwing a dice:

random-throw-dice
Your task is to write a Python script to throw a dice by randomly generating a value between 1 and 6.

Challenge #4: Generating a random phone number:

random-phone-number
Your task is to write a Python script to generates a random phone number consisting of 11 digits.

Challenge #5: Generating a random postcode:

random-postcode
Your task is to write a Python script to generates a random UK postcode in the format: LetterLetterNumber_NumberLetterLetter.

Challenge #6: Generating a random date:

random-date
Your task is to write a Python script to generates a random date in the format: DD/MM/YYYY.

Challenge #7: Generating a randomly pick a playing card:

random-playing-card
Your task is to write a Python script to randomly pick and output a card from a deck of 52 playing cards. The program should output the suit and value of the card (e.g. 7 of hearts, Queen of clubs, etc…).

Challenge #8: Generating a random password:

random-password
Your task is to write a Python script to randomly generate a strong password mixing lowercase, uppercase, numbers and punctuation signs in any order.
You can check this post for some extra help on this challenge.

Challenge #9: Generating 6 random lottery numbers:

random-lottery-numbers
Your task is to write a Python script to randomly generates and outputs 6 unique random numbers between 1 and 50.
You can check this post for some extra help on this challenge.

Solution...

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

DOS Emulator using Python

Posted on January 22, 2021 by Administrator Posted in A Level Concepts, Computer Science, OOP Concepts, Python - Advanced, Python Challenges

In the 1980’s, when IBM introduced the IBM PC which was built with the Intel 8088 microprocessor, they needed an operating system. They approached Microsoft who provided IBM with the “Microsoft Disk Operating System”: MS-DOS.

A Disk Operating System is operated via a command prompt. The user can interact by typing key commands to maintain and operate their computer. One of the key functionality of a DOS operating system is the ability to navigate through the files and folders structure and create, rename, move or delete files and folders.

Try it yourself, by accessing this online DOS emulator.

In this blog post we will create a “DOS emulator” but only focusing on the navigation and maintenance of the files and folders structure. We will not implement other functionalities of a DOS.

Files & Folders Tree Structure

On a computer system, files and folders are organised using a Tree structure. For instance, let’s consider the following folder structure:

In MS-DOS, the main commands to navigate through and maintain a folder structure are:

Command	Description
DIR	To list the content of a directory/folder.
CD	To change directory/folder. This can be used to access a subfolder or a parent folder (e.g. cd ..)
MKDIR	To make a new sub-directory/folder.
DEL	To delete a file or a directory/folder. This would delete the content (subfolders and files of the directory)
MOV	To move a folder or a file from one folder to another.
RENAME	To rename a folder or a file.

Class Diagram

We will use a File class and a Folder class to implement this tree structure:

Python Code

We have started the code for you and implemented the CD, DIR, MKDIR, DELETE and RENAME instructions as well as a HELP and a CLS (clear screen) instruction. Your task is to complete this code to create the MOVE instruction and apply it to the Folder class to let the user move a file or folder within a subfolder or the parent folder. For instance to move a file to the parent folder, the user would type the following instruction:
MOVE sea.jpg ..
Or to move a file into a subfolder called “landscapes”:
MOVE sea.jpg landscapes

4-bit counter using D-Type flip-flop circuits

Posted on January 21, 2021 by Administrator Posted in A Level Concepts, Computer Hardware, Computer Science, Computing Concepts, Physical Computing

In this blog post we will design an electronic circuit using logics gates (combined into D-Type flip-flop circuits) to create a 4-bit binary counter. This approach will help us understand how a program counter may be designed within the CPU and automatically incremented for each tick of the clock cycle.

D-Type Flip-Flop Circuits?

A D-Type Flip-Flop circuit is built using four NAND logic gates connected as follows:

We represent a D-Type Flip-Flop Circuit as follows. You can change the input values D and E by clicking on the corresponding buttons below to see the impact on the outputs Q and Q.

A D-Type Flip-Flop Circuit can be used to store 1 bit of information. It has two input pins (Called D (Data) and E (Enabler) and two output pins (Q and Q = NOT Q).

The truth table of a D-Type Flip-Flop circuit is as follows:

When the enabler input E is set to 1, the output Q can be set to the Data input D.
When the enabler input E is set to 0, the output Q cannot be changed. It remains as its previous value. In other word it retains its value. This is why this circuit is used to create memory cells (e.g in the RAM).

You can test this circuit online by clicking on the picture below:

Frequency Division

Another use of a D-Type flip-flop circuit is to perform a frequency division of a signal. For this type of circuit, we will need to use a slight variation to our D-Type Flip Flop by using an edge triggered D-type flip flop. The difference being that the output Q and Q can only change state with the transition of the clock pulse, which means when the Enabler is changing state from 0 to 1. After that, when the enabler is set to 1, the outputs Q and Q remain the same even when the data input D changes.

You can test this circuit online by clicking on the picture below:

By creating a feedback loop (connecting the output Q to the Data pin, D) and applying a regular clock signal to the Enabler pin (E), the resulting signal (pin Q) has the frequency of the input signal divided by two.

This diagram represents both the input and output signals when a feedback loop is applied to a D-Type flip-flop circuit:

You can test this frequency divider circuit by clicking on the picture below:

Designing a 4-bit binary counter

By applying the same circuit in series we can then divide the frequency by 2, 4 and 8. The original signal (clock) and the 3 resulting signals will then produce the desired counting effect:

You can test this circuit with our logic gates circuit simulator by clicking on the picture below:

And here is the full circuit using Logic.ly:

Tagged with: logic gates

Solving a Murder Mystery using Prolog

Posted on January 19, 2021 by Administrator Posted in A Level Concepts, Computer Science, Computing Concepts

In the middle of last winter, eight guests were invited to a luxurious retreat at the Duke of York Grand Hotel. On the last day of their three-day getaway, the guests were free to vacate to their own occupations. Mrs White and Reverend Green did some “gardening” walking alongside the water fountains, Colonel Mustard and Professor Plum played golf (alone though, purposefully avoiding each other). The other guests spent their days either in their rooms or in the lounge, by the log fire. Later on in the afternoon, all the guests were indoors and Colonel Mustard was seen playing cards with Reverend Green and Mrs Peacock.

As the guests were called for dinner, they soon realised that Dr Black was missing. He was later found lying down on the floor of his bedroom. Dr Black had been shot dead using an old fashion revolver. Except from a few muddy footprints at the entrance of his bedroom, there was no other evidence left by the murderer.

Here is the list of all the guests for the weekend and the rooms they were staying in. Note that the hotel consists of twin bedrooms accommodating two guests per room. We also know that three of the guests (Reverend Green, Colonel Mustard and Madame Rose) own a revolver that they brought with them and kept in their room.

– Click on the picture to zoom in/enlarge –

Prolog?

Prolog is a language built around the Logical Paradigm: a declarative approach to problem-solving.

There are only three basic constructs in Prolog: facts, rules, and queries.

A collection of facts and rules is called a knowledge base (or a database) and Prolog programming is all about writing knowledge bases. That is, Prolog programs simply are knowledge bases, collections of facts and rules which describe some collection of relationships that we find interesting.

So how do we use a Prolog program? By posing queries. That is, by asking questions about the information stored in the knowledge base. The computer will automatically find the answer (either True or False) to our queries.

Source: http://www.learnprolognow.org/

Knowledge Base (Facts & Rules)

Let’s see how a detective with some good computer science skills would solve this murder mystery. Their first step would be to write all the facts about the case using the Prolog syntax:

/* Facts */
man(dr_black).
man(reverend_green).
man(colonel_mustard).
man(professor_plum).

woman(mrs_peacock).
woman(madame_rose).
woman(miss_scarlett).
woman(mrs_white).

victim(dr_black).

playing_cards(colonel_mustard).
playing_cards(reverend_green).
playing_cards(mrs_peacock).

gardening(mrs_white).
gardening(reverend_green).

played_golf(professor_plum).
played_golf(colonel_mustard).

smoker(miss_scarlett).
smoker(colonel_mustard).
smoker(mrs_white).
smoker(dr_black).
smoker(mrs_peacock).

room(room_21).
room(room_22).
room(room_23).
room(room_24).
room(room_25).

stay_in(dr_black,room_22).
stay_in(reverend_green,room_24).
stay_in(miss_scarlett,room_21).
stay_in(colonel_mustard,room_24).
stay_in(professor_plum,room_22).
stay_in(mrs_peacock,room_23).
stay_in(madame_rose,room_21).
stay_in(mrs_white,room_23).

owns_revolver(reverend_green).
owns_revolver(colonel_mustard).
owns_revolver(madame_rose).

Then our detective would write some rules and apply them to these facts.

A suspect is either a man or a woman who is not the victim!

#Rule #1: