pass

def replicate(times, num):
    if times <= 0: return []
    return [num] + replicate(times-1, num)

# BaseException >> Exception
def f1(): raise Exception()

# BaseException >> Exception >> ArithmeticError >> ZeroDivisionError
def f2(): return 1 // 0

# BaseException >> Exception >> LookupError >> KeyError
def f3(): return {}[1]

def f0(): pass

# Correct solution
def add(a, b): return a + b

# Incorrect solution
def add1(a, b): return a | b

# Solution that timeouts
def add2(a, b):
    while a: a, b = a-1, b+1
    return b

# Solution that cheats
def add3(a, b):
    class X(object):
        def __eq__(self, other): return True
        def __ne__(self, other): return True
        def __gt__(self, other): return True
        def __lt__(self, other): return True
        def __ge__(self, other): return True
        def __le__(self, other): return True
    return X()
    
#add = add1
#add = add2
#add = add3

#from __future__ import print_function

class AssertException(Exception):
    pass


'''Fix the dreaded Unicode Error Trap'''
_print = print
def print(*args, sep=' ', end='\n'):
    from io import StringIO
    def _escape(s): return s.encode('ascii', 'xmlcharrefreplace').decode('ascii')
    sio = StringIO()
    _print(*args, sep=sep, end=end, file=sio)
    _print(_escape(sio.getvalue()))
    sio.close()


def format_message(message):
    return message.replace("\n", "<:LF:>")


def expect(passed=None, message=None, allow_raise=False):
    if passed: print("\n<PASSED::>Test Passed")
    else:
        message = message or "Value is not what was expected"
        print("\n<FAILED::>{0}".format(message))
        if allow_raise: raise AssertException(message)


'''Fix the blocking asserts to non-blocking'''
def assert_equals(actual, expected, message=None, allow_raise=False):
    equals_msg = "{0} should equal {1}".format(repr(actual), repr(expected))
    if message is None: message = equals_msg
    else: message += ": " + equals_msg
    expect(actual == expected, message, allow_raise)


'''
Fix the blocking asserts to non-blocking
Also change the expected formula from `actual != expected` to `not (actual == expected)`
so that using this assertion can prevent the `==` / `!=` injection hack
'''
def assert_not_equals(actual, expected, message=None, allow_raise=False):
    equals_msg = "{0} should not equal {1}".format(repr(actual), repr(expected))
    if message is None: message = equals_msg
    else: message += ": " + equals_msg
    expect(not (actual == expected), message, allow_raise)


def expect_error(message, function):
    passed = False
    try: function()
    except: passed = True
    expect(passed, message)


'''Additional test functions: pass, fail, and assert_approx_equals'''
def pass_(): expect(True)
def fail(message): expect(False, message)


def assert_approx_equals(actual, expected, margin=1e-9, message=None, allow_raise=False):
    equals_msg = "{0} should be close to {1} with absolute or relative margin of {2}".format(
        repr(actual), repr(expected), repr(margin))
    if message is None: message = equals_msg
    else: message += ": " + equals_msg
    div = max(abs(actual), abs(expected), 1)
    expect(abs((actual - expected) / div) < margin, message, allow_raise)


def display(type, message, label="", mode=""):
    print("\n<{0}:{1}:{2}>{3}".format(type.upper(), mode.upper(), label, format_message(message)))


'''
Modern-Style Describe & It
Usage:
@describe('describe text')
def describe1():
    @it('it text')
    def it1():
        # some test cases...
'''
def _timed_block_factory(opening_text):
    from timeit import default_timer as timer
    from traceback import format_exception
    from sys import exc_info
    
    def _timed_block_decorator(s, before=None, after=None):
        print('<{}::>{}'.format(opening_text, s))
        def wrapper(func):
            if callable(before): before()
            time = timer()
            try: func()
            except:
                fail('Unexpected exception raised')
                tb_str = ''.join(format_exception(*exc_info())).replace('\n', '<:LF:>')
                print('<ERROR::>' + tb_str)
            print('<COMPLETEDIN::>{}'.format(round((timer() - time) * 1000, 2)))
            if callable(after): after()
        return wrapper
    return _timed_block_decorator

describe = _timed_block_factory('DESCRIBE')
it = _timed_block_factory('IT')


'''
Timeout utility
Usage:
with run_with_timeout(func, tuple_of_args, timeout_in_seconds) as run:
    Test.assert_equals(run.get(), expected_value)
Note: Timeout value can be a float.
'''
class run_with_timeout(object):
    def __init__(self, func, inputs, sec):
        from multiprocessing import Process, Queue
        def timeout_wrapper(func, inputs, q):
            q.put(func(*inputs))
        self.sec = sec
        self.q = Queue()
        self.p = Process(target=timeout_wrapper, args=(func, inputs, self.q))
        self.result = None
    def __enter__(self):
        self.p.start()
        return self
    def get(self):
        if self.result is None: self.result = self.q.get(timeout=self.sec)
        return self.result
    def __exit__(self, typ, val, traceback):
        self.q.close()
        self.p.terminate()
        self.p.join()
        if traceback: fail('Exceeded time limit of {:.3f} seconds'.format(self.sec))
        return True


'''Old-style Fixture'''
describe('Old-style Describe')
it('Old-style It')
assert_equals(0, 0)
assert_equals(0, 1)
print('<COMPLETEDIN::>')
it('Old-style It 2')
assert_equals('a', 'a')
assert_equals('a', 'b')
print('<COMPLETEDIN::>')
print('<COMPLETEDIN::>')


'''Sample Fixture #1'''
@describe('Sample Fixture #1')
def sample_describe_1():
    @it('Sample Testcase #1-1')
    def sample_it_1():
        assert_equals(0, 0)
        assert_equals(0, 1)
        assert_not_equals(0, 2)
        pass_()
        fail('This should fail')
    @it('Sample Testcase #1-2')
    def sample_it_2():
        expect_error('ZeroDivisionError', lambda: 0 / 0)
        assert_equals(0, 0 / 0)
        assert_equals(1, 1, 'This is not run due to exception')
    @it('Sample Testcase #1-3')
    def sample_it_3():
        assert_equals('abc', 'abc')
        # source code doesn't support utf-8 chars, but you can at least log and test unicode
        assert_equals('\uac00 \ub098 \ub2e4', '\uac00 \ub098 \ub2e4')
        print('\uac00 \ub098 \ub2e4')
        assert_equals('\uac00 \ub098 \ub2e4', 'a b c')


'''Sample Fixture #2: Featuring Before and After'''
@describe('Sample Fixture #2')
def sample_describe_2():
    a = {0}
    def before():
        a.add(len(a))
    @it('Sample Testcase #2-1', before=before, after=before)
    def sample_it_1():
        assert_equals(a, {0, 1})
    @it('Sample Testcase #2-2')
    def sample_it_2():
        assert_equals(a, {0, 1, 2})


'''Sample Fixture #3: Featuring Timeout'''
@describe('Sample Fixture #3')
def sample_describe_3():
    def wait_count(n):
        for _ in range(n): pass
        return n
    @it('Sample Testcase #3-1')
    def sample_it_1():
        with run_with_timeout(wait_count, (100,), 0.01) as run:
            assert_equals(run.get(), 100)
    @it('Sample Testcase #3-2')
    def sample_it_2():
        with run_with_timeout(wait_count, (10 ** 10,), 0.01) as run:
            assert_equals(run.get(), 10 ** 10)


'''Sample Fixture #4: Featuring assert_approx_equals'''
@describe('Sample Fixture #4')
def sample_describe_4():
    @it('Sample Testcase #4-1')
    def sample_it_1():
        assert_approx_equals(1, 1 + 1e-10, 1e-9)
        assert_approx_equals(1, 1 + 1e-7, 1e-9)
        assert_approx_equals(-1, -1 - 1e-10, 1e-9)
        assert_approx_equals(-1, -1 - 1e-7, 1e-9)
    @it('Sample Testcase #4-2')
    def sample_it_2():
        assert_approx_equals(0, 1e-10, 1e-9)
        assert_approx_equals(0, 1e-7, 1e-9)
        assert_approx_equals(0, -1e-10, 1e-9)
        assert_approx_equals(0, -1e-7, 1e-9)

def fibonacci(n):
    if n <= 1: return 1
    if n > 35: raise RuntimeError('Too large input')
    return fibonacci(n-1) + fibonacci(n-2)