Introducción

Mi sobrina quiere hacer una pista de autos de carrera. Ella tiene partes de madera que encajan entre sí para formar la pista. Cada parte tiene forma cuadrada y contiene una forma diferente. Usaré los caracteres de dibujo de tubería para ilustrar:

• │: el camino que va verticalmente
• ─: el camino que va horizontalmente
• ┌ ┐ └ ┘: los caminos que giran en una dirección
• ┼: Un puente con un paso subterráneo

Curiosamente, no hay piezas de unión en t.

Aquí hay un ejemplo de una posible pista de carreras:

┌─┐
│ │┌─┐
│ └┼─┘
└──┘

Las reglas para una pista de autos de carrera válida son las siguientes:

• No puede haber ningún camino que vaya a ninguna parte.
• Debe formar un bucle (y todas las piezas deben ser parte del mismo bucle).
• En los puentes / pasos subterráneos, no puede girar (por lo que debe atravesarlos directamente).

Desafortunadamente, las piezas de la pista de autos de carrera que mi sobrina y yo tenemos son limitadas. Pero definitivamente queremos usarlos todos en la pista. Escriba un programa que, dada una lista de las piezas que están en nuestro inventario, genere una pista de autos de carrera que use todas esas piezas.

Descripción de entrada

Nos gustaría que la entrada ingrese a través de STDIN, argumentos de línea de comandos, lectura de archivos o una función de entrada de usuario (como raw_inputo prompt). La entrada es enteros positivos separados por comas en la forma

│,─,┌,┐,└,┘,┼

donde cada uno de ellos representa la cantidad de esa pieza en particular que tenemos. Entonces, por ejemplo, la entrada:

1,1,1,1,1,1,1

significaría que teníamos una de cada pieza.

Descripción de salida

Salida de una pista de carreras de coches utilizando los caracteres de dibujo de tubería enumerados anteriormente. La pista de autos de carrera debe usar exactamente el número de cada pieza especificada en la entrada, ni más ni menos. Habrá al menos una pista de carrera válida para cada entrada.

Ejemplo de entradas y salidas

Entrada: 3,5,2,2,2,2,1

Una posible salida:

┌─┐
│ │┌─┐
│ └┼─┘
└──┘

Entrada: 0,0,1,4,4,1,3

Una posible salida:

 ┌┐
 └┼┐
  └┼┐
   └┼┐
    └┘

Rubí 664 671 677 687 701 (678 bytes)

_={│:[1,4],─:[2,8],┌:[4,8],┐:[4,2],└:[1,8],┘:[1,2],┼:[1,4,2,8]}
s=->a,l,b{l==[]&&a==[]?b:(l.product(l).any?{|q,r|q,r=q[0],r[0];(q[0]-r[0])**2+(q[1]-r[1])**2>a.size**2}?!0:(w,f=l.pop
w&&v=!a.size.times{|i|y=_[x=a[i]]
f&&y&[f]==[]||(k=l.select{|p,d|w!=p||y&[d]==[]}
(y-[f]).map{|d|z=[w[0]+(d<2?-1:(d&4)/4),w[1]+(d==2?-1:d>7?1:0)]
g=d<3?d*4:d/4
b[z]?_[b[z]]&[g]!=[]||v=0:k<<[z,g]}
v||r=s[a[0...i]+a[i+1..-1],k,b.merge({w=>x})]
return r if r)}))}
c=eval"[#{gets}]"
r=s[6.downto(0).map{|i|[_.keys[i]]*c[i]}.flatten,[[[0,0],nil]],{}]
h=j=k=l=0
r.map{|w,_|y,x=w
h>x&&h=x
j>y&&j=y
k<x&&k=x
l<y&&l=y}
s=(j..l).map{|_|' '*(k-h+1)}
r.map{|w,p|y,x=w
s[y-j][x-h]=p.to_s}
puts s

Este no es el programa más corto que se me ocurrió, pero sacrifiqué algo de brevedad por la velocidad de ejecución.

Puedes experimentar con el programa aquí . Tenga en cuenta que ideone tiene un límite de tiempo de ejecución, por lo que para las entradas que constan de más de aproximadamente 12 piezas, el programa probablemente expire.

También hay un conjunto de pruebas para el programa. Tenga en cuenta que las dos últimas pruebas están deshabilitadas en ideone, debido al límite de tiempo mencionado anteriormente. Para habilitar estas pruebas, elimine el x_prefijo de sus nombres.

El programa encuentra una solución usando la búsqueda de profundidad primero; coloca las piezas de una en una y mantiene huellas de cabos sueltos. La búsqueda se detiene cuando no hay más extremos sueltos (desconectados) y todas las piezas han sido colocadas.

Este es el programa sin golf:

N, W, S, E = 1, 2, 4, 8

# given a direction, find the opposite
def opposite (dir)
  dir < 3 ? dir * 4 : dir / 4
end

# given a set of coordinates and a direction,
# find the neighbor cell in that direction
def goto(from, dir)
  y, x = from

  dx = case dir
  when W then -1
  when E then 1
  else 0
  end

  dy = case dir
  when N then -1
  when S then 1
  else 0
  end

  [y+dy, x+dx]
end

CONNECTIONS = {
  ?│ => [N, S],
  ?─ => [W, E],
  ?┌ => [S, E],
  ?┐ => [S, W],
  ?└ => [N, E],
  ?┘ => [N, W],
  ?┼ => [N, S, W, E], 
}

BuildTrack =-> { 
  piece_types = CONNECTIONS.keys
  piece_counts = gets.split(?,).map &:to_i

  pieces = 6.downto(0).map{|i|piece_types[i]*piece_counts[i]}.join.chars

  def solve (available_pieces, loose_ends=[[[0,0],nil]], board={})

    return board if loose_ends==[] and available_pieces==[]

    # optimization to avoid pursuing expensive paths
    # which cannot yield a result.
    # This prunes about 90% of the search space
    c = loose_ends.map{ |c, _| c }
    not_enough_pieces = c.product(c).any? { |q, r| 
      ((q[0]-r[0])**2+(q[1]-r[1])**2) > available_pieces.size**2
    }
    return if not_enough_pieces

    position, connect_from = loose_ends.pop

    return unless position

    available_pieces.size.times do |i|
      piece = available_pieces[i]

      remaining_pieces = available_pieces[0...i] + available_pieces[i+1..-1]

      piece_not_connected_ok = connect_from && CONNECTIONS[piece] & [connect_from] == []
      next if piece_not_connected_ok

      new_loose_ends = loose_ends.select  { |pos, dir| 
        # remove loose ends that may have been 
        # fixed, now that we placed this piece
        position != pos || CONNECTIONS[piece] & [dir] == []
      }

      invalid_placement = false

      (CONNECTIONS[piece]-[connect_from]).map do |dir|
        new_pos = goto(position, dir)
        new_dir = opposite(dir)

        if board[new_pos]
          if CONNECTIONS[board[new_pos]] & [new_dir] != []
            # do nothing; already connected
          else
            # going towards an existing piece
            # which has no suitable connection
            invalid_placement = true
          end
        else
          new_loose_ends << [new_pos, new_dir]
        end
      end

      next if invalid_placement

      new_board = board.merge({position => piece})

      result = solve(remaining_pieces, new_loose_ends, new_board)
      return result if result
    end
    nil
  end

  def print_board board
    min_x = min_y = max_x = max_y = 0

    board.each do |position, _|
      y, x = position
      min_x = [min_x, x].min
      min_y = [min_y, y].min
      max_x = [max_x, x].max
      max_y = [max_y, y].max
    end

    str = (min_y..max_y).map{|_|
      ' ' * (max_x - min_x + 1)
    }

    board.each do |position, piece|
      y, x = position
      str[y-min_y][x-min_x] = piece
    end
    puts str
  end

  print_board(solve(pieces))
}