Ragged index of

Question

Your input is a ragged list of positive integers and a positive integer. Your task is to find that positive integer and return it's index, or if the positive integer doesn't exist, indicate it's nonexistence.

How are indices in ragged lists defined? They are simply lists of indices that when used consecutively to index the ragged list, return the desired element. For example, if the ragged list is [1,[2,3],[[4,5]],[]] then the index of 2 is [1,0] and the index of 5 is [2,0,1].

If there are multiple integers, return the index of the first one. That is, the one whose index is the smallest when compared lexicographically.

Rules

You can choose between 0 and 1 based indexing and also the order of the returned index.

You must indicate the non-existance of a solution in some easily identified manner. Here are some examples:

Ok

• Return a value that is not a list. For example, -1 or None
• Return an empty list
• Error in some way
• Exit the program

Not ok

• Infinite loop/recursion (if you want to use a resource exhaustion error, be sure to read this)
• Undefined behavior
• A list of integers, even if those integers are out of bounds or negative.

An exception to the last point. You may use a single consistent value that can never be the output to indicate nonexistence. For example, a program that returns [-1] whenever there is no solution is allowed, but a program that returns [-1] or [-2] when there isn't a solution is not allowed.

Finally, you can also return a list of all solutions in sorted order. If you use this IO format, you must return an empty list if there are no solutions.

Test cases

[], 1 -> None
[[[40]]], 40 -> [0,0,0]
[[1,[]],[[3]],3,[3]], 3 -> [1,0,0]
[5], 5 -> [0]
[[],[[],[]]], 5 -> None

Answer 1

Wolfram Language (Mathematica), 8 bytes

Position

Try it online!

Built-in that returns all indices, 1-indexed. A very interesting answer, I'm sure.

---

To return the first such index:

Wolfram Language (Mathematica), 13 bytes

FirstPosition

Try it online!

Another built-in. Returns Missing["NotFound"] if n is not present. Almost as interesting as the above.

Answer 2

APL(Dyalog Unicode), 14 bytes ^SBCS

Returns an empty list if the value is not present. 1-based indexing.

∊(∊↑⍸⍤=)∘(↑⍣≡)

Try it on APLgolf!

↑⍣≡ Mix right argument until homogeneous (array). This converts the nested list to a rectangular array by inserting 0's.
⍸⍤= All indices where the left argument is equal to the resulting array.
∊↑ Take 1 index if the left argument is present, 0 otherwise.
∊ Flatten resulting list. This might not be necessary, but returning results with different levels of nesting seems wrong.

If returning an out-of-bounds index for the error case would be allowed, something like ⊃⍸⍤=∘(↑⍣≡) could work.

Answer 3

Jelly, 2 bytes

œi

Try it online!

Just the builtin. 1-indexed and outputs an empty list if not found.

Marginally less built in:

Jelly, 4 bytes

=ŒṪṂ

Try it online!

1-indexed and outputs 0 if not found.

Answer 4

Javascript, 54 bytes

t=>g=a=>r=a.some?.((n,i)=>s=g(n)&&[i,...r])?s:a==t&&[]

Input the target and the array. Output an array or false if not found.

f=

t=>g=a=>r=a.some?.((n,i)=>s=g(n)&&[i,...r])?s:a==t&&[]

console.log(f(1)([]))
console.log(f(40)([[[40]]]))
console.log(f(3)([[1,[]],[[3]],3,[3]]))
console.log(f(5)([5]))
console.log(f(5)([[],[[],[]]]))

JavaScript 62 bytes

a=>t=>JSON.parse(a,(x,y)=>y.some?.(x=>z=x)?x?x+[,z]:z:y==t&&x)

f=

a=>t=>JSON.parse(a,(x,y)=>y.some?.(x=>z=x)?x?x+[,z]:z:y==t&&x)

console.log(f("[]")(1))
console.log(f("[[[40]]]")(40))
console.log(f("[[1,[]],[[3]],3,[3]]")(3))
console.log(f("[5]")(5))
console.log(f("[[],[[],[]]]")(5))

Input the array as JSON, and target value currying. Output a comma separated string or false if not found. It could be 58 bytes if a leading comma is acceptable.

Answer 5

Brachylog, 16 bytes

dbĖ|ċʰiʰgᵗz↰ʰkᵗc

Try it online!

Input as a list [list, item]. Output 0-indexed, innermost index first, declarative failure if not found. There's definitely a byte or two left to shave off with all this list juggling, but it's already 5 down from how it started, so I'm giving it a rest for now.

Brachylog, 16 bytes

h~t?bk|bB&hċi,B↰

Try it online!

This feels somehow worse.

Answer 6

Pari/GP, 72 bytes

f(l,a)=if(l==a,[],#l'&&s=[concat(i,r)|i<-[1..#l],e!=r=f(l[i],a)],s[1],e)

Try it online!

1-indexed. Returns e if not found.

---

Pari/GP, 64 bytes

f(l,a)=if(l==a,,#l'&&s=[r*x+i|i<-[1..#l],e!=r=f(l[i],a)],s[1],e)

Try it online!

Returns a polynomial whose coefficient list is the index, e.g., [[1, []], [[3]], 3, [3]], 3 -> x^2 + x + 2. I'm not sure if this is allowed.

1-indexed. Returns e if not found.

Answer 7

Python 2, 75 bytes

f=lambda n,l,h=[],t=0:f(n,l[0],h+[t])or f(n,l[1:],h,t+1)if[]<l else(l==n)*h

Try it online!

Answer 8

Python, 72 bytes (@att)

f=lambda L,n,*p:sum((f(l,n,*p,i:=i+1)for l in-1*L+L or[]),[p]*(i:=L==n))

Attempt This Online!

Old Python, 75 bytes

f=lambda L,n,*p:[p]*(i:=L==n)+sum([f(l,n,*p,i:=i+1)for l in-1*L+L or[]],[])

Attempt This Online!

1-based, outputs all matches.

Answer 9

Ruby, 63 59 bytes

f=->l,x{l*0==0?x==l:(x=l.index{|e|l=f[e,x]})&&[x,*l]-[1>0]}

Try it online!

f=->l,x{...}
Lambda taking l list, x element and return index or nil.

l*0==0?x==l:
if l is a value, return if it's the value, else:

(x=l.index{|e|l=f[e,x]})&&
x becomes index of{..} which may be nil, in that case return nil(falsely).
Block calls recursively f on each element returning true or an array of indexes( which are both truthy ), or false otherwise.

[x,*l==1>0?[]:l] [x,*l]-[1>0] else return that index and append l(next indexes) removing true.

Answer 10

Whython, 63 62 59 bytes

-3 bytes thanks to att

f=lambda l,n,i=0:[i]+f(l[i],n)?[l[i]]*0+f(l,n,i+1)?l-n or[]

Returns the 0-based ragged index if found; raises an exception if not found. Attempt This Online! Or, verify all test cases.

Explanation

We define a recursive function f that takes three arguments:

• l is the object we're searching--usually a list, but could also be an integer at the bottom of the recursion
• n is the number we're searching for
• i is the current index in l that we're testing

We want to error if the number is not found; using Whython's ? operator, we can catch any errors from deeper recursive calls and try the next case. As soon as we find the right number, we return a result instead of erroring. Or, once we run out of options, the error propagates back to the caller.

The function body has three cases, connected by ?:

[i]+f(l[i],n)

If l is a list and i is a valid index into that list, try recursing over l[i]. If that succeeds, it returns a list representing a ragged index, to which we prepend i and return. If the recursive call fails, or if l is not a list, or if len(l) <= i and therefore i is not a valid index into l, error and try the next branch:

[l[i]]*0+f(l,n,i+1)

If l is a list and i is a valid index into that list, try recursing over the same l with i+1. If that succeeds, it returns a list representing a ragged index, to which we add an empty list and return. If the recursive call fails, or if l is not a list, or if i is not a valid index into l, error and try the next branch:

l-n or[]

If l is an integer and is equal to n, we've found the number we're looking for; the difference is 0, so we return []. If l is not an integer, l-n errors; if l is an integer not equal to n, returning some nonzero integer causes an error when we return from the recursive call and try to add the result to a list.

Answer 11

Python3, 99 bytes:

f=lambda l,t,c=[]:next((m for i,a in enumerate([l,[]][l*0==0])if(m:=f(a,t,c+[i]))),0)if l!=t else c

Try it online!

Answer 12

JavaScript (ES6),  62  60 bytes

Saved 2 bytes thanks to @l4m2

Expects (value)(array). Returns false if not found.

n=>g=(a,...o)=>a.map?a.some((v,i)=>g(v,...o,i))&&r:a-n?0:r=o

Try it online!

Answer 13

05AB1E (legacy), 15 bytes

ΔQƶʒZĀ}нZˆĀ*}¯¨

1-based. Results in [[]] if the ragged list doesn't contain the integer.

Try it online. (Or here a scuffed attempt to create a test suite..)

Uses the legacy version of 05AB1E, because there apparently is a bug with Ā (Python-style truthify) incorrectly resulting in 1 for (some) empty strings..

Explanation:

Δ           # Loop until the result no longer changes:
 Q          #  Check for each value in the ragged list if it's equal the to
            #  second (implicit) input-integer
            #  (will use the implicit first input-list in the first iteration)
  ƶ         #  Multiply each inner value by its 1-based index
   ʒ  }н    #  Find the first inner list which is truthy for:
    Z       #   Push the flattened maximum ("" if it lacks integers)
     Ā      #   Check if this is truthy (thus not 0 nor "")
        Z   #  Push the flattened maximum of the found list (without popping)
         ˆ  #  Pop and add it the global array
        Ā   #  Truthify the integers in the ragged list
         *  #  Multiply it by the second (implicit) input-integer
}¯          # After the loop: push the global array
  ¨         # Remove the last value, since the `Δ`-loop will have looped an
            # additional time before it stops; otherwise we could have printed
            # the flattened maximum directly instead of using the global array
            # (after which this list is output implicitly)

Answer 14

Perl 5, 83 bytes

sub{($_,$n,@_)=@_;/\[/?push@_,0:/]/?pop:/,/?$_[-1]++:/^$n$/?return\@_:0for/\d+|./g}

Try it online!

Answer 15

Julia 1.0, 95 78 77 75 73 72 bytes

l::Int\n=l==n&&[]
l\n=for(i,v)=pairs(l);0∈(p=[i;v\n])||return p;end==0

Try it online!

Returns false for not found, 1-based indices for found.

l::Int\n = l==n && [] - base case, when first argument is an Integer: if it's equal to the second argument, return empty Array []; if it's not, return false (== 0).

0 ∈ (p=[i;v\n]) || return p - 1-based index i can never be 0, so if [i; v\n] contains a 0, that means the recursive call failed, move on. If v\n isn't 0, we found the number, so prepend the current index and return that back to the caller.

==0 at the end - This check happens at the end of the loop and always returns false (thanks to @MarcMush for -1 byte by using this). If for loop completed without returning, we didn't find the number anywhere. So return false to indicate failure.

Answer 16

Charcoal, 38 bytes

⊞υ⟦⟦⟧θ⟧ＦυＦＥ⁺⟦⟧§ι¹⟦⁺§ι⁰⟦λ⟧κ⟧⊞υκＩ⌊Φυ⁼⊟ιη

Try it online! Link is to verbose version of code. Outputs None if the desired element is not present in the ragged array. Explanation:

⊞υ⟦⟦⟧θ⟧Ｆυ

Start a breadth-first enumeration of all the elements and their ragged indices with the input list and an empty index.

ＦＥ⁺⟦⟧§ι¹⟦⁺§ι⁰⟦λ⟧κ⟧⊞υκ

If this element is a non-empty list then push all of its elements and their ragged indices to the search list.

Ｉ⌊Φυ⁼⊟ιη

Output the lexicographically earliest (if any) index of the desired element.