Você deve escrever um programa ou função que receba uma string como entrada e saia ou retorne se a entrada for uma árvore ASCII.

  _
\/  /
 \_/
  |
  |

As árvores ASCII consistem em caracteres / \ | _ spacese newlines.

Os caracteres que não são de espaço em branco conectam dois pontos de extremidade de suas células por um segmento de linha:

• / conecta os cantos inferior esquerdo e superior direito
• \ conecta os cantos inferior direito e superior esquerdo
• | conecta os pontos médios da borda inferior e superior
• _ conecta os cantos inferior esquerdo e inferior direito e o ponto médio da borda inferior

(Observe que isso significa que |só pode conectar-se com |ou _mas não com /ou \.)

Uma imagem ASCII é chamada de árvore se as seguintes regras se aplicarem:

• Exatamente um ponto (a raiz) de exatamente um caractere toca na borda inferior da última linha.

• Você pode alcançar qualquer ponto de qualquer segmento de linha:

  • começando da raiz
  • usando apenas os segmentos de linha
  • nunca indo em direção descendente (nem de lado para baixo)

Entrada

• Uma sequência que consiste nos caracteres / \ | _ spacee newlinecontém pelo menos um caractere que não é um espaço em branco.

• Você pode escolher entre dois formatos de entrada:

  • Não há espaço em branco desnecessário ao redor da árvore (como visto nos exemplos).
  • Não há espaço em branco desnecessário ao redor da árvore (como visto nos exemplos), exceto espaços no lado direito das linhas para tornar todas as linhas do mesmo comprimento.

• A nova linha à direita é opcional.

Saída

• Um valor de verdade consistente se a entrada for uma árvore ascii.
• Um valor falso consistente se a entrada não for uma árvore ascii.

Exemplos

Árvores válidas:

|

  _
\/  /
 \_/
  |
  |

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

 \___/
 /   \
 \___/
   |
   |

   __/
 _/
/

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

Árvores inválidas (com explicações extras que não fazem parte das entradas):

\/
 \_______/
  \__   /
   | \_/    <- 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)
|

Isso é código-golfe, portanto a entrada mais curta vence.

PMA / Caracóis , 99 93

Imprime 1 se estiver de acordo com a definição da "árvore" ou 0 se não estiver. A forma retangular de entrada preenchida com espaço é preferida, embora custe apenas um byte (usando a Fopção) para converter a versão irregular em um retângulo preenchido com espaço, o que foi útil nos testes.

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

Versão desatualizada e desatualizada (para meu prazer pessoal):

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

Isso acaba sendo bastante adequado aos recursos de idioma atuais. Infelizmente, tive que passar algumas horas perseguindo um bug de contagem de referência antes que ele pudesse funcionar.

A &opção significa que a partida deve ter sucesso em todos os personagens. A partir de cada ponto de partida que não seja espaço, ele procura um caminho descendente até o final. Felizmente, fazer uma máquina de estados finitos com uma regex é muito mais curto usando asserções, aqui =.... Na linha inferior, ele verifica se não há caracteres que não sejam espaços à direita.

Mathematica, 345 300 bytes

Ainda muito longo, mas acho que é um começo ...

(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[#,"
"])&

Aqui está uma versão ligeiramente não-destruída:

(
  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"]
) &

Isso define uma função sem nome que recebe a string como entrada e retorna Trueou False.

A idéia básica é primeiro verificar se existe uma única raiz e depois criar um Graphobjeto real (direcionado) para verificar se todos os vértices podem ser alcançados a partir da raiz. Aqui está como construímos o gráfico:

Imagine uma grade inteira sobreposta à arte ASCII, em que as coordenadas inteiras correspondem aos cantos das células de caracteres. Em cada uma das células, existem seis pontos relevantes que podem ser conectados. Aqui está um exemplo, onde eu também rotulei os pontos apara f:

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

Assim, podemos construir um gráfico cujos vértices são essas coordenadas semi-inteiras e cujas bordas são determinadas pelos caracteres que não são espaços na entrada. |Ligações bpara e, /Ligações apara fe \se conecta ca d. Observe que essas bordas devem ser direcionadas para garantir que nunca nos movamos para baixo enquanto percorremos o gráfico posteriormente. Para _nós podemos ir de qualquer maneira, por isso, em teoria, precisamos de quatro bordas a -> b, b -> a, b -> c, c -> b. No entanto, podemos perceber que tudo o que importa é que há um ciclo que contém todos os três vértices, para que possamos encurtar isso para três arestas: a -> b, b -> c, c -> a.

Construir esse gráfico é bastante simples no Mathematica, porque qualquer objeto pode atuar como um vértice, para que eu possa construir um gráfico cujos vértices sejam os pares de coordenadas.

Finalmente, verificamos que todos os vértices podem ser alcançados a partir da raiz. A coordenada da raiz é facilmente encontrada como o primeiro vértice que adicionamos ao gráfico. Então, a maneira mais curta que encontrei para verificar se todos os vértices podem ser alcançados é verificar se o VertexOutComponentda raiz (ou seja, o conjunto de todos os vértices alcançáveis ​​a partir da raiz) é idêntico ao conjunto de todos os vértices no gráfico.

Rubi 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/]}

Teste on-line: http://ideone.com/Z7TLTt

O programa faz o seguinte:

• pesquisas para uma raiz (uma \, /ou |sobre a última linha)
• a partir dessa raiz, suba na árvore usando as regras e substituindo cada caractere visitado por um espaço
• no final, veja se nossa string é totalmente composta de espaço em branco (ou seja, uma árvore válida) ou não (árvore inválida; nem todas as peças foram "visitadas")

Aqui é ungolfed:

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

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

  # coordinates to process
  todo = [root_coord]

  add_todo = -> coord, char{
    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 ?|
      add_todo[x - row_size, ?|]
    when ?_
      add_todo[x - 1, ?\\]
      add_todo[x + 1, ?/]
    when ?/
      add_todo[x - row_size + 1, ?/]
      add_todo[x - row_size, ?\\]
    when ?\\
      add_todo[x - row_size - 1, ?\\]
      add_todo[x - row_size, ?/]
    end
    input[x]=' '
  end
  input.strip < ?*
}