Powinieneś napisać program lub funkcję, która odbiera ciąg znaków jako dane wejściowe i wyjściowe lub zwraca, jeśli dane wejściowe są drzewem ASCII.

  _
\/  /
 \_/
  |
  |

Drzewa ASCII składają się z znaków / \ | _ spacesi newlines.

Nie-białe znaki łączą dwa punkty krawędzi ich komórek za pomocą segmentu linii:

• / łączy lewy dolny i prawy górny róg
• \ łączy prawy dolny i górny lewy róg
• | łączy środkowe punkty dolnej i górnej krawędzi
• _ łączy lewy dolny i prawy dolny róg ze środkowym punktem dolnej krawędzi

(Należy pamiętać, że oznacza to, że |może łączyć się tylko z |albo _, ale nie z /lub \.)

Obraz ASCII jest nazywany drzewem, jeśli mają zastosowanie następujące reguły:

• Dokładnie jeden punkt (pierwiastek) dokładnie jednego znaku dotyka dolnej krawędzi ostatniego rzędu.

• Możesz dotrzeć do dowolnego punktu dowolnego segmentu linii poprzez:

  • zaczynając od korzenia
  • używając tylko segmentów linii
  • nigdy nie idąc w dół (nawet w dół w dół)

Wejście

• Ciąg znaków składający się ze znaków / \ | _ spacei newlinezawierający co najmniej jeden znak spacji.

• Możesz wybrać dwa formaty wejściowe:

  • Brak zbędnych białych znaków wokół drzewa (jak pokazano w przykładach).
  • Żadnych niepotrzebnych białych znaków wokół drzewa (jak pokazano w przykładach), z wyjątkiem spacji po prawej stronie rzędów, aby wszystkie rzędy miały tę samą długość.

• Końcowy znak nowej linii jest opcjonalny.

Wynik

• Spójna prawdziwa wartość, jeśli dane wejściowe są drzewem ascii.
• Spójne falsy wartość jeśli wejście nie jest drzewo ASCII.

Przykłady

Prawidłowe drzewa:

|

  _
\/  /
 \_/
  |
  |

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

 \___/
 /   \
 \___/
   |
   |

   __/
 _/
/

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

Nieprawidłowe drzewa (z dodatkowymi objaśnieniami, które nie stanowią części danych wejściowych):

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

To jest golf golfowy, więc wygrywa najkrótszy wpis.

PMA / Snails , 99 93

Drukuje 1, jeśli spełnia definicję „drzewa” lub 0, jeśli nie. Preferowana jest prostokątna, wypełniona spacją forma wprowadzania danych, chociaż kosztuje tylko jeden bajt (przy użyciu Fopcji), aby przekonwertować poszarpaną wersję na wypełniony spacją prostokąt, co było przydatne w testowaniu.

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

Niegolfowana, nieaktualna wersja (dla mojej osobistej przyjemności oglądania):

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

Okazuje się, że dość dobrze pasuje do obecnych funkcji językowych. Niestety musiałem spędzić kilka godzin, szukając błędu liczenia referencji, zanim zadziała.

Ta &opcja oznacza, że ​​dopasowanie musi zakończyć się każdą postacią. Z każdego niepoczątkowego punktu początkowego sprawdza ścieżkę do dołu. Tworzenie skończonej maszyny stanów za pomocą wyrażenia regularnego jest na szczęście znacznie krótsze przy użyciu asercji, tutaj =... W dolnym rzędzie sprawdza, czy po prawej stronie nie ma znaków spacji.

Mathematica, 345 300 bajtów

Wciąż dość długo, ale myślę, że to początek ...

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

Oto nieco niestosowana wersja:

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

Definiuje nienazwaną funkcję, która przyjmuje ciąg znaków jako dane wejściowe i zwraca Truelub False.

Podstawową ideą jest najpierw sprawdzenie, czy istnieje jeden root, a następnie zbudowanie rzeczywistego (ukierunkowanego) Graphobiektu, aby sprawdzić, czy wszystkie wierzchołki są dostępne z roota. Oto jak budujemy wykres:

Wyobraź sobie siatkę liczb całkowitych nałożoną na grafikę ASCII, w której współrzędne liczbowe odpowiadają rogom komórek znakowych. Następnie na każdej komórce jest sześć odpowiednich punktów, które można połączyć. Oto przykład, w którym oznaczyłem również punkty ado f:

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

Możemy więc zbudować wykres, którego wierzchołkami są te współrzędne połowy liczb całkowitych i których krawędzie są określone przez znaki spacji na wejściu. |łączy bdo e, /łączy ado fi \łączy cdo d. Pamiętaj, że muszą to być skierowane krawędzie, aby nigdy nie przesuwać się w dół podczas przechodzenia przez wykres później. Dla _możemy pójść w obu kierunkach, więc teoretycznie musimy cztery krawędzie a -> b, b -> a, b -> c, c -> b. Można jednak zauważyć, że wszystko, co się liczy, to, że nie jest to cykl zawierający wszystkie trzy wierzchołki, więc możemy skrócić to do trzech krawędziach: a -> b, b -> c, c -> a.

Budowanie tego wykresu jest w Mathematica dość proste, ponieważ każdy obiekt może działać jako wierzchołek, więc mogę zbudować wykres, którego wierzchołki są parami współrzędnych.

Na koniec sprawdzamy, czy do każdego wierzchołka można dotrzeć z katalogu głównego. Współrzędną pierwiastka można łatwo znaleźć jako pierwszy wierzchołek, który dodaliśmy do wykresu. Następnie najkrótszym sposobem, jaki znalazłem, aby sprawdzić, czy wszystkie wierzchołki są osiągalne, jest sprawdzenie, czy VertexOutComponentzrootowany (tj. Zbiór wszystkich wierzchołków osiągalny z rdzenia) jest identyczny z zestawem wszystkich wierzchołków na wykresie.

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

Test online: http://ideone.com/Z7TLTt

Program wykonuje następujące czynności:

• wyszukuje korzenia (A \, /albo |na ostatnim rzędzie)
• zaczynając od tego korzenia, wspinaj się na drzewo zgodnie z zasadami i zastępując każdego odwiedzonego chara spacją
• na końcu sprawdź, czy nasz łańcuch jest w pełni złożony z białych znaków (co oznacza prawidłowe drzewo), czy nie (nieprawidłowe drzewo; nie wszystkie elementy zostały „odwiedzone”)

Tutaj nie jest golfem:

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