Minimum excluded number

Question

This is intended to be an easy, bite-size code-golf.

The mex (minimal excluded number) of a finite collection of numbers is the smallest non-negative integer 0, 1, 2, 3, 4, ... that does not appear in the collection. In other words, it's the minimum of the complement. The mex operation is central to the analysis of impartial games in combinatorial game theory.

Your goal is to write a program or named function to compute the mex using as few bytes as possible.

Input:

A list of non-negative integers in any order. May contain repeats. For concreteness, the length of the list and the allowed range of elements will both be between 0 and 20 inclusive.

The definition of "list" here is flexible. Any structure that represents a collection of numbers is fine, as long as it has a fixed ordering of elements and allows repeats. It may not include any auxiliary information except its length.

The input can be taken as a function argument or through STDIN.

Output

The smallest excluded number. Output or print it.

Test cases

[1]
0
[0]
1
[2, 0]
1
[3, 1, 0, 1, 3, 3]
2
[]
0
[1, 2, 3]
0
[5, 4, 1, 5, 4, 8, 2, 1, 5, 4, 0, 7, 7]
3
[3, 2, 1, 0]
4
[0, 0, 1, 1, 2, 2, 3]
4
[1, 0, 7, 6, 3, 11, 15, 1, 9, 2, 3, 1, 5, 2, 3, 4, 6, 8, 1, 18]
10

Answer 1

Pyth, 6 bytes

h-U21Q

Example run

$ pyth -c h-U21Q <<< '[5, 4, 1, 5, 4, 8, 2, 1, 5, 4, 0, 7, 7]'
3

How it works

  U21   range(21)
     Q  eval(input())
 -U21Q  setwisedifference(range(21), eval(input))          # Pyth function. Preserves order.
h-U21Q  setwisedifference(range(21), eval(input))[0]

Answer 2

CJam, 11 8 bytes

K),l~^1<

How it works:

K),         "Create an array with numbers 0 through 20"
   l~       "Read the input and eval it, resulting to an array"
     ^      "XOR the elements of two arrays, resulting in a complement array"
      1<    "Take the first element of the resultant array"

Sample input:

[1 0 7 6 3 11 15 1 9 2 3 1 5 2 3 4 6 8 1 18]

Output:

10

Try it online here

Answer 3

J - 13 char

f=:0{i.@21&-.

Very simple actions in J, and thus very hard to make smaller.

i.@21 creates a list from 0 to 20 inclusive. -. performs set-subtracts the input from this list. 0{ takes the first element of what's left, i.e. the smallest number. f=: defines a named function. At the REPL:

   f=:0{(i.21)&-.
   f 1
0
   f 0
1
   f 2 0
1
   f 3 1 0 1 3 3
2
   f ''    NB. empty list
0
   f 1 2 3
0
   f 5 4 1 5 4 8 2 1 5 4 0 7 7
3
   f 3 2 1 0
4
   f 0 0 1 1 2 2 3
4
   f 1 0 7 6 3 11 15 1 9 2 3 1 5 2 3 4 6 8 1 18
10

Since the release of J806 in November 2017, a new syntax exists which saves us one byte by letting us use i.@21 for the old (i.21) in this context.

Answer 4

Jelly, 5 4 bytes

0ḟ1#

Try it online!

Doesn't use the bounds on the input.

...am I missing something?

0       Starting with 0,
  1#    find the first integer
 ḟ      which is not in the input.

Answer 5

Brachylog, 4 bytes

ℕ≜¬∈

Try it online!

Works for any list size and any integer magnitudes.

Takes input from the Output variable, and outputs to the Input variable.

Explanation

ℕ      We want a non-negative integer
 ≜     Assign a value such that… 
  ¬∈   …it is not an element of the list

Answer 6

Golfscript 7

~21,^0=

A further-golfed version of Peter Taylor's answer. Community wiki since I don't have the rep to comment on his post.

The difference is using the known max list size from the question instead of length +1 to save a character and dropping the irrelevant $.

Try it online

Answer 7

Burlesque - 9 Bytes

20rzj\\<]

Takes input from stdin in the format {7 6 5 5 1 2 2 4 2 0}

Explained:

 20 rz   map a range from 0 to 20. (thanks to algorithmshark for the cocde fix)
  j \\    swaps the two arrays, and collects the difference between the two into a new array
  <]      gets the smallest element of the resulting array.

Try some examples:

{1 0 7 6 3 11 15 1 9 2 3 1 5 2 3 4 6 8 1 18}20rzj\\<]

{5 4 1 5 4 8 2 1 5 4 0 7 7}20rzj\\<]

Answer 8

Bash+coreutils, 23 bytes

seq 0 20|egrep -vwm1 $1

This assumes input as a | (pipe) separated list. E.g:

$ ./mex.sh "5|4|1|5|4|8|2|1|5|4|0|7|7"
3
$

Answer 9

Jelly, 7 bytes

Ṁ‘‘Ḷḟ⁸Ḣ

Try it online!

How it works

Ṁ‘‘Ḷḟ⁸Ḣ  Main Link; argument is z
Ṁ‘‘      Takes 2 above the largest element in z
   Ḷ     Takes lowered range (thus returning [0, ..., max(z) + 1])
    ḟ⁸   Exclude all elements from the range that are also in z
      Ḣ  Take the first element (which is the smallest)

Thanks to @LeakyNun for -1 byte!

Answer 10

Vyxal gH, 2 bytes

ʀ⊍

Try it Online! (Includes test cases)

   # H flag presets the stack to 100
ʀ  # inclusive range 0..100
 ⊍ # set difference
   # g flag takes the minimum of the top of stack after execution
   # which is implicitly output

Answer 11

Nekomata, 2 bytes

ᵏf

Attempt This Online!

ᵏf
ᵏ   Find the first natural number n such that:
 f  the input does not contain n

Answer 12

Trilangle, 53 bytes

'0.<_.\.>?0e#L_'\r/(&\,<.|.1.2S<.^#':2',.<..^\,!@.^)S

I'm not convinced this is optimal, but I've thought about it for a while and I don't think I can shrink it without substantial restructuring. I have proven that it's impossible to do this general approach without at least a grid of size n=8, and this is n=10.

Try it on the online interpreter!

Unfolds to this:

         '
        0 .
       < _ .
      \ . > ?
     0 e # L _
    ' \ r / ( &
   \ , < . | . 1
  . 2 S < . ^ # '
 : 2 ' , . < . . ^
\ , ! @ . ^ ) S . .

Equivalent to this C code:

#include <stdio.h>

// Read an integer from stdin, throwing out any separators. Returns -1 on EOF.
// Exact implementation is unimportant (and provided by the interpreter).
extern int getint(void);

int main() {
    // RED PATH
    // Keep a bitfield of the numbers that have been seen so far
    int field = 0;
    int i;
    while ((i = getint()) >= 0)
        // GREEN PATH
        field |= 1 << i;

    // BLUE PATH
    // Find the lowest nonzero bit
    int missing = 0;
    while (field & 1) {
        // MAGENTA PATH
        field >>= 1;
        ++missing;
    }

    // YELLOW PATH
    printf("%d\n", missing);
}

I am not doing an instruction-by-instruction walkthrough of this code. If you're interested, you can look into the disassembly feature of the interpreter.

Answer 13

Ruby, 32 bytes

f=->n{(0..20).find{|i|n-[i]==n}}

Defines a function f to be called with an array.

Answer 14

Jelly, 7 bytes

Another approach. Can be used in a chain with any arity, and doesn't need chain separator or anything.

‘Ṭ;0i0’

Because the answer is guaranteed to be less than 256, this also works:

Jelly, 5 bytes

⁹ḶḟµḢ

Try it online!

Answer 15

MathGolf, 5 4 bytes

Jr,╓

Try it online!

This solution is restricted to just the range 0 to 20, though this can be extended easily by increasing the initial range.

Explanation:

Jr     Range from 0 to 20
  ,    Remove elements from the input list from this range
   ╓   Return the minimum element

Alternatively, a 5 byte solution for all numbers:

Åï╧▲ï

Try it online!

Explanation:

Å  ▲   Do while true
  ╧    Does the input contain
 ï     The index of the loop?
    ï  Push the number of iterations of the last loop

Answer 16

Perl 6, 18 16 bytes

-2 bytes thanks to nwellnhof

{(0...*∉@_)-1}

Try it online!

Anonymous code block that counts up until it finds a number that is not an element of the input list, and returns the length of the range minus one

Answer 17

JavaScript (ES6), 33 bytes

Thanks to @fhuvi for letting me know that my answer to this more recent challenge also works here.

a=>a.reduce(m=>m+a.includes(m),0)

Try it online!

Answer 18

Rust, 117, 113, 79 78 bytes

|l:&[u8]|{let mut r:Vec<_>=(0..22).collect();r.retain(|n|!l.contains(n));r[0]}

Attempt This Online!

Explanation

|l: &[u8]| {
    // Make a vector of the integers from 0 to 21
    let mut r: Vec<_> = (0..22).collect();
    // Keep only the numbers that aren't in the input
    r.retain(|n|!l.contains(n));
    // Return the first remaining number in the vector
    r[0]
}

Answer 19

GolfScript (10 9 bytes)

~.,),^$0=

Takes input from stdin in the format [5 4 1 5 4 8 2 1 5 4 0 7 7].

Online demo

Answer 20

Xojo, 55 bytes

dim x as int8
while a.indexOf(x)>-1
x=x+1
wend
return x

Answer 21

Ruby, 22

x=->n{([*0..20]-n)[0]}

Explanation

• Input is taken as an argument to a lambda. It expects an Array of Integers.
• The input is subtracted from the array [0,1,2..20].
• Because the Array [0,1,2..20] is sorted, the first element must be the mex.

Answer 22

Haskell, 30

f s=filter(`notElem`s)[0..]!!0

This works for lists of all size and lists beyond 20. This can be made 15 bytes long if Data.List is imported:

f s=[0..]\\s!!0

Answer 23

Scheme - 219

(define (A X) (define (B X) (if (equal? (length X) 1) (+ (car X) 1) (if (< (- (cadr X) (car X)) 2) (B (cdr X)) (+ (car X) 1)))) (if (empty? X) `() (if (equal? (car (sort X <)) 0) (B (sort X <)) (- (car (sort X <)) 1))))

Not very competitive. But I like writing scheme :),

Here's the ungolfed code:

(define (minExclude X)
  (define (firstNonOneDifference X)
     (if (equal? (length X) 1)
         (+ (car X) 1)
     (if (< (- (cadr X) (car X)) 2) 
         (firstNonOneDifference (cdr X))
         (+ (car X) 1)
     ))
  )
  (let ([s (sort X <)])
     (if (empty? X)
         `()
     (if (equal? (car s) 0)
        (firstNonOneDifference s)
        (- (car s) 1)
     ))
  )
)

Answer 24

R, 27 bytes

Reads from stdin; computes the first element in the set difference between [0..20] and x.

x=scan()
setdiff(0:20,x)[1]

R, 36 bytes

which.min(y%in%x) returns the index of the first element of y that is not in x.

x=scan()
y=0:20
y[which.min(y%in%x)]

Answer 25

Perl 5 -p, 28 bytes

$#i++;/\b$#i\b/&&redo;$_=$#i

Try it online!

Answer 26

Powershell, 28 bytes

for(;+$i-in$args){$i++}+$i

Test script:

$f = {
 for(;+$i-in$args){$i++}+$i
#for(;$i++-in$args){}(--$i)   # alternative version
}

@(
    ,(0 , 1)
    ,(1 , 0)
    ,(2 , 3, 1, 0, 1, 3, 3)
    ,(0 )
    ,(0 , 1, 2, 3)
    ,(3 , 5, 4, 1, 5, 4, 8, 2, 1, 5, 4, 0, 7, 7)
    ,(4 , 3, 2, 1, 0)
    ,(4 , 0, 0, 1, 1, 2, 2, 3)
    ,(10, 1, 0, 7, 6, 3, 11, 15, 1, 9, 2, 3, 1, 5, 2, 3, 4, 6, 8, 1, 18)
) | % {
    $e, $a = $_
    $r = &$f @a
    "$($r-eq$e): $r"
}

Output:

True: 0
True: 1
True: 2
True: 0
True: 0
True: 3
True: 4
True: 4
True: 10

Explanation:

• Increment $i while the $args array contains the integer value +$i.
• Output a last integer value +$i.

Answer 27

Prolog (SWI), 64 35 bytes

-29 bytes thanks to @Jo King

L+X:-between(0,20,X),\+member(X,L).

Try it online!

Answer 28

Vyxal r, 7 5 4 bytes

₇ʀFg

-2 bytes thanks to lyxal

-1 byte thanks to Steffan

Try it online or verify all test cases.

Explanation:

 ʀ    # The range 0 to
₇     # 128
  F   # Filter out items from the range that are in the input list
      # (The r flag swaps the arguments)
    g  # Get the lowest one

Answer 29

Thunno, \$ 9 \log_{256}(96) \approx \$ 7.41 bytes

21RAq0sAh

Attempt This Online!

Explanation

21RAq0sAh  # Implicit input                     INPUT: [4, 1, 0, 2]
21R        # Push range(21)                     STACK: [4, 1, 0, 2], [0..20]
   Aq      # Check whether each of the items    STACK: [1, 1, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
           # in the input occurs in range(21)
     0sAh  # Find the index of the first 0      STACK: 3
           # (0-indexed)
           # Implicit output

Answer 30

Julia 0.6, 22 bytes

>(x,i=0)=i∈x?x>i+1:i

Try it online!

Minimally adapted from MarcMush's recursive solution to a related challenge.

Julia 0.6 supports ternary operators without spaces, which were deprecated in 0.7 and removed in 1.0.