CMU 15-112 Summer 2020: Fundamentals of Programming and Computer Science
Homework 11 (Due Fri 12-Jun, at 5:00pm)

• This assignment is SOLO. This means you may not look at other student's code or let other students look at your code for these problems. See the syllabus for details.


• To start:
  1. Create a folder named 'hw11'
  2. Download hw11.go
  3. Edit hw11.go using VSCode
  4. When you are ready, submit hw11.go to Autolab. For this hw, you may submit up to 10 times, but only your last submission counts.
• You may finally (and in fact must) use recursion in this assignment!
• Do not hardcode the test cases in your solutions.
• NOTE: For the next few days, assignments in Go will be manually graded.

1. powersOf3ToN(n int) []int [30pts]
   Write the function powersOf3ToN(n int) []int that takes a possibly-negative int n, and returns a list of the positive powers of 3 up to and including n, or the empty list if no such values exist. As an example, powersOf3ToN(10) returns []int{1, 3, 9}. You must use recursion for this problem, following the same rules as collab11.


2. friendsOfFriends(friends map[string]cs112.StringSet) (map[string]cs112.StringSet) [30pts]
   Background: we can create a map mapping people to sets of their friends. For example, we might say:
   
   mkSet := cs112.StringSetFromSlice friends1 := map[string]cs112.StringSet{ "jon": mkSet([]string{"tyrion","arya"}), "tyrion": mkSet([]string{"pod","jaime","jon"}), "arya": mkSet([]string{"jon"}), "jaime": mkSet([]string{"brienne","tyrion"}), "brienne": mkSet([]string{"jaime","pod"}), "pod": mkSet([]string{"brienne","tyrion","jaime"}), "ramsay": mkSet([]string{}), }
   
   With this in mind, write the function friendsOfFriends that takes such a map 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:
   mkSet := cs112.StringSetFromSlice map[string]cs112.StringSet{ "tyrion": mkSet([]string{"brienne","arya"}), "pod": mkSet([]string{"jon"}), "brienne": mkSet([]string{"tyrion"}), "arya": mkSet([]string{"tyrion"}), "jon": mkSet([]string{"jaime","pod"}), "jaime": mkSet([]string{"jon","pod"}), "ramsay": mkSet([]string{}), }
   
   Note 0: you may use iteration for this problem
   
   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. =(