First, some terminology (source):
- A hip roof is (quoting Wikipedia) "a type of roof where all sides slope downwards to the walls, usually with a fairly gentle slope"
- A slope is a planar surface that is a part of the roof
- A ridge is an edge where two opposite roof slopes meet
- A hip is a convex edge where two slopes belonging to perpendicular walls meet
- A valley is a concave edge where two slopes belonging to perpendicular walls meet
- Hips and valleys shall be collectively referred to as diagonal edges.
Possible input:
** * ***
********
** * **
Corresponding output:
+-------+ +---+ +-----------+
|\ /| |\ /| |\ /|
| \ / | | V | | \ ^---< |
| \ / | | | | | \ / \ \|
+---+ V +---+ | +---+ X +---+
|\ \ | / \|/ \ / \ |
| >---> | <-------X-------V > |
|/ / | \ /|\ /| |
+---+ ^ +---+ | +-------+ | +---+
| / \ | | | | | |/ /|
| / \ | | ^ | | /---< |
|/ \| |/ \| |/ \|
+-------+ +---+ +-------+
A couple more test cases:
** *** * * * *
* *** *****
** ***** *****
* * * *** *** ***
* **** * * *
Corresponding outputs :
+-------+ +-----------+ +---+ +---+ +---+ +---+
|\ /| |\ /| |\ /| |\ /| |\ /| |\ /|
| \---< | | >-------< | | V | | V | | V | | X |
| |\ \| |/ \| | | | | | | | | | |/ \|
| | +---+ +-----------+ +---+ | +---+ | | +-----------+ | | +---+
| | | |\ \|/ /| | |/ \| |
| ^ | | \ V / | | < > |
|/ \| | \ / | | \ / |
+---+ +-------+ +---+ \ / +---+ | \-----------/ |
|\ /| |\ \ \ / / /| | |\ /| |
| >---/ | | >---> X <---< | | | \ / | |
|/ /| | |/ / / \ \ \| | | \ / | |
+---+ +---+ +---+ | | +---+ / \ +---+ +---+ ^ +---+ ^ +---+
|\ /| |\ /| | | | | / \ | |\ \ / \ | | / \ / /|
| V | | V | | | | | / ^ \ | | >---V > | | < V---< |
| | | | | | | | | |/ /|\ \| |/ /| | | |\ \|
| | | | | +-------+ | | +---+ | +---+ +-------+ | | | | +-------+
| | | | |/ \| | | | | | | | | | |
| ^ | | /-----------\ | | ^ | | ^ | | ^ |
|/ \| |/ \| |/ \| |/ \| |/ \|
+---+ +---------------+ +---+ +---+ +---+
Your input will be a bitmap - a 2D array of square pixels - of the area that should be covered by roof. You may assume the boundary of this area will be a Jordan curve - that is, continuous and non-self-intersecting - that is, the roofed area will be continuous, without holes and there will never be four walls meeting at a single point. Valid input formats include a single string with newline separators, a list of strings and a 2D array of chars or booleans.
The rules of building the roof are:
- Each straight segment of the roofed area (henceforth referred to as a wall) shall have exactly one adjoining slope. The slope shall rise away from the wall. Each slope shall have at least one adjoining wall, and all walls adjoining to a slope must be collinear.
- All slopes shall have the same (nonzero) angle against the horizontal surface. That is, they must have the same pitch.
- The slopes shall form a surface whose boundary is the boundary of the roofed area. That is, no surfaces other than the slopes may be used.
- Any scenario where more than one solution (up to vertical scaling) is allowed by this specification is considered a bug in the specification. Any corrections apply retroactively.
Equivalently, the roof may be defined by the rule that each point of the roof is placed as high as possible without exceeding the maximum slope for that roof as measured using the Chebyshev distance in top-down view.
Your output shall be an ASCII art representation of the roof - either a single string containing newline characters or an array of strings, each denoting a single line of the output. The roof shall be rendered in top-down view at a 4x scale - that is, each square of the floor-plan should affect a 5x5 area of the output such that the corners of this 5x5 area are shared with neighboring squares (such that each corner character is affected by four different input squares), as indicated by the example output. Extra whitespace is allowed as long as the output shape is preserved. The characters in output shall be:
- an environment-defined newline marker shall be used (usually U+000A, U+000D or a pair of both) if the output is in the form of a single string
(U+0020 space) represents a point outside a roofed area or a point interior to a slope
+
(U+002B plus sign) represents a point with two perpendicular walls adjoined to it-
(U+002D hyphen-minus) represents a wall or a ridge oriented horizontally (east-west)/
(U+002F solidus) represents a hip or a valley oriented north-east to south-east, or a point adjoined to two of those<
(U+003C less-than sign) represents a point with two diagonal edges adjoined to it on the east>
(U+003E greater-than sign) represents a point with two diagonal edges adjoined to it on the west\
(U+005C reverse solidus) represents a hip or a valley oriented north-west to south-east, or a point adjoined to two of those^
(U+005E circumflex accent) represents a point with two diagonal edges adjoined to it on the southV
(U+0056 latin capital letter v) represents a point with two diagonal edges adjoined to it on the northX
(U+0058 latin capital letter x) represents a point with diagonal edges adjoined to it on all four sides|
(U+007C vertical bar) represents a wall or a ridge oriented vertically (north-south)
Note that it is not possible for an odd number of diagonal edges to end at the same point (except on walls). We can visualize that by partitioning the neighborhood of each point into north slope + south slope and into east slope + west slope. The boundary between both partitions has to be composed of diagonal edges.
If your environment uses a character encoding incompatible with ASCII, you may use the equivalent characters (same glyph or closest available) in the character encoding your environment uses.
The following (ugly) reference implementation in Ruby is normative with respect to the non-whitespace output. Note particularly the render
method:
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
*
. Otherwise that's probably enough. \$\endgroup\$ – mbomb007 Sep 2 '16 at 20:24[[0,1,1],[1,0,1],[1,1,1]]
valid input? (The input has no “holes”, but there's a pesky corner near-self-intersection.) \$\endgroup\$ – Lynn Sep 2 '16 at 20:35