Sie sollten ein Programm oder eine Funktion schreiben, die eine Zeichenfolge als Eingabe empfängt und ausgibt oder zurückgibt, wenn die Eingabe ein ASCII-Baum ist.

  _
\/  /
 \_/
  |
  |

ASCII-Bäume bestehen aus Zeichen / \ | _ spacesund newlines.

Die Nicht-Leerzeichen verbinden zwei Randpunkte ihrer Zellen durch ein Liniensegment:

• / Verbindet die untere linke und obere rechte Ecke
• \ Verbindet die unteren rechten und oberen linken Ecken
• | verbindet die Mittelpunkte von Unterkante und Oberkante
• _ Verbindet die untere linke und die untere rechte Ecke mit dem Mittelpunkt der unteren Kante

(Beachten Sie, dass dies bedeutet, dass |nur eine Verbindung mit |oder hergestellt werden kann _, nicht jedoch mit /oder \.)

Ein ASCII-Bild wird als Baum bezeichnet, wenn folgende Regeln gelten:

• Genau ein Punkt (die Wurzel) genau eines Zeichens berührt den unteren Rand der letzten Zeile.

• Sie können jeden Punkt eines Liniensegments erreichen, indem Sie:

  • ausgehend von der Wurzel
  • Verwenden Sie nur die Liniensegmente
  • niemals in eine abwärts gerichtete Richtung gehen (nicht einmal seitwärts abwärts)

Eingang

• Eine Zeichenfolge, die aus den Zeichen besteht / \ | _ spaceund newlinemindestens ein Nicht-Leerzeichen enthält.

• Sie können zwischen zwei Eingabeformaten wählen:

  • Kein unnötiger Leerraum um den Baum (wie in den Beispielen zu sehen).
  • Keine unnötigen Leerzeichen um den Baum (wie in den Beispielen gezeigt) außer Leerzeichen auf der rechten Seite der Zeilen, um alle Zeilen gleich lang zu machen.

• Der Zeilenumbruch ist optional.

Ausgabe

• Ein konsistenter Wahrheitswert , wenn die Eingabe ein ASCII-Baum ist.
• Ein konsistenter falscher Wert, wenn die Eingabe kein ASCII-Baum ist.

Beispiele

Gültige Bäume:

|

  _
\/  /
 \_/
  |
  |

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

 \___/
 /   \
 \___/
   |
   |

   __/
 _/
/

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

Ungültige Bäume (mit zusätzlichen Erklärungen, die nicht Teil der Eingaben sind):

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

Dies ist Code-Golf, also gewinnt der kürzeste Eintrag.

PMA / Snails , 99 93

Gibt 1 aus, wenn die "Baum" -Definition erfüllt ist, oder 0, wenn dies nicht der Fall ist. Die rechteckige, mit Leerzeichen aufgefüllte Form der Eingabe wird bevorzugt, obwohl die FKonvertierung der zerlumpten Version in ein mit Leerzeichen gefülltes Rechteck nur ein Byte (mithilfe der Option) kostet , was beim Testen hilfreich war.

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

Ungolfed, veraltete Version (für mein persönliches Sehvergnügen):

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

Dies stellt sich für die aktuellen Sprachfunktionen als ziemlich gut geeignet heraus. Leider musste ich ein paar Stunden damit verbringen, einen Referenzzählfehler aufzuspüren, bevor er funktionieren konnte.

Die &Option bedeutet, dass die Übereinstimmung bei jedem Zeichen erfolgreich sein muss. Von jedem Nicht-Leerzeichen-Startpunkt aus wird nach einem Abwärtspfad nach unten gesucht. Die Erstellung einer endlichen Zustandsmaschine mit einem regulären Ausdruck ist glücklicherweise viel kürzer, wenn man Behauptungen verwendet, hier =.... In der unteren Zeile wird überprüft, ob rechts keine Nicht-Leerzeichen stehen.

Mathematica, 345 300 Bytes

Immer noch ziemlich lang, aber ich denke, es ist ein Anfang ...

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

Hier ist eine leicht ungolfederte 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"]
) &

Dies definiert eine unbenannte Funktion, die den String als Eingabe nimmt und Trueoder zurückgibt False.

Die Grundidee besteht darin, zuerst zu überprüfen, ob es eine einzelne Wurzel gibt, und dann ein tatsächliches (gerichtetes) GraphObjekt zu erstellen, um zu überprüfen, ob alle Eckpunkte von der Wurzel aus erreicht werden können. So erstellen wir das Diagramm:

Stellen Sie sich ein ganzzahliges Raster vor, das über die ASCII-Grafik gelegt wird, wobei ganzzahlige Koordinaten den Ecken der Zeichenzellen entsprechen. Dann gibt es auf jeder der Zellen sechs relevante Punkte, die verbunden werden können. Hier ist ein Beispiel, wo ich auch die Punkte markiert haben azu f:

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

Wir können also ein Diagramm erstellen, dessen Scheitelpunkte diese halben Ganzzahlkoordinaten sind und dessen Kanten durch die Nicht-Leerzeichen in der Eingabe bestimmt werden. |verbindet sich bmit e, /verbindet sich amit fund \verbindet sich cmit d. Beachten Sie, dass dies gerichtete Kanten sein müssen, um sicherzustellen, dass wir uns beim späteren Durchlaufen des Diagramms niemals nach unten bewegen. Denn _wir in beiden Richtungen gehen können, so in der Theorie benötigen wir vier Kanten a -> b, b -> a, b -> c, c -> b. Allerdings können wir feststellen , dass alles, was zählt ist , dass es ein Zyklus ist , alle drei Scheitelpunkte enthalten, so dass wir diese drei Kanten verkürzen können: a -> b, b -> c,c -> a .

Diese Grafik zu bauen ist recht einfach in Mathematica, weil jeder Gegenstand als Vertex wirken kann, so dass ich tatsächlich einen Graphen , dessen Eckpunkte aufbauen können sind die Koordinatenpaare.

Schließlich prüfen wir, ob jeder Scheitelpunkt von der Wurzel aus erreichbar ist. Die Wurzelkoordinate wird leicht als der allererste Scheitelpunkt gefunden, den wir dem Diagramm hinzugefügt haben. Dann ist der kürzeste Weg, den ich gefunden habe, um zu prüfen, ob alle Eckpunkte erreicht werden können, zu prüfen, ob die VertexOutComponentWurzel (dh die Menge aller von der Wurzel aus erreichbaren Eckpunkte) mit der Menge aller Eckpunkte im Diagramm identisch ist.

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

Das Programm macht folgendes:

• Suchen nach einer Wurzel (a \, /oder| in der letzten Zeile)
• Steige von dieser Wurzel aus nach den Regeln auf den Baum und ersetze jeden besuchten Saibling durch ein Leerzeichen
• Am Ende wird geprüft, ob unsere Zeichenfolge vollständig aus Leerzeichen besteht (dh einem gültigen Baum) oder nicht (ungültiger Baum; nicht alle Teile wurden "besucht").

Hier ist es 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 < ?*
}