Manejo de colecciones de objetos¶

Vamos a ver a continuación algunos ejemplos de retos donde es necesario (o recomendable) almacenar la información de forma más compleja, empleando clases y objetos ya que hay varios datos que tratar de cada individuo del problema. También, en algunos de estos casos, será necesario ordenar la colección de datos siguiendo algún criterio para resolver el problema.

1. Ordenando listas de objetos: los niños buenos¶

En este reto de Acepta el Reto nos plantean que resolvamos cómo va a repartir Papá Noel los regalos a los niños. De cada niño tenemos dos datos: cómo de bien se ha portado (número entre 1 y 100) y cuánto pesan los regalos que ha pedido (número entre 1 y 1000). Papá Noel quiere repartir primero los regalos a los niños que mejor se han portado y, si dos niños se han portado igual, quiere repartir primero los regalos que pesen menos.

Cada caso de prueba vendrá iniciado por un número n, que indica a cuántos niños hay que repartir regalos. Luego vienen los datos de cada niño en una línea; de cada uno guardaremos dos datos: cómo de bueno ha sido y cuánto pesan los regalos que ha pedido. Deberemos mostrar por pantalla los datos ordenados de los niños, en el orden en que Papá Noel repartirá los regalos.

Por ejemplo, si tenemos este caso de entrada:

Tendremos que procesar en total 3 niños. Primero se repartirán los regalos a los niños que se han portado 100 de bien y, ante esto, se elegirá primero al que sus regalos pesan 1, y luego al que pesan 12. Se deja en tercer lugar al niño que se ha portado 80 de bien. Así, la salida para este caso debería ser:

100 1
100 12
80 2

Para empezar, crearemos una clase Nino que almacenará como atributos los datos de cada niño: cómo de bueno ha sido (atributo bueno) y cuánto pesan sus regalos (atributo peso). En el constructor asignamos las dos cosas, y hacemos que la clase implemente la interfaz Comparable<Nino> para poder comparar dos niños entre sí. Lo que haremos será comparar el atributo bueno de mayor a menor y, si son iguales, entonces comparamos el atributo peso de menor a mayor. Añadimos también un método toString para sacar la información del niño con el formato que pide el problema (bueno y peso separados por un espacio). Así quedaría esta clase:

class Nino implements Comparable<Nino>
{
    private int bueno;
    private int peso;

    public Nino(int bueno, int peso)
    {
        this.bueno = bueno;
        this.peso = peso;
    }

    @Override
    public int compareTo(Nino n)
    {
        // Comparamos "bueno" de mayor a menor
        int resultado = Integer.compare(n.bueno, this.bueno);
        // Si coincide, comparamos "peso" de menor a mayor
        if(resultado == 0)
        {
            resultado = Integer.compare(this.peso, n.peso);
        }
        return resultado;
    }

    @Override
    public String toString()
    {
        return bueno + " " + peso;
    }
}

Ahora que ya tenemos esta clase, podemos construir un programa principal que lea cada caso de prueba, construya una lista de objetos Nino con los datos que vaya leyendo de cada línea, la ordene según el criterio que hemos definido en la propia clase y la saque por pantalla:

public class Reto366
{
    public static void main(String[] args)
    {
        Scanner sc = new Scanner(System.in);
        ArrayList<Nino> lista;
        int n;

        do
        {
            // Leemos el número de niños
            n = sc.nextInt();
            if(n != 0)
            {
                // Almacenamos los niños en una lista
                lista = new ArrayList<Nino>();
                for(int i = 1; i <= n; i++)
                {
                    lista.add(new Nino(sc.nextInt(), sc.nextInt()));
                }
                // Ordenamos por el criterio de la clase Nino
                Collections.sort(lista);
                for(Nino nino : lista)
                {
                    System.out.println(nino);
                }
                // Debemos sacar una línea en blanco al final de cada caso
                System.out.println();
            }
        }
        while(n != 0);
    }
}

1.1. Desarrollos en las bicicletas¶

En este reto de Acepta el Reto debemos hacer algo parecido con los desarrollos de las bicicletas que nos plantean. Cada caso de prueba consta de tres líneas:

En la primera línea nos dicen cuántos platos p y cuántas coronas c tiene la bicicleta en cuestión
En la segunda línea nos dan los tamaños de los platos, separados por espacios
En la tercera línea nos dan los tamaños de las coronas, separados por espacios

La idea es crear una clase Desarrollo que almacene una combinación de tamaño de plato y corona, y en el programa principal una lista de desarrollos que comprueba todas las combinaciones de platos y coronas que se puede tener con la bicicleta, y las ordene de menor a mayor desarrollo (es decir, de menor a mayor relación entre tamaño de plato y de corona).

Por ejemplo, para este caso de prueba:

2 3
34 48
20 26 34

Tenemos 2 platos de tamaño 34 y 48, y 3 coronas de tamaño 20, 26 y 34. Con esto salen 6 posibles combinaciones:

Plato 34, Corona 20
Plato 34, Corona 26
Plato 34, Corona 34
Plato 48, Corona 20
Plato 48, Corona 26
Plato 48, Corona 34

La combinación que menos desarrollo tiene es la primera (34 / 34), y la que más tiene es la cuarta (48 / 20). Ordenadas de menor a mayor con el formato que pide el ejercicio (mostrando plato y corona separados por un guión, todos en una línea separados por espacios) quedaría así:

34-34 34-26 48-34 34-20 48-26 48-20

Ejercicio 1

Trata de resolver este reto en Java y comprueba que la plataforma lo acepta.

2. Uso de diccionarios: el telegrama más corto¶

Vamos a practicar cómo emplear diccionarios o mapas en retos con este reto de Acepta el Reto. En él nos dan al principio una tabla de cómo se codifican los distintos símbolos en código Morse, empleando puntos y rayas. Debemos procesar una serie de casos de pruebas, cada uno formado por un texto, y debemos indicar cuál es la duración en puntos totales del telegrama transcrito a Morse. Para ello se deben tener en cuenta las siguientes premisas:

Cada raya que se emita equivale a 3 puntos
Entre cada símbolo (punto o raya) de una misma letra hay que esperar 1 punto
Entre cada letra o símbolo del mensaje hay que esperar 3 puntos
Entre cada palabra (es decir, cada espacio en blanco que nos encontremos) hay que esperar 5 puntos

Así, por ejemplo:

Para el mensaje "?", cuyo código Morse es ..--.., tendremos en total:
- 1 + 1 + 3 + 3 + 1 + 1 = 10 puntos de los puntos y rayas del mensaje
- 5 puntos, uno por la separación entre cada uno de los 6 símbolos anteriores
- Total: 15 puntos
Para el mensaje "YA NACIO" tendremos el siguiente cómputo
Y = -.-- = 10 puntos + 3 de separación = 13 puntos
A = .- = 4 puntos + 1 de separación = 5 puntos
(espacio en blanco) = 5 puntos
N = -. = 4 puntos + 1 de separación = 5 puntos
A = .- = 4 puntos + 1 de separación = 5 puntos
C = -.-. = 8 puntos + 3 de separación = 11 puntos
I = .. = 2 puntos + 1 de separación = 3 puntos
O = --- = 9 puntos + 2 de separación = 11 puntos
Además, contamos 3 puntos de separación entre cada letra: Y-A, N-A, A-C, C-I e I-O (15 en total)
Suma total = 73 puntos

Comenzaremos almacenando en un diccionario o tabla hash la codificación de cada símbolo en su cadena Morse equivalente. Esto lo haremos con la siguiente función:

static HashMap<Character, String> crearMapaMorse()
{
    HashMap<Character, String> tabla = new HashMap<>();

    tabla.put('A', ".-");
    tabla.put('B', "-...");
    tabla.put('C', "-.-.");
    tabla.put('D', "-..");
    tabla.put('E', ".");
    tabla.put('F', "..-.");
    tabla.put('G', "--.");
    tabla.put('H', "....");
    tabla.put('I', "..");
    tabla.put('J', ".---");
    tabla.put('K', "-.-");
    tabla.put('L', ".-..");
    tabla.put('M', "--");
    tabla.put('N', "-.");
    tabla.put('O', "---");
    tabla.put('P', ".--.");
    tabla.put('Q', "--.-");
    tabla.put('R', ".-.");
    tabla.put('S', "...");
    tabla.put('T', "-");
    tabla.put('U', "..-");
    tabla.put('V', "...-");
    tabla.put('W', ".--");
    tabla.put('X', "-..-");
    tabla.put('Y', "-.--");
    tabla.put('Z', "--..");
    tabla.put('!', "-.-.--");
    tabla.put('?', "..--..");

    return tabla;
}

En nuestro programa principal leeremos primero el número de casos de prueba, y luego leemos el texto de cada caso y vamos analizando símbolo a símbolo:

public static void main(String[] args)
{
    HashMap<Character, String> tabla = crearMapaMorse();
    String linea;        
    Scanner sc = new Scanner(System.in);

    // Leemos los casos y el salto de línea que hay después
    int casos = sc.nextInt();
    sc.nextLine();

    for(int n = 1; n <= casos; n++)
    {
        // Leemos cada caso
        linea = sc.nextLine();
        int total = 0;
        // Procesamos cada símbolo del texto leído
        for(int i = 0; i < linea.length(); i++)
        {
            if(linea.charAt(i) != ' ')
            {
                // Obtenemos la representación Morse de la letra
                String representacion = tabla.get(linea.charAt(i));
                for(int j = 0; j < representacion.length(); j++)
                {
                    if(representacion.charAt(j) == '.')
                        total += 1;
                    else
                        total += 3;
                }
                // Un punto entre cada símbolo
                total += representacion.length() - 1;

                if (i > 0 && linea.charAt(i-1) != ' ')
                {
                    // 3 puntos entre cada letra
                    total += 3;
                }
            }                
            else
            {
                // 5 puntos entre cada palabra
                total += 5;
            }
        }            

        System.out.println(total);
    }
}

2.2. Ninots indultados¶

En este reto de Acepta el Reto debemos determinar qué ninots son indultados en las fallas de Valencia. Cada caso de prueba vendrá dado por un número n de votaciones de ninots, y luego seguirán n palabras (dispuestas en varias líneas, y separadas por espacios) con los nombres de los ninots votados (en mayúsculas si son de fallas adultas, en minúsculas si son infantiles). Debemos indicar en una línea, y separados por espacios, los nombres de los ninots infantil y adulto que han recibido más votos.

Por ejemplo, para este caso de prueba:

5
condealtea GUANYARDINES
antigadecampanar QUARTEXTRAMURS GUANYARDINES

Deberemos indicar que en el caso de las fallas infantiles hay "empate", y en el de las adultas se indulta a GUANYARDINES:

empate GUANYARDINES

Aquí van algunas PISTAS:

Para leer cada palabra por separado de las siguientes puede usar el método next() de Scanner (sc.next()), que va procesando cada token o palabra clave que encuentra. Es conveniente que la enlaces con una operación trim para eliminar espacios que puedan quedar a ambos lados: sc.next().trim().
Puedes crear un diccionario o mapa para guardarte las ocurrencias de las fallas infantiles y otra para las adultas (o un solo diccionario para todas). Cada vez que leas una palabra, miras si está en el diccionario: si no está la añades con contador 1, y si está le incrementas el contador. Deberás crear para ello un diccionario cuyas claves sean Strings (nombres de las fallas) y cuyos valores sean enteros (Integer en Java).

Ejercicio 2

Trata de resolver este reto en Java y comprueba que la plataforma lo acepta.

3. Uso de conjuntos: ¿Podemos empezar?¶

En este reto de Acepta el Reto debemos decidir si puede empezar o no una reunión de vecinos. Para ello, en cada caso de prueba nos darán dos líneas:

En la primera nos dan tres números indicando cuántos pisos hay en la urbanización (p), cuántas letras o puertas hay en cada piso (l) y cuántos asistentes han venido a la reunión (a).
En la segunda línea nos dan, separados por espacios, el piso y la letra donde vive cada vecino. Puede haber más de un vecino que viva en el mismo piso y letra y hayan venido juntos a la reunión

Deberemos mostrar el mensaje "EMPEZAMOS" si al menos hay vecinos de la mitad de viviendas, o "ESPERAMOS" si aún no. En el caso de que el total de viviendas sea impar, se considerará la mitad por exceso.

Por ejemplo, dado este caso de prueba:

4 1 3
1 A 2 A 1 A

La casa tiene 4 plantas, con una letra por planta, y han venido 3 vecinos que son dos del 1ºA y otro del 2ºA. En total se han cubierto 2 de las 4 viviendas del edificio, con lo que podemos empezar la reunión.

Para resolver el reto haremos lo siguiente:

Calcularemos cuántas viviendas totales hay en el edificio. Esto se consigue multiplicando los dos primeros datos que nos dan: el número de pisos p por el total de letras en cada piso l.
Almacenamos en un conjunto las distintas viviendas que vienen a la reunión, de forma que descartamos las viviendas repetidas. Si el tamaño del conjunto es al menos la mitad del total, podremos empezar (considerando también el caso de que haya un número impar de viviendas)

Aquí tenemos una posible solución en Java:

import java.util.*;

public class PodemosEmpezar
{
    public static void main(String[] args)
    {
        Scanner sc = new Scanner(System.in);
        HashSet<String> viviendas;
        int pisos, letras, asistentes, totalViviendas, mitad;

        do
        {
            pisos = sc.nextInt();
            letras = sc.nextInt();
            asistentes = sc.nextInt();

            if (pisos != 0)
            {
                // Calculamos el total de viviendas
                totalViviendas = pisos * letras;

                viviendas = new HashSet<>();
                // Añadimos en el conjunto el número de piso seguido de la letra
                for (int i = 0; i < asistentes; i ++)
                {
                    String piso = sc.next();
                    String letra = sc.next();
                    viviendas.add(piso + letra);
                }

                // Calculamos la mitad de asistentes necesaria
                if (totalViviendas % 2 == 0)
                    mitad = totalViviendas / 2;
                else
                    mitad = totalViviendas / 2 + 1;

                if (viviendas.size() >= mitad)
                    System.out.println("EMPEZAMOS");
                else
                    System.out.println("ESPERAMOS");
            }

        } while (pisos != 0);
    }
}

En esta ocasión también empleamos sc.next() para ir leyendo los pisos y letras de los asistentes a la reunión, de forma consecutiva.

3.1. Michael J. Fox y el Pato Donald¶

En este reto de Acepta el Reto tenemos que distinguir si hay cumpleaños repetidos en una secuencia de fechas. Nos darán para cada caso de prueba el número de fechas que tenemos que procesar, y luego una secuencia de fechas, separadas por espacios. Tenemos que indicar si hay cumpleaños repetidos (SI) o todos son distintos (NO).

Por ejemplo, para este caso de prueba:

5
9/6/1961 22/10/1938 31/5/1961 20/4/1964 9/6/1934

Vemos que el cumpleaños el 9/6 se repite dos veces, por lo que diremos que SI.

Ejercicio 3

Trata de resolver este reto en Java y comprueba que la plataforma lo acepta.