Little Man Computer: Factorial Challenge

Posted on May 5, 2017 by Administrator Posted in Computer Science, Computing Concepts, Little Man Computer (LMC)

In Mathematics, the factorial of n is denoted by n! and calculated by the product of integer numbers from 1 to n.

For instance:

In this challenge you will write a program using Little Man Computer to ask the user to enter a positive number. In return the program will output the factorial of this number.

Before completing this challenge, we recommend you to have a go at:

Multiplication using LMC

While checking the Little Man Computer Instruction Set (See table at the bottom of this post), you will have noticed that, through there are two instructions for adding (ADD) and subtracting (SUB) numbers, there is no instruction for multiplying two numbers.

The solution to overcome this, is two consider a multiplication as a series of additions. For instance:

5 * 4 = 5 + 5 + 5 + 5

Find out more: Little Man Computer: Multiplication

Iteration using LMC

To apply an iterative approach for this challenge we will use branching options: Little Man Computer: 5 + 4 + 3 + 2+ 1.

This challenge will add a level of complexity as we will be using a nested loop approach: one loop to list all the multiplications to be performed (e.g. 4! = 4 * 3 * 2 * 1) and one loop for implementing each multiplication as a series of additions. (e.g. 4 * 3 = 4 + 4 + 4)

LMC Simulators

Solution

This solution also caters for the fact that 0! = 1. This is the purpose of line 3, 34,35 and 36.

          inp 
          sta final 
          brz oneval
          sub one
          sta iteration
          sta counter
          lda final
          sta num
mult      lda iteration
          brz end
          sub one
          brz end
          lda final
          add num
          sta final
          lda counter
          sub one
          sta counter
          sub one
          brz next
          bra mult
next      lda final
          sta num 
          lda iteration
          sub one
          sta iteration
          sta counter
          sub one
          brz end
          bra mult
end       lda final
          out
          hlt
oneval    lda one
          out
          hlt
final     dat 0
counter   dat 0
one       dat 1
iteration dat 0
num       dat 0

© Solution by Howard C.

LMC Instruction Set

Note that in the following table “xx” refers to a memory address (aka mailbox) in the RAM. The online LMC simulator has 100 different mailboxes in the RAM ranging from 00 to 99.

Mnemonic	Name	Description	Op Code
INP	INPUT	Retrieve user input and stores it in the accumulator.	901
OUT	OUTPUT	Output the value stored in the accumulator.	902
LDA	LOAD	Load the Accumulator with the contents of the memory address given.	5xx
STA	STORE	Store the value in the Accumulator in the memory address given.	3xx
ADD	ADD	Add the contents of the memory address to the Accumulator	1xx
SUB	SUBTRACT	Subtract the contents of the memory address from the Accumulator	2xx
BRP	BRANCH IF POSITIVE	Branch/Jump to the address given if the Accumulator is zero or positive.	8xx
BRZ	BRANCH IF ZERO	Branch/Jump to the address given if the Accumulator is zero.	7xx
BRA	BRANCH ALWAYS	Branch/Jump to the address given.	6xx
HLT	HALT	Stop the code	000
DAT	DATA LOCATION	Used to associate a label to a free memory address. An optional value can also be used to be stored at the memory address.

Tagged with: Little Man Computer, LMC

Little Man Computer: Multiplication

Posted on April 28, 2017 by Administrator Posted in Computer Science, Computing Concepts, Little Man Computer (LMC)

Write an LMC program to let the user enter two numbers, num1 and num2.
The program should output the results of multiplying these two numbers: num1 x num2.

LMC Simulators

Solution

The solution to overcome this, is two consider a multiplication as a series of additions. For instance:

5 * 4 = 5 + 5 + 5 + 5

This is how we will implement our multiplication algorithm:

        INP
        STA NUM1
        INP 
        STA NUM2
LOOP    LDA TOTAL
        ADD NUM1
        STA TOTAL
        LDA NUM2
        SUB ONE
        STA NUM2
        BRP LOOP
        LDA TOTAL
        SUB NUM1
        STA TOTAL
        OUT
        HLT
NUM1    DAT
NUM2    DAT
ONE     DAT 1
TOTAL   DAT 0

LMC Instruction Set

Note that in the following table “xx” refers to a memory address (aka mailbox) in the RAM. The online LMC simulator has 100 different mailboxes in the RAM ranging from 00 to 99.

Mnemonic	Name	Description	Op Code
INP	INPUT	Retrieve user input and stores it in the accumulator.	901
OUT	OUTPUT	Output the value stored in the accumulator.	902
LDA	LOAD	Load the Accumulator with the contents of the memory address given.	5xx
STA	STORE	Store the value in the Accumulator in the memory address given.	3xx
ADD	ADD	Add the contents of the memory address to the Accumulator	1xx
SUB	SUBTRACT	Subtract the contents of the memory address from the Accumulator	2xx
BRP	BRANCH IF POSITIVE	Branch/Jump to the address given if the Accumulator is zero or positive.	8xx
BRZ	BRANCH IF ZERO	Branch/Jump to the address given if the Accumulator is zero.	7xx
BRA	BRANCH ALWAYS	Branch/Jump to the address given.	6xx
HLT	HALT	Stop the code	000
DAT	DATA LOCATION	Used to associate a label to a free memory address. An optional value can also be used to be stored at the memory address.

Tagged with: Little Man Computer, LMC

Little Man Computer: 5+4+3+2+1

Posted on April 28, 2017 by Administrator Posted in Computer Science, Computing Concepts, Little Man Computer (LMC)

Write an LMC program to let the user enter a number n.

The program should calculate the output n + (n-1) + (n-2) + … + 3 + 2 + 1.

For instance if the user enters the value 5. The program should output the number 15 because:

5 + 4 + 3 + 2 + 1 = 15

LMC Simulators

Solution

LMC Instruction Set

Note that in the following table “xx” refers to a memory address (aka mailbox) in the RAM. The online LMC simulator has 100 different mailboxes in the RAM ranging from 00 to 99.

Mnemonic	Name	Description	Op Code
INP	INPUT	Retrieve user input and stores it in the accumulator.	901
OUT	OUTPUT	Output the value stored in the accumulator.	902
LDA	LOAD	Load the Accumulator with the contents of the memory address given.	5xx
STA	STORE	Store the value in the Accumulator in the memory address given.	3xx
ADD	ADD	Add the contents of the memory address to the Accumulator	1xx
SUB	SUBTRACT	Subtract the contents of the memory address from the Accumulator	2xx
BRP	BRANCH IF POSITIVE	Branch/Jump to the address given if the Accumulator is zero or positive.	8xx
BRZ	BRANCH IF ZERO	Branch/Jump to the address given if the Accumulator is zero.	7xx
BRA	BRANCH ALWAYS	Branch/Jump to the address given.	6xx
HLT	HALT	Stop the code	000
DAT	DATA LOCATION	Used to associate a label to a free memory address. An optional value can also be used to be stored at the memory address.

Tagged with: Little Man Computer, LMC

Little Man Computer – Burglar Alarm

Posted on April 28, 2017 by Administrator Posted in Computer Science, Computing Concepts, Little Man Computer (LMC), Solved Challenges

Write an LMC program to let the user enter a PIN code to deactivate a burglar alarm.

The program should let the user have up to 3 attempts to enter the correct PIN code before starting the alarm.

The correct PIN code is “123”.

If the user gets the right PIN code the program should output value 1.
If the user gets the wrong PIN code the program should output value 9 indicating that they can have another go at entering the PIN code.
If after three attempts the PIN code entered is still incorrect, the program should output value -1.

LMC Simulators

LMC Instruction Set

Note that in the following table “xx” refers to a memory address (aka mailbox) in the RAM. The online LMC simulator has 100 different mailboxes in the RAM ranging from 00 to 99.

Mnemonic	Name	Description	Op Code
INP	INPUT	Retrieve user input and stores it in the accumulator.	901
OUT	OUTPUT	Output the value stored in the accumulator.	902
LDA	LOAD	Load the Accumulator with the contents of the memory address given.	5xx
STA	STORE	Store the value in the Accumulator in the memory address given.	3xx
ADD	ADD	Add the contents of the memory address to the Accumulator	1xx
SUB	SUBTRACT	Subtract the contents of the memory address from the Accumulator	2xx
BRP	BRANCH IF POSITIVE	Branch/Jump to the address given if the Accumulator is zero or positive.	8xx
BRZ	BRANCH IF ZERO	Branch/Jump to the address given if the Accumulator is zero.	7xx
BRA	BRANCH ALWAYS	Branch/Jump to the address given.	6xx
HLT	HALT	Stop the code	000
DAT	DATA LOCATION	Used to associate a label to a free memory address. An optional value can also be used to be stored at the memory address.

Solution...

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

Tagged with: Little Man Computer, LMC

Binary Trees – Linked Lists

Posted on April 27, 2017 by Administrator Posted in A Level Concepts, A Level Quiz, Computer Science, Computing Concepts

Binary trees are useful data structures used to solve specific computational problems. They provide a visual representation of how data can be stored and linked.

Computers use linked lists to store the information of binary trees. This blog post will look at how we can convert a binary tree into a linked list.

Binary Tree #1

Linked List

Memory Address	Node Value	Left Pointer	Right Pointer
0	K	4	1
1	T	2	3
2	S	5	–
3	U	–	–
4	A	–	–
5	L	–	–
6	–	–	–
7	–	–	–
…	…	…	…

The Tree is accessed using two pointers:

RootPointer = 0
EndPointer = 6

Each time a new element is added to the tree, the EndPointer increments by 1.

Binary Tree #2

Linked List

Memory Address	Node Value	Left Pointer	Right Pointer
0	T
1	F
2	L
3	B
4	A
5	U
6	C

Complete the linked list above.

What would happen if the next value to be added to the tree was letter S?

Binary Tree #3

The values have been received/stored in the following order:
N,E,T,F,B,V,U,C,Y
Draw the binary search tree on paper and complete the following link list table:

Memory Address	Node Value	Left Pointer	Right Pointer

What would happen if the next value to be added to the tree was letter K?

Tagged with: Binary Tree

Binary Expression Trees

Posted on April 25, 2017 by Administrator Posted in A Level Concepts, A Level Quiz, Computer Science, Computing Concepts

A binary expression tree is a specific kind of a binary tree used to represent expressions. Two common types of expressions that a binary expression tree can represent are algebraic expressions and boolean expressions. These trees can represent expressions that contain both unary and binary operators.

Algebric Expression Trees

An algebric expression such as (3 * 7) + 9 consists of:

Operands such as 3, 7, 9 or x, y, z,
Binary Operators such as +, – , *, /, DIV, MOD, ^
Unary Operators such as –

Algebric expressions can be represented using a binary expression tree where:

Each node is an operator,
Each leaf is an operand.

	Algebric Expression: (view solution)
	Algebric Expression: (view solution)
	Algebric Expression: (view solution)
	Algebric Expression:
	Algebric Expression:
	Algebric Expression:

Boolean Expression Trees

An Boolean expression such as (A OR B) AND C consists of:

Operands such as A, B, C,
Binary Operators such as AND, OR, XOR
Unary Operators such as NOT

Boolean expressions can be represented using a binary expression tree where:

Each node is an operator,
Each leaf is an operand.

	Boolean Expression: (view solution)
	Boolean Expression: (view solution)
	Boolean Expression:
	Boolean Expression:

Tagged with: Binary Tree

Traversal of a Binary-Tree

Posted on April 24, 2017 by Administrator Posted in A Level Concepts, A Level Quiz, Algorithms, Computer Science, Computing Concepts

In this blog post we will investigate four key algorithms used to read through the content of a binary tree:

Breadth-First Traversal Algorithm
Depth-First Algorithms:
- Pre-Order Traversal
- In-Order Traversal
- Post-Order Traversal

Binary Tree?

A Binary Tree is a data structure used in some algorithms to store data. In a binary tree each node can have up to two children.

Breadth-First Traversal Algorithm

A Breadth-first traversal consists of accessing each node, one level after the other. On each layer the nodes are accessed as they appear, from left to right.

Depth-First Traversal Algorithms

There are three depth-first traversal agorithms which are all based on a recursive approach.

Pre-Order Traversal Algorithm:

FUNCTION preorder-traverse(tree)
    IF tree is not empty
         visit root node of tree
         preorder-traverse(left sub-tree)
         preorder-traverse(right sub-tree)
    END IF
END FUNCTION

In-Order Traversal Algorithm:

FUNCTION inorder-traverse(tree)
    IF tree is not empty
         inorder-traverse(left sub-tree)
         visit root node of tree
         inorder-traverse(right sub-tree)
    END IF
END FUNCTION

Post-Order Traversal Algorithm:

FUNCTION postorder-traverse(tree)
    IF tree is not empty
         postorder-traverse(left sub-tree)
         postorder-traverse(right sub-tree)
         visit root node of tree
    END IF
END FUNCTION

Binary Tree #1

Breadth First: (view solution)

Depth-first Pre-order Traversal: (view solution)

Depth-first In-order Traversal: (view solution)

Depth-first Post-order Traversal: (view solution)

Binary Tree #2

Breadth First: (view solution)

Depth-first Pre-order Traversal: (view solution)

Depth-first In-order Traversal: (view solution)

Depth-first Post-order Traversal: (view solution)

Binary Tree #3

Breadth First: (view solution)

Depth-first Pre-order Traversal: (view solution)

Depth-first In-order Traversal: (view solution)

Depth-first Post-order Traversal: (view solution)

Binary Tree #4

Breadth First: (view solution)

Depth-first Pre-order Traversal: (view solution)

Depth-first In-order Traversal: (view solution)

Depth-first Post-order Traversal: (view solution)

Tagged with: Binary Tree

ASCII-Bot Challenge

Posted on April 20, 2017 by Administrator Posted in Computer Science, Python - Beginner, Python Challenges

In this challenge we will use the print() instruction in Python to create an ASCII-bot: A robot made of ASCII characters, in other words characters that you can type with a standard QWERTY keyboard.

Python Code

This is what your code will look like:

#ASCII-Bot Challenge - www.101computing.net/ASCII-bot-challenge/

print("         +-+      +")
print("           | +-+  |   +-+")
print("     +-+   |   |  |   |    +--+")
print("       |   |   |  |   |    |")
print("       |   |   |  |   |    |")
print("   +---+---+---+--+---+----+----+")
print("   |                            |")
print("   |   +-------+     +-------+  |")
print("+--+   |       |     |       |  +--+")
print("|  |   |       |     |       |  |  |")
print("|  |   |    +--+     |    +--+  |  |")
print("+--+   |    |--|     |    |--|  +--+")
print("   |   +-------+     +-------+  |")
print("   |             +-+            |")
print("   |             | |            |")
print("   |             +-+            |")
print("   |  +--+               +--+   |")
print("   |    +-----------------+     |")
print("   |                            |")
print("   +----------------------------+")
print("")
print("      ASCII-BOT: Hello World!")

Step 1: ASCII Art

Use asciiflow.com to create your own robot using ASCII characters.

Step 2: Create the Python code

Once your ASCII art is complete click on the

icon to generate the ASCII code. Copy and paste the code in the trinket window below.

Add print(“ at the beginning and “) at the end of each line of your ASCII art and check if your code is working by running the code using the icon.

Tagged with: Sequencing

Italian Takeaway Ordering System

Posted on April 15, 2017 by Administrator Posted in Computer Science, Python - Intermediate, Python Challenges, Solved Challenges

An Italian Takeaway is asking you to write a computer program to facilitate the ordering process and automatically calculate the total cost of an order.

They have stored their menu and all prices into a text file with the following information:

Code;Description;Price;

food-menu.txt

When a customer order food, they give the lists of codes they would like order. For instance a customer could order the following: S4,P3,P7,X2,D4,C1,W2

Your program should allow the customer to order as many options from the menu as they need. For each option, it should lookup the price in the text file provided. It should then calculate and output the total cost of the order.

To complete this challenge you will need to read more about how to read through a CSV file.

Complete the Code

Testing

Once you have completed the code check that it produces the expected output by performing the following tests:

Test #	Input Values	Expected Output	Actual Output
#1	S4,P3,P7	£28.89
#2	P10,S1	£16.00
#3	P4,D2,C2	£19.30

Extension Task

Add some input validation routines to your code so that the customer can only enter a valid code from the menu.

Video Tutorial / Solution

Solution...

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

Tagged with: CSV, File Handling, Linear Search

Cinema Booking Challenge

Posted on April 14, 2017 by Administrator Posted in Computer Science, Python - Advanced, Python Challenges, Solved Challenges

A cinema has created a booking system for their main theatre which consists of 48 seats, organised in 6 rows of 8 seats.

To store information as to whether a seat is booked or available, the program uses a 2-dimensional array (in python a list of lists). Each cell of the array contains the value 1 if the seat is booked or 0 if it is empty:

The following code is used to check whether a specific seat (identified by its row and column number) is already booked or not:

Challenge #1: Booking Options

Add a menu system to this code with 4 otpions:

Option 1: Book a seat by row/column
Option 2: Book a seat close to the front
Option 3: Book a seat close to the back
Option X: Exit

View Solution

#Cinema Booking Challenge - www.101computing.net/cinema-booking-challenge
seats = []
seats.append([0,0,1,1,0,1,1,1])
seats.append([0,1,1,0,0,1,0,1])
seats.append([1,0,0,1,0,1,1,0])
seats.append([0,1,1,1,0,0,0,1])
seats.append([0,0,1,1,0,1,0,0])
seats.append([1,0,1,1,0,0,1,1])

def displayBookings():
  #Display Bookings
  print("")
  print("======================================")
  print("")
  for row in seats:
    print(row)
  print("")
  print("======================================")

def checkSeat():
  row = int(input("Enter a row number (between 0 and 5)"))
  column = int(input("Enter a column number (between 0 and 7)"))
  
  if seats[row][column]==1:
    print("This seat is already booked.")
  else:
    print("This seat is empty.")

def bookSeat():
  print("Booking a Seat by Row/Column")
  #....
    
def bookSeatAtFront():
  print("Booking seat at the front")
  #....
  
def bookSeatAtBack():
  print("Booking seat at the back")
  #....
  

#Main Program Starts Here
print("+============================+")
print("+   CINEMA BOOKING SYSTEM    +")
print("+============================+")
print("")
print("1 - Book a seat by row/column")
print("2 - Book a seat at the front")
print("3 - Book a seat at the back")
print("x - Exit")

choice = input("Your Choice?")
if choice=="1":
  bookSeat()
  displayBookings()
elif choice=="2":
  bookSeatAtFront()
  displayBookings()
elif choice=="3":
  bookSeatAtBack()
  displayBookings()
elif choice=="x":
  print("Good Bye!")
else:
  print("Invalid Menu Option")
  print("Good Bye!")

Option 1:

Let the user enter a row and column number. If the seat is available, book it by changing the corresponding value in the array to a 1. If it’s not available carry on asking for a row and column number until a free seat is found.

View Solution

def bookSeat():
  booked = False
  while booked == False:
    row = int(input("Enter a row number (between 0 and 5)"))
    column = int(input("Enter a column number (between 0 and 7)"))

    if seats[row][column]==1:
      print("This seat is already booked.")
    else:
      print("This seat is empty.")
      print("Booking seat...")
      seats[row][column]=1
      print("We have now booked this seat for you.")
      booked=True

Option 2:

If the user chooses this option the program should automatically book the first seat available starting from the front row (row 0) from the left (column 0), and scanning each seat one by one until a free seat is found. The program should inform the user which seat (row/column) has been booked.

View Solution

def bookSeatAtFront():
  print("Booking seat at the front")
  for row in range(0,6):
    for column in range(0,8):
      if seats[row][column]==0:
        print("Booking seat...")
        print("Row: " + str(row))
        print("Column: " + str(column))
        seats[row][column]=1
        print("We have now booked this seat for you.")
        #Stop Searching
        return True
  #We scanned the whole theatre without finding an empty seat:
  print("Sorry the theatre is full - Cannot make a booking")
  return False

Option 3:

If the user chooses this option the program should automatically book the first seat available starting from the back row (row 5) from the right (column 7), and scanning each seat one by one until a free seat is found. The program should inform the user which seat (row/column) has been booked.

View Solution

def bookSeatAtBack():
  print("Booking seat at the back")
  for row in range(5,-1,-1):
    for column in range(7,-1,-1):
      if seats[row][column]==0:
        print("Booking seat...")
        print("Row: " + str(row))
        print("Column: " + str(column))
        seats[row][column]=1
        print("We have now booked this seat for you.")
        #Stop Searching
        return True
  #We scanned the whole theatre without finding an empty seat:
  print("Sorry the theatre is full - Cannot make a booking")
  return False

Challenge #2: Saving Bookings in a CSV file

Create a CSV file containing the following data:
0,0,1,1,0,1,1,1
0,1,1,0,0,1,0,1
1,0,0,1,0,1,1,0
0,1,1,1,0,0,0,1
0,0,1,1,0,1,0,0
1,0,1,1,0,0,1,1

When the program starts, the seats array should be initialised by reading the content of the CSV file.

View Solution

def loadBookings():
  file = open("seats.csv","r")
  row = 0
  for line in file:
    data = line.split(",")
          if len(data)==8: #Only process lines which contain 8 values
             for column in range (0,8):
                seats[row][column] = int(data[column])
             row = row + 1
  file.close()

When the user exit the program (option X), the content of the CSV file should be replaced with the content of the seats array.

View Solution

def saveBookings():
  file = open("seats.csv","w")
  for row in range(0,6):
    line=""
    for column in range(0,8):
      line = line + str(seats[row][column]) + ","
    line = line[:-1] + ("\n") #Remove last comma and add a new line
    file.write(line)    
  file.close()

To complete this challenge you will need to read more about how to read through a CSV file.

Challenge #3: Resetting the Array

Add an extra menu option (option 4). If this option is chosen, the seats array should automatically be reset so that all seats are reset to 0.

Challenge #4: Improvements

Can you think of any other features that could be useful to improve this cinema booking system? This could include:

A login screen so that only authorised staff can access the booking system,
An option to cancel a booking,
A message to inform the end-user of how many seats are left,
A message to inform the end-user when the theatre is full (all the seats have been booked),
Input validation (e.g. row number between 0 and 5, column number between 0 and 7),
Multiple bookings where the computer can identify if the user wants to book several (e.g. 2 or 3) consecutive seats on the same row,
etc.

Solution...

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

Tagged with: 2D Array, array, CSV, File Handling, Function, List, Procedure, subroutines

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

Multiplication using LMC

Iteration using LMC

LMC Simulators

Solution

LMC Instruction Set

LMC Simulators

Solution

LMC Instruction Set

LMC Simulators

Solution

LMC Instruction Set

LMC Simulators

LMC Instruction Set

Solution...

Binary Tree #1

Linked List

Binary Tree #2

Linked List

Binary Tree #3

Algebric Expression Trees

Boolean Expression Trees

Binary Tree?

Breadth-First Traversal Algorithm

Depth-First Traversal Algorithms

Binary Tree #1

Binary Tree #2

Binary Tree #3

Binary Tree #4

Python Code

Step 1: ASCII Art

Step 2: Create the Python code

Complete the Code

Testing

Extension Task

Video Tutorial / Solution

Solution...

Challenge #1: Booking Options

Option 1:

Option 2:

Option 3:

Challenge #2: Saving Bookings in a CSV file

Challenge #3: Resetting the Array

Challenge #4: Improvements

Solution...

Recent Posts

Our Latest Book