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

• Martin Ender: Restricting the numbers to a fixed range makes this problem even simpler.
• xnor: @MartinBüttner If the array contains all number 0 to 20, the correct output is 21. I'll add a test case. Yes, the fixed range definitely makes it easier, though one could still arguably use sys.maxint or 2**64 if I didn't specify it.
• Martin Ender: No need for that test case. You said, the input can only contain 21 elements.
• Kevin Fegan: @MartinBüttner - I read ".. the length of the list and the allowed range of elements will both be between 0 and 20 inclusive" to mean that the list will have at most 20 elements. So, the highest output would be 20, given a list of all numbers starting with 0 and ending with 19. Am I wrong?
• xnor: @KevinFegan Yes, the maximum possible output is 20. My comment was mistaken and I think MartinBüttner typoed.

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]

• xnor: When the set is converted to list, is it always in sorted order?
• Dennis: Pyth's set difference preserves the order of the first argument (range(21)), which is ordered. (This also means the explanation isn't entirely accurate. Pyth and Python 3 are both fairly new to me.)
• izzyg: To clarify, - in Pyth is actually a filter - it filters the first argument for absence from the second argument, then converts it to the form of the first argument (string, list or set).
• izzyg: Also, Dennis, it should be h-U22Q so it will give the correct output of 21 on the input containing the full allowable range.
• Dennis: @isaacg: The list's length is also limited to 20, so it cannot contain all 21 numbers from 0 to 20.

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

• xnor: How high do the single-character numbers in CJam go?
• Optimizer: @xnor Sadly, 20 - sourceforge.net/p/cjam/wiki/Variables
• xnor: A lucky choice!

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.

• Esolanging Fruit: Do you need f=:?
• FrownyFrog: Since November 2017 i.@21-.] would save 1 byte.

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

N≜¬∈

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

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

• Unrelated String: Oddly enough, it looks like the ≜ can be dropped going the other way.
• Unrelated String: ...Actually, the original version can handle an empty list, while this can't. Whoops
• Fatalize: @UnrelatedString Reverted.

Answer 6

Nekomata, 2 bytes

kf

Attempt This Online!

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

Answer 7

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 8

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

• Optimizer: Dammit Golfscript for saving 1 character so as to not read the input -_-

Answer 9

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\\<]

• algorithmshark: This fails to give any output on the input {0 1 2}, because you need to rz one more than the largest number. Just going straight for 20rzj\\<] fixes this and saves a char.
• AndoDaan: @algorithmshark No way around it, you are very right. Fixed. And thank you.

Answer 10

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
$

• Dennis: I don't think you need "(...)" around the 1ドル.
• xnor: Pipe-separated is fine, it meets the list-like condition of the spec.
• pxeger: If you take input separated by newlines, you can use grep instead of egrep

Answer 11

Jelly, 7 bytes

Ṁ‘‘Ḷḟ8Ḣ

Try it online!

How it works

Ṁ‘‘Ḷḟ8Ḣ Main Link; argument is z
Ṁ‘‘ Takes 2 above the largest element in z
 Ḷ Takes lowered range (thus returning [0, ..., max(z) + 1])
 ḟ8 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!

• Leaky Nun: 1 byte off

Answer 12

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 13

Ruby, 32 bytes

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

Defines a function f to be called with an array.

• Martin Ender: Any comments from the downvoter? Did I miss some part of the spec?
• Greg Hewgill: I doubt it. Several other answers (including mine) got a mystery downvote.
• Martin Ender: @ipi but it does... in exactly the same format given in the examples in the challenge posts, e.g. f[[0, 1]] (where the outer brackets are invocation syntax and the inner brackets define the array).
• Esolanging Fruit: Why do you need the f=?

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

9ḶḟμḢ

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

• maxb: With the new changes that are (hopefully) being added to TIO today, there's a 4 byte solution to this problem. It is restricted to an upper limit defined in the code, but since MathGolf has a 1-byte literal for 10^8, it shouldn't be noticeable.
• maxb: This was the exact solution I had (I used Z instead of J because I was lazy).

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

Prolog (SWI), (削除) 64 (削除ここまで) 35 bytes

-29 bytes thanks to @Jo King

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

Try it online!

Answer 18

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 19

Rust, (削除) 117, 113, 79, 78 (削除ここまで) 58 bytes

|l:&[u8]|(0..22).filter(|n|!l.contains(n)).next().unwrap()

Attempt This Online!

Answer 20

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

• Optimizer: Shouldn't the ; before the input string be counted in the program itself ?
• Peter Taylor: @Optimizer, that's simulating input from stdin because the online GolfScript site doesn't support a separate input field.

Answer 21

Xojo, 55 bytes

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

Answer 22

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.

• Martin Ender: Sweet, that was my first attempt, but I couldn't get the destructuring to work - I didn't think of surrounding it with brackets. Btw, you can use 20 instead of 21, because the input can only contain 20 elements.

Answer 23

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 24

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 25

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 26

Perl 5 -p, 28 bytes

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

Try it online!

Answer 27

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.

• Julian: Can be shortened down to 24 bytes :)

Answer 28

Desmos, 52 bytes

L=[0...20]
f(l)=L[[(i-join(e,l))^2.minfori=L]>0].min

Try It On Desmos!

Try It On Desmos! - Prettified

Answer 29

Zsh, 31 bytes

for ((;$@[(I)$[i]];i++)):
bye i

Attempt This Online! Outputs via exit code.

Answer 30

05AB1E, (削除) 6 (削除ここまで) 5 bytes

2ÝIKн

-1 byte thanks to @emanresuA

Try it online or verify all test cases.

Explanation:

2Ý # Push a list in the range [0,26]
 # (26 is the smallest 1-byte constant above 19)
 IK # Remove all values of the input-list from this ranged list
 н # Pop and push the first integer remaining (which is the minimum)
 # (which is output implicitly as result)

• emanresu A: Would using a builtin number larger than 20 save bytes?
• Kevin Cruijssen: @emanresuA It indeed would, thanks.