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 3 (Due Sunday 3-Feb, at 5pm)


  1. Style [0 pts]
    Starting with this assignment, we will be grading your code based on whether it follows the 15-112 style guide. We may deduct up to 10 points from your overall grade for style errors. Writing your code with good style from the beginning is the best way to avoid losing points!
    2. Lab collaborative problems [25pts]
    The lab problems will be released on Friday, and must be completed collaboratively with your classmates.
    Collaborative problem

  2. COLLABORATIVE Top-Down Design: rightJustifyText(text, width) [20 pts]
    In this problem, we want you to practice applying the algorithmic thinking strategy of top-down design. We recommend that you solve this problem by using a primary function and at least one well-designed helper function. You get to decide what that helper function should be!

    Write the function rightJustifyText(text, width) that takes a string (which may contain various kinds of whitespace) and a width (which you may assume is a positive integer), and returns that same text as a multi-line string that is right-justified to the given line width. For example, consider the following text:

    text = """\ We hold these truths to be self-evident: that all men are created equal; that they are endowed by their Creator with certain unalienable rights; that among these are life, liberty, and the pursuit of happiness."""

    With this text, a call to rightJustifyText(text, 30) would return this text right-justified with 30 characters per line, as such:

    """\ We hold these truths to be self-evident: that all men are created equal; that they are endowed by their Creator with certain unalienable rights; that among these are life, liberty, and the pursuit of happiness."""

    To solve this problem, we recommend that you follow these three general algorithmic steps.
    1. First, replace all sequences of any kind of whitespace (spaces, tabs, newlines) with a single space. For our example, that creates the following string:

      """\ We hold these truths to be self-evident: that all men are created equal; that they are endowed by their Creator with certain unalienable rights; that among these are life, liberty, and the pursuit of happiness."""

    2. Next, break the text into individual lines by repeatedly finding the existing space as far to the right as possible while still allowing the line to remain under the given width restriction. That space will be replaced with a newline ("\n") to create a new string of multiple lines. You are guaranteed that no word in the string will be longer than the provided width. For our example, that creates the following string:

      """\ We hold these truths to be self-evident: that all men are created equal; that they are endowed by their Creator with certain unalienable rights; that among these are life, liberty, and the pursuit of happiness."""

    3. Finally, for each line, add extra spaces to the left of the line to make it fit the given width. For our example, that creates the final result string. Note that some lines (like the second line above) will already fit the width and won't need to be changed.

    Hint: while debugging, you should print out the intermediate result at the end of each of these three steps, to see if it matches the intended result. Also, you can use the repr() function to check if the whitespace in your solution is working as expected.
    3. Solo problems
    NOTE: The remainder of the assignment must be completed solo. That means these problems must be completed without collaboration. It is your responsibility to maintain academic integrity as outlined in the syllabus. You may always use piazza, office hours, and other official 15-112 course resources for questions.


  3. Fix the Style [10 pts, hand-graded]
    We've written a program, areAnagrams(s1, s2), which returns True if two strings are anagrams (that is, if they contain the same letters in possibly-different orders). For example, "smart" and "trams" are anagrams; on the other hand, "read" and "dared" are not anagrams, since they have a different number of letters. The program is functionally correct, but we've written it with terrible style.

    Fix this program so that it meets the 15-112 style guide without rewriting the main logic. Then, in a comment above the fixed program, write out a list of the changes you made to fix the style. You must make valid changes that cover at least five different style rules to get full credit. This problem is not autograded; we will hand-grade it instead.

    def areAnagrams(s1, s2): if len(s1) != len(s2): return False print("bad case") if len(s1) == len(s2): for str in s1: one = 1 count_matches_1= 0 count_matches_2 = 0 for i in range(len(s1)): if s1[i] == str: count_matches_1 += one for i in range(len(s2)): if s2[i] == str: count_matches_2 += one if count_matches_1 !=count_matches_2: return False return True

  4. Top-Down Design: longestCommonSubstring(s1, s2) [15 pts]
    In this problem, we want you to practice applying the algorithmic thinking strategy of top-down design. We recommend that you solve this problem by using a primary function and at least one well-designed helper function. You get to decide what that helper function should be!

    Write a function, longestCommonSubstring(s1, s2), that takes two possibly-empty strings and returns the longest string that occurs in both strings (and returns the empty string if either string is empty). For example:

    assert(longestCommonSubstring("abcdef", "abqrcdest") == "cde") assert(longestCommonSubstring("abcdef", "ghi") == "") # the empty string

    If there are two or more longest common substrings, return the lexicographically smaller one (ie, just use "<" to compare the strings). So, for example:

    assert(longestCommonSubstring("abcABC", "zzabZZAB") == "AB") # not "ab"

  5. Algorithmic Thinking: asciiDraw(canvas, artStr, width, height) [30 pts, hand-graded]
    Write the function asciiDraw(canvas, artStr, width, height) which converts ASCII art to pixel art in tkinter. The function should take canvas as an input, and width and height as integers, and artStr (a string). This problem will require you to think algorithmically! Before you start coding, think about the problem statement and how you can break this problem down into helper functions. Good style will also help you to debug and modify your program.

    Note: We provide the function runAsciiDraw(artStr, width, height), which includes the starter code for setting up the canvas. You should not modify this function. The variables artStr, width, and height are passed to asciiDraw(canvas, artStr, width, height) without modification.
    The variable artStr is composed of whitespace, newlines, and the numbers 0-7. Here is a very simple example:

    artStr = ''' 1 2 4 111 222 444 11111 22222 44444 111 222 444 1 2 4 ''' runAsciiDraw(artStr, 600, 300)

    6. This code should produce the following image in a 600 by 300 window:

    The image is composed of colored rectangles corresponding to the location of the numeric characters in artStr. The size of the rectangles is determined by the size of the canvas and the number of lines in artStr and the number of characters in the longest line (i.e. the drawing should fill the entire canvas and every character should fit on the canvas).

    Hint: Think about how you can programmatically draw these rectangles. You could conceivably use a while loop to iterate through the characters in artStr, updating a row and col variable each time. If the character is not a newline, what should happen to col? What should happen to row? What should happen to row and col when you encounter a newline? A reasonable starting point might be to simply draw rectangles using a single color in the locations indicated by non-whitespace characters. Once that's working reliably, you can move on to getting the colors right.

    Note that each number corresponds to a different color (in the diamond example, 1 is blue, 2 is green, 4 is red). When drawing in tkinter, you can specify colors using a string of RGB values. Because we want to specify colors using a single character (numbers 0 to 7 inclusive), our mapping must be very simple. The decimal values 0 to 7 can be represented with a three-digit binary value. In this problem, each of the three bits corresponds to the presence (1) or absence (0) of red, green, or blue. The leftmost bit corresponds to red, the middle to green, and the right to blue. The table below shows how each integer is represented in binary, and how those binary values should correspond to an RGB string that can be used by tkinter.

    Decimal value Binary value #RGB string Color
    0 000 "#000"
    1 001 "#00F"
    2 010 "#0F0"
    3 011 "#0FF"
    4 100 "#F00"
    5 101 "#F0F"
    6 110 "#FF0"
    7 111 "#FFF"


    If you aren't familiar with binary (base-2) numbers, you can read more here. Likewise, if you wish to read more about RGB values in tkinter, you can read more here here under "RGB specifications." However, it is sufficient to just understand the pattern and algorithmically generate the color strings for tkinter.

    Hint: How do you get the binary digits from a decimal number? It's not really any different than getting its base-ten digits with mod and div, except you use 2 instead of 10! For example, 5 is 101 in binary: The ones digit can be calculated as (5%2**1)//(2**0)=1. Likewise the twos digit is (5%2**2)//(2**1)=0 and the fours digit is (5%2**3)//(2**2)=1.

    Here is a test pattern you can use to see if you're getting the colors right! (Note that the newline character "\n" is the same as if we wrote the string on two lines with triple quotes.)

    artStr = "0123\n4567" runAsciiDraw(artStr, 600, 300)

    This code should produce the following image in a 600 by 300 window:

    Here's a more complicated pattern and its output:

    artStr = ''' 0022222222222222222 02222222222222222222222220 02222222222222222222222222222220 02 02 02 0 0 0 02222222222222222222222222222222222220 02 22 2202 0 2 2 02 0222222222 2222222222222 2222222220 02202202 022222202 0222222222 22222222222 22222222220 02222222 0222222 02222222222 22222222222 22222222222222222222222 02222222222222222222222 2222222222222 22222222222222 0222 022202222222222222222222222222222222222222222222222222222 0222 022 022222222222222222222222222222222222222222222222222 02220 0220 222222222222222222222222222222222222222222222222222 2220 022 222222222222222222222222222222222222222222222000222222022220 0222022222 2222222222222222222222222222222222222 022222222222222222 0222 202222 2222222222222222222222222222222222 02220 0222 0222 022222222222222222222222222220 0222 02220 02222222222222222220220 022 0220 02202222220 0222 02220 02220 022220 02222220022220 02222 0222220 022222222220 022220 0222220 022222222222220 02222222022222222222 022222222222 022222222222 02222222220 02220 ''' runAsciiDraw(artStr, 800, 600)

    This code should produce the following image in a 800 by 600 window:

    And one more:

    artStr = ''' 0000 00000000000000000000 00 00000000 0000000000000 00 0 000000000000000000 000000 00 0000 11111 0 0 00 00 00 0 111111111111111110 0 0000 0 0 000000111111111111111111110 00000 0000 0 0 0 111111111111111111110 0 0 0 0 0 0 111111111111111555550 0 0 0 0 0 0 111111111555644644640 0 0 0 0 0 0 111115546446446446440 0 0 0 0 0 0 111546464464464464460 0 0 0 0 0 0 154644644644644646660 0 0 0 0 0 0 056446446446666666660 0 0 0 0 0 0 0 5666666666666666650 0 0 0 0 0 0 0 566666666666666510 0 0 0 0 0 0 0 16666666666661 0 0 0 0 0 0 0 0 116666666651 0 0 0 0 0 0 0 0 1156111 0 0 0 0 0 0 0 0 55 0 0 0 0 0 0 0 0 11165111 0 0 0 0 0 0 0 0 1111156111111 0 0 0 0 0 0 0 0 111111551111111 0 0 0 0 0 0 0 0 111111165111111110 0 0 0 0 0 0 0 1111111155111111110 0 0 0 0 0 0 011111111161111111110 0 0 0 0 0 0 011111111161111111110 0 0 0 0 0 0 111111115666511111110 0 0 0 0 0 0 111111156666651111110 0 0 0 0 0 0 111111566666665111110 0 0 0 0 0 01111115666666666511110 0 0 0 0 0 0001111156666666666651110 00000 0000 0 00 1111566666666666665110 0 000 00 0 0 1111566666666666666510 0 00 0 00000 0115666666666666666510 0 00 00 0 00000000006666660000 000 00 00 0000000000000 111111 0000000000 00 00000000000000000000000 ''' runAsciiDraw(artStr, 400, 600)

    This code should produce the following image in a 400 by 600 window:


    That's it! Good luck! Remember to break this problem down into manageable steps, use helper functions where appropriate, and practice good style.
  6. Bonus/Optional: getEvalSteps(expr) [3 pts]
    Write the function getEvalSteps(expr), that takes a string containing a simple arithmetic expression and returns a multi-line string containing the step-by-step (one operator at a time) evaluation of that expression. For example, this call:

    getEvalSteps("2+3*4-8**3%3")

    produces this result (which is a single multi-line string):

    2+3*4-8**3%3 = 2+3*4-512%3
             = 2+12-512%3
             = 2+12-2
             = 14-2
             = 12

    You are only responsible for legal input as described below:
    • Numbers (which must be integers and non-negative).
    • Operators (which are limited to +, -, *, /, //, %, and **).
    • All operators are binary, so they take two operands. So there are no unary operators, meaning "-5" is not a legal input. For that, you'd need "0-5".
    • In fact, the previous restriction is even stronger: no intermediate value of expr can be negative! So "1-2+3" is not legal, since it would be converted first into "-1+3" which is not legal. So you can safely ignore all such cases.
    • There are no parentheses and no whitespace.

    Here are more instructions and hints:
    • Operators must be evaluated by precedence (** first, then *,/,//,%, then +,-). Equal-precedence operators are evaluated left-to-right.
    • Evaluation proceeds until a single integer with no operators remains after the equals sign.
    • The equal signs must all be stacked directly over each other.
    • In our sample solution, we used very few string methods, just "find" and "isdigit". You may use others, but you should not spin your wheels trying to find that awesome string method that will make this problem remarkably easier, as that method does not exist.
    • For this function, as any other function, you may not use the eval function, so you will have to write your own equivalent simple-eval just for the kinds of simple expressions you will deal with here. Eval is dangerous and should be avoided, as it can lead to serious bugs or security holes.