Vuelta a una nueva página

19

Te dan un árbol que, en la tradición de la informática, tiene la raíz en la parte superior y las hojas en la parte inferior. Los nodos de hoja están etiquetados con números. Su objetivo es tomar la hoja especial marcada -1y moverla hacia arriba para que sea la nueva raíz.

[3, [[16], -1], [4]] --> [[[[4], 3], [16]]]

ingrese la descripción de la imagen aquí

Puedes imaginar rotar la hoja especial hacia la parte superior y dejar que el resto del árbol cuelgue de ella. Mantener el árbol en el plano mientras lo gira para obtener el orden correcto de izquierda a derecha de todas las ramas.

El nuevo árbol tiene todas las hojas del árbol original, excepto -1.

Entrada:

Un árbol cuyas hojas son enteros positivos distintos, a excepción de una hoja de -1. La raíz del árbol tendrá al menos dos ramas saliendo.

La entrada se proporciona como una lista anidada [3, [[16], -1], [[4]]]o como su representación de cadena. Los delimitadores son opcionales y dependen de usted, pero los números adyacentes deben separarse.

Salida:

Imprima o imprima el árbol invertido en el mismo formato que su entrada. El orden de las entradas de la lista debe ser correcto. La modificación en el lugar está bien.

Si su entrada / salida es un tipo de datos, debe ser uno que imprima en el formato requerido de forma predeterminada. Las funciones integradas que básicamente hacen la tarea por usted no están permitidas.

Casos de prueba:

>> [3, [[16], -1], [4]]
[[[[4], 3], [16]]]

>> [2, -1]
[[2]]

>> [44, -1, 12]
[[12, 44]]

>> [[[[-1]]], [[[[4]]]]]
[[[[[[[[[4]]]]]]]]]

>> [[1, 2, 3], [4, -1, 6], [7, 8, 9]]
[[6, [[7, 8, 9], [1, 2, 3]], 4]]

>> [9, [8, [7, [6, -1, 4], 3], 2], 1]
[[4, [3, [2, [1, 9], 8], 7], 6]]
xnor
fuente
1
El ejemplo no parece alinearse con el diagrama. El 4tiene dos corchetes más a su alrededor que el 3, pero está diagramado solo 1 capa más profundo.
isaacg

Respuestas:

7

CJam, 24 24 22 bytes

l~{):T]{s$}$(+T1+}gW<p

Pruébalo en línea .

Gracias Dennis por eliminar 2 bytes.

Explicación

l~          e# Read the input.
{           e# Do:
    ):T     e# Save the last item to T.
    ]       e# Wrap everything else (as an array) and the last item into an array,
    {s$}$   e#   where the one with -1 (having "-" if stringified) is the first item.
    (+      e# Insert the second array into the first array as the first item,
            e#   or just move the -1 to the end if the first item is already -1.
    T1+     e# Check if the array before this iteration ended with -1.
}g          e# Continue the loop if it did't.
W<p         e# Remove the -1 and print.
jimmy23013
fuente
Puede usar {s$}$, con el orden de inversión invertido. Además, una función anónima ahorraría un byte sobre un programa completo.
Dennis
1
@ Dennis Gracias. Pero si es una función, creo que necesitaré un extra [.
jimmy23013
6

Pyth, 26 25 24 23 bytes

L?y.>b1}\-`Jtb.xyahbJ]J

Demostración. Arnés de prueba.

Esto define una función, yque toma una lista anidada de Pyth como entrada.

Hay tres casos para explorar en esta función recursiva, debido a la ternaria, ?y la oportunidad - a excepción de la función, .x. En la función, la entrada es b.

El primer caso ocurre cuando }\-`Jtbes verdad. Esto prueba si hay una -representación en la cadena de tb, la "cola" de b, que es todo bexcepto su primer elemento. tbtambién se almacena en J. Dado que todas las etiquetas son positivas, excepto -1, esto será cierto si y solo si -1no está en el primer elemento de la lista.

En este caso, desplazamos cíclicamente a la derecha bpor 1 con .>b1, y luego llamamos a la función de forma recursiva. Esto asegura que avanzaremos al siguiente paso con el elemento que contiene -1como encabezado (primer elemento) de la lista.

En los siguientes dos casos, lo anterior es falso, por lo que -1está en el encabezado de la lista.

En el segundo caso, ahbJno arroja un error. Se generará un error si y solo si hbes un número entero. Si este no es el caso, entonces hbes una lista, y necesitamos rotar el árbol para que la -1hoja esté más cerca de la raíz. ahbJlogra esto agregando Jcomo un elemento único al final de hb, que efectivamente mueve la raíz del árbolb a hb.

En el tercer y último caso, se produce un error. Por lo tanto, hbes un elemento único. Debido a la prueba en el primer caso, hbdebe ser -1. Por lo tanto, podemos devolver el resto de b, es decir J, envuelto en una lista, es decir ]J.

isaacg
fuente