Write a set as a union of ranges

Question

In this challenge, we define a range similarly to Python's range function: A list of positive integers with equal differences between them. For example, [1, 2, 3] is a range from 1 to 3 with a skip count of 1, because there is a difference of 1 between each item, and [4, 7, 10, 13] is a range from 4 to 13 with a skip count of 3.

Here, I'll represent ranges as a list of integers, but you can use any reasonable format that unambiguously represents a single range, e.g representing it as [start, skip, end] or something.

Your challenge is to, given a strictly increasing list of positive integers, represent it as a union of multiple ranges of integers with as few ranges as possible. For example, [1, 2, 4, 7, 12] can be represented as a union of [1, 4, 7] and [2, 7, 12], and this is (an) optimal solution as it uses two ranges and there is no way to represent it as one range.

This is code-golf, shortest wins!

Testcases

Note that these only show one possible solution. In almost all cases there will be multiple optimal solutions, and you can output any one or all of them.

[1, 5] -> [1, 5]
[1, 2, 3] -> [1, 2, 3]
[1, 2, 4, 7, 12] -> [1, 4, 7], [2, 7, 12]
[1, 2, 3, 11, 12, 13, 21, 22, 23] -> [1, 2, 3], [11, 12, 13], [21, 22, 23]
[8, 9, 13] -> [8, 9], [13]
[23, 24, 25, 27, 30, 33, 35, 37, 40, 44, 45] -> [24, 27, 30, 33], [23, 30, 37, 44], [25, 30, 35, 40, 45]
[1,2,3,4,5,6,7,9,10,11,12,13,14,15] -> [1,2,3,4,5,6,7], [9,10,11,12,13,14,15]
[1, 2, 4, 7, 12, 17] -> [1, 4, 7], [2, 7, 12, 17]

Answer 1

05AB1E, 13 12 bytes

-1 thanks to @KevinCruijssen

æʒ¥Ë}æé.Δ˜êQ

Try it online!

æ       # all subsets
ʒ       # keep those such that
 ¥       # their deltas
 Ë       # are all equal
}
æ       # look at sets of such ranges
é       # sorted by length
.Δ      # and return the first one such that
 ˜       # flattened
 ê       # and sort uniquified
 Q       # and is equal to the implicit input 

Answer 2

Haskell + hgl, 31 bytes

mBl<(sSt<iS^.sr<fo*^sSt(lq<δ))

This is really quite slow.

Explanation

• sSt(lq<δ) get all sublists of the input that have constant deltas
• sSt<iS^.sr<fo get all sublists of the above that contain the input when unioned
• mBl get the minimum by length

Reflection

There are a few things that could be improved here. I will note separately things that improve the golf score, and things that don't necessarily improve the golf score but help with speedy ways to complete this.

Golf improvements

• Support for sets has been on my todo for a while, this answer really could have benefited from that. Here are some things I could have used here:
  • Some sort of union for lists
  • Some sort of subset for list (are all of this lists elements contained in this other list?)
• lss gets the longest sublist satisfying a predicate but there is no function to get the shortest sublist satisfying a predicate. That should exist.
• This is the second time I have used lq<δ in a challenge. It should have an abbreviation at this point.

Performance improvements

• It would be nice to have a version of sSt restricted to non-empty lists. This wouldn't change the big O complexity or anything but it would halve the number of checks that need to be performed.
• As an extension of the above it would be nice to have a version of sSt which would only give the maximum elements, i.e. it would give only subsequences satisfying a predicate that are not subsequences of other subsequences also satisfying the predicate. In our case we don't need to care about the set [2] or [2,3] or [3] etc. if the set [2,3,4] is present, so eliminating those other ones would save a ton of time. It would be fastest if it never generated the bad subsequences, however either way would speed things up.

Answer 3

JavaScript (Node.js), 127 bytes

f=(a,b=m=a,...p)=>m=p[m.length]?m:b+b?a.map(n=>f(a,a.filter(v=>v-i?b.includes(v):c.push(v)>(i+=n),n-=i=b[0],c=[]),...p,c))&&m:p

Try it online!

f=(
  a, // `a` is the input array
  b= // `b` is uncovered numbers
    m=a, // `m` is best solution we have ever found
         // initialize use `a` as length of `a` greater than best answer
  ...p // all ranges we have used, initialized as empty array
)=>m= // save best answer we found to `m`
  p[m.length]?m: // if currently used ranges is more than best answer
                 // give up attempt and return `m` directly
  b+b? // if there are numbers not covered yet
    a.map(n=> // for each number `n` in input
              // generate a range contains `b[0]` and `n` and step `n-b[0]`
      f(a,
        a.filter(v=> // for each number in input
          v-i?b.includes(v): // keep it in `b` as is if it not belongs to new range
          c.push(v)> // otherwise, add it to new range
            (i+=n), // calculate next expected number
                    // the next expected number >= length of `c`
                    //   so it is false, and filter this number out from `b`
          n-=i=b[0], // `i` is next number expected in the new range
                     // `n` is step of the new range
          c=[] // `c` is the new range
        ),...p,c)
      )&&m: // returns the best answer got so far
    p // found a better solution, assign it to m

Answer 4

JavaScript (ES13), 148 bytes

Some kind of a compromise between golfiness and speed.

Output ranges are in reverse order (+5 bytes if this is not acceptable).

f=(a,n=0)=>(g=a=>a.reduce((b,x)=>b.flatMap(y=>(x.at?y[n]:2*y[0]-y[1]-x)?[y]:[y,[x,...y]]),[[]]))(g(a)).find(b=>!a[new Set(b.flat()).size])||f(a,n+1)

Attempt This Online!

Commented

Helper function g

This function computes the powerset of its input, applying the following constraints:

• If the input contains integers, we make sure that the output sets are valid 'ranges' (as per the Python definition).
• If the input contains arrays, we make sure that the output sets contain at most n+1 entries (where n is defined in the scope of the main function).

g = a =>           // a[] = input array
a.reduce((b, x) => // for each array x[] in a[],
                   // using b[] as the accumulator
  b.flatMap(y =>   //   for each array y[] in b[]:
    (              //
      x.at ?       //     if x is an array:
        y[n]       //       test whether y[n] is defined
      :            //     else:
        2 * y[0] - //       test whether y[0] - x is equal
        y[1] -     //       to y[1] - y[0]
        x          //
    ) ?            //     if the above test is truthy:
      [y]          //       just pass y[]
    :              //     else:
      [            //
        y,         //       pass y[]
        [x, ...y]  //       create a new entry with x
      ]            //       inserted at the beginning of y[]
  ),               //   end of flatMap()
  [[]]             //   start with b[] = [ [] ]
)                  // end of reduce()

Main function f

This function recursively attempts to find a solution using a single range, then two ranges, and so on. The counter n holds the maximum number of ranges, minus 1.

f = (              // f is a recursive function taking:
  a,               //   a[] = input array
  n = 0            //   n = counter
) =>               //
g(                 // get the powerset ...
  g(a)             //   ... of the powerset of a[],
)                  // using the constraints described above
.find(b =>         // look for an array b[] in there:
  !a[              //   such that the total number of distinct
    new Set(       //   items in b[] is equal to the length of
      b.flat()     //   the input array
    ).size         //   (i.e. a[number_of_items] is undefined)
  ]                //
)                  // end of find()
|| f(a, n + 1)     // if not found, try again with n + 1

Answer 5

Python3, 306 bytes

def f(s):
 q,S=[[[s[0]]]],[]
 while q:
  b=q.pop(0)
  if S and len(b)>=len(S):continue
  U={i for j in b for i in j}
  if not{*s}-U:S=b;continue
  if len(B:=b[-1])<2:
   for i in s:
    if i>B[-1]:q+=[b[:-1]+[B+[i]]]
  elif(y:=2*B[-1]-B[-2])in s:q=[b[:-1]+[B+[y]]]+q
  else:q+=[b+[[min({*s}-U)]]]
 return S

Try it online!

A little long, but runs in 0.026 seconds on all test cases.

Answer 6

Ruby, 126 ... 101 bytes

->l{t=a=[];t,*a=a|l.product(l,l).map{|a,b,c|t+[[*a.step(b,c>a ?c-a:1)]]}while t.flatten.sort|[]!=l;t}

Try it online!

Let me explain:

First, initialize 2 empty lists, one as a list of possible solutions, and one as an iterator on the list.

->l{t=a=[];

On every iteration: t is the first element of the list. We append all possible solutions including the previous value of t and another range to the list. This way, we check all solutions breadth-first.

t,*a=a|l.product(l,l).map{|a,b,c|t+

The ranges are calculated by getting 3 values a, b, c from the initial list, then going from a to b using c-a as increment. We need to be careful in case c==a (the step is 0 which is an error)

[[*a.step(b,c>a ?c-a:1)]]}

Check in the while-loop if t is a solution (must be the same as the input list if flattened and sorted).

while t.flatten.sort|[]!=l;t}

Answer 7

Python 3.8 (pre-release), 217 216 bytes

def f(s):
 q,*S=[[[s[0]]]],
 while q:b,*q=q;R={*s}-{*sum(b,[])};*T,B=b;*_,Z=B;0<len(S)<=len(b)or(R and(q:=(len(B)<2and[T+[B+[i]]for i in s if i>Z]or[[b+[[min(R)]],T+[B+[y:=2*Z-B[-2]]]][y in s]])+q)or(S:=b))
 return S

Try it online!

Severely golfed answer by Ajax1234.

Monads are awesome - {*sum(b,[])} is significantly shorter compared to plain comprehension ({i for j in b for i in j}).

Answer 8

Charcoal, 62 bytes

⊞υ⟦θ⟧Ｆυ¿¬ⅉ«≔⊟ικＦΦ⁻θ⌊κ›λ⁰«≔⟦⌊κ⟧ζＷ№θ⁺⌈ζλ⊞ζ⁺⌈ζλ≔⁺ι⟦ζ⁻κζ⟧ζ¿⌊ζ⊞υζＩζ

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

⊞υ⟦θ⟧Ｆυ

Start a breadth-first search with no ranges in the union and the input list as the remaining elements.

¿¬ⅉ«

Stop once a solution is found (which will necessarily have a minimum number of ranges).

≔⊟ικ

Get the remaining numbers.

ＦΦ⁻θ⌊κ›λ⁰«

Loop over the potential step sizes.

≔⟦⌊κ⟧ζＷ№θ⁺⌈ζλ⊞ζ⁺⌈ζλ

Calculate the largest set that contains the minimum remaining element with this step size.

≔⁺ι⟦ζ⁻κζ⟧ζ

Calculate the elements remaining after this set is excluded and create a new union with this set and the remaining elements.

¿⌊ζ⊞υζＩζ

If there are elements remaining then add this union so far to the list of unions to be processed otherwise print this union.