Wprowadzenie

Moja siostrzenica chce zrobić tor wyścigowy. Ma drewniane elementy, które pasują do siebie, tworząc tor. Każda część ma kwadratowy kształt i zawiera inny kształt. Wykorzystam znaki rysunkowe do zilustrowania:

• │: droga prowadząca w pionie
• ─: droga prowadząca poziomo
• ┌ ┐ └ ┘: drogi skręcające w określonym kierunku
• ┼: Most z przejściem podziemnym

Co ciekawe, nie ma trójników.

Oto przykład możliwego toru wyścigowego:

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

Zasady obowiązującego toru wyścigowego są następujące:

• Żadne drogi nie prowadzą do nikąd.
• Musi tworzyć pętlę (a wszystkie elementy muszą być częścią tej samej pętli).
• Na mostach / przejazdach podziemnych nie możesz skręcić (więc musisz przejść prosto przez nie).

Niestety kawałki toru wyścigowego, które moja siostrzenica i ja mamy, są ograniczone. Ale zdecydowanie chcemy wykorzystać je wszystkie na torze. Napisz program, który, biorąc pod uwagę listę elementów znajdujących się w naszym ekwipunku, generuje tor samochodu wyścigowego, który wykorzystuje wszystkie te elementy.

Opis wejścia

Chcielibyśmy, aby dane wejściowe były wprowadzane za pośrednictwem STDIN, argumentów wiersza poleceń, odczytu plików lub funkcji wprowadzania danych przez użytkownika (np. raw_inputLub prompt). Dane wejściowe to oddzielone przecinkami dodatnie liczby całkowite w formularzu

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

gdzie każdy z nich reprezentuje ilość tego konkretnego kawałka, który mamy. Na przykład dane wejściowe:

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

oznaczałoby to, że mieliśmy po jednym z każdego kawałka.

Opis wyjścia

Wyprowadź tor samochodu wyścigowego, używając znaków rysowania rur wymienionych powyżej. Tor samochodu wyścigowego powinien wykorzystywać dokładnie numer każdego elementu podany na wejściu - nie więcej i nie mniej. Dla każdego wejścia będzie co najmniej jeden ważny tor wyścigowy.

Przykładowe wejścia i wyjścia

Wejście: 3,5,2,2,2,2,1

Możliwe wyjście:

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

Wejście: 0,0,1,4,4,1,3

Możliwe wyjście:

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

Rubinowy 664 671 677 687 701 (678 bajtów)

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

To nie jest najkrótszy program, jaki mogłem wymyślić, ale poświęciłem trochę zwięzłości dla szybkości wykonywania.

Możesz eksperymentować z programem tutaj . Należy pamiętać, że ideone ma limit czasu wykonania, więc dla danych wejściowych składających się z ponad 12 elementów program prawdopodobnie przekroczy limit czasu.

Istnieje również pakiet testowy dla programu. Zwróć uwagę, że ostatnie dwa testy są wyłączone na ideone, ze względu na wyżej wspomniany limit czasu. Aby włączyć te testy, usuń x_prefiks z ich nazw.

Program znajduje rozwiązanie za pomocą wyszukiwania w pierwszej kolejności; umieszcza elementy pojedynczo i śledzi luźne końce. Wyszukiwanie kończy się, gdy nie ma już luźnych (niepołączonych) końców i wszystkie elementy zostały umieszczone.

To jest program bez golfa:

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