19
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ If the integer appears at one depth multiple times, do we have to only return that depth number once? \$\endgroup\$ – Giuseppe Sep 28 '17 at 20:23
  • \$\begingroup\$ @Giuseppe yes, that's correct. \$\endgroup\$ – HyperNeutrino Sep 28 '17 at 20:24
  • 1
    \$\begingroup\$ @Adám Well given that one of my test cases has zeros, no. Also I will add that negative integers are fair game. \$\endgroup\$ – HyperNeutrino Sep 28 '17 at 20:43
  • 1
    \$\begingroup\$ Multi-digit numbers should also be added in a test case, if they can occur. \$\endgroup\$ – Zgarb Sep 28 '17 at 20:48
  • 1
    \$\begingroup\$ @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. \$\endgroup\$ – HyperNeutrino Sep 29 '17 at 12:00

15 Answers 15

7
\$\begingroup\$

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}
\$\endgroup\$
7
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ I came up with a quite similar solution for 81 bytes: Try it online! \$\endgroup\$ – Laikoni Sep 29 '17 at 13:48
  • \$\begingroup\$ @Laikoni Very nice, do you want to post it yourself, or do you suggest I update mine? \$\endgroup\$ – H.PWiz Sep 29 '17 at 15:40
  • \$\begingroup\$ Feel free to update your answer. :) \$\endgroup\$ – Laikoni Sep 29 '17 at 15:46
  • \$\begingroup\$ Concerning the NB: I tried to get rid of the import, but endet up at 88 bytes: Try it online! \$\endgroup\$ – Laikoni Sep 29 '17 at 15:54
  • 2
    \$\begingroup\$ You can remove the parenthesis around E n and L s. \$\endgroup\$ – 4castle Sep 29 '17 at 17:02
6
\$\begingroup\$

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!

\$\endgroup\$
4
\$\begingroup\$

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!

\$\endgroup\$
4
\$\begingroup\$

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]
\$\endgroup\$
  • \$\begingroup\$ \o/ this was my exact solution when comparing Jelly to Python. yay! :P \$\endgroup\$ – HyperNeutrino Sep 28 '17 at 22:03
4
\$\begingroup\$

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 :(

\$\endgroup\$
3
\$\begingroup\$

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.

\$\endgroup\$
2
\$\begingroup\$

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!

\$\endgroup\$
2
\$\begingroup\$

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.

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

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)
\$\endgroup\$
  • \$\begingroup\$ 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 \$\endgroup\$ – HyperNeutrino Sep 28 '17 at 21:28
  • \$\begingroup\$ This doesn't quite work: tio.run/##y0rNyan8//9R45ZU60MrD607sfxR446HO@YDBR7u6ju09fCEI/… \$\endgroup\$ – HyperNeutrino Sep 28 '17 at 21:31
  • \$\begingroup\$ Hmm found bugs during the write up... deleting for now. \$\endgroup\$ – Jonathan Allan Sep 28 '17 at 21:33
  • \$\begingroup\$ Ah I had somehow changed the order of my concatenation :/ should be working now \$\endgroup\$ – Jonathan Allan Sep 28 '17 at 21:36
1
\$\begingroup\$

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

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

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

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

APL (Dyalog Classic), 31 30 bytes

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

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

Try it online!

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

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
\$\endgroup\$
0
\$\begingroup\$

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;
}
\$\endgroup\$

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.