11
\$\begingroup\$

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]]] -> [[[],[],[]],[[],[],[]],[[[],[],[]],[[],[],[]]]]
\$\endgroup\$
5
  • 2
    \$\begingroup\$ Took me a few minutes to make sense of this but it’s a nice challenge \$\endgroup\$
    – Jonah
    Feb 5 at 16:23
  • \$\begingroup\$ Would like to see one that work well for infinite recurse. Tried one but it fail JSON stringifying \$\endgroup\$
    – l4m2
    Feb 5 at 18:07
  • 1
    \$\begingroup\$ 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). \$\endgroup\$
    – Sundar R
    Feb 5 at 19:03
  • \$\begingroup\$ 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). \$\endgroup\$
    – Sundar R
    Feb 5 at 19:08
  • \$\begingroup\$ "the first O= is missing a final bracket" <-- actually, it just has an extra initial one that's to be deleted. \$\endgroup\$
    – Sundar R
    Feb 5 at 19:19

4 Answers 4

3
\$\begingroup\$

JavaScript (Node.js), 94 90 87 86 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

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

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.

\$\endgroup\$
1
\$\begingroup\$

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!

\$\endgroup\$
0
\$\begingroup\$

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!

\$\endgroup\$
1

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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