6
\$\begingroup\$

We define a tree-like list, or trist for short, as the empty list or a list containing only previously constructed trists.

The natural numbers can either include 0 or not, according to your preference.

The task is to create a pair of functions or complete programs f and g (they don't have to be named like this or even named at all) that implement a bijection between trists and the natural numbers. In other words:

  • f must be able to turn any trist into a natural number

  • g must be able to turn any natural number into a trist

  • f(g(n)) must equal n for any natural number n

  • g(f(l)) must be equivalent to l for any trist l

You can assume that all arguments and results fit in the usual numeric type for your language. Alternatively, instead of the numeric type you could represent a natural number as a list of binary digits, either consistently little- or consistently big-endian.

The shortest solution per language wins. If your functions are recursive, you must name them. If your language requires a statement separator or a newline between the two functions/programs, you don't have to count it.

This is a sample algorithm in Python3 (you are free to implement the bijection in any way you like):

def f(x):
    r = 0
    for y in x:
        r = (2 * r + 1) * 2**f(y)
    return r

def g(n):
    r = []
    while n:
        m = 0
        while n % 2 == 0:
            n //= 2
            m += 1
        n //= 2
        r = [g(m)] + r
    return r

tests = [
    [],
    [[]],
    [[],[]],
    [[[]],[],[[[]],[]]],
    [[[[[]]]]],
]
for l in tests: print(g(f(l)) == l)

for n in range(20): print(f(g(n)) == n)

It uses the following representation:

\$ \begin{array}{|l} f([~])=0\\ f([a_0,a_1,\ldots,a_{n-1}])=\overline{ 1\underbrace{0\ldots0}_{f(a_0)\\\text{zeroes}}~ 1\underbrace{0\ldots0}_{f(a_1)\\\text{zeroes}}~ \ldots~ 1\underbrace{0\ldots0}_{f(a_{n-1})\\\text{zeroes}}} {}_{(2)} \end{array} \$

Challenge inspired by @LeakyNun's question in chat.

\$\endgroup\$
3
  • \$\begingroup\$ Related \$\endgroup\$
    – Luis Mendo
    Jul 31, 2018 at 10:24
  • 2
    \$\begingroup\$ The similarity to Decode the Void is striking. Duplicate indeed, and I suck at searching PPCG. \$\endgroup\$
    – ngn
    Jul 31, 2018 at 11:13
  • 3
    \$\begingroup\$ PPCG sucks at being searched. \$\endgroup\$
    – JayCe
    Jul 31, 2018 at 19:23

1 Answer 1

2
\$\begingroup\$

Python 2, 118 114 109 105 103 97 94 bytes

f=lambda x:x>[]and f(x[:-1])*2+1<<f(x[-1])
g=lambda n:[g(len(w))for w in bin(n).split('1')[1:]]

Try it online!

Same encoding as the example...

\$\endgroup\$
3
  • \$\begingroup\$ @Lynn, it seems i can remove n and and it still works \$\endgroup\$
    – TFeld
    Jul 31, 2018 at 10:44
  • \$\begingroup\$ @TFeld I'm afraid this meta implies that f= and g= should be counted. Sorry for the confusion. You can still omit the newline, as I intended the byte count to be the sum of two separate functions/programs. \$\endgroup\$
    – ngn
    Jul 31, 2018 at 10:51
  • \$\begingroup\$ @ngn, No problem, I've counted them in my counts already (and omitted the newline) \$\endgroup\$
    – TFeld
    Jul 31, 2018 at 10:52

Not the answer you're looking for? Browse other questions tagged or ask your own question.