Einführung

Meine Nichte will eine Rennstrecke bauen. Sie hat Holzteile, die zusammenpassen, um die Spur zu bilden. Jedes Teil ist quadratisch und enthält eine andere Form. Ich werde die Rohrzeichen verwenden, um Folgendes zu veranschaulichen:

• │: die Straße, die vertikal verläuft
• ─: die Straße, die horizontal verläuft
• ┌ ┐ └ ┘: die Straßen, die sich in eine Richtung drehen
• ┼: Eine Brücke mit einer Unterführung

Seltsamerweise gibt es keine T-Stücke.

Hier ist ein Beispiel für eine mögliche Rennstrecke:

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

Die Regeln für eine gültige Rennstrecke lauten wie folgt:

• Es kann keine Straßen geben, die ins Nirgendwo führen.
• Es muss eine Schleife bilden (und alle Teile müssen Teil derselben Schleife sein).
• An den Brücken / Unterführungen kann man nicht abbiegen (also muss man sie gerade durchfahren).

Leider sind die Rennstreckenstücke, die meine Nichte und ich haben, begrenzt. Aber wir wollen auf jeden Fall alle in der Strecke verwenden. Schreiben Sie ein Programm , das anhand einer Liste der Teile in unserem Inventar eine Rennbahn ausgibt, auf der alle Teile verwendet werden.

Eingabebeschreibung

Wir möchten, dass die Eingabe über STDIN, Befehlszeilenargumente, das Lesen von Dateien oder eine Benutzereingabefunktion (wie z. B. raw_inputoder prompt) erfolgt. Die Eingabe erfolgt durch Kommas getrennte positive Ganzzahlen in der Form

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

wo jedes von denen die Menge dieses bestimmten Stückes darstellt, das wir haben. So zum Beispiel die Eingabe:

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

würde bedeuten, dass wir eines von jedem Stück hatten.

Ausgabebeschreibung

Geben Sie eine Rennstrecke mit den oben aufgeführten Rohrzeichen aus. Die Rennstrecke sollte genau die Nummer jedes in der Eingabe angegebenen Stücks verwenden - nicht mehr und nicht weniger. Für jede Eingabe gibt es mindestens eine gültige Rennstrecke.

Beispiel Ein- und Ausgänge

Eingang: 3,5,2,2,2,2,1

Eine mögliche Ausgabe:

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

Eingang: 0,0,1,4,4,1,3

Eine mögliche Ausgabe:

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

Ruby 664 671 677 687 701 (678 Byte)

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

Dies ist nicht das kürzeste Programm, das ich mir vorstellen konnte, aber ich habe etwas Kürze für die Ausführungsgeschwindigkeit geopfert.

Sie können mit dem Programm experimentieren hier . Beachten Sie, dass ideone ein Ausführungszeitlimit hat. Bei Eingaben, die aus mehr als 12 Teilen bestehen, wird das Programm wahrscheinlich eine Zeitüberschreitung aufweisen.

Es gibt auch eine Testsuite für das Programm. Beachten Sie, dass die letzten beiden Tests auf ideone aufgrund des oben genannten Zeitlimits deaktiviert sind. Um diese Tests zu aktivieren, löschen Sie das x_Präfix aus ihren Namen.

Das Programm findet eine Lösung mit der Tiefensuche. Es platziert die Teile einzeln und verfolgt die losen Enden. Die Suche wird abgebrochen, wenn keine losen (nicht verbundenen) Enden mehr vorhanden sind und alle Teile platziert wurden.

Dies ist das ungolfed Programm:

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