# Decompress a ragged list

Your input is a ragged list of possibly empty lists of non-negative integers. For example, [[2,0],[[]],[[[],[1],[]],[]]] is a valid input. This input is a "compressed" ragged list. What this means is that when we have a list of numbers, we interpret those as a list of indices, indexing the output.

For example, if I=[[2,0],[[]],[[[],[1],[]],[]]] then the decompressed list is O=[[[[],[[]],[]],[[]],[[[],[[]],[]],[]]], because if we replace [2,0] with O[2][0]=[[],[[]],[]] and [1] with O[1]=[[]] in the input list, we get O as the output.

The naïve method is just to have the input as a working list and then iteratively replace lists of numbers with by indexing the working list. However this runs into two potential problems:

First, consider an input like I=[[1,0,0,0],[2],[[[[]]]]]. Here if we index this input like so: I[1][0][0][0] we will get an index error. We would have to first replace [2] with I[2] giving tmp=[[1,0,0,0],[[[[]]]],[[[[]]]]]. Now we can replace [1,0,0,0] with tmp[1][0][0][0] giving O=[[],[[[[]]]],[[[[]]]]] as the output.

Another difficulty is that we can get a form of co-recursion with inputs like [1],[[0,1],[]]. This decompresses to [[[],[]],[[],[]]]

Full blown infinite recursion like [[0]] or [[1],[[0],[0]]] won't happen though.

# Rules

Your input is a ragged list I that may contain lists consisting of only numbers. Your task is to find a ragged list O, containing only lists, where if you replace every list L of numbers in I by O[L] you get O as the output. Your program must output O. You may assume that a unique solution exists.

You can choose between 0- and 1-based indexing. You can also choose the order of the indices, i.e. whether [2,3,4] corresponds to O[2][3][4] or O[4][3][2].

This is so shortest code wins.

# Examples

[] -> []
[[],[[],[]]] -> [[],[[],[]]]
[[[],[]],[[0],[0]],[[1],[1]]] -> [[[],[]],[[[],[]],[[],[]]],[[[[],[]],[[],[]]],[[[],[]],[[],[]]]]]
[[[],[[],[],[[]]]],[0,1,2]] -> [[[],[[],[],[[]]]],[[]]]
[[1,0,0,0],[2],[[[[]]]]] -> [[],[[[[]]]],[[[[]]]]]
[[1],[[],[0,0]]] -> [[[],[]],[[],[]]]
[[1],[[2,0,2],[0,0],[]],[[1],[0]]] -> [[[],[],[]],[[],[],[]],[[[],[],[]],[[],[],[]]]]

• Took me a few minutes to make sense of this but it’s a nice challenge Commented Feb 5, 2022 at 16:23
• Would like to see one that work well for infinite recurse. Tried one but it fail JSON stringifying
– l4m2
Commented Feb 5, 2022 at 18:07
• You could make understanding the question a bit easier by formatting I to be on several lines, making it visually parseable. I had to copy paste I and O to an editor to make sense of the brackets (the first O= is missing a final bracket, by the way). Commented Feb 5, 2022 at 19:03
• Also, I believe "inputs like [1],[[0,1],[]]" is supposed to have a wrapping pair of brackets around it (maybe it's implied, but best to have it explicit). Commented Feb 5, 2022 at 19:08
• "the first O= is missing a final bracket" <-- actually, it just has an extra initial one that's to be deleted. Commented Feb 5, 2022 at 19:19

# JavaScript (Node.js), 94908786 85 bytes

f=(x,n,s=(g=y=>y[0]>=' '?n=y.map(b=>e=e[b]||0,e=x)<e.map?e:y:y.map(g))(x))=>n?f(s):s


Try it online!

After y[0]>= is U+00A0

• Brilliant solution! I started to work on mine but it is way over 87 bytes. ;) Commented Feb 6, 2022 at 12:11
• @brotherFilip I think it quite intended and how's yours?
– l4m2
Commented Feb 6, 2022 at 12:15
• @tsh Fail if y is []
– l4m2
Commented Feb 7, 2022 at 3:11
• @tsh [][0] is undefined and undefined+0==undefined&undefined+0>undefined are both false
– l4m2
Commented Feb 7, 2022 at 3:13
• y[0]+0==y[0] -> x[y[0]+0+0]
– tsh
Commented Feb 7, 2022 at 3:19

# Python 2, 138 bytes

def f(x):
def g(y):y[:]=h(x,y)if[]<y<[f]else map(g,y)*0+y
h=lambda z,y:h(x,z+y)if[]<z<[f]else(h(z[y[0]],y[1:])if y[1:]else z[y[0]]);g(x)

Attempt This Online!

"Decompresses" the list in-place.

Function g does the main recursion. Function h looks ahead to resolve individual multi-step compressions where needed. The main purpose of function f is to put x in the closures of g and h.

# Clojure, 126 bytes

#(loop[a %](letfn[(g[x](let[y(get-in a x)](cond(=[]x)x(coll? y)y(every? coll? x)(mapv g x)1 x)))](if(= a(g a))a(recur(g a)))))


Try it online!

# Python3, 353 bytes:

from itertools import*
S=str
g=lambda x:[x]if x and int==type(x[0])else[j for k in x for j in g(k)]
def r(v,p):
for i in p:
try:
l=v
for x in i:
l=l[x]
v=eval(S(v).replace(S(i),S(l)))
except:return 0
return [0,v][all(i in'[], 'for i in S(v))]
f=lambda x:i[0]if(i:=[l for i in permutations(g(x),len(g(x)))if(l:=r(eval(S(x)),i))])else i


Try it online!

• 345 Commented Feb 6, 2022 at 0:13