Introdução

Minha sobrinha quer fazer uma pista de corrida. Ela tem peças de madeira que se encaixam para formar a pista. Cada parte é quadrada e contém uma forma diferente. Usarei os caracteres de desenho de tubo para ilustrar:

• │: a estrada que segue verticalmente
• ─: a estrada que percorre horizontalmente
• ┌ ┐ └ ┘: as estradas que viram em uma direção
• ┼: Uma ponte com passagem subterrânea

Curiosamente, não existem peças do entroncamento.

Aqui está um exemplo de uma possível pista de carro de corrida:

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

As regras para uma pista de corrida válida são as seguintes:

• Não pode haver estradas que não levam a lugar nenhum.
• Ele deve formar um loop (e todas as peças devem fazer parte do mesmo loop).
• Nas pontes / passagens inferiores, você não pode virar (então você precisa passar direto por elas).

Infelizmente, as peças de pista de corrida que eu e minha sobrinha são limitadas. Mas definitivamente queremos usar todos eles na pista. Escreva um programa que, dada uma lista de quais peças estejam em nosso inventário, produza uma pista de carro de corrida que use todas essas peças.

Descrição da entrada

Gostaríamos que a entrada chegasse via STDIN, argumentos de linha de comando, leitura de arquivo ou uma função de entrada do usuário (como raw_inputou prompt). A entrada é números inteiros positivos separados por vírgula no formato

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

onde cada um deles representa a quantidade daquela peça em particular que temos. Então, por exemplo, a entrada:

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

significaria que tínhamos um de cada peça.

Descrição da saída

Crie uma pista de carro de corrida usando os caracteres de desenho de tubo listados acima. A pista de corrida deve usar exatamente o número de cada peça especificada na entrada - nem mais nem menos. Haverá pelo menos uma pista de carro de corrida válida para cada entrada.

Exemplo de entradas e saídas

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

Uma saída possível:

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

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

Uma saída possível:

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

Ruby 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 não é o programa mais curto que eu poderia criar, mas sacrifiquei alguma brevidade pela velocidade de execução.

Você pode experimentar o programa aqui . Observe que o ideone possui um limite de tempo de execução; portanto, para entradas que consistem em mais de 12 partes, o programa provavelmente expirará.

Há também uma suíte de testes para o programa. Observe que os dois últimos testes estão desativados no ideone, devido ao limite de tempo mencionado acima. Para ativar esses testes, exclua o x_prefixo de seus nomes.

O programa encontra uma solução usando a pesquisa Depth first; coloca peças uma de cada vez e mantém registros de pontas soltas. A pesquisa é interrompida quando não há mais pontas soltas (não conectadas) e todas as peças foram colocadas.

Este é o programa não destruído:

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))
}