Homework 6

Due Tuesday 16-March, at ~~8pm~~10pm

To start

Create a folder named ‘hw6’
Create a new file, hw6.py, in that folder.
Edit hw6.py and add the functions and some testcases as required.
When you have completed and fully tested hw6, submit hw6.py to Gradescope.

For this hw, you may submit up to 10 times, but only your last submission counts.

Some important notes

This homework is solo. You may not collaborate or discuss it with anyone outside of the course, and your options for discussing with other students currently taking the course are limited. See the academic honesty policy for more details.
After you submit to Gradescope, make sure you check your score. If you aren’t sure how to do this, then ask a CA or Professor.
There is no partial credit on Gradescope testcases. Your Gradescope score is your Gradescope score.
Read the last bullet point again. Seriously, we won’t go back later and increase your Gradescope score for any reason. Even if you worked really hard and it was only a minor error…
Do not hardcode the test cases in your solutions.
We are not giving you any starter code this week. That means you need to create your file from scratch and include your own testcases. For writing testcases, follow the style of testcases uses in the previous homeworks.
Remember the course’s academic integrity policy. Solving the homework yourself is your best preparation for exams and quizzes; cheating or short-cutting your learning process in order to improve your homework score will actually hurt your course grade long-term.
Your code will be graded for style. Check the style notes on the website for details.

Limitations

Do not use try/except or classes this week. The autograder will reject your submission entirely if you do.

A few notes on the problems marked recursive:

You may (and in fact must) finally use recursion this week.
The recursive problems require that you use recursion meaningfully in order to receive the points.
You also may not use loops -- no for loops or while on the problems marked recursive.
You may use helper functions, so long as they are not iterative.
You may use wrapper functions -- that is, your solution function may itself be a non-recursive (but also non-iterative) wrapper around a recursive helper function.
You may only use builtin functions if they don't iterate over something. So in particular, among many other builtins you may not use this week, you may not use sum, sort, sorted, min, or max this week (you can write your own recursive versions of these if you wish, though that is not required, and we did not do that for our sample solutions).

Problems

Midsemester Survey [5 pts]
Take the midsemester survey linked from Piazza. Be sure to also fill out the second survey (linked at the end of the first) so that you get the points.

The survey is due Thursday, March 11 at 5:00pm.

friendsOfFriends(d) [10 pts]
Background: we can create a dictionary mapping people to sets of their friends. For example, we might say:
d = { } d["jon"] = set(["arya", "tyrion"]) d["tyrion"] = set(["jon", "jaime", "pod"]) d["arya"] = set(["jon"]) d["jaime"] = set(["tyrion", "brienne"]) d["brienne"] = set(["jaime", "pod"]) d["pod"] = set(["tyrion", "brienne", "jaime"]) d["ramsay"] = set()
With this in mind, write the function friendsOfFriends(d) that takes such a dictionary mapping people to sets of friends and returns a new dictionary mapping all the same people to sets of their friends of friends. For example, since Tyrion is a friend of Pod, and Jon is a friend of Tyrion, Jon is a friend-of-friend of Pod. This set should exclude any direct friends, so Jaime does not count as a friend-of-friend of Pod (since he is simply a friend of Pod) despite also being a friend of Tyrion's.

Thus, in this example, friendsOfFriends should return:
{ 'tyrion': {'arya', 'brienne'}, 'pod': {'jon'}, 'brienne': {'tyrion'}, 'arya': {'tyrion'}, 'jon': {'pod', 'jaime'}, 'jaime': {'pod', 'jon'}, 'ramsay': set() }
Note 1: your function should not modify the initial provided dictionary!

Note 2: you may assume that everyone listed in any of the friend sets also is included as a key in the dictionary.

Note 3: you may assume that a person will never be included in their own friend set. You should also not include people in their own friends-of-friends sets!

Note 4: you may not assume that if Person1 lists Person2 as a friend, Person2 will list Person1 as a friend! Sometimes friendships are only one-way.

Hint: How is this different or similar to the facebook friends problem?

recursive alternatingSum(lst) [10 pts]
Write the function alternatingSum(lst) that takes a possibly-empty list of numbers, lst, and returns the alternating sum of the list, where every other value is subtracted rather than added. For example: alternatingSum([1,2,3,4,5]) returns 1-2+3-4+5 (that is, 3). If lst is empty, return 0.

recursive onlyEvenDigits(L) [10 pts]
Without using iteration and without using strings, write the recursive function onlyEvenDigits(L), that takes a list L of non-negative integers (you may assume that), and returns a new list of the same numbers only without their odd digits (if that leaves no digits, then replace the number with 0). So: onlyEvenDigits([43, 23265, 17, 58344]) returns [4, 226, 0, 844]. Also the function returns the empty list if the original list is empty. Remember to not use strings. You may not use loops/iteration in this problem.

Hint: We wrote a recursive helper function onlyEvens(n) that takes an integer n and returns the same integer but with all the odd digits removed. So onlyEvens(1234) returns 24.

recursive powersOf3ToN(n) [10 pts]
Write the function powersOf3ToN(n) that takes a possibly-negative float or int n, and returns a list of the positive powers of 3 up to and including n. As an example, powersOf3ToN(10.5) returns [1, 3, 9]. If no such powers of 3 exist, you should return the empty list.

Hints:
1. No matter how you solve this, it's crucial that you have just one additional recursive call per power of 3. So you can't just count up to n (or down from n) and include each value if it is a power of 3. That will stack-overflow.
2. Our recommended approach to solving this uses a recursive helper function powersOf3ToNHelper(n, powerOf3) that takes both n and a powerOf3 (so 1, 3, 9, etc), and returns a list of the powers of 3 starting from that power up to the largest power of 3 up to an including n. So powersOf3ToNHelper(30, 9) returns [9, 27].
3. Another approach which is perhaps less recommended (as you have to properly manage floating-point issues) does not use a helper function, but instead uses log_3(n) to determine the largest power of 3 up to n.

Turtle Script [55 pts]

This problem is designed to get you more practice with using dictionaries, processing strings and get you thinking about recursion. This homework has been adapted from the presentation of Eric Roberts for nifty assignments at SIGCSE 2013.

Turtle Refresher

turtle is a Python module that allows for drawing of simple figures. In order to use it, you give an imaginary on-screen turtle commands regarding where to go, and it draws a line along its path.

The details of turtle library can be found at http://docs.python.org/library/turtle.html

Consider the following very simple turtle program which makes use of some basic turtle functionality to draw two squares:

import turtle
turtle.pendown()
turtle.left(90)
turtle.forward(50)
turtle.left(90)
turtle.forward(50)
turtle.left(90)
turtle.forward(50)
turtle.left(90)
turtle.forward(50)
turtle.penup()
turtle.forward(100)
turtle.pendown()
turtle.left(90)
turtle.forward(50)
turtle.left(90)
turtle.forward(50)
turtle.left(90)
turtle.forward(50)
turtle.left(90)
turtle.forward(50)
turtle.penup()
turtle.forward(100)

(You should run this in Python and convince yourself you understand how it works.)

Turtle Script

In order to simplify the usage of turtle, we have designed a new language to writing turtle programs. We call it Turtle Script. A Turtle Script program is specified as a string consisting of a sequence of commands. For example, consider the following Turtle Script program:

F120 L90 F120 L90 F120 L90 F120

This program moves the turtle in a square 120 pixels on a side, ending up in the same position and orientation as when it started, like so:

Repetition

Turtle Script also includes the concept of repetition. If you enclose a sequence of commands in curly braces, you can repeat that entire sequence any number of times by preceding that block of commands with the letter X followed by the desired number of repetitions. The program to draw a square can therefore be simplified like this:

X4 {F120 L90}

In English pseudocode form, this program therefore has the following effect:

Repeat the following sequence of commands 4 times
  Move forward 120 pixels.
  Turn left 90 degrees.

Repetitions can be nested to any level. You could, for example, use the program:

X4 {X4 {F120 L90} L10}

to draw two squares with a 10-degree left turn in the middle.The figure after drawing these four squares looks like this:

Functions

Turtle Script also includes functions. You can defne a function by enclosing the body of the function in braces and then preceding the braces with the command M followed by a single character name for the function. The following example shows a definition of a function called S that draws a square:

MS {F120 L90 F120 L90 F120 L90 F120 L90}

The keyword M specifies that the following is a function name, followed by function body enclosed in braces. Remember that M command only defines a function but does not execute it. After this function has been defined, you can use the function name to call this function. Here is an example of defining a function and then calling it two times:

MS { X4 { L90 F50}} S U F100 D S

This program will create two squares in a single line separated by 50 pixels.

Turtle Command Summary

Command	Description
`Fn`	Move the turtle forward by n pixels. If n is missing move by default value of 50 pixels.
`Ln`	Turn the turtle left by n degrees, where n defaults to 90
`Rn`	Turn the turtle right by n degrees, where n defaults to 90
`D`	Calls the pendown function from Turtle
`U`	Calls the penup function from Turtle
`Xn cmds`	Repeats the specified block of commands n times.
`MA cmds`	Defines a function A where A is any single character not already reserved. The function A consists of the commands specified in the block. A cannot be one of the other commands (F, L, R, D, U, X, or M).
`A`	Execute the function A. A is just a placeholder, you can use any character to define a function. A cannot be one of the other commands (F, L, R, D, U, X, or M).

Functions to Write

Here are the functions you should write while solving this problem.

Function 1: `tokenizeTurtleScript(program)`

Write a function called tokenizeTurtleScript(program) which, given a Turtle Script program, return a list of commands in that program. The function should break up the input string into individual commands and return a list containing commands as strings.

The most common kind of token in a turtle program is a command character (typically a letter, although any non-whitespace character is legal), which is typically followed by a sequence of decimal digits. For example, the command F120, which moves the turtle forward 120 pixels, is a single token in a turtle program. All command listed in the table above are individual tokens, including repetition and function definitions.

In addition, spaces are not required between tokens but are permitted for readability. These rules mean, for example, that you could rewrite the program that draws a square as:

F120L90F120L90F120L90F120

even though doing so makes the program much more difficult for people to read.

Consider the following examples:

tokenizeTurtleScript("F120L90F120L90F120L90F120") returns
['F120', 'L90', 'F120', 'L90', 'F120', 'L90', 'F120']

tokenizeTurtleScript("X4 {F120 L90} U F200 X4 {F120 L90}") returns
['X4{F120L90}', 'U', 'F200', 'X4{F120L90}']

tokenizeTurtleScript("MS { X4 { L90 F50}} S U F100 D S") returns
['MS{X4{L90F50}}', 'S', 'U', 'F100', 'D', 'S']

Note: This problem is made much easier if you plan ahead by choosing good helper functions.

Function 2: `convertTurtleScript(program, funcs)`

Write a function convertTurtleScript(program, funcs) that will convert a Turtle Script program to a Python program. It should take as arguments a Turtle Script program and a dictionary consisting of all the functions defined so far in the program. The dictionary will contain function names as keys and function code as values.

The convertTurtleScript function has the responsibility of taking the program and translating each token to the appropriate command for turtle in Python. For example, given the program tokens:

['F120', 'L90', 'F120', 'L90', 'F120', 'L90', 'F120']

The convertTurtleScript function will have to translate each token into the appropriate function call in Python. Thus, executing the F120 token needs to invoke the function call turtle.forward(120). Similarly, executing the L90 token needs to invoke a call to turtle.left(90)

Notes:

You should call tokenizeTurtleScript in order to convert the program to tokens, and then execute the tokens one at a time.
This function does not return anything. Instead, it prints the Python program.
You should make this function recursive when necessary. Recursion makes handling the repetition tokens (X) and the function tokens (M) much easier.
The funcs argument that is passed to this function is a dictionary to map function names to function code. Recall that functions are defined as part of Turtle Script. Hence, as you are executing commands you will come across function definitions. When you do, add those functions to the funcs dictionary. Later, if a function is being called, you can retrieve that function’s commands from the dictionary. For the initial call to convertTurtleScript, you should just pass an empty dictionary.

Consider the following examples.

First,

p = "F120 L90 F120 L90 F120 L90 F120"
funcs = dict()
convertTurtleScript(p, funcs)

will print out:

turtle.forward(120)
turtle.left(90)
turtle.forward(120)
turtle.left(90)
turtle.forward(120)
turtle.left(90)
turtle.forward(120)

Second,

p = "MS { X4 { L90 F50}} S U F100 D S"
funcs = dict()
convertTurtleScript(p, funcs)