<jupyter_start><jupyter_text>"И помни, что коронный твой  - прямой"*<NAME>., "<NAME>"*Никаких дополнительных билбиотек, чистый питон, учимся программировать простые задачи.Сегодня разрешены brute force решения.<jupyter_code>import sem2_tests<jupyter_output><empty_output><jupyter_text>Problem 0. PEP8 (This is more important than you might think)https://www.kbsoftware.co.uk/docs/_downloads/a9d605adc5dbf1d1338643d6a756e6c7/pep8_cheat.pdf  Problem 1. Fizz Buzz Write a program that outputs the string representation of numbers from 1 to n.But for multiples of three it should output “Fizz” instead of the number and for the multiples of five output “Buzz”. For numbers which are multiples of both three and five output “FizzBuzz”.<jupyter_code>def fizz_buzz(n):
    """
    :type n: int
    :rtype: List[str]
    """
    # ans list
    ans = []

    for num in range(1,n+1):
        
        divisible_by_3 = (num % 3 == 0)
        divisible_by_5 = (num % 5 == 0)

        if divisible_by_3 and divisible_by_5:
            # Divides by both 3 and 5, add FizzBuzz
            ans.append("FizzBuzz")
        elif divisible_by_3:
            # Divides by 3, add Fizz
            ans.append("Fizz")
        elif divisible_by_5:
            # Divides by 5, add Buzz
            ans.append("Buzz")
        else:
            # Not divisible by 3 or 5, add the number
            ans.append(str(num))
    return ans

sem2_tests.test_fizz_buzz(fizz_buzz)
fizz_buzz(15)<jupyter_output><empty_output><jupyter_text>Problem 2. Fibonacci Write a program that asks the user how many Fibonnaci numbers to generate and then generates them. Take this opportunity to think about how you can use functions. Make sure to ask the user to enter the number of numbers in the sequence to generate.(Hint: The Fibonnaci seqence is a sequence of numbers where the next number in the sequence is the sum of the previous two numbers in the sequence. The sequence looks like this: 1, 1, 2, 3, 5, 8, 13, …)<jupyter_code>def fib(num):
    #num = int(input("How many numbers to generate?: "))
    fib = [0] * num
    fib[0] = 1
    fib[1] = 1
    for i in range(2, num):
        fib[i] = fib[i-1] + fib[i-2]
    return fib
print(*fib(10))<jupyter_output>1 1 2 3 5 8 13 21 34 55<jupyter_text>Problem 3. Find All Duplicates in an ArrayGiven an array of integers, 1 ≤ a[i] ≤ n (n = size of array), some elements appear twice and others appear once.Find all the elements that appear twice in this array.Дополнительное условние: выводить елементы нужно в том же порядке, в котором они первый раз встретились в листе<jupyter_code>def find_duplicates(arr):
    ans = []
    for i in range(len(arr)):
        for j in range(i+1, len(arr)):
            if arr[i] == arr[j]:
                ans.append(arr[i])
    return ans

sem2_tests.test_find_duplicates(find_duplicates)
dup_arr = [0, 4, 3, 2, 7, 8, 2, 3, 1, 98, 98]
find_duplicates(dup_arr)
def diff(arr1, arr2): 
    diff = arr1[:]  # make a copy
    ans = []
    for x in arr2:
        if x not in diff:
            ans.append(x)
        else:
            diff.remove(x)
    return ans
diff([1, 2, 3], [1, 2, 3, 3])
def find_duplicates2(arr):
    arr_set = set(arr)
    ans = diff(list(arr_set), arr)
    return ans

sem2_tests.test_find_duplicates(find_duplicates2)
find_duplicates([1, 2, 3, 3])
find_duplicates(dup_arr)<jupyter_output><empty_output><jupyter_text>Problem 4. Word FrequencyWrite a script to calculate the frequency of each word.Your script should output sorted by descending frequency:Дополнительное условние: на вход поступает строка, на выход нужно получить лист из кортежей (слово, частота)<jupyter_code>def count_word_frequency(string):
    s_list = string.split()
    wordfreq = {}
    for word in s_list:
        if word not in wordfreq:
            wordfreq[word] = 0
        wordfreq[word] += 1
    ans = sorted(wordfreq.items(), key=lambda x: x[1], reverse=True) 
    return ans

sem2_tests.test_word_frequency(count_word_frequency)
s = 'game game  of of of thrones'
s_split = s.split()
s_split
d = {}
for word in s_split:
    if word not in d:
        d[word] = 0
    d[word] += 1
d
d.keys()
d.items()
sorted(d.items(), key=lambda x: x[1], reverse=True)<jupyter_output><empty_output><jupyter_text>Problem 5. Valid Palindrome    Given a non-empty string s, you may delete at most one character. Judge whether you can make it a palindrome.<jupyter_code>def is_almost_palindrome(string):
    for i in range(len(string)):
        t = string[:i] + string[i+1:]
        if t == t[::-1]:
            return True
    return string == string[::-1]

sem2_tests.test_valid_palindrome(is_almost_palindrome)<jupyter_output>OK!<jupyter_text>Problem 6. Longest substring without repeating charactersGiven a string, find the length of the longest substring without repeating characters.<jupyter_code>def isUnique(string):
    init_len = len(string)
    set_len = len(set(list(string)))
    if init_len == set_len:
        return True
    else:
        return False
def length_of_longest_substring(string):
    ans = 0
    for i in range(len(string)):
        for j in range(i+1, len(string)):
            if isUnique(string[i:j]):
                ans = max(ans, j - i)
    return ans

sem2_tests.test_longest_substring(length_of_longest_substring)<jupyter_output>OK!
{'fraction_non_alphanumeric': 0.09773156899810964, 'fraction_numerical': 0.024763705103969753, 'mean_word_length': 3.322712418300654, 'pattern_counts': {'":': 0, '<': 28, '<?xml version=': 0, '>': 28, 'https://': 1, 'lorem ipsum': 0, 'www.': 1, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 1, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '7', 'dir': 'jupyter-structured-clean-dedup', 'id': '168888', 'license': 'MIT', 'n_tokens_mistral': 1939, 'n_tokens_neox': 1851, 'n_words': 578, 'path': 'lect08_O_notation_regexp/2021_DPO_6_1_algo_problems_solved.ipynb', 'repo_name': 'weqrwer/Python_DPO_2021_fall', 'size': '5312'}