Contexte

Un arbre non étiqueté peut ressembler à ceci:

   o
 / | \
o  o  o
|    / \
o   o   o

Pour linéariser cet arbre, nous étiquetons d'abord chaque nœud oavec son nombre de nœuds enfants:

   3
 / | \
1  0  2
|    / \
0   0   0

puis écrivez les nombres dans une liste d'une manière haletante, ce qui signifie ligne par ligne et de gauche à droite:

[3, 1, 0, 2, 0, 0, 0]

Il s'agit d'une représentation unique et sans ambiguïté de l'arbre ci-dessus, ce qui signifie que deux arbres purs différents n'auront pas les mêmes linéarisations et que nous pouvons reconstruire l'arbre d'origine à partir de la liste.

Bien que chaque arbre corresponde à une certaine liste d'entiers, chaque liste d'entiers ne représente pas un arbre linéarisé valide: par exemple [2, 0, 0, 0]ne représente pas un arbre valide, si nous essayons de le linéariser, nous nous retrouvons avec cet arbre

[2,0,0,0] -> 2 [0,0,0] -> 2 [0,0] -> 2 [0]
            / \          / \        / \
                        0          0   0

mais ont encore une 0gauche dans la liste et nulle part où le mettre. De même [2, 0], la linéarisation d'arbre n'est pas non plus valide, car l'arbre dé-linéarisé a une tache enfant vide:

  2
 / \
0

Tâche

Étant donné une liste entière, décidez s'il s'agit d'une linéarisation valide d'un arbre en utilisant le moins d'octets possible. Vous pouvez écrire un programme complet ou une fonction.

Entrée: une liste non vide d'entiers non négatifs.

Sortie: une valeur vraie si la liste est une linéarisation d'un arbre, une valeur fausse sinon.

Cas de test

[0]
[2, 0, 0]
[1, 1, 1, 1, 1, 0]
[3, 1, 0, 2, 0, 0, 0]
[2, 0, 2, 2, 0, 0, 2, 0, 0]
[3, 2, 2, 1, 1, 1, 0, 0, 0, 0, 0]
[1, 5, 3, 0, 2, 1, 4, 0, 1, 0, 0, 2, 1, 0, 0, 1, 1, 0, 0, 0, 0, 2, 1, 0, 0, 1, 0]

[0, 1]
[2, 0]
[2, 0, 0, 0]
[1, 0, 1]
[3, 2, 1, 0]
[2, 0, 0, 2, 0, 0]
[4, 1, 0, 3, 0, 0, 0, 0]
[4, 2, 0, 3, 1, 0, 0, 0, 0, 0]

Haskell, 44 octets

f[n:k]=iterate f[k]!!n
f _=[]
g x=f[x]==[[]]

Définit une fonction gqui prend une liste et retourne un booléen. Voyez-le passer tous les cas de test .

Explication

Cela repose sur le fait que les linéarisations en profondeur d'abord et en largeur produisent les mêmes tableaux. Voir les réponses de Martin pour plus de détails; fondamentalement, ils donnent tous deux la même condition arithmétique sur le tableau.

La fonction freçoit la liste d'entrée enveloppée dans une liste singleton. Il saute un nombre nde la liste, puis s'appelle nfois sur la liste restante pour traiter les enfants du nœud sauté (profondeur d'abord). Le fait de faire apparaître la liste vide dans [], que j'utilise comme état d'erreur. La fonction gvérifie que le résultat final est [[]], l'état non erroné unique sans noeuds non traités. Si Haskell était faiblement tapé, je pourrais simplement utiliser 0ou quelque chose comme état d'erreur, et je n'aurais pas à envelopper l'entrée dans une autre liste.

Mathematica, 38 octets

Last@#<0<=Min@Most@#&@Accumulate[#-1]&

L'idée de base est que nous gardons une trace d'un certain nombre de nœuds à remplir. Chaque élément de la liste utilise un nœud et en ajoute autant qu'il a d'enfants. Ainsi, chaque élément imodifie le nombre total de i-1. Ce nombre est décalé d'une unité, car il devrait commencer par 1(la racine), non 0.

Pour que l'arbre soit valide, nous a) ne pouvons jamais descendre en bas de 0la liste, car nous n'aurions nulle part où placer le nœud actuel et b) nous devons nous retrouver -1à la fin, sinon il nous reste des nœuds inutilisés.

Nous obtenons ce total cumulé des nœuds restants avec Accumulate[#-1](qui calcule les sommes de préfixe de la liste d'entrée moins un). Et puis on vérifie que le dernier élément et seulement le dernier élément est -1avec:

Last@#<0<=Min@Most@#

Notez que vérifier que le dernier élément est négatif est suffisant, car nous ne pouvons jamais décrémenter de plus de 1, donc si les dernières valeurs étaient -2ou inférieures, il serait impossible pour le minimum que les autres ne soient pas négatifs.

Rétine , 29 octets

\d+
$*
^(?<-1>(1)*,)*$(?(1)!)

Essayez-le en ligne! (La première ligne active une suite de tests séparés par un saut de ligne.)

Explication

L'idée de base est la même que celle de ma réponse Mathematica : nous gardons une trace d'un total cumulé de nœuds restants, garantissons qu'il ne descend jamais en dessous de zéro mais se termine sur zéro. Cependant, la façon dont cela est implémenté avec regex est très différente.

\d+
$*

Cela convertit simplement l'entrée en unaire, transformant chaque entier nen n1s.

^(?<-1>(1)*,)*$(?(1)!)

C'est là que la vraie magie opère. C'est une expression régulière assez courte qui ne correspond qu'à des arbres valides, mais sa mécanique est assez subtile.

J'utilise des groupes d'équilibrage pour garder une trace du nombre de nœuds, qui sont un moyen de travailler avec des piles à l'intérieur de l'expression régulière.

Tout d'abord, bien sûr, une telle pile ne peut jamais avoir une profondeur négative, donc nous ne pouvons pas vraiment nous retrouver avec une représentation de -1la fin, comme nous le faisons dans la solution Mathematica. Cependant, nous pouvons noter que l'élément final de l'entrée doit être zéro sur une pile valide (sinon nous ne pourrions pas nous retrouver avec -1). Il s'avère qu'il enregistre réellement des octets pour vérifier à la fois que nous terminons sur zéro et avec zéro nœuds restants.

Voici donc une ventilation de l'expression régulière:

^        e# Anchor the match to the beginning of the string.
(?<-1>   e# Each repetition of this group will match one number. 
         e# We can ignore the <-1> for now.
  (1)*   e#   Match each unary digit of the current number, pushing
         e#   a capture onto stack 1. This increments our total of
         e#   remaining nodes by 1 for each child.
  ,      e#   Match a comma. Note that this requires that there is at
         e#   least one more number in the list.
)*       e# At the end of the repetition the <-1> pops one capture from
         e# the stack. This is the node that the current number itself
         e# takes up.
$        e# Match the end of the string. This requires the input to end
         e# in a zero, because the last thing we matched was a comma.
(?(1)!)  e# Make sure that stack 1 is empty, so that we don't have any
         e# unused nodes.

CJam (20 octets)

{X0@{+\(_0>{\}*}/|!}

Suite de tests en ligne . Il s'agit d'un bloc anonyme qui prend un tableau sur la pile et laisse 0 ou 1 sur la pile.

Dissection

En pseudocode, c'est:

p = 1
q = 0
foreach (i in input):
  q += i
  if (--p <= 0):      # in practice, if (--p == 0):
      p, q = q, p
return (p | q) == 0   # i.e. p == 0 && q == 0

qaccumule la somme des étiquettes des nœuds au niveau actuel dans l'arbre; pdécompte les nœuds restant dans le niveau actuel.

Labyrinthe , 17 octets

(
+?
;-)
,_"
@@,!

Essayez-le en ligne!

La sortie -1vraie est la sortie fausse est vide. Définir le vrai et le faux dans le Labyrinthe est un peu délicat, car les branches du Labyrinthe sont principalement ternaires. Cependant, la seule façon de construire un conditionnel avec deux branches fiables, vous ne pouvez que le faire:

>"F
 T

Dans ce cas, j'envisagerais d'avancer droit devant la fausseté (car la direction du mouvement n'est pas affectée) et de devenir véridique. Celles-ci correspondent respectivement à zéro et non nul. La raison pour laquelle j'utilise une sortie vide pour représenter zéro est que, si vous redirigez la sortie vers un autre programme Labyrinth, l'opérateur d'entrée ?poussera en fait un zéro si l'entrée est vide, donc je considère que la chaîne vide est valide représentation de zéro.

Explication

L'algorithme est toujours le même que dans mes réponses Mathematica et Retina, mais en raison du flux de contrôle de Labyrinth, il fonctionne un peu différemment cette fois:

• Ici, nous ne travaillons pas avec le compteur total un par un. Au lieu de cela, nous a) travaillons avec un compteur négatif et b) l'initialisons -11initialement, de sorte que nous voulons que le compteur soit négatif dans toute la liste et que nous frappions zéro sur la dernière entrée. Cela simplifie en fait le flux de contrôle ici.

• Au lieu de construire la liste complète et de vérifier si elle contient la mauvaise valeur, il y a trois conditions de résiliation possibles:

  1. Nous avons atteint EOF avant d'atteindre un compte total de zéro. Dans ce cas, il reste des nœuds inutilisés et nous n'imprimons rien.
  2. Nous atteignons zéro et nous sommes à l'EOF. Dans ce cas, nous avons un arbre valide.
  3. Nous atteignons zéro et ne sommes pas encore à l'EOF. Dans ce cas, nous avons manqué de nœuds avant de couvrir tous les éléments et nous n'imprimons rien.

Quant au code réel, nous commençons dans le coin supérieur gauche. Le (transforme le zéro implicite au-dessus de la pile en un -1, qui sera le total cumulé. On entre alors dans la boucle principale très serrée du programme +?-)"_,;+,:

+   Add the top two values. This does nothing on the first iteration,
    but gets rid of a helper-zero on subsequent iterations.
?   Read and push integer.
-   Subtract it from running total.
)   Increment.
"   No-op. There is a branch at this point. If the running total is zero,
    we move straight ahead onto the , (see below). Otherwise, the loop continues.
_   Push a zero. This is necessary to prevent the IP from turning south.
,   Read a character. This will either be the next separator (some positive
    number) or EOF (-1). If it's EOF, the IP turns south and the program
    terminates. Otherwise, the loop continues.
;   Discard the separator.

Cela ne laisse que les cas où nous avons réduit le total cumulé à zéro à un moment donné. L'IP se déplace en bas à droite ,et lit un autre caractère pour vérifier si nous avons atteint EOF. Sinon, la valeur sera positive et l'IP se tournera vers l'ouest vers le @et le programme se terminera. Si nous avons atteint EOF, l'IP tourne vers l'est et imprime le -1avec !. L'IP se dirigera ensuite vers le coin inférieur gauche @via un chemin légèrement étrange pour terminer le programme.

Python, 82 octets

lambda l:len(l)==sum(l)+1 and not any(list(l[x]>=len(l)-x for x in range(len(l))))

Besoin de plus de cas de test.

Pyth, 13 octets

qxsM._tMQ_1tl

Nous commençons par calculer le remplissage actuel de l'arbre à tous les points de la représentation d'entrée. Cette partie de l'idée est en grande partie empruntée à Martin Ender, donc grâce à lui.sM._tMQ

Une fois que nous avons cette liste, nous vérifions si le premier index contenant -1( x..._1) est la longueur de l'entrée moins un ( q...tl(Q)).

Vous ne croyez pas que cela fonctionne? Essayez-le vous-même!