Debe escribir un programa o función que reciba una cadena como entrada y produzca o devuelva si la entrada es un árbol ASCII.

  _
\/  /
 \_/
  |
  |

Los árboles ASCII consisten en caracteres / \ | _ spacesy newlines.

Los caracteres que no son espacios en blanco conectan dos puntos de borde de sus celdas por un segmento de línea:

• / conecta las esquinas inferiores izquierda y superior derecha
• \ conecta las esquinas inferiores derecha e superior izquierda
• | conecta los puntos medios del borde inferior y el borde superior
• _ conecta las esquinas inferiores izquierda e inferior derecha y el punto medio del borde inferior

(Tenga en cuenta que esto significa que |solo puede conectarse con |o _pero no con /o \).

Una imagen ASCII se llama árbol si se aplican las siguientes reglas:

• Exactamente un punto (la raíz) de exactamente un carácter toca el borde inferior de la última fila.

• Puede llegar a cualquier punto de cualquier segmento de línea:

  • a partir de la raíz
  • usando solo los segmentos de línea
  • nunca ir hacia abajo (ni siquiera de lado hacia abajo)

Entrada

• Una cadena que consta de los caracteres / \ | _ spacey que newlinecontiene al menos un carácter que no es un espacio en blanco.

• Puede elegir entre dos formatos de entrada:

  • No hay espacios en blanco innecesarios alrededor del árbol (como se ve en los ejemplos).
  • No hay espacios en blanco innecesarios alrededor del árbol (como se ve en los ejemplos) excepto espacios en el lado derecho de las filas para hacer que todas las filas tengan la misma longitud.

• La nueva línea final es opcional.

Salida

• Un valor de verdad consistente si la entrada es un árbol ascii.
• Un valor falso falso si la entrada no es un árbol ascii.

Ejemplos

Árboles válidos:

|

  _
\/  /
 \_/
  |
  |

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

 \___/
 /   \
 \___/
   |
   |

   __/
 _/
/

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

Árboles no válidos (con explicaciones adicionales que no son partes de las 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)
|

Este es el código de golf por lo que gana la entrada más corta.

PMA / Caracoles , 99 93

Imprime 1 si cumple con la definición de "árbol" o 0 si no. Se prefiere la forma rectangular de entrada con relleno de espacio, aunque solo cuesta un byte (usando la Fopción) para convertir la versión irregular en un rectángulo lleno de espacio, lo que fue útil en las pruebas.

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

Versión desactualizada y sin golf (para mi placer visual personal):

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

Esto resulta ser bastante adecuado para las características del lenguaje actual. Desafortunadamente, tuve que pasar algunas horas persiguiendo un error de conteo de referencias antes de que pudiera funcionar.

La &opción significa que la partida debe tener éxito en cada personaje. Desde cada punto de partida no espacial, verifica una ruta descendente hacia el fondo. Hacer una máquina de estados finitos con una expresión regular es afortunadamente mucho más corto mediante el uso de aserciones, aquí =.... En la fila inferior, verifica que no haya caracteres que no sean espacios a la derecha.

Mathematica, 345 300 bytes

Todavía es bastante largo, pero supongo que es un comienzo ...

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

Aquí hay una versión ungolfed:

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

Esto define una función sin nombre que toma la cadena como entrada y devuelve Trueo False.

La idea básica es primero verificar que haya una sola raíz, y luego construir un objeto real (dirigido) Graphpara verificar si se puede alcanzar todos los vértices desde la raíz. Así es como construimos el gráfico:

Imagine una cuadrícula entera superpuesta sobre el arte ASCII, donde las coordenadas enteras corresponden a las esquinas de las celdas de caracteres. Luego, en cada una de las celdas hay seis puntos relevantes que se pueden conectar. Aquí hay un ejemplo, donde también he etiquetado los puntos aa f:

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

Por lo tanto, podemos construir un gráfico cuyos vértices sean estas coordenadas de medio entero y cuyos bordes estén determinados por los caracteres no espaciales en la entrada. |Conexiones ba e, /se conecta aa fy \se conecta ca d. Tenga en cuenta que estos deben ser bordes dirigidos para garantizar que nunca nos movemos hacia abajo mientras atravesamos el gráfico más tarde. Para _que podamos ir en cualquier dirección, por lo que, en teoría, necesitamos cuatro bordes a -> b, b -> a, b -> c, c -> b. Sin embargo, podemos notar que lo único que importa es que hay un ciclo que contiene los tres vértices, por lo que podemos acortar este a tres aristas: a -> b, b -> c, c -> a.

Construir este gráfico es bastante simple en Mathematica, porque cualquier objeto puede actuar como un vértice, por lo que en realidad puedo construir un gráfico cuyos vértices son los pares de coordenadas.

Finalmente, verificamos que se puede llegar a cada vértice desde la raíz. La coordenada de la raíz se encuentra fácilmente como el primer vértice que agregamos al gráfico. Entonces, la forma más corta que he encontrado para verificar si se pueden alcanzar todos los vértices es verificar si el VertexOutComponentde la raíz (es decir, el conjunto de todos los vértices accesibles desde la raíz) es idéntico al conjunto de todos los vértices en el gráfico.

Rubí 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/]}

Prueba en línea: http://ideone.com/Z7TLTt

El programa hace lo siguiente:

• búsquedas de una raíz (una \, /o |en la última fila)
• comenzando desde esa raíz, trepa al árbol usando las reglas y reemplazando cada char visitado por un espacio
• al final, vea si nuestra cadena está completamente compuesta de espacios en blanco (es decir, un árbol válido) o no (árbol no válido; no todas las piezas han sido "visitadas")

Aquí no tiene golf:

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 < ?*
}