Vous devez écrire un programme ou une fonction qui reçoit une chaîne en entrée et sort ou renvoie si l'entrée est une arborescence ASCII.

  _
\/  /
 \_/
  |
  |

Les arbres ASCII se composent de caractères / \ | _ spaceset newlines.

Les caractères non blancs relient deux points de bord de leurs cellules par un segment de ligne:

• / relie les coins inférieur gauche et supérieur droit
• \ relie les coins inférieur droit et supérieur gauche
• | relie les points médians du bord inférieur et du bord supérieur
• _ relie les coins inférieur gauche et inférieur droit et le point médian du bord inférieur

(Notez que cela signifie que |vous ne pouvez vous connecter qu'avec |ou _mais pas avec /ou \.)

Une image ASCII est appelée un arbre si les règles suivantes s'appliquent:

• Exactement un point (la racine) d'un caractère exactement touche le bord inférieur de la dernière ligne.

• Vous pouvez atteindre n'importe quel point de n'importe quel segment de ligne en:

  • à partir de la racine
  • en utilisant uniquement les segments de ligne
  • ne jamais aller vers le bas (même pas latéralement vers le bas)

Contribution

• Une chaîne composée des caractères / \ | _ spaceet newlinecontenant au moins un caractère non blanc.

• Vous pouvez choisir entre deux formats d'entrée:

  • Aucun espace inutile autour de l'arbre (comme le montrent les exemples).
  • Aucun espace inutile autour de l'arborescence (comme illustré dans les exemples) à l'exception des espaces sur le côté droit des lignes pour rendre toutes les lignes de la même longueur.

• Le retour à la ligne est facultatif.

Production

• Une valeur véridique cohérente si l'entrée est un arbre ascii.
• Une valeur de falsification cohérente si l'entrée n'est pas un arbre ascii.

Exemples

Arbres valides:

|

  _
\/  /
 \_/
  |
  |

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

 \___/
 /   \
 \___/
   |
   |

   __/
 _/
/

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

Arbres non valides (avec des explications supplémentaires qui ne font pas partie des entrées):

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

Il s'agit de code-golf, donc l'entrée la plus courte l'emporte.

PMA / Escargots , 99 93

Imprime 1 s'il satisfait à la définition "d'arbre" ou 0 sinon. La forme rectangulaire d'entrée remplie d'espace est préférée, bien qu'elle ne coûte qu'un octet (en utilisant l' Foption) pour convertir la version irrégulière en un rectangle rempli d'espace, ce qui était utile pour les tests.

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

Version obsolète et obsolète (pour mon plaisir de visionnement personnel):

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

Cela s'avère assez bien adapté aux fonctionnalités actuelles du langage. Malheureusement, j'ai dû passer quelques heures à rechercher un bogue de comptage de référence avant qu'il ne puisse fonctionner.

L' &option signifie que la correspondance doit réussir à chaque personnage. À partir de chaque point de départ non spatial, il recherche un chemin vers le bas vers le bas. Faire une machine à états finis avec une expression rationnelle est heureusement beaucoup plus court en utilisant des assertions, ici =.... Dans la ligne du bas, il vérifie qu'il n'y a pas de caractère non espace à droite.

Mathematica, 345 300 octets

Encore assez long, mais je suppose que c'est un début ...

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

Voici une version légèrement non golfée:

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

Ceci définit une fonction sans nom qui prend la chaîne en entrée et renvoie Trueou False.

L'idée de base est d'abord de vérifier qu'il n'y a qu'une seule racine, puis de construire un objet réel (dirigé) Graphpour vérifier si tous les sommets peuvent être atteints à partir de la racine. Voici comment nous construisons le graphique:

Imaginez une grille entière superposée à l'art ASCII, où les coordonnées entières correspondent aux coins des cellules des caractères. Ensuite, sur chacune des cellules, il y a six points pertinents qui peuvent être connectés. Voici un exemple, où je l' ai aussi étiquetée points aà f:

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

Nous pouvons donc construire un graphe dont les sommets sont ces coordonnées demi-entières, et dont les arêtes sont déterminées par les caractères non-espace dans l'entrée. |se connecte bàe , se /connecte aà fet se \connecte cà d. Notez que ceux-ci doivent être dirigés vers les bords pour garantir que nous ne descendons jamais en traversant le graphique plus tard. Pour que _nous pouvons aller de toute façon, donc en théorie nous avons besoin de quatre arêtes a -> b, b -> a, b -> c, c -> b. Cependant, on peut remarquer que tout ce qui compte est qu'il ya un cycle contenant les trois sommets, donc nous pouvons raccourcir ce à trois arêtes: a -> b, b -> c, c -> a.

La construction de ce graphique est assez simple dans Mathematica, car n'importe quel objet peut agir comme un sommet, donc je peux réellement construire un graphique dont les sommets sont les paires de coordonnées.

Enfin, nous vérifions que chaque sommet peut être atteint depuis la racine. La coordonnée de la racine est facilement trouvée comme le tout premier sommet que nous avons ajouté au graphique. Ensuite, le moyen le plus court que j'ai trouvé pour vérifier si tous les sommets peuvent être atteints est de vérifier si le VertexOutComponentde la racine (c'est-à-dire l'ensemble de tous les sommets accessibles depuis la racine) est identique à l'ensemble de tous les sommets du graphique.

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

Test en ligne: http://ideone.com/Z7TLTt

Le programme fait ce qui suit:

• recherche une racine (un \, /ou |sur la dernière ligne)
• à partir de cette racine, grimpez dans l'arbre en suivant les règles et remplacez chaque char visité par un espace
• à la fin, voyez si notre chaîne est entièrement composée d'espaces (signifiant un arbre valide), ou non (arbre invalide; toutes les pièces n'ont pas été "visitées")

Ici, il n'est pas 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 < ?*
}