Calculo mejor equipo gran dt

En otro blog que tengo, estuve mostrando algunos cálculos realizados sobre los resultados del GranDT . En el último post calculé cuales serían los equipos ideales de la primera fecha y recibí un comentario preguntándome si podía publicar el programa con el que los había calculado, así que lo voy a hacer acá, junto con una pequeña explicación.

Antes que nada me disculpo por el programa, no es mucho más que un script Ruby, hecho medio a los apurones, asi que el estilo no es gran cosa y le vendría bien un refactoring.

En el Gran DT uno juega armando un equipo de f'utbol con jugadores reales de la primera división del fútbol argentino. En cada fecha cada uno de esos jugadores recibe un puntaje (basado en la calificación de periodistas, goles convertidos, etc.) y el equipo que suma más puntos gana. Los equipos no pueden formar de cualquier manera sino que tienen que respetar 3 condiciones: tener 1 arquero, 4 defensores, 4 mediocampistas y 2 delanteros, no tener más de 3 jugadores del mismo club real y además que la suma de las cotizaciones de los integrantes ( de acuerdo a una tabla proporcionada por el juego ) no supere los 60 millones.

Lo que queremos hacer es calcular que combinación de jugadores formarían el equipo que hubiera sumado la mayor cantidad de puntos en una fecha dada. La dificultad está en que no basta con buscar los jugadores que más puntos sumaron en cada puesto porque podría pasar que fuera imposible formar un equipo con esos jugadores porque no se cumpliría con las restricciones  de presupuesto o con la de no tener más de 3 jugadores del mismo equipo.

Estos problemas generalmente se atacan con la técnica de backtracking, que consiste básicamente en ir probando todas las combinaciones posibles hasta hallar la mejor, aunque descartando muchas de las posibles combinaciones basándonos en propiedades conocidas del problema. 

Veamos primero que pasa si intentamos probar directamente todas las combinaciones posibles (lo que sería buscar por fuerza bruta). En la primer fecha del torneo que se tuvo en cuenta para el Gran DT jugaron 18 arqueros, 75 defensores, 97 volantes y 43 delanteros. Por lo tanto, dadas las restricciones de posiciones de los jugadores, la cantidad de combinaciones que deberíamos revisar antes de definir cual es el mejor equipo son:

     18 x 75 x 74 x 73 x 72 x 97 x 96 x 95 x 94 x 43 x 42 = 78855686497857024000

Es un número tan grande que aún si pudieramos calcular 100000 equipos por segundo, necesitaríamos más de 2 millones y medio de años para terminar nuestras cuentas.

No tenemos tanto tiempo, así que vamos a tener que buscar alguna manera de achicar la cantidad de combinaciones posibles. En primer lugar, es interesante ver que muchos de los jugadores no tienen ninguna posibilidad de estar en el equipo ideal. Por ejemplo, Gracián, de Boca (lo elegí al azar, no es solo porque yo sea hincha de River). Gracián cuesta 4.5 millones e hizo 4 puntos, mientras que muchos jugadores que cuestan mucho menos que eso sumaron más puntos. El algoritmo general para descartar un jugador es que haya N jugadores que jueguen en su misma posición y que cuesten menos y hayan hecho los mismos puntos o más en la fecha, donde N es 4 para volantes y defensores,  2 para delanteros y 1 para arqueros, por la cantidad de puestos disponibles para cada una de estas posiciones. Descartando los jugadores que caen en estas condiciones tenemos 4 arqueros, 16 defensores, 13 volantes y 7 delanteros, con lo que la cantidad de combinaciones a considerar cae mucho:

  4 x 16 x 15 x 14 x 13 x 13 x 12 x 11 x 10 x 7 x 6 = 125924198400

Si pudiéramos procesar 100000 equipos por segundo, terminaríamos en 15 días. No voy a negar que es más razonable que dos millones y medio de años, pero todavía es muy lento, sobre todo considerando que 100000 equipos por segundo es una velocidad muy poco probable.

Por lo tanto, tenemos que bajar las combinaciones y la manera de hacer eso es no terminar de calcular aquellos equipos que no tengan chances de ser el ideal. Por ejemplo si estamos en la mitad del procesamiento de un equipo y vemos que no es válido (por ejemplo por tener mas de 3 jugadores del mismo club o costar más de 60 millones) ya podemos suspender el procesamiento de ese equipo. El otro criterio que se usa en el programa es el siguiente: supongamos que ya tenemos un equipo candidato a ser el mejor de la fecha, con 110 puntos. Supongamos además que estamos terminando de calcular otro equipo al que solo nos falta agregarle el arquero y que tiene hasta ahora 90 puntos. Si el mejor arquero de la fecha hubiera hecho 10 puntos, no vale la pena seguir con el cálculo, ya que es imposible que este equipo llegue a ser mejor que el candidato. La misma idea se puede extender calculando antes de empezar cuanto sumaría la mejor defensa, mediocampo o delantera.

   

Con todo esto la velocidad mejora muchisimo y el calculo se puede hacer en menos de un minuto (lo cual es toda una mejora contra 2500000 años... .

Si le interesa el código, lo pueden tomar aquí