Time Conversion Algorithm

Posted on February 28, 2018 by Administrator Posted in Computer Science, Python - Beginner, Python Challenges, Solved Challenges

Did You Know?

The 12-hour clock is a time convention in which the 24 hours of the day are divided into two periods: a.m. (from the Latin ante meridiem, meaning “before midday”) and p.m. (post meridiem, “after midday”). Each period consists of 12 hours numbered: 12 (acting as zero), 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, and 11. The 24 hour/day cycle starts at 12 midnight (often indicated as 12 a.m.), runs through 12 noon (often indicated as 12 p.m.), and continues to the midnight at the end of the day.

24-hour to 12-hour clock convertor

Your challenge consists of writing a computer program that asks the end-user to enter a time in the 24-hour format (e.g. 18:36). The program will convert this time in the 12-hour format (e.g. 6:36 PM).

To do so you can base your Python code on the following flowchart:

Python Code

Testing

Once your code is done, complete the following tests to check that your code is working as it should:

Test #	Input Values	Expected Output	Actual Output
#1	06:30	6:30 am
#2	14:25	2:25 pm
#3	00:52	12:52 am
#4	11:59	11:59 am
#5	12:00	12:00 pm
#6	23:59	11:59 pm

Extension

Amend this code to validate the user entry and make sure they enter a time between 00:00 and 23:59 and to display a meaningful error message if not.

Solution...

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

Tagged with: Flowchart

A Level Computer Science – Connect Wall

Posted on February 21, 2018 by Administrator Posted in A Level Concepts, A Level Quiz, Computer Science, Computing Concepts, Quizzes

A Level Connect Wall

Group the cards below in groups of 4 by clicking on each card.

Tagged with: Quiz

GCSE Computer Science – Connect Wall

Posted on February 21, 2018 by Administrator Posted in Computer Science, Computing Concepts, GCSE Concepts, GCSE Quiz, Quizzes

GCSE Connect Wall

Group the cards below in groups of 4 by clicking on each card.

Tagged with: Quiz

Python Turtle Spirograph

Posted on February 16, 2018 by Administrator Posted in Computer Science, Python - Advanced, Python Challenges

In this blog post we will create a spirograph using Python Turtle to draw different types of curves.

Did you know?

A Spirograph is a geometric drawing toy that produces mathematical roulette curves of the variety technically known as hypotrochoids and epitrochoids. It was developed by British engineer Denys Fisher and first sold in 1965.

Examples of patterns created using a spirograph:

HypotrochoidHypocycloidEpicycloidEpitrochoidCycloid

A hypotrochoid is a type of curve traced by a point attached to a circle of radius r rolling around the inside of a fixed circle of radius R, where the point is a distance d from the center of the interior circle.

The parametric equations for a hypotrochoid are:
hypotrochoid-formulas

Where θ (theta) is the angle formed by the horizontal and the center of the rolling circle.

Source: https://en.wikipedia.org/wiki/Hypotrochoid

You can tweak the Python code provided below to change the three key parameters: R, r and d to see their impacts on the hypotrochoid curve.

Find out the properties of an Hypocycloid (https://en.wikipedia.org/wiki/Hypocycloid) and adapt the Python code (see below) to create your own Hypocycloid curves.

The parametric equations for a hypocycloid are:
hypocycloid-formulas

Find out the properties of an Epicycloid (https://en.wikipedia.org/wiki/Epicycloid) and adapt the Python code (see below) to create your own Epicycloid curves.

The parametric equations for an epicycloid are:
epicycloid-formulas

Find out the properties of an Epicycloid (https://en.wikipedia.org/wiki/Epitrochoid) and adapt the Python code (see below) to create your own Epitrochoid curves.

The parametric equations for an epitrochoid are:
epitrochoid-formulas

A cycloid is the curve traced by a point on the rim of a circular wheel as the wheel rolls along a straight line without slipping.

Find out the properties of a Cycloid (https://en.wikipedia.org/wiki/Cycloid) and adapt the Python code (see below) to create your own Cycloid curves.

Python Turtle Spirograph: (Hypotrochoid)

Spirograph Pattern:

By changing some of the parameters (r, R or d) and the number of iterations (steps) we can create more advanced patterns.

Tagged with: Python Turtle

Complementary Colours Tool

Posted on February 14, 2018 by Administrator Posted in Computer Science, HTML, CSS & JavaScript, JavaScript

Two colors are considered complimentary (or opposite) if they produce a neutral color — black, white, or grey — when mixed evenly.

When placed next to each other, a colour and its complimentary colour create the strongest contrast that can be created with this initial colour.

RGB colours code consists of 3 values to identify a unique colour:

Red Value: A number between 0 and 255
Green Value: A number between 0 and 255
Blue Value: A number between 0 and 255

For instance:

(255,0,0) is the colour code for red,
(255,0,255) is the colour code for magenta,
(100,0,100) is the colour code for a dark purple colour,
(255,255,255) is the colour code for white,
(0,0,0) is the colour code for black,

Let’s consider a colour with a colour code of (Red, Green, Blue).
The colour code for its opposite colour will be (255 – Red, 255 – Green, 255 – Blue)

Colour (Red, Green, Blue)
Opposite Colour (255 – Red, 255 – Green, 255 – Blue)

Your Challenge

Use the above formula to complete this codepen where the user can pick a colour (by inputting the RGB colour code) to preview this colour. The code should calculate the RGB code of the opposite colour and use it to preview this opposite colour code.

See the Pen Opposite Colours Tool by 101 Computing (@101Computing) on CodePen.

Extension Task

Complete this code to also calculate and display the colour codes of both colours using an hexadecimal colour code.

Python Turtle – Morphing Algorithm

Posted on February 9, 2018 by Administrator Posted in Computer Science, Python - Advanced, Python Challenges, Solved Challenges

Tweening/Morphing effects are often used in Computer Animations to change the shape of an object by morphing an object from one shape into another.

In tweening, key frames are provided and “in-between” frames are calculated to make a smooth looking animation.

In this blog post we will implement a tweening algorithm to morph a letter of the alphabet (e.g. “A” into another letter “Z”) using a linear interpolation.

We will consider a letter as being a list of connected nodes (dots) where each dot has its own set of (x,y) coordinates.

Linear Interpolation Formulas:

Using the following linear interpolation formulas we can calculate the (x,y) coordinates of each dot for any “in-between” frame.

x(t) = x_A + (x_Z – x_A) * t / 10

y(t) = y_A + (y_Z – y_A) * t / 10

“t” represents the time: in other words the frame number (e.g. between 0 and 10)
(x_A,y_A) the coordinates of a node/dot from the starting letter (e.g. A)
(x_Z,y_Z) the coordinates of a node/dot from the ending letter (e.g. Z)

Using these formulas we can see that:

x(0) = x_A
y(0) = y_A

x(10) = x_Z
y(10) = y_Z

Our tweening algorithm will need to apply these formulas to each node of the letter.

Python Code (using Python Turtle)

Your Task #1

Tweak this code to create a tweening animation going through all the letters of your firstname.
(e.g. J -> A -> M -> E -> S).

Your Task #2

Tweak this code to create an animated count down timer counting from 9 to 0.
(e.g. 9 -> 8 -> 7 -> 6 -> 5 -> 4 -> 3 -> 2 -> 1 -> 0).

Solution...

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

Machine Learning – Top Trumps Game

Posted on February 6, 2018 by Administrator Posted in A Level Concepts, Algorithms, Computer Science, Computing Concepts, HTML, CSS & JavaScript, JavaScript

The purpose of this post is to demonstrate a basic example of how machine learning works.

In this example, the computer learns how to play a game of Top Trumps more effectively to increase its chance of winning the game.

It does so by running a learning sequence. During this learning sequence its machine learning algorithm pick two random cards from the deck and compare them against a random criteria.

Based on which card wins the round, it updates its knowledge base accordingly. By repeating this process many times (number of iterations), the algorithm records in its knowledge base statistics for each category of each card. (Probability of winning the round)

The algorithm hence progressively learns which criteria has the highest probability of winning and records this information for each card of the deck.

These probabilities become more accurate when you increase the number of iterations of the learning sequence.

Use the buttons provided in the code pen below to show the impact of the learning phase on the knowledge base.

See the Pen Machine Learning Top Trumps by 101 Computing (@101Computing) on CodePen.

Machine Learning?

Let’s consider the following definition of Machine Learning:

“A computer program is said to learn from experience E with respect to some task T and some performance measure P, if its performance on T, as measured by P, improves with experience E.” — Tom Mitchell, Carnegie Mellon University

Let’s apply this defintion to our Top Trumps Machine Learning algorithm:

E: (The Experience/learning sequence): The experience consists of randomly picking two cards and comparing them against a criteria to see which card would win the round.
T: (The Task): Playing a full game of Top Trumps against an end-user.
P: (The Performance Measure): The probability of winning the game.

In our example, the probability (P) of winning a game of Top Trumps (T) increases with the number of iterations of the learning sequence (Experience E).

So we effectively have a machine learning algorithm.

Obviously, with a fixed data sets of 9 cards and 4 criteria per card, the learning is limited. More complex scenarios use a similar approach with larger data sets which are often open/limitless and where the computer can constantly learn and improve the accuracy of its knowledge base by either analysing existing data sets or populating new data by interacting with real end-users/human beings.

Next Step?

To complete this algorithm, the next step would be to implement the playing phase, where the computer should use its knowledge base to play against an end-user.

Heuristic Approaches to Problem Solving

Posted on February 5, 2018 by Administrator Posted in A Level Concepts, Algorithms, Computer Science, Computing Concepts

“A heuristic technique, often called simply a heuristic, is any approach to problem solving, learning, or discovery that employs a practical method not guaranteed to be optimal or perfect, but sufficient for the immediate goals. Where finding an optimal solution is impossible or impractical, heuristic methods can be used to speed up the process of finding a satisfactory solution. Heuristics can be mental shortcuts that ease the cognitive load of making a decision. Examples of this method include using a rule of thumb, an educated guess, an intuitive judgement, guesstimate, stereotyping, profiling, or common sense.” (Source: Wikipedia)

“In computer science, a heuristic is a technique designed for solving a problem more quickly when classic methods are too slow, or for finding an approximate solution when classic methods fail to find any exact solution. This is achieved by trading optimality, completeness, accuracy, or precision for speed. In a way, it can be considered a shortcut.” (Source: Wikipedia)

The objective of a heuristic algorithm is to apply a rule of thumb approach to produce a solution in a reasonable time frame that is good enough for solving the problem at hand. There is no guarantee that the solution found will be the most accurate or optimal solution for the given problem. We often refer the solution as “good enough” in most cases.

Heuristic Algorithms?

Heuristic Algorithms can be found in:

Artificial Intelligence

E.g. When a computer algorithm plays a game of Chess (e.g. Deep Blue) or a game of Go (e.g. AlphaGo), the computer cannot investigate every single move that can be played. Instead it will apply a few rules of thumb to quickly discard some moves while focusing on key moves that are more likely to lead to a victory.

Language recognition

When analysing the meaning of a user input, for instance when a user asks a question on a search engine or interacts with a Google Home or Amazon Echo device, an algorithm tries to make sense of the user inputs. Word associations, analysis of context, previous searches history and current trends/search engine statistics can be used in a heuristic algorithm to speed up the search process.

Big Data Analysis

When there are large amounts of data to analyse. This is the case for search engines to return search results very efficiently, profiling algorithms which can be used by a marketing department to identify members of a target audience and their behaviours, data analysis in scientific research (e.g. medicine to identify cause/effect correlations between large data sets).

Shortest Path Algorithms

used by GPS systems and self-driving cars also use a heuristic approach to decide on the best route to go from A to Z (e.g. A* Search Algorithm). More advanced algorithms can also take into consideration a range of factors including the type of roads, the speed limits, live traffic data, etc. which can result in extremely complex algorithms.

Machine Learning

Artificial Intelligence algorithms based on machine learning where the computer builds up a knowledge base from previous experiences is another application of heuristic algorithms. In this case the algorithm uses a self-maintained knowledge base to inform decisions and make “educated guesses” based on previous experiences.

Let’s investigate a few basic examples where a heuristic algorithm can be used:

Noughts & CrossesGame of ChessTop TrumpsLanguage RecognitionShortest Path Algorithms

To help the computer make a decision as to where to place a token on a 3×3 noughts and crosses grid, a basic heuristic algorithm should be based on the rule of thumb that some cells of the grid are more likely to lead to a win:
heuristic-noughts-and-crosses

Based on this approach, can you think of how a similar approach could be used for an algorithm to play:

Othello (a.k.a. Reversi Game)
A Battleship game?
Rock/Paper/Scissors?

When playing a game of chess, expert players can “see” several moves ahead. It would be tempting to design an algorithm that could investigate every single possible move that players can make and investigate the impacts of such moves on the outcome of the game. However such an algorithm would have to investigate far too many possible moves and would quickly become too slow and too demanding in terms of memory resources in order to perform effectively.

It is hence essential to use a heuristic approach to quickly discard some moves which would most likely lead to a defeat while focusing on moves that would seem to be a good step towards a win!

heuristic-chess-move

Let’s consider the above scenario when investigating all the possible moves for this white pawn. Can the computer make a quick decision as to what would most likely be the best option?

Heuristic approaches do not always give you the best solution. Can you explain how this could be the case with this scenario?

Sometimes your algorithm need to collect or analyse data before applying heuristic to make a decision. This can be done by providing the computer with some data or by implementing an algorithm based on machine learning.

For instance in a game of Top Trumps, if your algorithm knows the average value of each card for each category, it will be able to select the criteria which is most likely going to win the round.

Alternatively, a machine learning algorithm could play the game and record and update statistics after playing each card to progressively learn which criteria is more likely to win the round for each card in the deck.
You can investigate how machine learning can be used in a game of Top Trumps by reading this blog post.

Heuristic methods can be used when developing algorithms which try to understand what the user is saying, or asking for. For instance, by looking for words associations, an algorithm can narrow down the meaning of words especially when a word can have two different meanings:

heuristic-raspberry

e.g. When using Google search a user types: “Raspeberry Pi Hardware” We can deduct that in this case Raspberry has nothing to do with the piece of fruit, so there is no need to give results on healthy eating, cooking recipes or grocery stores…

However if the user searches for “Raspeberry Pie ingredients”, we can deduct that the user is searching for a recipe and is less likely to be interested in programming blogs or computer hardware online shops.

Short Path Algorithms used by GPS systems and self-driving cars also use a heuristic approach to decide on the best route to go from A to Z. This is for instance the case for the A* Search algorithm which takes into consideration the distance as the crow flies between two nodes to decide which paths to explore first and hence more effectively find the shortest path between two nodes.

signs-distance

You can compare two different algorithms used to find the shortest route from two nodes of a graph:

A* Search Algorithm

Posted on February 1, 2018 by Administrator Posted in A Level Concepts, A Level Quiz, Algorithms, Computer Science, Computing Concepts, Solved Challenges

The A* Search algorithm (pronounced “A star”) is an alternative to the Dijkstra’s Shortest Path algorithm. It is used to find the shortest path between two nodes of a weighted graph. The A* Search algorithm performs better than the Dijkstra’s algorithm because of its use of heuristics.

Before investigating this algorithm make sure you are familiar with the terminology used when describing Graphs in Computer Science.

Let’s decompose the A* Search algorithm step by step using the example provided below. (Use the tabs below to progress step by step).

Note that, in this graph, the heuristic we will use is the straight line distance (“as the crow flies”) between a node and the end node (Z). This distance will always be the shortest distance between two points, a distance that cannot be reduced whatever path you follow to reach node Z.

GraphStep 1234567

Start by setting the starting node (A) as the current node.

Check all the nodes connected to A and update their “Shortest Distance from A” and set their “previous node” to “A”.
Update their total distance by adding the shortest distance from A and the heuristic distance to Z.

Set the current node (A) to “visited” and use the unvisited node with the smallest total distance as the current node (e.g. in this case: Node C).
Check all unvisited nodes connected to the current node and add the distance from A to C to all distances from the connected nodes. Replace their values only if the new distance is lower than the previous one.

C -> D: 3 + 7 = 10 < ∞ – Change Node D
C -> E: 3 + 10 = 13 < ∞ – Change Node E

The next current node (unvisited node with the shortest total distance) could be either node B or node D. Let’s use node B.

Check all unvisited nodes connected to the current node (B) and add the distance from A to B to all distances from the connected nodes. Replace their values only if the new distance is lower than the previous one.

B -> E: 4 + 12 = 16 > 13 – Do not change Node E
B -> F: 4 + 5 = 9 < ∞ – Change Node F

The next current node (unvisited node with the shortest total distance) is D.

Check all unvisited nodes connected to the current node (D) and add the distance from A to D to all distances from the connected nodes. Replace their values only if the new distance is lower than the previous one.

D -> E: 10 + 2 = 12 < 13 – Change Node E

The next current node (unvisited node with the shortest total distance) is E.

Check all unvisited nodes connected to the current node (E) and add the distance from A to E to all distances from the connected nodes. Replace their values only if the new distance is lower than the previous one.

E -> Z: 12 + 5 = 17 < ∞ – Change Node Z

We found a path from A to Z, but is it the shortest one?

Check all unvisited nodes. In this example, there is only one unvisited node (F). However its total distance (20) is already greater than the distance we have from A to Z (17) so there is no need to visit node F as it will not lead to a shorter path.

We found the shortest path from A to Z.
Read the path from Z to A using the previous node column:
Z > E > D > C > A
So the Shortest Path is:
A – C – D – E – Z with a length of 17

Your Task

Graph #1Graph #2

Apply the steps of the A* Search algorithm to find the shortest path from A to Z using the following graph:

Node	Status	Shortest Distance from A	Heurisitic Distance to Z	Total Distance	Previous Node
A			21
B			14
C			18
D			18
E			5
F			8
Z			0

Shortest Path?

Length?

Apply the steps of the A* Search algorithm to find the shortest path from A to Z using the following graph:

Node	Status	Shortest Distance from A	Heurisitic Distance to Z	Total Distance	Previous Node
A			11
B			8
C			8
D			4
E			2
Z			0

Shortest Path?

Length?

Solution...

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

Tagged with: Algorithm, Graph

Dijkstra’s Shortest Path Algorithm

Posted on January 31, 2018 by Administrator Posted in A Level Concepts, A Level Quiz, Algorithms, Computer Science, Computing Concepts, Solved Challenges

Dijkstra’s Shortest Path Algorithm is an algorithm used to find the shortest path between two nodes of a weighted graph.

Before investigating this algorithm make sure you are familiar with the terminology used when describing Graphs in Computer Science.

Let’s decompose the Dijkstra’s Shortest Path Algorithm step by step using the following example: (Use the tabs below to progress step by step).

GraphStep 123456789

Start by setting the starting node (A) as the current node.

Check all the nodes connected to A and update their “Distance from A” and set their “previous node” to “A”.

Set the current node (A) to “visited” and use the closest unvisited node to A as the current node (e.g. in this case: Node C).

Check all unvisited nodes connected to the current node and add the distance from A to C to all distances from the connected nodes. Replace their values only if the new distance is lower than the previous one.

C -> B: 2 + 1 = 3 < 4 – Change Node B
C -> D: 2 + 8 = 10 < ∞ – Change Node D
C -> E: 2 + 10 = 12 < ∞ – Change Node E

Set the current node C status to Visited.
We then repeat the same process always picking the closest unvisited node to A as the current node.
In this case node B becomes the current node.

B -> D 3+5 = 8 < 10 – Change Node D

Next “Current Node” will be D as it has the shortest distance from A amongst all unvisited nodes.

D -> E 8+2 = 10 < 12 – Change Node E
D -> Z 8+6 = 14 < ∞ – Change Node Z

We found a path from A to Z but it may not be the shortest one yet. So we need to carry on the process.

Next “Current Node”: E

E -> Z 10+5 = 15 > 14 – We do not change node Z.

We found the shortest path from A to Z.
Read the path from Z to A using the previous node column:
Z > D > B > C > A
So the Shortest Path is:
A – C – B – D – Z with a length of 14

Your Task

Graph #1Graph #2

Apply the steps of the Dijkstra’s Algorithm to find the shortest path from A to Z using the following graph:
Dijkstra-Algorithm-Graph

Node	Status	Shortest Distance from A	Previous Node
A
B
C
D
E
F
Z

Shortest Path?

Length?

Apply the steps of the Dijkstra’s Algorithm to find the shortest path from A to Z using the following graph:
Graph-Dijkstra-Algorithm

Node	Status	Shortest Distance from A	Previous Node
A
B
C
D
E
F
Z

Shortest Path?

Length?

Solution...

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

Tagged with: Algoithm, Graph

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

Did You Know?

24-hour to 12-hour clock convertor

Python Code

Testing

Extension

Solution...

A Level Connect Wall

GCSE Connect Wall

Did you know?

Python Turtle Spirograph: (Hypotrochoid)

Spirograph Pattern:

Your Challenge

Extension Task

Linear Interpolation Formulas:

Python Code (using Python Turtle)

Your Task #1

Your Task #2

Solution...

Machine Learning?

Next Step?

Heuristic Algorithms?

Your Task

Solution...

Your Task

Solution...

Our Latest Book

Recent Posts