Фон
Немеченое дерево может выглядеть так:
o
/ | \
o o o
| / \
o o o
Чтобы линеаризовать это дерево, мы сначала помечаем каждый узел o
числом его дочерних узлов:
3
/ | \
1 0 2
| / \
0 0 0
а затем запишите числа в списке в порядке дыхания, означая строку за строкой и слева направо:
[3, 1, 0, 2, 0, 0, 0]
Это уникальное и однозначное представление дерева выше, означающее, что никакие два разных чистых дерева не будут иметь одинаковые линеаризации и что мы можем восстановить исходное дерево из списка.
Хотя каждое дерево соответствует определенному целочисленному списку, не каждый целочисленный список представляет допустимое линеаризованное дерево: например [2, 0, 0, 0]
, не представляет допустимое дерево, если мы пытаемся его линеаризовать, мы получаем это дерево
[2,0,0,0] -> 2 [0,0,0] -> 2 [0,0] -> 2 [0]
/ \ / \ / \
0 0 0
но все равно есть 0
в списке и некуда его поставить. Точно так [2, 0]
же не является допустимой линеаризацией дерева, поскольку у линеаризованного дерева есть пустое дочернее пятно:
2
/ \
0
задача
Учитывая список целых чисел, решите, является ли это допустимой линеаризацией дерева, используя как можно меньше байтов. Вы можете написать полную программу или функцию.
Входные данные: непустой список неотрицательных целых чисел.
Вывод: истинное значение, если список является линеаризацией дерева, иначе ложное значение.
Testcases
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@{+\(_{\}&}/|!}
Думаю?@
.Лабиринт , 17 байт
Попробуйте онлайн!
Истинный вывод есть,
-1
а ложный вывод пуст. Определить правду и ложь в Лабиринте немного сложно, потому что ветви Лабиринта преимущественно троичные. Однако единственный способ построить условно с надежно двумя ветвями, вы можете сделать только это:В этом случае я бы подумал о том, чтобы двигаться вперёд (потому что направление движения не изменилось) и повернуть правдиво. Они соответствуют нулю и отличны от нуля соответственно. Причина, по которой я использую пустой вывод для представления нуля, заключается в том, что если бы вы перенаправили вывод обратно в другую программу Labyrinth, оператор ввода
?
фактически выдвинул бы ноль, если вход пустой, поэтому я считаю пустую строку допустимой представление нуля.объяснение
Алгоритм все тот же, что и в моих ответах Mathematica и Retina, но из-за потока управления Лабиринта, в этот раз он работает немного иначе:
-11
изначально, чтобы мы хотели, чтобы счетчик был отрицательным по всему списку, и достигли нуля на последнем входе. Это на самом деле упрощает поток управления здесь.Вместо создания полного списка и проверки, содержит ли он неправильное значение, существует три возможных условия завершения:
Что касается фактического кода, мы начинаем в верхнем левом углу.
(
Превращает неявный ноль на вершине стека в-1
, который будет нарастающим итогом. Затем мы входим в очень узкий основной цикл программы+?-)"_,;+
:Это оставляет только те случаи, когда мы в какой-то момент сократили промежуточную сумму до нуля. IP перемещается в нижний правый
,
угол и читает другой символ, чтобы проверить, достигли ли мы EOF. Если нет, значение будет положительным, и IP поворачивается на запад в направлении,@
и программа завершается. Если мы достигли EOF, IP поворачивается на восток и печатает-1
с!
. После этого IP-адрес пробирается к левому нижнему@
краю по слегка странному пути, чтобы завершить программу.источник
Python, 82 байта
Нужно больше тестовых случаев.
источник
list
если это, по крайней мере, Python 2, и, переставив и инвертировав второе условие, вы можете получить его до 70 байт:lambda l:all(l[x]<len(l)-x for x in range(len(l)))and len(l)==sum(l)+1
all
,x<len(l)-y for y,x in enumerate(l)
чтобы сохранить еще 2 байта, чтобы получить его до 68.Pyth, 13 байт
Мы начнем с вычисления текущей заполненности дерева во всех точках входного представления. Эта часть идеи в значительной степени заимствована у Мартина Эндера, так что благодаря ему.
sM._tMQ
Получив этот список, мы проверяем, является ли первый индекс, содержащий
-1
(x..._1
), длину ввода минус один (q...tl(Q)
).Не веришь, что это работает? Попробуй сам!
источник