18
\$\begingroup\$

In this challenge, we define the complement of a list of positive integers as all positive integers not included in that list. For example, the complement of the even numbers [2, 4, 6, 8...] is the odd numbers [1, 3, 5, 7...]. Your challenge is to, given a monotonically increasing, infinite list of positive integers, return its complement.

Infinite lists may be input/output as:

  • Streams from/to stdin/stdout
  • Native infinite list / iterator / generator / etc objects
  • Functions that take an index and return an item of the list

Additionally, you may take an index n along with the infinite list and return the nth item of the list's complement. For all options, you may use 0-indexing or 1-indexing, and your output format does not need to be the same as your input format.

Testcases

2, 4, 6, 8... (even numbers) => 1, 3, 5, 7...
1, 4, 9, 16... (squares) => 2, 3, 5, 6, 7...
2, 3, 5, 7, 11... (primes) => 1, 4, 6, 8...
3, 6, 9, 12... (multiples of 3) => 1, 2, 4, 5, 7...
1, 3, 6, 10... (triangle numbers) => 2, 4, 5, 7...
\$\endgroup\$
7
  • \$\begingroup\$ Are we allowed to take a function as the input which returns truthy results for values that appear in the list? \$\endgroup\$
    – math scat
    Commented Oct 3, 2023 at 9:07
  • 4
    \$\begingroup\$ @mathscat Although it's a bit inconsistent since some languages have infinite list membership check functions, I'm going to say no to that one since it boils down to logically negating the input. \$\endgroup\$
    – emanresu A
    Commented Oct 3, 2023 at 9:46
  • \$\begingroup\$ For languages where normal native integer types are fixed-width, can we still use them? That somewhat makes a mockery of the "infinite" stream idea. e.g. a C implementation on a 64-bit machine with 32-bit int can have an int sequence[1ULL<<31] array big enough to hold every positive int. (In which case the output is the empty set). i.e. the length of a monotonic sequence of fixed-width integers is also finite. \$\endgroup\$ Commented Oct 3, 2023 at 21:56
  • \$\begingroup\$ (I'm not asking if we can use arrays, just whether we can e.g. read volatile int *source and write volatile int *sink for fixed-width 32-bit int. I guess in C you could hypothetically compile for an implementation where int is arbitrarily wide, for any fixed problem size. But in x86 machine code for example, a type width of 32-bit really would be baked in to the answer. I assume this is still fine and sufficiently captures the spirit of the exercise, especially if you avoid a loop counter of some fixed width or array of fixed size.) \$\endgroup\$ Commented Oct 3, 2023 at 21:57
  • 2
    \$\begingroup\$ @PeterCordes It's fine as long as your answer works in theory for arbitrarily large integer types - e.g. your answer would still work if run in a hypothetical version of C with 64-bit ints. I believe there's a standard loophole somewhere about abusing native integer limits. \$\endgroup\$
    – emanresu A
    Commented Oct 3, 2023 at 21:59

20 Answers 20

13
\$\begingroup\$

Python (no imports), 52 bytes

-3 bytes, thanks to xnor

def f(s,x=0):
 for y in s:yield from range(x+1,x:=y)

Attempt This Online!

input/output as generator

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

05AB1E, 7 bytes

∞.i_ƶ0K

Try it online!, or try all testcases

I feel like 6 bytes should definitely be possible, but I can't find it. м doesn't work for infinite lists, and ∞ʒ.i_ doesn't work for some reason ):

Explanation

∞       # [1, 2, 3, ...]
.i      # for each, check whether it appears on the input
_       # bool not
ƶ       # multiply by the 1-based index
0K      # and remove zeros
\$\endgroup\$
2
  • \$\begingroup\$ Nice answer. I was working on an answer, but was distracted by some meetings at work. Didn't think about using .i, but that seems to be the only suitable way here to make it work in the first place. Since K indeed doesn't work for infinite lists (м wouldn't have worked even if the list wasn't infinite, since it removes digits from numbers). Here is a test suite for all the test cases if you want it. \$\endgroup\$ Commented Oct 3, 2023 at 9:55
  • 1
    \$\begingroup\$ As for why ∞ʒ.i_ doesn't work: I'm not sure why it doesn't use the infinite list that's on the stack in the first iteration, but it seems to use the implicit empty input in all iterations, and 0.i (where 0 is any single digit) on an empty input is apparently truthy.. :/ try it online. If you save the infinite list in the header in a variable and use that in the filter, it does work, but unfortunately is also 7 bytes: try it online. \$\endgroup\$ Commented Oct 3, 2023 at 10:00
6
\$\begingroup\$

Haskell + hgl, 19 bytes

nt~<<pa(ef<P1)<(0:)

Explanation

  • (0:) add a zero to the front of the list
  • pa map over consecutive elements of a list ...
  • ef<P1 range excluding the initial element
  • nt~< concat map removing the last element of each range.

Reflection

There are some things that can be improved

  • K0 is nominally a shortcut for (0:) but it has issues with type ambiguity here. That should be investigated.
  • This really wants an exclusive range, having to use P1 and nt is a really big waste. There should be various exclusive ranges for Enums.
  • This could use a pa with a concat, but I'm not sure how reusable that would be.
  • Overall there could just be operations for monotonic lists. A function to determine if something is an element of a monotonic list would probably be useful here and elsewhere.
\$\endgroup\$
6
\$\begingroup\$

Scratch 3, 138 bytes

-9 bytes by att

define
forever
set[b v]to(
ask()and wait
add(answer)to[a v
repeat(answer
change[b v]by(1
if<not<[a v]contains(b)?>>then
say(b
add(b)to[a v
Program Image

Attempt This Online! | Test it on Scratchblocks!

Continuously prompts for input while printing out the missing integers.

\$\endgroup\$
1
  • \$\begingroup\$ when gf clicked -> define \$\endgroup\$
    – att
    Commented Oct 4, 2023 at 4:58
5
\$\begingroup\$

Vyxal, 53 bitsv2, 6.625 bytes

-10 bits by lyxal

£Þ∞'¥ḟu=
£Þ∞'¥ḟu=­⁡​‎‎⁡⁠⁢‏⁠‎⁡⁠⁣‏⁠‎⁡⁠⁤‏‏​⁡⁠⁡‌⁢​‎‎⁡⁠⁢⁢‏‏​⁡⁠⁡‌⁣​‎‎⁡⁠⁡‏⁠‎⁡⁠⁢⁡‏‏​⁡⁠⁡‌⁤​‎‎⁡⁠⁢⁣‏⁠‎⁡⁠⁢⁤‏‏​⁡⁠⁡‌­
 Þ∞'      # ‎⁡Filter list of positive integers by
     ḟ    # ‎⁢Index of integer
£   ¥     # ‎⁣in input list
      u=  # ‎⁤is -1 (not in input)
💎

Try it Online!

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

Haskell, 30 bytes

(1%)
p%(h:t)=[p..h-1]++(h+1)%t

Try it online!

33 bytes:

f l=do(a,b)<-zip(0:l)l;[a+1..b-1]

34 bytes

f l=[n|n<-[1..],all(/=n)$take n l]

Try it online!

\$\endgroup\$
2
  • \$\begingroup\$ what does the (1%) do here? \$\endgroup\$ Commented Oct 6, 2023 at 1:35
  • 1
    \$\begingroup\$ @JayantChoudhary It's the function (%) that's defined below but curried with its first argument set to 1. \$\endgroup\$
    – xnor
    Commented Oct 6, 2023 at 2:26
4
\$\begingroup\$

R, 54 bytes

g=\(f,i,j=1,k=1,l=f(k)>j)`if`(i,g(f,i-l,j+1,k+!l),j-1)

Attempt This Online!

Input & output as functions that take an index and return an item of the list


R, 48 bytes

repeat{if((y=scan(,,1))>T)cat(T:(y-1),'');T=y+1}

Attempt This Online!

Takes input from STDIN or the R console, and outputs the non-inclusive ranges between successive input values to STDOUT or the R console.

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

x86 machine code, 13 bytes

This is basically a function that would be part of a device driver: it repeatedly reads the same address, so that should be an MMIO register for a PCIe device that accepts an input sequence. It outputs via port I/O to a specified port number (perhaps on the same PCIe device). Or more realistically, this runs in a VM where the hypervisor handles these streams. In C for the x86-64 System V ABI, void complement_sequence(int dummy, volatile int *input, uint16_t output_portnum) (except this is 32-bit code.)

IDK how justifiable it is to do binary I/O to MMIO and an IO port; it could save bytes incrementing pointers if used for finite challenges, and is not usable as a function on data in memory. But an infinite series requires I/O, if we pretend that 32-bit fixed-width integers didn't actually cap the input + output size as 4 x 2^32 bytes = 16 GiB, which x86-64 can easily handle. I don't plan to use this (or C volatile int*) for any finite challenges.

               ;; MMIO address in ESI for input
               ;; I/O port number in DX for output (or pointer in EDI for MMIO)
               complement_sequence:
 31C0            xor   eax, eax      ; start as if last value written or considered for writing was 0
                                     ; So we output (0, first_seq_num) non-inclusive on both ends
                .next_seq:
 8B0E            mov   ecx, [esi]   ; next sequence number
 A8              db  0xa8  ; opcode for test al, imm8 works like a forward jump by 1 byte  ;  jmp .entry  
               .write:              ; do {
 EF              out  dx, eax         ; 1-byte instruction skipped on first iteration
                .entry:                ; entry point for first inner iteration
 40              inc  eax              ; ++next_write
 39C8            cmp  eax, ecx
 75FA            jne  .write        ; } while(next_write != next_seq);
 EBF5            jmp  .next_seq
          ; no ret, we never return

Tested with a debugger locally, after replacing out with stosd and adding add esi, 4 after the load. Then I can pass it pointers to arrays in memory, and display (int[15])outbuf as I si in GDB.


Less golfed is 14 bytes, without the partial-instruction hack for loop entry skipping the 1-byte out dx, eax. The code above does that by using the opcode for a 2-byte test al, imm8 as equivalent to a 1-byte jmp forward, consuming the first byte as an immediate so it doesn't run on entry to the loop, only on subsequent iterations.

;; MMIO address in ESI for input
;; I/O port number in DX for output (or pointer in EDI for MMIO)
complement_sequence_less_golfed:
  xor   eax, eax      ; start as if last value written or considered for writing was 0
                      ; So we output (0, first_seq_num) non-inclusive on both ends
 .next_seq:
  mov   ecx, [esi]   ; next sequence number
  jmp .entry  
.write:              ; do {
  out  dx, eax         ; or  mov  [edi], eax for MMIO
 .entry:
  inc  eax               ; ++next_write
  cmp  eax, ecx
  jne  .write        ; } while(next_write != next_seq);
  jmp  .next_seq
; no ret needed, this is a noreturn function

Algorithm: start with i = 0; (EAX)

  • x = input from sequence (ECX)
  • for ( ; ++i != x ; ) { out(i); }
  • leave the loop with i == x, so i = previous sequence number.
  • repeat, getting a new x. (With i the same.)

This feels like a lot of jmp instructions, like maybe there's a better branch layout I'm not seeing. But with 2 nested loops, one of which might have run 0 iterations of part of the body, I guess this is reasonable.

\$\endgroup\$
1
  • \$\begingroup\$ the test %al hack is pretty sexy. \$\endgroup\$
    – Noah
    Commented Oct 18, 2023 at 16:52
3
\$\begingroup\$

Python, 79 bytes

lambda x,j=0:(i for i in count()if i-j or(j:=next(x))*0)
from itertools import*

Attempt This Online!

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

Jelly, 9 bytes

‘rƓṪḷṄ€Ɗß

Try it online!

A full program that reads an infinite list from STDIN and outputs an infinite list to STDOUTbof the complement.

Explanation

‘         | Increment by 1 (will start from an implicit zero)
 rƓ       | Range from this to the next number from STDIN
       Ɗ  | Following as a monad using this range as an argument
   Ṫ      | Tail
    ḷ     | Left value (I.e. the tail above) rather than:
     Ṅ€   | - Output all of the remaining values in the range to STDOUT separated by new lines
        ß | Recursively call the link again
\$\endgroup\$
3
\$\begingroup\$

JavaScript, 49 48 bytes

function*(L,P=0){for(v of L)while(++P<v)yield P}

Try it online!

Takes an iterable and returns an iterable. Starts from 1.

-1 thanks to bsoelch.

\$\endgroup\$
1
  • \$\begingroup\$ You do not need the semicolon tio \$\endgroup\$
    – bsoelch
    Commented Oct 3, 2023 at 16:55
3
\$\begingroup\$

Python, 50 bytes

lambda s,*i:(n for z in s if{n:=len(i:={*i,z})}-i)

Attempt This Online!

Test harness borrowed from @bsoelch.

How?

For each prefix of the given sequence checks whether it contains its length. If not yields the length.

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

Ruby, 58 ... 35 bytes

->g{->n{b=0;n+=1until g[b+=1]>n;n}}

Try it online!

Accept a generator function in input, returns a function.

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

Minecraft Data Pack via Lectern, 202 bytes

@function a:b
scoreboard players add a  1
function a:a
execute if score o  = a  run scoreboard players add i  1
execute if score o  > a  run tellraw @a {"score":{"name":"a","objective":""}}
function a:b

The function is a:b.

Takes input as a function a:a, which takes in i <empty> the 0-based index of an element and returns it, and outputs all numbers to chat.

Assumes the objective <empty> exists but no values in it do.

Might be invalid, because while <empty> is a valid objective, it requires weird workarounds from the function to work with it because it can't appear at the end of commands.

This is how you'd have the squares as input, for example:

@function a:a
scoreboard objectives add temp dummy
execute store result score i temp run scoreboard players add i  1
scoreboard players remove i  1
execute store result score o  run scoreboard players operation i temp *= i temp
\$\endgroup\$
2
\$\begingroup\$

Charcoal, 19 bytes

WNF…⊕↨υ⁰↨⊞Oυι⁰«IκD⎚

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

WN

Keep inputting numbers while they're positive. (Which they should always be, but it does also mean that if you try this interactively you can enter 0 to quit.)

F…⊕↨υ⁰↨⊞Oυι⁰«

Push the input number to the predefined list, but make a range between the previous number (defaulting to 0) and the current number, and loop over that range.

IκD⎚

Output the current number eagerly so that it will appear before the next input.

I output each number individually because outputting a range fails if it is empty. Maybe I should make Dump(); do nothing if the canvas is completely empty?

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

Headass, 22 bytes

{{D+^(U)}:{PD+^(R):};}

I'll be honest, I have no idea how infinite input streams work, and I have no idea whether either implementation of the language supports it, but the actual language itself takes input similarly to brainfuck and doesn't have any issues with getting infinite input, so this is at least theoretically correct... let me know if that's an issue :P

If you want to test it out with infinite output, you'll have to use my online interpreter and run this command:

srun('{{D+^(U)}:{PD+^(R):};}',...list)

with list replaced by the list of your choice. With the speed this program runs at, you're probably going to start seeing outputs at around 3000-4000 so keep that in mind if you're inputting something finite / short.

For a version which halts at the end of input (in case you just want to try it out), try this modified version;

{{D+^(U)}:{PD+^(R):};N()}

Try It Online!

Make sure input isn't empty or of the form 1,2...n or else it will freeze :P DSO doesn't have a time limit, and those input cases are nontrivial to fix. This has no bearing on the validity of the actual program as it relates to the challenge.

Explanation

{{D+^(U)}:{PD+^(R):};}  full program
{                   ;}  while(true)
 {D+^(U)}:                do {} while(++i == nextinput())
           P              do {print(i)}
          { D+^(R):}      while(++i == currentinput())
\$\endgroup\$
1
\$\begingroup\$

MaybeLater, 68 bytes

wheni is*{if(i<n)printi elsen=readline0when0spass i++}n=readline0i=1

Try it online!

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

Befunge-98 (PyFunge), 39 bytes

1>:&\->:3j>;#_;\:.1+\1-3jj'<;$1+3jj!'<

Try it online!
Takes input in the form 1 3 5 7 ... and outputs in the same form. You will need to manually interrupt the TIO program to see the result, since the program doesn't terminate (it assumes infinite input).

Explanation

I have replaced the unprintable character with the letter R (since it is supposed to be the character with ascii value 18, and R is the 18th letter of the alphabet)

1>:&\->:3j>;#_;\:.1+\1-3jjR'<;$1+3jj!'<    Program
1                                          Push 1
 >                               3jj!'<    Repeat forever (the j!' is read backwards and
                                           makes the IP jump 33 cells back to the start)
  :&                                       Duplicate top of stack and read input
    \-                                     Swap top two elements and then get difference
      >:3j>;#_;        3jjR'<;             Inner loop (Repeat until top of stack is 0)
       :3j                                 Duplicate top of stack then jump to _
          >;#_;              ;             If top of stack is not 0, continue looping,
                                           otherwise jump out of loop
               \:                          Swap then Duplicate
                 .                         Pop and output
                  1+                       Increment
                    \1-                    Swap then decrement
                       3jjR'<              Return to start of loop (the unprintable
                                           character has ascii value of 18, which is how
                                           far the IP jumps)
                              $1+          Pop and increment
                                 3jj!'<    Return to start of main loop (the j!' is read
                                           backwards and makes the IP jump 33 cells back
                                           to the start, since ! has ascii value of 33)
\$\endgroup\$
1
\$\begingroup\$

brainfuck, 35 bytes

+[>,<[->->+<<]>[->.+<]>[-<<+>>]<<+]

Try it online!

Note that this inputs and returns raw bytes rather than ascii numbers, and it runs forever regardless of EOF, so TIO isn't the best way to demo it. You can use my own Brainfuck interpreter and pipe the input/output through atob.py and btoa.py.

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

JavaScript (SpiderMonkey), 35 bytes

g=>f=(n,i=0)=>g(i)>n+i?n+i:f(n,i+1)

Try it online!

Input and output as function

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.