[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](/questions/tagged/code-golf "show questions tagged '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]
# [05AB1E](https://github.com/Adriandmen/05AB1E), ~~13~~ 12 bytes
-1 thanks to @KevinCruijssen
```
æʒ¥Ë}æé.Δ˜êQ
```
[Try it online!](https://tio.run/##AS8A0P9vc2FiaWX//8OmypLCpcOLfcOmw6kuzpTLnMOqUf//WzEsIDIsIDQsIDcsIDEyXQ "05AB1E – 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]
# [Haskell](https://www.haskell.org) + [hgl](https://www.gitlab.com/wheatwizard/haskell-golfing-library), 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]
# [JavaScript (Node.js)](https://nodejs.org), 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!](https://tio.run/##dVJNb9swDL3nV/AwxPLCCPFHljWFnNMuO2yHHTUDUVy50eAvWK7RoehvzyjFcYdiAySA7/HxUSL4S43KFr3phnXTPuhLKegwhSdRC4Wc8y4UWS06WfNKN4/DOT/U@9PqdFC8Vh1rRFaSWvHSVIPu2SiycW0OJ26aonp60JaN4b7g3ZM9U5QxsxJNiM1aGHGSmxwLIfPQt8EiDJfLet9dBm2HQlltQcBxISOEbQ7rDK6RJ2KEZOY8uNEpwg4hiuesI3IEGd8SswGhyDF0KY4dS3H8zphK32Te6E24kJ8R7nzC1zjkC1wqdqbUPd7SpdbJhi5xCeGEcEo4pXw6/c5rZ53vlEzIqVPPbCdmO9Vf5xFjgilu8RPu8A6jDdKL6cH0rSjFaJ7eXzJn9i/l@zHS3f13lD65OPKhNzULue0qM7DgZxOEfjeeQWTwfKPX2USPjv764/s33qneanaUH17G1/wYhtc8k9JQF53T4oE0PrpfzEvBy7b/oooz6a45Z/eyACjaxraV5lX7yFhLu1MyQ5bXrQUhBOgbWC6h5XrU/W/Wu/J@AmxEMN5w9AU9rSiswMBHYL2MaBCeopc6CzNVNa6g5bat9c1u3v7GaQ8QdMraAPYQlMpUAUJLX3oN7y9/AA "JavaScript (Node.js) – 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]
# JavaScript (ES13), 148 bytes
Some kind of a compromise between golfiness and speed.
Output ranges are in reverse order ([+5 bytes](https://ato.pxeger.com/run?1=fVGxTsMwEBUr38BgtjM4VuykUCol_QIWGC0PTmOHSJGDaCpi1B9BLB3go-BrODdiQLQMZ93de_fu2X57931td7uPzeCS-eerK8AwX6S0KKEpTFEa_mTrzcretc3DAFCxEaGKu84Mt-YRAvJGboZlUF4v5EVQqU6CEjoZ6VIFvVCBqZFxzoPWlCmFJ4UGDKXctb6GqijPjfL2mdzbASZhQHDdvlhNt1sX_VwKOhn8Ojlb9X7dd5Z3fQMOlGBkhpKnf9uSkewokjNyzYiQx0cRFZGBgbmMXczlIck5IzeRdgCScRaXyRkGbsxSDOxlWGdY51jniOf_XGLvFvlXe89xU_rbnEBcRIHpkX5-8xs) 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!](https://ato.pxeger.com/run?1=fVGxTsMwEBUr38BgtjM4VuykUCo5_QImRsuD09hRpchBNBUx6mewsXSAj4Kv4dyIAdEynHX33ru7Z_vtPfSN2-8_toPP5p-vXoFlQeVUVdAqqyrLn1yzXTmAmo2I1tx3dri3jxBRMnI7LKMOZiGvos5NFrUw2UiXOpqFjkyPjHMejaFMazwptGAp5X4dGqhVdWl1cM_kwQ0wDQYkN-sXZ-hu55OVa0Enb19nF6s-bPrO8a5vwYMWjMxw5PlfWDJSnGRKRm4ZEfJ0K7IiKTAwlwnFXB4bOWfkLsmOUDL14jI5w8CNRY6BWIF1gXWJdYl8-c8lDm5Rf3PwnDblv80J5EUaMD3Sz0d-Aw)
## 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]
# 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!](https://tio.run/##fU/LbsIwELzzFXu0yVLFTlLArTnwCxEnK4emJMKIOk9UIcS3p@twKKlQI22y8/B4Ul/6Q@WiVd0Ow74ooWQdVzNoMNXGmM6EGT1oshl8H@ypgIZEyHXzUlc1CzkBW0IKH24Pp8KxnG@0/6ZcfVaut@5ckGWnrxbKqoUjWAf5uFq/Hm/3AFf113l3W@xUqvO3h5Ok@bit0rlZiIy/S3//b0A3Qm@zm613qCbQJjeK1sBsA2OpPlmKky3ZRWk5H10LesuMjwHNxH8hf9CMJ7riHhYY82UduxfkY15b9OfWQTrUrXU9K5kRCEnG@eyRkAjREy5GWCII@cxOvPAaDe3Ss7TLacwKYe0NE1J6P0XLhIbyo5CGuIhwRDgmHJMe/60pMcIYE3zFJa5RhEgNqADdL2IUyT8/QLMkefgB)
A little long, but runs in 0.026 seconds on all test cases.
[Answer]
# [Ruby](https://www.ruby-lang.org/), ~~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!](https://tio.run/##dVFLT8JAEL7zK8Zw4TEt7KNWhOJFr/6BzZostUSSFRpYNIby2@vsUooSPUwy32MeO7vdL77qZVZHc3twmcmUnjocmMxUNi63m9d97noWbT9@N@WhMrjAvHJDpQYm3rmi7BGeG3jII3PP@lofP99WtgAXL61xrljHu83WVUrfZHbqjvVs9vT8GNvVutgdKluVsFTFh7Fg1Ui9aD3UI2rRUQwh0RDN4ZQFgiOIlgvgTEuEFIHxVvWERlD8LJycGrrdbltOAvMiBeXcs5TzqxnU5WILPS/GjrpDmAQh1HgUCsTvgdz3p514QkELiTEFcYKwICwJS9Jl8@bgbX1hqGiQd8vAJA2TNPWnK3EUKDHBW0xxgmyMtDztTi9kEll70x823@wv5/VxKdJ/DxzEDn1t/Q0 "Ruby – 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]
# [Python 3.8 (pre-release)](https://docs.python.org/3.8/), ~~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!](https://tio.run/##fU9BbsIwELzzij3aySIlTlIgwT3kCYQTK6tqRCIsgUMSUIUq3p6u20upUC2NvTszXo/Pt8uhc8nyPEzTvmmhFaPMZ9BjUGkiGikyvHAGHwd7bKDPawx63Rcb/RmM9zlv15OokYy8F8EWS10XwRvudFlE62PjRCXX2p@17AaxgXe3F32uhadKuVbc0zakMiRrTNsNYME6GMG2YF93phuI6pDoZJ3YSM7x473lWgW7eUlz5dPR7fuSMTLs/TNVrmspZzA0l@vgoJrOg3UX0QqKETLD0m9CISRPuBRhgRCrZ3bmY68xuFae5Vo9jlkirLzhgVTez6NVxuD5ScRgLuE@4T7lPmU9/RtTYYIpZviCC1xhHCEn4AD8fpxinP3zAcaC5ekL "Python 3.8 (pre-release) – Try It Online")
Severely golfed answer by [Ajax1234](https://codegolf.stackexchange.com/a/265686/110585).
Monads are awesome - `{*sum(b,[])}` is significantly shorter compared to plain comprehension (`{i for j in b for i in j}`).
[Answer]
# [Charcoal](https://github.com/somebody1234/Charcoal), 62 bytes
```
⊞υ⟦θ⟧Ｆυ¿¬ⅉ«≔⊟ικＦΦ⁻θ⌊κ›λ⁰«≔⟦⌊κ⟧ζＷ№θ⁺⌈ζλ⊞ζ⁺⌈ζλ≔⁺ι⟦ζ⁻κζ⟧ζ¿⌊ζ⊞υζＩζ
```
[Try it online!](https://tio.run/##bY8xa8MwEIVn@1fceAIVQuzQIVMJtFOK12A0iKBUworVSFYbCPntyklUZOlwoHfv8d3TUUt/dNKmNMSgMXIYL4Jt25PzgJGBOQF@ugUPyBiDW9u8hWC@ZhzcNxrGYaJsU8Lvxi7K497MMeCFAz3MOZ5xYhT78Epm13JY/YEqaXwGBQedec2vNlYB7lycl8waLDH38lpymng2Q0pj/b@7fR4otqGP6VKKxJTvCFav5T/WErpyY3WVDQoGb6jJToYlJ2h9b@8pjeO647DuaTY0rxy6FQ3tOtId6Z50T36/ESK9/NgH "Charcoal – 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.
]