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

Perl - 34

Here's a subroutine.

sub f{$_~~@_?1:return$_ for0..20}

Test with:

perl -e'print f(0,1,3,4,5,6,7); sub f{$_~~@_?1:return$_ for 0..20}'

Answer 2

Java, 93

int f(int[]a){int i=0,j=0,k=a.length;for(;i++<20&j<k;){for(j=0;j<k&&a[j++]!=i;);}return i-1;}

Ungolfed:

int f(int[] a) {
    int i = 0, j = 0, length = a.length;
    for (; i < 20 & j < length; i++) {
        for (j = 0; j < length && a[j] != i; j++) { }
    }
    return i - 1;
}

Answer 3

Cobra - 50

def f(l)
    for n in 22,if n not in l,break
    print n

Answer 4

Javascript, 74

i=-1;a=prompt().split(',');while(i<21&&a.indexOf(String(++i))>=0);alert(i)

Nice and simple! Note the empty while loop.

Answer 5

JavaScript (E6) 35

Recursive function, array parameter in input and returning the mex. Not limited to 20

F=(l,i=0)=>~l.indexOf(i)?F(l,++i):i

Test in FireFox/FireBug console

;[[1],[0],[2, 0],[3, 1, 0, 1, 3, 3],[],[1, 2, 3],
[5, 4, 1, 5, 4, 8, 2, 1, 5, 4, 0, 7, 7],[3, 2, 1, 0],[0, 0, 1, 1, 2, 2, 3],
[1, 0, 7, 6, 3, 11, 15, 1, 9, 2, 3, 1, 5, 2, 3, 4, 6, 8, 1, 18]]
.forEach(list => console.log(list, F(list)))

Output

[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 6

Pyth, 6 bytes

f!}TQZ

Test suite

Makes no assumptions on the contents of the list.

Explanation:

f!}TQZ | Full code
-------+--------------------------------
f    Z | First T starting at 0 such that
 !}TQ  |  T is not in the input

Answer 7

Pyt, 7 bytes

05²Ř←\↓

Try it online!

  05²Ř           generate [0,1,2,...,25]
  ←              get input
  \              set difference
  ↓              get minimum; implicit print

Answer 8

Arturo, 27 17 bytes

$=>[[email protected]&]

Try it

$=>[       ; a function
    min    ; minimum of
    --     ; difference of
    @0..20 ; 0..20, reified
    &      ; and input
]          ; end function

Answer 9

Java 8 (OpenJDK 8), 49 bytes

Solution using only inline stream :

l->l.stream().sorted().reduce(0,(a,b)->a<b?a:b+1)

Try it online!

Answer 10

Stax, 6 bytes

21r|^h

Run and debug it

This is my first answer in Stax, so I may be missing some builtin that helps.

Explanation

21r|^h # 
21r    # range 0..20
   |^  # setwise difference with the input
     h # first element

Answer 11

JavaScript (Node.js), 37 bytes

Only 4 bytes above the best JS solution :'(

l=>l.sort().map(b=>a=a<b?a:b+1,a=0)|a

Try it online!

Answer 12

GNU sed, 127 bytes

s/.*/ & %-,-0123456789#/;:1;s/%0*(.*)(.)(,.*\2)(.)/%0\1\4\3\4/;s/(.)#(.*\1)(.)/\30\2\3/;/ (\S*) .*%0*\1,/b1;s/.*%0*(..*),.*/\1/

Try it online!

Without the array limit, six more bytes are needed for the inner loop that handles the 99->100 case:

s/.*/ & %-,-0123456789#/
:1
s/%0*(.*)(.)(,.*\2)(.)/%0\1\4\3\4/
:2
s/(.)#(.*\1)(.)/\30\2\3/
t2
/ (\S*) .*%0*\1,/b1
s/.*%0*(..*),.*/\1/

Answer 13

Z80 machine language, 11 bytes

Base address of list in HL, length in BC.

AF C5 E5 ED B1 E1 C1 C0 3C 18 F6

Returns with mex in A unless it's at least 256, then never returns. If you replace the last two bytes with B7 20 F5 C8 then it returns with mex in A if it's at most 255 and with the zero flag OFF, else with 0 in A and zero flag ON.

    xor a
l:  push bc
    push hl
    cpir // 8086: repnz scas
    pop hl
    pop bc
    ret nz
    inc a
    jr l

The alternative above replaces jr l with:

    or a
    jr nz,l
    ret