18
\$\begingroup\$

Consider this nested array

[[1,2,4],[1,2,3],[2,3]]

In each subarray in which 1 appears, a 2 appears. You might say that 1's presence is dependent on 2's presence. The converse is not true, as 2 appears in a subarray without 1. Additionally, 3 is dependent on 2, and 4 is dependent on 1 and 2.

Task

Given a list of lists of positive integers (in whatever I/O form is most convenient for you) remove only the integers which are dependent on integers larger than themselves. In other words, for every integer A that is dependent on an integer B, and B>A, remove A.

You may assume:

Positive integers only

Input will not be nested further than one level, as in the example above

No integer will appear more than once in a given subarray

Subarrays will be sorted (increasing or decreasing, whichever is more convenient as long as you state in your answer)

No empty arrays anywhere in input

Examples:

in: [[1,2,4],[1,2,3],[2,3]]
out: [[2,4],[2,3],[2,3]]
in: [[3,4],[5,6]]
out: [[4],[6]]
in: [[1,2,3],[1,2,3,4],[2,3,4]]
out: [[3],[3,4],[3,4]]
in: [[1]]
out: [[1]]
in: [[2,12],[2,13],[2,14]]
out: [[2,12],[2,13],[2,14]]

Shortest code wins :)

Improve this question
\$\endgroup\$

9 Answers 9

Reset to default
3
\$\begingroup\$

Python, 104 93 bytes

lambda i:[[x for x in a if~-any(x<c>0<all(c in d for d in i if x in d)for c in a)]for a in i]

Attempt This Online!

Stupid naïve iterative solution which I'm really not happy with. A recursive solution will be shorter.

-11 bytes thanks to a hint from xnor.

for a in z for b in a for c in b for d in c for e in d for f in e for g in f for h in g for i in h for j in i for k in j for l in j for m in l for n in m for o in n for p in o for q in p for r in q for s in r for t in s for u in t for v in u for w in v for x in w for y in x for z in y please kill me why is python's syntax so whitespace and keyword heavy
Improve this answer
\$\endgroup\$
1
  • 1
    \$\begingroup\$ I think the mess of loops could be simplified a little by noting that the candidate c's that x might depend on are restricted to those also in a along with x. \$\endgroup\$
    – xnor
    Commented Jan 9, 2022 at 7:58
3
\$\begingroup\$

Charcoal, 21 bytes

ＩＥθΦι⬤ι∨¬›νλ⊙θ‹№πν№πλ

Try it online! Link is to verbose version of code. Explanation:

  θ                     Input array
 Ｅ                      Map over subarrays
    ι                   Current subarray
   Φ                    Filtered where
      ι                 Current subarray
     ⬤                  All elements satisfy
          ν             Innermost element
        ¬›              Not greater than
           λ            Inner element
       ∨                Logical Or
             θ          Input array
            ⊙           Any subarray satisfies
               №        Count of
                 ν      Innermost element
                π       In innermost subarray
              ‹         Is less than
                  №     Count of
                    λ   Inner element
                   π    In innermost subarray
Ｉ                       Cast to string
                        Implicitly print
Improve this answer
\$\endgroup\$
3
\$\begingroup\$

Jelly, 15 bytes

ċƇf/>Ƈ⁹ȧ
çⱮFḟ@Ɱ

A monadic Link accepting a list of lists of strictly positive integers that yields a list of lists of strictly positive integers.

Try it online! (The footer calls the Link for each and formats the output)

How?

ċƇf/>Ƈ⁹ȧ - Helper Link: list of lists, A; integer, I
 Ƈ       - filter keep those lists in A for which:
ċ        -   count occurrences of I - truthy if the list contains I
   /     - reduce this list of lists that contain I by:
  f      -   filter keep
             - gets us a list of those values appearing in all of them
      ⁹  - use I as the right argument of:
     Ƈ   -   filter keep those for which:
    >    -     greater than I?
       ȧ - logical AND I (non-vectorising)
             - i.e. I if it is a consistently dependent smaller integer, else 0

çⱮFḟ@Ɱ - Link: list of lists, A
  F    - flatten A
 Ɱ     - map across each integer I in that with:
ç      -   call the Helper Link as a dyad - f(A, I)
     Ɱ - map across each list in A with:
    @  -   with swapped arguments:
   ḟ   -     filter discard
Improve this answer
\$\endgroup\$
3
\$\begingroup\$

R, 167 163 159 157 147 bytes

Or R>= 4.1, 126 bytes by replacing three function occurrences with \s.

Edit: -2 bytes thanks to @Giuseppe and -10 bytes thanks to @Dominic van Essen.

function(x,b=combn(c(0,sort(unique(unlist(x)))),2))lapply(x,setdiff,b[1,apply(b,2,function(y,`+`=function(k)sapply(x,match,x=y[k],0))all(!+1|+2))])

Try it online!

That turned out long...

Straightforward approach:

  1. Create all pairs of values from input list (leading zeros to fix issues with 1-length inputs). unique and sort take care of the "first element is smaller" requirement.
  2. Define a helper function + to look for a value in nested list.
  3. Which pairs are dependent? (Uses \$\lnot p \lor q\$ for implication.) Extract first elements from them.
  4. setdiff those from all sublists.
Improve this answer
\$\endgroup\$
6
  • \$\begingroup\$ sort unique is very clever \$\endgroup\$
    – thejonymyster
    Commented Jan 10, 2022 at 13:26
  • \$\begingroup\$ trivial 2 byte reduction by shoving s and b into function arguments and removing the {} \$\endgroup\$
    – Giuseppe
    Commented Jan 10, 2022 at 16:15
  • \$\begingroup\$ @Giuseppe, thanks - that was a leftover from previous attempts. \$\endgroup\$
    – pajonk
    Commented Jan 10, 2022 at 16:31
  • \$\begingroup\$ Do you need both of the leading zeros? It seems to work with 1-length inputs with only one of them... \$\endgroup\$
    – Dominic van Essen
    Commented Jan 15, 2022 at 9:50
  • \$\begingroup\$ ...and possibly you could use apply instead of sapply(1:ncol()), like this... \$\endgroup\$
    – Dominic van Essen
    Commented Jan 15, 2022 at 9:57
2
\$\begingroup\$

Haskell, 80 70 bytes

f l=filter(\n->all(\m->m<=n||any((&&).elem n<*>all(/=m))l)$l>>=id)<$>l

Try it Online!

-10 bytes thanks to Wheat Wizard

Improve this answer
\$\endgroup\$
1
2
\$\begingroup\$

05AB1E, 14 12 bytes

εʒδåÏ.«Ãy›O_

Try it online or verify all test cases.

Explanation:

ε            # Map over each inner list of the (implicit) input list of lists:
 ʒ           #  Filter this inner list by:
  δ          #   Map over each list of the (implicit) input list of lists:
   å         #    Check if it contains the current integer
    Ï        #   Only keep those lists from the (implicit) input list of lists
     .«      #   Reduce the remaining list of lists by:
       Ã     #    Keep the values which are present in both lists
        y›   #   Then check which remaining values are larger than the current integer
          O  #   Sum to get the amount of values for which this is truthy
           _ #   Check if this sum is 0
             # (after which the modified list of lists is output implicitly as result)
Improve this answer
\$\endgroup\$
2
\$\begingroup\$

Wolfram Language (Mathematica), 62 60 bytes

#/.(i#⋂##&@@#~Select~MemberQ@ii||i->Set@$)/@Join@@#&

Try it online!

⋂ are \[Function]\[Intersection]\[VectorLessEqual].

   (i                                     )/@Join@@# for all i in input
#/.                                i->Set@$             remove i if
      #⋂##&@@                                             intersection of
             #~Select~MemberQ@i                             lists containing i
                               i||                       not all ≤i
Improve this answer
\$\endgroup\$
1
\$\begingroup\$

JavaScript (ES6), 79 bytes

Expects an array of sets.

a=>a.map(([...b])=>b.filter(p=>!b.some(q=>q>p&a.every(b=>b.has(q)|!b.has(p)))))

Try it online!

Improve this answer
\$\endgroup\$
1
\$\begingroup\$

Ruby, 85 bytes

->l{l.map{|a|a-l.flatten.select{|x|l.select{|c|c&[x]!=[]}.reduce(&:&).any?{|y|y>x}}}}

Try it online!

Improve this answer
\$\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.