Deep Search a List

Question

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 -> [2]

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

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

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

11 -> [0]
22 -> [0]
33 -> [1]
44 -> [1]

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.

Answer 1

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}

Answer 2

Haskell, 102 93 80 76 bytes

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.

Answer 3

Python 2, 68 bytes

f=lambda l,k,d=-1:l>[]and f(l[0],k,d+1)|f(l[1:],k,d)or{d}-{d+(l==k)}

Try it online!

Answer 4

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!

Answer 5

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]

Answer 6

R, 101 95 92 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 :(

Answer 7

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.}

Answer 8

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!

Answer 9

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.

Answer 10

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)

Answer 11

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 = [[[[[1],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)) // [0]
console.log(f(a,22)) // [0]
console.log(f(a,33)) // [1]
console.log(f(a,44)) // [1]
console.log(f(a,55)) // empty set

Answer 12

Python 3, 123 86 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

Answer 13

APL (Dyalog Classic), 31 30 bytes

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

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

Try it online!

Answer 14

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

Answer 15

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))
        s.add(0l);
    for (Object o : l)
        if (o instanceof List)
            for (long d : f((List) o, n))
                s.add(d + 1);
    return s;
}