Homework 2: Harlem Shaking into 2020!

The goal of this assignment is for you to get some practice writing functions using while loops and recursion.

Setup and Handin

Setup

If you are using PyCharm, set up a project as in HW1. For the second homework problem, you will need this words file. Download it to your project directory, just as you did with the CSV file in HW1.

Handin

You may submit as many times as you want. Only your latest submission will be graded. This means that if you submit after the deadline, you will be using a late day – so do NOT submit after the deadline unless you plan on using late days.

The README template can be found here. Please follow the design and clarity guide–part of your grade will be for code style and clarity. After completing the homework, you will submit:

  • README.txt
  • cronut.py
  • cronut_test.py
  • hotline.py
  • hotline_test.py

Because all we need are the files, you do not need to submit the whole project folder. As long as the file you create has the same name as what needs to be submitted, you’re good to go!

If you are using late days, make sure to make a note of that in your README. Remember, you may only use a maximum of 3 late days per assignment. If the assignment is late (and you do NOT have anymore late days) no credit will be given.

Please don’t put your name anywhere in any of the handin files–we grade assigments anonymously!

You can follow this step-by-step guide for submitting assignments through gradescope here.

Helpful Things

Documentation

Staff Assistance

Your friendly TAs and Professor are here to help with this assignment! You can find our schedule for office hours here.

The Assignment

Greatest Cronut Deliverer (GCD)

In an effort to expand your startup, which specializes in producing and selling cronuts and avocado toast, you decide to reach out to Instagram influencers to promote your product.

You want to send identical gift packages to each influencer. However, you have a avocado toasts and b cronuts, where a is probably not equal to b. Determine the greatest number of identical gift packages you can send out to the influencers without having any leftover product.

To find the greatest number of packages you can send out, you come accross an algorithm that solves for the Greatest Common Divisor (GCD): given two numbers a and b, continuously subtract the smaller of the two from the larger until they are equal. More specifically:

  1. If a is equal to b, then your result is a and stop the algorithm.
  2. If a is greater than b, subtract b from a, updating the value of a. Repeat from Step 1.
  3. If b is greater than a, subtract a from b, updating the value of b. Repeat from Step 1.

Your tasks for this assignment are:

  1. Implement the GCD algorithm using one or more while loops in the function gcd_loop(a: int, b: int) -> int.
  2. Implement the same algorithm without loops using recursion in the function gcd_recur(a: int, b: int) -> int.
  3. Write exhaustive test cases for both gcd_loop and gcd_recur (hint: do these tests need to be different?) in cronut_test.py. Refer to the testing guide linked above.

4685463 25464

You found your old Nokia cellphone while you were Marie Kondo-ing your bedroom. You tried to read some of your old text messages, but you forgot that you dropped your phone in the toilet, changing all the letters to their corresponding numbers on the phone keyboard in the following way:

{
    2: ["a", "b", "c"],
    3: ["d", "e", "f"],
    4: ["g", "h", "i"],
    5: ["j", "k", "l"],
    6: ["m", "n", "o"],
    7: ["p", "q", "r", "s"],
    8: ["t", "u", "v"],
    9: ["w", "x", "y", "z"]
}

Luckily, you have access to a text file containing common English words, some of which show up in the messages you are trying to decode.

Your task, given a list of digits, is to determine the word that corresponds to those digits. For example, the sequence 25464 has 3**5 = 243 possible string outputs, most of which are meaningless (for instance, "ajgmg"). However, the output that actually corresponds to a word is "bling".

  1. Before you can determine the word, you need to find all possible combinations of characters that can be formed given the digits. Write the function find_combinations(code: list) -> list that takes in a list of digits and outputs all possible character combinations that can be formed from those digits. For example, for [2, 5, 4, 6, 4], you should get produce "ajgmg", "akgmg","bkimk", and so on–a list of length 243. Remember that you can add a character to the beginning of a string with +–for instance, "d" + "rake" == "drake".
  2. Now that you have all the possible character combinations given a list of digits, your task is to identify what words you were trying to say by cross referencing with the text file. Write the function real_words(combinations: list) -> list to interpret the corrupted texts. The function should take in a list of possible words and return the words in the list that are in your words.txt file. For instance, real_words(["aiaoqaioe", "champagne"]) should return ["champagne"]. You can get a list of all of the words in the file like this: words = open("words.txt").read().split("\n")
  3. Write a function decode(code: list) -> list that takes a list of digits and returns a list of possible decoded words. Implement this function by combining find_combinations and real_words. You should now be able to decode the name of this homework problem.
  4. Write exhaustive test cases for both find_combinations, real_words, and decode in hotline_test.py.

Note: Most digit keyboards allow you to choose letters by selecting a key multiple times (for example, if you hit the digit 2 three times you’ll get c rather than aaa three times in a row). This is not a feature you need to worry about, meaning that hitting the digit 2 three times in a row can result in aaa, abc, or bbc, but not c.

README

In your README.txt, include answers to the following questions:

  • Did you find it more intuitive to implement GCD with a loop or with recursion?
  • Did you discuss this assignment with any other students? Please list their cs logins.
  • How many late days are you using on this assignment?