17
\$\begingroup\$

Given a list of lists of positive integers, output a subset of them so their union forms a continuous non-empty range with no numbers missing. For example, consider this input:

[
   [1, 2, 3, 5],
   [2, 4, 6],
   [7, 9, 11]
]

The union of the first 2 forms a continuous sequence: [1, 2, 3, 4, 5, 6] with no numbers missing. Adding the last one would create [1, 2, 3, 4, 5, 6, 7, 9, 11] which is missing 8 and 10 so would not be a valid answer.

Output can be either the indexes of the included lists or the lists themselves.

Lists are guaranteed to be sorted, and the list of lists will also be sorted lexicography. All lists will have at least one element. There may be more than one valid solution, if so you may choose output any of them, or all of them, or some of them. If you output multiple solutions all must be valid and they must be clearly separated.

There will never be no solutions.

Test cases

Input Output
[[1, 2, 3]] 0
[[1, 3], [2, 4]] 0, 1
[[2, 4], [4, 23], [8, 10], [8, 12], [9, 13], [10, 23], [11, 14]] 2, 3, 4, 6
[[1, 3], [2, 4], [5,7], [6,8]] 0,1 OR 2,3 OR 0,1,2,3
[[1, 17], [2,23], [3,42], [4,17], [5, 3912], [6]] 5
Improve this question
\$\endgroup\$
4
  • \$\begingroup\$ Would a list that include more numbers to include in the final list have precendent over a list that include fewer? For example: [[1,5][5,6][5,6,7]], could just be 2? \$\endgroup\$
    – JvdV
    Jan 10 at 18:16
  • 1
    \$\begingroup\$ @JvdV if there are multiple possible solutions you may choose to output any of them. No specific preference. \$\endgroup\$
    – mousetail
    Jan 10 at 18:17
  • \$\begingroup\$ Can we output the empty list as a solution? \$\endgroup\$
    – emanresu A
    Jan 12 at 10:30
  • \$\begingroup\$ No, as the problem states "a continuous non-empty range" \$\endgroup\$
    – mousetail
    Jan 12 at 10:31

16 Answers 16

Reset to default
3
\$\begingroup\$

Factor + math.combinatorics math.unicode, 61 57 bytes

[ all-subsets rest [ concat dup minmax [a,b] ⊃ ] find ]

Try it online!

Returns the lists that make up the range. Returns the first solution it finds.

  • all-subsets rest Powerset sans the empty set.
  • [ ... ] find Find the first element that returns true when [ ... ] is run on it.
  • concat The union of all sets in a sequence (with duplicates, but it doesn't matter).
  • dup minmax [a,b] Create a range from the minimum and maximum elements in the union.
  • ⊃ Is the union a superset of the range?
Improve this answer
\$\endgroup\$
3
\$\begingroup\$

Pyth, 12 bytes

f!-.+{SsT1ty

Try it online!

Returns a list of all answers, each in list of lists form.

Explanation

f!-.+{SsT1tyQ    # implicitly add Q
                 # implicitly assign Q = eval(input())
           yQ    # power set of Q
          t      # all but the first element (thus excluding the empty element)
f                # filter on lambda T
       sT        #   flatten T
      S          #   sort
     {           #   deduplicate
   .+            #   take the deltas (should be all 1s if we have a continuous range)
  -      1       #   remove all instances of 1
 !               #   not (will only be true for the empty list)
Improve this answer
\$\endgroup\$
3
\$\begingroup\$

Jelly, 9 bytes

ŒPṬSṠṢƑƲƇ

A monadic Link that accepts a list of lists of positive integers and yields a list of the valid lists of lists for which the union forms a continuous range.

Try it online! Or see the test-suite.

How?

ŒPṬSṠṢƑƲƇ - Link: list of lists of positive integers, A
ŒP        - powerset (of A)
        Ƈ - keep those for which:
       Ʋ  -   last four links as a monad:
  Ṭ       -     untruth - e.g. [[2], [2, 5, 7]] -> [[0, 1], [0, 1, 0, 0, 1, 0, 1]]
   S      -     sum (columns of that)           -> [0, 2, 0, 0, 1, 0, 1]
    Ṡ     -     sign                            -> [0, 1, 0, 0, 1, 0, 1]
      Ƒ   -     is invariant under?:
     Ṣ    -       sort                          -> 0

If we may also identify the empty set (as producing a continuous range of zero positive integers) then \$8\$ bytes: ŒPFṬṢƑƊƇ - test suite.

Improve this answer
\$\endgroup\$
3
\$\begingroup\$

Vyxal 22 18 17 15 or 10 bytes

This code output resulting range:

ṗƛÞfUs;'¯U1w⁼;,

Try it online!

and this (@lyxal) - the lists that are used in the range:

ṗꜝ'ƒ∪s¯1=A

Try it online!

Improve this answer
\$\endgroup\$
3
  • \$\begingroup\$ Here's a 10 byte answer that also works. It's similar to yours, but just uses a few tricks like the reduce-by modifier and keep only truthy. \$\endgroup\$
    – lyxal
    Jan 11 at 3:34
  • \$\begingroup\$ @lyxal Hmmm but output looks not exactly what is required! For [[2, 4], [4, 23], [8, 10], [8, 12], [9, 13], [10, 23], [11, 14]] my: ⟨ ⟨ 8 | 9 | 10 | 11 | 12 | 13 | 14 ⟩ ⟩ and yours ⟨ ⟨ ⟨ 8 | 10 ⟩ | ⟨ 8 | 12 ⟩ | ⟨ 9 | 13 ⟩ | ⟨ 11 | 14 ⟩ ⟩ ⟩ Or I miss smth? \$\endgroup\$
    – lesobrod
    Jan 11 at 4:58
  • 1
    \$\begingroup\$ answers need to output the lists that are used in the range \$\endgroup\$
    – lyxal
    Jan 11 at 5:08
2
\$\begingroup\$

Japt, 15 bytes

Outputs all possible solutions as the original arrays.

à fÊkÈrâ Íän dÉ

Try it

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

Python, 150 bytes

lambda l:[x for i in range(len(l))for x in combinations(l,i+1)if(s:=sorted({*chain.from_iterable(x)}))==[*range(s[0],s[-1]+1)]]
from itertools import*

Attempt This Online!

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

05AB1E, 7 or 10 bytes

ā<æ¦ʒè˜ê¥P

Outputs all possible result, by outputting the 0-based indices like the challenge description.

Try it online or verify all test cases.

æ¦ʒ˜ê¥P

Outputs all possible results, by outputting the lists of lists themselves.

Try it online or verify all test cases.

If we're also allowed to include an empty list, the ¦ can be dropped in both programs for -1 byte.

Explanation:

ā           # Push a list in the range [1, (implicit) input-length]
 <          # Decrease each by 1 to the range [0, length)
  æ         # Get the powerset of this
   ¦        # Remove the empty leading list
    ʒ       # Filter the list of lists by:
     è      #  Index each into the (implicit) input list of lists
      ˜     #  Flatten it
       ê    #  Sorted-uniquify it
        ¥   #  Get all deltas / forward-differences
         P  #  Take the product (only 1 is truthy in 05AB1E)
            # (after which the filtered result is output implicitly)

The second program is similar, but without ā< so the powerset is done directly on the input-list of lists, and therefore also without è.

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

JavaScript (Node.js), 84 bytes

f=([x,...y],v=[])=>x?f(y,[...v,x])||f(y,v):v.flat().map(i=>y[i]=0)|/0,,/.test(y)?0:v

Try it online!

f=([x,...y],v=[])=>
x?
  f(y,[...v,x])||f(y,v)   // [] is always a continuous range, so it's last tested
:
  v.flat().map(i=>y[i]=0) // Writing 0, so if v.flat().length==1 then it returns 0, not bother bitOR
  |/0,,/.test(y)?0:v      // Is there hole between, ,,,0,0,0,0 is fine, ,,,0,0,,0 isn't
Improve this answer
\$\endgroup\$
1
\$\begingroup\$

JavaScript (ES6), 81 bytes

-1 thanks to @l4m2

Returns a single solution as a space-separated string of integer lists.

f=([v,...a],m,o)=>v?f(a,m,o)||f(a,v.map(k=>m|=1<<k)|m,[o]+v+' '):(m|=m-1)&m+1?0:o

Try it online!

Improve this answer
\$\endgroup\$
1
  • \$\begingroup\$ 81 \$\endgroup\$
    – l4m2
    Jan 10 at 17:54
1
\$\begingroup\$

Charcoal, 30 bytes

ＩΦＥＸ²ＬθΦθ﹪÷ιＸ²μ²∧ι¬⁻…·⌊Σι⌈ΣιΣι

Attempt This Online! Link is to verbose version of code. Outputs all solutions. Explanation:

    ²                           Literal integer `2`
   Ｘ                            Raised to power
      θ                         Input list
     Ｌ                          Length
  Ｅ                             Map over implicit range
        θ                       Input list
       Φ                        Filtered where
           ι                    Outer value
          ÷                     Integer divided by
             ²                  Literal integer `2`
            Ｘ                   Raised to power
              μ                 Inner index
         ﹪     ²                Is odd
 Φ                              Filtered where
                 ι              Current result
                ∧               Logical And
                        ι       Current result
                       Σ        Flattened
                      ⌊         Minimum
                           ι    Current result
                          Σ     Flattened
                         ⌈      Maximum
                    …·          Inclusive range
                   ⁻            Remove elements present in
                             ι  Current result
                            Σ   Flattened
                  ¬             Logical Not i.e. is empty
Ｉ                               Cast to string
                                Implicitly print

The output format is as follows: Each result is triple-spaced from each other, while within a result, the sets that comprise the result are double-spaced from each other and each element is output on its own line.

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

Haskell, 94 bytes

import Data.List
s=take 1.filter((\s->s>[]&&s==[head s..last s]).nub.sort.concat).subsequences

Try it online!

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

Brachylog, 9 bytes

⊇.cod~⟦₂∧

Try it online!

Generates solution with the largest number of sublists first.

Explanation

⊇.           Output is a sublist of the input
  cod        Concatenate, sort, remove duplicates
     ~⟦₂     The resulting list must be a range between 2 integers
        ∧
Improve this answer
\$\endgroup\$
1
\$\begingroup\$

BQN, 35 bytes

({(⌈´¬⌊´)=≠}¨/⊢)∘((⍷∾)¨(⥊(↕2˘)/¨<))

Try it online!

Explanation

({(⌈´¬⌊´)=≠}¨/⊢)∘((⍷∾)¨(⥊(↕2˘)/¨<)) 
                          (↕2˘)/¨<      Powerset (as a length-dimensional tensor)
                         (⥊        )    Deshape tensor to single dimension
                     ((⍷∾)¨          )  Concatenate, remove dupes in each element
                   ∘                    Then...
               /⊢                       filter the input by...
  (⌈´¬⌊´)                               whether range (span)...
         =                              is equal to...
          ≠                             length...
({          }¨    )                     for each element.

Originally had 34 bytes but there was a bug.

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

Arturo, 57 bytes

$=>[select--powerset&[[]]=>[b:flatten&[]=--@..b\0max<=b]]

Try it

$=>[                  ; a function
    select            ; select elements from
    --powerset&[[]]   ; powerset of input without empty set
    =>[               ; begin select, assign current elt to &
        b:flatten&    ; flatten sets in current elt
        []=           ; is the empty block equal to
        --            ; set difference of
        @             ; evaluate block
        ..            ; range
        b\0           ; first element of b
        max<=         ; max of b
        b             ; and b (second argument to set difference)
    ]                 ; end select
]                     ; end function
Improve this answer
\$\endgroup\$
1
\$\begingroup\$

Julia 1.0, 66 bytes

!l=all(diff(sort([l...;])).<2) ? l : maximum(i->!setdiff(l,[i]),l)

Try it online!

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

Python 3.8 (pre-release), 84 bytes

f=lambda a:max(f(a-{i})for i in a)if a and~-len(b:={*sum(a,())})-max(b)+min(b)else a

Try it online!

Takes a set of tuples as input and recursively removes items until a valid result is found.

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