Zunächst einige Begriffe ( Quelle ):

• Ein Walmdach ist (unter Angabe von Wikipedia) "eine Art Dach, bei dem alle Seiten nach unten zu den Wänden abfallen, normalerweise mit einer ziemlich leichten Neigung".
• Eine Neigung ist eine ebene Fläche, die Teil des Daches ist
• Ein First ist eine Kante, an der sich zwei gegenüberliegende Dachschrägen treffen
• Eine Hüfte ist eine konvexe Kante, an der sich zwei zu senkrechten Wänden gehörende Schrägen treffen
• Ein Tal ist eine konkave Kante, an der sich zwei Hänge treffen, die zu senkrechten Wänden gehören
• Hüften und Täler werden gemeinsam als diagonale Kanten bezeichnet.

Mögliche Eingabe:

 ** * ***
******** 
 ** *  **

Entsprechende Ausgabe:

    +-------+   +---+   +-----------+
    |\     /|   |\ /|   |\         /|
    | \   / |   | V |   | \   ^---< |
    |  \ /  |   | | |   |  \ / \   \|
+---+   V   +---+ | +---+   X   +---+
|\   \  |  /     \|/     \ / \  |
| >---> | <-------X-------V   > |
|/   /  |  \     /|\         /| |
+---+   ^   +---+ | +-------+ | +---+
    |  / \  |   | | |       | |/   /|
    | /   \ |   | ^ |       | /---< |
    |/     \|   |/ \|       |/     \|
    +-------+   +---+       +-------+

Noch ein paar Testfälle:

** ***   *    *   * *
*       ***   *****  
    ** *****  *****  
* *  *  ***  *** *** 
* ****   *     * *   

Entsprechende Ausgänge:

+-------+   +-----------+           +---+               +---+           +---+   +---+
|\     /|   |\         /|           |\ /|               |\ /|           |\ /|   |\ /|
| \---< |   | >-------< |           | V |               | V |           | V |   | X |
| |\   \|   |/         \|           | | |               | | |           | | |   |/ \|
| | +---+   +-----------+       +---+ | +---+           | | +-----------+ | |   +---+
| | |                           |\   \|/   /|           | |/             \| |
| ^ |                           | \   V   / |           | <               > |
|/ \|                           |  \     /  |           |  \             /  |
+---+           +-------+   +---+   \   /   +---+       |   \-----------/   |
                |\     /|   |\   \   \ /   /   /|       |   |\         /|   |
                | >---/ |   | >--->   X   <---< |       |   | \       / |   |
                |/   /| |   |/   /   / \   \   \|       |   |  \     /  |   |
+---+   +---+   +---+ | |   +---+   /   \   +---+   +---+   ^   +---+   ^   +---+
|\ /|   |\ /|       | | |       |  /     \  |       |\   \ / \  |   |  / \ /   /|
| V |   | V |       | | |       | /   ^   \ |       | >---V   > |   | <   V---< |
| | |   | | |       | | |       |/   /|\   \|       |/       /| |   | |\       \|
| | |   | | +-------+ | |       +---+ | +---+       +-------+ | |   | | +-------+
| | |   | |/         \| |           | | |                   | | |   | | |
| ^ |   | /-----------\ |           | ^ |                   | ^ |   | ^ |
|/ \|   |/             \|           |/ \|                   |/ \|   |/ \|
+---+   +---------------+           +---+                   +---+   +---+

Ihre Eingabe ist eine Bitmap - ein 2D-Array aus quadratischen Pixeln - des Bereichs, der vom Dach abgedeckt werden soll. Sie können davon ausgehen, dass die Grenze dieses Bereichs eine Jordan-Kurve ist - das heißt, kontinuierlich und sich nicht selbst schneidend - das heißt, die überdachte Fläche ist kontinuierlich, ohne Löcher, und es werden niemals vier Wände an einem einzigen Punkt zusammentreffen. Gültige Eingabeformate sind eine einzelne Zeichenfolge mit Trennzeichen für Zeilenumbrüche, eine Liste von Zeichenfolgen und ein 2D-Array mit Zeichen oder Booleschen Zeichen.

Die Regeln für den Bau des Daches sind:

• Jedes gerade Segment der überdachten Fläche (im Folgenden als Wand bezeichnet) muss genau eine angrenzende Neigung aufweisen. Der Hang soll von der Wand abheben. Jeder Hang muss mindestens eine angrenzende Wand haben, und alle an einen Hang angrenzenden Wände müssen kollinear sein.
• Alle Neigungen müssen gegenüber der horizontalen Fläche den gleichen Winkel (ungleich Null) haben. Das heißt, sie müssen die gleiche Tonhöhe haben.
• Die Hänge müssen eine Fläche bilden, deren Grenze die Grenze der überdachten Fläche ist. Das heißt, keine anderen Oberflächen als die Gefälle dürfen verwendet werden.
• Jedes Szenario, in dem in dieser Spezifikation mehr als eine Lösung (bis zur vertikalen Skalierung) zulässig ist, wird als Fehler in der Spezifikation angesehen. Korrekturen gelten rückwirkend.

Entsprechend kann das Dach durch die Regel definiert werden, dass jeder Punkt des Dachs so hoch wie möglich platziert wird, ohne die maximale Neigung für dieses Dach zu überschreiten, die unter Verwendung des Chebyshev-Abstands in der Ansicht von oben nach unten gemessen wird .

Ihre Ausgabe soll eine ASCII-Grafikdarstellung des Daches sein - entweder eine einzelne Zeichenfolge mit Zeilenumbrüchen oder eine Reihe von Zeichenfolgen, die jeweils eine einzelne Zeile der Ausgabe kennzeichnen. Das Dach wird in einer Ansicht von oben nach unten in einem 4-fachen Maßstab gerendert - das heißt, jedes Quadrat des Grundrisses sollte einen 5x5-Bereich der Ausgabe so beeinflussen, dass die Ecken dieses 5x5-Bereichs mit benachbarten Quadraten geteilt werden (so dass jeder Das Eckzeichen wird von vier verschiedenen Eingabequadraten beeinflusst (siehe Beispielausgabe). Zusätzliches Leerzeichen ist zulässig, solange die Ausgabeform erhalten bleibt. Die auszugebenden Zeichen müssen sein:

• Ein umgebungsdefinierter Newline-Marker (normalerweise U + 000A, U + 000D oder ein Paar von beiden) wird verwendet, wenn die Ausgabe in Form einer einzelnen Zeichenfolge vorliegt
• (U + 0020-Raum) steht für einen Punkt außerhalb eines überdachten Bereichs oder einen Punkt innerhalb eines Abhangs
• + (U + 002B Pluszeichen) steht für einen Punkt mit zwei daran anschließenden senkrechten Wänden
• - (U + 002D Bindestrich-Minus) steht für eine Wand oder einen horizontal ausgerichteten Grat (Ost-West)
• / (U + 002F solidus) repräsentiert eine Hüfte oder ein Tal, das von Nordosten nach Südosten ausgerichtet ist, oder einen Punkt, der an zwei davon angrenzt
• < (U + 003C kleiner als Vorzeichen) steht für einen Punkt mit zwei diagonalen Rändern im Osten
• > (U + 003E Größer-als-Zeichen) steht für einen Punkt, an den im Westen zwei diagonale Kanten angrenzen
• \ (U + 005C reverse solidus) repräsentiert eine Hüfte oder ein Tal, das von Nordwesten nach Südosten ausgerichtet ist, oder einen Punkt, der an zwei dieser Punkte angrenzt
• ^ (U + 005E Zirkumflex-Akzent) stellt einen Punkt dar, an den im Süden zwei diagonale Kanten angrenzen
• V (U + 0056 lateinischer Großbuchstabe v) steht für einen Punkt, an den sich im Norden zwei diagonale Kanten anschließen
• X (U + 0058 lateinischer Großbuchstabe x) steht für einen Punkt, an den an allen vier Seiten diagonale Kanten angrenzen
• | (U + 007C vertikaler Balken) repräsentiert eine Wand oder einen Kamm, der vertikal (Nord-Süd) ausgerichtet ist.

Beachten Sie, dass eine ungerade Anzahl diagonaler Kanten nicht am selben Punkt enden kann (außer an Wänden). Wir können uns das vorstellen, indem wir die Nachbarschaft jedes Punktes in Nordhang + Südhang und in Osthang + Westhang unterteilen. Die Grenze zwischen beiden Partitionen muss aus diagonalen Kanten bestehen.

Wenn in Ihrer Umgebung eine mit ASCII nicht kompatible Zeichenkodierung verwendet wird, können Sie in der Zeichenkodierung, die in Ihrer Umgebung verwendet wird, die entsprechenden Zeichen (gleiche Glyphe oder nächstliegende verfügbare) verwenden.

Die folgende (hässliche) Referenzimplementierung in Ruby ist in Bezug auf die Ausgabe ohne Leerzeichen normativ. Beachten Sie insbesondere die renderMethode:

def pad ary
  row = ary.first.map{-1}
  ([row] + ary + [row]).map{|r| [-1] + r + [-1]}
end

def parse str
  str.split("\n").map{|r| r.chars.map(&{" " => -1, "*" => Float::INFINITY})}
end

def squares ary, size
  ary.each_cons(size).map do |rows|
    rows.map{|row| row.each_cons(size).to_a}.transpose
  end
end

def consmap2d ary, size
  squares(ary, size).map{|sqrow| sqrow.map{|sq| yield sq}}
end

def relax ary
  loop do
    new = consmap2d(pad(ary), 3){|sq| sq[1][1] == -1 ? -1 : sq.flatten.min + 1}
    return new if new == ary
    ary = new
  end
end

def semidouble ary, op
  ary.zip(ary.each_cons(2).map{|r1,r2|r1.zip(r2).map(&op)}).flatten(1).compact.transpose
end

def heightmap str
  relax(semidouble(semidouble(semidouble(semidouble(pad(parse str),:max),:max),:min),:min))
end

def render heightmap
  puts consmap2d(heightmap, 3){|sq|
    next " " if sq[1][1] == -1
    hwall = sq[0][1] == -1 || sq[2][1] == -1
    vwall = sq[1][0] == -1 || sq[1][2] == -1
    next "+" if hwall && vwall
    next "-" if hwall
    next "|" if vwall
    next "+" if sq.flatten.min == -1

    nws = sq[0][1] == sq[1][0]
    nes = sq[0][1] == sq[1][2]
    sws = sq[2][1] == sq[1][0]
    ses = sq[2][1] == sq[1][2]

    next "X"  if nws && nes && sws && ses
    next "V"  if nws && nes
    next "^"  if sws && ses
    next ">"  if nws && sws
    next "<"  if nes && ses
    next "/"  if nes && sws
    next "\\" if nws && ses
    next " "  if sq[0][1] != sq[2][1] || sq[1][0] != sq[1][2]
    next "|"  if sq[0][1] == sq[1][1]
    next "-"  if sq[1][0] == sq[1][1]
    ??
  }.map(&:join)
end

render heightmap $<.read if __FILE__ == $0 

Python 2, 500 Bytes

z=input()
W=4*len(z[0])+1
H=4*len(z)+1
R=range
s=[-~W*[0]for _ in R(-~H)]
for y in R(H/4):
 for x in R(W/4):
        for h in R(25):s[y*4+h%5][x*4+h/5]|=z[y][x]
F=[(x/3-1,x%3-1)for x in[1,7,3,5,0,6,8,2]]
exec'for y in R(H):\n for x in R(W):s[y][x]+=0<s[y][x]<=min(s[y+d][x+e]for(e,d)in F)\n'*H
for y in R(H):
 l=''
 for x in R(W):h=s[y][x];a=[s[y+d][x+e]for(e,d)in F[:4]];l+=r' XabcVde^f ||g>h\\+//+<<jk<l//+\\+>>m --^^oVVqrX'[h and int(''.join(`int(n==h)`for n in a),2)*3+((h==1)*2or max(a)==h)+1]
 print l

Ich bin es leid, Golf zu spielen, und bin zu einer guten Runde gekommen.

Der Einzug mit acht Leerzeichen ist ein Tabulator.

Übergeben Sie STDIN eine binäre Matrix wie folgt:

python2.7 roof.py <<<"[[1,1,0,1,1,1,0,0,0,1,0,0,0,0,1,0,0,0,1,0], [1,0,0,0,0,0,0,0,1,1,1,0,0,0,1,1,1,1,1,0], [0,0,0,0,1,1,0,1,1,1,1,1,0,0,1,1,1,1,1,0], [1,0,1,0,0,1,0,0,1,1,1,0,0,1,1,1,0,1,1,1], [1,0,1,1,1,1,0,0,0,1,0,0,0,0,0,1,0,1,0,0]]"