Resolviendo el #TuentiChallenge4: Problema 1 – Anonymous Poll

Hola.

Luego de tres años, he vuelto a participar en la competencia anual de Tuenti. Ahora iré publicando mis soluciones a los problemas que resolví. La idea es presentarlo de una forma didáctica, de manera que todo aquel que esté aprendiendo a programar pueda aprovechar al máximo el análisis y los razonamientos. Si quieres echarle un vistazo a mis soluciones del #TuentiContest de 2011, también puedes hacerlo.

Ahora sí, sin más preámbulos el Problema 1.

En este problema nos daban una lista de nombres de estudiantes y cada nombre venía acompañado de las características del estudiante: género, edad, estudios y año académico. Luego el problema nos pedía, dado un conjunto de características, listar todos los estudiantes que cumplieran con estos criterios.

Análisis del problema

A rasgos generales, lo que nos pedían es crear un directorio de estudiantes que pudiera consultarse según sus características. Las claves de este problema fueron tres:

  1. Siempre nos daban las cuatro características de un estudiante.
  2. El resultado final debía ser una lista con estudiantes que poseyeran todas.
  3. Las características nos las daban exactamente en el mismo orden que en la lista de estudiantes.

Con estas condiciones, el problema entonces se reducía a tomar el conjunto de cuatro características de cada estudiante como las claves de un diccionario y llenar cada entrada del diccionario con todos los estudiantes que coincidieran. Finalmente, el resultado vendría dado por una búsqueda en dicho diccionario.

Solución enviada

El algoritmo que he descrito antes puede hacerse en muy pocas líneas en cualquier lenguaje: Python, C++, Java, C#, etc. Yo en cambio he decidido presentar un script de bash, para practicar con las herramientas de Linux. En concreto, he usado grep, cut, sort, tr, xargs y sed.

grep – programa que busca subcadenas de caracteres en un archivo de texto. Lo uso para buscar todas las líneas (estudiantes) que coincidan con las características solicitadas.

cut – luego de encontrada una línea válida, solo necesitamos el nombre del estudiante. Cut es el programa que extrae solo esa información.

sort – Para ordenadas lexicográficamente la lista de estudiantes obtenida hasta ahora

tr – este es un programa que “traduce” caracteres, es decir, sustituye unos caracteres por otros. Como hasta ahora tenemos una línea por estudiantes, tr sustituye el salto de línea por la coma, para tener la lista en una sola línea

xargs – este programa tiene infinidad de usos. Su finalidad es utilizar los parámetros que recibe de entrada como argumentos para ejecutar el programa que queramos. En mi solución, recibe la lista de estudiantes y las usa para escribirlas justo después de escribir el encabezado de cada solución “Case #Ti: ”

sed – sed es un tr en esteroides. Realiza transformaciones de texto utilizando expresiones regulares. En mi caso lo utilicé para sustituir la lista vacía por la palabra NONE (requerimiento del problema) y para eliminar la coma al final de una lista de estudiantes (que aparecía por el reemplazo de tr).

El código es el siguiente:

T=0
while read line; do
 if [ $T -gt 0 ]; then # ignore first line
 grep "$line" $1 |\
 cut -d, -f1 |\
 sort |\
 tr '\n' ',' |\
 xargs echo "Case #$T:" |\
 sed -re 's/:$/: NONE/g' \
      -e 's/,$//g'
 fi
 T=$(($T+1))
done

¿Qué te parece la solución? Entre las soluciones de los compañeros, Guillermo ofrece una aproximación más compacta aun que incluso puede adaptarse a un tweet, usando “paste” en vez de “tr” y otros trucos más. Me encanta.

Deja un comentario