Пустой список - это список, который ни на каком уровне не содержит объектов, не входящих в список. Или, если вы предпочитаете рекурсивное определение

• Пустой список недействителен

• Список, содержащий только другие пустые списки, является недействительным

Все списки пустот имеют конечную глубину.

Вот несколько примеров списков пустот (с использованием синтаксиса Python):

[]
[[]]
[[],[]]
[[[]]]
[[[]],[]]
[[],[[]]]

Вот несколько примеров того, что не является списком пустот:

["a"]
[[...]]
[1]
2
[[],([],[])]

задача

Напишите две отдельные функции (или программы, если вы предпочитаете). Один должен взять положительное целое число (вы также можете включить ноль, если хотите) в качестве аргумента и вернуть список пустот, другой должен взять список пустот и вернуть ему целое число. Эти две функции всегда должны быть противоположны друг другу. То есть, если вы передадите вывод fв, gвы должны получить исходный результат fкак результат g. Это означает, что отображение должно быть 1: 1, т. Е. Для каждого целого числа может существовать только один список пустот, для которого gдается это целое число, а для каждого списка пустот должно быть ровно одно целое число, для которого fэтот список пустот.

Вы по сути создаете Биекцию

Вы можете использовать строковое представление списка пустот (с запятыми или без пробелов) вместо родного типа списка ваших языков.

счет

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

Pyth, 27 + 29 = 56 байт

f:

L?bol`NS{sm[d+d]Y]d)ytb]Y@y

Тестирование

g:

L?bol`NS{sm[d+d]Y]d)ytb]Yxyl`

Тестирование

Система очень проста: я генерирую все возможные списки с не более чем определенным числом [. Затем я сортирую их так, чтобы списки, которые я еще не создал, были ближе к концу. Все это делает функция y, идентичная в обеих программах. Написано как

L?bol`NS{sm[d+d]Y]d)ytb]Y

Затем я включаю в этот список f и ищу его g.

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

Программы позволяют / возвращают 0 в качестве опции.

Python 2 , 96 байт

Попробуйте онлайн! проверить биекцию.

f=lambda l:len(l)and f(l[0])*2+1<<f(l[1:])

Принимает пустые списки с неотрицательными целыми числами. 42 байта.

g=lambda n:n*[g]and[g(n/(n&-n)/2)]+g(len(bin(n&-n))-3)

Принимает неотрицательные целые числа для аннулирования списков. 54 байта. Более рекурсивная попытка дала такую ​​же длину.

g=lambda n,i=0:n*[g]and[g(n/2,i+1),[g(n/2)]+g(i)][n%2]

Java 7, 725 байт

f(int)( 325 байт ):

String f(int i){String s="";for(int j=0,e=0;e<i;e+=v(s))s=Integer.toBinaryString(j++);return"["+s.replace("1","[").replace("0","]")+"]";}int v(String s){for(;!s.isEmpty();s=s.replaceFirst("1","").replaceFirst("0",""))if(s.replace("1","").length()!=s.replace("0","").length()|s.charAt(0)<49|s.endsWith("1"))return 0;return 1;}

g(String)( 75 + 325 байт ):

int g(String s){int r=0;for(String i="10";!i.equals(s);i=f(++r));return r;}

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

Объяснение:

В общем случае метод fпросто перебирает все двоичные String-представления целых чисел и увеличивает счетчик каждый раз, когда найден действительный. Допустимые двоичные строки для этой задачи соответствуют следующим правилам: они начинаются с a 1и заканчиваются a 0; они имеют равное количество единиц и нулей; и каждый раз, когда вы удаляете первое 1и 0снова проверяете то, что осталось, эти два правила все еще применяются. После того, как счетчик равен входному значению, он преобразует эту двоичную строку в список пустых строк, заменяя все 1на [и все 0на ].

Что касается метода g: мы начинаем с "[]"(представляющего void-list 0), а затем продолжаем использовать метод f, увеличивая целое число, пока оно не будет соответствовать input-String.

String f(int i){         // Method `f` with integer parameter and String return-type
  String s="";           //  Start with an empty String
  for(int j=0,e=0;e<i;   //  Loop as long as `e` does not equal the input
      e+=v(s))           //    And append increase integer `e` if String `s` is valid
    s=Integer.toBinaryString(j++);
                         //   Change `s` to the next byte-String of integer `j`
                         //  End of loop (implicit / single-line body)
  return"["+             //  Return the result String encapsulated in "[" and "]"
    s.replace("1","[").replace("0","]")+"]";
                         //  after we've replaced all 1s with "[" and all 0s with "]"
}                        // End of method `f`

int v(String s){         // Separate method with String parameter and integer return-type
  for(;!s.isEmpty();     //  Loop as long as String `s` isn't empty
      s=s.replaceFirst("1","").replaceFirst("0",""))
                         //    After each iteration: Remove the first "1" and "0"
    if(s.replace("1","").length()!=s.replace("0","").length()
                         //   If there isn't an equal amount of 1s and 0s
       |s.charAt(0)<49   //   or the String doesn't start with a 1
       |s.endsWith("1")) //   or the String doesn't end with a 0
      return 0;          //    Return 0 (String is not valid)
                         //  End of loop (implicit / single-line body)
  return 1;              //  Return 1 (String is valid)
}                        // End of separate method

int g(String s){         // Method `g` with String parameter and integer return-type
  int r=0;               // Result integer
  for(String i="[]";!i.equals(s);
                         //  Loop as long as `i` does not equal the input String
      i=f(++r));         //   After each iteration: Set `i` to the next String in line
  return r;              //  Return the result integer
}                        // End of method `g`

Примеры случаев ввода и вывода:

Попробуй это здесь. (ПРИМЕЧАНИЕ. В последние несколько тестов это происходит довольно медленно. На все это уйдет около 10-15 секунд.)

0   <-> []
1   <-> [[]]
2   <-> [[][]]
3   <-> [[[]]]
4   <-> [[][][]]
5   <-> [[][[]]]
6   <-> [[[]][]]
7   <-> [[[][]]]
8   <-> [[[[]]]]
9   <-> [[][][][]]
10  <-> [[][][[]]]
11  <-> [[][[]][]]
12  <-> [[][[][]]]
13  <-> [[][[[]]]]
14  <-> [[[]][][]]
50  <-> [[[][[[]]]]]
383 <-> [[[][]][[[][]]]]

K (нгн / к) , 49 байтов

{$[#x;2/,/1,'&:'o'x;0]}
{$[x;o'|-1+-1-':&|2\x;()]}

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

использует формулу из примера в Bijection: древовидные списки - натуральные числа

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

f=(n,i)=>n?n&1<<i?[f(i),...f(n>>-~i)]:f(n,-~i):[]
g=([a,...b])=>a?g(b)*2+1<<g(a):0

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

идея кснора

Python 3 - знак / абс, 73 байта

f=lambda n:[[[]]*(n<0),[[]]*abs(n)]
g=lambda l:[-1,1][not l[0]]*len(l[1])

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

Прямая реализация, поддерживает отрицательные числа.

Целое число iзакодировано [sign(i), abs(i)], где sign(i)=[] if i > 0 else [[]]иabs(i)=[[]] * i , т.е. список пустых списков с длиной abs (i).

Python 3 - двоичный файл, 126 байт

Это более сложная версия (и намного длиннее ...), где абсолютное значение кодируется в виде двоичного списка.

f=lambda n:[[[]]*(n<0),[[[]]*int(i)for i in f"{n:+b}"[1:]]]
g=lambda l:[-1,1][not l[0]]*int(''.join(map(str,map(len,l[1]))),2)

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

Stax , всего 33 байта

Эти программы противоположны друг другу. Они преобразуются в и из всех списков пустот и всех неотрицательных целых чисел, так что они включают 0. Кажется, что это может быть известная функция из какой-то алгебры, которую я не знаю. Чтобы обернуть голову вокруг этого, я сначала реализовал программы как функции в python.

def convert_to_void(n):
    lst = []
    while n > 0:
        n -= 1
        choices = len(lst) + 1
        choice = n % choices
        cutpoint = len(lst) - choice
        n //= choices
        newgroup = lst[cutpoint:]
        del lst[cutpoint:]
        lst.append(newgroup)
    return lst

def convert_from_void(lst):
    n = 0
    while lst != []:
        newgroup = lst.pop()
        n *= len(lst) + len(newgroup) + 1
        n += len(newgroup) + 1
        lst.extend(newgroup)
    return n

Программы Stax ведут себя одинаково.

Неотрицательное целое число → Список пустот, 15 байт

ƒâ₧~└3BI─¿-rÅ;ì

Запустите и отладьте его

Список пустот → неотрицательное целое число, 18 байт

Çäê[!σ`c↑Ö§░NR╥ç=Æ

Запустите и отладьте его