Codegolf - Построй Гнездо

Задача проста: написать программу или функцию, которая при задании конечного неотрицательного целого числа выводит вложенный массив.

Правила

• Ваш код должен создавать уникальный действительный вложенный массив для каждый целое число 0 ‌≤ n ‌< 2³¹.
• Каждый В этом диапазоне должен быть выведен возможный вложенный массив, содержащий до 16 открытых скобок. (Это не означает, что ваш код никогда не сможет вывести вложенный массив с более чем 16 открытыми скобками.)
• Ваш код может выводить строковое представление вложенного массива вместо реального массива (с запятыми или без них).

Одно из возможных сопоставлений:

 0 -> []
1 -> [[]]
2 -> [[[]]]
3 -> [[], []]
4 -> [[[[]]]]
5 -> [[[], []]]
6 -> [[[]], []]
7 -> [[], [[]]]
8 -> [[], [], []]
9 -> [[[[[]]]]]
etc.
 

Подсчет очков

Это, так побеждает самый короткий код в байтах.

#code-golf #code-golf #array #сбалансированная строка #открытая функция #рваный список

Питон, 153 128 байт

 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 x=>(h=x.toString(2).replace(/./g,c=>']['[i+=c-.5,i-=!i,c],i=0),i-.5?'['+'[]'.repeat(x+20):h)+']'
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Мы сопоставляем число н во вложенный список, просматривая его двоичные цифры слева направо. Этот алгоритм работает для любого числа, а не меньше 2.³².

1. Если текущая двоичная цифра равна 1, выведите x=>eval("g=i=>i>1?(h-=[i]*2%4-1)&&']['[i%2n]+g(i>>1n):']';for(i=0n;~x;~h||--x)h=0,g(i++)") .
2. В противном случае, если последовательность скобок, которую мы вывели до сих пор, будет уравновешена одной закрывающей скобкой, выведите x=>eval("g=i=>i>1?(h-=i*2%4-1)&&']['[i%2]+g(i>>1):']';for(i=0;~x;~h||--x)h=0,g(i++)") .
3. В противном случае, если это последний 0 в двоичном числе, выведите O % Push 0: initial count of valid numbers ` % Do...while @ % Push iteretation index k, starting at 1 B % Convert to binary. For example, k=6 gives [1 1 0 0] Eq % Multiply by 2, subtract 1: transforms [1 1 0 0] into [1 1 -1 -1] XJ % Copy that to clipboard J, without popping it Ys % Cumulative sum: gives [1 2 1 0] 0&) % Split array into its final element and the rest. Gives 0, [1 2 1] 0> % Yields 1 for positive entries (condition 2). So in this case it % gives [1 1 1] w % Swap: moves second-top element in the stack (0 in this case) to top ~ % Negate: yields 1 if input is 0 (condition 1). Gives 1 in this case h % Concatenate horizontally. Gives [1 1 1 1] A % All: gives 1 if all elements are 1. Gives 1 in this case, meaning % that this k is valid + % Add the result (0 or 1) to the count of valid numbers t % Duplicate G % Push input n >~ % Loop condition: false (exit loop) if count exceeds input n ] % End loop. At this point the result is in clipboard J, in 1/-1 format x % Delete count 92 % Push 92. Will be used to convert 1, -1 to '[', ']' (ASCII 91, 93) J % Push result in 1/-1 format - % Subtract: converts 1 to 91, -1 to 93 c % Convert to char. Implicitly display .
4. В противном случае выведите ] .

Наконец, мы закрываем все открытые скобки.

Python 2.7, 172 149 124 118 байт

Объяснение:

Определите биекцию по [ ↔ 1 и -1 ↔ 1 . Тогда любое расположение скобок можно записать в виде двоичного числа и наоборот, например -1 ↔ 1 (10) и ']' ↔ -1 (52). Все допустимые комбинации до 15 открытых скобок (всего 30 скобок) охватываются числами длиной до 30 бит (без учета ведущих нулей), которые в точности являются числами меньше 2.³¹.

Первый цикл for дает обратную биекцию, преобразуя число в набор скобок и проверяя при этом правильность расположения.

Недопустимые расположения заменяются в операторе печати длинными последовательностями скобок, чтобы избежать коллизий. Например '[' (3)↔ 1 недопустимо, поэтому вместо этого мы объединяем скобки 3+16. Это гарантирует уникальность всех аранжировок.

Полученное расположение помещается в пару скобок, образуя вложенный массив, так что -1 (10) becomes 1 и -1 (52) becomes 0 . Дополнительная открытая скобка означает, что теперь мы покрыли все массивы 16 открытыми скобками.

Следующую программу можно использовать для вычисления числа для данного массива, содержащего до 16 скобок.

Ложка, 63 байта (501 бит)

Это следующая программа Brainfuck, преобразованная в ложку:

Считывает целое число в двоичном формате на стандартный вход и выводит вложенный список на стандартный ввод. Требуется ввести 0 в качестве пустой строки (без цифр) и требуется интерпретатор Brainfuck с 8-битными ячейками. Тот же алгоритм, что и мой ответ на Python.

Читабельная версия:

Желе, 28 байты

Это перебирает все строки символов m и n которые начинаются с # and end with a "[][]" , проверяет, совпадают ли скобки, и печатает н^й соответствовать.

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

Перл, 80 79 байт

Снова использует орлпалгоритм, но на этот раз я сначала проверил, работает ли он...

Включает +1 за (([0..]>>= \y->y#y)!!) 3

Укажите номер входа в STDIN

] :

ЛинусРешение составляет 64 байта в Perl:

ДеннисРешение - 59 байт в Perl (все медленнее для больших чисел):

Питон 3, 120 114 байт

Проверьте это на идея.

Как это работает

Определенная функция ж принимает входные данные н и инициализирует к к 0. Мы будем продолжать увеличивать к до п + 1 ценности к результат будет действительным. Каждый раз, когда мы находим такое значение к, н уменьшается, как только достигает -1, p=<<[1..] yields 0и список р что соответствует последнему значению к печатается.

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

1. Конвертировать к к представлению двоичной строки, начиная с 0б.

   Например, 44 ↦ «0b101100».

2. Заменить все 0' (кодовая точка 48) в строковом представлении со строкой "]," и все 1' (кодовая точка 49) с [.

   Например, "0b101100" ↦ "],b[],[[],],".

3. Удалите первые три символа (они соответствуют "0б") и завершающий символ (надеюсь, запятая).

   Например, "],b[],[[],]," ↦ "[],[[],]".

4. Попробуйте оценить сгенерированный код. Если это приведет к ошибке, к не сопоставлен ни с одним списком.

   Например, "[],[[],]" ↦ ([], [[]]).

5. Объедините результат (если есть) с пустым списком. Если это приведет к ошибке, к не сопоставлен ни с одним списком.

   Например, ([], [[]]) + [] ошибки, так как + не может объединять списки и кортежи.

Хаскель, 71 байт

Функция main в последней строке индексирует список всех вложенных массивов, отсортированных по размеру (количеству открытых скобок). Итак, все массивы размером не более 16 перечислены первыми.

Давайте сначала посмотрим на код, который лучше и короче, но программа проверки типов Haskell отказывается его принимать.

Функция t on input k дает список всех вложенных массивов размера h (open brackets). This is done recursively. Each such array consists of some head n (первый член) размера n and some tail p (другие члены) размера p 1=[[]] p n=[h:t|k<-[1..n-1],h<-p k,t<-p$n-k] ((p=<<[1..])!!) , both sizes nonzero. Or, it's the empty array for size p 1=["[]"] p n=['[':h++t|k<-[1..n-1],h<-p k,_:t<-p$n-k] ((p=<<[1..])!!) .

Выражение ~n then flattens def f(n,k=0): while~n: k+=1 try:r=eval(bin(k).translate({48:'],',49:'['})[3:-1])+[];n-=1 except:0 print(r) в один бесконечный список всех массивов, отсортированных по размеру

и основная функция индексируется в него.

... Или так бы и было, если бы Haskell не ныл о «конструировании бесконечного типа: t ~ [t]». Haskell не может представлять бесконечный список, элементы которого представляют собой произвольно вложенные массивы. Все его элементы должны иметь один и тот же тип, но тип t не может совпадать со списком t. Фактически, функция #!/usr/bin/perl -p $_=sprintf"%b",/.+/g;$_=10x($&&&$&+16)if!/^(1(?1)*0)+$/;y;10;() itself cannot be assigned a consistent type without dependent typing, which Haskell lacks.

Итак, вместо этого мы работаем со строками скобок, имитируя операцию cons, воздействуя на #!/usr/bin/perl -p ($_=sprintf"%b",$_).=2x(s^.^$&or++$n-pos&&/.0/g?++$n%1:$`&&21^eg-$n);y;102;(); и nest.pl персонажи. Это занимает дополнительные 9 байт. Опасности игры в гольф на типобезопасном языке.

Хаскелл, 87 82 байта

Выводит элементы массива. Пример использования: -p -> ] .

Функция [ builds all nested arrays as strings for ] открытый и [ close brackets, by keeping track of how many of each are left over. Always starts with ḃ2-*µSN;+\>-Ạ 1Ç#Ṫḃ2?2;1ị⁾][ . Основная функция вызывает -[+[+<]>>+]<+++. push open bracket and print it [->+>+<<] dup >>++ increment to close bracket >>,[ read input loop >-[<->-----]+<+++ subtract 48 and set up if/else [- if c == 1 <+ increment s <<.>>> output open bracket >-<]>[-< else <-[->+<] decrement and move s <<<[-] zero l >>>>[-<+<<<+>>>>] l = s and restore s <<.> output close bracket >+<[>-]>[- if s == 0 <+ undo s decrement <<. output open bracket >>>>]<< >>]< ,] <<<<[ if l >.>. output pair <<[-]] >>>+[-<.>] output close bracket s+1 times for every -[+[+<]>>+]<+++.[->+>+<<]>>++>>,[>-[<->-----]+<+++[-<+<<.>>>>-<]>[-<<-[->+<]<<<[-]>>>>[-<+<<<+>>>>]<<.>>+<[>-]>[-<+<<.>>>>]<<>>]<,]<<<<[>.>.<<[-]]>>>+[-<.>]+ и выбирает элемент по индексу, заданному входными данными.

МАТЛ, 31 байт

Попробуйте онлайн! Или проверить первые несколько тестовых случаев (занимает несколько секунд).

Полученное отображение:

Объяснение

Код продолжает тестировать возрастающие двоичные числа, с цифрой [[[][]]] replaced by 110100 ; то есть, используя [[][]] and 1010 как цифры. цифра [[ will represent 11 and 110100 will represent [[][]] .

Программа считает до тех пор, пока н+1 действительный цифры получены. Число является действительным, если выполняются следующие два условия:

1. Сумма цифр равна нулю (то есть существует равное количество цифр). 1010 and [][] )
2. Совокупная сумма цифр всегда положительна (т. е. накопленное количество цифр). 0 digits always exceeds that of ] ), кроме конца (где он равен нулю по условию 1).

Один раз нПолучено +1 допустимое число, последнее транслитерируется путем замены 1 into [ and x=input();y="";z=0 for b in bin(x)[2+(x<1):]:y+="[]"[b<"1"];z+=b>"0"or-1;z+=99*(z<0) print"["+(y,"[]"*(x+16))[z>0]+"]" into ] , а затем оно отображается.

Код:

JavaScript (Node.js), 85 байт

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

Работайте для всех положительных целых чисел, предполагая бесконечную разрядность. Но может произойти сбой, если n велико и бит сломан. Медленный.

JavaScript (Node.js), 90 байт

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

Должно хватить и теоретически все. Медленный.

JavaScript (Node.js), 97 96 байт

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

Соответствует только диапазону. Быстрый для короткого вывода