Atención: No leer sin antes haber realizado el problema "señales y patrones".
Seguramente la dificultad media del problema de "señales y patrones" haya supuesto un plus de motivación para los que os enfrentásteis a problemas anteriores. Sin embargo es muy probable que os haya parecido más sencillo que problemas anteriores. Y es que este problema no ha envejecido bien. En los años 90, la manipulación de estructuras de datos era uno de los problemas que normalmente se resolvían desde cero. Era frecuente que los programadores fueran desarrollando sus propias bibliotecas que manipularan cadenas, listas, conjuntos, etc. En la actualidad esta funcionalidad ya viene ofrecida de serie en la mayoría de los lenguajes orientados a objetos. Esto hace que con muy poco esfuerzo podamos ofrecer una solución a este problema que en otro tiempo nos hubiera consumido más energías.
A pesar de esta simplificación tan enorme del problema de trabajar con estructuras de datos complejas, el soporte ofrecido por las bibliotecas estándar para la manipulación, búsqueda y filtrado de información casi siempre ha sido escaso. Últimamente y a raíz de la moda de crear lenguajes específicos de dominio (en inglés, DSLs) se han diseñado APIs que permiten la manipulación de datos desde código.
Un DSL, es un lenguaje que se diseña para construir aplicaciones para un dominio muy concreto, en contraposición a los lenguajes de propósito general como Java o C que permiten crear múltiples tipos de aplicaciones. Tal vez el DSL más utilizado en la actualidad sea el lenguaje de consultas SQL. Para cualquier persona que sepa un mínimo de inglés puede resultar muy natural el lenguaje utilizado, que facilita la comprensión del código fuente escrito. Existen otros lenguajes como pueden ser ANTLR, que genera parsers capaces de interpretar un lenguaje (herramienta muy utilizada para crear otros DSLs), el lenguaje R, utilizado para computación estadística, o el propio lenguaje HTML para la presentación de información en navegadores.
Crear un DSL implica la definición de las estructuras léxicas, sintácticas y semánticas, que deben implementarse en herramientas capaces de interpretarlas y ejecutarlas. Esto supone un esfuerzo importante que en ocasiones no es suficientemente rentable. Es por ello que surgen lo que se denominan DSL internos, que utilizan las estructuras que ofrecen otros lenguajes para facilitar la creación de un tipo determinado de aplicaciones. Para crear un DSL interno tan solo es necesario definir métodos que permitan encadenar varias llamadas en una sola instrucción. Basta con jugar con saltos de línea y tabulados para mejorar la legibilidad del código y que aquello parezca un DSL.
La biblioteca Guava de Google ya incorporaba estos conceptos desde sus inicios y la versión 8 de Java también se ha sumado a esta moda. En Java 8 se ha incorporado entre sus novedades un DSL interno que permite manipular cualquiera de las estructuras de datos estándar a través de un nuevo tipo de estructura denominado Stream
. He aquí una pequeña muestra de lo que se puede hacer con esta DSL:
listOfPersons .stream() .filter(e -> e.getGender() == Person.Sex.FEMALE) .forEach(e -> System.out.println(e.getName()));
El código anterior filtra una lista de personas, extrayendo únicamente las mujeres y escribiendo su nombre por pantalla. Aunque no sepas nada sobre esta API, es fácil entender su funcionalidad de un vistazo rápido. ¿Y por qué hablo hoy de esto? Pues porque he visto varias soluciones que utilizan de forma incorrecta las DSLs que ofrecen tanto Guava como Java 8. Un par de ejemplos de mal uso:
Lists.newArrayList(Ordering.natural().reverse().sortedCopy(map.values()));
Map<String,Integer> result = new HashMap<String,Integer>(); frecuencyMap.entrySet().stream() .sorted((e1, e2) -> e2.getValue().compareTo(e1.getValue())).limit(topRank) .forEach(e -> result.put(e.getKey(), e.getValue()));
La reacción que tuve al leer ambas líneas de código fue la misma: bofetada visual. Y todo por no ordenar convenientemente las líneas de código. Estas formas de ordenar el código son mucho más legibles:
Lists.newArrayList( Ordering.natural().reverse(). sortedCopy(map.values()) );
Map<String,Integer> result = new HashMap<String,Integer>(); frecuencyMap.entrySet().stream() .sorted((e1, e2) -> e2.getValue().compareTo(e1.getValue())) .limit(topRank) .forEach(e -> result.put(e.getKey(), e.getValue()));
Y si ya lo acompañamos de comentarios, eso es la releche. Los programadores solitarios que cuando evitan escribir comentarios piensan que el código fuente sólo lo van a leer ellos, están cometiendo un atropello con su "yo del futuro". Y es que cualquier programador con poca experiencia seguro que se ha encontrado con ese momento en el que te preguntas "¿de verdad he escrito yo eso?", "¿en qué momento de enfermedad mental se me ocurrió escribirlo?". Y es ahí donde echas en falta un poco de cariño en la redacción de comentarios útiles, el uso de nombres de variables y métodos comprensibles, uso de tabulados y retorno de carro, etc.
La estructura tan particular de las DSLs internas siempre me han evocado a la diosa griega más maltratada del mundo de la informática: Demeter. Esta diosa dio nombre al grupo de investigación que propuso la citada Ley de Demeter, la ley que más programadores se pasan por el arco del triunfo digital. Te la resumo en un ejemplo sencillo:
// ¡¡¡ no hagas esto nunca !!! objeto.llamadaQueDevuelveObjeto().llamadaAMetodo();
¿Qué problemas trae esto? Pues que si la llamada intermedia devuelve null
, tenemos una excepción como un templo. "No, pero eso no me pasa a mí, esto nunca devuelve null". También el sueldo de los funcionarios era intocable y 4 bajadas que llevamos ya. Aparta la soberbia y piensa que tu código siempre puede fallar. En lugar de lo anterior escribe esto:
// ¡¡¡ Me siento seguro !!! if (objeto != null) { OtroObjeto otroobjeto = objeto.llamadaQueDevuelveObjeto(); if (otroObjeto != null ) { otroObjeto.llamadaAMetodo(); } }
Este código cumple con la citada ley, evita problemas y además facilita la depuración y ejecución paso a paso del código. Un código compacto no sirve para nada si falla. ¿Alguna vez has pensado qué beneficio trae escribir poco a la hora de programar? Ninguno. Utiliza nombres largos en los métodos y atributos, que los compiladores actuales autocompletan a medida que escribes. Un nombre largo no hace que el código resultante rinda mejor o peor, que eso los compiladores ya lo tienen muy estudiado. Abusa de las llaves aunque puedas evitarlas porque el if sólo tiene una línea, que el día que una línea se convierta en dos te arrepentirás. Y sobre todo, haz honor a la ley de Demeter, que en el fondo es buena gente.
Y te estarás preguntando "Y si yo tengo que cumplirla, ¿por qué ellos no?". Échale un vistazo al mecanismo de refactorización Null Object y sé creativo. Tal vez entiendas una de las técnicas más importantes en el diseño de DSLs internas y podrás ignorar a Demeter, aunque sea solo un poquito.
Pablo Trinidad 26 octubre, 2014
Posted In: Aprendiendo algoritmia, Tecnologería
En los viejos tiempos a los que se refiere el problema, y dado que la longitud máxima de código (B) está acotada en el problema original (a 12), es el típico que se hubiera podido resolver usando una tabla en memoria para la primera parte y recolección+quicksort para la segunda. El gran problema era el manejo de la memoria, más que otra cosa 🙂
Puedes convertir cada posible patrón a un número binario único poniéndole un 1 como prefijo, así un patrón de longitud L corresponde a un número binario de longitud (nº de cifras significativas) igual a L+1. En este caso, puedes identificar cada patrón con L <= 12 con un número binario entre 2 (0b10, patrón "0") y 2^13-1 = 8191 (0b11111 11111111, patrón doce unos). Después te haces un anillo de largo B al que vas empujando caracteres de uno en uno y vas añadiendo uno a todas las "celdillas" de la tabla que tengan un código que corresponda al contenido del anillo (bien al anillo completo, bien a la "cola" de largo A o superior). La mayor complicación es que necesitas 3 bytes por patrón, dado que en el problema original el fichero de entrada podía tener hasta 2 megas, luego en potencia un mismo patrón puede repetirse 2^21 veces (pensemos en un fichero con todo ceros y A=1). Para finalizar, recorres la tabla, mandas cada patrón distinto de cero a un array, y ordenas el array usando como criterio el número de repeticiones. Todo cabe en 64kb. Desde luego que conceptualmente el problema tiene poco que ver con la solución que se le da con un lenguaje mínimamente más moderno.
Estuve curioseando los problemas de la convocatoria aquella de la IOC y me gustó mucho el de las lucecitas, un problema inabarcable por fuerza bruta pero que prácticamente se puede resolver con lápiz y papel.
Respecto a lo de Démeter, todo eso está muy bien pero es bien sabido que en cuanto hay presión de tiempo esas son las primeras cosas que se caen... así que para entrenar ese tipo de prácticas es mejor que el ejercicio sea la implementación y no también el análisis 😛
Efectivamente el trabajar con la presunción de recursos infinitos con la que se trabaja hoy en día simplifica mucho la situación. Si bien lo que propones es una mejora en el uso de memoria, se puede ir un poco más allá con la estructura de datos más eficiente para este caso: el trie. Si a esto le sumamos algo de compresión según el algoritmo de Huffman ya la liamos del todo. Échale un vistazo a este artículo que guardaba en el cajón para estas ocasiones 😉
En cuanto a Demeter, la metodología TDD considera la presión por tiempo y entrega. Primero debe funcionar a toda costa. Luego debe refactorizarse para higienizar el código. Y normalmente la refactorización elimina errores. Si no se hace, los errores se acumulan, aumenta la deuda técnica y por tanto las posibilidades de una implosión de magnitudes galácticas. Hay que combatir el síndrome de Diógenes informático de ir acumulando mierda en el código.
Le echaré un vistazo a las lucecitas a ver si lo incorporo a mi catálogo de problemas 😀