CMU 15-112: Fundamentals of Programming and Computer Science
Extra Practice for Unit 3 (Due never)

  1. interleave(s1, s2)
    Write the function interleave(s1, s2) that takes two strings, s1 and s2, and interleaves their characters starting with the first character in s1. For example, interleave('pto', 'yhn') would return the string "python". If one string is longer than the other, concatenate the rest of the remaining string onto the end of the new string. For example ('a#', 'cD!f2') would return the string "ac#D!f2". Assume that both s1 and s2 will always be strings.

  2. longestCommonSubstring(s1, s2)
    Write the 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:
         longestCommonSubstring("abcdef", "abqrcdest") returns "cde"
         longestCommonSubstring("abcdef", "ghi") returns "" (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:
        longestCommonSubstring("abcABC", "zzabZZAB") returns "AB" and not "ab"

  3. leastFrequentLetters(s)
    Write the function leastFrequentLetters(s), that takes a string s, and ignoring case (so "A" and "a" are treated the same), returns a lowercase string containing the least-frequent alphabetic letters that occur in s, each included only once in the result and then in alphabetic order. So:
       leastFrequentLetters("aDq efQ? FB'daf!!!") 
    returns "be". Note that digits, punctuation, and whitespace are not letters! Also note that seeing as we have not yet covered lists, sets, maps, or efficiency, you are not expected to write the most efficient solution. Finally, if s does not contain any alphabetic characters, the result should be the empty string ("").

  4. sameChars(s1, s2)
    Write the function sameChars(s1, s2) that takes two strings and returns True if the two strings are composed of the same characters (though perhaps in different numbers and in different orders) -- that is, if every character that is in the first string, is in the second, and vice versa -- and False otherwise. This test is case-sensitive, so "ABC" and "abc" do not contain the same characters. The function returns False if either parameter is not a string, but returns True if both strings are empty (why?).

  5. areAnagrams(s1, s2)
    Write the function areAnagrams(s1, s2) that takes two strings, s1 and s2, that you may assume contain only upper and/or lower case letters, and returns True if the strings are anagrams, and False otherwise. Two strings are anagrams if each can be reordered into the other. Treat "a" and "A" as the same letters (so "Aba" and "BAA" are anagrams). You may not use sort() or sorted() or any other list-based functions or approaches. Hint: you may use s.count(), which could be quite handy here.

  6. replace(s1, s2, s3)
    Without using the builtin method s.replace(), write its equivalent. Specifically, write the function replace(s1, s2, s3) that returns a string equal to s1.replace(s2, s3), but again without calling s.replace().

  7. hasBalancedParentheses(s)
    Write the function hasBalancedParentheses, which takes a string and returns True if that code has balanced parentheses and False otherwise (ignoring all non-parentheses in the string). We say that parentheses are balanced if each right parenthesis closes (matches) an open (unmatched) left parenthesis, and no left parentheses are left unclosed (unmatched) at the end of the text. So, for example, "( ( ( ) ( ) ) ( ) )" is balanced, but "( ) )" is not balanced, and "( ) ) (" is also not balanced. Hint: keep track of how many right parentheses remain unmatched as you iterate over the string.

  8. largestNumber(text)
    largestNumber: Write the function largestNumber(text) that takes a string of text and returns the largest int value that occurs within that text, or None if no such value occurs. You may assume that the only numbers in the text are non-negative integers and that numbers are always composed of consecutive digits (without commas, for example). For example:
        largestNumber("I saw 3 dogs, 17 cats, and 14 cows!")
    returns 17 (the int value 17, not the string "17"). And
        largestNumber("One person ate two hot dogs!")
    returns None (the value None, not the string "None").

  9. capitalizeFirstLetters(s)
    Write the function capitalizeFirstLetters(s) which takes a string, s, and returns the original string with the first character of every word capitalized. For example, capitalizeFirstLetters("hello, my name is john.") will return "Hello, My Name Is John." Note: A new word starts after one or more spaces. Non-letters are capitalized as themselves. Punctuation does not affect the start of a new word. For example: capitalizeFirstLetters("don't do that (please)") returns "Don't Do That (please)" and not "Don'T Do That (please)" or "Don't Do That (Please)".

  10. foil(expression)
    Write the function foil(expression) which takes a string, expression, representing a product of two expressions of the form (x + b), such as "(x + 2)(x + 3)" and returns a string containing the expanded form. In this case "x**2 + 5*x + 6". The variable (in this case x) can be any letter, uppercase or lowercase, and must be the same in both expressions. The constants (2 and 3 in this case) must be positive integers less than 10. Legal inputs will include spaces where shown in the example.

  11. pigLatin(s)
    Background: Pig Latin is a fun-spirited alteration of English. To make a word in Pig Latin, take an English word, move the leading consonants to the end, followed by "ay" (e.g. "school" -> "oolschay"). If the word begins with a vowel, or if it contains no vowels, then simply add "ay" to the end (e.g. "in" -> "inay"). With that in mind, write a function named pigLatin which takes a string of English words and translates it into Pig Latin. The function should return the result as a string. You should treat "qu" as a single consonant, and "y" should be treated as a vowel. Words are divided by spaces, and any non-alphabetic characters (punctuation, numbers, etc.) inside a word should remain where they are. If outside of a word, they should remain outside (e.g. "hey, don't do that!" -> "eyhay, on'tday oday atthay!"). If a "word" (such as "9000") contains no letters, do not add "ay" to the end. Finally, if the first letter of a word is capitalized, then the first letter of the pig latin word should be capitalized (e.g. "Professor Kosbie" -> "Ofessorpray Osbiekay"). All letters except the first will be lowercase in the input, and should be lower case in your output as in the previous example.

  12. drawFlagOfQatar(canvas, width, height)
    Write the function drawFlagOfQatar(canvas, width, height) that takes a canvas and its width and height and draws a flag of Qatar:

    Be sure to follow these guidelines:
    • Colors do not have to perfectly match.
    • The flag must have a thin black border around it.
    • The flag must be twice as wide as it is tall, with at least 30 pixels between the edge of the flag and any side of the canvas, and it must be centered in the canvas, and as large as possible given these restrictions.
    • The canvas must have the name 'Qatar' in bold, centered at the top.

  13. drawFlagOfTheEU(canvas, width, height)
    Write the function drawFlagOfTheEU(canvas, width, height) that follows the same guidelines as the flag of Qatar above, only now it draws a flag of the European Union:

    Note that you should use circles instead of stars, and it should say 'European Union' at the top of the canvas.

  14. patternedMessage(message, pattern)
    Write the function patternedMessage(message, pattern) that takes two strings, a message and a pattern, and returns a string produced by replacing the non-whitespace characters in the pattern with the non-whitespace characters in the message (where any leading or trailing newlines in the pattern are first removed), with the message repeating over and over again until the pattern is complete. As a first example:

    patternedMessage("Go Pirates!!!", """
    ******   ******
    irates   !!!GoP

    Here, the message is "Go Pirates!!!" and the pattern is a block of asterisks with a few missing in the middle. Notice how the whitespace in the pattern is preserved, but the whitespace in the message is removed. Again, note that any leading or trailing newlines in the pattern are removed.

    Here is another example:

    patternedMessage("Three Diamonds!","""
        *     *     *
       ***   ***   ***
      ***** ***** *****
       ***   ***   ***
        *     *     *
        T     h     r
       eeD   iam   ond
      s!Thr eeDia monds
       !Th   ree   Dia
        m     o     n

    Hint: In our sample solution, we started with an empty result string, then built up the answer character by character. How did we determine the next character? Using both the message and the pattern in some way...

    And here is one last example, just for fun:

    patternedMessage("Go Steelers!",
                       oo$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$o         o$   $$ o$
       o $ oo        o$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$o       $$ $$ $$o$
    oo $ $ '$      o$$$$$$$$$    $$$$$$$$$$$$$    $$$$$$$$$o       $$$o$$o$
    '$$$$$$o$     o$$$$$$$$$      $$$$$$$$$$$      $$$$$$$$$$o    $$$$$$$$
      $$$$$$$    $$$$$$$$$$$      $$$$$$$$$$$      $$$$$$$$$$$$$$$$$$$$$$$
      $$$$$$$$$$$$$$$$$$$$$$$    $$$$$$$$$$$$$    $$$$$$$$$$$$$$  '$$$
       '$$$'$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$     '$$$
        $$$   o$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$     '$$$o
       o$$'   $$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$       $$$o
       $$$    $$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$' '$$$$$$ooooo$$$$o
      o$$$oooo$$$$$  $$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$   o$$$$$$$$$$$$$$$$$
      $$$$$$$$'$$$$   $$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$     $$$$'
     ''''       $$$$    '$$$$$$$$$$$$$$$$$$$$$$$$$$$$'      o$$$
                '$$$o     '$$$$$$$$$$$$$$$$$$'$$'         $$$
                  $$$o          '$$'$$$$$$'           o$$$
                   $$$$o                                o$$$'
                    '$$$$o      o$$$$$$o'$$$$o        o$$$$
                      '$$$$$oo     '$$$$o$$$$$o   o$$$$'
                         '$$$$$oooo  '$$$o$$$$$$$$$'
                            '$$$$$$$oo $$$$$$$$$$

    Returns this:

                       teelers!GoSteelers!GoSteelers!GoS         te   el er
       s ! Go        Steelers!GoSteelers!GoSteelers!GoSteel       er s! GoSt
    ee l e rs      !GoSteeler    s!GoSteelers!    GoSteelers       !GoSteel
    ers!GoSte     elers!GoSt      eelers!GoSt      eelers!GoSt    eelers!G
      oSteele    rs!GoSteele      rs!GoSteele      rs!GoSteelers!GoSteeler
      s!GoSteelers!GoSteelers    !GoSteelers!G    oSteelers!GoSt  eele
       rs!GoSteelers!GoSteelers!GoSteelers!GoSteelers!GoSteel     ers!
        GoS   teelers!GoSteelers!GoSteelers!GoSteelers!GoSteelers     !GoSt
       eele   rs!GoSteelers!GoSteelers!GoSteelers!GoSteelers!GoSt       eele
       rs!    GoSteelers!GoSteelers!GoSteelers!GoSteelers!Go Steelers!GoSteele
      rs!GoSteelers  !GoSteelers!GoSteelers!GoSteelers!GoS   teelers!GoSteelers
      !GoSteelers!G   oSteelers!GoSteelers!GoSteelers!Go     Steel
     ers!       GoSt    eelers!GoSteelers!GoSteelers!G      oSte
                elers     !GoSteelers!GoSteelers!         GoS
                  teel          ers!GoSteel           ers!
                   GoSte                                elers
                    !GoSte      elers!GoSteele        rs!Go
                      Steelers     !GoSteelers!   GoStee
                         lers!GoSte  elers!GoSteeler
                            s!GoSteele rs!GoSteel

  15. Top-Down Design: justifyText(text, width) [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 the function justifyText(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 left- and right- justified to the given line width (except for the last line, which does not need to be justified). 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 justifyText(text, 30) would return this text left- and 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. 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 from the left to the right to make it fit the given width. For our example, that creates the final result string. Further examples are shown below.

      • Some lines (like the second line above) will already fit the width and won't need to be changed.
      • Other lines will require that you add spaces. Consider the first line in the example above ("We hold these truths to be"). There are 5 total spaces (one between each word), and since the line is 26 characters long, it requires 4 more spaces to pad out to a width of 30. This is done by adding an extra space to each space from left-to-right.
      • Note that you may have to add more than one extra space of padding to each gap (such as the 3 total spaces between "certain" and "unalienable"), there cannot be more than a 1-space difference between any two gaps on a line, and the extra spaces must all be on the left side of the line.