# Is This a Real Tree?

You should write a program or function which receives a string as input and outputs or returns if the input is an ASCII tree.

  _
\/  /
\_/
|
|


ASCII trees consist of characters / \ | _ spaces and newlines.

The non-whitespace characters connect two edge points of their cells by a line segment:

• / connects the bottom left and top right corners
• \ connects the bottom right and top left corners
• | connects the middle points of the bottom edge and top edge
• _ connects the bottom left and bottom right corners and the middle point of the bottom edge

(Note that this means that | can only connect with | or _ but not with / or \.)

An ASCII picture is called a tree if the following rules apply:

• Exactly one point (the root) of exactly one character touches to the bottom edge of the last row.
• You can reach any point of any line segment by:

• starting from the root
• using only the line segments
• never going into a downward direction (not even sideways downward)

## Input

• A string consisting of the characters / \ | _ space and newline containing at least one non-whitespace character.
• You can choose of two input format:

• No unnecessary whitespace around the tree (as seen in the examples).
• No unnecessary whitespace around the tree (as seen in the examples) except spaces on the right side of the rows to make all rows the same length.
• Trailing newline is optional.

## Output

• A consistent truthy value if the input is an ascii tree.
• A consistent falsy value if the input isn't an ascii tree.

## Examples

Valid trees:

|

  _
\/  /
\_/
|
|

/ /    \/
\ \____/
\/
/
/

 \___/
/   \
\___/
|
|

   __/
_/
/

____
\  ___
\ \/
\/\_____/
\/  \/
\__/
|
|


Invalid trees (with extra explanations which are not parts of the inputs):

\/
\_______/
\__   /
| \_/    <- reachable only on with downward route
|

_           <- multiple roots

\/          <- multiple root characters

/\          <- multiple roots

|           <- unreachable part

|

 __/
/           <- unreachable parts
|

\____/
|  |       <- multiple roots

_\__/       <- unreachable parts (_ and \ don't connect to each other)
|


This is code-golf so the shortest entry wins.

# PMA/Snails, 99 93

Prints 1 if it satisfies the "tree" definition or 0 if not. The rectangular space-padded form of input is preferred, although it costs only one byte (using the F option) to convert the ragged version to a space-filled rectangle, which was useful in testing.

&
\ |{(\_|\|)d=\||(\\a7|\/d|\_da7)=\\|(\\d|\/a5|\_da5)=\/|(\_lr|\|d|\/l|\\r)=\_},^_!(r.,^ )d~


Ungolfed, outdated version (for my personal viewing pleasure) :

F&
\ |
{
\_ (lr=\_|da5=\/|da7=\\|d=\|) | \/ (l=\_|a5=\/|d=\\) |
\\ (r=\_|a7=\\|d=\/) | \|d=(\_|\|)
},
^_ !(r.,^ ) d~


This turns out to be fairly well suited to the current language features. Unfortunately, I had to spend a few hours chasing down a reference counting bug before it could work.

The & option means that the match must succeed at every character. From each non-space starting point it checks for a downward path to the bottom. Making a finite state machine with a regex is luckily much shorter by using assertions, here = ... . At the bottom row, it checks that there are no non-space characters to the right.

# Mathematica, 345 300 bytes

Still quite long, but I guess it's a start...

(s=StringSplit;v=Reverse;#=="|"||#=="\\"||#=="/"&[""<>s@#]&&(g={};i=0;(c={i,++j};d={i,j+1/2};e=2d-c;g=Join[g,Switch[#,"|",{d->{1,0}+d},"/",{c->c+1},"\\",{e->{i+1,j}},"_",{c->d,d->e,e->c},_,{}]])&/@Characters[++i;j=0;#]&/@{##};Sort@VertexOutComponent[Graph@g,g[[1,1]]]==Union@@List@@@g)&@@v@s[#,"
"])&


Here is a slightly ungolfed version:

(
s = StringSplit;
v = Reverse;
# == "|" || # == "\\" || # == "/" &[
"" <> s@#
] && (
g = {};
i = 0;
(
c = {i, ++j};
d = {i, j + 1/2};
e = 2 d - c;
g = Join[g, Switch[#,
"|", {d -> {1, 0} + d},
"/", {c -> c + 1},
"\\", {e -> {i + 1, j}},
"_", {c -> d, d -> e, e -> c},
_, {}
]]
) & /@ Characters[
++i;
j = 0;
#
] & /@ {##};
Sort@VertexOutComponent[Graph@g, g[[1, 1]]] ==
Union @@ List @@@ g
) & @@ v@s[#, "\n"]
) &


This defines an unnamed function which takes the string as input and returns True or False.

The basic idea is first to check that there's a single root, and then to build an actual (directed) Graph object to check if all vertices can be reached from the root. Here is how we build the graph:

Imagine an integer grid overlaid onto the ASCII art, where integer coordinates correspond to the corners of the character cells. Then on each of the cells there are six relevant points that can be connected. Here is an example, where I've also labelled the points a to f:

     |                 |
|                 |
---(2,3)---(2.5,3)---(3,2)---
| d      e      f |
|                 |
|                 |
|                 |
|                 |
|                 |
|                 |
| a      b      c |
---(2,2)---(2.5,2)---(3,2)---
|                 |
|                 |


So we can build a graph whose vertices are these half-integer coordinates, and whose edges are determined by the non-space characters in the input. | connects b to e, / connects a to f and \ connects c to d. Note that these must be directed edges to ensure that we're never moving downwards while traversing the graph later. For _ we can go either way, so in theory we need four edges a -> b, b -> a, b -> c, c -> b. However, we can notice that all that matters is that there's a cycle containing all three vertices, so we can shorten this to three edges: a -> b, b -> c, c -> a.

Building this graph is quite simple in Mathematica, because any object can act as a vertex, so I can actually build a graph whose vertices are the coordinate pairs.

Finally, we check that every vertex can be reached from the root. The root's coordinate is easily found as the very first vertex we added to the graph. Then the shortest way I have found to check if all vertices can be reached is to check if the VertexOutComponent of the root (i.e. the set of all vertices reachable from the root) is identical to the set of all vertices in the graph.

• 300 bytes may be long, but exactly 300 is so satisfying! – Alex A. May 11 '15 at 23:02

# Ruby 226 227 228

->i{w=i.index(?\n)+1
t=[i.index(/[^ _] *\n\z/)]
a=->x,c{(i[x]==c||i[x]==?_)&&t<<x}
((x=t.pop)&&(s=x-w;c=i[x])<?0?(a[s+1,?/];a[s,?\\]):c<?]?(a[s-1,?\\];a[s,?/]):c<??(a[x-1,?\\];a[x+1,?/]):a[s,?|]
i[x]=' ')while t!=[]
!i[/\S/]}


Online test: http://ideone.com/Z7TLTt

The program does the following:

• searches for a root (a \, /, or | on the last row)
• starting from that root, climb the tree using the rules and replacing every visited char with a space
• at the end, see if our string is fully composed of whitespace (meaning a valid tree), or not (invalid tree; not all pieces have been "visited")

Here it is ungolfed:

F =-> input {
row_size = input.index(?\n)+1

root_coord = input.index /[^ _] *\n\z/

# coordinates to process
todo = [root_coord]

if input[coord] == char || input[coord] == ?_
todo << coord
end
}

while todo.any?
x = todo.pop

next unless x # exit quickly if no root present

case input[x]
when ?|
when ?_
`