pulsus_q1.py

# -*- encoding: utf-8 -*-
import math
import sys

try:
    import pytest
except ImportError:
    if len(sys.argv) < 1 or sys.argv[1] != '-f':
        print 'pip2.7 install --user pytest'
        print 'Ou eu vou ficar sem meus testes :^('
        print 'Para forçar: python2.7 '+sys.argv[0]+' -f'
        sys.exit(1)


def sum_side(lst):
    '''
    Pega a maior soma consecutiva possível da lista e a sua posição.

    Parâmetros:
    lst - numeric list - lista do ramo da árvore sendo combinado

    Retorno: tuple (numeric, int) - sendo offset a posição relativa da maior
             soma
    '''
    sum_total, sum_parcial = None, 0
    i, offset = 0, 0
    for elem in lst:
        sum_parcial += elem
        if sum_total is None or sum_parcial > sum_total:
            sum_total = sum_parcial
            offset = i
        # i é a distância do início da lista à solução atual
        i += 1
    return (sum_total, offset)


def result(start, end, value):
    """
    Transforma os valores de resultado das funções em um dicionário.

    Parâmetros:
    start - int
    end   - int
    value - numeric

    Retorno: dict - dicionário com keys "pos" e "value"
    """
    return {'pos': (start, end), 'value': value}


def combine(left_side, right_side, mid):
    """
    Realiza a combinação de ramos da árvore de divisão.

    Parâmetros:
    left_side   - numeric list - lado esquerdo da lista (ramo esq. da árvore)
    right_side  - numeric list - lado direito
    start - int - offset do começo
    mid   - int - média dos offsets de começo e fim, _não é o meio da lista_
    end   - int - offset de fim

    Retorno: result(...) - dicionário criado por result()
    """
    # O inverso de left_side é usado porque: offset(-4 1 2) != offset(2 1 -4)
    # no caso, offset(-4 1 2) = 0, soma=0+x (dependendo do ramo direito),
    # enquanto offset(2 1 -4) = 2, soma=3.
    sum_left, offset_left = sum_side(reversed(left_side))
    sum_right, offset_right = sum_side(right_side)

    # Cálculo dos offsets dos ramos e soma total
    total = sum_left + sum_right
    index_left = mid - offset_left        # meio - distância ao meio
    index_right = mid + offset_right + 1  # meio + 1 + distância do meio

    return result(index_left, index_right, total)


def median(n):
    """
    Calcula o arrendondamento pra baixo da média _inteira_ de n.

    Parâmetros:
    n - int - número que será realizada a média

    Retorno:	int
    """
    return int(math.floor(float(n)/float(2)))


def divide(lst, start, end):
    """
    Divide uma lista ao meio em log(len(lst)) etapas recursivas, formando
    n*log(n) níveis	de nodos e chegando a uma lista de tamanho 1.
    A cada chamada, divide a lista ao meio e executa a função combine, que
    junta os resultados.

    Parâmetros:
    lst   - numeric list - lista que será dividida
    start - int      - offset do começo da lista
    end   - int      - offset do final da lista

    Retorno: result(...) - dicionário criado por result()
    """
    if len(lst) == 1:
        return result(start, end, lst[0])
    else:
        mid_index = median(start + end)
        mid_lst = median(len(lst))  # meio da lista, não dos offsets
        left_side, right_side = lst[:mid_lst], lst[mid_lst:]

        # são gerados 2 ramos: esquerda e direita, e a combinação do ramo
        # atual
        left_brench = divide(left_side, start, mid_index)
        right_brench = divide(right_side, mid_index, end)
        joined_brench = combine(left_side, right_side, mid_index-len(lst) % 2)
        # len(lst)%2 porque em caso de nodos impares, queremos sempre o maior
        # número de nodos na esquerda
        # (_) (_) | (_)    ----/---->  (_) | (_) (_)
        # assim, o cálculo de offsets não precisa variar +-1 para cada caso

        # nos interessa apenas o maior ramo, pois queremos maximizar os
        # resultados
        max_value = max(left_brench['value'],
                        right_brench['value'],
                        joined_brench['value'])

        for brench in [left_brench, right_brench, joined_brench]:
            if brench['value'] == max_value:
                max_brench = brench
        return max_brench


def max_sum(lst):
    """
    Wrapper para a função divide(), setando automaticamente os índices de
    início e fim da lista.

    Parâmetros:
    lst - numeric list - lista em que a soma max consecutiva sera calculada

    Retorno: divide(...)

    Exemplos:
    max_sum([2, -4, 6, 8, -10, 100, -6, 5])
    max_sum([2, 4, 6, 8, 10, 100, 6])
    """
    return divide(lst, 0, len(lst)-1)['pos']


# Alguns testes...
def test_sum():
    assert max_sum([2, -4, 6, 8, -10, 100, -6, 5]) == (2, 5)
    assert max_sum([2, 4, 6, 8, 10, 100, 6]) == (0, 6)
    assert max_sum([2, 4, 6, 8, 10, 100, 6, 7]) == (0, 7)
    assert max_sum([-2, 4, 6, 8, 10, 100, 6, 7]) == (1, 7)
    assert max_sum([-2, 4, 6, 8, 10, -100, -6, 7]) == (1, 4)
    assert max_sum([-2, 4, 6, 8, 10, -100, -6, 7]) != (11, 4)


def test_sum_typeerror():
    with pytest.raises(Exception):
        max_sum(["dijkstra", "turing"])


def test_sum_typeerror2():
    with pytest.raises(Exception):
        max_sum("tiaraju")


def test_divide_error():
    with pytest.raises(Exception):
        divide(131, 1, 1)
        divide(["tesla"], 1, 1)


def test_median_type():
    assert type(median(12)) is int


def test_divide_error():
    with pytest.raises(Exception):
        median("agulha")


def test_divide_error():
    with pytest.raises(Exception):
        median("agulha")


def test_sum_side_typeerror():
    with pytest.raises(Exception):
        sum_side("aqui tem que dar erro no sistema de inferencia de tipos")


def test_sum_side():
    assert sum_side([0, 1]) == (1, 1)


if __name__ == '__main__':
    if len(sys.argv) > 1:
        index = 1
        if sys.argv[1] == '-f':
            index += 1
        lst = [float(_) for _ in sys.argv[index:]]
        print max_sum(lst)
    else:
        print 'Rodar testes: python2.7 -m pytest '+sys.argv[0]
        print 'Ou rodar script: '+sys.argv[0]+' 2 -4 6 8 -10 100 -6 5 <..>'