gistfile1.py

def subset(s):
    result = []
    length = 1 << len(s)
    for i in range(length):
        j = i
        index = 0
        tmp = []
        while j:
            if j & 1:
                tmp.append(s[index])
            j >>= 1
            index += 1
        result.append(tmp)
    return result


def permutaions(s):
    assert len(s) > 0
    if len(s) == 1:
        yield s
    else:
        for ps in permutaions(s[1:]):
            for i in range(len(s)):
                yield ''.join((ps[0:i], s[0], ps[i:]))


def par(left, right, current):
    assert left >= 0 and right >= 0
    if left == 0 and right == 0:
        yield ''.join(current + [')'] * right)
    if left > 0:
        for i in par(left - 1, right, current + ['(']):
            yield i
    if right > left:
        for i in par(left, right - 1, current + [')']):
            yield i


def print_par(n):
    print tuple(par(n, n, []))


def merge_sort(l):
    if len(l) <= 1:
        return l
    divide = len(l) / 2
    l1 = merge_sort(l[:divide])
    l2 = merge_sort(l[divide:])

    final = []
    while l1 and l2:
        final.append(l1.pop(0) if l1[0] <= l2[0] else l2.pop(0))
    return final + l1 + l2


def pow(base, exp):
    assert exp == int(exp)
    neg_flag = False
    result = 1
    if exp == 0:
        return result
    if exp < 0:
        exp *= -1
        neg_flag = True
    while exp:
        if exp & 1:
            result *= base
        exp >>= 1
        base *= base
    if neg_flag:
        result = 1.0 / result
    return result


def find_ijk(a):
    """
    Given a array of integers, find 3 indexes i,j,k such that,
    i<j<k and a[i] < a[j] < a[k].
    Best possible is a O(n) algorithm.
    """
    length = len(a)
    left_min = [0] * length
    right_max = [0] * length

    for i, v in enumerate(a):
        if i == 0 or v < a[left_min[i - 1]]:
            left_min[i] = i
        else:
            left_min[i] = left_min[i - 1]

    for i, v in reversed(list(enumerate(a))):
        if i == length - 1 or v > a[right_max[i + 1]]:
            right_max[i] = i
        else:
            right_max[i] = right_max[i + 1]

    for i, v in enumerate(a):
        if left_min[i] < i and i < right_max[i]:
            print "index: %d, %d, %d, value: %d, %d, %d" % (
                left_min[i], i, right_max[i],
                a[left_min[i]], a[i], a[right_max[i]]
            )


def find_point(intervals):
    """
    giving lots of intervals [ai, bi],
    find a point intersect with the most number of intervals
    """
    START = 1
    END = 2

    max_num = intervals[0][1]
    for i in intervals:
        assert i[0] >= 0 and i[1] >= 0
        if i[1] > max_num:
            max_num = i[i]

    num_line = [0] * (max_num + 1)
    for i in intervals:
        num_line[i[0]] = START
        num_line[i[1]] = END

    counter = 0
    max_counter = 0
    max_index = []
    for i, v in enumerate(num_line):
        if v == START:
            counter += 1
            if counter > max_counter:
                max_counter = counter
                max_index = [i]
        elif v == END:
            counter -= 1
        else:
            max_index.append(i)

    print max_counter, max_index


def find_longest(s):
    """
    You are going to take some numbers as an input from a file.
    You need to witer a program to find longest increasing sequence.
    You should process it as soon as you are taking an input.
    After finishing the last input immediately you should be able to
    tell the sequence.
    Input: 1 5 3 4 6 4 Output: 3 4 6
    """
    longest = []
    substr = []
    for i in s:
        if len(substr) == 0 or i > substr[-1]:
            substr.append(i)
        else:
            if len(longest) < len(substr):
                longest = substr
            substr = [i]
    print longest


def roman_convert(s):
    convert_table = {'I': 1, 'V': 5, 'X': 10}
    assert s[-1] in convert_table
    result = convert_table[s[-1]]
    look_forward = result
    for i in reversed(range(len(s) - 1)):
        assert s[i] in convert_table
        num = convert_table[s[i]]
        if num < look_forward:
            result -= num
        else:
            result += num
        look_forward = num
    return result


def square_root(n):
    """Use binary search to fing the square root of a number"""
    assert n >= 0

    if n == 0:
        return 0

    low = 0
    high = n if n > 1 else 1
    try_count = 500

    while high >= low and try_count > 0:
        middle = (low + high) / 2.0
        try_count -= 1
        if middle * middle == n:
            return int(middle) if int(middle) == middle else middle
        elif middle * middle > n:
            high = middle
        else:
            low = middle

    return middle


def flat_list(l):
    assert isinstance(l, list) or isinstance(l, tuple)
    for i in l:
        if isinstance(i, list):
            for j in flat_list(i):
                yield j
        elif isinstance(i, tuple):
            for j in flat_list(list(i)):
                yield j
        else:
            yield i


if __name__ == '__main__':
    #print subset([1, 2, 3, 4])
    #print tuple(permutaions('abcd'))
    #print_par(3)
    #print merge_sort([1, 3, 7, 5, 4, 6, 2])
    #print pow(2, -10)
    #find_ijk((4, 7, 5, 1, 3, 8, 9, 6, 2))
    #find_point(((1, 14), (3, 6), (5, 12), (7, 13), (9, 13)))
    #find_longest((1, 5, 3, 4, 6, 8, 4, 7, 9, 11, 13, 4, 2))
    #print map(roman_convert, ['I', 'II', 'III', 'IV', 'VI', 'VIII', 'IX', 'XXIV', 'XXVIII', 'XXIX'])
    #print map(square_root, [0, 1, 0.25, 0.8, 2, 4, 16, 81, 100, 999])
    print tuple(flat_list((1, (2, 3, ), (4, (5, 6, ), 7, ), ((((8, ), ), ), ), )))