Tout d'abord, une terminologie ( source ):

• Un toit en croupe est (citant Wikipedia) "un type de toit où tous les côtés descendent vers les murs, généralement avec une pente assez douce"
• Une pente est une surface plane qui fait partie du toit
• Une crête est un bord où deux pentes de toit opposées se rencontrent
• Une hanche est un bord convexe où deux pentes appartenant à des murs perpendiculaires se rencontrent
• Une vallée est un bord concave où deux pentes appartenant à des murs perpendiculaires se rencontrent
• Les hanches et les vallées seront collectivement appelées bords diagonaux.

Entrée possible:

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

Sortie correspondante:

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

Quelques cas de test supplémentaires:

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

Sorties correspondantes:

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

Votre entrée sera un bitmap - un tableau 2D de pixels carrés - de la zone qui devrait être couverte par le toit. Vous pouvez supposer que la limite de cette zone sera une courbe de Jordan - c'est-à-dire continue et non auto-entrecroisée - c'est-à-dire que la zone couverte sera continue, sans trous et qu'il n'y aura jamais quatre murs se rencontrant en un seul point. Les formats d'entrée valides incluent une chaîne unique avec des séparateurs de nouvelle ligne, une liste de chaînes et un tableau 2D de caractères ou de booléens.

Les règles de construction du toit sont les suivantes:

• Chaque segment droit de la zone couverte (dorénavant dénommé mur) doit avoir exactement une pente adjacente. La pente doit s'éloigner du mur. Chaque pente doit avoir au moins un mur adjacent et tous les murs adjacents à une pente doivent être colinéaires.
• Toutes les pentes doivent avoir le même angle (non nul) contre la surface horizontale. Autrement dit, ils doivent avoir le même pas.
• Les pentes doivent former une surface dont la limite est la limite de la zone couverte. Autrement dit, aucune surface autre que les pentes ne peut être utilisée.
• Tout scénario dans lequel plusieurs solutions (jusqu'à une mise à l'échelle verticale) sont autorisées par cette spécification est considéré comme un bogue dans la spécification. Toutes les corrections s'appliquent rétroactivement.

De manière équivalente, le toit peut être défini par la règle selon laquelle chaque point du toit est placé aussi haut que possible sans dépasser la pente maximale pour ce toit mesurée en utilisant la distance de Tchebychev en vue de haut en bas.

Votre sortie doit être une représentation artistique ASCII du toit - soit une seule chaîne contenant des caractères de nouvelle ligne ou un tableau de chaînes, chacune désignant une seule ligne de la sortie. Le toit doit être rendu en vue de haut en bas à une échelle de 4x - c'est-à-dire que chaque carré du plan d'étage doit affecter une zone 5x5 de la sortie de telle sorte que les coins de cette zone 5x5 soient partagés avec les carrés voisins (de telle sorte que chaque le caractère de coin est affecté par quatre carrés d'entrée différents), comme indiqué par l'exemple de sortie. Un espace supplémentaire est autorisé tant que la forme de sortie est préservée. Les caractères en sortie doivent être:

• un marqueur de nouvelle ligne défini par l'environnement doit être utilisé (généralement U + 000A, U + 000D ou une paire des deux) si la sortie est sous la forme d'une seule chaîne
• (Espace U + 0020) représente un point à l'extérieur d'une zone couverte ou un point à l'intérieur d'une pente
• + (U + 002B plus signe) représente un point avec deux parois perpendiculaires qui lui sont adjacentes
• - (U + 002D trait d'union moins) représente un mur ou une crête orientée horizontalement (est-ouest)
• / (U + 002F solidus) représente une hanche ou une vallée orientée du nord-est au sud-est, ou un point adjacent à deux de ces
• < (U + 003C moins que signe) représente un point avec deux bords diagonaux qui lui sont adjacents à l'est
• > (U + 003E signe supérieur à) représente un point avec deux bords diagonaux qui lui sont adjacents à l'ouest
• \ (U + 005C solidus inversé) représente une hanche ou une vallée orientée du nord-ouest au sud-est, ou un point adjacent à deux de ces
• ^ (Accent circonflexe U + 005E) représente un point avec deux bords diagonaux qui lui sont adjacents au sud
• V (U + 0056 lettre majuscule latine v) représente un point avec deux bords diagonaux qui lui sont adjacents au nord
• X (U + 0058 lettre majuscule latine x) représente un point avec des bords diagonaux qui lui sont attachés sur les quatre côtés
• | (U + 007C barre verticale) représente un mur ou une crête orientée verticalement (nord-sud)

Notez qu'il n'est pas possible qu'un nombre impair d'arêtes diagonales se termine au même point (sauf sur les murs). Nous pouvons visualiser cela en partitionnant le voisinage de chaque point en pente nord + pente sud et en pente est + pente ouest. La frontière entre les deux partitions doit être composée de bords diagonaux.

Si votre environnement utilise un codage de caractères incompatible avec ASCII, vous pouvez utiliser les caractères équivalents (même glyphe ou le plus proche disponible) dans le codage de caractères utilisé par votre environnement.

L' implémentation de référence suivante (laide) dans Ruby est normative en ce qui concerne la sortie non blanche. Notez particulièrement la renderméthode:

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 octets

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

Fatigué de jouer au golf, et j'ai obtenu un bon score, donc le voici.

L'indentation de huit espaces est un onglet.

Passez une matrice binaire sur STDIN, comme ceci:

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]]"