Лаб. 04: Абстракция данных и списки

Теория

Списки

Список — это структура данных в Python для хранения множества значений. Каждый элемент может быть разного типа, более того, элементом списка может быть другой список! Для создания списка используют квадратные скобки и перечисление элементов через запятую.

>>> list_of_nums = [1, 2, 3, 4]
>>> list_of_bools = [True, True, False, False]
>>> nested_lists = [1, [2, 3], [4, [5]]]

К элементам списка можно обращаться по порядковому номеру — индексу. Нумерация начинается с 0.

>>> lst = [6, 5, 4, 3, 2, 1]
>>> lst[0]
6
>>> lst[3]
3

Часто бывает нужно узнать длину списка. Для этого используется функция len.

>>> len([])
0
>>> len([2, 4, 6, 8, 10])
5

Пустой список [] — это ложное значение. Можно производить действия над непустыми списками так:

if lst:
    # Какая-то обработка

Это эквивалентно.

if len(lst) > 0:
    # Какая-то обработка

Списковые включения (list comprehensions)

Списковые включения — это компактный и эффективный способ создавать списки из последовательностей. Полный синтаксис спискового включения выглядит так:

[<выражение> for <элемент> in <последовательность> if <условие>]

Смотри:

>>> [i**2 for i in [1, 2, 3, 4] if i % 2 == 0]
[4, 16]

Здесь i пробегает по всем значениям [1, 2, 3, 4]. В новый список попадут только те элементы, для которых i % 2 == 0 (то есть чётные). В новый список заносятся не значения i, а i**2. Другими словами, это списковое включение отфильтровывает чётные значения и возводит их в квадрат. Эквивалентное поведение будет у такого фрагмента кода:

>>> lst = []
>>> for i in [1, 2, 3, 4]:
...     if i % 2 == 0:
...         lst += [i**2]
>>> lst
[4, 16]

Часть спискового включения, начинающаяся с if, опциональна. Можно не проводить фильтрацию.

>>> [i**2 for i in [1, 2, 3, 4]]
[1, 4, 9, 16]

Абстракция данных

Это мощная концепция в компьютерных науках, позволяющая работать с кодом как с объектами предметной области. Программист может не беспокоиться о том, как устроен тот или иной объект — нужно лишь знать, что он делает.

Абстракция данных позволяет откидывать из рассмотрения второстепенные детали, так же как люди делают с окружающим миром. Если водитель управляет машиной, ему не важно, как устроен двигатель и из какого именно материала сделаны шины — достаточно вращать руль и жать на педаль газа.

Абстрактный тип данных (АТД) определяется двумя видами функций:

Конструкторы — функции для создания АТД;
Селекторы — функции для получения информации об объекте.

Создание АТД подразумевает сокрытие информации об устройстве реализации от пользователя АТД (тоже программиста), который, как и водитель автомобиля, не интересуется подробностям.

Основная часть

После завершения работы над каждым вопросом фиксируй изменения (делай коммит):

$ git add .
$ git commit -m "Решение вопроса X"

Так же не возбраняется в любое время проталкивать изменения на GitHub:

$ git push

Вопрос 1: Доступ по индексу (ПСП)

Проверять правильность ответов на ПСП-вопросы можно и нужно из терминала вот таким образом:

$ python3 lab_04.py

Для каждого списка нужно записать выражение, чтобы его результат равнялся 7. Например, если x = [7], ответ будет x[0].

>>> x = [1, 3, [5, 7], 9]
>>> x[______]
7
>>> x = [[7]]
>>> x[______]
7
>>> x = [3, 2, 1, [9, 8, 7]]
>>> x[______]
7
>>> x = [[3, [5, 7], 9]]
>>> x[______]
7

Представь себя пайтоном! Что получится?

>>> lst = [3, 2, 7, [84, 83, 82]]
>>> lst[4]
______
>>> lst[3][0]
______

Вопрос 2: А это вообще как? (ПСП)

>>> [x*x for x in range(5)]
______
>>> [n for n in range(10) if n % 2 == 0]
______
>>> ones = [1 for i in ["привет", "как", "сам"]]
>>> ones + [str(i) for i in [6, 3, 8, 4]]
______
>>> [i+5 for i in [n for n in range(1,4)]]
______

>>> [i**2 for i in range(10) if i < 3]
______
>>> lst = ['привет' for i in [1, 2, 3]]
>>> print(lst)
______
>>> lst + [i for i in ['1', '2', '3']]
______

Вопрос 3: Если это не то?

Определи функцию if_this_not_that, которая принимает список целых i_list и целое число this. Каждый элемент в i_list, если элемент больше this, выводится в консоль; в противном случае выводится слово that.

Проверять правильность решения теперь нужно так:

$ python3 -m doctest lab_04.py

def if_this_not_that(i_list, this):
    """
    Определи функцию, которая принимает список целых `i_list` и целое число
    `this`. Каждый элемент в `i_list`, если элемент больше `this`, выводится в консоль;
    в противном случае выводится слово `that`.

    >>> original_list = [1, 2, 3, 4, 5]
    >>> if_this_not_that(original_list, 3)
    that
    that
    that
    4
    5
    """
    "*** ТВОЙ КОД ЗДЕСЬ ***"

Абстракция данных (города)

Пусть есть абстрактный тип данных для описания городов. У города есть название name, широта latitude и долгота longitude.

Имеется конструктор:

make_city(name, lat, lon) — создаёт объект, описывающий город с названием name, широтой lat и долготой lon.

И три селектора:

get_name(city) — возвращает название города;
get_lat(city) — возвращает широту города;
get_lon(city)— возвращает долготу города.

Пример использования конструктора и селекторов для создания объекта и получения информации из него:

>>> city = make_city('Ярославль', 57.616667, 39.85)
>>> get_name(city)
'Ярославль'
>>> get_lat(city)
57.616667
>>> get_lon(city)
39.85

И конструктор, и селекторы могут быть найдены в файле lab_04.py; ты можешь даже изучить, как они устроены. Однако не забывай, что абстракция данных состоит как раз в противоположном — не важно, как устроен абстрактный тип данных. Важно, что с ним можно взаимодействовать и использовать его целиком.

Всё же вот эти функции:

def make_city(name, lat, lon):
    return [name, lat, lon]

def get_name(city):
    return city[0]

def get_lat(city):
    return city[1]

def get_lon(city):
    return city[2]

Вопрос 4: Расстояния

Теперь сделай функцию distance, которая вычисляет расстояние между двумя заданными городами. Расстояние между \((x_1,y_1)\) и \((x_2,y_2)\) рассчитывай по формуле:

\[d = \sqrt{(x_2-x_1)^2+(y_2-y_1)^2}\]

Нужно получать значения координат, используя селекторы.

from math import sqrt
def distance(city1, city2):
    """
    >>> city1 = make_city('city1', 0, 1)
    >>> city2 = make_city('city2', 0, 2)
    >>> distance(city1, city2)
    1.0
    >>> city3 = make_city('city3', 6.5, 12)
    >>> city4 = make_city('city4', 2.5, 15)
    >>> distance(city3, city4)
    5.0
    """
    "*** ТВОЙ КОД ЗДЕСЬ ***"

Вопрос 5: Ближайший город

Теперь сделай функцию closer_city, определяющую, какой из городов city1 или city2 ближе к заданным координатам lat, lon. В решении можно использовать только селекторы и конструктор, а также определённую выше функцию distance.

def closer_city(lat, lon, city1, city2):
    """
    Возвращает название города city1 или города city2 в зависимости от того,
    какой из них ближе к координате (lat, lon).

    >>> moscow = make_city('Москва', 55.75, 37.616667)
    >>> saint_petersburg = make_city('Питер', 59.9375, 30.308611)
    >>> closer_city(57.616667, 39.85, moscow, saint_petersburg)
    'Москва'
    >>> london = make_city('Лондон', 51.507222, -0.1275)
    >>> mumbai = make_city('Мумбаи', 18.975, 72.825833)
    >>> closer_city(57.616667, 39.85, london, mumbai)
    'Лондон'
    """
    "*** ТВОЙ КОД ЗДЕСЬ ***"

Вопрос 6: Не пересекай границу абстракции

Работая с абстрактным типом данных важно всегда, когда это возможно, использовать его конструктор и селекторы не полагаясь на внутреннюю реализацию. Обращение напрямую ко внутренностям абстрактного типа данных известно как нарушение границы абстракции. Не делай так!

Даже если бы в предыдущих вопросах произошло нарушение границы абстракции, доктесты не обнаружили бы этого. Чтобы проверить, что всё сделано верно, надо заменить реализацию абстрактного типа данных. Для это раскомментируй эти строчки в файле lab_04.py и выполни тестирование.

make_city = lambda name, lat, lon: { 'name': name, 'lat': lat, 'lon': lon }
get_name = lambda city: city['name']
get_lat = lambda city: city['lat']
get_lon = lambda city: city['lon']

Если что-то поломалось — поправь.

Дополнительные вопросы: N в ряд

Ты, наверное, знаешь про игру «Четыре в ряд». Играют двое, бросая фишки своего цвета в своего рода регулярную решётку. Фишка опускается сверху и ложится в первом незанятом месте. Выигрывает тот, кто соберёт из фишек своего цвета линию из четырёх по вертикали, горизонтали или вертикали.

Расширим правила тем, что вместо 4 надо собирать линии длины N. И приступим к созданию текстовой версии игры.

Проектируем «N в ряд»

Пусть сражаются игроки X и O. Пустые поля обозначим так: -. Игровую доску будем представлять списком списков, поскольку доска двумерная. То есть, список

'[['-', '-', '-', '-'], ['O', 'O', 'O', 'X'], ['X', 'X', 'X', 'O']]'

будет представлять поле

- - - -
O O O X
X X X O

Что означает количество вложенных списков? А как соотносятся элементы этих списков с игровой ситуацией? Как только разберёшься — можешь двигаться дальше.

Нумерация и строк, и столбцов на игровой доске будет начинаться с нуля — как будто мы такие труъ-программисты.

0  - - - -
1  O O O X
2  X X X O
   0 1 2 3

Попрос 7: Пустая доска

Для создания игры пригодится абстракция данных, поэтому сначала нужно сделать конструкторы. Пустое поле будет обозначаться строкой -.

Сперва напиши функцию create_row, создающую пустую строку доски. Эта функция должна состоять из единственного выражения.

def create_row(size):
    """
    Возвращает отдельную пустую строку поля заданного размера. Каждый пустой
    элемент обозначается строкой '-'.

    >>> create_row(5)
    ['-', '-', '-', '-', '-']
    """
    "*** ТВОЙ КОД ЗДЕСЬ ***"

Теперь можно браться за функцию create_board, создающую пустую игровую доску. Эта функция тоже должна состоять из единственного выражения, и в ней нужно использовать create_row.

def create_board(rows, columns):
    """Возвращает игровое поле заданного размера.

    >>> create_board(3, 5)
    [['-', '-', '-', '-', '-'], ['-', '-', '-', '-', '-'], ['-', '-', '-', '-', '-']]
    """
    "*** ТВОЙ КОД ЗДЕСЬ ***"

Попрос 8: Обновление доски

По ходу игры расположение фишек на доске будет меняться. Нужно как-то уметь поддерживать состояние доски актуальным. Проще всего после каждого хода пересоздавать доску, отражающую новое состояние игры. Сделай функцию replace_elem, которая принимает список lst, позицию index и значение нового элемента elem. Задача функции — вернуть новый список, в котором все элементы будут теми же, что и в lst, за исключением элемента в позиции index, значение которого должно быть elem.

Эта функция тоже должна состоять из единственного выражения.

def replace_elem(lst, index, elem):
    """Создаёт и возвращает новый список с теми же элементами, что и lst,
    за исключением элемента index, значение которого должно быть elem.

    >>> old = [1, 2, 3, 4, 5, 6, 7]
    >>> new = replace_elem(old, 2, 8)
    >>> new
    [1, 2, 8, 4, 5, 6, 7]
    >>> new is old         # проверяем, что replace_elem возвращает новый список
    False
    """
    assert index >= 0 and index < len(lst), 'Индекс за пределами размера списка'
    "*** ТВОЙ КОД ЗДЕСЬ ***"

Попрос 9: Управление фишками

Теперь доска готова! Займёмся селекторами. Нужно каким-то образом понимать какая фишка ('X', 'O' или '-') находится в заданном месте. Создай для этого функцию get_piece.

Поскольку get_piece — селектор, то внутри этой функции можно обращаться к доске как к списку списков.

Реши в одно выражение.

def get_piece(board, row, column):
    """Возвращает состояние поля в позиции (row, column).

    >>> rows, columns = 2, 2
    >>> board = create_board(rows, columns)
    >>> board = put_piece(board, rows, 0, 'X')[1] # Ставим "X" в столбец 0 поля и обновляем доску
    >>> board = put_piece(board, rows, 0, 'O')[1] # Ставим "O" в столбец 0 поля и обновляем доску
    >>> get_piece(board, 1, 0)
    'X'
    >>> get_piece(board, 1, 1)
    '-'
    """
    "*** ТВОЙ КОД ЗДЕСЬ ***"

Так. Теперь нужен способ добавлять фишки на поле, а то игра будет не очень-то интересной. Создай функцию put_piece, которая помещает фишку player в заданный столбец. Функция должна возвращать двухэлементный тапл (<индекс строки>, <новая доска>). Если столбец уже заполнен, первый элемент тапла должен быть равен -1. Второй элемент — новая доска с изменённым состоянием. Если фишку сунуть некуда, то создавать новую доску не нужно.

Считай, что индекс передаваемого столбца column попадает в границы доски. Помни, что проверять состояние ячеек можно функцией get_piece. Аргумент max_rows пригодится, чтобы определить, сколько ячеек можно проверить в столбце для нахождения свободной.

Возможно тебе придётся использовать функцию replace_elem дважды.

def put_piece(board, max_rows, column, player):
    """Размещает фишку игрока player в самом нижнем свободном поле заданного
    столбца. Возвращает тапл из двух элементов:

        1. Индекс строки, в которую встала фишка, или -1, если там нет мест.
        2. Новую доску.

    >>> rows, columns = 2, 2
    >>> board = create_board(rows, columns)
    >>> row, new_board = put_piece(board, rows, 0, 'X')
    >>> row
    1
    >>> row, new_board = put_piece(new_board, rows, 0, 'O')
    >>> row
    0
    >>> row, new_board = put_piece(new_board, rows, 0, 'X')
    >>> row
    -1
    """
    "*** ТВОЙ КОД ЗДЕСЬ ***"

Для того, чтобы проходили все доктесты, нужно сделать обе функции. Тесты из get_piece используют put_piece.

####### Граница абстракции #######

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

Вопрос 10: Ход

Напиши функцию make_move, которая позволяет сделать ход игроку. Отличие от put_piece состоит в проверке достоверности сведений о столбце col — функция make_move должна разместить на доске фишку только если заданный столбец существует. Так же, как и put_piece, функция make_move возвращает двухэлементный тапл.

Аргументы max_rows и max_cols показывают размер доски и могут быть использованы для определения корректности других аргументов.

def make_move(board, max_rows, max_cols, col, player):
    """Размещает фишку игрока в столбец col доски в случае возможного хода.
    Возвращает тапл из двух значений:

        1. Если ход возможен, возвращается индекс строки, в которую попала фишка.
           Иначе возвращает -1.
        2. Обновлённая доска

    >>> rows, columns = 2, 2
    >>> board = create_board(rows, columns)
    >>> row, board = make_move(board, rows, columns, 0, 'X')
    >>> row
    1
    >>> get_piece(board, 1, 0)
    'X'
    >>> row, board = make_move(board, rows, columns, 0, 'O')
    >>> row
    0
    >>> row, board = make_move(board, rows, columns, 0, 'X')
    >>> row
    -1
    >>> row, board = make_move(board, rows, columns, -4, '0')
    >>> row
    -1
    """
    "*** ТВОЙ КОД ЗДЕСЬ ***"

Вопрос 11: Распечатка игрового состояния

Во время игры было бы неплохо видеть, что происходит на доске. Напиши функцию print_board, которая будет распечатывать состояние доски.

Для того, чтобы доска выглядела хорошо, лучше использовать строки, а не списки. То есть, пусть список ['X', 'X', 'O', '-'] на экране выглядит так X X O - — состояния ячеек отделены друг от друга пробелами. Кстати, соединять строки можно так 'при'+'вет' = 'привет'.

Помни, что ты за границей абстракции. Сделать print_board нужно так, чтобы она обращалась только к селекторам, а не к нижележащим спискам.

Вполне вероятно, что доктесты будут проваливаться из-за дополнительного пробела в конце строки. Имей ввиду, от них хорошо помогает функция strip().

>>> s = '   привет '
>>> s.strip()
'привет'

def print_board(board, max_rows, max_cols):
    """
    Распечатывает доску. Строка 0 сверху, столбец 0 слева.

    >>> rows, columns = 2, 2
    >>> board = create_board(rows, columns)
    >>> print_board(board, rows, columns)
    - -
    - -
    >>> new_board = make_move(board, rows, columns, 0, 'X')[1]
    >>> print_board(new_board, rows, columns)
    - -
    X -
    """
    "*** ТВОЙ КОД ЗДЕСЬ ***"

С этого момента уже можно играть! Попробуй запустить:

$ python3 -i lab_04.py
>>> start_game()

Вопрос 12: Проверка выигрыша

Кто победил? В том-то и дело, что эта часть ещё не готова… Последнее, что осталось сделать — определять выигрышные ситуации.

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

Проверка выигрышной ситуации будет происходить после каждого хода, таким образом выиграть может только сделавший ход. Функции check_win_row и check_win_col принимают аргумент player, указывающий, чью победу требуется искать. Аргумент num_connect указывает, какой длины должна быть линия для победы. Аргументы max_rows и max_cols описывают размер игровой доски.

Не пересекай границу абстракции!

def check_win_row(board, max_rows, max_cols, num_connect, row, player):
    """
    Возвращает True, если игрок player победил в заданной строке, иначе False.

    >>> rows, columns, num_connect = 4, 4, 2
    >>> board = create_board(rows, columns)
    >>> board = make_move(board, rows, columns, 0, 'X')[1]
    >>> board = make_move(board, rows, columns, 0, 'O')[1]
    >>> check_win_row(board, rows, columns, num_connect, 3, 'O')
    False
    >>> board = make_move(board, rows, columns, 2, 'X')[1]
    >>> board = make_move(board, rows, columns, 0, 'O')[1]
    >>> check_win_row(board, rows, columns, num_connect, 3, 'X')
    False
    >>> board = make_move(board, rows, columns, 1, 'X')[1]
    >>> check_win_row(board, rows, columns, num_connect, 3, 'X')
    True
    >>> check_win_row(board, rows, columns, 4, 3, 'X')           # Победа зависит от num_connect
    False
    >>> check_win_row(board, rows, columns, num_connect, 3, 'O') # Ищем победу только заданного игрока
    False
    """
    "*** ТВОЙ КОД ЗДЕСЬ ***"

def check_win_column(board, max_rows, max_cols, num_connect, col, player):
    """
    Возвращает True, если игрок player победил в заданном столбце, иначе False.

    >>> rows, columns, num_connect = 5, 5, 2
    >>> board = create_board(rows, columns)
    >>> board = make_move(board, rows, columns, 0, 'X')[1]
    >>> board = make_move(board, rows, columns, 1, 'O')[1]
    >>> check_win_column(board, rows, columns, num_connect, 0, 'X')
    False
    >>> board = make_move(board, rows, columns, 1, 'X')[1]
    >>> board = make_move(board, rows, columns, 1, 'O')[1]
    >>> check_win_column(board, rows, columns, num_connect, 1, 'O')
    False
    >>> board = make_move(board, rows, columns, 2, 'X')[1]
    >>> board = make_move(board, rows, columns, 1, 'O')[1]
    >>> check_win_column(board, rows, columns, num_connect, 1, 'O')
    True
    >>> check_win_column(board, rows, columns, 4, 1, 'O')
    False
    >>> check_win_column(board, rows, columns, num_connect, 1, 'X')
    False
    """
    "*** ТВОЙ КОД ЗДЕСЬ ***"

Вопрос 13: Победа!

Осталось собрать всё вместе. Сделай функцию check_win, которая возвращает True, если на доске есть победная комбинация в любом направлении (вертикальном, горизонтальном или диагональном).

Используй функции check_win_row, check_win_column и check_win_diagonal(board, max_rows, max_cols, num_connect, row, col, player) (она уже есть в файле).

def check_win(board, max_rows, max_cols, num_connect, row, col, player):
    """
    Возвращает True, если игрок player победил любым образом в заданных строке,
    столбце или диагонали (row, col), иначе False.

    >>> rows, columns, num_connect = 2, 2, 2
    >>> board = create_board(rows, columns)
    >>> board = make_move(board, rows, columns, 0, 'X')[1]
    >>> board = make_move(board, rows, columns, 1, 'O')[1]
    >>> board = make_move(board, rows, columns, 0, 'X')[1]
    >>> check_win(board, rows, columns, num_connect, 0, 0, 'O')
    False
    >>> check_win(board, rows, columns, num_connect, 0, 0, 'X')
    True

    >>> board = create_board(rows, columns)
    >>> board = make_move(board, rows, columns, 0, 'X')[1]
    >>> board = make_move(board, rows, columns, 0, 'O')[1]
    >>> board = make_move(board, rows, columns, 1, 'X')[1]
    >>> check_win(board, rows, columns, num_connect, 1, 0, 'X')
    True
    >>> check_win(board, rows, columns, num_connect, 0, 0, 'X')
    False

    >>> board = create_board(rows, columns)
    >>> board = make_move(board, rows, columns, 0, 'X')[1]
    >>> board = make_move(board, rows, columns, 1, 'O')[1]
    >>> board = make_move(board, rows, columns, 1, 'X')[1]
    >>> check_win(board, rows, columns, num_connect, 0, 0, 'X')
    False
    >>> check_win(board, rows, columns, num_connect, 1, 0, 'X')
    True
    """
    diagonal_win = check_win_diagonal(board, max_rows, max_cols, num_connect,
                                      row, col, player)
    "*** ТВОЙ КОД ЗДЕСЬ ***"

Не забудь отправить работу на проверку:

$ git add .
$ git commit -m "Решение всех вопросов"
$ git push