15
\$\begingroup\$

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
\$\endgroup\$
8
  • 2
    \$\begingroup\$ Restricting the numbers to a fixed range makes this problem even simpler. \$\endgroup\$ Sep 29 '14 at 21:25
  • \$\begingroup\$ @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. \$\endgroup\$
    – xnor
    Sep 29 '14 at 21:27
  • \$\begingroup\$ No need for that test case. You said, the input can only contain 21 elements. \$\endgroup\$ Sep 29 '14 at 21:28
  • \$\begingroup\$ @MartinBüttner Right, fencepost. Thanks. \$\endgroup\$
    – xnor
    Sep 29 '14 at 21:29
  • 1
    \$\begingroup\$ @KevinFegan Yes, the maximum possible output is 20. My comment was mistaken and I think MartinBüttner typoed. \$\endgroup\$
    – xnor
    Oct 1 '14 at 0:13

41 Answers 41

1
2
0
\$\begingroup\$

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)]
\$\endgroup\$
0
\$\begingroup\$

Jelly, 7 bytes (non-competing)

Ṁ‘‘Ḷḟ⁸Ḣ

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!

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

Japt, 7 bytes

@!UøXÃa
@    Ãa # Starting from zero, find the smallest integer
 !UøX   # that's not present in the input array.

Try it online!

\$\endgroup\$
0
\$\begingroup\$

F#, 38 bytes

let f s={0..20}|>Seq.except s|>Seq.min

Try it online!

Fairly straight-forward to be honest...

\$\endgroup\$
0
\$\begingroup\$

Perl 5 -p, 28 bytes

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

Try it online!

\$\endgroup\$
0
\$\begingroup\$

Lua, 92 bytes

x=function(a,...)q=...or 0 for i=0,#a do if a[i]==q then return x(a,q+1)end end return q end

This seems way too long.

Try it online!

\$\endgroup\$
0
\$\begingroup\$

Wolfram Language (Mathematica), 29 bytes

Min@Complement[0~Range~20,#]&

Try it online!

\$\endgroup\$
0
\$\begingroup\$

Stax, 5 bytes

wiix#

Run and debug it

w      run until condition is satisfied
 ii    push iteration index twice
   x#  number of times iteration index appears in input (non-zero is truthy)

When the loop is finished, the final iteration index will be on top of the main stack, and implicitly printed.

\$\endgroup\$
0
\$\begingroup\$

Python 2, 36 bytes

lambda a,i=0:i in a and f(a,i+1)or i

Try it online!

\$\endgroup\$
0
\$\begingroup\$

k, 7 bytes

*(!22)^

Try it online!

 (!22)  /[0, 1, 2, ..., 21]
      ^ /set difference between [0, 1, 2, ..., 21] and input (called exclude)
*       /get first element

For an arbitrary positive maximum instead of 20, the smallest I have so far is 13 bytes:

{*(!2+|/x)^x}
\$\endgroup\$
0
\$\begingroup\$

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

\$\endgroup\$
0
1
2

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.