HW 1: Puzzling through Functions

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:

1. 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

2. 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.

3. 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.

4. 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).

""" 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()

""" 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()

""" 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()

""" 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()

As per the Syllabus: you should use these to support your learning. Do not look at solutions until you have attempted the work. It is up to you to best leverage this resource.