# Let's build a race car track!

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:

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

• Does it need to give the output? Or does it only theoretically need to give the output? – Sumurai8 May 26 '15 at 9:48
• @Sumurai8 What do you mean by "theoretically" give the output? Do you mean a program that won't terminate for an extremely long time but will eventually give the output? – absinthe May 26 '15 at 10:28
• One would probably be able to create a field of n x n squares filled with the race pieces and empty squares, where you can generate permutations until you find something that is a race track. That would take forever for anything more than a few tiles. – Sumurai8 May 26 '15 at 11:23
• @Sumurai8 Ah okay, I understand now. I would prefer that programs will give an output before the heat death of the universe for the small value inputs I've shown in the challenge. – absinthe May 26 '15 at 11:38
• Your niece is not patient enough! :P – Sumurai8 May 26 '15 at 16:41

# 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] != []
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))
}