Ejercicios Resueltos de Programación en Python: Algoritmos y Estructuras de Datos

Búsqueda y combinación de contactos

Funciones para la gestión, búsqueda y fusión ordenada de colecciones de contactos.

def search_phone(c1: tuple, nombre: str) -> int:
    res = None
    for i in range(len(c1)):
        if c1[i][0] == nombre:
            res = nombre
    return res

def combine(c1: list[Contact], c2: list[Contact]) -> list[Contact]:
    i = 0
    j = 0
    res = []
    while i < len(c1) and j < len(c2):
        if c1[i][0] < c2[j][0]:
            res.append(c1[i])
            i += 1
        elif c1[i][0] > c2[j][0]:
            res.append(c2[j])
            j += 1
        else:
            res.append(c1[i])
            i += 1
            j += 1
    while i < len(c1):
        res.append(c1[i])
        i += 1
    while j < len(c2):
        res.append(c2[j])
        j += 1
    return res

Ejercicio: Números libres

Implementación de funciones para identificar y recopilar números libres de cuadrados (aquellos cuyos factores primos no se repiten).

def is_free(num: int) -> bool:
    assert num > 0
    still_free = True
    factor = 2
    while num > 1 and still_free:
        exp = 0
        while num % factor == 0:
            num = num // factor
            exp += 1
        still_free = exp <= 1
        factor += 1
    return still_free

Realiza una función free_until(num: int) -> list[int] que devuelva la lista de números libres hasta num (sin incluir):

def free_until(num: int) -> list[int]:
    flist = []
    for i in range(1, num):
        if is_free(i):
            flist.append(i)
    return flist

Ejercicio: Problema del cambio de monedas

Resolución del cambio de monedas bajo dos modalidades: disponibilidad ilimitada y disponibilidad limitada mediante un enfoque voraz (greedy).

def change_unlimited(amount: int, coins: list[int]) -> list[int]:
    change = []
    for coin in coins:
        change.append(amount // coin)
        amount = amount % coin
    return change

def change_limited(amount: int, coins: list[int], limit: list[int]) -> tuple[bool, list[int]]:
    change = []
    i = 0
    while i < len(coins):
        ncoins = amount // coins[i]
        if ncoins > limit[i]:
            ncoins = limit[i]
        change.append(ncoins)
        amount = amount - coins[i] * ncoins
        i += 1
    return amount == 0, change

Ejercicio: Juego de dominó

Comprobaciones de compatibilidad, validez de secuencias y cálculo de puntuación para fichas de dominó.

def value(tile: Tile) -> int:
    return tile[0] + tile[1]

def are_compatible(t1: Tile, t2: Tile) -> bool:
    return t1[1] == t2[0] or t1[1] == t2[1]

def is_valid_sequence(seq: list[tuple[int, int]]) -> bool:
    if len(seq) <= 1:
        res = True  # Una ficha sola o ninguna siempre es válida
    else:
        i = 0
        res = True
        while i < len(seq) - 1:
            if seq[i][1] != seq[i + 1][0]:
                res = False
            i += 1
    return res

def score(seq: list[Tile]) -> int:
    if is_valid_sequence(seq):
        res = 0
        for tile in seq:
            res += value(tile)
    else:
        res = 0
    return res

Ejercicio: Conjetura de Goldbach

Verificación de números primos y descomposición de un número par como la suma de dos primos.

def is_prime(n: int) -> bool:
    i = 2
    while (i * i <= n) and n % i != 0:
        i += 1
    return i * i > n

def decompose(n: int) -> tuple[bool, int, int]:
    a, b = 2, n - 2
    while a <= b and not (is_prime(a) and is_prime(b)):
        a, b = a + 1, b - 1
    return a <= b, a, b

Ejercicio de listas y secuencias

Operaciones y algoritmos sobre listas numéricas: ordenación, extremos locales, divisibilidad y propiedades numéricas.

def is_ascending(lst: Sequence) -> bool:
    i = 1
    while i < len(lst) and lst[i - 1] <= lst[i]:
        i += 1
    return i >= len(lst)

def is_local_max(lst: list[int], pos: int) -> bool:
    assert pos > 0 and pos < len(lst) - 1, f'Error: {pos} debe ser una posición intermedia'
    return lst[pos] > lst[pos - 1] and lst[pos] > lst[pos + 1]

def is_local_min(lst: list[int], pos: int) -> bool:
    assert pos > 0 and pos < len(lst) - 1, f'Error {pos} must be an intermediate position'
    return lst[pos] < lst[pos - 1] and lst[pos] < lst[pos + 1]

def peaks_valleys(lst: list[int]) -> tuple[list[int], list[int]]:
    i = 1
    peaks = []
    valleys = []
    while i < len(lst) - 1:
        if is_local_max(lst, i):
            peaks.append(i)
        if is_local_min(lst, i):
            valleys.append(i)
        i += 1
    return peaks, valleys

def gcd(a: int, b: int) -> int:
    while b > 0:
        a, b = b, a % b
    return a

def communitary(lst: list[int]) -> bool:
    i = 1
    divisor = lst[0]
    while i < len(lst) and divisor > 1:
        divisor = gcd(divisor, lst[i])
        i += 1
    return divisor > 1

def is_baroque(lst: list[int]) -> bool:
    i = 0
    while i < len(lst) and lst[i] % 2 == i % 2:
        i += 1
    return i == len(lst)

def less_than(lst: list[int], v: int) -> list[int]:
    i = 0
    newlst = []
    while i < len(lst) and lst[i] < v:
        newlst.append(lst[i])
        i += 1
    return newlst

def is_ascending(lst: Sequence) -> bool:
    i = 1
    while i < len(lst) and lst[i - 1] <= lst[i]:
        i += 1
    return i >= len(lst)

Ejercicio de máximo de repeticiones

Cálculo de frecuencias de caracteres y localización del carácter con mayor número de repeticiones dentro de una cadena.

def count_occurrences(palabra: str, letra: str) -> int:
    i = 0
    cuenta = 0
    while i < len(palabra):
        if palabra[i] == letra:
            cuenta += 1
        i += 1
    return cuenta

def max_occurrences(palabra: str, letra: str) -> str:
    s = palabra
    assert len(s) > 0
    num_rep = 0
    ltr = ''
    i = 0
    while i < len(s):
        current = count_occurrences(s, s[i])
        if current > num_rep:
            num_rep = current
            ltr = s[i]
        i += 1
    return ltr

Números de Thabit

Determinación de si un entero dado pertenece a la sucesión de los números de Thabit de la forma 3 · 2^k - 1.

def thabit(n: int) -> bool:
    k = 0
    res = True
    while res:
        t = 3 * (2 ** k) - 1
        if t == n:
            return True
        elif t > n:
            res = False
        k += 1
    return res

Codificación tipo espejo

Transformación y cifrado de caracteres alfabéticos mediante una correspondencia invertida respecto a los extremos del abecedario o subrangos definidos.

def espejo(c: str) -> str:
    if 'a' <= c <= 'z':
        res = chr(ord('z') - (ord(c) - ord('a')))
    else:
        res = c
    return res

def espejo1(inic, fin, car):
    res = car
    if inic <= car <= fin:
        res = chr(ord(inic) + ord(fin) - ord(car))
    return res

def codifica_espejo(cadena):
    inic = 'z'
    fin = 'a'
    i = 0
    while i < len(cadena):
        c = cadena[i]
        if 'a' <= c <= 'z':
            if c < inic:
                inic = c
            if c > fin:
                fin = c
        i += 1
    nueva = ""
    j = 0
    while j < len(cadena):
        nueva = nueva + espejo1(inic, fin, cadena[j])
        j += 1
    return nueva

Juego de las siete y media

Lógica de cómputo de puntuaciones y selección del jugador ganador en el tradicional juego de naipes de las siete y media.

def value(player: list[int]) -> float:
    total = 0.0
    for card in player:
        if card in [8, 9, 10]:
            total += 0.5
        else:
            total += card
    return total

def winner(game: list[list[int]]) -> int:
    max_score = -1.0
    winner_index = -1
    for i, jugada in enumerate(game):
        v = value(jugada)
        if v <= 7.5 and v > max_score:
            max_score = v
            winner_index = i
    return winner_index