More results...

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

The Honeycomb Challenge

honeycomb-pattern-300Honeycomb is a structure of hexagonal cavities (cells of wax), made by bees to store honey and eggs.

In this challenge we will use a set of iterative algorithms to draw a honeycomb pattern.

First, we will create a function to draw a single hexagonal cavity. Our function called drawCavity() will take three parameters:

  • x – the x coordinates to position the hexagon.
  • y – the x coordinates to position the hexagon.
  • edgeLength – the length in pixels of an edge of the hexagon.

honeycomb-cavity

We will then need to use some nested for loops in order to tessellate the hexagonal cell to recreate a 2D honeycomb pattern.
honeycomb

Python Code


We have started the code for you, using Python Turtle. You will need to complete this code further to complete the pattern fully.

unlock-access

Solution...

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

Sudoku Generator Algorithm

Your task is to design an algorithm used to create a Sudoku Grid. The generated Sudoku grid should have enough clues (numbers in cells) to be solvable resulting in a unique solution.

Sudoku?


A Sudoku game is number-placement puzzle. The objective is to fill a 9×9 grid with digits so that each column, each row, and each of the nine 3×3 subgrids that compose the grid (also called “boxes”, “blocks”, or “regions”) contain all of the digits from 1 to 9. The puzzle setter provides a partially completed grid, which for a well-posed puzzle has a single solution.

Our aim for this challenge is not to generate a Sudoku solver algorithm but instead to create an algorithm to be used by a puzzle setter to produce a well-posed Sudoku grid: a grid with a unique solution. For instance the output of our algorithm could be a grid such as this one:

sudoku-grid

Did You Know?

Sudoku fanatics have long claimed that the smallest number of starting clues a Sudoku puzzle can contain is 17. There are effectively numerous examples of grids with 17 clues that have a unique solution but we have never found a well-posed grid with only 16 clues. This suggests that the minimum number of clues to provide in a grid is 17.

This key fact might be useful to help you solve this challenge more effectively.

Sudoku Solver Algorithm


Your Sudoku Generator algorithm may need to use a Sudoku Solver Algorithm in order to test whether a generated grid is solvable and to check that it only gives a single solution.

The most common type of Sudoku Solver Algorithm is based on a backtracking algorithm used to investigate all possible solutions of a given grid.

You can find an example of such an algorithm by investigating the code provided in this Python Challenge: Sudoku Solver using a Backtracking Algorithm

Extension Task:


Sudoku puzzles are often given a difficulty level such as “Beginner – Intermediate – Advanced – Expert”.

How could your algorithm be adapted to estimate the difficulty level of a Sudoku grid?
Should different algorithms be used to generate Sudoku grids for a specific difficulty level?

Solution


Our solution is based on 5 steps:

  1. Generate a full grid of numbers (fully filled in). This step is more complex as it seems as we cannot just randomly generate numbers to fill in the grid. We have to make sure that these numbers are positioned on the grid following the Sudoku rules. To do so will use a sudoku solver algorithm (backtracking algorithm) that we will apply to an empty grid. We will add a random element to this solver algorithm to make sure that a new grid is generated every time we run it.
  2. From our full grid, we will then remove 1 value at a time.
  3. Each time a value is removed we will apply a sudoku solver algorithm to see if the grid can still be solved and to count the number of solutions it leads to.
  4. If the resulting grid only has one solution we can carry on the process from step 2. If not we will have to put the value we took away back in the grid.
  5. We can repeat the same process (from step 2) several times using a different value each time to try to remove additional numbers, resulting in a more difficult grid to solve. The number of attempts we will use to go through this process will have an impact on the difficulty level of the resulting grid.

Full Python Code


unlock-access

Solution...

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

Chemical Elements Quiz

chemical-elementsThe aim of this challenge is to create a quiz based on the list of chemical elements of the periodic table based on the following requirements:

  • The quiz will include 10 questions.
  • Each question will display the name of an element (e.g. Aluminum) and ask the user to enter the symbol of this element (e.g. Al).
  • For each correct answer the user will score 2 points and for each incorrect answer, the user will lose 1 point.
  • The score cannot go in the negative values.
  • A feedback with the correct answer will be given after each question.
  • The final score (out of 20) will be displayed at the end of the quiz.

Python Dictionary


A Python dictionary is a mapping of unique keys to values. Each key is separated from its value by a colon (:), the items are separated by commas (,), and the whole set of key/value pairs is enclosed in curly braces {}.

For this challenge, we will use a dictionary data structure to store all the chemical elements of the periodic table using the symbol of each element as the key and the name of the element as the value. e.g.

elements = {"Ac":"Actinium","Ag":"Silver","Al":"Aluminum","Am":"Americium", ...}

Each value of a dictionary can be accessed by providing its key as follows (notice the use of square brackets [] to access a value from a dictionary):

print(elements["Al"])

Flowchart


To help you complete this challenge, we have created the flowchart of this quiz algorithm.
chemical-element-quiz-flowchart

Python Quiz


We have started the code for the Chemical Elements Quiz and created the Python dictionary containing all 118 chemical elements of the periodic table.

Your task is to complete the code to implement the full quiz based on the above mentioned requirements.

unlock-access

Solution...

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

Airport Code Lookup Check

airport-signIn this challenge we will implement a small Python program to:

  • Ask the user to enter a 3-letter airport code (e.g. LHR) for one of the top 20 busiest airports in the world.
  • Output the full name of the airport matching the code.

For this program we will use the official codes from the International Air Transport Association (IATA).

To make our program more robust, we will implement a couple of validation checks used to check if an airport code is valid. Our validation routine will:

  • Automatically convert the user input (airport code) to uppercase
  • Ensure the airport code provided is exactly 3 characters long (Length Check)
  • Ensure the airport code provided is one of the top 20 airport codes (Lookup Check)

To implement our lookup check we will use a dictionary data structure containing all 20 airport codes and their full names.

A dictionary is a data structure which contains an unordered list of key/value pairs. In our examples the keys are the airport codes, the values are the full airport names. e.g.

airports = {"ATL":"Hartsfield–Jackson Atlanta International Airport",
            "PEK":"Beijing Capital International Airport",
            "DXB":"Dubai International Airport",
            "LAX":"Los Angeles International Airport",
            ...
           }

Notice the use of curly brackets in Python when creating a dictionary data structure.

With this dictionary we can then retrieve a single value by providing a key. e.g.

print(airports["DXB"])

The above line of code would output “Dubai International Airport” on screen.

We can also check if a key exists in a dictionary by using the keyword in. e.g.

if "DXB" in airports:
      print(airports["DXB"])
else:
      print("Airport code not recognised")

Python Code

Check the code below to validate a 3-letter airport code using both a length check and a lookup check.

Your Task

Your task is to create another dictionary called airlines which will contains twelve of the main international airlines with their 2-letter codes as follows:

Airline Code Airline
AA AMERICAN AIRLINES
AC AIR CANADA
AF AIR FRANCE
AI AIR INDIA
BA BRITISH AIRWAYS
DL DELTA AIR LINES
CA AIR CHINA
JL JAPAN AIRLINES
MS EGYPTAIR
QF QANTAS AIRWAYS
SQ SINGAPORE AIRLINES
UA UNITED AIRLINES

Your program should ask what airlines the end-user is flying with (using a 2 letter code input) and use the airlines dictionary to validate the user input and retrieve and display the full name of the airline company.

unlock-access

Solution...

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

My Class Register

class-register-clipboardFor this challenge we will create a program to be used by a teacher at a start of a lesson to take the register. The program will go through a class list and for each pupil in the list, will ask the teacher if the pupils is present (y) or absent (n).

The program will then output the total number of students in the class, the number of students present and the number of students who are absent.

Flowchart / Algorithm


We have designed the following flowchart for this program. This algorithm uses a list called pupils used to store the names of all the students in the class.
class-register-flowchart

Python Code


Your tasks is to type the Python code following the steps identified in the above flowchart.

unlock-access

Solution...

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

Pentagram Challenge

pentagon-circumcircleA polygon is a plane shape (2D) with straight lines. It consists of vertices and edges.

A polygon is regular when all angles are equal and all sides are equal. For instance a regular pentagon consists of 5 vertices and 5 edges of equal size. The vertices of a regular pentagon are equally spread on a circle. This outside circle is called a circumcircle, and it connects all vertices (corner points) of the polygon. The radius of the circumcircle is also the radius of the polygon. We can use the trigonometric formulas to work out the (x,y) coordinates of each vertex of a regular pentagon. (See picture on the right).

Using this approach, we can use a Python script to calculate the (x,y) coordinates of the 5 vertices of a regular pentagon and store them in a list of [x,y] sub-lists.

pentagon=[]
R = 150
for n in range(0,5):
  x = R*math.cos(math.radians(90+n*72))
  y = R*math.sin(math.radians(90+n*72))
  pentagon.append([x,y])

Star Shapes


pentagramA pentagram is a polygon that looks like a 5-pointed star. The outer vertices (points of the stars) form a regular pentagon. The inner vertices of the star also form a smaller “inner” regular pentagon.

We can hence use a similar approach to calculate the (x,y) coordinates of both “outer” and “inner” vertices of our pentagram.
pentagram-coordinates

Python Turtle


We have completed the code to calculate the coordinates of a regular pentagon (using the code provided above) and have created a function called drawPolygon() that uses Python Turtle to draw a polygon on screen.

Your Task


Adapt the above Python code to calculate the coordinates of all the vertices of a pentagram (star shape) and draw the pentagram on screen.

The output of your program should be as follows:
pentagram-star-shape

Extension Task


Use the shoelace algorithm to calculate the area of your pentagram.
unlock-access

Solution...

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

The Shoelace Algorithm

shoelace-formula-polygonThe shoelace formula or shoelace algorithm is a mathematical algorithm to determine the area of a simple polygon whose vertices are described by their Cartesian coordinates in the plane.

The method consists of cross-multiplying corresponding coordinates of the different vertices of a polygon to find its area. It is called the shoelace formula because of the constant cross-multiplying for the coordinates making up the polygon, like tying shoelaces. (See table below). This algorithm has applications in 2D and 3D computer graphics graphics, in surveying or in forestry, among other areas.

the-shoelace-formula

To apply the shoelace algorithm you will need to:

  • List all the vertices in anticlockwise order. (e.g. A,B,C,D,E) in a table, and note the x and y coordinates in two separate columns of the table,
  • Calculate the sum of multiplying each x coordinate with the y coordinate in the row below (wrapping around back to the first line when you reach the bottom of the table),
  • Calculate the sum of multiplying each y coordinate with the x coordinate in the row below (wrapping around back to the first line when you reach the bottom of the table),
  • Subtract the second sum from the first, get the absolute value (Absolute dfference |sum1-sum2|,
  • Divide the resulting value by 2 to get the actual area of the polygon.

shoelace-table

the-shoelace-formula-ABCDE

The Shoelace Algorithm using Python:


To implement the shoelace algorithm we will define a polygon as a list of vertices, listed in anticlockwise order. Each vertex will be a list of 2 values: its x and y coordinates.

Alternative Approach


The above algorithm requires the computer to calculate two different sums that could potentially lead to very high numbers. On occasion these numbers could generate an overflow error if they reach the maximum capacity of an integer value.

The Shoelace formula can be rewritten as follows:
the-shoelace-formula-v2

In this case the python code given above can be adapted to reflect this new formula and reduce the risk of creating an overflow error.

Your task is to tweak the above code to base the code on this alternative Shoelace formula.

unlock-access

Solution...

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

Sorting Algorithms using Python

sorting-algorithms-pythonComputers are often used to sort large amounts of data. Though this may seem like a simple task to complete, a lot of research has focused on finding the most effective algorithms to sort large amount of data.

Four of the most basic algorithms to sort a set of data are:

  • Insertion Sort Algorithm,
  • Bubble Sort Algorithm,
  • Selection Sort Algorithm,
  • Merge Sort Algorithm.
  • We have implemented each these algorithms below, using Python to sort a set list of values.

    Insertion SortBubble SortSelection SortMerge Sort

    Insertion Sort


    The insertion sort is an iterative algorithm (using nested loops).


    Bubble Sort


    The Bubble sort is an iterative algorithm (using nested loops).


    Selection Sort


    The selection sort is an iterative algorithm (using nested loops).


    Merge Sort


    The merge sort algorithm uses a recursive function.


Merge Sort Algorithm

Computers are often used to process large amounts of data. Some of the tasks they can be used for is to sort data sets in order, e.g. numerical order or alphabetical order. Though this may seem like a simple task to complete, a lot of research has focused on finding the most effective sorting algorithm, especially when working on large data sets.

One of the key sorting algorithms is called a merge sort and is based on a divide and conquer approach.

Merge-Sort-Algorithm

Your Task


Practise sorting lists of numbers using a Merge sort: (Open in new window)

Tagged with:

Bubble Sort vs. Insertion Sort

sorting-algorithmsComputers are often used to sort large amounts of data (e.g. numerical order or alphabetical order). Though this may seem like a simple task to complete, a lot of research has focused on finding the most effective approach to sort data.

Two of the most basic algorithms used to sort data are the Bubble Sort Algorithm, and the Insertion Sort Algorithm.


Insertion-sort-1-9

Insertion Sort Algorithm


To start with, the algorithm considers the first value of a list as a sorted sub-list (of one value to start with). This iterative algorithm then checks each value in the remaining list of values one by one. It inserts the value into the sorted sub-list of the data set in the correct position, moving higher ranked elements up as necessary.

This algorithm is not always very efficient and is mostly recommended when sorting a small lists of values or a list that is already almost sorted.

You can check our Python implementation of this algorithm on this blog post.


Bubble-sort-1-9

Bubble Sort Algorithm


The algorithm starts at the beginning of the data set. It compares the first two value, and if the first is greater than the second, it swaps them. It continues doing this for each pair of adjacent values to the end of the data set. It then starts again with the first two elements, repeating until no swaps have occurred on the last pass.

This algorithm is particularly useful when you need to find the top x values of a list.

You can check our Python implementation of this algorithm on this blog post.


Your Task


Practise sorting lists of numbers using both the Insertion sort and the Bubble sort algorithms using the two tabs below:
Insertion SortBubble Sort
Tagged with: