def group_by_retval(sequence, grouper_func):
    # TODO

l = ["ab", 12, "cd", "d", 3]

assert(group_by_retval(l, lambda x: isinstance(x, str)) == {True: ["ab", "cd", "d"], False: [12, 3]})
assert(group_by_retval([1, 1, 2, 3, 4], lambda x: x % 3) == {0: [3], 1: [1, 1, 4], 2: [2]})

"""
Explanation: [Your name]
Homework 1
The maximum score of this homework is 100+20 points. Grading is listed in this table:
| Grade | Score range |
| --- | --- |
| 5 | 85+ |
| 4 | 70-84 |
| 3 | 55-69 |
| 2 | 40-54 |
| 1 | 0-39 |
Most exercises include tests which should pass if your solution is correct.
However successful test do not guarantee that your solution is correct.
You are free to add more tests.
Exercise 1, small exercises (30 points)
1.1 Groupby function (10 points)
Write a function that takes a sequene and a callable as parameters. The function should call its second parameter on every element on the sequence and group them by return value. It should return a dictionary whose keys are the return values of the callable and values are lists of sequence elements that the callable return that value to.
End of explanation
"""


#TODO

assert(replace_rare_words("a b a b b c", 2) == "a b a b b __RARE__")
assert(replace_rare_words("a b a b b c", 2, rare_symbol="rare") == "a b a b b rare")

"""
Explanation: 1.2 Replace rare words (10 points)
Write a function that takes a text and a number $N$ as parameters and replaces every word other than the most common $N$ in the text with a common symbol. The symbol by default is __RARE__ but it can be redefined.
End of explanation
"""


# TODO

assert(levenshtein("abc", "ab") == 1)
assert(levenshtein("abc", "abc") == 0)
assert(levenshtein("abc", "ab c") == 1)
assert(levenshtein("", "abc") == 3)

"""
Explanation: 1.3 Levenshtein distance (10 points)
Write a function that returns the Levenshtein distance of two strings.
https://en.wikipedia.org/wiki/Levenshtein_distance
End of explanation
"""


class MutableString(object):
    #TODO
    
m1 = MutableString("abc")
m1[1] = "d"
assert(m1[1] == "d")
m1[1] = "b"
m1[4] = "d"
assert(m1[3] == " " and m1[4] == "d" and len(m1) == 5)

assert(list(m1) == list("abc d"))
assert(str(m1) == "abc d")

m1 = MutableString("abc")
m2 = m1 + "def"
assert(isinstance(m2, MutableString))
assert(m2 == "abcdef")

m3 = m1 * 3
assert(isinstance(m3, MutableString) and m3 == "abcabcabc")

m2[0] = "A"  # modifying m2 should not change m1
assert(m1 == "abc")

# right addition with strings
m1 = MutableString("abc")
m2 = "def" + m1
assert(m2 == "defabc")

"""
Explanation: Exercise 2, Mutable string (40 points)
Python strings are immutable. Create a mutable string class.
Implement the following features (see the tests below).

initialization from str.
assignment (i.e. modifying a character),
if the index is out of range, it should fill the blanks with spaces (see the tests below)
conversion to built-in str and list. The latter is a list of the characters.
addition with other MutableString instances and built-in strings,
multiplication with integers. Multiplying a string with 3 means repeating the string 3 times.
built-in len function,
comparision with strings,
iteration.
End of explanation
"""


# TODO

assert(count_ngram_freqs("abcc", 1) == {"a": 1, "b": 1, "c": 2})
assert(count_ngram_freqs("abccab", 2) == {"ab": 2, "bc": 1, "cc": 1, "ca": 1})

"""
Explanation: Exercise 3 - Text generation (30+20 points)
3.1 (Same as a laboratory exercise) Write a function that computes N-gram frequencies in a string. (0 point)
End of explanation
"""


# TODO

toy_freqs = count_ngram_freqs("abcabcda", 3)
gen = generate_text("abc", 5, toy_freqs, 3)

assert(len(gen) == 5)
assert(set(gen) <= set("abcd"))

"""
Explanation: 3.2 Define a text generator function. (25 points)
The function takes 4 arguments:

starting text (at least $N-1$ long,
target length: length of the output string,
n-gram frequency dictionary,
N, length of the n-grams.

The function generates one character at a time given the last $N-1$ characters.
The probability of c being generated after ab is defined as:
$$
P(c | a b ) = \frac{\text{freq}(a b c)}{\text{freq}(a b)},
$$
where  $\text{freq}(a b c)$ is obtained by counting how many times abc occurs in the training corpus (count_ngram_freqs function).
If the generated text ends with a $N-1$-gram that does not occur in the training data, generate the next character from the full distribution.
End of explanation
"""


