More results...

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

Drone Display

drone-light-showDrone displays/light shows are performed by synchronized and choreographed collections of drones that position themselves to recreate various aerial formations. Each drone is equipped with LED lights that can change colour during the display. The first drone display was presented in 2012 in Austria, where Ars Electronica Futurelab introduced SPAXELS (short for “space elements”) for the first time. More recent drone display includes the Edinburgh’s Hogmanay 2020 New Year Celebrations and the London 2020 New Year Firework and Lights display.

For this challenge, we are using Glowscript to recreate a drone display choreography.

Glowscript/vPython?…


To complete this challenge and find out about all the 3D shapes you can use in Glowscript, you will need to refer to the Glowscript/vPython online documentation.

Drone Display Preview


Here is our drone display demonstration which consists of 3 scenes. Each scene involves 20 drones.

(x,y,z) Coordinates


The drones are positioned in the night sky using (x,y,z) 3D coordinates.

Each scene is defined as a list of 20 sets of (x,y,z) coordinates, to store the position of each drone in the scene. For instance the Moon scene is stored as follows:

#Scene 1: Moon
scene = [(20,180,0),
(-10,160,0),
(-30,130,0),
(-50,100,0),
(-60,60,0),
(-70,20,0),
(-70,-20,0),
(-60,-50,0),
(-40,-80,0),
(-10,-110,0),
(20,-150,0),
(-30,-130,0),
(-70,-110,0),
(-100,-80,0),
(-130,-50,0),
(-140,0,0),
(-130,50,0),
(-110,100,0),
(-80,140,0),
(-40,170,0)]

You can easily recreate your own scene using this online plotting tool:
drone-light-show-plotting-coordinates

Linear Interpolation Formulas


Linear interpolation formulas are used on the (x,y,z) coordinates to reposition the drones from one scene to another creating a smooth animation effect.

Here is an explanation of how linear interpolation formulas can be applied to progressively move a drone from one position (from scene A) to another position (from scene Z), to simplify we are only focusing on 2D coordinates (x,y).
tweening-linear-interpolation

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

x(t) = xA + (xZ – xA) * t / 10
y(t) = yA + (yZ – yA) * t / 10

In 3D, the same formula would be applied to the z coordinate:

z(t) = zA + (zZ – zA) * t / 10
  • “t” represents the time: in other words the frame number (e.g. from 0 to 10 frames)
  • (xA,yA,zA) the coordinates of a drone from the starting position (e.g. scene “A”)
  • (xZ,yZ,zZ) the coordinates of a drone from the ending position (e.g. scene “Z”)

In our animation we have used 100 frames between each scene to create a smooth transition.

RGB Colour Codes and Linear Interpolation Formulas


The same linear interpolation formulas are used on the RGB codes of each drone to smoothly change the drone’s light colours using a gradient animation.

In Glowscript a colour is represented using an (r,g,b) vector where r, g and b are three decimal values between 0 and 1.

The linear interpolation formulas on an RGB colour code are as follows:

R(t) = RA + (RZ – RA) * t / 10
G(t) = GA + (GZ – GA) * t / 10
B(t) = BA + (BZ – BA) * t / 10
  • “t” represents the time: in other words the frame number (e.g. from 0 to 10 frames)
  • (RA,GA,BA) the RGB colour code of a drone on the starting scene (e.g. scene “A”)
  • (RZ,GZ,BZ) the RGB colour code of a drone on the next scene (e.g. scene “Z”)

Camera Position


To improve the preview of our demo, we are also rotating the camera (changing the camera angle) between each frame, to preview the light show using a 365 rotation.

You can also control the position of the camera by right clicking on the canvas and you can zoom-in/out using a wheel mouse.

Tagged with:

Wired & Wireless Connection Methods

Take the Quiz! (open full screen)


Can you recognise the different types of cables used in IT? Do you know what are the main wireless technologies used to connect IT equipment? Take the quiz to check your knowledge of wired and wireless connection methods!

LED Dice Logic Gates Diagrams

LED Dice


Our aim is to create an LED Dice using a breadboard and 7 LEDs disposed as follows:
LED-Dice

We will then use three buttons/switches to control the 7 LEDs of the dice to recreate the following patterns:
LED-Dice-6

Octal Number System

The octal numeral system, or oct for short, is the base-8 number system. It uses 8 digits from 0 to 7. Octal numerals can be converted into binary using 3 binary digits and the following conversion table.
octal-conversion-table

We will use three input buttons A,B,C representing the 3 binary digits to generate 8 binary patterns representing the 8 octal digits from 0 to 7.
LED-Dice-input-output

We will then use logic gates circuits to control each of the 7 LED based on the three inputs:

LED Dice: Truth Tables & Karnaugh Maps


We will use three inputs A,B and C to represent the three digits as ABC (A is the most significant digit, C is the least significant digit). When creating the electronic circuit we will use 3 switches to represent these 3 inputs.

We will need 7 outputs one for each LED. So let’s investigate each LED one at a time.

LED 1 & 6LED 2 & 5LED 3 & 4LED 7
LED 1 & LED 6 (top-left and bottom right) should be on for the following values:

LED-Dice-value-4ABC:100 LED-Dice-value-5ABC:101 LED-Dice-value-6ABC:110 LED-Dice-value-7ABC:111

LED 1 & 6 should be off for the following values:

LED-Dice-value-0ABC:000 LED-Dice-value-1ABC:001 LED-Dice-value-2ABC:010 LED-Dice-value-3ABC:011

Hence the Truth Table for LED 1 & LED 6 is as follows:

Inputs Output
A B C LED 1
0 0 0 0
0 0 1 0
0 1 0 0
0 1 1 0
1 0 0 1
1 0 1 1
1 1 0 1
1 1 1 1

This Truth table can be represented using a Karnaugh Map:

Karnaugh Map for LED 1 & LED 6

Karnaugh Map for LED 1 & LED 6

LED 2 & LED 5 (top-right and bottom left LED) should be on for the following values:

LED-Dice-value-2ABC:010 LED-Dice-value-3ABC:011 LED-Dice-value-4ABC:100 LED-Dice-value-5ABC:101 LED-Dice-value-6ABC:110 LED-Dice-value-7ABC:111

LED 2 & LED 5 should be off for the following values:

LED-Dice-value-0ABC:000 LED-Dice-value-1ABC:001        

Hence the Truth Table for LED 2 & LED 5 is as follows:

Inputs Output
A B C LED 2
0 0 0 0
0 0 1 0
0 1 0 1
0 1 1 1
1 0 0 1
1 0 1 1
1 1 0 1
1 1 1 1

This Truth table can be represented using a Karnaugh Map:

Karnaugh Map for LED 2 and LED 5

Karnaugh Map for LED 2 and LED 5

Follow the same process to define the Truth Table and Karnaugh Map of LED 3 and LED 4 which have the same truth table.

LED 3 & LED 4 (middle-left and middle-right) should be on for the following values:

LED-Dice-value-6ABC:110 LED-Dice-value-7ABC:111        

LED 3 & 4 should be off for the following values:

LED-Dice-value-1ABC:001 LED-Dice-value-2ABC:010 LED-Dice-value-3ABC:011 LED-Dice-value-4ABC:100 LED-Dice-value-5ABC:101 LED-Dice-value-0ABC:000


Follow the same process to define the Truth Table and Karnaugh Map of LED 7 (LED in the middle of the dice).
LED 7 (in the middle) should be on for the following values:

LED-Dice-value-1ABC:001 LED-Dice-value-3ABC:011 LED-Dice-value-5ABC:101 LED-Dice-value-7ABC:111

LED 7 should be off for the following values:

LED-Dice-value-4ABC:100 LED-Dice-value-0ABC:000 LED-Dice-value-2ABC:010 LED-Dice-value-6ABC:110


LED Dice: Boolean Expressions


The Karnaugh maps will help us define the Boolean Expressions associated with each of the 7 LEDs.

LED 1 & 6LED 2 & 5LED 3 & 4LED 7
Karnaugh Map:
Karnaugh Map for LED 1 & 6

Karnaugh Map for LED 1 & LED 6

Boolean Expression:
Boolean Expression for LED1 & LED 6

Boolean Expression for LED1 & LED 6

Karnaugh Map:
Karnaugh Map for LED 2 & LED 5

Karnaugh Map for LED 2 & LED 5

Boolean Expression:
Boolean expression for LED 2 & LED 5

Boolean expression for LED 2 & LED 5

Use the Karnaugh Map for LED 3 & 4 to define the Boolean Expression of LED 3 & LED 4.
Use the Karnaugh Map for LED 7 to define the Boolean Expression of LED 7.

LED Dice: Logic Gates Diagrams


We can now convert each Boolean expression into a Logic Gates circuit to link our 3 inputs (switches) to our 7 LEDs display using a range of logic gates.
LED 1 & LED 6LED 2 & LED 5LED 3 & LED 4LED 7
Boolean Expression:
Boolean Expression for LED1 & LED 6

Boolean Expression for LED1 & LED 6

Logic Gates Diagram:
In this case, the Boolean expression being so basic, there is no need for any logic gates to control LED 1. The LED is directly connected to input A.
Logic Gates Diagram for LED 1 & LED 6

Logic Gates Diagram for LED 1 & LED 6

Boolean Expression:
Boolean expression for LED 2 & LED 5

Boolean expression for LED 2 & LED 5

Logic Gates Diagram:
In this case, the Boolean expression being so basic, only one OR gate is needed using input A and input B.
Logic Gates Diagrams for LED 2 & LED 5

Logic Gates Diagrams for LED 2 & LED 5

Use the Boolean Expression of LED 3 & LED 4 to draw the logic gates diagram required to control LED 3 & LED 4.
Use the Boolean Expression of LED 7 to draw the logic gates diagram required to control LED 7.

Testing


You can now recreate your logic gates circuit using our logic gates circuit simulator to test if it behaves as expected for all 8 entries.

You can also recreate the electronic circuit using bread boards, LEDs, resistors and logic gates or create your electronic cricuit online using tinkercad.

LED Dice - Electronic Circuit - Using AND and OR gates.

LED Dice – Electronic Circuit – Using AND and OR gates.

unlock-access

Solution...

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

Stopwatch Class (JavaScript)

stopwatch-classIn this challenge we will create an interactive stopwatch using HTML, CSS and JavaScript. The aim of this blog post is to use Object Oriented Programming to create our own Stopwatch class.

Step 1: Stopwatch Class and its constructor

First we will create a class for our stopwatch and use its constructor to initialise all the properties of the class as follows:

  • state: the state of the stopwatch, either “paused” or “running”, initially set to “paused”.
  • delay: the delay/interval in ms between two “ticks” of the stopwatch. This defines the accuracy of the stopwatch. Per default it will be set to 100ms.
  • value: the number of milliseconds the stopwatch has been running for. Initialised to 0ms.
  • display: the HTML element where the stopwatch value will be displayed.

Here is the JavaScript code of our stopwatch so far:

class Stopwatch {
  constructor(id, delay=100) { //Delay in ms
    this.state = "paused";
    this.delay = delay;
    this.display = document.getElementById(id);
    this.value = 0;
  }
}

We can then create an HTML element (DIV tag) that will be used to display the stopwatch value.

<div id="stopwatch">00:00:00.0</div>

We can then create a stopwatch object/instance of the Stopwatch class as follows:

stopwatch = new Stopwatch("stopwatch");

When creating our stopwatch object, the constructor of the class is automatically called to initialise the stopwatch.

At this stage nothing happens yet, as we have not defined any behaviours/methods to our Stopwatch class.

Notice the naming convention: when creating classes and objects it is good practice for the identifier of a class to start with an uppercase letter (e.g. Stopwatch) whereas identifiers used for objects start with a lowercase letter (e.g. stopwatch).

Step 2: Adding a few methods

The main methods of our Stopwatch class will be:

  • start(): to start/resume the stopwatch!
  • stop(): to stop/pause the stopwatch
  • reset(): to stop and reset the stopwatch to 0ms.
  • update(): to increment the stopwatch (based on the set delay) and refresh its display with the current value.

The update() method of the stopwatch will use an extra formatTime() method used to convert a number of milliseconds into the HH:MM:SS format.

Here is the full code for the Stopwatch class including all 5 methods:

class Stopwatch {
  constructor(id, delay=100) { //Delay in ms
    this.state = "paused";
    this.delay = delay;
    this.display = document.getElementById(id);
    this.value = 0;
  }
  
  formatTime(ms) {
    var hours   = Math.floor(ms / 3600000);
    var minutes = Math.floor((ms - (hours * 3600000)) / 60000);
    var seconds = Math.floor((ms - (hours * 3600000) - (minutes * 60000)) / 1000);
    var ds = Math.floor((ms - (hours * 3600000) - (minutes * 60000) - (seconds * 1000))/100);

    if (hours   < 10) {hours   = "0"+hours;}
    if (minutes < 10) {minutes = "0"+minutes;}
    if (seconds < 10) {seconds = "0"+seconds;}
    return hours+':'+minutes+':'+seconds+'.'+ds;
  }
  
  update() {
    if (this.state=="running") {
      this.value += this.delay;
    }
    this.display.innerHTML = this.formatTime(this.value);
  }
  
  start() {
    if (this.state=="paused") {
      this.state="running";
      if (!this.interval) {
        var t=this;
        this.interval = setInterval(function(){t.update();}, this.delay);
      }
    }
  }
  
  stop() {
       if (this.state=="running") {
      this.state="paused";
    if (this.interval) {
      clearInterval(this.interval);
      this.interval = null;
    }
       }
  }
  
  reset() {
    this.stop();
    this.value=0;
    this.update();
  }
}

Note that the setInterval() function used in the start() method is used to constantly call the update() method at the specified interval/delay (in milliseconds).

Step 3: Using the stopwatch object

We have already (see step 1) created our stopwatch object using the following JavaScript code:

stopwatch = new Stopwatch("stopwatch");

We can now add three buttons in HTML to trigger the start(), stop() and reset() methods of our object:

<div id="stopwatch">00:00:00.0</div>
<button onclick="stopwatch.start();">Start</button> 
<button onClick="stopwatch.stop();">Stop</button>
<button onClick="stopwatch.reset();">Reset</button>
</div>

HTML – CSS & JavaScript Code

Here is the full code for our stopwatch with some extra CSS to improve the look & feel of our stopwatch.

See the Pen
Stopwatch Class
by 101 Computing (@101Computing)
on CodePen.

Your Challenge

Your challenge is to adapt this code to create a new timer class.
The timer will have the same look & feel as the stopwatch, but instead of counting up, it will count down from a pre-set time (e.g. 1 minute timer, 5 minute timer). The user should be able to set the pre-set time for the timer and start/pause/reset the timer using control buttons. The timer should automatically stop when it reaches 00:00:00.0.

Tagged with:

Poker Card Game (JavaScript)

playing-cardsIn this challenge we will create a one-player game of poker based on the rules of Texas Hold’em Poker.

In a game of Texas Hold’em Poker, for each round, five “community cards” are dealt face-up on the “board”. Each player is then dealt two private cards. All players in the game can use the “community” cards alongside their own private cards to make their best possible five-card poker hand.

At the start of each round, the 5 community cards are presented face-up. Players can only see their two private cards and can start betting. Then the first 3 cards of the board are revealed (The “flop”). Another round of betting can then take place. Then the 4th card is revealed (the “turn”), followed by another round of betting. The fifth card is then revealed (the “river”) and a final round of betting ensues. Finally the players who have not folded yet will reveal their cards and the player with the strongest hand wins the round.

The hands’ values are defined as follows: (From weakest to strongest)

  1. High card: Simple value of the card. Lowest: 2 – Highest: Ace
  2. Pair: Two cards with the same value
  3. Two pairs: Two sets of two cards with the same value
  4. Three of a kind: Three cards with the same value
  5. Straight: Sequence of 5 cards in increasing value (Ace can precede 2 and follow up King)
  6. Flush: 5 cards of the same suit
  7. Full house: Combination of three of a kind and a pair
  8. Four of a kind: Four cards of the same value
  9. Straight flush: Straight of the same suit
  10. Royal flush Straight: flush from Ten to Ace

JavaScript implementation

We will create our game using HTML, CSS and JavaScript.

Our JavaScript code will use two main classes as follows:
deck-card-classes

Deck ClassCard ClassMain Code
class Deck {
    constructor() {
    this.deck = [];
    this.reset(); //Add 52 cards to the deck
    this.shuffle(); //Shuffle the deck
  } //End of constructor
  
  
  reset() {
    this.deck = [];
    const suits = ['Hearts', 'Diamonds', 'Clubs', 'Spades'];
    const values = ['Ace', 2, 3, 4, 5, 6, 7, 8, 9, 10, 'Jack', 'Queen', 'King'];

    for (let suit in suits) {
      for (let value in values) {
        this.deck.push(values[value] + " of " + suits[suit]);
      }
    }
  } //End of reset()
  
  
  shuffle() {
    let numberOfCards = this.deck.length;  
    for (var i=0; i<numberOfCards; i++) {
      let j = Math.floor(Math.random() * numberOfCards);
      let tmp = this.deck[i];
      this.deck[i] = this.deck[j];
      this.deck[j] = tmp;
    }
  } //End of shuffle()
  
  deal(){
    return this.deck.pop();
  } //End of deal()
  
  isEmpty() {
    return (this.deck.length==0);
  } //End of isEmpty()
  
  length() {
    return this.deck.length;
  }
  
} //End of Deck Class
class Card {
  constructor(card) {
      this.card = card;
      const cardValues = {"Ace of Hearts":1, "2 of Hearts":2, "3 of Hearts":3, "4 of Hearts":4, "5 of Hearts":5, "6 of Hearts":6, "7 of Hearts":7, "8 of Hearts":8, "9 of Hearts":9, "10 of Hearts":10, "Jack of Hearts":11, "Queen of Hearts":12, "King of Hearts":13, "Ace of Diamonds":1, "2 of Diamonds":2, "3 of Diamonds":3, "4 of Diamonds":4, "5 of Diamonds":5, "6 of Diamonds":6, "7 of Diamonds":7, "8 of Diamonds":8, "9 of Diamonds":9, "10 of Diamonds":10, "Jack of Diamonds":11, "Queen of Diamonds":12, "King of Diamonds":13, "Ace of Clubs":1, "2 of Clubs":2, "3 of Clubs":3, "4 of Clubs":4, "5 of Clubs":5, "6 of Clubs":6, "7 of Clubs":7, "8 of Clubs":8, "9 of Clubs":9, "10 of Clubs":10, "Jack of Clubs":11, "Queen of Clubs":12, "King of Clubs":13, "Ace of Spades":1, "2 of Spades":2, "3 of Spades":3, "4 of Spades":4, "5 of Spades":5, "6 of Spades":6, "7 of Spades":7, "8 of Spades":8, "9 of Spades":9, "10 of Spades":10, "Jack of Spades":11, "Queen of Spades":12, "King of Spades":13};
    
    this.value = cardValues[card];
    this.suit = card.substring(card.indexOf(" of ")+4);
    this.placeHolder = null;
    this.flipped = false;
  
    var suits = {'Hearts':0, 'Diamonds':13, 'Clubs':26, 'Spades':39 }
    this.position = suits[this.suit] + this.value; //Position in a sorted deck
  } //End of Constructor
  
  displayCard(placeHolder,flipped=true) {
    this.placeHolder = document.getElementById(placeHolder);
    this.placeHolder.classList.add("card");
    this.flipped=flipped;
    if (flipped) {
      this.placeHolder.style.backgroundPosition = -150*this.position + "px";
    } else {
      this.placeHolder.style.backgroundPosition = "0px";  
    }
  }
  
  flip() {
    if (this.flipped) {
      this.placeHolder.style.backgroundPosition = "0px";
      this.flipped=false;
    } else {
      this.placeHolder.style.backgroundPosition = -150*this.position + "px";
      this.flipped=true;  
    }
  } //End of flip()
  
} //End of Card class
const deck = new Deck();
let card1,card2,card3,card4,card5,playerCard1,playerCard2;

function deal() {
  if (deck.length()<7) {
    deck.reset();
    deck.shuffle();
  }  
  card1 = new Card(deck.deal());
  card2 = new Card(deck.deal());
  card3 = new Card(deck.deal());
  card4 = new Card(deck.deal());
  card5 = new Card(deck.deal());
  playerCard1 = new Card(deck.deal());
  playerCard2 = new Card(deck.deal());
  
  card1.displayCard("card1",false);  
  card2.displayCard("card2",false);  
  card3.displayCard("card3",false);  
  card4.displayCard("card4",false);  
  card5.displayCard("card5",false);  
  playerCard1.displayCard("playerCard1",true);  
  playerCard2.displayCard("playerCard2",true); 
} //End of deal()

function nextStep(el) {
  if (!card1.flipped) {
    card1.flip();
    card2.flip();
    card3.flip();
    el.innerHTML="Reveal 4<sup>th</sup> card";
  } else if(!card4.flipped) {
    card4.flip();
    el.innerHTML="Reveal 5<sup>th</sup> card";
} else if(!card5.flipped) {
    card5.flip();
    el.innerHTML="New Round";
} else {
  deal();
  el.innerHTML="Reveal first 3 cards.";
}
} //End of nextStep()

deal();
//The user then clicks the button to call the nextStep() function...

Your Challenge

We have started the code for you. Investigate how this code works and how the Deck class and the Card class have been implemented and used in the game.

The code is incomplete as it does not output the hand’s value at the end of the round. Complete this code to work out and output the hand’s value.

See the Pen
Poker Card Game
by 101 Computing (@101Computing)
on CodePen.


Note that this script uses one picture. In case this picture is not displaying properly, you may have to replace its URL in the CSS code, using the following address:

Note that the following picture gives you additional information on how each card is displayed using a single picture (png file) containing all 52 cards. The right section of the picture is displayed by re-positioning (translating) the background image to match the position of the desired card (using the background-position-x CSS property of the card):
card-css

Tagged with:

Stacks and Queues in LMC

In this post we will investigate how to implement a queue and a stack data structure using low-level programming. We will use an upgraded version of Little Man Computer (LMC) that supports indirect addressing to to do.

Implementing a Queue in LMC


A queue is a FIFO data structure: First-In First-Out in other words, it is used to implement a first come first served approach. An item that is added (enqueue) at the end of a queue will be the last one to be accessed (dequeue).

queue-diagram

Two pointers are needed to implement a queue data structure: A front pointer which holds the memory address of the first item of the queue and a rear pointer which holds the memory address of the last item of the queue.

When implementing a Queue data structure we need to implement two algorithms/functions to enqueue a new value at the end of the queue and to dequeue a value from the front of the queue.

Algorithm to enqueue a value to a queue:

FUNCTION ENQUEUE(value):
     If queue IS NOT FULL:
            rearPointer = rearPointer + 1
            queue[rearPointer] = value

Algorithm to dequeue a value from a queue:

FUNCTION DEQUEUE():
     If queue IS NOT EMPTY:
            value = queue[frontPointer]
            frontPointer = frontPointer + 1
            RETURN value

Low Level Implementation of a queue using LMC:

menu    INP
        SUB one
        BRZ enqueue 
        SUB one 
        BRZ dequeue
        BRA exit
	
exit    HLT
 
enqueue LDA max
        SUB rear
        BRZ full
        INP
        STA @rear
        LDA rear
        ADD one
        STA rear
        BRA menu

full    LDA error1
        OUT
        BRA menu

dequeue LDA front
        SUB rear
        BRZ empty
        LDA @front
        OUT
        LDA front
        ADD one
        STA front
        BRA menu

empty   LDA error2
        OUT
        BRA menu

front   DAT 50
rear    DAT 50 
one     DAT 1 
max     DAT 100 
error1  DAT -1  
error2  DAT -2

The above algorithm works as follows:

  • The user needs to input one of the following three menu options:
    • 1: To enqueue a new value,
    • 2: To dequeue a value,
    • Any other value: To exit the program.
  • If the user opts for option 1, they will then need to input the value to enqueue. They will then be redirected to the start of the program to input their next option from the menu. If the queue is full, the program will output the error code -1. The queue will be stored in memory starting at memory location 50. The queue will be full once it reaches memory location 99.
  • If the user opts for option 2, a value will be removed from the queue and displayed as an output. They will then be redirected to the start of the program to input their next option from the menu. If the queue is empty, the program will output the error code -2.
  • The program will stop if the user selects a value different from 1 or 2 from the menu.

Direct vs indirect addressing:
The LMC language was initially implemented to only support direct addressing: Each operand is a memory location of where the data to be used is stored. However to access the value stored at the front (dequeue) or rear (enqueue) memory locations of the queue it is necessary to use indirect addressing. The above code will hence only work with an LMC simulator that supports indirect addressing. In the code above the @ sign is used to indicate when indirect addressing is used. The following page gives more explanations of the main memory address modes used in low-level languages.

You can try code provided above in our LMC simulator as it does support indirect addressing:
LMC SimulatorOpen in New Window

Test Plan:

Test # Input Values Expected Output Pass/Fail?
#1 1,10 – 1,11 – 1,12 – 2 – 2 – 2 – 2 – 3 LMC-Queue-Test-2
#2 1,1 – 1,2 – 1,3 – 2 – 1,4 – 2 – 1,5 – 2 – 3 LMC-Queue-Test-1

Implementing a Stack in LMC


A stack is a FILO data structure: First-In Last-Out. Imagine a stack of books piled up on a table. When you add (push) a book on top of the pile, it will be the first book that you will then take (pop) from the pile (stack).

stack-diagram

Only one pointer is needed to implement a stack data structure: An End of Stack pointer which holds the memory address of the last item of the stack.

When implementing a Stack data structure we need to implement two algorithms/functions to push a new value at the end of the stack and to pop a value from the end of the stack.

Algorithm to push a value to a stack:

FUNCTION PUSH(value):
     If stack IS NOT FULL:
            stackPointer = stackPointer + 1
            stack[stackPointer] = value

Algorithm to pop a value from a stack:

FUNCTION POP():
     If stack IS NOT EMPTY:
            value = stack[stackPointer]
            stackPointer = stackPointer - 1
            RETURN value

Your Challenge:
Your challenge is to adapt the code given to implement a queue in order to implement a stack instead. You will need to apply the right terminology (push and pop instead of enqueue and dequeue) and apply the above two algorithms in LMC.

Tagged with:

Algebraic Pyramid Challenge

algebraic-pyramidFor the purpose of this challenge we will use algebraic pyramids pointing downwards (or upside down pyramids!).

The idea of this mathematical puzzle is to fill in all the bricks of a pyramid based on the following rule:

  • To work out the value of a brick, add the values of the two adjacent bricks above it.

algebraic-pyramid-rule

Python Challenge #1: Fix sized pyramids


This Python challenge will consist of writing a procedure that will take a list of values as a parameter, and will as a result generate and output an upside down pyramid where the top layer of the pyramid will contain all the values from the given list.

To simplify this problem, we will first assume that the list of number will always contains exactly 4 values.
For example:
algebraic-pyramid-list

The output of our procedure should be as follows:
algebraic-pyramid

Challenge #1: Python Code:


You will need to complete the following python code to work out and print all the layers of the pyramid.

Challenge #1: Test Plan


Check that your code is working using the following list of 4 values.

Test # List Expected Output Pass/Fail?
#1 [4,6,8,2] algebraic-pyramid-test-2
#2 [30,12,10,5] algebraic-pyramid-test-1
#3 [3,6,9,12] algebraic-pyramid-test-3

Challenge #2: Using lists of different sizes


The second challenge consists of adapting the code from challenge 1 to make sure that it works for any list (of any length) of values.

Challenge #2: Test Plan

Test # List Expected Output Pass/Fail?
#1 [3,6,9] algebraic-pyramid-test-3-layers
#2 [30,12,10,5] algebraic-pyramid-test-1
#3 [1,2,3,4,5,6] algebraic-pyramid-test-6-layers
Tagged with:

Bracket Validator

bracketsThe 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

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.
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:
cross-products

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.
unlock-access

Solution...

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

Linked Lists

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.
linked-list

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

Memory Address linked-list-nodeNode Value linked-list-pointerPointer
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:
linked-list-before-insertion
linked-list-after-insertion
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 linked-list-nodeNode Value linked-list-pointerPointer
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:
linked-list-deletion

Memory Address linked-list-nodeNode Value linked-list-pointerPointer
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.
circular-list

Memory Address linked-list-nodeNode Value linked-list-pointerPointer
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!
double-linked-list

Memory Address linked-list-nodeNode Value linked-list-previous-pointerPrevious Node Pointer linked-list-pointerNext 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:
circular-double-linked-list

Memory Address linked-list-nodeNode Value linked-list-previous-pointerPrevious Node Pointer linked-list-pointerNext Node Pointer
0 21 3 1
1 35 0 2
2 47 1 3
3 89 2 0

Other use of linked lists…

Linked-lists can be used to implement more abstract data types such as queues, stacks and binary trees.