Вступление

Моя племянница хочет сделать гоночную машину. У нее есть деревянные части, которые соединяются, чтобы сформировать след. Каждая часть имеет квадратную форму и содержит различную форму. Я буду использовать символы рисования трубы, чтобы проиллюстрировать:

• │: дорога, которая идет вертикально
• ─: дорога, которая идет горизонтально
• ┌ ┐ └ ┘: дороги, которые поворачивают в направлении
• ┼: Мост с подземным переходом

Любопытно, что там нет тройников.

Вот пример возможной трассы гоночного автомобиля:

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

Правила действующего гоночного трека следующие:

• Там не может быть никаких дорог, которые ведут в никуда.
• Он должен образовывать цикл (и все части должны быть частью одного цикла).
• На мостах / подземных переходах вы не можете повернуть (поэтому вы должны пройти прямо через них).

К сожалению, куски гоночной машины у моей племянницы ограничены. Но мы определенно хотим использовать их все в треке. Напишите программу, которая, учитывая список того, что находится в нашем инвентаре, выводит дорожку гоночной машины, которая использует все эти части.

Описание входа

Мы бы хотели, чтобы ввод поступал через STDIN, аргументы командной строки, чтение файла или функцию пользовательского ввода (например, raw_inputили prompt). Входные данные разделены запятыми положительными целыми числами в форме

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

где каждый из них представляет количество этой конкретной части, которую мы имеем. Так, например, вход:

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

будет означать, что у нас был один из каждого куска.

Описание выхода

Выведите дорожку гоночной машины, используя символы рисования труб, перечисленные выше. Трасса гоночной машины должна использовать именно то число, которое указано во входных данных - не больше и не меньше. Для каждого входа будет хотя бы одна действующая трасса гоночного автомобиля.

Пример входов и выходов

Входные данные: 3,5,2,2,2,2,1

Возможный вывод:

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

Входные данные: 0,0,1,4,4,1,3

Возможный вывод:

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

Рубин 664 671 677 687 701 (678 байт)

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

Это не самая короткая программа, которую я мог придумать, но я пожертвовал некоторой краткостью ради скорости выполнения.

Вы можете поэкспериментировать с программой здесь . Обратите внимание, что ideone имеет ограничение по времени выполнения, поэтому для входных данных, состоящих более чем из 12 частей, программа, вероятно, истечет время ожидания.

Есть также набор тестов для программы. Обратите внимание, что последние два теста отключены на ideone из-за ограничения по времени, указанного выше. Чтобы включить эти тесты, удалите x_префикс из их имен.

Программа находит решение, используя поиск в глубину; он расставляет фигуры по одному и отслеживает свободные концы. Поиск прекращается, когда больше нет свободных (не связанных) концов, и все фрагменты размещены.

Это негольфированная программа:

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