26
\$\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\$ Commented Sep 29, 2014 at 21:25
  • 1
    \$\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
    Commented Sep 29, 2014 at 21:27
  • 1
    \$\begingroup\$ No need for that test case. You said, the input can only contain 21 elements. \$\endgroup\$ Commented Sep 29, 2014 at 21:28
  • 1
    \$\begingroup\$ @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? \$\endgroup\$ Commented Oct 1, 2014 at 0:10
  • 2
    \$\begingroup\$ @KevinFegan Yes, the maximum possible output is 20. My comment was mistaken and I think MartinBüttner typoed. \$\endgroup\$
    – xnor
    Commented Oct 1, 2014 at 0:13

73 Answers 73

1 2
3
0
\$\begingroup\$

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}'
\$\endgroup\$
0
\$\begingroup\$

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;
}
\$\endgroup\$
1
  • \$\begingroup\$ Produces -1 for test case []. \$\endgroup\$ Commented Sep 30, 2014 at 16:08
0
\$\begingroup\$

Cobra - 50

def f(l)
    for n in 22,if n not in l,break
    print n
\$\endgroup\$
0
\$\begingroup\$

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.

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

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

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

Pyt, 7 bytes

05²Ř←\↓

Try it online!

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

Arturo, 27 17 bytes

$=>[[email protected]&]

Try it

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

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!

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

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

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!

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

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

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
\$\endgroup\$
1 2
3

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.