En este post te mostraré un ejercicio resuelto con Python que cubre varias cosas como recursividad, manejo de diccionarios, listas, etcétera.

Vamos a ver cómo resolver cada apartado de este problema propuesto. Igualmente con éste puedes practicar tus habilidades con el lenguaje.

Ejercicio

Es un ejercicio del laboratorio del profesor Oak que dice así:

Te encuentras trabajando como practicante en el laboratorio del Profesor Oak y te ha
asignado la tarea de analizar el inventario de Pokemones. Él tiene un archivo que
contiene los siguientes datos:

• name: nombre del Pokémon
• id: número de identificación correspondiente al Pokémon
• sp_attack: puntos de ataque del Pokémon
• sp_defense: puntos de defensa del Pokémon
• speed: puntos de velocidad del Pokémon
• ability: lista de habilidades del Pokémon

Un ejemplo del contenido del archivo y el orden de las columnas se puede observar a continuación, es un archivo CSV:

name;id;sp_attack;sp_defense;speed;ability
Bulbasaur1;1;65;65;45;Overgrow
Ivysaur1;2;80;80;60;Overgrow
Venusaur1;3;122;120;80;Overgrow
Charmander1;4;60;50;65;Blaze
Charmeleon1;5;80;65;80;Blaze
Charizard1;6;159;115;100;Blaze
Squirtle1;7;50;64;43;Torrent
Wartortle1;8;65;80;58;Torrent
Blastoise1;9;135;115;78;Torrent
Caterpie1;10;20;20;45;Shield Dust
Metapod1;11;25;25;30;Shed Skin
Butterfree1;12;90;80;70;Compoundeyes
Weedle1;13;20;20;50;Shield Dust
Kakuna1;14;25;25;35;Shed Skin
Beedrill1;15;15;80;145;Swarm
Pidgey1;16;35;35;56;Keen Eye
Pidgeotto1;17;50;50;71;Keen Eye
Pidgeot1;18;135;80;121;Keen Eye
Rattata1;19;25;35;72;Run Away
Raticate1;20;40;80;77;Run Away
Spearow1;21;31;31;70;Keen Eye
Fearow1;22;61;61;100;Keen Eye
Ekans1;23;40;54;55;Intimidate
Arbok1;24;65;79;80;Intimidate
Pikachu1;25;50;50;90;Static
Raichu1;26;95;85;110;Static
Sandshrew1;27;10;35;40;Sand Veil
Sandslash1;28;25;65;65;Sand Veil
Nidoran-h1;29;40;40;41;Poison Point
Nidorina1;30;55;55;56;Poison Point

Para trabajar esta información el profesor Oak te pide pasar los datos de los Pokemones a un diccionario que contiene otro diccionario con la siguiente estructura:

• Clave: ID del Pokémon
• Valor: Diccionario con la siguiente estructura:
  • Clave: “Nombre”; Valor: Nombre del Pokémon
  • Clave: “puntos_ataque”; Valor: Sp_attack del Pokémon
  • Clave: “puntos_defensa”; Valor: Sp_defense del Pokémon
  • Clave: “puntos_velocidad”; Valor: Speed del Pokémon
  • Clave: “habilidad”; Valor: Ability del Pokémon

Aquí un ejemplo del diccionario:

{1: {'nombre': 'Bulbasaur1', 'puntos_ataque': 65, 'puntos_defensa': 65, 'puntos_velocidad': 45, 'habilidad': 'Overgrow'}, 2: {'nombre': 'Ivysaur1', 'puntos_ataque': 80, 'puntos_defensa': 80, 'puntos_velocidad': 60, 'habilidad': 'Overgrow'}, 3: {'nombre': 'Venusaur1', 'puntos_ataque': 122, 'puntos_defensa': 120, 'puntos_velocidad': 80, 'habilidad': 'Overgrow'}, 4: {'nombre': 'Charmander1', 'puntos_ataque': 60, 'puntos_defensa': 50, 'puntos_velocidad': 65, 'habilidad': 'Blaze'}, 5: {'nombre': 'Charmeleon1', 'puntos_ataque': 80, 'puntos_defensa': 65, 'puntos_velocidad': 80, 'habilidad': 'Blaze'}, 6: {'nombre': 'Charizard1', 'puntos_ataque': 159, 'puntos_defensa': 115, 'puntos_velocidad': 100, 'habilidad': 'Blaze'}, 7: {'nombre': 'Squirtle1', 'puntos_ataque': 50, 'puntos_defensa': 64, 'puntos_velocidad': 43, 'habilidad': 'Torrent'}, 8: {'nombre': 'Wartortle1', 'puntos_ataque': 65, 'puntos_defensa': 80, 'puntos_velocidad': 58, 'habilidad': 'Torrent'}, 9: {'nombre': 'Blastoise1', 'puntos_ataque': 135, 'puntos_defensa': 115, 'puntos_velocidad': 78, 'habilidad': 'Torrent'}, 10: {'nombre': 'Caterpie1', 'puntos_ataque': 20, 'puntos_defensa': 20, 'puntos_velocidad': 45, 'habilidad': 'Shield Dust'}, 11: {'nombre': 'Metapod1', 'puntos_ataque': 25, 'puntos_defensa': 25, 'puntos_velocidad': 30, 'habilidad': 'Shed Skin'}, 12: {'nombre': 'Butterfree1', 'puntos_ataque': 90, 'puntos_defensa': 80, 'puntos_velocidad': 70, 'habilidad': 'Compoundeyes'}, 13: {'nombre': 'Weedle1', 'puntos_ataque': 20, 'puntos_defensa': 20, 'puntos_velocidad': 50, 'habilidad': 'Shield Dust'}, 14: {'nombre': 'Kakuna1', 'puntos_ataque': 25, 'puntos_defensa': 25, 'puntos_velocidad': 35, 'habilidad': 'Shed Skin'}, 15: {'nombre': 'Beedrill1', 'puntos_ataque': 15, 'puntos_defensa': 80, 'puntos_velocidad': 145, 'habilidad': 'Swarm'}, 16: {'nombre': 'Pidgey1', 'puntos_ataque': 35, 'puntos_defensa': 35, 'puntos_velocidad': 56, 'habilidad': 'Keen Eye'}, 17: {'nombre': 'Pidgeotto1', 'puntos_ataque': 50, 'puntos_defensa': 50, 'puntos_velocidad': 71, 'habilidad': 'Keen Eye'}, 18: {'nombre': 'Pidgeot1', 'puntos_ataque': 135, 'puntos_defensa': 80, 'puntos_velocidad': 121, 'habilidad': 'Keen Eye'}, 19: {'nombre': 'Rattata1', 'puntos_ataque': 25, 'puntos_defensa': 35, 'puntos_velocidad': 72, 'habilidad': 'Run Away'}}

Importante: el ID del pokémon, los puntos de ataque, puntos de defensa y puntos de velocidad deben ser un entero. El nombre y habilidad deben estar en formato string.

Problema 1: diccionario

El profesor Oak le solicita que cree el diccionario a partir del archivo pokemon.csv. Recuerde que el diccionario debe tener la estructura previamente descrita.

    def crear_diccionarios(self, ruta="pokemon.csv"):
        pokemones = {}
        with open(ruta) as archivo:
            next(archivo)  # Descartar la primera línea
            for linea in archivo:
                linea_como_arreglo = linea.rstrip().split(";")
                name = linea_como_arreglo[0]
                id = linea_como_arreglo[1]
                sp_attack = linea_como_arreglo[2]
                sp_defense = linea_como_arreglo[3]
                speed = linea_como_arreglo[4]
                ability = linea_como_arreglo[5]
                pokemones[int(id)] = {
                    "nombre": name,
                    "puntos_ataque": int(sp_attack),
                    "puntos_defensa": int(sp_defense),
                    "puntos_velocidad": int(speed),
                    "habilidad": ability,
                }
        return pokemones

Simplemente leemos un CSV, usamos split y luego convertimos la cadena a un número.

Problema 2: buscar dato de Pokémon

El profesor Oak necesita consultar frecuentemente datos de los Pokémon que tiene en su laboratorio para intercambiar con otros investigadores.

Por ese motivo, él le solicita que genere una función que a partir del ID del Pokémon y un valor de búsqueda devuelva como resultado el dato para el Pokémon.

    def buscar_dato(self, pokemones, id, valor):
        for id_pokemon in pokemones:
            if id_pokemon == id:
                pokemon = pokemones.get(id_pokemon)
                return pokemon[valor]
        return "Pokémon no encontrado"

Los valores de entrada son el id, el valor y el diccionario de Pokemones. El valor de salida debería ser el dato solicitado para el Pokémon con ese ID.

Pokémon más rápido: problema 3

El profesor Oak requiere conocer el Pokémon más rápido que tiene en su laboratorio para enviarlo a una competencia en el torneo Pokémon de la ciudad Johto.

Él le solicita que cree un algoritmo de búsqueda con complejidad O(n) que retorne una tupla con el nombre del Pokémon y el puntaje de velocidad.

    def pokemon_rapido(self, pokemones):
        nombre = ""
        puntaje = -1  # iniciar valores en algo muy bajo
        for id_pokemon in pokemones:
            pokemon = pokemones.get(id_pokemon)
            if pokemon["puntos_velocidad"] >= puntaje:
                puntaje = pokemon["puntos_velocidad"]
                nombre = pokemon["nombre"]
        return nombre, puntaje

Lo que hacemos aquí es recorrer todo el diccionario y buscar el Pokémon.

Ordenar Pokemones por nombre: problema 4

El profesor Oak necesita ordenar el nombre de los Pokemones de forma ascendente para publicar la lista en la página web del laboratorio.

Él le solicita que cree un algoritmo de ordenamiento con complejidad O(n log n), que retorne una lista de tuplas que contenga el nombre del Pokémon y el ID del mismo.

def merge(left, right):
    merged_list = []
    indice_de_izquierda = 0
    indice_de_derecha = 0
    indice_arreglo_ordenado = 0
    while indice_de_izquierda < len(left) and indice_de_derecha < len(right):
        valor_izquierda = left[indice_de_izquierda]
        valor_derecha = right[indice_de_derecha]
        # Accedemos a 0 porque en 0 está el nombre (en 1 está el ID)
        if valor_izquierda[0] <= valor_derecha[0]:
            # El de la izquierda es menor, entonces lo ponemos primero
            merged_list.append(valor_izquierda)
            # Y aumentamos en 1 el valor de la izquierda
            indice_de_izquierda += 1
        else:
            merged_list.append(valor_derecha)
            indice_de_derecha += 1

        # Sin importar lo que hayamos movido, aumentamos el índice del actual
        indice_arreglo_ordenado += 1
    # Hasta aquí puede que el índice izquierdo o derecho hayan llegado a su fin, pero no ambos. Entonces
    # nos aseguramos de recorrerlos a ambos hasta el final
    while indice_de_izquierda < len(left):
        merged_list.append(left[indice_de_izquierda])
        indice_de_izquierda += 1

    while indice_de_derecha < len(right):
        merged_list.append(right[indice_de_derecha])
        indice_de_derecha += 1
    return merged_list


def merge_sort(lista):
    longitud = len(lista)
    mitad = longitud//2  # El doble / es para dividir y redondear hacia abajo
    # Condición de salida de recursividad es que el arreglo mida 1 o 0
    if longitud <= 1:
        return lista
    left = merge_sort(lista[:mitad])
    right = merge_sort(lista[mitad:])
    return merge(left, right)

def nombre_ascendente(self, pokemones):
      result = []
      for id_pokemon in pokemones:
          result.append((pokemones.get(id_pokemon)["nombre"], id_pokemon))
      result = merge_sort(result)
      return result

En este caso usamos el algoritmo de merge sort para ordenar la lista, ya que la complejidad lo requiere así.

Problema 5: búsqueda binaria

En tres semanas el profesor Oak necesita entregar Pokemones a los nuevos entrenadores que llegan a su laboratorio.

En esta ocasión va a realizar un sorteo con los nombres de los Pokemones publicados en la página web del laboratorio.

Luego del sorteo necesita conocer la habilidad que el Pokémon tiene para instruir a los entrenadores, por ese motivo le solicita que cree un algoritmo de búsqueda binaria con complejidad O(log n), que reciba como parámetro el nombre del Pokémon a buscar y retorne los datos del Pokémon en el diccionario.

Si el nombre del Pokémon no es encontrado debe retornar el valor de -1 como llave y el texto “No encontrado” como valor.

    def busqueda_habilidad(self, nombre_a_buscar, nombres_ordenados, pokemones):
        result = {}
        izquierda, derecha = 0, len(nombres_ordenados) - 1
        while izquierda <= derecha:
            indiceDelElementoDelMedio = (izquierda + derecha) // 2
            elementoDelMedio = nombres_ordenados[indiceDelElementoDelMedio]
            # Accedemos a 0 porque queremos el primer valor de la tupla, mismo que es el nombre
            if elementoDelMedio[0] == nombre_a_buscar:
                # Aquí hemos encontrado al Pokémon. Usamos su índice para acceder al diccionario
                id = elementoDelMedio[1]
                return {id: pokemones[id]}
            if nombre_a_buscar < elementoDelMedio[0]:
                derecha = indiceDelElementoDelMedio - 1
            else:
                izquierda = indiceDelElementoDelMedio + 1
        return {-1: "No encontrado"}

En este caso simplemente usamos la búsqueda binaria que ya hemos visto anteriormente, solo que adaptada para este ejercicio.

Poniendo todo junto

El código completo queda como se ve a continuación. Ya te dije que es un ejercicio resuelto de Python, por ello es que es muy específico en su solicitud:

import sys
sys.setrecursionlimit(20000)
# FUNCIONES RECURSIVAS EMPIEZAN AQUÍ


def merge(left, right):
    merged_list = []
    indice_de_izquierda = 0
    indice_de_derecha = 0
    indice_arreglo_ordenado = 0
    while indice_de_izquierda < len(left) and indice_de_derecha < len(right):
        valor_izquierda = left[indice_de_izquierda]
        valor_derecha = right[indice_de_derecha]
        # Accedemos a 0 porque en 0 está el nombre (en 1 está el ID)
        if valor_izquierda[0] <= valor_derecha[0]:
            # El de la izquierda es menor, entonces lo ponemos primero
            merged_list.append(valor_izquierda)
            # Y aumentamos en 1 el valor de la izquierda
            indice_de_izquierda += 1
        else:
            merged_list.append(valor_derecha)
            indice_de_derecha += 1

        # Sin importar lo que hayamos movido, aumentamos el índice del actual
        indice_arreglo_ordenado += 1
    # Hasta aquí puede que el índice izquierdo o derecho hayan llegado a su fin, pero no ambos. Entonces
    # nos aseguramos de recorrerlos a ambos hasta el final
    while indice_de_izquierda < len(left):
        merged_list.append(left[indice_de_izquierda])
        indice_de_izquierda += 1

    while indice_de_derecha < len(right):
        merged_list.append(right[indice_de_derecha])
        indice_de_derecha += 1
    return merged_list


def merge_sort(lista):
    longitud = len(lista)
    mitad = longitud//2  # El doble / es para dividir y redondear hacia abajo
    # Condición de salida de recursividad es que el arreglo mida 1 o 0
    if longitud <= 1:
        return lista
    left = merge_sort(lista[:mitad])
    right = merge_sort(lista[mitad:])
    return merge(left, right)


# FUNCIONES RECURSIVAS TERMINAN AQUÍ
class Solution:
    # NO MODIFICAR ABAJO DE EST LINEA, ES PARTE DEL AUTOGRADER
    def sort(self, data=[]):
        return "clear"

    def sorted(self, data=[]):
        return "clear"
    # NO MODIFICAR ARRIBA DE EST LINEA, ES PARTE DEL AUTOGRADER

    def crear_diccionarios(self, ruta="pokemon.csv"):
        pokemones = {}
        with open(ruta) as archivo:
            next(archivo)  # Descartar la primera línea
            for linea in archivo:
                linea_como_arreglo = linea.rstrip().split(";")
                name = linea_como_arreglo[0]
                id = linea_como_arreglo[1]
                sp_attack = linea_como_arreglo[2]
                sp_defense = linea_como_arreglo[3]
                speed = linea_como_arreglo[4]
                ability = linea_como_arreglo[5]
                pokemones[int(id)] = {
                    "nombre": name,
                    "puntos_ataque": int(sp_attack),
                    "puntos_defensa": int(sp_defense),
                    "puntos_velocidad": int(speed),
                    "habilidad": ability,
                }
        return pokemones

    def buscar_dato(self, pokemones, id, valor):
        for id_pokemon in pokemones:
            if id_pokemon == id:
                pokemon = pokemones.get(id_pokemon)
                return pokemon[valor]
        return "Pokémon no encontrado"

    def pokemon_rapido(self, pokemones):
        nombre = ""
        puntaje = -1  # iniciar valores en algo muy bajo
        for id_pokemon in pokemones:
            pokemon = pokemones.get(id_pokemon)
            if pokemon["puntos_velocidad"] >= puntaje:
                puntaje = pokemon["puntos_velocidad"]
                nombre = pokemon["nombre"]
        return nombre, puntaje

    def nombre_ascendente(self, pokemones):
        result = []
        for id_pokemon in pokemones:
            result.append((pokemones.get(id_pokemon)["nombre"], id_pokemon))
        result = merge_sort(result)
        return result

    def busqueda_habilidad(self, nombre_a_buscar, nombres_ordenados, pokemones):
        result = {}
        izquierda, derecha = 0, len(nombres_ordenados) - 1
        while izquierda <= derecha:
            indiceDelElementoDelMedio = (izquierda + derecha) // 2
            elementoDelMedio = nombres_ordenados[indiceDelElementoDelMedio]
            # Accedemos a 0 porque queremos el primer valor de la tupla, mismo que es el nombre
            if elementoDelMedio[0] == nombre_a_buscar:
                # Aquí hemos encontrado al Pokémon. Usamos su índice para acceder al diccionario
                id = elementoDelMedio[1]
                return {id: pokemones[id]}
            if nombre_a_buscar < elementoDelMedio[0]:
                derecha = indiceDelElementoDelMedio - 1
            else:
                izquierda = indiceDelElementoDelMedio + 1
        return {-1: "No encontrado"}


s = Solution()
pokemones = s.crear_diccionarios()
print(s.buscar_dato(pokemones, 8, "habilidad"))
print(s.buscar_dato(pokemones, 88888, "puntos_velocidad"))
print(s.buscar_dato(pokemones, 3, "puntos_ataque"))
print(s.pokemon_rapido(pokemones))
print(s.nombre_ascendente(pokemones))
print(s.busqueda_habilidad("Squirtle5", s.nombre_ascendente(pokemones), pokemones))

En las últimas líneas te muestro cómo usar los métodos. Por cierto, si quieres la listas de pokemones puedes verla aquí.

Te dejo más tutoriales y códigos de Python en mi blog.