15
\$\begingroup\$

For this challenge, we will define the "complement" of a list of integers A as being any list B such that the union of A and B is a list of consecutive integers with no repeats.

In other words, B is the complement of A if

  • B has all of the integers between the minimum and maximum of A which are missing from A, and
  • B has none of the integers present in A

For example: [2, 4, 6, 7] is a complement of [1, 3, 5, 8, 9], [1, 3, 5], and [3, 5], but it is not a complement of [1, 2, 3, 5] or [1, 3, 5, 9].

Worth noting: For a list of consecutive integers, a complement may be the empty list, as no integers are "missing" between the minimum and maximum.

Any given list of integers with no repeats has infinitely many complements (proof left as an exercise for the reader), but has exactly one smallest complement, which itself has this very same property.

For example, if we start with the list [1, 2, 3, 5, 8, 13] and repeatedly find the smallest complement, we get this chain of lists:

[1, 2, 3, 5, 8, 13]
[4, 6, 7, 9, 10, 11, 12]
[5, 8]
[6, 7]
[]

The smallest complement of the empty list is the empty list, so we can stop here.

Challenge

Given a list of non-repeating positive integers A, output the A's smallest complement, followed by that list's smallest complement, all the way until the empty list.

Rules

  • You may choose to include or omit the input list in your output.
  • You may choose to include or omit the empty list in your output.
  • The input list will always have complements. (i.e. the list will never contain duplicates)
  • The input will be sorted.
  • The input will never be the empty list.
  • The input will never contain 0 or negative integers. (although they are well defined)
  • This is , so shortest code in bytes wins.

Examples

Outputs will include both the original list and the empty list, for clarity

input => output
[1, 3, 5, 7, 9] => [[1, 3, 5, 7, 9], [2, 4, 6, 8], [3, 5, 7], [4, 6], [5], []]
[5, 10, 15, 20] => [[5, 10, 15, 20], [6, 7, 8, 9, 11, 12, 13, 14, 16, 17, 18, 19], [10, 15], [11, 12, 13, 14], []]
[5, 10, 15] => [[5, 10, 15], [6, 7, 8, 9, 11, 12, 13, 14], [10], []]
[1, 2, 6, 7, 11, 12] => [[1, 2, 6, 7, 11, 12], [3, 4, 5, 8, 9, 10], [6, 7], []]
[1, 2, 3] => [[1, 2, 3], []]
[5, 6, 7] => [[5, 6, 7],  []]
\$\endgroup\$
5
  • 1
    \$\begingroup\$ "Worth noting: For a list of consecutive integers, a complement is always the empty list, as no integers are "missing" between the minimum and maximum." This seems incorrect to me. \$\endgroup\$ Jun 24 at 1:15
  • \$\begingroup\$ @GregMartin ah, good eye, i think i thought i was talking about "the smallest complement" there, and got mixed up. Fixed now, thank you :D \$\endgroup\$ Jun 24 at 2:37
  • \$\begingroup\$ Can you output a infinite amount of empty lists at the end? \$\endgroup\$
    – mousetail
    Jun 24 at 14:20
  • \$\begingroup\$ @mousetail IMO no, but i could have sworn there was a meta about that sort of thing \$\endgroup\$ Jun 24 at 15:11
  • \$\begingroup\$ found it, programs must terminate by default, though the vote isn't won by quite so much. Either way, though, my spec says to output "until the empty list" so I've covered my bases there :P \$\endgroup\$ Jun 24 at 15:38

22 Answers 22

8
\$\begingroup\$

R, 45 44 bytes

f=function(r)r&f(print(setdiff(r:max(r),r)))

Attempt This Online!

Derived without peeking at pajonk's R answer, but ended-up with a pretty similar approach ...

\$\endgroup\$
6
\$\begingroup\$

Husk, 5 bytes

U¡S-…

Try it online!

 ¡     # Apply function repeatedly, collect values in infinite list:
   -   # list difference of
  S    # last result (or input for first iteration)
  S …  # and last result with gaps filled with numeric ranges;
U      # Finally, get longest prefix of the list with all unique elements.
\$\endgroup\$
5
\$\begingroup\$

K (ngn/k), 18 bytes

Includes input and empty list (!0) in the output.

{(x,/x_!0^*|x)^x}\

Try it online!

{ ... }\ Converges; Call the lambda repeatedly until the value doesn't change.
( ... )^x The range computed in the parentheses without the elements in x.

*|x Last (largest) value in x. This returns 0N if x is empty, then 0^ replaces 0N with 0.
! range from 0 to this value value (exclusive).
x_ cut this range at the indices given by x. Because the first slice is omitted, this gets rid of the numbers up to the minimum of x.
x,/ Flatten the cutted list, prepending x. We need to prepend x to get the shape right for the empty list.

Instead of converges we could use whiles to avoid dealing with the empty list. This would save 3 bytes in the lambda, but add 4 on the outside:

(::){(,/x_!*|x)^x}\

Try it online!

\$\endgroup\$
5
\$\begingroup\$

R, 55 50 bytes

Edit: -5 bytes thanks to @Giuseppe.

f=function(v)if(s<-setdiff(v:max(v),print(v)))f(s)

Try it online!

Prints the inital list but not the empty one. Terminates with an error.

In R==4.1 replace function with \ to achieve 43 bytes (still longer than @Dominic van Essen's answer working in R>=4.1 after also implementing this notation there). This doesn't work in R>=4.2.0 (and consequently in ATO), due to introduction of a strict check for argument length for if.

Explanation outline

  1. Compute sequence from min to max with v:max(v) (: takes first element of a vector and as input is sorted, this is the minimum).
  2. Take set difference setdiff of this and input (we print it here and print conveniently returns its argument).
  3. Assign this to s.
  4. if takes the first element of a vector and checks if it's truthy (not 0 or FALSE) and errors for empty input. Essentially, check if s is nonempty.
  5. Recurse.
\$\endgroup\$
4
  • \$\begingroup\$ I think that my answer would be 37 bytes in R ≥ 4.1 (and even seems to work on ATO)... \$\endgroup\$ Jun 24 at 10:22
  • \$\begingroup\$ (BTW, for demo purposes only you can re-define if to make ATO run Ok like this...) \$\endgroup\$ Jun 24 at 10:33
  • 1
    \$\begingroup\$ Ah, nevermind @DominicvanEssen. I somehow linked in my brain using ATO with using \ instead of function and didn't even check your answer for this... \$\endgroup\$
    – pajonk
    Jun 24 at 10:38
  • \$\begingroup\$ Ha ha. Actually, I saw that you'd answered, and so wrote my own answer without looking, assuming you'd use \. Then, when I finally looked, I realised you'd used function so I changed mine to match, but left it on ATO... \$\endgroup\$ Jun 24 at 11:06
4
\$\begingroup\$

Python 3, 56 bytes

f=lambda l:l and[l]+f(sorted({*range(l[0],l[-1])}-{*l}))

Try it online!

\$\endgroup\$
4
\$\begingroup\$

Vyxal, 7 bytes

≬₌gGṡ⊍İ

Try it Online! or Try all the tests

Input list not included, empty list is.

Explained

≬₌gGṡ⊍İ
≬-----     # Next three elements as a function:
 ₌gG       #   Get the smallest and largest item of the argument
    ṡ      #   Create an incluse range between those values
     ⊍     #   and set xor with the original argument
      İ    # Repeat that function until the result is no longer unique, collecting results
\$\endgroup\$
4
\$\begingroup\$

J, 18 bytes

(-.~{:-.&i.{.)^:a:

Try it online!

thejonymyster has allowed this output... since J only supports heterogeneous lists with boxing, and since 0 is disallowed in the input, I am displaying the output as a homogeneous matrix with 0 fill, so that the successive lists are simply each row, without the 0 fill:

1 2 3 5  8 13  0
4 6 7 9 10 11 12
5 8 0 0  0  0  0
6 7 0 0  0  0  0
0 0 0 0  0  0  0

Note that, if desired, we could add boxing for 3 more bytes.

  • (...)^:a: Until a fixed point is reached, collecting results, do the following...
  • -.~{:-.&i.{. Remove -. the input from 0 1 ... <largest element - 1> without 0 1 ...<smallest element - 1>
\$\endgroup\$
1
  • 1
    \$\begingroup\$ Honestly, I'll allow it. It's not ambiguous, and it's not like the 0s are in between the list elements. Reminds me of excel :P keep the bit about boxing though, cause its interesting. \$\endgroup\$ Jun 23 at 15:02
4
\$\begingroup\$

Pyth, 9 8 bytes

#p=-rhQe

Try it online!

#p=(Q)-rhQe(QQ)
              // Implicitly initialize Q as the input
#             // Repeat until an error occurs:
     rhQeQ    // Range from first to last element of Q...
    -     Q   // ...with elements of Q removed
  =Q          // Set Q to the result
 p            // Print  
\$\endgroup\$
4
\$\begingroup\$

Zsh, 44 bytes

<<<$@
a=({$1..$@[$#]})
(($#))&&$0 ${a:|argv}

Try it online!

<<<$@             # output arguments
a=({$1..$@[$#]})  # all integers between first and last args
(($#)) &&         # if there was at least one argument
    $0 ${a:|argv}  # recurse with set difference between $a and the arguments

Using $argv is needed in the ${a:|b} notation, ${a:|@} does not work.

\$\endgroup\$
3
\$\begingroup\$

JavaScript (ES10), 66 bytes

The empty list is included. The input list is not.

f=a=>a+a&&[b=a.flatMap(p=g=v=>++p-v?[p,...g(v)]:(p=v,[])),...f(b)]

Try it online!

Or as ES6 (also 66 bytes):

f=a=>a+a&&[a.map(p=g=v=>++p-v?g(v,b.push(p)):p=v,b=[])&&b,...f(b)]

Try it online!

\$\endgroup\$
3
\$\begingroup\$

BQN, 23 bytes

{𝕊¬∘∊⟜𝕩⊸/𝕩⊑⊸↓↕⌈´•Show𝕩}

Try it here!

Terminates with error.

Explanation

Input is x.

  • •Show𝕩 output x
  • ↕⌈´ exclusive range from 0 to max of x
  • 𝕩⊑⊸↓ drop (first element in x) elements
  • ¬∘∊⟜𝕩⊸/ filter elements not in x
  • 𝕊 recurse
\$\endgroup\$
3
\$\begingroup\$

Factor + math.unicode, 51 50 bytes

[ [ 3 dupn . minmax [a,b] swap ∖ ] until-empty ]

Input list is included; empty list is omitted.

Try it online!

  • [ ... ] until-empty Call [ ... ] on the input repeatedly until it is empty.
         ! { 1 3 5 7 9 }
3        ! { 1 3 5 7 9 } 3
dupn     ! { 1 3 5 7 9 } { 1 3 5 7 9 } { 1 3 5 7 9 }
.        ! { 1 3 5 7 9 } { 1 3 5 7 9 }   ((output to stdout))
minmax   ! { 1 3 5 7 9 } 1 9
[a,b]    ! { 1 3 5 7 9 } { 1 2 3 4 5 6 7 8 9 }
swap     ! { 1 2 3 4 5 6 7 8 9 } { 1 3 5 7 9 }
∖        ! { 2 4 6 8 }    ((set difference))
         !   ((and so forth...))
\$\endgroup\$
3
\$\begingroup\$

Haskell, 65 49 bytes

-10 bytes thanks to @Lynn

g[]=[];g x=x:g[e|e<-[head x..last x],notElem e x]
\$\endgroup\$
1
  • \$\begingroup\$ Some saves: g[]=[];g x=x:g[e|e<-[minimum x..maximum x],notElem e x] \$\endgroup\$
    – Lynn
    Jun 25 at 2:17
2
\$\begingroup\$

Charcoal, 15 bytes

Wθ«≔⁻…⌊θ⌈θθθ⟦Iθ

Try it online! Link is to verbose version of code. Does not output the initial list. Would output the final list except that Charcoal has no output for an empty list. Explanation:

Wθ«

Repeat until the list is empty.

≔⁻…⌊θ⌈θθθ

Subtract the list from the range of its lowest to highest elements.

⟦Iθ

Output the new list with separation from the previous list.

\$\endgroup\$
2
\$\begingroup\$

Burlesque, 39 bytes

1{sa1.>{Jl_g_/vjr@j\\}q{}IE}C~J{}Fi+..+

Try it online!

The only bit which is required to compute this is

1{Jl_g_/vjr@j\\}C~

Unfortunately, this crashes on reaching a 0/1 element block because it tries to pull head/tail from an empty list.

1        # Number of elements Continue forever keeps from the top of the stack
{
 sa1.>   # Length of block at least 2 elements
 {
  J      # Duplicate
  l_g_/v # Get head and tail of list
  jr@    # Range head..tail 
  j\\    # List difference with original
 }
 q{}IE   # If list too short return empty list
}C~      # Continue forever
J{}Fi    # Find the first occurrence of empty list 
+..+     # Take that many (including an empty element)
\$\endgroup\$
2
\$\begingroup\$

05AB1E, 8 bytes

Δ=WsàŸyK

Outputs the intermediate lists separately to STDOUT; includes both the input-list and empty-list. Stops with an error.

Try it online or verify all test cases.

Explanation:

Δ         # Loop until the result no longer changes
          # (although it'll basically loop until the error in this case)
 =        #  Print the current list with trailing newline (without popping)
          #  (which will use the implicit input-list in the first iteration)
  W       #  Push its minimum (without popping)
   s      #  Swap so the list is at the top again
    à     #  Pop and push its maximum
     Ÿ    #  Pop both, and push a list in the range [min,max]
          #  (the min/max of an empty list are ""; so here it'll error)
      y   #  Push the current list again
       K  #  Remove all those values from the [min,max]-ranged list
\$\endgroup\$
2
\$\begingroup\$

Ruby, 34 bytes

f=->a{a[0]&&f[p [*a[0]..a[-1]]-a]}

Try it online!

\$\endgroup\$
2
\$\begingroup\$

Retina 0.8.2, 80 bytes

$
;¶$%`
\d+
$*
%(M!&`^.+;|(1+)$(?<!^\1.*)(?<!\b\1\b.*)
O`
)`¶
,
1+
$.&
}`;¶$

;

Try it online! Explanation:

$
;¶$%`

Duplicate the last line and mark the previous line as not to be altered.

\d+
$*

Convert to unary.

%(`
)`

Run the next three commands separately for each line, so that they don't accidentally clobber one another.

M!&`^.+;|

Just output the previous lines in full, so nothing happens...

(1+)$

... but for the last line, output overlapping substrings of the final run of 1s...

(?<!^\1.*)

... that are greater than the first run of 1s...

(?<!\b\1\b.*)

... and do not match any of the runs of 1s.

O`

Sort the lines into ascending order.

¶
,

Join them with commas.

1+
$.&

Convert to decimal.

;¶$

If the were no matching runs of 1s, then just undo everything, so that the loop stops repeating.

}`

Repeat the above commands until the buffer stops changing.

;

Remove the markers on the previous lines.

\$\endgroup\$
2
\$\begingroup\$

Rust, 138 bytes

let f=|l:Vec<u8>|std::iter::successors(Some(l),|l|if l.len()>0{Some((l[0]..l[l.len()-1]).filter(|i|!l.contains(i)).collect())}else{None});

Returns a generator.

Goal was to get the longest answer possible, right?

try it yourself

\$\endgroup\$
2
\$\begingroup\$

GeoGebra, 93 bytes

l={
InputBox(l
a=IterationList(Remove(Min(L)...Max(L),L),L,{l},Length(l
Take(a,1,IndexOf({},a

Input as comma separated numbers in the input box. Output is the list l1.

Try It On GeoGebra!

Try It On GeoGebra! (with example test case)

\$\endgroup\$
2
\$\begingroup\$

Wolfram Language (Mathematica), 55 bytes

NestWhileList[Complement[Range@@MinMax@#,#]&,#,#!={}&]&

Try it online!

\$\endgroup\$
1
\$\begingroup\$

Python 3, 50 bytes

f=lambda K:[*K]and[K]+f({*range(min(K),max(K))}-K)

Try it online!

Takes input as a set rather than a list so I can use the more efficient set difference operator. Output will not be sorted. Basic logic to build a list efficiently copied from @m90

\$\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.