Программирование

И. В. Щуров, НИУ ВШЭ

Данный notebook является набором задач по курсу «Программирование» (Магистерская программа «Журналистика данных», НИУ ВШЭ, 2018-19).

На странице курса находятся другие материалы.

Домашнее задание №7

Максимум за ДЗ можно набрать 18 баллов.

Чтобы сдать ДЗ, его надо загрузить в nbgr-x в виде ipynb-файла. Получить ipynb-файл можно, выбрав в Jupyter пункт меню File → Download as... → IPython Notebook (.ipynb).

Задача 1 (1 балл)

Написать функцию sumprod(u, v), принимающую на вход два списка и вычисляющая сумму попарных произведений их элементов. Например, sumprod([1, 2, 3], [4, 5, 6]) должен вернуть результат вычисления 1 * 4 + 2 * 5 + 3 * 6, то есть 32.

Подсказка. Здесь нужно использовать zip. Задачу можно решить в одну строку с помощью list comprehensions (списочных включений) и функции sum (которую можно использовать).

In [ ]:
# YOUR CODE HERE
In [ ]:
assert sumprod([1, 2, 3], [4, 5, 6]) == 32
assert sumprod([1, 0], [0, 1]) == 0
assert sumprod([1.1, 2.2], [-2.2, 1.1]) == 0
assert sumprod(range(100), range(100)) == 328350

Задача 2 (1 балл)

Написать функцию elementwise_concat(words1, words2, sep), принимающую на вход два списка строк words1 и words2 и строку sep, и возвращающую список, состовленный следующим образом: его первый элемент — это первый элемент списка words1, сконкатенированный с sep и затем с первым элементом words2, второй элемент — второй элемент words1, сконкатенированный с sep, а затем со вторым элементом words2 и т.д. Например, elementwise_concat(['Harry', 'Ron'], ['Potter', 'Weasley'], sep='+') должен вернуть список ['Harry+Potter', 'Ron+Weasley'].

В решении необходимо использовать list comprehensions (списковые включения) и zip.

In [ ]:
# YOUR CODE HERE
In [ ]:
assert elementwise_concat(['Harry', 'Ron'], 
                          ['Potter', 'Weasley'], "") == ['HarryPotter', 
                                                     'RonWeasley']
assert elementwise_concat(['a'], ['bb'], "") == ['abb']
assert elementwise_concat(map(str, range(10)),
                          map(str, range(9, -1, -1)), "") == ['09', '18', '27', 
                                                          '36', '45', '54', 
                                                          '63', '72', '81', 
                                                          '90']
assert elementwise_concat(['Harry', 'Ron'], 
                          ['Potter', 'Weasley'], sep="+") == ['Harry+Potter', 
                                                              'Ron+Weasley']
assert elementwise_concat(['Harry', 'Harry'], ['Ron', 'Hermiona'], 
                          sep=' and ') == ['Harry and Ron', 
                                           'Harry and Hermiona']

Задача 3 (1 балл)

Написать функцию swap(some_list, i, j), меняющую в списке some_list местами элементы с индексами i и j. Функция должна модифицировать переданный список some_list и не должна ничего возвращать.

In [ ]:
# YOUR CODE HERE
In [ ]:
this_list = [1, 2, 10, 35, 20]
x = swap(this_list, 0, 4)
assert x is None, "Ваша функция ничего не должна возвращать"
assert this_list == [20, 2, 10, 35, 1]

swap(this_list, 3, 3)
assert this_list == [20, 2, 10, 35, 1]

this_list = [1, 2, 10, 35, 20] * 100
swap(this_list, 1, len(this_list) - 2)
assert this_list == [1, 35, 10, 35, 20] + [1, 2, 10, 35, 20] * 98 + [1, 2, 10, 2, 20]

Задача 4 (1 балл)

Написать функцию swapped(some_list, i, j), возвращающую новый список, совпадающий со списком some_list, в котором поменяли местами элементы с индексами i и j. Список some_list не должен меняться.

In [ ]:
# YOUR CODE HERE
In [ ]:
this_list = [1, 2, 10, 35, 20]
backup_list = this_list.copy()
x = swapped(this_list, 0, 4)
assert this_list == backup_list, "Исходный список не должен изменяться"
assert x == [20, 2, 10, 35, 1]

assert swapped([1, 2, 3, 4], 2, 2) == [1, 2, 3, 4]

this_list = [1, 2, 10, 35, 20] * 100
assert swapped(this_list, 1, len(this_list) - 2) == ([1, 35, 10, 35, 20] +
                                                     [1, 2, 10, 35, 20] * 98 + 
                                                     [1, 2, 10, 2, 20])

Задача 5 (1 балл)

Написать функцию first_str(words), принимающую на вход список строк и возвращающую ту из них, которая будет идти первой при упорядочивании по алфавиту.

Подсказка. Хотите отсортировать весь список и взять его первый элемент? Это не самое лучшее решение: для сортировки всего списка понадобится много времени, если он большой. Можно заметить, что строки можно сравнивать: строка A меньше строки B, если A идёт раньше при сортировке по алфавиту, чем B. Следовательно, вас интересует такая строка из списка, которая будет меньше, чем все остальные строки этого списка. Как называется элемент списка, который меньше всех остальных элементов списка? Как его найти?

In [ ]:
# YOUR CODE HERE
In [ ]:
from random import shuffle, seed
seed(0)
def shuffle_test(f, inp, outp, n=10):
    for i in range(n):
        shuffle(inp)
        assert f(inp)==outp
def test(inp,outp, n=10):
    return shuffle_test(first_str, inp, outp)

test(['Hello'], 'Hello')
test(['Hello', 'World'], 'Hello')
test(['hello', 'World'], 'World')
test(['a','b','c','d','e'], 'a', 20)
test(['hello']*100+['World'], 'World')
test(['a', 'aa', 'aaa', 'aaaa'], 'a')
test(['q', 'ww', 'eee', 'zzzzz'], 'eee')


del shuffle, seed, shuffle_test, test
print("Верно!")

Задача 6 (1 балл)

Написать функцию get_first_student_grade(students), принимающую на вход список students, каждый элемент которого является кортежем: первый элемент кортежа является именем студента, а второй его оценкой. Например: students = [('Bob', 3), ('Alice', 4)]. Функция должна вернуть оценку студента, имя которого является первым при алфавитной сортировке. (В нашем случае должна вернуть число 4.) Все студенты имеют разные имена.

Подсказка. См. подсказку к задаче 1. Возможно, функции min() удастся скормить кортежи? Попробуйте! Кстати, задача решается ровно в одну строчку (не считая def). Использовать библиотеки нельзя.

In [ ]:
# YOUR CODE HERE
In [ ]:
from random import shuffle, seed
seed(0)
def shuffle_test(f, inp, outp, n=10):
    for i in range(n):
        shuffle(inp)
        assert f(inp)==outp
def test(inp,outp, n=10):
    return shuffle_test(get_first_student_grade, inp, outp)
test([('Bob', 3), ('Alice', 4)], 4)
test([('Zzz', 1)], 1)
test([('Haha', 2), ('Hoho', 3), ('Zzz', 4), ('aaaa', 5)], 2)

del shuffle, seed, shuffle_test, test
print("Хорошо, поехали дальше!")

Задача 7 (1 балл)

Написать функцию my_map(f, some_list), которая принимает на вход функцию f и список some_list и возвращает новый список, полученный путём применения функции f к каждому элементу списка some_list. Например, my_map(str, [1, 2, 3]) должен вернуть список, получающийся как [str(1), str(2), str(3)], то есть ['1', '2', '3'].

In [ ]:
# YOUR CODE HERE
In [ ]:
assert my_map(str, [1, 2, 3]) == ['1', '2', '3']
assert my_map(int, ['12', '34', '56', '789']) == [12, 34, 56, 789]
assert my_map(lambda x: x + 1, [1, 2, 3, 4]) == [2, 3, 4, 5]
assert my_map(None, []) == []
assert my_map(lambda x: x, list(range(10000))) == list(range(10000))
print("Хорошо! Кстати, примерно то же самое делает встроенная функция map")

Задача 8 (2 балла)

Написать функцию get_name_of_best_student(students), принимающую на вход список students, каждый элемент которого является кортежем: первый элемент кортежа является именем студента, а второй его оценкой. Например: students = [('Bob', 3), ('Alice', 4)]. Функция должна вернуть имя студента с наибольшей оценкой. Если таких студентов несколько, она должна вернуть имя того из них, кто первый встречается в списке students (в том порядке, в котором этот список передан). Например, для списка [('Bob', 4), ('Alice', 4)] необходимо вернуть 'Bob', а для списка [('Alice', 4), ('Bob', 4)] вернуть 'Alice'.

Подсказка. У функций min() и max() есть необязательный параметр key, работающий так же, как и у функции sort() — то есть при выборе наибольшего/наименьшего элемента сравниваются не сами элементы, а значение ключа сортировки на них. К чему бы это? Кстати, задачу можно решить без циклов и условных операторов.

In [ ]:
# YOUR CODE HERE
In [ ]:
assert get_name_of_best_student([('Bob', 4), ('Alice', 4)]) == 'Bob'
assert get_name_of_best_student([('Alice', 4), ('Bob', 4)]) == 'Alice'
assert get_name_of_best_student([('Zzz', 3), ('Bob', 4), ('Alice', 4)]) == 'Bob'
assert get_name_of_best_student([('Alice', 4), ('Zzz', 3), ('Bob', 4)]) == 'Alice'
assert get_name_of_best_student([('Zzz', 5), ('Bob', 4), ('Alice', 4)]) == 'Zzz'
assert get_name_of_best_student([('Alice', 4), ('Zzz', 5), ('Bob', 4)]) == 'Zzz'
assert get_name_of_best_student([('Alice', 4), ('Zzz', 5), ('Bob', 4), ('Zzz', 5)]) == 'Zzz'
assert get_name_of_best_student([('Alice', 4), ('Zzz', 5), ('Bob', 4), ('Zzz', 3)]) == 'Zzz'
assert get_name_of_best_student([('Alice', 0)]) == 'Alice'
print("Отлично!")

Задача 9 (2 балла)

Написать функцию sort_by_last_name(names), которая на вход принимает список строк с именами и фамилиями (например, ["Donald Trump", "Hillary Clinton", "Gary Johnson", "Jill Stein", "Darrell Castle", "Evan McMullin"]), сортирующую его по фамилиям и возвращающую в отсортированном виде. (Можно менять исходный список.) Для указанного выше списка функция должна вернуть список ['Darrell Castle', 'Hillary Clinton', 'Gary Johnson', 'Evan McMullin', 'Jill Stein', 'Donald Trump']. Порядок записей с одинаковыми фамилиями должен сохраняться. Например, для списка ["Alice Smith", "John Doe", "Jack Doe"] должно быть возвращено ["John Doe", "Jack Doe", "Alice Smith"].

Подсказка. Вам нужно будет написать функцию, получающую на вход элемент списка names (то есть одну строку с именем и фамилией) и возвращающую фамилию. Затем эту функцию необходимо передать функции sorted в качестве параметра key.

In [ ]:
# YOUR CODE HERE
In [ ]:
from random import shuffle, seed
seed(0)
def shuffle_test(f, inp, outp, n=10):
    for i in range(n):
        shuffle(inp)
        assert f(inp)==outp
def test(inp,outp, n=10):
    return shuffle_test(sort_by_last_name, inp, outp)

test(["Donald Trump", "Hillary Clinton", "Gary Johnson", "Jill Stein", "Darrell Castle", "Evan McMullin"],
     ['Darrell Castle', 'Hillary Clinton', 'Gary Johnson', 'Evan McMullin', 'Jill Stein', 'Donald Trump'])
assert sort_by_last_name(["Aaa Aaa", "Aaa Bbb", "Bbb Aaa"]) == ["Aaa Aaa", "Bbb Aaa", "Aaa Bbb"]
assert sort_by_last_name(["Aaa Bbb", "Bbb Aaa", "Aaa Aaa"]) == ["Bbb Aaa", "Aaa Aaa", "Aaa Bbb"]
assert sort_by_last_name(["Alice Smith", "John Doe", "Jack Doe"]) == ["John Doe", "Jack Doe", "Alice Smith"]

del shuffle, seed, shuffle_test, test
print("Не так уж это было и страшно, да?")

Задача 10 (2 балла)

Написать функцию sort_by_last_first_name(names), которая на вход принимает список строк с именами и фамилиями, сортирующую его по фамилии, а при совпадении фамилий — по именам, и возвращающую в отсортированном виде. (Можно менять исходный список.) Например, для списка ["Alice Smith", "John Doe", "Jack Doe"] должно быть возвращено ["Jack Doe", "John Doe", "Alice Smith"].

In [ ]:
# YOUR CODE HERE
In [ ]:
from random import shuffle, seed
seed(0)
def shuffle_test(f, inp, outp, n=10):
    for i in range(n):
        shuffle(inp)
        assert f(inp)==outp
def test(inp,outp, n=10):
    return shuffle_test(sort_by_last_first_name, inp, outp)

test(["Donald Trump", "Hillary Clinton", "Gary Johnson", "Jill Stein", "Darrell Castle", "Evan McMullin"],
     ['Darrell Castle', 'Hillary Clinton', 'Gary Johnson', 'Evan McMullin', 'Jill Stein', 'Donald Trump'])
test(["Donald Trump", "Melania Trump", "Hillary Clinton", "Bill Clinton", 
      "Gary Johnson", "Jill Stein", "Darrell Castle", "Evan McMullin"],
     ['Darrell Castle', "Bill Clinton", 'Hillary Clinton', 'Gary Johnson', 'Evan McMullin', 
      'Jill Stein', 'Donald Trump', "Melania Trump"])
test(["Aaa Aaa", "Aaa Bbb", "Bbb Aaa"],  ["Aaa Aaa", "Bbb Aaa", "Aaa Bbb"])
test(["Alice Smith", "John Doe", "Jack Doe"], ["Jack Doe", "John Doe", "Alice Smith"])

del shuffle, seed, shuffle_test, test
print("Хорошо!")

Задача 11 (4 балла)

Это необязательная задача. Можно смело пропустить.

Написать функцию sort_gradebook(gradebook), принимающую на вход некую ведомость в виде списка, элементами которого являются списки такого вида: [first_name, last_name, grade_1, grade_2, ..., grade_n, final_grade], где first_name — имя студента, last_name — его фамилия, grade_1, ..., grade_n — оценки студента по контрольным от 1 до n (число n — общее число контрольных, оно одинаковое для конкретного gradebook, но заранее не известно), final_grade — итоговая оценка. Функция должна отсортировать gradebook следующим образом (и вернуть его отсортированным):

  • По итоговой оценке;
  • При совпадении итоговой оценки — по оценке за первую контрольную;
  • При совпадении всего предыдущего — по оценке за вторую контрольную;
  • При совпадении всего предыдущего — по оценке за третью контрольную (и т.д. пока контрольные не закончатся);
  • При совпадении всех оценок — по фамилии;
  • При совпадении всех оценок и фамилии — по имени.

Сортировки по оценкам производятся по убыванию, а по фамилии и имени — по возрастанию.

Примеры см. в тестах.

Подсказка. Если при сортировке списка с ключом получаются одинаковые ключи, то порядок следования элементов сохраняется. Ключом может быть не только число или строка, но и список.

In [ ]:
# YOUR CODE HERE
In [ ]:
from itertools import permutations
def test_sort(inp, outp):
    for i in permutations(inp):
        assert sort_gradebook(list(i)) == outp

test_sort([
        ['Alice', 'Smith', 2, 3, 4],
        ['John', 'Smith', 2, 3, 5]
    ], [
        ['John', 'Smith', 2, 3, 5],
        ['Alice', 'Smith', 2, 3, 4]
])

test_sort([
        ['Alice', 'Smith', 2, 3, 4],
        ['John', 'Smith', 2, 3, 4]
    ], [
    ['Alice', 'Smith', 2, 3, 4],
    ['John', 'Smith', 2, 3, 4]
])

test_sort([
        ['Alice', 'Smith', 1, 3, 4],
        ['John', 'Smith', 2, 3, 4]
        ], [
        ['John', 'Smith', 2, 3, 4],
        ['Alice', 'Smith', 1, 3, 4]
])

test_sort([
            ['Alice', 'Smith', 1, 1, 1, 3, 4],
            ['John', 'Smith', 1, 1, 2, 3, 4]],
                         [
            ['John', 'Smith', 1, 1, 2, 3, 4],
            ['Alice', 'Smith', 1, 1, 1, 3, 4]
])

test_sort([
            ['Alice', 'Doe', 1, 1, 3, 3, 4],
            ['Alice', 'Smith', 1, 1, 3, 3, 4],
            ['John', 'Smith', 1, 1, 2, 3, 4]], 
          [
            ['Alice', 'Doe', 1, 1, 3, 3, 4],
            ['Alice', 'Smith', 1, 1, 3, 3, 4],
            ['John', 'Smith', 1, 1, 2, 3, 4]
])

test_sort([
        ['Alice', 'Doe', 1, 1, 3, 3, 4],
        ['Alice', 'Smith', 1, 1, 3, 3, 4],
        ['John', 'Smith', 2, 1, 2, 3, 4]], 
          [
        ['John', 'Smith', 2, 1, 2, 3, 4],
        ['Alice', 'Doe', 1, 1, 3, 3, 4],
        ['Alice', 'Smith', 1, 1, 3, 3, 4],
])

del test_sort
print("Это была непростая задача!")

Задача 12 (2 балла)

Написать функцию sum_ints_in_file(filename), принимающую на вход имя файла, содержащего целые числа (каждое число на новой строке). Функция должна вернуть сумму этих чисел. Внутри файла могут содержаться пустые строки — их следует игнорировать.

Не забудьте закрыть файл!

In [ ]:
# YOUR CODE HERE
In [ ]:
try:
    del open
except:
    pass
from tempfile import NamedTemporaryFile
import os

testsuite = [([1, 2, 3]),
             ([5]),
             ([111, 23, 123]),
             ([0]),
             ([-1, -10, -123]),
             (0, -1, 1, 100, 500, 9999)]

for testlist in testsuite:
    try:
        f = NamedTemporaryFile(dir='.', delete=False, mode='w')
        name = f.name
        f.file.write("\n".join(map(str, testlist)))
        f.file.close()
        assert sum_ints_in_file(name) == sum(testlist)
    finally:
        os.remove(name)

import io

test_txt = io.StringIO("1\n2\n")

def get_test_txt():
    return test_txt

def open(file, mode = 'r', *args, **kwargs):
    return get_test_txt()

try:
    s = sum_ints_in_file("test.txt")
    assert test_txt.closed, "Вы забыли закрыть файл"
    assert s == 3
finally:
    del open
In [ ]:
try:
    f = NamedTemporaryFile(dir='.', delete=False, mode='w')
    name = f.name
    f.file.write("1\n\n2\n\n")
    f.file.close()
    assert sum_ints_in_file(name) == 3
except:
    print("Ошибка! Обратите внимание: файл может содержать пустые строки.")
    raise
finally:
    os.remove(name)

Задача 13 (3 балла)

Написать функцию three_best_applicants(portfolio), принимающую на вход имя файла с портфолио в формате, аналогичном этому файлу, и возвращающую список фамилий и имён трёх лучших абитуриентов, упорядоченных по числу набранных ими баллов (по убыванию). Каждый элемент возвращаемого списка должен был кортежем, в котором на первом месте стоит фамилия студента, а на втором — его имя. В файле идет сначала имя, потом фамилия, а потом число баллов, причём между именем и фамилией стоит пробел, а между фамилием и числом баллов — символ табуляции (\t).

In [ ]:
# YOUR CODE HERE
In [ ]:
from tempfile import NamedTemporaryFile
import os

def test_portfolio(inp, outp):
    try:
        f = NamedTemporaryFile(dir='.', delete=False, mode='w')
        name = f.name
        f.file.write(inp)
        f.file.close()

        obtained = three_best_applicants(f.name)
        assert obtained == outp, ("input file: {inp}, "
                                 "expected output: {outp} "
                                 "obtained output: {obtained}").format(
            inp=inp, outp=outp, obtained=obtained)
    finally:
        os.remove(name)

test_portfolio(
"""Ann Brown\t25
Emily Calvert\t89
Alice Charr\t78
Bill Taylor\t94
Polly Smith\t32
Jill Acker\t68
Tom Bass\t15
Victoria Greg\t48
Philipp Pruitt\t65
Cristine Evans\t82
""",[('Taylor', 'Bill'), ('Calvert', 'Emily'), ('Evans', 'Cristine')])

test_portfolio(
"""Ann Brown\t125
Emily Calvert\t89
Alice Charr\t78
Bill Taylor\t94
Polly Smith\t932
Victoria Greg\t648
Philipp Pruitt\t65
Cristine Evans\t82
""",[('Smith', 'Polly'), ('Greg', 'Victoria'), ('Brown', 'Ann')])

Задача 14 (1 балл)

Написать функцию seq(a, b, filename), создающую файл filename и записывающую в неё целые числа от a до b включительно, каждое число на своей строке. Не забудьте закрыть файл!

In [ ]:
# YOUR CODE HERE
In [ ]:
from tempfile import NamedTemporaryFile
import os

testsuite = [(10, 11), (100, 1000), (0, 10), (1, 2), (1, 1), (5, 5)]

for a, b in testsuite:
    f = NamedTemporaryFile(dir='.', delete=False)
    name = f.name
    f.close()
    try:
        seq(a, b, name)
        with open(name) as f:
            collected_output = list(map(int, f))
            assert collected_output == list(range(a, b + 1)), \
                "Incorrect output for a = {}, b = {}\n".format(a, b) + \
                "Your output:\n" + "\n".join(map(str,collected_output))
    finally:
        os.remove(name)

Задача 15 (2 балла)

Написать функцию censore_haha(filename), считывающую файл с именем, лежащем в переменной filename и записывающим его в новый файл, имя которого получается добавлением к концу имени исходного файла .censored.txt. При записи в новый файл все вхождения слова haha должны быть заменены на [censored], больше ничего не должно меняться.

Например, если функция была вызвана как censore_haha('test.txt'), она должна создать файл test.txt.censored.txt и записать в него отцензурированную версию исходного файла.

Обратите внимание: в новом файле не должно появиться новых (в т.ч. пустых) строк!

In [ ]:
# YOUR CODE HERE
In [ ]:
from tempfile import NamedTemporaryFile
import os

def test_censore(inp, outp):
    try:
        f = NamedTemporaryFile(dir='.', delete=False, mode='w')
        name = f.name
        f.file.write(inp)
        f.file.close()

        censore_haha(f.name)
        with open(f.name + ".censored.txt") as f:
            content = f.read()
        assert content == outp, ("input file: {inp}, "
                                 "expected output: {outp} "
                                 "obtained output: {content}".format(
                                 inp=inp, outp=outp, content=content
                                 ))
    finally:
        os.remove(name)

test_censore(
    "haha test\nanother haha haha test\nhahahaha hahahaha\n"
    "this is a test\nwell",
    ("[censored] test\nanother [censored] [censored] test\n"
    "[censored][censored] [censored][censored]\nthis is a test\nwell")
)

test_censore(
    (
        "this is a haha haha haha\n"
        "haha ha ha hahahahahaha ha haha\n"
        "\n"
        "ha\n"
        "ha\n"
        "\n"
        "thisisahahahathis\n"
        "well...\n"
        "\n"
        "Hello, world!\n"
    ),
    (
        "this is a [censored] [censored] [censored]\n"
        "[censored] ha ha [censored][censored][censored] ha [censored]\n"
        "\n"
        "ha\n"
        "ha\n"
        "\n"
        "thisisa[censored]hathis\n"
        "well...\n"
        "\n"
        "Hello, world!\n"
    )
)