##### IB111 skupina 10 #####
##### cvičení 07

# kód musí projít nástrojem 'flake8' bez chyb
# používej typovou annotaci, kontroluj 'C:\Python3.7\python.exe -m mypy --strict --disallow-any-expr'


### PASCAL TRIANGLE
# ÚKOL 1
# Napište funkci triangle(n), která vrací seznam n seznamů takových, že první
# obsahuje 1 jedničku, druhý 2 jedničky až poslední n jedniček.

>>> triangle(0)
[]
>>> triangle(1)
[[1]]
>>> triangle(3)
[[1], [1, 1], [1, 1, 1]]
>>> triangle(5)
[[1], [1, 1], [1, 1, 1], [1, 1, 1, 1], [1, 1, 1, 1, 1]]

# TIP
# pro pěknou vizualizaci výsledku použijte následující kód:

def print_pascal(pascal: List[List[int]]) -> None:
    max_number_size = len(str(pascal[-1][len(pascal)//2])) + 2
    for row in pascal:
        line = ""
        for x in row:
            line += ("{0: ^" + str(max_number_size) + "}").format(x)
        print(("{0: ^" + str(max_number_size * len(pascal[-1])) + "}").format(line))


# ÚKOL 2
# Napište funkci pascal_binomial(n), která vrací n řádků Pascalova trojúhelníku. Trojúhelník
# bude reprezentovaný jako seznam řádků, kde každý řádek je seznam hodnot v trojúhelníku.
# Funkce by měla hodnoty napočítávat pomocí kombinačních čísel. Napište si a použijte pomocné
# funkce 'factorial(n: int) -> int' pro výpočet faktoriálu a
# 'binominal_coefficient(n: int, k: int) -> int' pro výpočet kombinačního čísla.

>>> pascal_binomial(0)
[]
>>> pascal_binomial(1)
[[1]]
>>> pascal_binomial(3)
[[1], [1, 1], [1, 2, 1]]
>>> pascal_binomial(5)
[[1], [1, 1], [1, 2, 1], [1, 3, 3, 1], [1, 4, 6, 4, 1]]


# ÚKOL 3
# Napište funkci pascal(n), která vrací n řádků Pascalova trojúhelníku. Trojúhelník bude
# reprezentovaný jako seznam řádků, kde každý řádek je seznam hodnot v trojúhelníku. Funkce
# by měla hodnoty napočítávat jako součet hodnot z předchozího řádku.

>>> pascal(0)
[]
>>> pascal(1)
[[1]]
>>> pascal(3)
[[1], [1, 1], [1, 2, 1]]
>>> pascal(5)
[[1], [1, 1], [1, 2, 1], [1, 3, 3, 1], [1, 4, 6, 4, 1]]



### ŘADÍCÍ ALGORITMY

# ÚKOL 4
# implementujte řadící algoritmus Insert sort. Napište test, který zkotroluje pro dlouhý
# seznam čísel, že váš řadící algoritmus je korektní.

>>> array = [7, 6, 100, 3, 2, 11, -1, 10, 10, 42, 42, 42, 2, 13, 0, -5]
>>> insert_sort(array)
>>> print(array)
[-5, -1, 0, 2, 2, 3, 6, 7, 10, 10, 11, 13, 42, 42, 42, 100]


# ÚKOL 5
# implementujte řadící algoritmus Bubble sort.

>>> array = [7, 6, 100, 3, 2, 11, -1, 10, 10, 42, 42, 42, 2, 13, 0, -5]
>>> bubble_sort(array)
>>> print(array)
[-5, -1, 0, 2, 2, 3, 6, 7, 10, 10, 11, 13, 42, 42, 42, 100]


# ÚKOL 6
# implementujte řadící algoritmus Select sort.

>>> array = [7, 6, 100, 3, 2, 11, -1, 10, 10, 42, 42, 42, 2, 13, 0, -5]
>>> select_sort(array)
>>> print(array)
[-5, -1, 0, 2, 2, 3, 6, 7, 10, 10, 11, 13, 42, 42, 42, 100]
