introduction

Ma nièce veut faire une piste de course. Elle a des pièces en bois qui s'assemblent pour former la piste. Chaque pièce est de forme carrée et contient une forme différente. Je vais utiliser les caractères de dessin de tuyau pour illustrer:

• │: la route qui va verticalement
• ─: la route qui va horizontalement
• ┌ ┐ └ ┘: les routes qui tournent dans une direction
• ┼: Un pont avec un passage souterrain

Curieusement, il n'y a pas de pièces de jonction en T.

Voici un exemple de piste de course possible:

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

Les règles pour une piste de course automobile valide sont les suivantes:

• Il ne peut y avoir de routes qui ne mènent nulle part.
• Il doit former une boucle (et toutes les pièces doivent faire partie de la même boucle).
• Aux ponts / passages souterrains, vous ne pouvez pas tourner (vous devez donc les traverser directement).

Malheureusement, les morceaux de piste de voiture de course que ma nièce et moi avons sont limités. Mais nous voulons vraiment les utiliser tous sur la piste. Écrivez un programme qui, étant donné une liste des pièces qui sont dans notre inventaire, génère une piste de voiture de course qui utilise toutes ces pièces.

Description de l'entrée

Nous aimerions que l'entrée entre via STDIN, des arguments de ligne de commande, la lecture de fichier ou une fonction d'entrée utilisateur (comme raw_inputou prompt). L'entrée est des entiers positifs séparés par des virgules sous la forme

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

où chacun représente le montant de cette pièce particulière que nous avons. Ainsi, par exemple, l'entrée:

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

signifierait que nous avions un de chaque morceau.

Description de la sortie

Sortez une piste de course en utilisant les caractères de dessin de tuyaux répertoriés ci-dessus. La piste de course devrait utiliser exactement le nombre de chaque pièce spécifié dans l'entrée - ni plus, ni moins. Il y aura au moins une piste de course valide pour chaque entrée.

Exemples d'entrées et de sorties

Contribution: 3,5,2,2,2,2,1

Une sortie possible:

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

Contribution: 0,0,1,4,4,1,3

Une sortie possible:

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

Ruby 664 671 677 687 701 (678 octets)

_={│:[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

Ce n'est pas le programme le plus court que j'ai pu trouver, mais j'ai sacrifié une certaine brièveté pour la vitesse d'exécution.

Vous pouvez expérimenter avec le programme ici . Notez que ideone a une limite de temps d'exécution, donc pour les entrées composées de plus d'environ 12 pièces, le programme expirera probablement.

Il existe également une suite de tests pour le programme. Notez que les deux derniers tests sont désactivés sur ideone, en raison du délai mentionné ci-dessus. Pour activer ces tests, supprimez le x_préfixe de leurs noms.

Le programme trouve une solution en utilisant la recherche en profondeur d'abord; il place les pièces une à une et garde une trace des extrémités libres. La recherche s'arrête lorsqu'il n'y a plus d'extrémités lâches (non connectées) et que toutes les pièces ont été placées.

Voici le programme non 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))
}