# Write a set as a union of ranges

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 , 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]

• "arithmetic progression" might be clearer than "range" Oct 2, 2023 at 5:15
• @CommandMaster While that's more correct in a mathematical context, I'm going to continue using "range" because most people here are familiar with Python. Oct 2, 2023 at 5:16
• This might be interesting as a fastest-code question Oct 2, 2023 at 5:25
• Suggested test case: [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]. The greedy algorithm fails in this one, and gives [1,3,5,7,9,11,13,15], [2,6,10,14], [4, 12]. Can be generalized as [1,2,...,2^n-1,2^n+1,...,2^(n+1)-1] Oct 2, 2023 at 6:46
• Maybe the title should be updated to Write a set as a union of range()'s to emphasize the reference to the Python function. Oct 2, 2023 at 8:58

# 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

• @KevinCruijssen Thanks! I had it from an earlier version and didn't notice it can be removed now Oct 2, 2023 at 9:51

# 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.

# 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


# 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()
)                  // 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


# 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.

• I think if S and len(b)>=len(S):continue can be rearranged to if len(b)>=len(S)and S:continue to save a byte? Oct 3, 2023 at 7:07
• @SquareFinder what about if len(b)>=len(S)>0:continue?
– Neil
Oct 3, 2023 at 14:11

# 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}


# 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!

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

# 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.