# Deep Search a List

For this challenge, a list is considered valid if and only if it consists entirely of integers and valid lists (recursive definitions \o/). For this challenge, given a valid list and an integer, return a list of all depths at which the integer can be found.

# Example

Let's consider list [1, [2, [3, [1, 2, 3], 4], 1], 1] and integer 1. Then, we can draw out the list like this:

Depth 0 1 2 3
Num   1
2
3
1
2
3
4
1
1


You'll notice that 1 shows up at depths 0, 1, 3. Thus, your output should be 0, 1, 3 in some reasonable format (order does not matter).

The depth may be either 0- or 1-indexed, but please specify in your submission which one it is.

# Test Cases (0-indexed)

For list [1,[2,[3,4],5,[6,7],1],[[[[5,2],4,[5,2]]],6],3]:

1 -> [0, 1]
2 -> [1, 4]
3 -> [0, 2]
4 -> [2, 3]
5 -> [1, 4]
6 -> [1, 2]
7 -> 


For list [[[[,0],1],0],1]:

0 -> 1, 3
1 -> 0, 2, 4


For list [11,22,[33,44]]:

11 -> 
22 -> 
33 -> 
44 -> 


Return an empty list if the search term does not exist in the list anywhere.

Negative and zero values are valid in the input list and term.

• If the integer appears at one depth multiple times, do we have to only return that depth number once? Sep 28, 2017 at 20:23
• @Giuseppe yes, that's correct. Sep 28, 2017 at 20:24
• @Adám Well given that one of my test cases has zeros, no. Also I will add that negative integers are fair game. Sep 28, 2017 at 20:43
• Multi-digit numbers should also be added in a test case, if they can occur. Sep 28, 2017 at 20:48
• @KevinCruijssen Yes, yes, no, and yes. So you can take inputs both as strings, and you can display the depth in any order, but not multiple times. Sep 29, 2017 at 12:00

# Mathematica, 25 bytes

Tr/@Union[1^Position@##]&


(returns 1-indexed output)

# Explanation

                         test  {1, {2, {3, {1, 2, 3}, 4}, 1}, 1}
Position[test,1]  {{1}, {2, 2, 2, 1}, {2, 3}, {3}}
1^Position[test,1]  {{1}, {1, 1, 1, 1}, {1, 1}, {1}}
Union[1^Position[test,1]]  {{1}, {1, 1}, {1, 1, 1, 1}}
Tr/@Union[1^Position[test,1]]  {1, 2, 4}


Thanks Bruce Forte for saving some bytes, and Laikoni for saving some more.

Thanks 4castle for saving 4 bytes.

Haskell has no data type for this kind of list, so I made my own.

This solution is 1-indexed

import Data.List
data T=E Int|L[T]
E n%x=[0|x==n]
L s%x=nub$map(+1).(%x)=<<s  Try it online! First I define (recursively) a data type T T has either type E Int (single element of type Int) or L[L] (list of type T). (%) is function that takes 2 arguments, on of type T, the list through which we are searching, and x, the Int we are looking for. Whenever (%) finds something that is a single element E n, it checks n for equality with x and returns 0 if True. When (%) is applied to an L s (where s has type [T]) it runs (%) on all the elements of s and increments the result (as the depth is increasing since we are looking inside s), and the concatenates the result. nub then removes the duplicates from the list NB. import Data.List is only for nub. • I came up with a quite similar solution for 81 bytes: Try it online! Sep 29, 2017 at 13:48 • @Laikoni Very nice, do you want to post it yourself, or do you suggest I update mine? Sep 29, 2017 at 15:40 • Feel free to update your answer. :) Sep 29, 2017 at 15:46 • Concerning the NB: I tried to get rid of the import, but endet up at 88 bytes: Try it online! Sep 29, 2017 at 15:54 • You can remove the parenthesis around E n and L s. Sep 29, 2017 at 17:02 # Python 2, 68 bytes f=lambda l,k,d=-1:l>[]and f(l,k,d+1)|f(l[1:],k,d)or{d}-{d+(l==k)}  Try it online! # Python 2, 72 bytes f=lambda l,k,d=0:set([d]*(k in l)).union(*[f(x,k,d+1)for x in l if[]<x])  Try it online! # Jelly, 11 8 bytes WẎÐĿċ€IT  Try it online! ### How it works WẎÐĿċ€IT Main link. Left argument: A (array). Right argument: n (integer) W Wrap; yield [A]. ÐĿ Repeatedly apply the link to the left until the results are no longer unique. Yield the array of all unique results. Ẏ Concatenate all elements at depth 1 in the array. The last array of the array of results is completely flat. ċ€ Count the occurrences of n in each intermediate result. I Compute all forward differences. T Truth; yield the array of all indices of non-zero differences.  ### Example run For left argument [1, [2, [3, [1, 2, 3], 4], 1], 1]  W first yields the following array. [[1, [2, [3, [1, 2, 3], 4], 1], 1]]  ẎÐĿ repeatedly concatenates all elements at depth 1, reducing the depth of the array by 1 in each step. This yields the following array of intermediate results. [ [[1, [2, [3, [1, 2, 3], 4], 1], 1]], [ 1, [2, [3, [1, 2, 3], 4], 1], 1 ], [ 1, 2, [3, [1, 2, 3], 4], 1, 1 ], [ 1, 2, 3, [1, 2, 3], 4, 1, 1 ], [ 1, 2, 3, 1, 2, 3, 4, 1, 1 ] ]  For right argument 1, ċ€ counts the occurrences of 1 in each intermediate result. [0, 2, 3, 3, 4]  I now takes all forward differences. [2, 1, 0, 1]  Non-zero differences correspond to steps in which at least one other 1 was added to depth 1. Thus, a non-zero difference at index k indicates the presence of a 1 at depth k. T finds the indices of all truthy elements, yielding the desired result: [1, 2, 4]  • \o/ this was my exact solution when comparing Jelly to Python. yay! :P Sep 28, 2017 at 22:03 # R, 1019592 100 bytes f=function(L,n,d=0)unique(unlist(Map(function(x)if(n%in%unlist(x))"if"(is.list(x),f(x,n,d+1),d),L)))  Try it online! Recursive solution; it's quite inefficient in bytes, but R lists are super annoying to work with. Basically, takes L, and for each element x of L, (which is either a list or an atomic vector of one element), checks if n is %in% x, then checks if x is a list. If it isn't, then x==n so we return the depth d; otherwise we recursively call f on x, incrementing d. This, of course, returns a list, which we unlist and unique to ensure the right output (returning a vector of integer depths); returns NULL (an empty list) for invalid n. Apparently, %in% doesn't search recursively through a list like I thought, so I have to unlist(x) for +8 bytes :( # APL (Dyalog), 39 bytes* Full program. Prompts for list, then for number. Prints 1-based list to STDOUT. ⌊2÷⍨⍸∨⌿⍞⍷⎕FMT⎕JSON⍠'Compact'0⊢⎕  Try it online! ⎕ prompt for list ⊢ yield that (separates 0 and ⎕) ⎕JSON⍠'Compact'0 convert to indented JSON string with newlines ⎕FMT convert to matrix (one newline-delimited line per row) ⍞⍷ prompt for number as string and indicate where it begins in that ∨⌿ vertical OR reduction (i.e. which columns it begins in) ⍸ indices of those beginnings 2÷⍨ halve that (levels are indented with two spaces) ⌊ round down (because first data column is column 3) * In Dyalog Classic, counting ⍸ as ⎕U2378 and ⍠ as ⎕OPT. # PHP, 117 bytes $r;function z($a,&$r,$i=0){foreach($a as $v){is_int($v)?(@in_array($i,$r[$v])?:$r[$v][]=$i):z($v,$r,$i+1);}}z($s,\$r);


Try it online!

## JavaScript (ES6), 79 68 bytes

f=(a,n,r=new Set,d=0)=>a.map(e=>e.map?f(e,n,r,d+1):e-n||r.add(d))&&r


Returns a Set. If this is unacceptable, use &&[...r] at a cost of 5 bytes.

# Jelly,  17  16 bytes

⁴e®;©ȧ⁸ḟ⁴ẎµÐĿȧ®T’


A full program taking two command line arguments the list and an element to check for, and printing the depth or depths (if any) at which the element exists. The results are 1-indexed.

Try it online!

### How?

⁴e®;©ȧḟ⁴ẎµÐĿȧ®T’ - Main link: list, L
µÐĿ    - loop, collecting updated values of L, until a fixed point is reached:
⁴                -   4th argument (2nd program input) = the number
e               -   exists in (the current version of) L?
®              -   recall value from the register (initially 0)
;             -   concatenate the two
©            -   (copy this result to the register)
⁴         -   4th argument (2nd program input) again
ḟ          -   filter out (discard any instances of the number)
ȧ           -   logical and (non-vectorising)
Ẏ        -   tighten (flatten the filtered L by one level to create the next L)
®   - recall value from the register
ȧ    - logical and (non-vectorising)
T  - truthy indexes (1-indexed)
’ - decrement (account for the leading zero from the initial register)

• Nice! Fun fact though: by using a very similar approach but by changing the order of things a bit, you can get 8 bytes. edit the approach is actually a bit different, nvm Sep 28, 2017 at 21:28
• This doesn't quite work: tio.run/##y0rNyan8//9R45ZU60MrD607sfxR446HO@YDBR7u6ju09fCEI/… Sep 28, 2017 at 21:31
• Hmm found bugs during the write up... deleting for now. Sep 28, 2017 at 21:33
• Ah I had somehow changed the order of my concatenation :/ should be working now Sep 28, 2017 at 21:36

# JavaScript (ES6), 73 74 bytes

f=(a,n,i=0,o={})=>a.map(e=>e.pop?f(e,n,i+1,o):e-n||o[i]++)&&Object.keys(o)


Explanation:

f=(a,                             //input array
n,                             //input number to search
i=0,                           //start at first level
o={}                           //object to store the finds
)=>
a.map(                        //loop through the array
e => e.pop ?                //is this element an array?
f(e, n, i+1, o) :    //if so, recurse on it to the next level
e-n || o[i]++        //otherwise, update o if element equals the number
) &&
Object.keys(o)                //return o's keys


Test cases

f=(a,n,i=0,o={})=>a.map(e=>e.pop?f(e,n,i+1,o):e-n||o[i]++)&&Object.keys(o)

var a = [1,[2,[3,4],5,[6,7],1],[[[[5,2],4,[5,2]]],6],3];
console.log(f(a,1));
console.log(f(a,2));
console.log(f(a,3));
console.log(f(a,4));
console.log(f(a,5));
console.log(f(a,6));
console.log(f(a,7));

console.log('___________');
var a = [[[[,0],1],0],1];
console.log(f(a,0));
console.log(f(a,1));

console.log('___________');
var a = [11,22,[33,44]];
console.log(f(a,11)) // 
console.log(f(a,22)) // 
console.log(f(a,33)) // 
console.log(f(a,44)) // 
console.log(f(a,55)) // empty set

• Although there are no test cases [yet], my reading of the question suggests that it's valid for e to be zero, which would throw off your test.
– Neil
Sep 29, 2017 at 9:30
• @Neil, excellent point. Now changed to e.pop for a loss of one byte. Sep 29, 2017 at 9:47

# Python 3, 12386 82 bytes

def f(a,n,l=[],d=0):
for e in a:l+=[d]*(e==n);0*e==[]and f(e,n,l,d+1)
return{*l}


Try it online!

-37 bytes thanks to Hyper Neutrino and ovs

-4 bytes thanks to Jonathan Frech

• Try if type(a[i])!=int for -1 byte Sep 28, 2017 at 20:45
• Try l+=[d] for -5 bytes Sep 28, 2017 at 20:45
• Try l+=[d]*(a[i]==n) for -whatever_number_of_bytes_it_is Sep 28, 2017 at 20:48
• []==a[i]*0 for a shorter type check
– ovs
Sep 28, 2017 at 20:52
• Try iterating through a instead of a range and using getitem so much for -~20 bytes Sep 28, 2017 at 20:54

# APL (Dyalog Classic), 31 30 bytes

Function. Left arg ⍺ is the needle, right arg ⍵ is the haystack.

{×≢⍵:(⍳⍺∊⍵),1+⍺∇⊃,/⍵/⍨≢¨⍴¨⍵⋄⍬}


Try it online!

# Octave, 126 122 bytes

function n=r(p,t,l)n=[];if nargin<3
l=0;end
for x=p
if iscell(q=x{1})a=r(q,t,l+1);else
a=l*find(q==t);end
n=union(n,a);end


Try it online!

For readability, I replaced spaces or ;'s with line ends where possible. Explanation of ungolfed code:

function n=r(p,t,l) % Declare function with list p, integer t and optional recursion depth l
n=[];
if nargin<3
l=0;            % If l is not given (first iteration), set l to zero (or one for 1-indexing)
end
for x=p             % Loop over list
if iscell(q=x{1})   % If loop variable x is a cell, we must go down one level.
a=r(q,t,l+1);  % So recurse to l+1.
else
a=l*find(q==t); % Empty if q~=t (because find(false)==[], and l*[]==[]), else equal to l*1==l.
end
n=union(n,a);       % Append to list of levels, make sure we only get distinct values.
end


# Java, 154 + 19 = 173 bytes

import java.util.*;


Set<Long>f(List l,long n){Set s=new HashSet();if(l.contains(n))s.add(0l);for(Object o:l)if(o instanceof List)for(long d:f((List)o,n))s.add(d+1);return s;}


Try It Online

## Ungolfed method

Set<Long> f(List l, long n) {
Set s = new HashSet();
if (l.contains(n))