Resolviendo el #TuentiChallenge4: Challenge 9 – Bendito Caos

Pasada la vergüenza del problema anterior, toca ahora hablar de la fiesta que se está montando en AwesomeVille y la cantidad de gente que llegará allí en una hora.

Análisis del problema

En este problema, nos dan un mapa de ciudades y las carreteras entre ellas y nos preguntan cuántas coches pueden llegar hasta AwesomeVille, desde una ciudad determinada, en una hora. También nos daban la velocidad máxima permitida para cada carretera y cuántos canales tenía cada una.

La clave para identificar cómo resolver este problema estaba en el hecho de que todas las calles estaban repletas al comenzar y no dejarían de llegar coches mientras quedase tiempo y hubiese espacio. Múltiples rutas, límite en la capacidad de las calles y nos preguntan cuál es el máximo de coches que puede entrar a un único destino: este problema era un caso de Flujo Máximo.

Los requisitos para encontrar el flujo máximo son conocer la estructura del grafo (la conocíamos, pues nos la daban explícitamente), identificar los nodos fuente y sumidero (las ciudades dadas) y la capacidad de cada arista del grafo. En la capacidad de cada arista es donde estaba la gracia del problema.

Como información nos daban, para cada carretera que uniese los puntos A y B, la velocidad máxima. Sin embargo, eso no es una capacidad. ¿Cómo sé cuantos coches caben en la carretera? ¿Qué tan larga es?

Sabemos que tenemos que calcular la cantidad máxima de coches que llegarán a AwesomeVille en una hora. Ahora supongamos que la velocidad máxima entre A y B son 100km/h. Si la carretera tiene una velocidad máxima de 100 km/h, la distancia máxima de esa carretera debe ser 100km. Si fuese más larga, el coche no llegaría a tiempo pues no puede ir más rápido. Por otro lado, sabemos que los coches tienen 4 metros de largo y que la distancia entre coches es de un metro, así que cada coche ocupa un espacio de 5 metros por coche.

Dado que las unidades son distintas, pasamos todo a metros para poder operar. Así, 100 km. se vuelven 100000 m. y la capacidad máxima de coches para esa carretera será de (100km*1000m/km)/5m/coche = 20000 coches. Por último, como siempre tendremos que multiplicar por 1000 (para pasar a metros) y dividir por 5 (para saber cuántos coches caben), para cada carretera con un límite de X km./h., la capacidad se definirá como X*(1000/5)*N = 200*X*N, donde N es el número de canales de esa carretera.

Al ser una pregunta de flujo máximo con un límite de una hora, sabemos que la carretera no podrá ser más larga (tendría mayor capacidad pero no llegarían los coches por la restricción del tiempo) ni más corta (reduciríamos la capacidad máxima de la carretera).

Una vez identificados todos los elementos de un Flujo Máximo (grafo, fuente, sumidero y capacidades) toca buscar en nuestro arsenal el algoritmo que resuelve el problema. Su nombre: Ford-Fulkerson (el enlace es a la Wikipedia en inglés pues el artículo en español no es tan completo). En el Tuenti Contest de 2011 (sí, tenía otro nombre) también hubo un problema de Flujo Máximo. En esa ocasión, comenté con dibujos y todo la idea detrás del algoritmo. Te invito a echarle un vistazo a la idea. Aquí pasaré directamente a la solución.

Solución enviada

Dado que mi solución está escrita en Python, el algoritmo de Flujo Máximo que utilicé es el que puedes encontrar en Wikipedia. Así, descaradamente. El esfuerzo estaba en determinar la capacidad y reconocer el algoritmo.

Sí le hice un cambio y es que la manera en que busco el próximo flujo disponible es con BFS en vez de DFS. Esta variación lleva el nombre de Algoritmo de Edmonds-Karp. El método find_path queda de la siguiente manera

def find_path(self, source, sink):
  queue = [ source ]
  paths = {source: []}
  while queue:
    vertex = queue.pop(0)
    for edge in self.get_edges(vertex):
      if edge.capacity - self.flow[edge] > 0 and \
          edge.sink not in paths:
        paths[edge.sink] = paths[edge.source] + [edge]
      if edge.sink == sink:
        return paths[edge.sink]
      queue.append(edge.sink)
  return None

El resto, puedes verlo en Wikipedia directamente.

Por último la parte de leer los datos del problema y crear el grafo con las capacidades, es la siguiente:

from edmondskarp import * # use the Wikipedia impl of Ford-Fulkerson
                          # with BFS to find path

cities = int(raw_input())
r = 0
for c in range(cities):
  g = FlowNetwork()

  city_name = raw_input()
  normal_speed, dirt_speed = map(int,raw_input().split(' '))
  speeds = {'normal': normal_speed, 'dirt': dirt_speed} # a dict for easier access
  intersections, roads = map(int,raw_input().split(' '))

  for r in range(roads):
    node_from, node_to, road_type, lanes = raw_input().split(' ')

    # do not add a node twice
    if not node_from in g.get_vertex(): g.add_vertex(node_from)
    if not node_to in g.get_vertex(): g.add_vertex(node_to)

    capacity = 200*speeds[road_type]*int(lanes)
    g.add_edge(r, node_from, node_to, capacity)

  print city_name, g.max_flow(city_name,'AwesomeVille')

Entre las soluciones de los compañeros. Mis favoritas son la Leo, escrita en Python y la de Gerard, también en Python, pues reutilizan librerías externas (or-tools y NetworkX respectivamente) para el flujo máximo, lo cual es una mejor alternativa a copiar y pegar código (que fue lo que hice yo). Gerard organiza el código con demasiadas clases para mi gusto, dado que estábamos en una competencia, pero es una forma de trabajar muy valiosa si la practica también en lo laboral. El resultado es un código bien organizado y legible.

Y tú, ¿cómo lo resolviste?

Deja un comentario