project1.py

########################################################################Tarefa 1############################################################################

def limpa_texto (texto):
    '''
    Função que vai substituir todos os caracteres brancos(\n, \t, \v, \f, \r e os espaços) 
    por espaços únicos entre palavras

    str --> str
    '''
    
    return ' '.join(texto.split())


def corta_texto (texto, largura):
    '''
    Esta função pega num texto limpo e separa em duas partes
    A primeira contém todas as palavras completas até a largura (inteiro positivo) dada
    A segunda contém o restante do texto.

    str x int --> tuple
    '''

    parte1 = ''
    parte2 = ''
    flag = True #vai servir para verificar se a parte 1 já foi preenchida e evitar que se volte a meter mais palavras

    for palavra in texto.split(' '): #separar palavra a palavra
        if (len(parte1) + len(palavra)) <= largura and flag == True:
            parte1 += palavra + ' '
        else:
            flag = False
            parte2 += palavra + ' '
    
    parte1 = parte1.strip() #para retirar espaços no ínicio ou fim da cadeia
    parte2 = parte2.strip()
    
    return (parte1, parte2)


def insere_espacos (texto_limpo, largura):
    '''
    Esta função recebe um texto limpo e um inteiro positivo correspondente a uma largura
    No caso de haver mais de uma palavra, devolve uma cadeia de caracteres com espaços uniformes 
    entre palavras até à largura dada 
    Em caso contrário, insere espaços após a palavra até corresponder à largura de coluna

    str x int --> str
    '''

    texto = []
    n = len(texto_limpo)
    flag = False #vai servir para verificar se já atingimos a largura desejada
    
    if ' ' not in texto_limpo: #caso só haja uma palavra
        while len(texto_limpo) < largura:
            texto_limpo += ' '
    
    else:
        while flag == False:
            for i in range(len(texto_limpo)-1):
                if n == largura:
                    texto += texto_limpo[i]
                    if i == (len(texto_limpo))-2:
                        texto += texto_limpo[i+1]
                else:
                    texto += texto_limpo[i]
                    if texto_limpo[i] == ' ' and texto_limpo[i+1] != ' ': #no caso de haver mais de um espaço entre palavras
                        texto.append(' ') #só insere um se vir um espaço na posição atual e algo diferente à frente
                        n += 1
                    if i == (len(texto_limpo)-2):
                        texto += texto_limpo[i+1]
            
            texto_limpo = ''
            
            for j in texto:
                texto_limpo += j
            
            if len(texto_limpo) < largura:
                texto = []
            else:
                flag = True
    
    return texto_limpo

                        
def justifica_texto (cad, largura):
    '''
    Esta função recebe uma cadeia de caracteres não vazia e um inteiro positivo, correspondentes a um texto e
    uma largura e devolve um tuplo com o texto justificado, ou seja, com espaços, como descrito anteriormente,
    até à largura dada

    str x int --> tuple
    '''

    if type(cad) != str or type(largura) != int or largura <= 0 or len(cad) == 0 :
        raise ValueError('justifica_texto: argumentos invalidos')
    else:
        texto = limpa_texto(cad)
        for palavra in texto.split(' '):
            if len(palavra) > largura:
                raise ValueError('justifica_texto: argumentos invalidos')

        texto2 = corta_texto(texto, largura)
        texto_final = ()
        tuplo = ()
        flag = False #vai servir para verificar quando todas as linhas tiverem justificadas
        contador = 0 #para contar quando cada linha atingir a largura desejada

        while flag == False:
            for el in texto2:
                if len(el) > largura:
                    tuplo = corta_texto(el, largura)
                    texto_final += (tuplo,) 
                elif len(el) == largura:
                    texto_final += (el,)
                else:
                    if len (el) != 0:
                        el = insere_espacos(el, largura)
                        texto_final += (el,)

            i = 0

            while i < len(texto_final):
                if isinstance(texto_final[i], tuple):
                    texto_final = texto_final[:i] + texto_final[i] + texto_final[i+1:] #tirar possíveis tuplos dentro do tuplo obtido
                else:
                    i = i+1

            for el in texto_final:
                if len(el) == largura:
                    contador += 1
                if type(el) == str and contador == len(texto_final):
                    flag = True

            if flag == False:
                texto2 = texto_final
                texto_final = ()
                contador = 0

        texto_final = list(texto_final) #para poder alterar os elementos da última linha e inserir espaços no final

        for i in range(len(texto_final)):
            if i == len(texto_final)-1:
                texto_final[i] = limpa_texto(texto_final[i])
                while len(texto_final[i]) != largura:
                    texto_final[i] = texto_final[i] + ' '

        texto_final = tuple(texto_final)
        
        return texto_final

########################################################################Tarefa 2############################################################################

def calcula_quocientes (circulo, deputados):
    '''
    Esta função recebe um dicionário com os votos de um círculo eleitoral e um inteiro positivo correspondente ao nº de deputados
    Vai devolver um dicionário com os quocientes dos votos segundo o método de Hondt

    dict x int --> dict
    '''

    res = {}

    for partido in circulo:
        i = 1
        while i <= deputados:
            if partido in res:
                res[partido].append(circulo[partido]/i) #adicionar os quocientes a um dicionário
            else:
                res[partido] = [circulo[partido]/i]

            i += 1

    return res

def atribui_mandatos (circulo, deputados):
    '''
    Esta função recebe um dicionário com os votos de um círculo eleitoral e um inteiro positivo correspondente ao nº de deputados
    Devolve uma lista ordenada com o tamanho correspondente ao número de deputados cujos elementos da lista correspondem aos
    partidos que elegeram deputados
    No caso de empate dos quocientes, o mandato é atríbuido ao partido com menos votos totais

    dict x int --> dict
    '''

    res = calcula_quocientes (circulo,deputados)
    lista = []
    i = 1

    while i <= deputados:

        max = 0
        tuplo = ()

        for partido in res:
            if res[partido][0] > max:
                max = res[partido][0]
                partido_verificador = partido #vai guardar o nome do partido para depois comparar os votos
                tuplo = (partido_verificador,max)
            elif res[partido][0] == max:
                if circulo[tuplo[0]] > circulo[partido]: #acede ao dicionário original e compara
                    tuplo = (partido, max)

        lista += [tuplo[0]]
        del res[tuplo[0]][0] #permite comparar sempre o maior dos quocientes que já não foi utilizado
        i += 1

    return lista  

def obtem_partidos (info):
    '''
    Esta função recebe um dicionário contendo os vários círculos eleitorais e respetivas eleições
    Devolve uma lista ordenada alfabeticamente com os nomes dos partidos

    dict --> list
    '''

    lista_partidos = []

    for circulo in info.keys():
        for partido in info[circulo]['votos'].keys():
            if partido not in lista_partidos:
                lista_partidos.append(partido)

    return sorted(lista_partidos)

def eh_valido (info):
    '''
    Esta função recebe um dicionário e verifica se o dicionário cumpre todas as regras de definição da função seguinte

    dict --> bool
    '''

    if type(info) != dict or len(info) < 1:
        return False

    for circulo in info:
        if type(circulo) != str or circulo == '' or type(info[circulo]) != dict or len(info[circulo]) != 2 \
            or 'votos' not in info[circulo] or 'deputados' not in info[circulo] or type(info[circulo]['votos']) != dict or \
                type(info[circulo]['deputados']) != int or info[circulo]['deputados'] <= 0 or len(info[circulo]['votos']) <= 0:
                   return False

        for chave in info[circulo]['votos']:
            if type(chave) != str or chave == '' or type(info[circulo]['votos'][chave]) != int or info[circulo]['votos'][chave] <= 0:
                return False
                
    return True

def obtem_resultado_eleicoes (info):
    '''
    Esta função recebe um dicionário contendo os vários círculos eleitorais e respetivas eleições
    Devolve uma lista ordenada de comprimento igual ao número de partidos
    Cada elemento da lista é um tuplo com elementos correspondentes ao nome do partido,
    número de deputados eleitos e o número total de votos

    dict --> list
    '''

    res = []
    lista = []
    n_deputados = 0
    votos_totais = 0

    if eh_valido(info):
        for circulo in info:
            res += atribui_mandatos(info[circulo]['votos'], info[circulo]['deputados'])
        
        partidos = obtem_partidos(info)

        for partido in partidos: #serve para verificar quantas vezes o partido aparece na atribui_mandatos
            for partido_res in res:
                if partido == partido_res:
                    n_deputados += 1  #cada vez que aparece, significa mais um deputado

            for circulo in info:
                for i in info[circulo]['votos']:
                    if i == partido:
                            votos_totais += info[circulo]['votos'][partido]
                            
            lista += ((partido, n_deputados, votos_totais),)
            n_deputados = 0
            votos_totais = 0

        lista = sorted(lista, key = lambda x: x[1] if x[1] != x[1] else x[2], reverse = True) #ordenar a lista consoante nºdeputados e depois votos totais
        return lista

    else:
        raise ValueError ('obtem_resultado_eleicoes: argumento invalido')

        

########################################################################Tarefa 3############################################################################

def produto_interno (vetor1, vetor2):
    '''
    Esta função vai receber dois tuplos (números) com o tamanho
    Devolve o resultado do produto interno

    tuple x tuple --> float
    '''

    produto = 0

    for valor in range(len(vetor1)):
        produto += vetor1[valor]*vetor2[valor]

    return float(produto) #para aparecer com uma casa decimal

def verifica_convergencia (matriz, vetor_c, solucao, precisao):
    '''
    Esta função vai receber três tuplos de igual dimensão e um valor real positivo
    O primeiro tuplo corresponde a uma matriz quadrada
    Os outros dois correspondem ao vetor das constantes e a uma solução
    O valor real indica a precisão pretendida
    Devolve True se valor absoluto do erro de todas as equações seja inferior à precisão
    Caso contrário, devolve False

    tuple x tuple x tuple x float --> bool
    '''
    verificador = 0

    for i in range(len(matriz)):
        f_i = produto_interno (matriz[i], solucao)
        if abs(f_i - vetor_c[i]) < precisao:
            verificador += 1 #vai contar as linhas cujo erro é menor que a precisão

    if verificador == len(matriz):
        return True
    else:
        return False


def retira_zeros_diagonal (matriz, vetor_c):
    '''
    Esta função recebe um tuplo de tuplos correspondente a uma matriz e um tuplo de números correspondente a um vetor de constantes
    Devolve um tuplo de tuplos, correspondente a uma matriz sem zeros nas diagonais
    e um tuplo de números, correspondente a um vetor de constantes em que lhe foram aplicadas as mesmas operações

    tuple x tuple --> tuple x tuple
    '''

    matriz = list(matriz) #poder alterar valores
    vetor_c = list(vetor_c)
    flag = False #vai servir para verificar foi encontrada a linha para a qual fazer a troca

    for linha in range(len(matriz)):
        for coluna in range(len(matriz[linha])):
            if linha == coluna: #entrada da diagonal
                if matriz[linha][coluna] == 0:
                    for j in range(len(matriz)):
                        if matriz[j][coluna] != 0 and matriz[linha][j] != 0:
                            flag = True 
                            break #a partir do momento em que se verifica o if, para o loop para efetuar a troca

        if flag == True:
            matriz[linha], matriz[j] = matriz[j], matriz[linha]
            vetor_c[linha], vetor_c[j] = vetor_c[j], vetor_c[linha]
            flag = False 
    
    matriz, vetor_c = tuple(matriz), tuple(vetor_c)

    return (matriz, vetor_c)
    

def eh_diagonal_dominante (matriz):
    '''
    Esta função recebe um tuplo de tuplos, correspondente a uma matriz
    Devolve True se for uma matriz diagonal dominante (entrada da diagonal for maior ou igual que a soma das outras entradas da linha, em valores absolutos)
    Caso contrário devolve False~

    tuple --> bool
    '''

    valor_diagonal = 0

    for linha in range(len(matriz)):
        valor_restante = 0

        for coluna in range(len(matriz[linha])):
            if coluna == linha:
                valor_diagonal = abs(matriz[linha][coluna])
            else:
                valor_restante += abs(matriz[linha][coluna])

        if valor_diagonal < valor_restante:
            return False

    return True          


def eh_valido_2 (matriz,vetor_c,precisao):
    '''
    Esta função recebe um tuplo de tuplos, correspondente a uma matriz, um tuplo de números, correspondente a um vetor de constantes,
    e um valor real positivo, correspondente à precisão e verifica se todos os argumentos 
    cumprem todas as regras de definição da função seguinte

    tuple x tuple x float --> bool
    '''
    if type(matriz) != tuple or len(matriz) == 0 or type(vetor_c) != tuple or len(vetor_c) == 0 or not isinstance (precisao,(float,int))\
        or precisao >= 1 or precisao <= 0:
            return False

    for linha in vetor_c:
        if not isinstance(linha,(int,float)):
            return False

    for linha in range(len(matriz)):
        if type(matriz[linha]) != tuple or len(matriz) != len(matriz[linha]) or\
            len(matriz[linha]) != len(vetor_c) or len(matriz[0]) != (len(matriz[linha])): 
                return False
        
        for coluna in range(len(matriz[linha])):
            if not isinstance (matriz[linha][coluna], (int,float)):
                return False

    return True


def resolve_sistema (matriz:tuple,vetor_c:tuple,precisao:float) -> tuple:
    '''
    Esta função recebe um tuplo de tuplos, correspondente a uma matriz, um tuplo de números, correspondente a um vetor de constantes,
    e um valor real positivo, correspondente à precisão
    Devolve um tuplo que é a solução do sistemas de equações
    '''

    if not eh_valido_2(matriz,vetor_c,precisao):
        raise ValueError ('resolve_sistema: argumentos invalidos')

    solucao = []

    for x in range(len(matriz)): 
        solucao += [0]

    solucao = tuple(solucao)
    solucao_nova = []
    matriz, vetor_c = retira_zeros_diagonal (matriz, vetor_c) #atribui o primeiro valor à primeira variável, o segundo à outra
    
    if not eh_diagonal_dominante(matriz):
        raise ValueError ('resolve_sistema: matriz nao diagonal dominante')
    
    while not verifica_convergencia(matriz,vetor_c,solucao,precisao):
        for linha in range(len(matriz)):
            x = solucao[linha] + (vetor_c[linha]-produto_interno(matriz[linha], solucao))/matriz[linha][linha] #método de Jacobi
            solucao_nova += [x]

        solucao = tuple(solucao_nova)
        solucao_nova = []

    return solucao