Resolviendo el #TuentiChallenge4: Challenge 2 – F1 – Bird’s-eye Circuit

Si algo hay que reconocerle a los organizadores, es que los planteamientos de los problemas son originales. En el problema 2 nos pedían dibujar una pista de Fórmula 1 vista desde arriba, a vuelo de pájaro, como si fuera un mapa de Mario Kart :)

Análisis del problema

La entrada consistía en una línea de caracteres, cada uno con un significado: seguir recto, girar a la izquierda o a la derecha y un carácter especial para indicar el punto de partida/llegada. Es como si alguien nos diera una dirección paso a paso “sigue recto tantas calles, luego gira a la derecha y sigue tantas calles más, luego giras a la izquierda, …” y nosotros teníamos que mostrarlo en 2D.

Mi estrategia fue entonces representar la pista con una matriz de caracteres con el tamaño justo. Para ello, necesitaba saber cuál era el tamaño de esa matriz y cuál era la posición del primer carácter de la secuencia en dicha matriz. Con esa información, podía ubicarme en la posición correspondiente y simplemente seguirle el trazo a cada paso del mapa.

Por la forma en que planteé el problema, debía recorrer la secuencia de caracteres dos veces: la primera, para determinar tamaño y posición la segunda para pintar el mapa.

Solución enviada

Mi solución fue escrita en Python. Me gusta porque me llevó menos de 70 líneas de código (94 en total con los comentarios), lo cual, considerando que trato dos veces la entrada, me parece un tamaño aceptable.

El primero de los métodos era el que calculaba el tamaño del mapa y la posición del primer carácter. Para ello, uso dos variables dx y dy que irían creciendo/decreciendo según la descripción del mapa (dx crece a la derecha, dy crece hacia abajo). Cada vez que las variables se actualizaban, actualizaba también sus valores mínimo y máximo.

Con los valores mínimo y máximo y sabiendo que el primer carácter tenía el valor (0,0), podemos calcular la posición relativa considerando el origen arriba y a la izquierda y el ancho y alto del mapa.

def compute_size(track):
  '''compute_size(str) -> (row,column,width,height)
 
  Given a track, compute the position of the first character and
  the track's width and height
  '''
  (min_dx, min_dy, max_dx, max_dy) = (0, 0, 0, 0)

  horizontal = True # asume first character horizontal
  forward = True # asume first character going forward
  (dx,dy) = (-1,0) # keeps the current position in the map
                   # dx begins at -1 to make the first character's position 0

  for char in track:
    if horizontal and forward: dx += 1
    elif horizontal and not forward: dx -= 1
    elif not horizontal and forward: dy += 1
    else: dy -= 1

    min_dx = min(min_dx,dx)
    min_dy = min(min_dy,dy)
    max_dx = max(max_dx,dx)
    max_dy = max(max_dy,dy)

    if char == '/': forward = not forward # left and up means backwards
    if char == '/' or char == '\\': horizontal = not horizontal # change of orientation

  return (0-min_dy, 0-min_dx, max_dx-min_dx+1, max_dy-min_dy+1)

Una vez calculado el tamaño y la posición deseada, el segundo método creaba una matriz con el tamaño adecuado y la llenaba de espacios en blanco. Luego me ubicaba en la posición del primer carácter e iba escribiendo uno a uno siguiendo la dirección dada por la pista.

def prettify(track, row, column, width, height):
  '''prettify(str, int, int, int, int) -> returns a 2D representation '''
  track_grid = [list(repeat(' ',width)) for i in range(height)] # creates an empty track

  (i,j) = (row,column) # move cursor to first character's position
  orientation = '-' # assume first orientation horizontal
  forward = True # assume first orientation forward
  for char in track:
    # first determine which character is to be set
    cur_char = ' '
    if char == '/' or char == '\\': # change of orientation
      if orientation == '-': orientation = '|'
      else: orientation = '-'
      cur_char = char
    elif char == '-':
      cur_char = orientation
    elif char == '#':
      cur_char = char
    track_grid[i][j] = cur_char 

    # then update orientation and direction accordingly
    if char == '/': forward = not forward
    if forward:
      if orientation == '-': j+=1
      else: i+=1
    else:
      if orientation == '-': j-=1
      else: i-=1 

  return track_grid

Mi solución tiene dos puntos de mejora importantes. El primero es que es posible resolver el problema sin pre calcular el tamaño y la posición inicial. Entre las soluciones de los otros participantes, pueden encontrar varias formas de hacerlo.

La segunda optimización es al principio del método que pinta la pista. En la línea 3 creo una matriz vacía con las dimensiones indicadas y luego la lleno. Pude haber creado simplemente la primera fila e ir añadiendo filas hacia abajo y hacía arriba conforme creaba el mapa. Esto iría en línea con lo primera optimización, y es que en definitiva, habían maneras de ir ampliando el mapa conforme se leía por primera vez.

Sin embargo, la solución como tal me parece legible y creo que aporta algo que es muy importante sobre todo para quienes se inician en la programación (y que luego con la experiencia puedes ir ajustando a cada necesidad): poder separar un problema en sub problemas más pequeños que sea fáciles de atacar.

Para finalizar, le he echado un vistazo a las soluciones de los compañeros y las que más me han gustado han sido la de Pedro y la de @Dark_eye9.

La primera, porque aprovecha el defaultdict para representar la pista (en vez de una matriz tradicional), con lo cual el lenguaje resolvía por él las casillas vacías ¡muy ingenioso! Me lo apunto en mi repertorio de herramientas (aun me queda mucho por aprender de las librerías de Python).

La segunda solución porque está hecha en bash y eso para mí, es siempre digno de aplausos.

¿Qué opinas? ¿Te ha gustado mi solución?

7 thoughts on “Resolviendo el #TuentiChallenge4: Challenge 2 – F1 – Bird’s-eye Circuit

  1. Gracias por la mención, de verdad! Pero la pena es que mi versión en BASH del reto hace uso de los caracteres de escape ANSI para la consola. Característica que no detecta el script de submit de tuenti, y por eso lo recodifiqué en PHP.

    Podía haber implementado mi solución de array 2d que hice en PHP, pero se puede decir que he aprendido BASH en un curso intensivo de una semana y patrocinado por Tuenti, así que para cuando iba por el ejercicio 2 aún no sabía mucho 😉

    Execelente blog!

  2. Yo he optado por hacerlo en C++. Para la parte de “no guardar espacios en blancos” la solución por la que opté fue un “map”. Tiene el problema de la inserción de orden logarítmico, pero si está balanceado y se utilizaran los iteradores para aprovechar la posición previa (ya que la “función” -carretera- es continua) no hay problema; y para la representación también se puede linealizar el “map”.

Deja un comentario