Let's build a race car track!

Question

Introduction

My niece wants to make a race car track. She has wooden parts that fit together to form the track. Each part is square shaped and contains a different shape. I'll use the pipe drawing characters to illustrate:

• │: the road that goes vertically
• ─: the road that goes horizontally
• ┌ ┐ └ ┘: the roads that turn in a direction
• ┼: A bridge with an underpass

Curiously, there are no t-junction pieces.

Here's an example of a possible race car track:

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

The rules for a valid race car track are as follows:

• There can't be any roads that go to nowhere.
• It must form a loop (and all the pieces must be part of the same loop).
• At the bridges / underpasses, you can't turn (so you have to go straight through them).

Unfortunately, the race car track pieces my niece and I have are limited. But we definitely want to use all of them in the track. Write a program that, given a list of what pieces are in our inventory, outputs a race car track that uses all of those pieces.

Input Description

We'd like the input to come in via STDIN, command line arguments, file reading, or a user input function (such as raw_input or prompt). The input is comma separated positive integers in the form

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

where each of those represent the amount of that particular piece we have. So for instance the input:

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

would mean that we had one of each piece.

Output Description

Output a race car track using the pipe drawing characters listed above. The race car track should use exactly the number of each piece specified in the input -- no more, and no less. There will be at least one valid race car track for every input.

Example Inputs and Outputs

Input: 3,5,2,2,2,2,1

A possible output:

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

Input: 0,0,1,4,4,1,3

A possible output:

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

Answer 1

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

This is not the shortest program I could come up with, but I sacrificed some brevity for execution speed.

You can experiment with the program here. Note that ideone has an execution time limit, so for inputs consisting of more than about 12 pieces, the program will probably time out.

There's also a test suite for the program. Note that the last two tests are disabled on ideone, due to the time limit mentioned above. To enable these tests, delete the x_ prefix from their names.

The program finds a solution using Depth-first search; it places pieces one at a time and keeps tracks of loose ends. The search stops when there are no more loose (unconnected) ends and all pieces have been placed.

This is the ungolfed program:

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