Ctrl+K

Примерни решения на задачите по тема 4

Примерни решения на задачите по тема 4#

Важно ! Решенията на задачите трябва да бъдат написани изцяло във функционален стил - избягвайте цикли, мутация на данни и т.н. Позволено е да използвате list comprehension, map, filter, reduce и т.н.

Задача 1 (0.25т)#

Напишете функция compose, която приема две функции f и g и връща нова функция h, която е композицията на f и g.

Може да приемем, че g може да приема множество аргументи, а f - само един. (Композиция на две функции f и g е нова функция h, такава че h(x) = f(g(x)).)

def square(x):
    return x * x

def double(x):
    return 2 * x

def sum_(x, y):
    return x + y

# Write your code here:
def compose(f, g):
    def inner(*args, **kwargs):
        return f(g(*args, **kwargs))
    return inner

assert compose(square, double)(5) == 100
assert compose(double, square)(5) == 50

h = compose(square, double)
assert h(5) == 100

assert compose(double, sum_)(2, 3) == 10
assert compose(square, sum_)(x=2, y=4) == 36


"✅ All OK! +0.25 points"

'✅ All OK! +0.25 points'

Задача 2 (0.5т)#

Нека имаме функции, които връщат True или False.

Напишете декоратор на име retry, който извиква дадена функция, докато тя не върне True или не се преминат 3 опита.

# ---Internal state, do not touch---
counters = {
    'pass_instantly': 0,
    'pass_after_third_try': 0,
    'pass_after_fifth_try': 0,
    'never_pass': 0,
}

# Write your code here:
def retry(f):
    def inner(current_try=0, *args, **kwargs):
        if current_try == 3:
            return False

        result = f(*args, **kwargs)

        if result is True:
            return True
        
        return inner(current_try + 1, *args, **kwargs)
    return inner

@retry
def pass_instantly():
    counters['pass_instantly'] += 1
    return True

@retry
def pass_after_third_try():
    counters['pass_after_third_try'] += 1
    return counters['pass_after_third_try'] == 3

@retry
def pass_after_fifth_try():
    counters['pass_after_fifth_try'] += 1
    return counters['pass_after_fifth_try'] == 5

@retry
def never_pass():
    counters['never_pass'] += 1
    return False


assert pass_instantly() == True
assert counters['pass_instantly'] == 1
assert pass_after_third_try() == True
assert counters['pass_after_third_try'] == 3
assert pass_after_fifth_try() == False
assert counters['pass_after_fifth_try'] == 3
assert never_pass() == False
assert counters['never_pass'] == 3

"✅ All OK! +0.5 points"

'✅ All OK! +0.5 points'

Задача 3 (0.5т)#

Напишете функция на име pair_up, която приема списък от елементи, и връща нов списък, съставен от елементите на първия, групирани по двойки.

Или по-формално: ако \( l = [a_1, a_2, a_3, ...a_i, a_{i+1}, a_n] \), то \( pair\_up(l) = [(a_1, a_2), ..., (a_i, a_{i+1}), (a_{n-1}, a_n)] \)

list_1 = [1, 2, 3, 4, 5, 6]
list_2 = [1, 2, 3, 4, 5]
list_3 = []
list_4 = [1]
list_5 = [1, 2]


# Write your code here:
def pair_up(l):
    return list(zip(l[::2], l[1::2]))

assert pair_up(list_1) == [(1, 2), (3, 4), (5, 6)]
assert pair_up(list_2) == [(1, 2), (3, 4)]  # We ignore the last element, if we cannot pair it up
assert pair_up(list_3) == []
assert pair_up(list_4) == []
assert pair_up(list_5) == [(1, 2)]

"✅ All OK! +0.5 points"

'✅ All OK! +0.5 points'

Задача 4 (0.5т + 0.5т)#

Дадена е матрица с размери MxM от цели числа.

“Сила” на матрицата дефинираме като сумата на елементите по главния диагонал минус сумата на елементите по вторичния диагонал.

Напишете функция power_of_matrix, която изчислява силата на дадена матрица.

Забележка: Напишете функция по два начина:

  1. Чрез използване на list comprehension и sum

  2. Чрез използване на map и reduce

from functools import reduce

matrix_1 = [
    [1, 2, 3],
    [4, 5, 6],
    [7, 8, 9]
]

matrix_2 = [
    [2, 3, 4, 5],
    [5, 6, 7, 8],
    [9, 1, 6, 3],
    [-2, 3, 7, 7]
]

matrix_3 = []

# Write your code here
def power_of_matrix(matrix):
    main_diagonal = [row[i] for i, row in enumerate(matrix)]
    reverse_diagonal = [row[-i-1] for i, row in enumerate(matrix)]

    return sum(main_diagonal) - sum(reverse_diagonal)

def power_of_matrix(matrix):
    main_diagonal = map(lambda enumerated: enumerated[1][enumerated[0]], enumerate(matrix))
    reverse_diagonal = map(lambda enumerated: enumerated[1][-enumerated[0]-1], enumerate(matrix))

    sum_main_diagonal = reduce(lambda acc, item: acc + item, main_diagonal, 0)
    sum_reverse_diagonal = reduce(lambda acc, item: acc + item, reverse_diagonal, 0)

    return sum_main_diagonal - sum_reverse_diagonal

assert power_of_matrix(matrix_1) == 0
assert power_of_matrix(matrix_2) == 10
assert power_of_matrix(matrix_3) == 0
"✅ All OK! +0.5 points"

'✅ All OK! +0.5 points'

Задача 5 (1.5т)#

В шахът, конят се движи по един от следните начини:

  • две полета хоризонтално и едно вертикално

  • две полета вертикално и едно

Напомняме, че редовете се номерират от 1 до 8, а колоните - от A до H. В случая, нашият кон е на позиция d4. Той може да се премести на следните позиции: e7, f6, f4, e3, c3, b4, b6, c7

Напишете генератор, който приема начална позиция на кон, и връща всички възможни ходове.

[(i, j) for i in range(-2, 3) for j in range(-2, 3)]

def offset_move(row, collumn, offset):
    row_as_number = ord(row) - ord('a') + 1
    
    new_row_as_number = row_as_number + offset[0]
    new_collumn = collumn + offset[1]

    new_row = chr(new_row_as_number + ord('a') - 1)

    return new_row, new_collumn

def is_move_valid(new_move):
    row, column = new_move
    return ord('a') <= ord(row) <= ord('h') and 1 <= column <= 8

def possible_moves(row, collumn):
    offsets = [(2, 1), (1, 2), (-1, 2), (-2, 1), (-2, -1), (-1, -2), (1, -2), (2, -1)]

    
    return (new_move for offset in offsets if is_move_valid((new_move := offset_move(row, collumn, offset))))
    

# 2 possible moves
assert set(possible_moves('a', 1)) == {('c', 2), ('b', 3)}
assert set(possible_moves('h', 1)) == {('f', 2), ('g', 3)}
assert set(possible_moves('h', 8)) == {('f', 7), ('g', 6)}
assert set(possible_moves('a', 8)) == {('c', 7), ('b', 6)}

# 3 possible moves
assert set(possible_moves('a', 2)) == {('c', 3), ('b', 4), ('c', 1)}
assert set(possible_moves('a', 7)) == {('c', 6), ('b', 5), ('c', 8)}
assert set(possible_moves('h', 2)) == {('g', 4), ('f', 1), ('f', 3)}
assert set(possible_moves('h', 7)) == {('f', 6), ('g', 5), ('f', 8)}

# 4 possible moves
assert set(possible_moves('a', 3)) == {('c', 4), ('b', 5), ('b', 1), ('c', 2)}
assert set(possible_moves('h', 6)) == {('g', 8), ('f', 5), ('g', 4), ('f', 7)}
assert set(possible_moves('g', 2)) == {('e', 1), ('f', 4), ('h', 4), ('e', 3)}

# 6 possible moves
assert set(possible_moves('b', 3)) == {('c', 5), ('d', 2), ('c', 1), ('d', 4), ('a', 5), ('a', 1)}
assert set(possible_moves('g', 6)) == {('f', 4), ('h', 4), ('e', 5), ('e', 7), ('h', 8), ('f', 8)}

# 8 possible moves
assert set(possible_moves('d', 4)) == {('b', 3), ('b', 5), ('c', 2), ('c', 6), ('e', 2), ('e', 6), ('f', 3), ('f', 5)}
assert set(possible_moves('f', 6)) == {('h', 7), ('g', 8), ('e', 8), ('g', 4), ('d', 5), ('e', 4), ('h', 5), ('d', 7)}

# Generator tests
for move in possible_moves('a', 1):
    assert move in {('c', 2), ('b', 3)}

generator = possible_moves('a', 1)
assert next(generator) in {('c', 2), ('b', 3)}
assert next(generator) in {('c', 2), ('b', 3)}

try:
    next(generator)
    assert False
except StopIteration:
    pass

"✅ All OK! +1.5 points"

'✅ All OK! +0.25 points'

Задача 6 (1.5т)#

Дефинираме операцията конволюция на два списъка по следния начин:

\( X = {x_0, x_1, ..., x_n} \), \( Y = {y_0, y_1, ..., y_n} \)

\( f(X, Y) = { \{ \sum_{\substack{i, j \\ i+j=m}} X_i * Y_j | m=0..{2n-1}\}}\)

Напишете функция conv, която приема два списъка и връща резултата от тяхната конволюция.

# Write your code here:
def generate_indexes(m, n):
    indexes = ((i, j) for i in range(n) for j in range(n))
    indexes = filter(lambda x: x[0] + x[1] == m, indexes)

    return indexes

def conv_n(x, y, m):
    indexes = generate_indexes(m, len(x))

    return sum(x[i] * y[j] for i, j in indexes)

def conv(x, y):
    return [conv_n(x, y, m) for m in range(2 * len(x) - 1)]


assert conv([1, 2, 3], [4, 5, 6]) == [4, 13, 28, 27, 18]
assert conv([1, 2, 3], [3, 2, 1]) == [3, 8, 14, 8, 3]

assert conv([2, 4, 6, 7], [-1, -2, -3, -4]) == [-2, -8, -20, -39, -48, -45, -28]

assert conv([1], [2]) == [2]
assert conv([], []) == []

"✅ All OK! +1.5 points"

'✅ All OK! +1.5 points'

Задача 7 (0.75т)#

Разполагаме със стандартната игра “Tic-Tac-Toe” (или “X and O”).

Напишете функция determine_winner, която намира победителя в дадена игра.

Функцията ще приема дъска, която е представена като двумерен списък. Стойностите могат да бъдат ‘X’, ‘O’ или None (празно поле).

Функцията връща “X”, “O” или “Draw”.

def check_for_winner(board, player):
    # Check rows
    rows = (True for row in board if row.count(player) == len(row))
    
    # Check columns
    columns = (True for column in zip(*board) if column.count(player) == len(column))

    # Check diagonals
    main_diagonal = (row[i] for i, row in enumerate(board))
    main_diagonal_check = all(item == player for item in main_diagonal)

    reverse_diagonal = (row[-i-1] for i, row in enumerate(board))
    reverse_diagonal_check = all(item == player for item in reverse_diagonal)
    
    return any(rows) or any(columns) or main_diagonal_check or reverse_diagonal_check


def determine_winner(board):
    if check_for_winner(board, 'X'):
        return 'X'
    elif check_for_winner(board, 'O'):
        return 'O'
    else:
        return 'Draw'
    

board_1 = [
    ['X', 'O', 'X'],
    ['O', 'X', 'O'],
    ['O', 'X', 'X']
]
board_2 = [
    ['X', 'O', 'X'],
    ['O', 'O', 'O'],
    ['O', 'X', 'X']
]
board_3 = [
    ['X', 'O', 'X'],
    ['O', 'X', 'O'],
    ['O', 'X', 'O']
]

board_4 = [
    ['X', 'X', 'X'],
    ['O', 'O', None],
    [None, None, None]
]

board_5 = [
    ['X', 'O', 'X'],
    ['O', 'X', 'X'],
    ['O', 'O', 'O']
]

board_6 = [
    ['O', 'O', 'X'],
    ['O', 'X', None],
    ['X', 'X', None]
]

board_7 = [
    ['X', 'O', 'X'],
    ['X', 'O', 'O'],
    ['X', 'X', 'O']
]

board_8 = [
    ['O', 'X', 'O'],
    ['O', 'X', None],
    ['X', 'X', None]
]

board_9 = [
    ['X', 'X', 'O'],
    [None, 'X', 'O'],
    [None, None, 'O']
]


assert determine_winner(board_1) == 'X'
assert determine_winner(board_2) == 'O'
assert determine_winner(board_3) == 'Draw'
assert determine_winner(board_4) == 'X'
assert determine_winner(board_5) == 'O'
assert determine_winner(board_6) == 'X'
assert determine_winner(board_7) == 'X'
assert determine_winner(board_8) == 'X'
assert determine_winner(board_9) == 'O'

"✅ All OK! +0.75 points"
Contents