Start 2017b

Tel-Aviv University
School of Computer Science
Introduction to Computer Science using Python
0368.1105
Fall Semester 2017-8



News

טסטים לתרגיל 6

מעלה טסטים לתרגיל 6.

מידע על הטסטים: לינק
סקריפט להרצת הטסטים: לינק

בהצלחה במבחנים :)

from itertools import combinations
 
import math
 
import pytest
 
from hw6_insert_id import choose_sets_gen, choose_sets_gen_specific, is_rotated_1, is_rotated_2, weighted_length, \
    optimal, corpus, lz_Qa, lz_Qb, lz_Qc, test, upside_down, segment, dilate, edges, decode
from matrix import *
 
def test_choose_sets_gen():
    for i in range(10):
        for k in range(5):
            lst = list(range(i))
            expected_list = sorted([sorted(l) for l in combinations(lst, k)])
            actual_list = sorted([sorted(l) for l in choose_sets_gen(lst, k)])
            assert actual_list == expected_list
 
    with pytest.raises(StopIteration):
        assert next(choose_sets_gen(list(range(5)), 10))
    assert sorted(next(choose_sets_gen(list(range(5)), 5))) == list(range(5))
 
def test_choose_sets_gen_specific():
    for i in range(10):
        for k in range(5):
            for j in range(10):
                lst = list(range(i))
                expected_list = sorted([sorted(l) for l in combinations(lst, k) if j in l])
                actual_list = sorted([sorted(l) for l in choose_sets_gen_specific(lst, k, j)])
                assert actual_list == expected_list
 
    with pytest.raises(StopIteration):
        assert next(choose_sets_gen_specific(list(range(5)), 10, 0))
 
    with pytest.raises(StopIteration):
        assert next(choose_sets_gen_specific(list(range(5)), 10, 100))
 
    assert sorted(next(choose_sets_gen_specific(list(range(5)), 5, 0))) == list(range(5))
 
def test_is_rotated_1():
    text = "asdfghjkl;"
    for i in range(len(text)):
        s = text[i:] + text[:i]
        assert is_rotated_1(text, s)
 
    assert not is_rotated_1("asdfghjkl", "sdfghjkl")
    assert not is_rotated_1("asdfghjkl", "asdfghjk")
    assert not is_rotated_1("asdfghjkl", "asdfhjkl")
    assert not is_rotated_1("1234567890", "0988777654321")
 
def test_is_rotated_2():
    text = "asdfghjkl;"
    for i in range(len(text)):
        s = text[i:] + text[:i]
        assert is_rotated_2(text, s)
 
    assert not is_rotated_2("asdfghjkl", "sdfghjkl")
    assert not is_rotated_2("asdfghjkl", "asdfghjk")
    assert not is_rotated_2("asdfghjkl", "asdfhjkl")
    assert not is_rotated_2("1234567890", "0988777654321")
 
def test_weighted_length():
    assert weighted_length(["0", "11", "10"], [5, 1, 3]) == 13
 
def test_optimal():
    assert optimal(["0", "11", "10"], [5, 1, 3])
    assert optimal(["1", "00", "01"], [5, 1, 3])
    assert not optimal(["00", "01", "0"], [5, 1, 3])
 
def test_corpus():
    def char_count(text):
        d = {}
        for ch in text:
            if ch in d:
                d[ch] += 1
            else:
                d[ch] = 1
        return d
 
    w = [s[1] for s in sorted(char_count(corpus()).items())]
    c1 = ["0", "100", "101", "11"]
    c2 = ["00", "01", "10", "11"]
    assert weighted_length(c1, w) == weighted_length(c2, w)
 
def test_lz_Q():
    def inter_to_bin(lst, w=2 ** 12 - 1, max_length=2 ** 5 - 1):
        """ converts intermediate format compressed list
            to a string of bits"""
        offset_width = math.ceil(math.log(w, 2))
        match_width = math.ceil(math.log(max_length, 2))
        # print(offset_width,match_width)   # for debugging
        result = []
        for elem in lst:
            if type(elem) == str:
                result.append("0")
                result.append((bin(ord(elem))[2:]).zfill(7))
            elif type(elem) == list:
                result.append("1")
                m, k = elem
                result.append((bin(m)[2:]).zfill(offset_width))
                result.append((bin(k)[2:]).zfill(match_width))
 
        return "".join(ch for ch in result)
 
    def get_new_code(new_k):
        def maxmatch(T, p, w=2 ** 12 - 1, max_length=2 ** 5 - 1):
            """ finds a maximum match of length k<=2**5-1 in a
            w long window, T[p:p+k] with T[p-m:p-m+k].
            Returns m (offset) and k (match length) """
            assert isinstance(T, str)
            n = len(T)
            maxmatch = 0
            offset = 0
            for m in range(1, min(p + 1, w)):
                k = 0
                while k < min(n - p, max_length) and T[p - m + k] == T[p + k]:
                    k += 1
                    # at this point, T[p-m:p-m+k]==T[p:p+k]
                if maxmatch < k:
                    maxmatch = k
                    offset = m
            return offset, maxmatch
 
        def LZW_compress2(text, w=2 ** 12 - 1, max_length=2 ** 5 - 1):
            """LZW compression of an ascii text. Produces
               a list comprising of either ascii characters
               or pairs [m,k] where m is an offset and
               k>3 is a match (both are non negative integers) """
            result = []
            n = len(text)
            p = 0
            while p < n:
                m, k = maxmatch(text, p, w, max_length)
                if k < new_k:  # modified from k<2
                    result.append(text[p])  # a single char
                    p += 1  # even if k was 2 (why?)
                else:
                    result.append([m, k])  # two or more chars in match
                    p += k
            return result  # produces a list composed of chars and pairs
 
        return LZW_compress2
 
    funcs = [lz_Qa, lz_Qb, lz_Qc]
    original = get_new_code(3)
    improved = get_new_code(4)
    for func in funcs:
        s, o, i = func()
        assert len(inter_to_bin(original(s))) == o
        assert len(inter_to_bin(improved(s))) == i
 
def test_upside_down():
    matrix = Matrix(1, 1)
    assert upside_down(matrix) == matrix
 
    matrix = Matrix(1, 1)
    matrix.rows = [
        [1, 2],
        [3, 4]
    ]
    assert upside_down(matrix).rows == [[3, 4], [1, 2]]
 
def test_segment():
    black_matrix = Matrix(10, 10)
    white_matrix = Matrix(10, 10, val=255)
 
    matrix = Matrix(10, 10, val=100)
    assert segment(matrix, 50) == white_matrix
    assert segment(matrix, 100) == white_matrix
    assert segment(matrix, 150) == black_matrix
 
def test_edges():
    m1 = Matrix(4, 4, 0)
    m1[0, 0] = 20
    m1[1, 0] = 60
    m2 = segment(m1, 10)
    assert m2.rows == [[255, 0, 0, 0], [255, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0]]
    m3 = dilate(m2, 1)
    assert m3.rows == [[255, 0, 0, 0], [255, 255, 0, 0], [0, 255, 0, 0], [0, 0, 0, 0]]
    m4 = m3 - m2
    assert m4.rows == [[0, 0, 0, 0], [0, 255, 0, 0], [0, 255, 0, 0], [0, 0, 0, 0]]
 
    assert edges(m1, 1, 10) == m4
 
def test_decode():
    assert decode("".join(["1" * 3, "1" * 3, "0" * 3]), 3) == "110"
    assert decode("".join(["1" * 3, "1" * 3, "100"]), 3) == "110"
    assert decode("".join(["1" * 3, "101", "0" * 3]), 3) == "110"
    assert decode("".join(["110", "1" * 3, "0" * 3]), 3) == "110"
    assert decode("".join(["110", "101", "100"]), 3) == "110"
    assert decode("".join(["1100", "1101", "0100"]), 4) is None
 
def test_tester():
    test()

(17 Jan 2018 19:53)

הרצאה מספר 21-מצגת

היי, להרצאה מספר 21 מצורפות 2 מצגות, אך המצגת השנייה מובילה ללינק שבור.
האם תוכלו לצרף את המצגת?

תודה רבה!


(16 Jan 2018 16:59)

תקציר תרגול 12

היי, תוכלו לפרסם את תרגול 12?

תודה רבה!


(12 Jan 2018 17:51)

טסטים לתרגיל 5

מעלה טסטים לתרגיל 5.

סקריפט להרצת הטסטים: לינק
הסבר על הטסטים ואיך מריצים ידנית: לינק

בחלק מהטסטים יש בדיקת תקינות קלט למרות שלא נדרש בשאלה אז אם אתם מקבלים את שגיאה שכתוב בה Did not raise… אז אתם יכולים לרוב למחוק את השורה הספציפית בטסט.

import pytest
 
from hw5_<insert_id> import Matrix, SparseMatrix, mat2a, mat2b, mat2c, Func, Binary_search_tree, hash_sequence, \
    intersects, test
 
def _get_matrix(n, m):
    matrix = Matrix(n, m)
 
    for i, row in enumerate(matrix.rows):
        for j in range(len(row)):
            row[j] = i * 10 + j
 
    return matrix
 
def _to_sparse_matrix(matrix):
    n, m = matrix.dim()
    sparse_matrix = SparseMatrix(n, m)
    for i in range(n):
        for j in range(m):
            if matrix[i, j] != 0:
                sparse_matrix.elements[i, j] = matrix[i, j]
 
    return sparse_matrix
 
def test_minor():
    matrix = _get_matrix(1, 1)
    assert matrix.minor(0, 0).rows == []
 
    for i in range(2):
        for j in range(2):
            matrix = _get_matrix(2, 2)
            assert matrix.minor(i, j).rows == [[(1 - i) * 10 + (1 - j)]]
 
    matrix = _get_matrix(3, 4)
    assert matrix.minor(1, 1).rows == [
        [0, 2, 3],
        [20, 22, 23]
    ]
 
def test_det():
    matrix = _get_matrix(1, 1)
    assert matrix.det() == 0
 
    matrix.rows = [
        [0, 2, 2],
        [2, 0, 2],
        [2, 2, 0]
    ]
    for i in range(3):
        assert matrix.det(i) == 16
 
    matrix.rows = [
        [1, 6, 0, 4],
        [1, 1, 7, 1],
        [3, 2, 1, 1],
        [0, 7, 0, 1]
    ]
 
    assert matrix.det() == -411
 
    with pytest.raises(AssertionError):
        _get_matrix(2, 3).det()
 
def test_sparse_matrix1():
    for i in range(1, 12):
        for j in range(i, 12):
            assert SparseMatrix(i, j).dim() == Matrix(i, j).dim()
            assert SparseMatrix(i, j).__repr__() == Matrix(i, j).__repr__()
            assert SparseMatrix(i, j) == _to_sparse_matrix(Matrix(i, j))
 
def test_sparse_matrix2():
    matrix = Matrix(4, 4)
    matrix.rows = [
        [1, 6, 0, 4],
        [1, 1, 7, 1],
        [3, 2, 1, 1],
        [0, 7, 0, 1]
    ]
    sparse_matrix = _to_sparse_matrix(matrix)
    assert sparse_matrix.__repr__() == matrix.__repr__()
    assert sparse_matrix == _to_sparse_matrix(matrix)
    assert sparse_matrix[1, 2] == 7
    with pytest.raises(AssertionError):
        sparse_matrix[5, 5]
 
    sparse_matrix[1, 1] = 2
    assert sparse_matrix[1, 1] == 2
    sparse_matrix[1, 1] = 0
    assert (1, 1) not in sparse_matrix.elements
    sparse_matrix[1, 1] = 1
    assert sparse_matrix[1, 1] == 1
 
def test_sparse_matrix3():
    with pytest.raises(AssertionError):
        SparseMatrix(1, 1) + SparseMatrix(1, 2)
    with pytest.raises(AssertionError):
        SparseMatrix(1, 1) + 6
 
    matrix1 = Matrix(1, 1)
    matrix1.rows = [
        [1, 10],
        [100, 1000]
    ]
    matrix2 = Matrix(1, 1)
    matrix2.rows = [
        [2, 20],
        [200, 2000]
    ]
    matrix3 = Matrix(1, 1)
    matrix3.rows = [
        [3, 30],
        [300, 3000]
    ]
 
    sparse_matrix1 = _to_sparse_matrix(matrix1)
 
    assert sparse_matrix1 + _to_sparse_matrix(matrix2) == _to_sparse_matrix(matrix1 + matrix2)
    assert sparse_matrix1 + (-sparse_matrix1) == _to_sparse_matrix(matrix1 + (-matrix1))
    assert sparse_matrix1 - sparse_matrix1 == _to_sparse_matrix(matrix1 - matrix1)
 
    for i in range(10):
        assert sparse_matrix1 * i == _to_sparse_matrix(matrix1 * i)
        assert i * sparse_matrix1 == _to_sparse_matrix(i * matrix1)
 
    assert sparse_matrix1 == _to_sparse_matrix(matrix1)
 
def test_sparse_matrix4():
    for i in range(2):
        for j in range(2):
            matrix = _get_matrix(2, 2) + Matrix(2, 2, 1)
            sparse_matrix = _to_sparse_matrix(matrix)
 
            assert sparse_matrix.minor(i, j).__repr__() == matrix.minor(i, j).__repr__()
 
    matrix = _get_matrix(3, 4)
    sparse_matrix = _to_sparse_matrix(matrix)
    assert sparse_matrix.minor(1, 1).__repr__() == matrix.minor(1, 1).__repr__()
 
def test_sparse_matrix5():
    matrix = _get_matrix(1, 1)
    assert _to_sparse_matrix(matrix).det() == 0
 
    matrix.rows = [
        [0, 2, 2],
        [2, 0, 2],
        [2, 2, 0]
    ]
    for i in range(3):
        assert _to_sparse_matrix(matrix).det(i) == 16
 
    matrix.rows = [
        [1, 6, 0, 4],
        [1, 1, 7, 1],
        [3, 2, 1, 1],
        [0, 7, 0, 1]
    ]
 
    assert _to_sparse_matrix(matrix).det() == -411
 
    with pytest.raises(AssertionError):
        _to_sparse_matrix(_get_matrix(2, 3)).det()
 
def test_mat_hash():
    def hash1(matrix):
        sorted_keys = sorted(matrix.elements.keys())
 
        keys_str = ",".join(str(i) + "," + str(j) for (i, j) in sorted_keys)
        vals_str = ",".join(str(matrix.elements[(i, j)]) for (i, j) in
                            sorted_keys)
        print(keys_str + "," + vals_str)
        return hash(keys_str + "," + vals_str)
 
    def hash2(matrix):
        sorted_keys = sorted(matrix.elements.keys())
        vals_str = ",".join(str(matrix.elements[(i, j)])
                            for (i, j) in
                            sorted_keys)
        return hash(vals_str)
 
    def hash3(matrix):
        keys_sum = sum(i + j for (i, j) in matrix.elements.keys())
        vals_sum = sum(matrix.elements[(i, j)] for (i, j) in
                       matrix.elements.keys())
        return hash(keys_sum + vals_sum)
 
    mat1 = SparseMatrix(3, 3)
    mat1[0, 0] = 1
    mat1[1, 2] = 6
    assert hash2(mat1) == hash2(mat2b())
    assert hash3(mat1) == hash3(mat2c())
 
def test_get_row():
    matrix = _to_sparse_matrix(_get_matrix(5, 5))
 
    assert list(matrix.gen_row1(0)) == list(range(1, 5))
    assert list(matrix.gen_row2(0)) == list(range(1, 5))
 
    assert list(matrix.gen_row1(1)) == list(range(10, 15))
    assert list(matrix.gen_row2(1)) == list(range(10, 15))
 
    matrix = SparseMatrix(5, 7)
    assert list(matrix.gen_row1(2)) == []
    assert list(matrix.gen_row2(2)) == []
 
def test_func_call():
    f1 = Func(lambda x: 1 / x, lambda x: x != 0)
    assert f1(3) == 1 / 3
    assert f1(0) is None
 
    f2 = Func(lambda x: x + 3, lambda x: True)
    assert f2(1) == 4
    assert f2(0) == 3
 
    f3 = Func(lambda x: 1 / x, lambda x: True)
    with pytest.raises(ZeroDivisionError):
        f3(0)
 
def test_func_compose():
    f1 = Func(lambda x: 1 / x, lambda x: x != 0)
    f2 = Func(lambda x: x + 3, lambda x: True)
 
    f3 = f1.compose(f2)
    assert f3(1) == 0.25
    assert f3(-3) is None
 
    f4 = f2.compose(f1)
    assert f4(2) == 3.5
 
    f5 = f1.compose(f1)
    assert f5(3) == 3
 
def test_func_exp():
    f2 = Func(lambda x: x + 3, lambda x: True)
    f3 = f2.exp(4)
    assert f3(0) == 12
 
    f4 = Func(lambda x: x + 3, lambda x: x != 0).exp(10)
    assert f4(-15) is None
 
def test_func_exp_rec():
    f2 = Func(lambda x: x + 3, lambda x: True)
    f3 = f2.exp_rec(4)
    assert f3(0) == 12
 
    f4 = Func(lambda x: x + 3, lambda x: x != 0).exp_rec(10)
    assert f4(-15) is None
 
def test_store_heights():
    bin_tree = Binary_search_tree()
    bin_tree.insert(2, "a")
    bin_tree.insert(4, "b")
    bin_tree.insert(2, "c")
    bin_tree.insert(3, "d")
    bin_tree.insert(1, "e")
    bin_tree.store_heights()
 
    assert bin_tree.root.height == 2
    assert bin_tree.root.left.height == 0
    assert bin_tree.root.right.height == 1
    assert bin_tree.root.right.left.height == 0
 
    bin_tree = Binary_search_tree()
    bin_tree.insert(3, 3)
    bin_tree.store_heights()
    assert bin_tree.root.height == 0
 
def test_height_diff():
    bin_tree = Binary_search_tree()
    bin_tree.insert(2, "a")
    bin_tree.insert(4, "b")
    bin_tree.insert(2, "c")
    bin_tree.insert(3, "d")
    bin_tree.insert(1, "e")
    bin_tree.insert(0, "f")
    bin_tree.insert(5, "g")
    bin_tree.insert(7, "h")
    bin_tree.insert(6, "i")
    assert bin_tree.height_diff() == 2
 
    bin_tree.insert(4.5, "j")
    bin_tree.insert(3.5, "k")
    bin_tree.insert(-1, "l")
    bin_tree.insert(1.5, "m")
    assert bin_tree.height_diff() == 1
 
    bin_tree = Binary_search_tree()
    bin_tree.insert(1, 1)
    assert bin_tree.height_diff() == 0
    bin_tree.insert(2, 1)
    assert bin_tree.height_diff() == 0
    bin_tree.insert(3, 1)
    assert bin_tree.height_diff() == 0
    bin_tree.insert(0, 1)
    assert bin_tree.height_diff() == 1
    bin_tree.insert(0.5, 1)
    assert bin_tree.height_diff() == 0
 
    bin_tree = Binary_search_tree()
    for i in range(5):
        bin_tree.insert(i, 1)
    bin_tree.insert(-1, 1)
    assert bin_tree.height_diff() == 3
 
def test_hash_sequence():
    assert hash_sequence("byebyeboy", 3) == {'yeb': [1, 4], 'boy': [6], 'bye': [0, 3], 'ebo': [5], 'eby': [2]}
    assert hash_sequence("aaaaa", 5) == {"aaaaa": [0]}
    assert hash_sequence("aaaaa", 1) == {"a": list(range(5))}
    assert hash_sequence("ababababa", 3) == {"aba": list(range(0, 7, 2)), "bab": list(range(1, 7, 2))}
    assert hash_sequence("", 3) == {}
    assert hash_sequence("aa", 3) == {}
 
def test_intersects():
    assert intersects("byebyebaboonboy", "babyboy", 4) is None
    assert intersects("byebyebaboonboy", "babyboy", 3) in ["bab", "boy"]
 
def test_tester():
    test()

(03 Jan 2018 19:21)

קוד להרצת הטסטים

הוראות:
1. לשמור את הקוד המצורף כקובץ py בתיקייה עם הקוד שלכם מהתרגיל
2. לשמור את קובץ הטסטים המתאים לתרגיל באותה תיקייה בשם test_hwX.py כאשר X זה מספר התרגיל
3. להריץ את הקובץ py מסעיף 1

שימו לב שבהרצה הראשונה הקוד יתקין ספריות פייתון חסרות ותצטרכו להריץ את הסקריפט שוב

import os
import sys
from subprocess import call
 
PACKAGES_TO_INSTALL = [
    "pip",
    "pytest",
    "mock"
]
 
try:
    import pip
    import pytest
    import mock
except ModuleNotFoundError:
    pip_path = os.path.join(sys.exec_prefix, "Scripts", "pip.exe")
    for package in PACKAGES_TO_INSTALL:
        call([pip_path, "install", "-U", package])
 
    print("Packages installed! Please rerun the script.")
    input("Press Enter to exit.")
    exit(0)
 
pytest.main(["--capture=sys"])
input("Press Enter to exit.")

(03 Jan 2018 19:06)

Fermat Primality Testing and Trial Division

Why isn't the number of operations performed by the Fermat Primality Testing exponential as it is in Trial Division?


(28 Dec 2017 09:25)

פתרונות לתרגילים

[div style="direction:rtl;"]]
האם יפורסמו פתרונות מלאים לתרגילים מתישהו?
תודה
[[/div]]


(23 Dec 2017 09:37)

הבדל בין ממואיזציה ופונקצית מעטפת

מה ההבדל בין פונקצית מעטפת לבין ממואיזציה?


(18 Dec 2017 21:44)

טסטים לתרגיל 4

מעלה טסטים לתרגיל 4.
הערות:

  1. הסבר על איך להריץ את הטסטים תוכלו למצוא פה
  2. בטסטים test_rw_stats ו-test_win_mem יש אלמנט רנדומי אז יש סיכוי מאוד נמוך שהם יכשלו מדי פעם
  3. השתמשי בספרייה mock בשביל הטסטים, יכולים להתקין אותה עם הפקודה pip install mock
  4. אם יש שאלות מוזמנים לכתוב פה ואני אנסה לענות כשאוכל:)
import time
 
from mock import mock
 
from hw4_<insert_id> import acc, myProd, compose, profit, profit2, profit3, win, win2, walk, rw_stats,test
 
class MockFunc(object):
    def __init__(self, values):
        self._values = values[::-1]
 
    def __call__(self, *args, **kwargs):
        return self._values.pop()
 
def test_acc():
    assert acc(lambda x, y: x + y, 0, [2, 3, 7]) == sum([2, 3, 7])
    assert acc(lambda x, y: x + y, -12, [2, 3, 7]) == 0
    assert acc(lambda x, y: x + y, 0, []) == 0
    assert acc(lambda x, y: x * y, 1, [2, 3, 7]) == 2 * 3 * 7
    assert acc(lambda x, y: x * y, 1, []) == 1
 
    assert acc(lambda x, y: x + y, 0, range(100)) == sum(range(100))
 
def test_myprod():
    def assert_myprod(lst):
        value = 1
        for i in lst:
            value *= i
 
        assert myProd(lst) == value
 
    assert_myprod(range(1, 100))
    assert_myprod(range(100))
    assert_myprod(range(1, 50, 2))
    assert_myprod(range(-100, 0))
 
    assert myProd([]) == 0
    assert myProd([3, 4, 5]) == 60
    assert myProd([10, 10, 10]) == 1000
    assert myProd([10, -1, -1]) == 10
 
def test_compose():
    assert compose([lambda x: x - 1, lambda x: x * 2, lambda x: x + 1])(5) == 11
    assert compose([])(5) == 5
    assert compose([lambda x: x - 1, lambda x: x + 1])(5) == 5
    assert compose([lambda x: x, lambda x: x])(5) == 5
    assert compose([lambda x: x + 1, lambda x: x * 0])(5) == 1
    assert compose([lambda x: x + 1, lambda x: x * 0, lambda x: x + 1])(5) == 1
    assert compose([lambda x: x + 1, lambda x: x + 1, lambda x: x + 1])(5) == 8
 
def test_profit():
    assert profit([1, 5, 8, 9], 4) == 10
    assert profit([2, 3, 7, 8, 9], 5) == 11
    assert profit([1, 2, 3, 4, 5], 5) == 5
    assert profit([1, 2, 4, 5, 6, 7], 6) == 8
    assert profit([i + 1 for i in range(10)], 10) == 10
    assert profit([2] + [i + 3 for i in range(9)], 10) == 20
    assert profit([1, 3] + [i + 1 for i in range(8)], 10) == 15
 
    assert profit([0, 2], 2) == 2
    assert profit([1], 1) == 1
 
def test_profit2():
    assert profit2([1, 5, 8, 9], 4) == 10
    assert profit2([2, 3, 7, 8, 9], 5) == 11
    assert profit2([1, 2, 3, 4, 5], 5) == 5
    assert profit2([1, 2, 4, 5, 6, 7], 6) == 8
    assert profit2([i + 1 for i in range(100)], 100) == 100
    assert profit2([2] + [i + 3 for i in range(9)], 10) == 20
    assert profit2([1, 3] + [i + 1 for i in range(8)], 10) == 15
 
    assert profit2([0, 2], 2) == 2
    assert profit2([1], 1) == 1
 
def test_profit3():
    assert profit3([1, 5, 8, 9], 4) == 10
    assert profit3([2, 3, 7, 8, 9], 5) == 11
    assert profit3([1, 2, 3, 4, 5], 5) == 5
    assert profit3([1, 2, 4, 5, 6, 7], 6) == 8
    assert profit3([i + 1 for i in range(10)], 10) == 10
    assert profit3([2] + [i + 3 for i in range(9)], 10) == 20
    assert profit3([1, 3] + [i + 1 for i in range(8)], 10) == 15
 
    assert profit3([0, 2], 2) == 2
    assert profit3([1], 1) == 1
 
def test_win():
    assert win(9, [1, 4, 2]) == False
    assert win(5, [3, 1]) == True
    assert win(1, [1]) == True
    assert win(2, [1]) == False
    assert win(2, [1, 2]) == True
    assert win(5, [1, 2, 3]) == True
    assert win(5, [1, 3]) == True
    assert win(7, [1, 4, 2]) == True
 
def test_win2():
    assert win2(9, [1, 4, 2]) == False
    assert win2(5, [3, 1]) == True
    assert win2(1, [1]) == True
    assert win2(2, [1]) == False
    assert win2(2, [1, 2]) == True
    assert win2(5, [1, 2, 3]) == True
    assert win2(5, [1, 3]) == True
    assert win2(7, [1, 4, 2]) == True
 
def test_win_mem():
    a = time.clock()
    win(40, [1, 3, 5])
    b = time.clock()
    t1 = b - a
 
    a = time.clock()
    win2(40, [1, 3, 5])
    b = time.clock()
    t2 = b - a
    assert t2 < t1
 
def test_walk():
    with mock.patch("random.choice", lambda _: 1):
        assert walk(10, 2) == ((10 ** 2 + 10 ** 2) ** 0.5, False)
 
    assert walk(0, 3) == (0, False)
 
    with mock.patch("random.choice", MockFunc([
        1, 0, 0,
        0, 1, 0,
        0, 0, 1
    ])):
        assert walk(3, 3) == (3 ** 0.5, False)
 
    with mock.patch("random.choice", MockFunc([
        1, 0, 1, 0,
        -1, 0, -1, 0,
        0, 0, 1, 0
    ])):
        assert walk(3, 4) == (1, True)
 
    with mock.patch("random.choice", MockFunc([
        1, 0, 1, 0,
        0, 1, 0, 1,
        -1, 0, -1, 0,
        0, -1, 0, -1
    ])):
        assert walk(4, 4) == (0, True)
 
    with mock.patch("random.choice", MockFunc([
        1, 0, 1, 0,
        0, 1, 0, 1,
        -1, 0, -1, 0,
        0, -1, 0, -1,
        1, 1, 1, 1,
    ])):
        assert walk(5, 4) == (2, True)
 
def test_rw_stats():
    run_length, average_dist, average_dist_divided, \
    min_dist, max_dist, origin_frequency = rw_stats(100, 3, 10 ** 3)
 
    assert run_length == 100
    assert 1.5 <= average_dist_divided <= 1.8
    assert 0.2 <= origin_frequency <= 0.3
 
def test_tester():
    test()

(18 Dec 2017 18:53)

טסטים לתרגיל 3

אני אשתף לכל תרגיל (או אנסה לפחות) קובץ טסטים שנועד לבדוק שהקוד בתרגילים עובד כמו שצריך.
הטסטים יהיו כתובים בpytest (למי שלא מכיר ניתן להתקין עם הפקודה pip install -U pytest)
על מנת להריץ את הטסטים צריך להכניס את הת"ז שלכם בשורה הראשונה ולשמור את הקוד בקובץ py בתיקייה שבה נמצא הקוד שלכם ולהריץ את הפקודה:
pytest test_hw3.py
(בהנחה ששמרתם את הקובץ בשם test_hw3.py)

מידע נוסף על התקנת pip:
https://pip.pypa.io/en/stable/installing/
מידע נוסף על pytest:
https://docs.pytest.org/en/latest/usage.html

שימו לב:
א. אני לא חלק מסגל הקורס אז הטסטים לא רשמיים.
ב. כנראה שיש עוד מקרים שלא נבדקים על ידי הטסטים.
ג. יכולים להיות מקרים מיוחדים שבהם הטסטים יכשלו אבל הקוד שלכם יהיה נכון

מוזמנים לשאול כאן שאלות על הקוד ואני אנסה לענות כמה שאוכל:)
הקוד:

import random
 
from hw3_<insert_id> import find_root1, find_root_range, find_root2, generate_sorted_blocks, merge_sorted_blocks, \
    sort_triplets1, sort_triplets2, equal, test, source, inverse
 
def is_equal(a, b, epsilon=10 ** (-8)):
    return abs(a - b) < epsilon
 
def test_find_root1():
    f1 = lambda x: x - 100
    assert find_root1(f1) == 100
 
    f2 = lambda x: x
    assert find_root1(f2) is None
 
    f3 = lambda x: 2 * x - 101
    assert find_root1(f3) is None
 
    f4 = lambda x: x ** 2 - 10000
    assert find_root1(f4) is 100
 
    f5 = lambda x: 2 * x + 1
    assert find_root1(f5) is None
 
def test_find_root_range():
    assert find_root_range(lambda x: x - 10, 1, 12) == 10
    assert find_root_range(lambda x: x - 10, 12, 20) is None
 
    assert find_root_range(lambda x: x - 10, 1, 1000) == 10
    assert find_root_range(lambda x: x - 1, 1, 1) == 1
 
    assert find_root_range(lambda x: x - 1, 1, 1) == 1
    assert find_root_range(lambda x: 2 * x / x, 1, 1) is None
 
def test_find_root2():
    assert find_root2(lambda x: x - 10) == 10
 
    assert find_root2(lambda x: x - 10) == 10
    assert find_root2(lambda x: x - 1) == 1
 
    assert find_root2(lambda x: x - 1) == 1
    assert find_root2(lambda x: 1) is None
    assert find_root2(lambda x: 2 ** 100 - x) is None
    assert find_root2(lambda x: 2 * x / x) is None
 
    assert find_root2(lambda x: x - 2 ** 99) == 2 ** 99
    assert find_root2(lambda x: x - 2 ** 100) == 2 ** 100
    assert find_root2(lambda x: x + 1 - 2 ** 100) == 2 ** 100 - 1
 
    assert find_root2(lambda x: 2 * x - 101) is None
 
    assert find_root2(lambda x: x - 2 ** 103) is None
 
def test_generate_sorted_blocks1():
    assert generate_sorted_blocks(list(range(10)), 3) == [[0, 1, 2], [3, 4, 5], [6, 7, 8], [9]]
    assert generate_sorted_blocks(list(range(10)), 1) == [[i] for i in range(10)]
    assert generate_sorted_blocks(list(range(10)), 10) == [list(range(10))]
 
    assert generate_sorted_blocks(list(range(10, 0, -1)), 3) == [[8, 9, 10], [5, 6, 7], [2, 3, 4], [1]]
    assert generate_sorted_blocks(list(range(10, 0, -1)), 1) == [[i] for i in range(10, 0, -1)]
    assert generate_sorted_blocks(list(range(10, 0, -1)), 10) == [list(range(1, 11))]
 
    lst = [610, 906, 308, 759, 15, 389, 892, 939, 685, 565]
    assert generate_sorted_blocks(lst, 2) == [[610, 906], [308, 759], [15, 389], [892, 939], [565, 685]]
    assert generate_sorted_blocks(lst, 3) == [[308, 610, 906], [15, 389, 759], [685, 892, 939], [565]]
    assert generate_sorted_blocks(lst, 10) == [[15, 308, 389, 565, 610, 685, 759, 892, 906, 939]]
 
def test_merge_sorted_blocks1():
    for k in range(1, 101):
        for n in range(k, 101):
            lst = list(range(n))
            random.shuffle(lst)
            assert merge_sorted_blocks(generate_sorted_blocks(lst, k)) == list(range(n))
 
    block_lst1 = [[610, 906], [308, 759], [15, 389], [892, 939], [565, 685]]
    assert merge_sorted_blocks(block_lst1) == [15, 308, 389, 565, 610, 685, 759, 892, 906, 939]
 
def test_sort_triplets():
    for k in range(2, 25, 5):
        for n in range(1, 100, 11):
            input_list = [(random.randint(0, k - 1), random.randint(0, k - 1), random.randint(0, k - 1)) for _ in
                          range(n)]
            random.shuffle(input_list)
 
            output_list1 = sort_triplets1(input_list, k)
            output_list2 = sort_triplets2(input_list, k)
            assert output_list1 == output_list2 == sorted(input_list)
 
def test_equal():
    result = equal(lambda x: 4 * x, lambda x: x ** 2 + 3)
    assert is_equal(result, 1) or is_equal(result, 3)
 
    result = equal(lambda x: x, lambda x: -x)
    assert is_equal(result, 0)
 
    result = equal(lambda x: x, lambda x: x + 1)
    assert result is None
 
    result = equal(lambda x: 100 - x, lambda x: x)
    assert is_equal(result, 50)
    result = equal(lambda x: -50, lambda x: x)
    assert is_equal(result, -50)
 
def test_source():
    assert is_equal(source(lambda x: x, 5), 5)
    assert is_equal(source(lambda x: x + 3, 5), 2)
    assert is_equal(source(lambda x: 2 * x, 9), 4.5)
    assert is_equal(source(lambda x: x, -100), -100)
    assert is_equal(source(lambda x: 50 - x, 0), 50)
 
def test_inverse():
    assert is_equal(inverse(lambda x: x)(5), 5)
    assert is_equal(inverse(lambda x: x + 3)(5), 2)
    assert is_equal(inverse(lambda x: 2 * x)(9), 4.5)
    assert is_equal(inverse(lambda x: x)(100), 100)
    assert is_equal(inverse(lambda x: 50 - x)(0), 50)
    assert is_equal(inverse(lambda x: 50 - x)(50), 0)
    assert is_equal(inverse(lambda x: 50 - x)(50), 0)
 
def test_tester():
    test()

(02 Dec 2017 21:16)

צירוף בכתב יד

היי,
ראיתי במייל ששלחתם שמותר להוסיף דברים בכתב יד רק לסעיף א בשאלה 1.
לדוגמא בשאלה 3 שצריך לנתח זמן ריצה
אי אפשר לשים פתרון בכתיב ברור שכותב ביד ולסרוק ולצרף לPDF?
אני לא רואה שום דרך לכתוב את זה בוורד שיצא קריא


(01 Dec 2017 12:02)

האם ניתן להשתמש ברקורסיה בתרגיל 3?

היי,
האם ניתן להשתמש ברקורסיה במטלה 3?

תודה,
פלג


(30 Nov 2017 22:44)

סיבוכיות זיכרון של פיבונצי איטרטיבי

The Presentation of lecture 12 in slide 25 says that the memory complixity of iterative fibonacci is o(1)? Why? I thought its o(n).


(30 Nov 2017 19:23)

מתי שעות הקבלה של המתרגלים והמרצים?

מתי שעות הקבלה של המתרגלים והמרצים?


(28 Nov 2017 19:36)

שאלה לגבי מקרי קצה

רציתי לשאול האם העובדה שפונקציית הטסט לא בדקה את כל מקרי הקיצון בשיעורי הבית הראשונים מכוונת, והאם זה יישאר כך.
אם כן, האם ישנם איזשהם קווים מנחים על מנת לוודא כי פגענו בכל מקרה קיצון?
תודה מראש,
עידו


(19 Nov 2017 16:31)

לא מוצא הערות על תרגיל 1

נכנסתי לטבלה עם הציונים בקורס ואני אכן רואה שורה בה בצד ימין יש "הגשת תרגיל בית 1" ואיזשהו ציון אבל אני לא רואה שם סימוני הערות.

תודה.


(18 Nov 2017 23:03)

שאלה 3 סעיף א - הפנייה לנוסחה מהתרגול

אשמח מאוד אם מישהו יוכל להפנות למצגת הרלוונטית כאן באתר.

תודה רבה.


(18 Nov 2017 14:08)

שאלה 3 ז

אם יש לנו שלושה ביטים שצריך לחבר, צריך לחבר בין השניים הראשונים ואז אם התוצאה היא חד-ספרתית צריך להוסיף את הביט השלישי לסכום, ואם היא דו ספרתית אז צריך להוסיף את הביט השלישי לביט הימני בסכום שבהכרח יהיה 0 כך לא תהיה העברת ביט

זה פתרון עם שתי פעולות חיבור אבל הוא משתמש בבדיקה אם ביט הוא 0 או1, כי הוא בודק אם הסכום של שני המספרים הראשונים הוא חד ספרתי או דו ספרתי שזה בעצם לבדוק את הביט השמאלי בסכום. אבל כיוון שאפשר להגדיר פעולת חיבור בין שני ביטים בעזרת תנאים כאלו (תנאים שבודקים אם ביט הוא 0 או 1) והעברות של ביטים בלבד , אפשר לחבר שלושה ביטים בלי פעולות חיבור אם אפשר להשתמש בתנאים כאלה. האם בכל זאת אפשר להשתמש בפתרון שהצעתי, או שנדרשות 3
פעולות חיבור בשביל לחבר שלושה ביטים?
תודה.


(17 Nov 2017 19:04)

Documentation

האם יש צורך לתעד את הקוד על מנת לקבל ניקוד מלא?


(17 Nov 2017 15:16)

HW2 Q5a

Hi,

I'd like to know if the placeholders represent only one line, or can I write more lines?
Thanks.


(12 Nov 2017 07:59)





Forums (see tips on the right ----->)

Do not forget to click "preview" before posting your message!




General Forum


All HW forums



Recent Forum Posts:

{"module":"feed\/FeedModule","params":{"src":"http:\/\/tau-cs1001-py.wikidot.com\/feed\/forum\/cp-2548580.xml","limit":"25","module_body":"++++ %%linked_title%%\n[[span style=\"color: gray; font-size: smaller\"]]By %%custom wikidot:authorName%% on %%date%%[[\/span]]\n%%long%%"}}
Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License