https://docs.google.com/document/d/1IbbZOHwH4gjZ70XtP_rH6QhX3BeDd1ANxj1DYaFUPXk/edit#

brangelina.py

#!/usr/bin/env python3

"""
Brangelina

The task of combining first names of celebrities into
a short catchy name for media consumption turns out
to be surprisingly simple to automate. Start by counting
how many groups of consecutive vowels (aeiou) there are
inside the first name. For example, "brad" and "ben" have
one group, "sheldon" and "britain" have two, and "angelina"
and "alexander" have four.

If the first name has only one vowel group, keep only the
consonants before that group and throw away everything else.
For example, "ben" becomes "b", and "brad" becomes "br".
Otherwise, if the word has n > 1 vowel groups, keep everything
before the vowel group n - 1. For example, "angelina" becomes
"angel" and "alexander" becomes "alex". Whatever that gives you,
concatenate it with the word constructed by removing all
consonants from the beginning of the second word.

All names given to this function are guaranteed to consist
of lowercase English letters only, and each name will have
at least one vowel and one consonant somewhere in it.
"""
from typing import List, NoReturn
import re


def brangelina(first: str, second: str) -> str:
    consonants_groups = re.split(r'[aeiouy]+', first)  # type: List[str]
    output = ''  # type: str
    if len(re.findall(r'[aeiouy]+', first)) == 1:
        output += consonants_groups[0]
    else:
        consonants = consonants_groups[-3]  # type: str
        output += first.split(consonants).pop(0) + consonants
    second = re.sub(r'^[^aeiouy]+', '', second)
    output += second
    return output


def main() -> NoReturn:
    names_pairs = [
        ["brad", "angelina"],
        ["donald", "melania"],
        ["sheldon", "amy"],
        ["britain", "exit"],
        ["bill", "hillary"],
        ["barack", "michelle"]
    ]  # type: List[List[str]]
    for pair in names_pairs:
        print(brangelina(*pair))


if __name__ == '__main__':
    main()

collapse_intervals.py

#!/usr/bin/env python3

"""
Collapse positive integer intervals

This function is the inverse of the earlier question of
expanding positive integer intervals. Given a nonempty
list of positive integers that is guaranteed to be in
sorted ascending order, create and return the unique
description string where every maximal sublist of
consecutive integers has been condensed to the notation
first-last. If some maximal sublist contains only one
integer, it is included in the result by itself without
the minus sign separating it from the now redundant last
number. Make sure that the string that your function
returns does not contain any whitespace characters,
and does not have an extra comma either in the beginning or end.
"""
from typing import List, NoReturn, Any


def collapse_intervals(items: List[int]) -> str:
    start = end = None  # type: Any
    output = []  # type: List[Any]
    for item in items:
        if start is None:
            start = end = item
        elif item == end + 1:
            end = item
        else:
            if start == end:
                interval = str(start)
            else:
                interval = str(start) + '-' + str(end)
            output.append(interval)
            start = end = item
    if start == end:
        interval = str(start)
    else:
        interval = str(start) + '-' + str(end)
    output.append(interval)
    return ','.join(output)


def main() -> NoReturn:
    list_items = [
        [1, 2, 6, 7, 8, 9, 10, 12, 13],
        [3, 5, 6, 7, 9, 11, 12, 13],
        [42]
    ]  # type: List[List[int]]
    for items in list_items:
        print(items, collapse_intervals(items))


if __name__ == '__main__':
    main()

expand_intervals.py

#!/usr/bin/env python3
"""
Expand positive integer intervals

An interval of positive integers can be succinctly described
by giving its first and last value, inclusive, separated by
a minus sign. For example, the interval 5, 6, 7, 8, 9 can be
described as "5-9". Multiple intervals can be described together
by separating them with commas. An interval that contains only
one value is given as just that value. Given a string that
contains one or more such comma-separated interval descriptions,
guaranteed not to overlap and to be listed in sorted ascending
order, create and return a list that contains all the integers
contained by these intervals.
"""
from typing import List, NoReturn, Any


def expand_intervals(intervals: str) -> List[int]:
    output = []  # type: List[int]
    for interval in intervals.split(','):
        if interval.isdigit():
            output.append(int(interval))
        else:
            start, end = interval.split('-')
            for digit in range(int(start), int(end) + 1):
                output.append(digit)
    return output


def main() -> NoReturn:
    list_intervals = [
        "4-6,10-12,16",
        "1-10,12,123-127,144",
        "12-12"
    ]  # type: List[str]
    for lst in list_intervals:
        print(lst, expand_intervals(lst))


if __name__ == '__main__':
    main()

flatten.py

#!/usr/bin/env python3
"""
Flatten an arbitrarily deep list

Given a list that contain arbitrary lists as element,
which in turn can contain arbitrary lists as elements,
and so on, create and return a new list that contains
all the atomic (that is, anything that is not a list)
elements without any nesting.
This particular problem is another classic textbook
exercise in recursion in all programming languages.
The base cases are the empty list and whenever items
is atomic. Otherwise, build a list by appending all
elements from the recursively flattened elements of items.
"""
from typing import List, NoReturn, Any


def flatten(items: List[Any], flattened: List[Any] = []) -> List[Any]:
    for item in items:
        if not isinstance(item, list):
            flattened.append(item)
        else:
            flatten(item, flattened)
    return flattened


def main() -> NoReturn:
    list_items = [
        [1, [2, 3, 4, 'yeah'], 5],
        [[[[[[1, 2]]]]]],
        [42, [99, [17, [33, ['boo!']]]]]
    ]  # type: List[List[Any]]
    for items in list_items:
        print(items, flatten(items, []))


if __name__ == '__main__':
    main()

frequency_sort.py

#!/usr/bin/env python3
"""
Sort array by element frequency

Sort the given integer array elems so that its elements
end up in the order of decreasing frequency, that is,
the number of times that they appear in elems. If two
elements have the same frequency, they should end up in
the ascending order of the element values with respect to each other.
"""
from typing import List, NoReturn
from collections import defaultdict


def frequency_sort(items: List[int]) -> List[int]:
    counts = defaultdict(int)  # type: defaultdict
    for item in items:
        counts[item] += 1
    sorted_by_counts = dict(sorted(
        counts.items(),
        key=lambda item: item[1],
        reverse=True
    ))
    # print(sorted_by_counts)
    sorted_items = []  # type: List[int]
    previous_count = 0  # type: int
    for item, count in sorted_by_counts.items():
        if not sorted_items:
            sorted_items.append(item)
            previous_count = count
        else:
            if count == previous_count and item < sorted_items[-1]:
                sorted_items.insert(-2, item)
            else:
                sorted_items.append(item)
    return sorted_items


def main() -> NoReturn:
    list_items = [
        [1, 2, 3, 3, 4, 5, 6, 1, 2, 3],
        [23, 22, 23, 22],
        [98, 98, 97, 96, 95, 96, 1, 1, 2, 2]
    ]  # type: List[List[int]]
    for lst in list_items:
        print(lst, frequency_sort(lst))


if __name__ == '__main__':
    main()

give_change.py

#!/usr/bin/env python3

"""
Giving back change

Given an amount of money (expressed as an integer as
the total number of cents, one dollar being equal to
100 cents) and the list of denominations of coins
(similarly expressed as cents), create and return a
list of coins that add up to amount using the greedy
approach where you use as many of the highest denomination
coins when possible before moving on to the next lower
denomination. The list of coin denominations is guaranteed
to given in sorted order, as should your result also be.
"""
from typing import List, NoReturn, Tuple


def give_change(amount: int, coins: List[int]) -> List[int]:
    change = []
    idx = 0
    while amount:
        if amount - coins[idx] >= 0:
            change.append(coins[idx])
            amount -= coins[idx]
        else:
            idx += 1
    return change


def main() -> NoReturn:
    data = [
        (64, [50, 20, 10, 5, 2, 1]),
        (123, [100, 20, 10, 5, 1]),
    ]  # type: List[Tuple[int, List[int]]]
    for d in data:
        print(d[0], give_change(*d))


if __name__ == '__main__':
    main()

group_equal.py

#!/usr/bin/env python3
"""
Group equal consecutive elements into sublists

Given a list of elements, create and return a list
whose elements are lists that contain the consecutive
runs of equal elements of the original list. Note that
elements that are not duplicated in the original list
should become singleton lists in the result, so that
every element gets included in the resulting list of lists.
"""
from typing import List, NoReturn, Any


def group_equal(items: List[Any]) -> List[List[Any]]:
    grouped_items = []  # type: List[List[Any]]
    for item in items:
        if len(grouped_items) == 0:
            grouped_items.append([item])
        elif item == grouped_items[-1][0]:
            grouped_items[-1].append(item)
        else:
            grouped_items.append([item])
    return grouped_items


def main() -> NoReturn:
    list_items = [
        [1, 2, 3, 3, 4],
        [None, 'XX', 'XX', 22, 22, 23],
        ['a', 'a', 'b', 'b']
    ]  # type: List[List[Any]]
    for lst in list_items:
        print(lst, group_equal(lst))


if __name__ == '__main__':
    main()

is_ascending.py

#!/usr/bin/env python3

"""
Ascending list

Determine whether the sequence of elements items
is ascending so that its each element is strictly
larger than (and not merely equal to) the element
that precedes it.
"""
from typing import List, NoReturn, Any


def is_ascending(items: List[int]) -> bool:
    ascending = True  # type: bool
    previous_item = items.pop(0)  # type: int
    for item in items:
        if not item > previous_item:
            ascending = False
            break
    return ascending


def main() -> NoReturn:
    list_items = [
        [1, 2, 3, 3, 4, 5, 6, 1, 2, 3],
        [23, 22, 23, 22],
        [98, 98, 97, 96, 95, 96, 1, 1, 2, 2],
        [1, 2, 3]
    ]  # type: List[List[int]]
    for lst in list_items:
        print(lst, is_ascending(lst))


if __name__ == '__main__':
    main()

iterated_remove_pairs.py

#!/usr/bin/env python3
"""
Iterated removal of consecutive pairs

Given a list of elements, create and return a new list that
contains the same elements except all occurrences of pairs
of consecutive elements have been left out. However, this
operation must continue in iterated fashion so that whenever
removing some pair of consecutive elements causes two equal
elements that were originally apart from each other to end
up next to each other, that new pair is also removed, and
so on until nothing can be removed.
"""
from typing import List, NoReturn, Any


def iterated_remove_pairs(items: List[Any]) -> List[Any]:
    for idx, item in enumerate(items):
        if idx == 0:
            previous_item = item
        else:
            if item == previous_item:
                del(items[idx])
                del(items[idx -1])
                items = iterated_remove_pairs(items)
            previous_item = item
    return items


def main() -> NoReturn:
    list_items = [
        [1, 2, 3, 3, 2,  4],
        [None, 'XX', 'XX', 22, 22, 23],
        ['a', 'a', 'b', 'b', 'a', 'a'],
    ] # type: List[List[Any]]
    for lst in list_items:
        print(lst, iterated_remove_pairs(lst.copy()))

if __name__ == '__main__':
    main()

reverse_ascending_sublists.py

#!/usr/bin/env python3
"""
Reverse every ascending sublist

Create and return a new list that contains the same elements
as the argument list items, but reversing the order of the
elements inside every maximal strictly ascending sublist.
This function should not modify the contents of the original list.
"""
from typing import List, NoReturn


def reverse_ascending_sublists(items: List[int]) -> List[int]:
    output = []  # type: List[int]
    sublist = []  # type: List[int]
    for item in items:
        if len(sublist) == 0:
            sublist.append(item)
        else:
            if item > sublist[0]:
                sublist.insert(0, item)
            else:
                output.extend(sublist)
                sublist = [item]
    output.extend(sublist)
    return output


def main() -> NoReturn:
    list_items = [
        [1, 2, 3, 3, 4, 5, 6, 1, 2, 3],
        [23, 22, 23, 22],
    ]  # type: List[List[int]]
    for lst in list_items:
        print(lst, reverse_ascending_sublists(lst))


if __name__ == '__main__':
    main()

reverse_reversed.py

#!/usr/bin/env python3
"""
Reversing the reversed

Create and return a new list that contains the items in
reverse, but so that whenever each item is itself a list,
its elements are also reversed. This reversal of sublists
must keep going on all the way down, no matter how deep
the nesting of these lists, so you necessarily have to
use recursion to solve this problem. The base case handles
any argument that is not a list. When items is a list
(use the Python function type or the isinstance operator
to check this), recursively reverse the elements that
this nested list contains. (List comprehensions might
come handy in solving this problem.) Note that this
function must create and return a new list to represent
the result, and should not rearrange or otherwise touch
the contents of the original list.
"""
from typing import List, NoReturn, Any
import copy


def reverse_reversed(items: List[Any]) -> List[Any]:
    new_items = copy.deepcopy(reversed(items))  # type: List[Any]
    new_items = [reverse_reversed(item) if isinstance(item, list) else item
                 for item in new_items]
    return new_items


def main() -> NoReturn:
    list_items = [
        [1, [2, 3, 4, 'yeah'], 5],
        [[[[[[1, 2]]]]]],
        [42, [99, [17, [33, ['boo!']]]]]
    ]  # type: List[List[Any]]
    for items in list_items:
        print(items, reverse_reversed(items))


if __name__ == '__main__':
    main()

sort_by_digit_count.py

#!/usr/bin/env python3
"""
Sort integers by their digit counts

Normally we would sort a list of integers according
to their magnitude. However, sorting can be performed
with respect to arbitrary comparison criteria, as long
as those criteria satisfy the mathematical requirements
of a total ordering relation. To demonstrate this, let
us define a wacky ordering comparison between positive
integers in that for any two integers, the one that contains
the digit 9 more times than the other is considered to be larger,
regardless of the magnitude and other digits of these numbers.
"""
from typing import List, NoReturn


def sort_by_digit_count(items: List[int]) -> List[int]:
    scores = []  # type: List[List[int]]
    for item in items:
        total = 0  # type: int
        # Convert item to list of digits as 12 => ['1', '2']
        digits = list(str(item))
        for digit in digits:
            # Count total score
            total += int(digit)
        # Count how many 9 in item
        nb_9 = digits.count('9')
        scores.append([item, nb_9, total])
    result = []  # type: List[int]
    # First sort on nb_9 (prior #1) then on total (prior #2)
    for score in sorted(scores,
                        key=lambda score: (score[1], score[2]),
                        reverse=True):
        result.append(score[0])
    return result


def main() -> NoReturn:
    list_items = [
        [1, 2, 3, 3, 4, 5, 6, 1, 2, 3],
        [23, 22, 23, 22],
        [98, 19, 4321, 9999, 73, 241, 111111, 563, 33]
    ]  # type: List[List[int]]
    for lst in list_items:
        print(lst, sort_by_digit_count(lst))


if __name__ == '__main__':
    main()