Dado un número entero n, enumere todos los árboles binarios completos posibles con n nodos internos. (Los árboles binarios completos tienen exactamente 2 hijos en cada nodo interno). La estructura de árbol se debe generar como un recorrido de preorden del árbol, donde 1 representa un nodo interno y 0 representa un nodo externo (Nulo).
Aquí hay ejemplos para los primeros n:
0:
0
1:
100
2:
11000
10100
3:
1110000
1101000
1100100
1011000
1010100
Este es un código de golf con el premio a la menor cantidad de personajes. Los árboles deben salir uno por línea a stdout. El programa debería leer n desde la línea de comandos o stdin.
code-golf
combinatorics
binary-tree
Kyle Butt
fuente
fuente
Respuestas:
Perl -
12579 caracteresEl recuento incluye 4 caracteres para las "
-ln
" opciones. Toma n de stdin.Nuevo enfoque constructivo:
Forme la solución para n sustituyendo un nuevo nodo interno ("100") para cada hoja ("0"), a su vez, en cada árbol de la solución para n-1.
(Debo este concepto a las soluciones de otros que usan el nodo interno para hojear la sustitución [100-> 0] para verificar cadenas generadas secuencialmente, y creo que vi, después de escribir mi respuesta basada en ese concepto, este mismo 0- > 100 método de construcción en la edición intermedia de alguien.)
Enfoque recursivo previo:
Recursivo sin golf:
fuente
PHP
(142)(138)(134)(113)Se ejecuta desde la línea de comando, es decir, "php golf.php 1" genera "100".
EDITAR: Corte 4 caracteres con un método alternativo, construyendo las cadenas desde 0 en lugar de recurrir desde $ n. Utiliza PHP 5.3 para el operador ternario acortado; de lo contrario, se necesitan 2 caracteres más.
EDIT 2: guardado 4 caracteres más con algunos cambios en los bucles.
EDITAR 3: estaba probando un enfoque diferente y finalmente lo obtuve por debajo del método anterior.
Todos los árboles pueden considerarse representaciones binarias de enteros entre 4 ^ n (o 0, cuando n = 0) y 2 * 4 ^ n. Esta función recorre ese rango y obtiene la cadena binaria de cada número, luego la reduce repetidamente reemplazando "100" por "0". Si la cadena final es "0", entonces es un árbol válido, así que escríbalo.
fuente
Ruby,
9994928987 caracteresLa entrada se lee desde stdin.
Edición 1: IO modificada (ver comentarios de Lowjacker)
Edición 2: Algoritmo cambiado.
Edición 3: La versión ahora toma el tercer enfoque (usando la idea de migimaru).
Edición 4: de nuevo dos personajes. Gracias a migimaru.
fuente
*?\n
, porqueputs
imprime cada elemento de la matriz en su propia línea.Rubí 1.9
(80)(79)Utilizando el enfoque constructivo no recursivo utilizado por DCharness.
EDITAR: Guardado 1 personaje.
fuente
Haskell 122 caracteres
Dado que el IO es una parte no trivial del código en Haskell, tal vez alguien pueda usar una solución similar en otro idioma. Esencialmente camina al azar en un cuadrado de abajo a la izquierda a la derecha y se detiene si se cruza la diagonal. Equivalente a lo siguiente:
fuente
Golfscript, 60
83Construí un modo golfscript para Emacs para trabajar en esto, si alguien está interesado.
fuente