Renderuj widok z góry dachu czterospadowego w ASCII

23

Po pierwsze, pewna terminologia ( źródło ):

  • Dachem jest (podając Wikipedia) „rodzaj dachu, w którym wszystkie boki nachylenie w dół do ściany, zwykle ze stosunkowo łagodnym nachyleniu”
  • Nachylenie to płaska powierzchnia, która jest częścią dachu
  • Grzbiet to krawędź, na której spotykają się dwa przeciwległe połacie dachu
  • Biodro to wypukła krawędź, na której spotykają się dwa zbocza należące do prostopadłych ścian
  • Dolina jest wklęsłą krawędzią, w której spotykają się dwa zbocza należące do prostopadłych ścian
  • Biodra i doliny określa się łącznie jako ukośne krawędzie.

Możliwe dane wejściowe:

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

Odpowiednia wydajność:

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

Jeszcze kilka przypadków testowych:

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

Odpowiednie wyniki:

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

Twój wkład będzie bitmapą - dwuwymiarową matrycą kwadratowych pikseli - obszaru, który powinien być pokryty dachem. Możesz założyć, że granicą tego obszaru będzie krzywa Jordana - to znaczy ciągła i nie przecinająca się - to znaczy obszar zadaszony będzie ciągły, bez otworów i nigdy nie będzie czterech ścian spotykających się w jednym punkcie. Prawidłowe formaty wejściowe obejmują pojedynczy ciąg znaków z separatorami nowej linii, listę ciągów znaków oraz tablicę 2D znaków lub boolanów.

Zasady budowy dachu to:

  • Każdy prosty odcinek zadaszonego obszaru (zwany dalej ścianą) powinien mieć dokładnie jedno sąsiednie nachylenie. Nachylenie powinno wynosić od ściany. Każde zbocze powinno mieć co najmniej jedną przylegającą ścianę, a wszystkie ściany przylegające do zbocza muszą być współliniowe.
  • Wszystkie zbocza powinny mieć taki sam (niezerowy) kąt względem powierzchni poziomej. Oznacza to, że muszą mieć ten sam ton.
  • Nachylenia powinny tworzyć powierzchnię, której granicą jest granica zadaszonego obszaru. Oznacza to, że nie można stosować żadnych innych powierzchni niż zbocza.
  • Każdy scenariusz, w którym więcej niż jedno rozwiązanie (do skalowania pionowego) jest dozwolone przez tę specyfikację, jest uważany za błąd w specyfikacji. Wszelkie korekty obowiązują z mocą wsteczną.

Równolegle dach może być określony przez zasadę, że każdy punkt dachu jest umieszczony tak wysoko, jak to możliwe, bez przekraczania maksymalnego nachylenia dla tego dachu, mierzonego za pomocą odległości Czebyszewa w widoku z góry na dół.

Twoje dane wyjściowe będą reprezentacją dachu ASCII - pojedynczy ciąg zawierający znaki nowego wiersza lub tablica ciągów, z których każdy oznacza pojedynczy wiersz wyniku. Dach powinien być renderowany w widoku z góry w skali 4x - to znaczy, każdy kwadrat w planie piętra powinien wpływać na obszar wyjściowy 5x5, tak że narożniki tego obszaru 5x5 są wspólne z sąsiednimi kwadratami (tak, że każdy na znak narożny mają wpływ cztery różne kwadraty wejściowe), jak wskazuje przykładowe wyjście. Dopuszczalne są dodatkowe białe znaki, o ile zachowany jest kształt wyjściowy. Wyjściowe znaki to:

  • należy użyć znacznika nowej linii zdefiniowanego w środowisku (zwykle U + 000A, U + 000D lub para obu), jeśli wynik jest w postaci pojedynczego ciągu
  • (Przestrzeń U + 0020) reprezentuje punkt poza zadaszonym obszarem lub punkt wewnątrz spadku
  • + (U + 002B plus znak) reprezentuje punkt, do którego przylegają dwie prostopadłe ściany
  • - (U + 002D łącznik minus) reprezentuje ścianę lub grzbiet zorientowany poziomo (wschód-zachód)
  • / (U + 002F solidus) reprezentuje biodro lub dolinę zorientowaną z północnego wschodu na południowy wschód lub punkt przylegający do dwóch z nich
  • < (U + 003C mniej niż znak) oznacza punkt z dwiema ukośnymi krawędziami przylegającymi do niego na wschodzie
  • > (U + 003E większy niż znak) oznacza punkt z dwiema ukośnymi krawędziami przylegającymi do niego na zachodzie
  • \ (U + 005C reverse solidus) reprezentuje biodro lub dolinę zorientowaną z północnego zachodu na południowy wschód lub punkt przylegający do dwóch z nich
  • ^ (U + 005E akcent obwodowy) reprezentuje punkt z dwiema ukośnymi krawędziami przylegającymi do niego na południu
  • V (U + 0056 łacińska wielka litera v) reprezentuje punkt z dwiema ukośnymi krawędziami przylegającymi do niego na północy
  • X (U + 0058 łacińska wielka litera x) reprezentuje punkt z ukośnymi krawędziami przylegającymi do niego ze wszystkich czterech stron
  • | (Pionowy pasek U + 007C) reprezentuje ścianę lub grzbiet zorientowany pionowo (północ-południe)

Należy pamiętać, że nieparzysta liczba ukośnych krawędzi kończy się w tym samym punkcie (z wyjątkiem ścian). Możemy to sobie wyobrazić dzieląc sąsiedztwo każdego punktu na północne zbocze + południowe zbocze i na wschodnie zbocze + zachodnie zbocze. Granica między obiema przegrodami musi składać się z ukośnych krawędzi.

Jeśli twoje środowisko używa kodowania znaków niekompatybilnego z ASCII, możesz użyć równoważnych znaków (ten sam glif lub najbliższy dostępny) w znaku kodującym twoje środowisko.

Następująca (brzydka) implementacja referencyjna w Ruby jest normatywna w odniesieniu do wyjścia innego niż białe znaki. Zwróć szczególną uwagę na rendermetodę:

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 
John Dvorak
źródło
1
Powinieneś dodać więcej przypadków testowych.
mbomb007
@ mbomb007 Dodano. Biorąc pod uwagę zajmowaną przestrzeń - czy powinienem dodać coś jeszcze?
John Dvorak,
@JanDvorak Może dodać przypadek testowy *. W przeciwnym razie to chyba wystarczy.
mbomb007
Czy [[0,1,1],[1,0,1],[1,1,1]]prawidłowe dane wejściowe? (Na wejściu nie ma „dziur”, ale jest nieznośny róg w pobliżu skrzyżowania.)
Lynn
@ Lynn Nie musisz się martwić o tę sprawę, to nie jest poprawny wpis. Wspomniany róg liczy się jako granica przecinająca się (a raczej granica, która nie jest krzywą).
John Dvorak

Odpowiedzi:

11

Python 2, 500 bajtów

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

Zmęczony graniem w golfa i mam dobry wynik rundy, więc oto jest.

Wcięcie ośmiu spacji jest tabulatorem.

Przekaż macierz binarną przez STDIN, tak jak:

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]]"
Lynn
źródło
W pełni golfa czy nie, to niesamowite. Dobra robota. +1
R. Kap.