HW 1: Puzzling through Functions
Submission Details
Due: 2/4
Submit via Gradescope:
5 files in total
secret_messages.py
pillow_stacks.py
towers_of_hanoi.py
river_crossing.py
A PDF that contains your self-assessment & reflection
Instructions
Log in to Coding Rooms
Navigate to the second Assignment of HW 1: Puzzling through Functions
Work through each part of the homework by using the corresponding script in the Coding Rooms assignment.
When you're ready to submit, download the 4 files (omit main.py) for Gradescope.
Review the solutions to perform a self-assessment and write your reflection. You may find it more useful to do this for each part or you may wish to wait until you've tried all 4 puzzles.
You may write up your self-assessment and reflection in whatever format is most comfortable for you (written on paper, typed in a Word or Google Doc, etc.), but you must convert it to a PDF before submitting. Please ask if you need help with this!
Submit the PDF to Gradescope and name it SelfAssessmentReflection.pdf.
Homeworks are an opportunity to engage with the material and practice your programming skills. To support you, solutions will be available on moodle. It is your responsibility to engage with them in a way that strategically moves your learning forward. You should:
Attempt the homework without looking at the solutions.
Review the solutions; if you were stuck, you may revise your homework. You may find yourself iteratively reviewing and revising to best support your learning.
When you submit your homework, you will be required to complete a self-assessment and reflection:
Give yourself an assessment mark on the initial attempt:
✘ if you did not complete it
✓- if you completed it, but were very far from the solution
✓ if you completed it and essentially had the solution
✓+ if you completed it correctly, including precise communication
? if you are unsure as to whether or not you completed it
Provide a short reflection as to why you earned that mark, such as:
I did not understand how to get started, and it was too close to the deadline to visit support hours.
I got stumped by a bug where my program entered an infinite loop.
If you used the solutions to revise your work, describe what you needed to change, as in:
I modified the style of my conditional when I saw a simpler approach in the solutions.
I was so stuck that the majority of my submission is based on the solutions.
Ask specific questions on portions that are still confusing, such as:
Why does it cause an error when I returned "1" instead of 1?
[Optional] Provide one hint for the homework (to your past self or future student).
Starter code
secret_messages.py
""" Mary Lyon has left us two coded messages with some cryptic instructions about
using any two secret shares to find the keys for decoding each.
You must print both decode both messages to receive her wisdom! """
secretMessage1 = "TtLhOqeGkrWPeEJ CAiUnshJ SnnTqoPLtbvhmBiOpnLugIX UZironLV tAtqbhwpeIe XRuIlnjtiKlvxqebcrwXshreHI uTtAuhuGaJHtil EsIMY bZfwnepjaAjrvr,rN VTbjzuEatwy jmtQBhbKauwtiM IgIgb qYsOihUzaEClTMlKU grnFToNXtay DakFnnXooZFwuD NlaHvlGQlpA UVmRByjG UQdpruWvtisydu,Pm nBoIsrBY JwsZWhhKafZlUOlWy qcfeWaoGivpllF adtAboqA DddZHoYf CWikdton.YG"
# secret shares for message 1's key:
# (10,-217)
# (2,-41)
# (-2,47)
# (-10,223)
secretMessage2 = "GruGkoPInw SVsXwqofQhcPPLeHFCZrAjJeeKTNx dEWtnlAgmooJMU aCJqoJxEmnfZFTeiRvj FlyUeRfQDlACpvsuJScevCBx tYIMwGddMiMcIGlyqsIlxigu JWgwgwelYovHhG.djZZ etNVDyAdnoakBn wZsvwKQXXhzoESaExlxtikBo QWvEnGRipoiFXu WRzcoInxynrfHCeYsyz zLWueJcnVlxVoHsJiOFeDaBk eLWswZocuiWnUrlktZhlrjks HPwrdKfvYoHTdP.jdmw"
# secret shares for message 2's key
# (-9,203)
# (2,-39)
# (-10,225)
# (8,-171)
def shamirsSecretDecoder( x1, y1, x2, y2 ):
""" Given two points (x1, y1) and (x2, y2), unlock a secret value by
finding the y-intercept of the line determined by these two points.
This is a 2-dimensional version of Shamir's secret sharing. """
# compute the slope and assign it to a variable named m
yDiff = y2 - y1 # compute the difference between the y-coordinates
xDiff = x2 - x1 # compute the difference between the x-coordinates
m = yDiff/xDiff # the slope is the y-coordinate difference over the x-coordinate difference
# compute the y-intercept of the line and assign it to a variable b
b = y1 - m*x1
return b
def keepLettersAtPositions( message, x ):
""" Keep every xth letter. Note this always keeps the first letter, as 0 is
considered a multiple of every number.
Examples:
if multiple is 2, this will keep every letter whose index is a multiple of x
keepLettersAtPositions( "Hrenlwlnos", 2 ) -> "Hello"
if multiple is 3, this will keep every third letter
keepLettersAtPositions( "MecHiBCse", 3 ) -> "MHC"
"""
cleanedMessage = "" # we will accumulate into this variable
# iterate over the valid indices in the message string
for i in range( len(message) ):
if i%x == 0: # if the index is a multiple of x
cleanedMessage += message[i] # keep the letter by adding it to the string
return cleanedMessage # return this accumulated message
def main():
# MODFIY/FILL IN YOUR SOLUTION FROM HERE
# YOU MUST PRINT BOTH DECODED MESSAGES
# we decoded the first message together in class
# compute the key by picking two of the points
# and passing them as parameters to the decoder function
key1 = shamirsSecretDecoder( 2, -41, -2, 47 )
# use the newly discovered key to decode the first message
decodedMessage1 = keepLettersAtPositions( secretMessage1, key1 )
# we won't see it if we don't print it!
print( decodedMessage1 )
if __name__ == "__main__":
main()
pillow_stacks.py
""" This program provides a set of functions for trying to solve a pillow stacking puzzle.
You start with stacks of pillows, some of differing heights.
Your goal is to make all the stacks the same height (so you can sleep!).
You can add a pillow to the top of a stack (this is a single move).
You can remove a pillow from the top of a stack (this is also a single move). """
# the bed is a list of numbers tracking the number of pillows in each stack
# we start labeling pillow stacks at 0, so bed1 has 2 pillows in stack 0, 4 in stack 1, ...
bed1 = [ 2, 4, 3, 4, 6 ]
bed2 = [ 6, 2, 5, 7, 4, 5 ]
def addPillow( bed, stackIndex ):
""" Add a pillow to the stack of pillows at stackIndex. """
bed[stackIndex] = bed[stackIndex] + 1 # add one to the number of pillows on that stack
# if we now have equal stacks
if equalStacks( bed ):
# congratulations!
print( f"Congratulations, you can sleep on {len(bed)} stacks of pillows!" )
def removePillow( bed, stackIndex ):
""" Remove a pillow from the stack of pillows at stackIndex.
If there are no pillows, this does nothing. """
# if there are pillows to remove
if bed[stackIndex] > 0:
bed[stackIndex] = bed[stackIndex] - 1 # subtract one from the number of pillows on that stack
# if we now have equal stacks
if equalStacks( bed ):
# congratulations!
print( f"Congratulations, you can sleep on {len(bed)} stacks of pillows!" )
def equalStacks( bed ):
""" Check if all the stacks have the same height. If so, return True; otherwise, return False. """
# how many pillows are in the first stack?
numPillowsInFirstStack = bed[0]
# iterate over the pillow stacks
for pillowHeight in bed:
# if we don't have a matching number of pillows
if not (pillowHeight == numPillowsInFirstStack):
# then we know we should return False - we don't have equal stacks
return False
# if we make it here, we never hit the return statement in line 36
# that means all stacks are equal and we should return True
return True
def main():
# MODFIY/FILL IN YOUR SOLUTION FROM HERE
# we worked on bed1 together in class
#
# let's work on bed1: [ 2, 4, 3, 4, 6 ]
# we'll try to get 4 pillows in each stack
# add two pillows to stack 0
addPillow( bed1, 0 )
addPillow( bed1, 0 )
# add one pillow to stack 2
addPillow( bed1, 2 )
# remove two pillows from stack 4
removePillow( bed1, 4 )
removePillow( bed1, 4 )
# NOW WORK ON bed2: [ 6, 2, 5, 7, 4, 5 ]
if __name__ == "__main__":
main()
towers_of_hanoi.py
""" This program provides a set of functions for playing the Towers of Hanoi.
The disks start on the far left tower;
to win, all disks must be moved to the far right tower.
Only one disk may be moved at a time, from the top of a tower onto a tower
that is empty or has a larger disk on its top. """
# towers is a list of tower lists; each tower list has the top of the tower to the right
# the entries in a tower list are int values that store the width of the
towers = [[3,2,1],[],[]]
def moveDisk( fromIndex, toIndex ):
""" If the move is allowed, takes the disk on top of the tower at the fromIndex
and moves it to the top of tower at the toIndex. For example moveDisk(0,2) tries
to move the disk on the top of the leftmost tower to the rightmost tower."""
# if the move is permitted
if permittedMove( fromIndex, toIndex ):
# remove the disk and store it in a variable diskToMove
diskToMove = towers[fromIndex].pop()
# add it to the top of the tower (end of the list)
towers[toIndex].append( diskToMove )
# print and check status of the game
printTowers()
checkWin()
def permittedMove( fromIndex, toIndex ):
""" Checks if the move is permitted: when the disk being picked up is smaller
than the disk on top of the intended destination.
Returns True if the move is permitted and False otherwise. """
# get the list representing each involved tower
fromTower = towers[fromIndex]
toTower = towers[toIndex]
# not permitted if the fromTower is actually empty
if len(fromTower) == 0:
print( "Nothing to move" )
return False
# permitted if the toTower is actually empty
elif len(toTower) == 0:
return True
else:
# get the top of the fromTower
fromDisk = fromTower[len(fromTower)-1]
# and the top of the toTower
toDisk = toTower[len(toTower)-1]
# not permitted if the from disk is larger than disk it will move to
if fromDisk > toDisk:
print( "Cannot move a larger disk on top of a smaller one")
return False
else:
return True
def checkWin():
""" Check if the game has been won: if all disks are on the rightmost tower """
# all disks are on the right precisely when the first and second towers are empty
if len(towers[0]) == 0 and len(towers[1] ) == 0:
print( "Congratulations, you won!" )
def printTowers():
""" Print the current state of the game. """
padding = 5 # characters between the towers
towerDisplay = "" # to hold the full display
# find the max disk size, which determines how height the pegs are
maxDiskSize = 0 # starting value for finding the max disk
for tower in towers: # iterate over each tower
if len(tower) > 0 and max(tower) > maxDiskSize: # new max
maxDiskSize = max(tower) # update it
# build the output string by iterating from the top level down
for level in reversed(range(maxDiskSize)):
# for each towerIndex
for towerIndex in range(3):
# check if the tower is empty at that level
if level + 1 > len( towers[towerIndex] ):
towerDisplay += "|".center(2*maxDiskSize + 5, " " )
# otherwise, there is a disk
else:
currentDisk = towers[towerIndex][level] # the disk to display
# double width with peg in the middle
diskDisplay = "-"*currentDisk + "|" + "-"*currentDisk
# center and remember padding between towers
towerDisplay += diskDisplay.center(2*maxDiskSize + padding, " " )
towerDisplay += "\n" # carriage return to have next level on the next line
towerDisplay += "="*(6*maxDiskSize + 3*padding) # base underneath all towers
print( towerDisplay ) # print the built display
def main():
printTowers() # display the starting state
# MODFIY/FILL IN YOUR SOLUTION FROM HERE
# YOU MUST GET ALL DISKS TO THE RIGHTMOST TOWER
# is this a good starting move?
moveDisk( 0, 2 ) # move the disk from the leftmost tower -> rightmost tower
if __name__ == "__main__":
main()
river_crossing.py
""" This program provides a set of functions for trying out the River Crossing puzzle.
You start on the right bank with a wolf, sheep and a cabbage. You must get them all
to the left bank using a boat that holds only one passenger (other than you).
But be careful...
If you leave the wolf and sheep unattended, the wolf will eat the sheep, and you lose.
If you leave the sheep and the cabbage unattended, the sheep eats the cabbage, and you lose. """
# keep track of the world state
world = {
"boat" : [], # the boat starts empty
"right" : ["sheep", "wolf", "cabbage"], # all critters on the right bank
"left": [], # no one is on the left
"you" : "right" # you are also on the right
}
def printWorld():
""" Print out the state of the world. """
print( f"Currently:\n - You are on the {world['you']} bank")
print( f" - The left bank has: {world['left']}")
print( f" - The right bank has: {world['right']}")
print( f" - The boat has: {world['boat']}\n")
def loadBoat( passenger ):
""" Attempt to load the passenger into the boat. """
# where are you?
yourLocation = world["you"]
# make sure the passenger is on the same side
if passenger in world[yourLocation]:
# move the passenger of that bank
world[yourLocation].remove( passenger )
# move the passenger to the boat
world["boat"].append(passenger)
print( f"You loaded the {passenger} into the boat.")
else:
print( f"No can do! You're not on the same bank as the {passenger}...")
def rowBoat():
""" Row the boat to the opposite bank. Then check if you won/lost the game. """
# where are you?
yourLocation = world["you"]
# row the boat and move you to the other side
yourLocation = oppositeSide(yourLocation)
# make sure the world is updated to know this
world["you"] = yourLocation
print( f"You rowed the boat to the {yourLocation} bank.")
# was there a passenger with you?
if len( world["boat"] )> 0:
# unload the passenger
passenger = world["boat"].pop()
# put them on bank
world[yourLocation].append(passenger)
print( f"You unloaded the {passenger} onto the {yourLocation} bank.")
# check if the game is over
checkGameStatus()
# print the current world
printWorld()
def oppositeSide( location ):
""" Convenience method for switching "left" <-> "right" values. """
if location == "left":
return "right"
else:
return "left"
def checkGameStatus():
""" Check if you won the game by getting everyone to the left bank
or if you lost the game by leaving the wolf and sheep alone or
by leaving the sheep and cabbage alone.
If you've lost, the program ends. Otherwise, program execution will continue. """
# where are you?
yourLocation = world["you"]
# did you win? you need to be on the left bank with all 3 items
if yourLocation == "left" and len(world[yourLocation]) == 3:
print( "Congratulations! You won!!\n")
# otherwise, did you lose?
else:
# if the sheep isn't with you and the cabbage isn't with you
if "sheep" not in world[yourLocation] and "cabbage" not in world[yourLocation]:
# then they must be unattended together...
world[oppositeSide(yourLocation)].remove( "cabbage") # the sheep eats the cabbage
print( "Uh oh, you lost... The sheep just ate the cabbage." )
exit() # end the program
# similarly, if the wolf isn't with you and the sheep isn't with you
if "wolf" not in world[yourLocation] and "sheep" not in world[yourLocation]:
# then they must be unattended together...
world[oppositeSide(yourLocation)].remove( "sheep") # the wolf eats the sheep
print( "Uh oh, you lost... The wolf just ate the sheep." )
exit() # end the program
def main():
printWorld() # display the starting state
# MODFIY/FILL IN YOUR SOLUTION FROM HERE
# YOU MUST GET THE WOLF, SHEEP & CABBAGE TO THE LEFT BANK
loadBoat( "wolf" ) # is this a good starting move?
rowBoat()
if __name__ == "__main__":
main()
Part 1: The Second Secret Message
It's your turn to decode Mary Lyon's second message (you may want to refer back to this page).
Pick up where we left off in class and decode the second message.
You'll need to print out the decoded message to get the autograded points on Gradescope.
GruGkoPInw SVsXwqofQhcPPLeHFCZrAjJeeKTNx dEWtnlAgmooJMU aCJqoJxEmnfZFTeiRvj FlyUeRfQDlACpvsuJScevCBx tYIMwGddMiMcIGlyqsIlxigu JWgwgwelYovHhG.djZZ etNVDyAdnoakBn wZsvwKQXXhzoESaExlxtikBo QWvEnGRipoiFXu WRzcoInxynrfHCeYsyz zLWueJcnVlxVoHsJiOFeDaBk eLWswZocuiWnUrlktZhlrjks HPwrdKfvYoHTdP.jdmw
(-9,203)
(-10,225)
(2,-39)
(8,-171)
Part 2: Who needs sleep?
(Inspired by a talk of Friday Agbo)
You're trying to sleep, but your bed is covered in stacks of pillows. The thing is... you need them all to be the same height in order to sleep! How will you solve this pillow stacking puzzle?
You start with stacks of pillows, some of differing heights.
Your goal is to make all the stacks the same height (so you can sleep!).
You can add a pillow to the top of a stack (this is a single move).
You can remove a pillow from the top of a stack (this is also a single move).
We worked through bed1 in class.
You'll need to work on bed2 and get all 6 stacks to be the same height to get the autograded points on Gradescope.
Part 3: Towers of Hanoi
The Towers of Hanoi is a puzzle with 3 "tower" pegs and (for us) 3 disks. Here are some additional details:
The disks are sized small, medium and large.
To start, the disks are stacked on the left tower.
The goal of the puzzle is to move all 3 disks to the right tower.
You can only move one disk at a time.
You can only take a disk from the top of a tower's stack.
You can only place a disk on the top of a tower's stack and only if the disk you are placing is smaller than the disk it is landing on.
The file towers-of-hanoi.py has functions to work through the puzzle.
Look through the program and figure out where your code will go.
Run the code and look at the output to understand what you have access to. You'll notice that the Console prints out the starting configuration first:
-|- | |
--|-- | |
---|--- | |
=================================
You will need to invoke the moveDisk function to implement a solution to the puzzle.
Use this version of the game (and brainstorm with a peer) to come up with your solution. You should write down the moves you plan on making before you try to invoke the corresponding functions!
You'll need to get all three disks stacked on the right tower like this to get the autograded points on Gradescope:
| | -|-
| | --|--
| | ---|---
=================================
Part 4: River Crossing
There is a family of River Crossing puzzles that generally require you to move a set of objects from one bank of a river to the other. Here are some additional details:
We will work with the version where there are 3 objects for you to move: a wolf, a sheep and a cabbage.
You are all on the right bank of the river. You need to all be on the left bank to solve the puzzle.
You have access to a boat that will carry one passenger (other than yourself).
If you leave the wolf and the sheep unattended, the wolf will eat the sheep.
If you leave the sheep and cabbage unattended, the sheep will eat the cabbage.
The file river-crossing.py has functions to work through the puzzle.
Look through the program and figure out where your code will go.
Run the code and look at the output to understand what you have access to. You'll notice that the Console prints out the current state of the world first, then the program ends:
Currently:
- You are on the right bank
- The left bank has: []
- The right bank has: ['sheep', 'wolf', 'cabbage']
- The boat has: []
You loaded the wolf into the boat.
You rowed the boat to the left bank.
You unloaded the wolf onto the left bank.
Uh oh, you lost... The sheep just ate the cabbage.
You will need to invoke the loadBoat and rowBoat functions to implement a solution to the puzzle.
Use this version of the game (and brainstorm with a peer) to come up with your solution. You should write down the moves you plan on making before you try to invoke the corresponding functions!
You'll need to get all three objects to the left bank to see a message like this to get the autograded points on Gradescope:
Congratulations! You won!!