fundo
Uma árvore não rotulada pode ser assim:
o
/ | \
o o o
| / \
o o o
Para linearizar essa árvore, primeiro rotulamos cada nó o
com seu número de nós filhos:
3
/ | \
1 0 2
| / \
0 0 0
e, em seguida, escreva os números em uma lista da maneira mais rápida possível, significando linha por linha e da esquerda para a direita:
[3, 1, 0, 2, 0, 0, 0]
Esta é uma representação única e inequívoca da árvore acima, o que significa que não existem duas árvores puras diferentes com as mesmas linearizações e que podemos reconstruir a árvore original a partir da lista.
Embora cada árvore corresponda a uma determinada lista inteira, nem cada lista inteira representa uma árvore linearizada válida: por exemplo [2, 0, 0, 0]
, não representa uma árvore válida, se tentarmos des linearizá-la, terminaremos com essa árvore
[2,0,0,0] -> 2 [0,0,0] -> 2 [0,0] -> 2 [0]
/ \ / \ / \
0 0 0
mas ainda tem uma 0
esquerda na lista e nenhum lugar para colocá-la. Da mesma forma, [2, 0]
também não é uma linearização de árvore válida, pois a árvore não linearizada tem um ponto filho vazio:
2
/ \
0
Tarefa
Dada uma lista inteira, decida se é uma linearização válida de uma árvore usando o mínimo de bytes possível. Você pode escrever um programa completo ou uma função.
Entrada: uma lista não vazia de números inteiros não negativos.
Saída: Um valor verdadeiro se a lista for uma linearização de uma árvore, caso contrário, um valor falso.
Casos de teste
Truthy[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]
Falsy
[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]
{X0@{+\(_{\}&}/|!}
Eu acho que?@
.Labirinto , 17 bytes
Experimente online!
A saída de verdade é
-1
e a saída falsa está vazia. Definir verdade e falsidade no Labirinto é um pouco complicado, porque os ramos do Labirinto são principalmente ternários. No entanto, a única maneira de construir uma condicional com duas ramificações confiáveis, você só pode fazer isso:Nesse caso, eu consideraria seguir em frente falsamente (porque a direção do movimento não é afetada) e virar verdade. Eles correspondem a zero e diferente de zero, respectivamente. O motivo pelo qual estou usando uma saída vazia para representar zero é que, se você canalizasse a saída de volta para outro programa Labyrinth, o operador de entrada
?
enviaria um zero se a entrada estiver vazia, por isso considero válida a sequência vazia representação de zero.Explicação
O algoritmo ainda é o mesmo que nas minhas respostas Mathematica e Retina, mas devido ao fluxo de controle do Labyrinth, funciona um pouco diferente desta vez:
-11
inicialmente, para que desejemos que o contador seja negativo em toda a lista e atinja zero na última entrada. Isso realmente simplifica o fluxo de controle aqui.Em vez de criar a lista completa e verificar se continha o valor errado, existem três condições de finalização possíveis:
Quanto ao código real, começamos no canto superior esquerdo. O
(
vira a zero, implícita no topo da pilha em um-1
, que será a execução total. Em seguida, entramos no loop principal muito apertado do programa+?-)"_,;+
:Isso deixa apenas os casos em que reduzimos o total de execução para zero em algum momento. O IP se move para o canto inferior direito
,
e lê outro caractere para verificar se alcançamos o EOF. Caso contrário, o valor será positivo e o IP vira para oeste em direção ae@
o programa termina. Se alcançamos o EOF, o IP vira para o leste e imprime o-1
com!
. O IP seguirá em direção à parte inferior esquerda@
por um caminho um pouco estranho para finalizar o programa.fonte
Python, 82 bytes
Precisa de mais casos de teste.
fonte
list
se este é Python 2, pelo menos, e reorganizando e invertendo a segunda condição, você pode obtê-lo para 70 bytes:lambda l:all(l[x]<len(l)-x for x in range(len(l)))and len(l)==sum(l)+1
all
serx<len(l)-y for y,x in enumerate(l)
para salvar mais 2 bytes para obtê-lo a 68.Pitão, 13 bytes
Começamos calculando o preenchimento atual da árvore em todos os pontos da representação de entrada. Essa parte da ideia é amplamente emprestada de Martin Ender, então, graças a ele.
sM._tMQ
Depois de termos essa lista, verificamos se o primeiro índice que contém
-1
(x..._1
) é o comprimento da entrada menos um (q...tl(Q)
).Não acredita que funciona? Tente você mesmo!
fonte