CMU 15-112: Fundamentals of Programming and Computer Science
Week 2: Strings

To start:
1. Create a folder named 'Week2'
2. Download 4. stringsPractice.py
3. Edit the downloaded file using your preferred editor
Do not use lists, recursion in the solutions.

Code Tracing
What will this code print? Figure it out by hand, then run the code to confirm. Then slightly edit the code and try again.

Trace #1 of 3:
def ct1(s, t): result = "" for c in s: if (c.upper() not in "NO!!!"): i = t.find(c) if (result != ""): result += ":" result += (str(i) + c + s[i] + t[i]) return result print(ct1("net", "two"))

Trace #2 of 3:
def ct2(s): result = "" d = ord("a") for c in s.lower(): if (c.isalpha() and (ord(c) >= d)): result += str(ord(c) - d) + chr(d) d += 1 return result print(ct2("Be a CA?!?"))

Trace #3 of 3:
def ct3(s): result = "" while (len(s) > 1): result += s[:1] + s[2:4] + "." s = s[1:-1:2] return result + s print(ct3("abcdefghi"))

Free Response (Problem-Solving)

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.

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.

    bestWord("I love programming", "iaov")

    bestWord("Programming is FUN", "ufo")

wordWrap(text, width)
Write the function wordWrap(text, width) that takes a string of text (containing only lowercase letters or spaces) and a positive integer width, and returns a possibly-multiline string that matches the original string, only with line wrapping at the given width. So wordWrap("abc", 3) just returns "abc", but wordWrap("abc",2) returns a 2-line string, with "ab" on the first line and "c" on the second line. After you complete word wrapping in this way, only then: All spaces at the start and end of each resulting line should be removed, and then all remaining spaces should be converted to dashes ("-"), so they can be easily seen in the resulting string. Here are some test cases for you:
```
        assert(wordWrap("abcdefghij", 4)  ==  """\
abcd
efgh
ij""")
        assert(wordWrap("a b c de fg",  4)  ==  """\
a-b
c-de
fg""")
```

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").

longestSubpalindrome(s)
Write the function longestSubpalindrome(s), that takes a string s and returns the longest palindrome that occurs as consecutive characters (not just letters, but any characters) in s. So:
```
   longestSubpalindrome("ab-4-be!!!")
```
returns "b-4-b". If there is a tie, return the lexicographically larger value -- in Python, a string s1 is lexicographically greater than a string s2 if (s1 > s2). So:
```
   longestSubpalindrome("abcbce")
```
returns "cbc", since ("cbc" > "bcb"). Note that unlike the previous functions, this function is case-sensitive (so "A" is not treated the same as "a" here). Also, from the explanation above, we see that longestSubpalindrome("aba") is "aba", and longestSubpalindrome("a") is "a".

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?).

collapseWhitespace(s)
Without using the s.replace() method, write the function collapseWhitespace(s), that takes a string s and returns an equivalent string except that each occurrence of whitespace in the string is replaced by a single space. So, for example, collapseWhitespace("a\t\t\tb\n\nc") replaces the three tabs with a single space, and the two newlines with another single space , returning "a b c". Here are a few more test cases for you:
```
    assert(cw("a\nb") == "a b")
    assert(cw("a\n   \t    b") == "a b")
    assert(cw("a\n   \t    b  \n\n  \t\t\t c   ") == "a b c ")
```
Once again, do not use s.replace() in your solution.

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().

encodeOffset(s, d)
Write the function encodeOffset(s, d) that takes a string and a possibly-negative int offset d (for "delta"), and returns the string formed by replacing each letter in s with the letter d steps away in the alphabet. So: encodeOffset("ACB", 1) return "BDC" encodeOffset("ACB", 2) return "CED" This works with wraparound, so: encodeOffset("XYZ", 1) returns "YZA" And with negative offsets, so: encodeOffset("ABC", -1) returns "ZAB" And the wraparound repeats with d>26, so: encodeOffset("ABC", -27) returns "ZAB" And it is case-preserving, so: encodeOffset("Abc", -27) returns "Zab" And it does not affect non-alphabetic characters (non-letters), so: encodeOffset("A2b#c", -27) returns "Z2a#b"

decodeOffset(s, d)
Write the function decodeOffset(s, d) that takes a string that was encoded by encodeOffset using the given offset d, and returns the original string.

encrypt and decrypt
Background: Here we will implement a simple password-based encryption scheme. First, we will start with a plaintext (not encrypted) message, say "Go team!". We will ignore all the non-letters and convert the letters to uppercase, giving us "GOTEAM". That is the message we will encrypt. Next, we need a password, which we assume is all lowercase letters, say "azby". We will think of each letter in the password as a shift, where a is 0 and z is 25, so "azby" specifies the shifts 0, 25, 1, 24 in order. We apply these shifts to the letters of the plaintext message, with wraparound (so after "Z" we go back to "A"). So we will shift "G" by 0 (resulting in "G"), "O" by 25 (resulting in "N"), "T" by 1 (resulting in "U"), and "E" by 24 (resulting in "C"). Then we run out of password characters, so we start over from the beginning of the password. So we shift "A" by 0 (resulting in "A") and "M" by 25 (resulting in "L"). Hence, encrypting "Go team!" with the password "azby" produces the ciphertext (that is, the encrypted text) "GNUCAL".
- encrypt
- decrypt