ICS3U Learning To Problem Solve With Python Part 3
ICS3U Learning Goals
In this ICS3U lesson you will be learning how to
- Solve problems using a modular design that need to store data in Lists and Strings
- Break more complicated programs into more manageable pieces
- Write pseudo code using the input-processing-output method of problem solving.
- Add documentation to a python program
- Evaluate the solutions to more complex problems
Problem Solving in Computer Science
Recall from the first problem solving lesson, in ICS3U we solve a lot of problems in computer science using an algorithm. (A series of steps that lead you to the correct answer) The INPUT – PROCESSING – OUTPUT model of problem solving generally works pretty well in this course for solving straightforward computational problems
- Input – Lists the data needed to be stored or entered from the user
- Processing – The logic / math, steps needed to solve the problem
- Output – Lists what is required to be displayed on the screen when the program is running or finished
ICS3U Problem Solving Example
ICS3U Center of Gravity Program
Your task is to find the center of gravity in a system of planets in an alien solar system. To accomplish this task you will need to know the mass of each planet and their coordinates in Three Dimensional Space. This information will be represented in an ordered 4-tuple (m,x,y,z)
All the input data are positive integers. The first line of input is the number of planets. Then the 4 tuples are entered. All planet input on one line like in the example below separated by a comma
The center of gravity is a weighted average of the mass at each location. The coordinate is the total mass at each coordinate / total mass system
$$ x = \frac {(50)(20)+(20)(45)+(60)(80)}{50+20+60} $$
$$ y = \frac {(50)(60)+(20)(5)+(60)(40)}{50+20+60} $$
$$ z = \frac {(50)(100)+(20)(15)+(60)(55)}{50+20+60} $$
Here is the output. It should show the total mass of the system along with the coordinates
Watch Your Teacher Solve the Problem
Full Coded Solution
#Functions Needed for the Solution
def sumList(myList):
total = 0
for i in range(0, len(myList)):
total = total + myList[i]
return total
def weightedSum(list1,list2):
total = 0
for i in range(0, len(list1)):
total = total + list1[i]*list2[i]
return total
#Main Program
def main():
#Get the number of planets in a solar system
numPlanets = int(input("Please Enter the number of planets: "))
#Lists to hold all the data
m = []
x = []
y = []
z = []
#Read the data and store in lists
for i in range(0, numPlanets):
#Get Planet
planet = input("Enter planet: m,x,y,z ")
#Split the string and store in the lists
planetData = planet.split(",")
m.append(int(planetData[0]))
x.append(int(planetData[1]))
y.append(int(planetData[2]))
z.append(int(planetData[3]))
#Find the total mass of the solar system
totalM = sumList(m)
#Find the sum of the masses at each coordinate
totalX = weightedSum(m,x)
totalY = weightedSum(m,y)
totalZ = weightedSum(m,z)
#Find the center of mass
xCoordinate = round(totalX/totalM,1)
yCoordinate = round(totalY/totalM,1)
zCoordinate = round(totalZ/totalM,1)
#Ouput location
print("\nCentered Around: ")
print(totalM,",",xCoordinate,",",yCoordinate,",",zCoordinate)
#Call Main Function to Start the Program
main()
ICS3U Problem Solving Example
ICS3U Shift and Substitution Cipher
Consider the following definitions:
- Plaintext: A message that can be read in normal English
- Ciphertext: An encoded (scrambled) message that needs to be decoded (unscrambled) to plaintext
- Encode: Change plaintext to ciphertext
- Decode: Change ciphertext to plaintext
A simple shift and substitution cipher algorithm is one that each character in the plaintext is “shifted” a certain number of places down the alphabet.
For example if the shift is 2: A becomes C, F becomes H, Z becomes B
Here is an example of taking a plaintext message and encoding it
- Plaintext: defend the east wall of the castle
- Ciphertext: efgfoe uif fbtu xbmm pg uif dbtumf
If you want to decode the ciphertext message into plaintext, you need to know the shift value. One way to accomplish this is to decode the message with all 26 possible shift values and see what plaintext result is readable in English. This is not overly efficient but works as a brute force decoding algorithm.
Your job is to write two programs:
- Program 1: Take a plain text message and encode it. The shift value will be determined by the character that appears most often in the plaintext message. For example if the most common letter was ‘e’, use a shift of 5. Tie goes to the letter closer to the end of the alphabet
- Program 2: Take a ciphertext message generated from your first program and decode it
Example of Encoding
Example of Decoding
Watch Your Teacher Solve the Problem
Full Coded Solution
#Function Definitions
#Maps a message from an oldAlpha to a newAlpha
def mapMessage(oldAlpha,newAlpha,oldMessage):
newMessage = ""
#Cycle through each letter in the message to change
for letter in range(0,len(oldMessage)):
#only change non space characters
if oldMessage[letter]!= " " :
#Find the location of the letter to change
location = oldAlpha.find(oldMessage[letter])
#Change the letter
newMessage = newMessage + newAlpha[location]
else:
newMessage = newMessage + " "
return newMessage
#Determines the shift value based on letter count
def shiftValue(message):
normalAlpha = "abcdefghijklmnopqrstuvwxyz"
#Temp values for max characters and corresponding location
largest = 0
maxLoc = 0
#Cycle through each letter in the alphabet
for letter in range(0,len(normalAlpha)):
#Count the # of times the letter appears
count = message.count(normalAlpha[letter])
#Find the largest & record location
if count >= largest :
largest = count
maxLoc = letter
#shift is one value more than the index of the letter
return maxLoc + 1
#Shift cipher encoding
def encode(message):
#The normal alphabet for plaintext
normalAlpha = "abcdefghijklmnopqrstuvwxyz"
#Find the shift
shift = shiftValue(message)
#Create the ciphertext alphabet
newAlpha = normalAlpha[shift:]+normalAlpha[0:shift]
#Map the plaintext to the ciphertext
encoded = mapMessage(normalAlpha,newAlpha,message)
print(encoded)
#Shift cipher decoding
def decode(message):
#The normal alphabet for plaintext
normalAlpha = "abcdefghijklmnopqrstuvwxyz"
#Cylce through all shift values
for shift in range(0,26):
#Create the ciphertext alphabet
newAlpha = normalAlpha[shift:]+normalAlpha[0:shift]
#Map the message from ciphertext to plaintext
decoded = mapMessage(newAlpha,normalAlpha,message)
print(decoded)
#Main Program
def main():
print("1. Encode -> Most Common Letter")
print("2. Decode -> Brute Force - All Shifts")
choice = int(input("Choose: "))
if choice == 1:
m = input("Enter Plaintext:\n")
encode(m)
elif choice == 2:
m = input("Enter Ciphertext:\n")
decode(m)
else:
print("invalid")
#Call Main Function to Start the Code
main()
ICS3U Coding Questions
Try to code the following ICS3U questions using an IDE of your choice (Spyder, IDLE, Pycharm, etc). You will save those files on your computer for future reference.
Make sure you are completing the Input-Processing-Output Problem Solving Process before you start your code. Clearly evaluate the solution when finished.
Your design should be modular (use functions to solve the problem)
Each question has:
- A video of your teacher live coding and explaining the solution
- The final code used in the video.
Try your best to solve the problems yourself without looking at the solutions.
Make sure you test your programs with multiple different inputs to ensure it is functioning properly.
ICS3U Practice Question
Name Your File : “ICS3UrobbersLanguageCipher.py”
To encode a message:
Each consonant in the plain text message is replaced by three letters in the following order
- the original consonant itself
- the vowel closet to the consonant in the alphabet (eg. if the consonant is d, then the closet vowel is e), with the rule that if the consonant falls exactly between two vowels, then the vowel closer to the start of the alphabet will be chosen. (eg if the consonant is c, then the closet vowel is a)
- the next consonant in the alphabet following the original consonant (eg if the consonant is d, then the next consonant is f) except if the original consonant is z, in which case the next consonant will be considered z as well
Vowels in the plaintext message will remain the same (Vowels are a, e, i, o, u)
Write two programs: one that will encode the plain text message, and one that will decode a cipher text message
Encoding Example
Decoding Example
def encode(plainText):
encoded = ""
#Mapping Alphabets
consonantAlpha = "bcdfghjklmnpqrstvwxyz"
closetVowelAlpha = "aaeeeiiiiooooouuuuuuu"
nextConsonantAlpha = "cdfghjklmnpqrstvwxyzz"
#Cycle through each letter in the plaintext message
for i in range(0, len(plainText)):
#Copy original letter
encoded = encoded + plainText[i]
#Find the location of the plaintext letter in consonant list
location = consonantAlpha.find(plainText[i])
#if found a consonant then add closet vowel and next consonant
if location > -1:
encoded = encoded + closetVowelAlpha[location] + nextConsonantAlpha[location]
return encoded
def decode(cipherText):
decoded = ""
consonantAlpha = "bcdfghjklmnpqrstvwxyz"
#loop through each letter in the cipherText message
position = 0
while position < len(cipherText):
#Copy original letter
decoded = decoded + cipherText[position]
#Check if cipherText letter is a consonant
if consonantAlpha.find(cipherText[position]) > -1:
position = position + 3 #Found consonant so point 3 letters ahead
else:
position = position + 1 #Found vowel or space so point 1 letter ahead
return decoded
def main():
print("Pick 1 to encode: ")
print("Pick 2 to decode: ")
choice = int(input("Make your choice: "))
if choice == 1:
m = input("Enter the plainText: ")
encoded = encode(m)
print(encoded)
elif choice == 2:
m = input("Enter the cipherText: ")
decoded = decode(m)
print(decoded)
else:
print("invalid")
main()
ICS3U Practice Question
Name Your File : “ICS3Unecklace.py”
A necklace begins with two single digit numbers. The next number is obtained by adding the first two numbers together and saving only the ones digit. This process is repeated until the necklace closes by returning to the original two numbers
Write a program that helps you determine:
- The # of different possible lengths
- The smallest length necklace
- The largest length necklace
- The most common length necklace
#Function Definitions
#Generate Ones Digit-> always the remainder of a division by 10
def ones(num1,num2):
total = num1 + num2
return total % 10
#Generate the necklace
def getNecklace(firstNum, secondNum):
#Set the first two values of the necklace
necklace = [firstNum, secondNum]
position = 2
while True:
#Check if necklace is finished
if position > 3 and necklace[position - 1] == secondNum and necklace[position - 2] == firstNum :
break
else:
#Get the ones digit
nextNum = ones(necklace[position - 1],necklace[position - 2])
#Add the next number to the list
necklace.append(nextNum)
position = position + 1
return necklace
#Main Program -> Finds the length of all the possible necklaces for analysis
def main():
#Cycle through digits 1 -> 9 for each combination of starting values
for first in range(1,10):
for second in range(1,10):
#Generate the necklace
theNecklace = getNecklace(first,second)
#Print the length of the necklace and look at output to answer questions
print(len(theNecklace))
#Call main function to start the program
main()