23
\$\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\$
10
  • \$\begingroup\$ If the integer appears at one depth multiple times, do we have to only return that depth number once? \$\endgroup\$
    – Giuseppe
    Sep 28, 2017 at 20:23
  • \$\begingroup\$ @Giuseppe yes, that's correct. \$\endgroup\$
    – hyper-neutrino
    Sep 28, 2017 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\$
    – hyper-neutrino
    Sep 28, 2017 at 20:43
  • 1
    \$\begingroup\$ Multi-digit numbers should also be added in a test case, if they can occur. \$\endgroup\$
    – Zgarb
    Sep 28, 2017 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\$
    – hyper-neutrino
    Sep 29, 2017 at 12:00

19 Answers 19

8
\$\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\$
6
  • \$\begingroup\$ I came up with a quite similar solution for 81 bytes: Try it online! \$\endgroup\$
    – Laikoni
    Sep 29, 2017 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, 2017 at 15:40
  • \$\begingroup\$ Feel free to update your answer. :) \$\endgroup\$
    – Laikoni
    Sep 29, 2017 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, 2017 at 15:54
  • 2
    \$\begingroup\$ You can remove the parenthesis around E n and L s. \$\endgroup\$
    – 4castle
    Sep 29, 2017 at 17:02
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\$
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\$
5
\$\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\$
1
  • \$\begingroup\$ \o/ this was my exact solution when comparing Jelly to Python. yay! :P \$\endgroup\$
    – hyper-neutrino
    Sep 28, 2017 at 22:03
5
\$\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\$
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\$
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\$
4
  • \$\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\$
    – hyper-neutrino
    Sep 28, 2017 at 21:28
  • \$\begingroup\$ This doesn't quite work: tio.run/##y0rNyan8//9R45ZU60MrD607sfxR446HO@YDBR7u6ju09fCEI/… \$\endgroup\$
    – hyper-neutrino
    Sep 28, 2017 at 21:31
  • \$\begingroup\$ Hmm found bugs during the write up... deleting for now. \$\endgroup\$ Sep 28, 2017 at 21:33
  • \$\begingroup\$ Ah I had somehow changed the order of my concatenation :/ should be working now \$\endgroup\$ Sep 28, 2017 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\$
2
  • \$\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, 2017 at 9:30
  • \$\begingroup\$ @Neil, excellent point. Now changed to e.pop for a loss of one byte. \$\endgroup\$ Sep 29, 2017 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\$
7
  • \$\begingroup\$ Try if type(a[i])!=int for -1 byte \$\endgroup\$
    – hyper-neutrino
    Sep 28, 2017 at 20:45
  • \$\begingroup\$ Try l+=[d] for -5 bytes \$\endgroup\$
    – hyper-neutrino
    Sep 28, 2017 at 20:45
  • \$\begingroup\$ Try l+=[d]*(a[i]==n) for -whatever_number_of_bytes_it_is \$\endgroup\$
    – hyper-neutrino
    Sep 28, 2017 at 20:48
  • 1
    \$\begingroup\$ []==a[i]*0 for a shorter type check \$\endgroup\$
    – ovs
    Sep 28, 2017 at 20:52
  • \$\begingroup\$ Try iterating through a instead of a range and using getitem so much for -~20 bytes \$\endgroup\$
    – hyper-neutrino
    Sep 28, 2017 at 20:54
1
\$\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\$
1
\$\begingroup\$

APL (Dyalog Classic), 31 30 bytes

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

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

Try it online!

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

Vyxal, 75 bitsv2, 9.375 bytes

w⁽Þf↔ƛ⁰O;¯T

Try it Online!

Might be able to shave off a byte here, port of Jelly

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

ReRegex, 299 bytes

#import math
(a[^<>\[\]]*?)\[/$1</(a.*?(_*)<[^<>\[\]]*?)\[/$1_$2</(a.*?(_*)<[^<>\[\]]*?)\]/$1$2>/(a.*?(_*)>[^<>\[\]]*?)\[/$1$2</(a.*?_(_*)>[^<>\[\]]*?)\]/$1$2>/a([^\[\]]*$)/bb$1/^(.*?)b(.*)b(.*?(_*)<[^<]*)\1/$1b$2,d<$4>b$3/^(.*?)b,?(.*)b(.(?!\1))*$/$2/(,|^)([^,<>\[\]]+)([^<>\[\]]*),\2/$1$2$3/#input

With comments

#import math
# Count the depths of all braces
(a[^<>\[\]]*?)\[/$1</
(a.*?(_*)<[^<>\[\]]*?)\[/$1_$2</
(a.*?(_*)<[^<>\[\]]*?)\]/$1$2>/
(a.*?(_*)>[^<>\[\]]*?)\[/$1$2</
(a.*?_(_*)>[^<>\[\]]*?)\]/$1$2>/
# Move to step b
a([^\[\]]*$)/bb$1/
# Record all the depths of all instances of the input
^(.*?)b(.*)b(.*?(_*)<[^<]*)\1/$1b$2,d<$4>b$3/
# Move to finalize
^(.*?)b,?(.*)b(.(?!\1))*$/$2/
# Deduplicate
(,|^)([^,<>\[\]]+)([^<>\[\]]*),\2/$1$2$3/
#input

Try it online!

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

Perl 5 -a, 65 bytes

$q=<>;s,-?\d+,$q-$&||$k{$`=~y/\[//-$`=~y/]//}++,ge;say for keys%k

Try it online!

Result is 1-indexed.

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

Ruby, 63 bytes

f=->n,a,x=0{a.map{f[n,_1,x+1]rescue n==_1 ?x:p}.flatten-[p]|[]}

Attempt This Online!

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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