Посади бинарный лес!

24

Вдохновленный A014486 .

Вызов

Учитывая целочисленный ввод в основании 10, создайте представление для двоичного леса, соответствующего вводу. Представления включают в себя, но не ограничиваются ими, вложенные массивы и строки.

Как?

Преобразовать входные данные в двоичный. 1s представляют ветви, а 0s представляют листья.

Чтобы это было легче понять, давайте использовать 834(1101000010 в двоичном виде) в качестве примера.


Начнем с первой цифры. Первая цифра - это 1, поэтому мы рисуем ветви:

\ /
 1

или как массив, {{1}}


Следующая цифра 1, поэтому мы рисуем больше веток (мы идем слева направо):

\ /
 1
  \ /
    1

или как массив, {{1, {1}}}


Следующая цифра 0, поэтому мы помещаем лист:

0
 \ /
  1
   \ /
     1

или как массив, {{1, {1, 0}}}


Следующая цифра - это 1, поэтому мы размещаем ветку:

     \ /
0 1
 \ /
   1
      \ /
         1

или как массив, {{1, {1, 0, {1}}}}


Повторяя процесс, мы получаем следующее дерево после 8-й цифры:

    0 0
     \ /
0 1
 \ /
   1 0
      \ /
         1

или как массив, {{1, {1, 0, {1, 0, 0}}, 0}}


Для оставшихся цифр мы рисуем больше деревьев:

9-ая цифра - это 0, поэтому мы помещаем листок (аааа, это молодой выстрел!)

    0 0
     \ /
0 1
 \ /
   1 0
      \ /
         1 0

или как массив, {{1, {1, 0, {1, 0, 0}}, 0}, 0}


Когда мы используем все цифры, мы получаем следующее:

    0 0
     \ /
0 1
 \ /
   1 0 0
      \ / \ /
         1 0 1

или как массив, {{1, {1, 0, {1, 0, 0}}, 0}, 0, {1, 0}}


Это выглядит странно, поэтому мы добавляем ноль для завершения дерева:

    0 0
     \ /
0 1
 \ /
   1 0 0 0
      \ / \ /
         1 0 1

или как массив, {{1, {1, 0, {1, 0, 0}}, 0}, 0, {1, 0, 0}}

Обратите внимание, что выравнивание массива дает исходное число в двоичном виде, но с добавленным нулем.

критерии

  • Выходные данные должны четко показывать разделение деревьев и ветвей (если это не вложенный массив, объясните, пожалуйста, ваш выходной формат).
  • Извлечение всех цифр из выходных данных должно быть идентично двоичному представлению входных данных (с добавленными нулями из вышеприведенного процесса).

Контрольные примеры

Выходные данные могут отличаться, если они соответствуют критериям.

0 -> {0}
1 -> {{1, 0, 0}}
44 -> {{1, 0, {1, {1, 0, 0}, 0}}}
63 -> {{1, {1, {1, {1, {1, {1, 0, 0}, 0}, 0}, 0}, 0}, 0}}
404 -> {{1, {1, 0, 0}, {1, 0, {1, 0, 0}}}}
1337 -> {{1, 0, {1, 0, 0}}, {1, {1, {1, 0, 0}, {1, 0, 0}}, 0}}

счет

Это , поэтому побеждают младшие байты!

Юнг Хван Мин
источник
5
Я бы избегал использования бонусов - это обычно не улучшает задачу.
Sanchises
1
@Sanchises Я добавил бонус, чтобы увидеть ответы с визуализацией ... Как еще я могу побудить людей попробовать сделать визуализацию в качестве результата?
JungHwan Мин
4
(Ваш комментарий) Требовать это?
msh210
1
@JungHwanMin Посмотрите на то, что я связал более подробно (особенно комментарии); или, в том же вопросе Meta, этот ответ. Ваш текущий вопрос требует от авторов создания 2 ^ 2 = 4 программ и подсчета баллов по каждой программе, прежде чем отправлять лучшую программу оценки. Либо потребуйте его, если вы считаете, что он станет более сложным, либо удалите его, если считаете, что он усугубляет проблему.
Sanchises
2
@JungHwanMin Справедливо достаточно. Они должны сыграть в гольф 3 программы и подсчитать каждый отдельный балл, прежде чем отправлять ответ. То, что у вас есть, это три испытания, объединенные в один. Я бы порекомендовал разместить визуализацию как отдельную задачу.
Sanchises

Ответы:

2

JavaScript (ES6), 96 89 80 79 74 73 байта

f=($,_=~Math.log2($))=>0>_?[(g=f=>$&1<<~_++&&[1,g(),g()])(),...f($,_)]:[]
<input type="number" value="1337" oninput="document.querySelector('#x').innerHTML=JSON.stringify(f(+this.value))"/><br/><pre id="x"></pre>

Определяет функцию, fкоторая возвращает вложенный массив. HTML-код только для тестирования.

PurkkaKoodari
источник
Какое-то время я думал: «Что, черт возьми $&, обходится без этого .replace?» : P
ETHпродукция 26.12.16
@ETHproductions Мне было скучно, и я запутывал имена переменных. Жаль, что JS не допускает других
односимвольных
9

Befunge, 138 117 104 байта

p&1v
%2:_v#:/2p9p00+1:g00
3\9g<>$\:!v!:<
9g!v ^,"}"_1-\1-:
"0"_2\"1{",,:|:,
`#@_\:#v_"}",>$\:8
,"0":-1<^

Попробуйте онлайн!

объяснение

Строка 1 считывает число из стандартного ввода, а строка 2 преобразует это число в двоичную последовательность, которую она сохраняет в игровом поле в строке 10. Строки с 3 по 5 затем выполняют итерацию по этим двоичным цифрам, выводя соответствующее представление дерева при обработке каждой цифры. Стек Befunge используется для отслеживания глубины в дереве и того, сколько листового пространства осталось на каждом уровне, чтобы мы знали, когда создавать новую ветвь. Строки 6 и 7 обрабатывают окончательное 0заполнение, чтобы заполнить любые пустые листья.

Для того, чтобы по возможности играть в гольф, я удалил запятые с вывода, а также посторонние внешние скобки. Это все еще не побеждает решение Mathematica, но это было весело, пытаться.

Если вы хотите увидеть, как это выглядело в исходном подробном формате вывода, я сохранил более раннюю версию кода здесь (131 байт).

Джеймс Холдернесс
источник
1
(это не имеет достаточно голосов: D)
Аддисон Крамп
4

Mathematica, 167 161 байт

b=Append;a=If[#&@@#>0,a[Rest@#~b~0,a[#,#3[#,{1,#4,#2},##5]&,#3,#2,##4]&,#2,##3],
#2[Rest@#~b~0,0,##3]]&;a[#~IntegerDigits~2,If[c=#3~b~#2;Tr@#>0,a[#,#0,c],c]&,
{}]&

Анонимная функция. Принимает число в качестве входных данных и возвращает произвольно вложенный список чисел в качестве выходных данных. Добавлены разрывы строк для ясности. Использует какой-то механизм, включающий продолжения, но я слишком устал, чтобы думать об этом больше.

LegionMammal978
источник
#[[1]]чтобы #&@@#сохранить байт. !#~FreeQ~1вместо того, чтобы #~MemberQ~1сохранить байт, а также.
JungHwan Мин
4

Mathematica, 115 109 108 104 98 байт

(i=#~IntegerDigits~2;f:=Switch[If[i=={},0,i={##2};#]&@@i,0,0,1,f~1~f];NestWhileList[f&,f,i!={}&])&

Генерирует сообщения об ошибках, которые можно безопасно игнорировать. Выводит двоичный лес. Он немного отличается от примера вывода, потому что 1это Headне первый элемент списка. (например, 1[0, 0]вместо {1, 0, 0})

Безошибочная версия (104 байта)

(i=#~IntegerDigits~2;f:=Switch[If[i=={},i={0}];(i={##2};#)&@@i,0,0,1,f~1~f];NestWhileList[f&,f,i!={}&])&

объяснение

i=#~IntegerDigits~2;

Преобразование ввода в список base-2. Сохраните это в i.

f:=

SetDelay fследующее (оценивается всякий раз, когда fвызывается):

Switch[If[i=={},0,i={##2};#]&@@i,0,0,1,f~1~f]

Switch заявление.

Во-первых, если iпусто, выведите 0. Если нет, выведите первый элемент iи удалите его из списка. Используйте вывод в качестве управляющей переменной.

Если управляющая переменная есть 0, выведите 0. Если это так 1, вывод 1[f, f](рекурсивный).

NestWhileList[f&,f,i!={}&]

Пока iне пусто, продолжайте звонить f. Выведите результат, завернутый в List.

пример

(i=#~IntegerDigits~2;f:=Switch[If[i=={},0,i={##2};#]&@@i,0,0,1,f~1~f];NestWhileList[f&,f,i!={}&])&[1337]

{1[0, 1[0, 0]], 1[1[1[0, 0], 1[0, 0]], 0]}

Альтернативное решение (120 байт)

Идентичен моему 104-байтовому решению, но преобразует выходные данные в формат, указанный в вопросе.

(i=#~IntegerDigits~2;f:=Switch[If[i=={},i={0}];(i={##2};#)&@@i,0,0,1,f~1~f];NestWhileList[f&,f,i!={}&]//.1[a__]:>{1,a})&
Юнг Хван Мин
источник
2

Python 2, 133 118 117 байт

Частично рекурсивный, частично итеративный. Я попытался использовать целое число, но дерево начинается с самых значимых битов, поэтому я не думаю, что оно того стоит.

def t():global b;a=b[:1];b=b[1:];return a and'0'<a and[1,t(),t()]or 0
b=bin(input())[2:]
L=[]
while b:L+=t(),
print L

Попробуйте онлайн

mbomb007
источник
1

Java 8, 367 байт

Golfed:

class f{static String r="";static int p=0;static void g(char[]s,int k){if(p>=s.length||s[p]=='0'){r+="0";p++;return;}else{r+="{1";p++;g(s,k+1);g(s,k+1);r+="}";}if(k==0&&p<s.length)g(s,0);}public static void main(String[]a){java.util.Scanner q=new java.util.Scanner(System.in);r+="{";g(Integer.toBinaryString(q.nextInt()).toCharArray(),0);r+="}";System.out.print(r);}}

Ungolfed:

class f{
    static String r="";
    static int p=0;
    static void g(char[]s,int k){
        // if there's empty space in last tree or current character is a 0
        if(p>=s.length || s[p]=='0'){
            r+="0";
            p++;
            return;
        }
        // if current character is a 1
        else{
            r+="{1";
            p++;
            // left branch
            g(s,k+1);
            // right branch
            g(s,k+1);
            r+="}";
        }
        // if they're still trees that can be added
        if(k==0 && p<s.length)g(s,0);
    }
    public static void main(String[]a){
        java.util.Scanner q=new java.util.Scanner(System.in);
        r+="{";
        g(Integer.toBinaryString(q.nextInt()).toCharArray(),0);
        r+="}";
        System.out.print(r);
    }
}
Bobas_Pett
источник
1

DUP , 84 байта (82 символа)

0[`48-$1_>][\10*+]#%1b:[$1>][2/b;1+b:]#[['{,1.b;1-b:FF'},][0.b;1-b:]?]⇒F[b;0>][F]#

По причинам, связанным с игрой в гольф, я избавился от внешних фигурных скобок и запятых, потому что они не нужны для восстановления деревьев.

Пример выходов:

0      → 0
1      → {100}
44     → {10{1{100}0}}
63     → {1{1{1{1{1{100}0}0}0}0}0}
404    → {1{100}{10{100}}}
1023   → {1{1{1{1{1{1{1{1{1{100}0}0}0}0}0}0}0}0}0}
1024   → {100}00000000
1025   → {100}0000000{100}
1026   → {100}000000{100}
1027   → {100}000000{1{100}0}
1028   → {100}00000{100}
1337   → {10{100}}{1{1{100}{100}}0}
4274937288 → {1{1{1{1{1{1{10{1{100}{1{1{100}{10{1{1{10{1{1{100}{100}}0}}0}0}}}0}}}0}0}0}0}0}0}
4294967297 → {100}00000000000000000000000000000{100}

Объяснение:

0[`48-$1_>][\10*+]#           While loop to read in the characters and convert them into a
                              base-10 integer.
0                             Push 0 (temporary value)
 [`48-$0>]       #            While input character-48 (digit)>-1
          [     ]
           \                      Swap top values
            10                    Push 10
              *                   Multiply (temporary value by 10)
               +                  Add to input value
%                                 Pop stack (EOL)
1b:                           Variable b=1 (bit count)
[$1>][2/b;1+b:]#              While loop to convert the number to base-2 digits on the
                              data stack, MSB on top. Each iteration increments bit count b.
[$1>]          #              While (DUP>1)
     [        ]#
      2                           Push 2
       /                          MOD/DIV (pushes both mod and div on the stack)
        b;1+b:                    Fetch b, increment, store b


[['{,1.b;1-b:FF'},][0.b;1-b:]?]⇒F     
[                             ]⇒F     Define operator F:
                                      pop top stack value
 [                ]          ?        if value != 0:
  '{,1.                                   print '{1'
       b;1-b:                             fetch b, decrement b, store b
             F                            execute operator F
              F                           execute operator F again
               '},                        print '}'
                   [        ]?        if value == 0:
                    0.                    print '0'
                      b;1-b:              fetch b, decrement b, store b
[b;0>][F]#
[b;0>]   #                            While (fetch b, b>0==true)
      [F]#                                execute operator F

Попробуйте это с помощью онлайнового интерпретатора DUP Javascript на quirkster.com или клонируйте мой GitHub-репозиторий моего интерпретатора DUP, написанный на Юлии.

ML
источник