Esto esta publicado bastante antes de lo que debería siguiendo la progresión de los posts que hablan sobre Tecnología, Informática y Programación; pero hay un buen motivo detrás de ello, el día 20 de febrero de 2020, se celebró la Hashcode de ese mismo año y formamos un equipo. Voy a decir algo que no quiero que se malinterprete y es el causante de la redacción de este post: "Se cometieron errores, no una sola persona si no de todos los integrantes"; y por ello estoy redactando este post, para intentar que nadie, de los que lean esto, los repita.

Pero antes que nada voy a explicar de que se trata la Hashcode. La Hashcode es una competición anual de programación por equipos organizada por Google, que se celebra por todo el mundo, en lugares físicos conocidos como Hubs o mediante presencia Online, destinado a todo tipo de programadores, en la que se les presenta un problema a los participantes que deben de resolver mediante código en unas pocas horas para pasar a la siguiente fase.

Y esta serie de consejos y métodos no solo os valdrán para esta competición o similares, si no que pueden aplicarse a entornos profesionales, así que id con cuidado.

• El primer paso es el mas evidente, aunque fue en lo que fallamos más y por eso voy a recalcarlo en mayúsculas y negrita: ASEGURAOS DE QUE TODOS ENTENDÁIS EL PROBLEMA. Es un consejo trivial, pero es que si falláis con esto es inútil el programa desarrollado y dependiendo del caso puede llegar a ser peligroso; por ejemplo si se aplicara en un entorno industrial o de uso público.

• El segundo paso es pensar en como se resolverá el problema, es decir, como funcionará una primera versión del programa, sin necesidad de programarlo, solamente el algoritmo. En esta parte es donde hay debates entre las "escuelas", dependiendo de la formación de cada uno intentará aplicar una metodología diferente, unos dirán de desarrollar un programa básico y luego mejorarlo; y otros analizando el problema desarrollarán el algoritmo más eficiente que encuentren y lo implementarán directamente. Dependiendo del caso cada metodología ofrece sus pros y sus contras, yo defiendo el punto medio para su uso en competiciones, aunque si hay tiempo de sobra para desarrollar, prefiero dedicarle su tiempo al algoritmo perfecto.

• El siguiente paso es obviamente implementar el algoritmo del paso anterior, en el lenguaje de preferencia, cada uno es libre de hacerlo como considere mejor. Aconsejo durante la implementación ir probando el programa para ver si funciona correctamente, y si existen inconsistencias en los resultados, revisar a que no se deba a un problema en el algoritmo, que si es así habría que rediseñarlo o reparar los casos en los que no funcione.

• El último paso a seguir, sería terminar las pruebas, comprobando que funciona como se esperaba y si es pertinente, asegurarse de hacer una correcta propagación o contención de errores, según dependa, esto último es innecesario en programas para competiciones, pero imprescindible para aplicaciones del mundo real y no hay que menospreciarlo.

• Y ahora, como demostración y ejemplo, a demás de para no convertir el título en un CLICKBAIT, voy a ir paso por paso, desde 0 resolviendo el problema de este año, haciendo las anotaciones pertinentes y consejos.

ENUNCIADO DEL PROBLEMA

Libros

Hay B libros diferentes con ID de 0 a B –1. Muchas bibliotecas pueden tener una copia del mismo libro, pero solo necesitamos escanear cada libro una vez. Cada libro se describe mediante un parámetro: la puntuación que se otorga cuando se escanea el libro.

Bibliotecas

Hay L bibliotecas diferentes con ID de 0 a L –1. Cada biblioteca se describe mediante los siguientes parámetros:

• El conjunto de libros en la biblioteca.
• El numero de días que lleva registrar la biblioteca para escanear.
• La cantidad de libros que se pueden escanear cada día desde la biblioteca una vez que la biblioteca se ha registrado.

Tiempo

Hay días D desde el día 0 hasta el día D –1. El primer registro de la biblioteca puede comenzar el día 0. D –1 es el último día durante el cual los libros se pueden enviar a la instalación de escaneo.

Registro de biblioteca

Cada biblioteca tiene que pasar por un proceso de registro antes de que se puedan enviar los libros de esa biblioteca. Solo una biblioteca a la vez puede pasar por este proceso (porque implica mucha planificación y visitas in situ a la biblioteca por parte de expertos logísticos): el proceso de registro de una biblioteca solo puede detenerse cuando no se están ejecutando otros procesos de registro. Las bibliotecas pueden registrarse en cualquier orden.

Los libros en una biblioteca se pueden escanear tan pronto como se complete el proceso de registro para esa biblioteca (es decir, el primer día inmediatamente después del proceso de registro, vea la figura a continuación). Los libros se pueden escanear en paralelo desde varias bibliotecas.

Exploración

Todos los libros se escanean en la instalación de escaneo. Todo el proceso de enviar los libros, escanearlos y devolverlos a la biblioteca ocurre en un día (tenga en cuenta que cada biblioteca tiene un número máximo de libros que se pueden escanear desde esta biblioteca por día). La instalación de escaneo es grande y puede escanear cualquier cantidad de libros por día.

Puntuación

Tú puntuación es la suma de las puntuaciones de todos los libros escaneados dentro de esos D días. Si un mismo libro es enviado por múltiples bibliotecas, solamente se sumará una vez, aunque si se envían varias la solución seguirá siendo correcta.

Este Sería el ejercicio de la Hashcode 2020, traducido al español, 90% por Google Tranlastor y 10% por mi persona. Así que...

¡EMPECEMOS!

ANÁLISIS DEL PROBLEMA

Primero, vamos a entender el problema a resolver, en este caso se trata de que hay un servicio central al que, desde diferentes bibliotecas, enviar una copia digital de los libros más valiosos posibles en un tiempo determinado. Hay que tener en cuenta que el valor de cada libro viene dado por el libro en especifico, varias bibliotecas pueden tener el mismo libro, pero solo tendrá valor la primera vez que es enviado.

Antes de que una biblioteca pueda empezar a enviar los libros necesita pasar un tiempo de registro, lo cual solo puede hacer una biblioteca a la vez y el tiempo que le lleva viene dado con la información de cada biblioteca, varias bibliotecas pueden enviar libros simultáneamente sin problemas.

Se puntuará la solución según el valor total obtenido por los libros enviados, independientemente de su cantidad, o de si hay bibliotecas que no se han registrado.

DISEÑAR LA SOLUCIÓN

Ahora que ya entendemos el problema y esta claro que debemos hacer y que no, toca pensar en como solucionarlo.

Dado que nos dan los datos en un formato de texto plano, y hay que devolverlo de la misma forma, tenemos la libertad de diseñar la estructura que usaremos a nuestra elección para hacer los cálculos. Se puede hacer de diversas formas, yo opto en este ejemplo por utilizar una lista con las propiedades del problema y una lista individual para cada biblioteca, que serán ordenadas por posición de entrada en una lista de listas.
Teniendo esto ya podemos empezar, este problema es de combinatoria, ya que lo importante es seleccionar la combinación mas optima de elementos y en que orden irá. Este problema se puede abordar con 3 enfoques, aunque uno sería una versión optimizada del otro.

• Fuerza bruta, probar todas las combinaciones validas y calcular cual es la que mayor puntaje nos daría. Esta es la menos eficiente en todos los aspectos.

• Algoritmos genéticos, utilizar soluciones al azar que al combinarse con otras soluciones usando un algoritmo de mutación y de unión generen nuevas soluciones, permitiendo a las mejores reproducirse y sobrevivir otra generación. Esta solución es ligeramente mas eficiente que la búsqueda por fuerza bruta, pero tiene el riesgo de mínimos locales.

• Solución única, en esta opción solamente calculamos una opción, cada iteración requerirá bastante mas trabajo que las otras alternativas, pero habrá bastantes menos iteraciones que calcular, siempre devolviendo la mejor solución.

Obviamente, en este caso usaremos la solución única, ya que son pocos los problemas de combinatoria que puedes aplicar este tipo de solución y que sea viable.

Pensando en esto, lo mejor es seleccionar que biblioteca obtendrá más puntos con los días que quedan disponibles, la primera biblioteca tendrá el numero total y las siguientes ese numero menos el costo de registro de las anteriores. Para calcular que biblioteca tiene prioridad, utilizaremos un algoritmo como el siguiente:

Libros_Enviables = (Dias_Restantes - Dias_Registro) * Envios_Diarios

(dentro de un bucle) Valor_Biblioteca += Valor_Libros[Libros(los n libros mas valiosos)]

Algo importante para el calculo anterior, es ordenar los libros de cada biblioteca por el valor que tiene el libro especifico antes de hacer este calculo, ordenándolos de mayor a menor valor, esto se puede hacer de diferentes formas, pero es un problema básico, así que no hace falta analizar esta parte.

Una vez obtenido esto, se guarda que librería se selecciona, con que libros, restamos a los días restantes los días de registro para la siguiente iteración y se reduce a 0 el valor de los libros ya escaneados, dado que es inútil volverlos a escanear.

Y con estoy ya estaría el algoritmo básico para obtener una solución correcta y satisfactoria.

IMPLEMENTACIÓN

En este punto ya tocaría hacer algo de código, para lo cual en este caso concreto usaré Python3, aunque se puede hacer en cualquier lenguaje de programación que se conozca. Para simplificarlo todo y porque es la parte más aburrida, voy a hacer una elipsis en la parte de cargar las variables en el programa.

Voy a utilizar los datos del caso de ejemplo, para simplificar las cosas, ya que es el dataset más pequeño.

He tenido que hacer otra elipsis durante la programación, dado que la etapa de implementación y de comprobaciones se intercalan, una vez implementada una parte se comprueba y se mejora de ser posible, así que mostraré el resultado final en el apartado de comprobaciones.

COMPROBACIONES

Uno de los detalles en los que no pensé dada la naturaleza del problema, es el caso de que sobren días, o como hacer que no se registre 2 veces la misma biblioteca manteniendo su posición en la lista, estos problemas han sido facilmente solucionables, analizando las salidas del programa a desarrollar y siguiendo una estrategia concreta, ceñirse al algoritmo planeado originalmente y si este tiene deficiencias, modificarlo antes de seguir programando. Siendo este el resultado de 1:48 horas de trabajo:

El tema en esta versión ha dejado de soportar código en formato texto, por lo que hasta que se arregle será una imagen. Lo sentimos.

Hay aún muchas mejoras que aplicar, para reducir la complejidad temporal, por ejemplo con cada iteración eliminar de una biblioteca los libros ya enviados, reduciendo el coste de reorganización de esa biblioteca, pero esto es un ejemplo de un programa funcional, que cumple todos los requisitos y que aún puede ser mejorado de considerarlo necesario.

Y bueno esto sería todo, la resolución es demasiado sencilla y he pasado mas tiempo intentando dejar el código compacto pero entendible que en su programación y diseño, lo que ha supuesto un empujón hacia arriba a mi orgullo de desarrollador.