15-112
Spring 19

Home

Syllabus

Schedule

Staff

Gallery

Piazza

Autolab

OH Queue

CMU 15-112 Spring 2019: Fundamentals of Programming and Computer Science
Homework 4 (Due Sunday 10-Feb, at 5pm)

    Collaborative problems
  1. Look and Say Numbers [15 pts]
    First, read about look-and-say numbers here.

    Second, write the non-destructive function lookAndSay(lst) that takes a list of numbers and returns a list of numbers that results from "reading off" the initial list using the look-and-say method, using tuples for each (count, value) pair. For example:
    assert(lookAndSay([]) == []) assert(lookAndSay([1, 1, 1]) == [(3, 1)]) assert(lookAndSay([-1, 2, 7]) == [(1, -1), (1, 2), (1, 7)]) assert(lookAndSay([3, 3, 8, -10, -10, -10]) == [(2, 3), (1, 8), (3, -10)]) assert(lookAndSay([3, 3, 8, 3, 3]) == [(2, 3), (1, 8), (2, 3)])

    Hint: you'll want to keep track of the current number and how many times it has been seen.

    Finally, write the non-destructive function inverseLookAndSay(lst) that does the inverse of the function lookAndSay, turning tuples of count and value into a single list. In general, inverseLookAndSay(lookAndSay(lst)) == lst. So for example:
    assert(inverseLookAndSay([(2, 3), (1, 8), (3, -10)]) == [3, 3, 8, -10, -10, -10])

  2. Tortoise Animation [40 pts] [manually-graded]
    Warning: this problem, like many animation problems, is a bit involved. Don't leave it until the last day!

    In addition to the Tkinter, which we all know and love, Python usually comes with another graphics package called "Turtle Graphics", which you can read about here. We will definitely not be using turtle graphics in this problem (and you may not do so in your solution!), but we will instead implement a small turtle-like (or maybe turtle-inspired) graphics language of our own. We'll call it Tortoise Graphics. This problem will be composed of two main parts:

    1. Part 1: Given a multi-line string of Tortoise Graphics commands, generate graphics based on the provided commands. [25 pts]

    2. Part 2: Allow users to add new commands to a Tortoise Graphics program with the animation framework. [15 pts]

    First, we need to understand how Tortoise Graphics programs work. Your tortoise is represented as a black triangle and starts in the middle of the screen, heading to the right. You can draw the tortoise using the provided function drawArrow(canvas, x, y, angle)), which takes the x and y coordinates of the turtle and the angle of the turtle in degrees. You can direct your tortoise with the following commands:

    • color name
      Set the drawing color to the given name, which is entered without quotes, and which can be "red", "blue", "green", or any other color that Tkinter understands. It can also be "none", meaning to not draw.

    • move n
      Move n pixels straight ahead, where n is a non-negative integer, while drawing a 4-pixel-wide line in the current drawing color. If the drawing color is "none", just move straight ahead without drawing (that is, just change the tortoise's location). Hint: you'll need to use a bit of trig for this part.

    • left n
      Turn n degrees to the left, without moving, where n is a non-negative integer.

    • right n
      Turn n degrees to the right, without moving, where n is a non-negative integer.

    Commands are given one-per-line. Lines can also contain comments, denoted by the hash sign (#), and everything from there to the end-of-line is ignored. Blank lines and lines containing only whitespace and/or comments are also ignored.

    Now we need to generate graphics based on a program using these commands! To do this, write a function runProgram(canvas, data, currentLine), which is called by redrawAll and draws graphics according to the provided tortoise program up to the given currentLine. So if currentLine if the number of lines in the string, the entire program would be executed; if currentLine was 5, only the first five lines would be executed. The original program will be stored in data.code, which is set in the run function.

    Next, to 'animate' the program, start a counter at 0 and increment it by one every time the user presses the Enter/Return key (you will want to store it in data). Then use this counter as the currentLine when you call runProgram in redrawAll. This will make the program appear to 'run' over time (though it's really drawing the whole program up to currentLine every time redrawAll is called).

    As a final step in Part 1, you should also display the program up to the currentLine in gray text on the left-hand side of the window. Don't worry if the program is longer than can fit in the window- there's no need to scroll or otherwise deal with this.

    Here's an example of what this looks like when run with the first and second sample programs in the test cases:



    Once your program behaves as shown above, you can move on to Part 2. In this stage, we'll make the programs ourselves! That's what the boxes at the bottom of the screen are for.

    The first seven boxes are colors: red, orange, yellow, green, blue, purple, and none (represented as white). When the user clicks any of these boxes, the command "color [chosen-color]" should be inserted to the current position in the program.

    The last three boxes are distances: 5, 25, and 50. When the user clicks any of these, the command "move [chosen-distance]" should be inserted to the current position in the program.

    Additionally, the command "left 30" should be inserted when the user presses the left arrow key, and the command "right 30" should be inserted when the user presses the right arrow key. All together, this lets the user modify the program on the go!

    Here's an example of a user trying each of these four commands:



    And here's an example of interrupting mid-program to change how things work:



    Still have questions? Here's a brief video demonstration of the features defined above.



    Have fun! Also, if you want to try improving on the animation, check out the first bonus problem below...
    3. Solo problems
  3. Non-destructive and Destructive removeRepeats(lst) [15 pts]
    In this problem, you will write one function two ways: non-destructively and destructively. The function is removeRepeats(lst), which removes any repeating elements from a given list. For example:

    assert(removeRepeats([1, 3, 5, 3, 3, 2, 1, 7, 5]) == [1, 3, 5, 2, 7])

    First, write nondestructiveRemoveRepeats(lst), which implements the function non-destructively. This function should not change the provided list, and should return a new list with no repeating elements.

    Then, write destructiveRemoveRepeats(lst), which implements the function destructively. This function should modify the provided list to not have any repeating elements, and should not return at all.

    Note: Do not use sets in this problem, even if you know how to use them.

  4. bestScrabbleScore(dictionary, letterScores, hand) [30 pts]
    Background: in a Scrabble-like game, players each have a hand, which is a list of lowercase letters. There is also a dictionary, which is a list of legal words (all in lowercase letters). And there is a list of letterScores, which is length 26, where letterScores[i] contains the point value for the ith character in the alphabet (so letterScores[0] contains the point value for 'a'). Players can use some or all of the tiles in their hand and arrange them in any order to form words. The point value for a word is 0 if it is not in the dictionary; otherwise it is the sum of the point values of each letter in the word, according to the letterScores list (pretty much as it works in actual Scrabble).

    In case you are interested, here is a list of the actual letterScores for Scrabble:
    letterScores = [ # a, b, c, d, e, f, g, h, i, j, k, l, m, 1, 3, 3, 2, 1, 4, 2, 4, 1, 8, 5, 1, 3, # n, o, p, q, r, s, t, u, v, w, x, y, z 1, 1, 3,10, 1, 1, 1, 1, 4, 4, 8, 4,10 ]

    Note that your function must work for any list of letterScores that is provided by the caller.

    With this in mind, write the function bestScrabbleScore(dictionary, letterScores, hand) that takes 3 lists -- dictionary (a list of lowercase words), letterScores (a list of 26 integers), and hand (a list of lowercase characters) -- and finds the highest-scoring word in the dictionary that can be formed by some arrangement of some set of letters in the hand.

    • If there is only one highest-scoring word, return it and its score in a tuple.
    • If there are multiple highest-scoring words, return a tuple with two elements: a list of all the highest-scoring words in the order they appear in the dictionary, then the score.
    • If no highest-scoring word exists (ie, if no legal words can be formed from the hand), return None instead of a tuple.

    The dictionary in this problem is a list of words, and thus not a true Python dictionary (which we haven't taught you and you may not use in this assignment)! It is OK to loop through the dictionary, even if the dictionary we provide is large.

    Note: You should definitely write helper functions for this problem! In fact, try to think of at least two helper functions you could use before writing any code at all.

    Another Note: You may not use itertools for this problem! In fact, you should not create permutations of the letters at all, and if you do, your solution will probably time out on Autolab. There's a much simpler way to find all the legal words you can create...
    5. Bonus problems
  5. Bonus/Optional: Super Tortoise Animation [1 pt]
    Have an idea for how to make the Tortoise Animation in the homework even cooler? Go ahead and add it! If you add a feature that is complex enough, you can get a bonus point on the homework.

    Important: your bonus feature must not break any of the core functionality of the problem. Also, to get credit, you must add text next to the comment 'Tortoise Animation bonus features:' explaining what new feature(s) you added.

  6. Bonus/Optional: Timeline Game [3 pts]
    Background: in the game called Timeline, your task is to construct an accurate timeline of events in history without looking at the dates when the events occurred. You are given a hand of cards, where each card has an event on one side and the year that the event occured on the other (which you cannot see). You are also given a timeline, which starts with one event card (with the year face-up). You have to insert each of the events in your hand into the timeline in the correct order, flipping each card to show its year once it is in the timeline. The game is over when you have placed all of the cards correctly.

    Your task is to build a basic game of Timeline using our animation framework, as is shown in the following video. A list of requirements is included below. Outside of these requirements, you can make whatever design decisions you'd like to build a game that you enjoy!



    Requirements:
    • You should start with the 15-112 animation starter code, along with the the provided starterCards() function, which returns a shuffled deck of cards you can use to construct the initial hand and timeline.
    • Appearance:
      • Your timeline should be drawn in the top half of the screen, with cards showing both the event name and the year. The cards must be sized so that they can all fit on the screen, no matter what the screen's width is.
      • Your hand should be drawn in the bottom half of the screen, with cards showing only the event name. Again, the cards should be sized so that they can all fit in the screen, no matter what the screen's width is.
      • A score should be drawn somewhere on the screen.
    • Gameplay:
      • When the user clicks on a card in the hand, that card becomes selected and is highlighted. Only one card in the hand may be selected at a time.
      • When the user clicks on a card in the timeline, that card becomes selected and is highlighted. Only one card in the timeline can be selected at a time.
      • If the user clicks on the screen not on a card, all selections are undone.
      • If the user has selected both a card in the timeline and a card in the hand, they can press the left arrow key or right arrow key to try to insert the selected card in the hand to the left of the selected timeline card or the right of the selected timeline card, respectively.
        • If the placement of the card is correct (ie, if the year belongs in that position in the current timeline), the card is removed from the hand and inserted into its new position in the timeline. Also, one point is added to the score.
        • If the placement of the card is incorrect, the selections are undone and one point is subtracted from the score. The score is allowed to become negative this way.
      • If the user presses the 'r' key, the game resets entirely.

    Have fun!