Bracket Validator

Posted on December 14, 2020 by Administrator Posted in Computer Science, Python - Advanced, Python Challenges

The aim of this Python Challenge is to write a script to validate an arithmetic expression by checking that it has a valid sequence of opening and closing brackets.

Let’s consider the following arithmetic expressions to decide whether they contain a valid or invalid combination of brackets:

Arithmetic Expression	Valid/Invalid?	Justification
(5+2)/3	Valid
(((5+2)/3)-1)*4	Valid
(5+2)*(3+4)	Valid
(5+2	Invalid	Missing closing bracket
(5+2)*)3+4(	Invalid	Invalid use of brackets
(5+2)/3)-1	Invalid	Missing an opening bracket

Opening & Closing Brackets Count

In order to validate whether an expression is valid or not, we could count the number of opening brackets and the number of closing brackets and see if both numbers are the same. Though this would detect a lot of invalid expressions, not all invalid expressions would be detected. For instance, using this approach, the expression (5+2)*)3+4( would appear valid as it contains 2 opening brackets and 2 closing brackets.

Using a stack

A more effective approach is to parse the expression one character at a time and every time an opening bracket is met, the bracket is pushed into a stack. Every time a closing bracket is found, we pop the last opening bracket from the stack (if when a closing bracket is met, the stack is empty then the expression is invalid). Once all characters of the expression have been checked, the stack should be empty. If not the expression is invalid.

Here is the implementation of this approach in Python:

Using multiple types of brackets

More complex expressions may use different types of brackets such as square brackets [], curly brackets {} and parentheses (). We can adapt our script to validate an expression by making sure that when a closing bracket is found, the algorithm checks that it is of the same type as the last bracket that has been pushed into the stack.

Proportions and cross products

Posted on December 11, 2020 by Administrator Posted in Computer Science, Python - Intermediate, Python Challenges, Solved Challenges

A proportion is simply a statement that two ratios are equal. The following are examples of proportions:

1/4 = 25/100
8/24 = 1/3
40/60 = 2/3

Proportions are often use in Maths to simplify a fraction or to represent a fraction as a percentage.

In order two find out if two fractions are equal, we can use one of the following three methods:

Calculate and compare their decimal values: e.g. 25/100 = 0.25 and 1/4 = 0.25 so 25/100 = 1/4
Simplify both fractions: e.g. 75/100 = 3/4 and 18/24 = 3/4 so 75/100 = 18/24
Compare cross products: e.g. 3 x 6 = 2 x 9 so 2/6 = 3/9

Cross Products

You can compare two fractions to find out if they are equal or not if their cross products are equal:

Python Challenge

Your aim is to write a Python program that will check if two fractions are equal or not using the cross products approach. The program will take 4 inputs: the numerator and denominator of both fractions.
It will then compare the cross products to decide and output if the two fractions are equal or not.

You will not to complete the following code:

Test Plan

Complete the following tests to check that your code is working as expected:

Test #	Input Values	Expected Output	Actual Output
#1	Fraction #1: 4/6 Fraction #2: 20/30	These fractions are equal.
#2	Fraction #1: 4/6 Fraction #2: 20/40	These fractions are not equal.
#3	Fraction #1: 75/100 Fraction #2: 3/4	These fractions are equal.
#4	Fraction #1: 1/3 Fraction #2: 30/100	These fractions are not equal.

Solution...

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

Linked Lists

Posted on December 4, 2020 by Administrator Posted in A Level Concepts, Computer Science, Computing Concepts

A linked-list is a dynamic data structure used in computer science. It consists of a collection of nodes where each node contains a piece of data (value) and a pointer (memory location) to the next node in the list.

The first node of the list is called the head, whereas the last node is the tail.

The following tables represent how the above linked list is stored in memory:

Memory Address	Node Value	Pointer
0	21	1
1	35	2
2	47	3
3	89	Null
…	…	…

The linked-list data structure is more flexible than the array data structure as it allows for efficient insertion or removal of elements from any position in the sequence.

Inserting a value in a linked list:

Let’s see how we can add the value 52 in the correct (sorted) position:

As you cans see on the table below, we have been able to add the value 52 to the linked list, in the desired position, without the need to move any other value in memory. The pointer of the previous node in the list has been updated accordingly.

Memory Address	Node Value	Pointer
0	21	1
1	35	2
2	47	4
3	89	Null
4	52	3
…	…	…

Though the data does not appear to be sorted in memory, the use of pointers enables the linked-list to have its own sequence. This makes the process of inserting and removing values from a linked list far more efficient as it does not require other values to be moved around in memory (a fairly slow process when manipulating a large amount of data).

Removing a value from a linked list:

Let’s now remove value 35 from the list:

Memory Address	Node Value	Pointer
0	21	2
1	35	2
2	47	4
3	89	Null
4	52	3
…	…	…

Circular list

Imagine all the children in the “pass the parcel” game. The parcel is passed around the children and when the last child receives the parcel, they then pass it on back to the first child in the list.

A circular list is when the pointer of the tail node points towards the head node of the linked list.

Memory Address	Node Value	Pointer
0	21	1
1	35	2
2	47	3
3	89	0
…	…	…

Double linked list

A double linked list uses two pointers per node, one pointer pointing towards the next node in the list and one pointer pointing towards the previous node in the list. It makes it easier to “navigate through” the list in both directions!

Memory Address	Node Value	Previous Node Pointer	Next Node Pointer
0	21	Null	1
1	35	0	2
2	47	1	3
3	89	2	Null
…	…	…	…

Circular Double linked list

A Circular double linked list is when the tail node points back to the head node and vice versa:

Memory Address	Node Value	Previous Node Pointer	Next Node Pointer
0	21	3	1
1	35	0	2
2	47	1	3
3	89	2	0
…	…	…	…

XOR Encryption Algorithm

Posted on November 28, 2020 by Administrator Posted in Algorithms, Computer Science, Computing Concepts, Cryptography, Python - Intermediate, Python Challenges

The XOR Encryption algorithm is a very effective yet easy to implement method of symmetric encryption. Due to its effectiveness and simplicity, the XOR Encryption is an extremely common component used in more complex encryption algorithms used nowadays.

The XOR encryption algorithm is an example of symmetric encryption where the same key is used to both encrypt and decrypt a message.

Symmetric Encryption: The same cryptographic key is used both to encrypt and decrypt messages.

The XOR Encryption algorithm is based on applying an XOR mask using the plaintext and a key:

Reapplying the same XOR mask (using the same key) to the cipher text outputs the original plain text. The following truth table (based on the XOR truth table) demonstrates how the encryption process works.

P (Plain text)	K (Key)	C (Cipher) = P XOR K	K (Key)	P (Plain Text) = C XOR K
0	0	0	0	0
1	0	1	0	1
0	1	1	1	0
1	1	0	1	1

The XOR encryption algorithm can be applied to any digital/binary information, included text based information encoded using the 8-bit ASCII code. In this case the encryption key can be expressed as a string of characters.

By itself, the XOR encryption can be very robust if:

It is based on a long key that will not repeat itself. (e.g. a key that contains as many bits/characters as the plaintext)
A new key is randomly generated for any new communication.
The key is kept secret by both the sender and the receiver.

When a large quantity of text is to be encrypted, a shorter repeating encryption key is used to match the length of the plain text. However re-using the same key over and over, or using a shorter repeating key results in a less secure method where the cipher text could be decrypted using a frequency analysis.

Python Code

In this Python code we are using the XOR bitwise operator (in Python: ^) to apply the XOR mask using the plain text and the key.

To improve readability, we are displaying the cipher text in different format: Ascii, Denary, Hexadecimal and Binary format.

Tagged with: cryptography, encryption

Eureka! (and King Hiero’s Crown)

Posted on November 26, 2020 by Administrator Posted in Computer Science, Python - Beginner, Python Challenges, Solved Challenges

Archimedes is one of the most famous physicist, mathematician, astronomer and inventor of the classical age.

Did you know?

Archimedes is one of the most famous physicist, mathematician, astronomer and inventor of the classical age: He lived in Syracuse on the island of Sicily in the third century B.C. Many of his inventions and theories are still being used today.

This Python challenge will be based on Archimedes’ most famous “Eureka!” moment: At the time, Hiero, The King of Syracuse (Sicily, Italy), had given his goldsmith some pure gold and asked him to make a crown out of this gold. On reception of the crown, Hiero suspected he had been cheated by the goldsmith. He believe the goldsmith had replaced some of the pure gold with the same weight of silver. However Hiero needed to be able to prove that his suspicion was correct and that the crown was not made of pure gold.

Knowing the weight/mass of the crown was not enough to confirm whether the crown was made of pure gold (as opposed to a mix of gold and silver). However if Archimedes knew that if he could accurately measure the volume of the crown, he could work out its density. (Density = mass / volume). He could then compare this density with the density of pure gold to see if they are the same. If not, this would be the proof that the crown is not just made of pure gold which would confirm Hiero’s suspicion. The issue was that, though it was easy at the time to precisely measure the mass of an object, there was no method for working out the exact volume of an irregular object (such as a crown!).

It’s while stepping into a bath that Archimedes noticed that the water level rose: he immediately deducted that the volume of water displaced must be equal to the volume of the part of his body he had submerged. He then realised that the volume of irregular objects could be measured with precision using this submersion approach. He is said to have been so eager to share his discovery that he leapt out of his bathtub and ran naked through the streets of Syracuse shouting Eureka! Eureka! (Greek for “I have it!”).

The volume of an object is equal to the volume of the water displaced when this object is submerged.

By applying this approach to the golden crown, Archimedes was able to get an accurate measure of the volume of the crown and could hence calculate the density of the crown which effectively turned out to be of a lesser density than pure gold. This confirmed Hiero’s suspicion that his goldsmith had stolen some of the pure gold he was given to make this crown!