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

10
\$\begingroup\$

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]
\$\endgroup\$
6
  • \$\begingroup\$ When the set is converted to list, is it always in sorted order? \$\endgroup\$
    – xnor
    Commented Sep 30, 2014 at 3:40
  • \$\begingroup\$ 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.) \$\endgroup\$
    – Dennis
    Commented Sep 30, 2014 at 3:48
  • 1
    \$\begingroup\$ 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). \$\endgroup\$
    – isaacg
    Commented Oct 1, 2014 at 6:55
  • \$\begingroup\$ Also, Dennis, it should be h-U22Q so it will give the correct output of 21 on the input containing the full allowable range. \$\endgroup\$
    – isaacg
    Commented Oct 1, 2014 at 6:57
  • \$\begingroup\$ @isaacg: The list's length is also limited to 20, so it cannot contain all 21 numbers from 0 to 20. \$\endgroup\$
    – Dennis
    Commented Oct 1, 2014 at 13:06
6
\$\begingroup\$

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

\$\endgroup\$
3
  • \$\begingroup\$ How high do the single-character numbers in CJam go? \$\endgroup\$
    – xnor
    Commented Sep 29, 2014 at 21:47
  • \$\begingroup\$ @xnor Sadly, 20 - sourceforge.net/p/cjam/wiki/Variables \$\endgroup\$
    – Optimizer
    Commented Sep 29, 2014 at 21:48
  • \$\begingroup\$ A lucky choice! \$\endgroup\$
    – xnor
    Commented Sep 29, 2014 at 21:50
5
\$\begingroup\$

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.

\$\endgroup\$
2
  • \$\begingroup\$ Do you need f=:? \$\endgroup\$ Commented May 2, 2017 at 0:44
  • \$\begingroup\$ Since November 2017 i.@21-.] would save 1 byte. \$\endgroup\$
    – FrownyFrog
    Commented May 7, 2018 at 16:26
5
\$\begingroup\$

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

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
\$\endgroup\$
3
  • 1
    \$\begingroup\$ Oddly enough, it looks like the can be dropped going the other way. \$\endgroup\$ Commented Sep 24, 2022 at 4:20
  • \$\begingroup\$ ...Actually, the original version can handle an empty list, while this can't. Whoops \$\endgroup\$ Commented Feb 26, 2023 at 14:46
  • 1
    \$\begingroup\$ @UnrelatedString Reverted. \$\endgroup\$
    – Fatalize
    Commented Feb 27, 2023 at 8:43
4
\$\begingroup\$

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

\$\endgroup\$
1
  • 1
    \$\begingroup\$ Dammit Golfscript for saving 1 character so as to not read the input -_- \$\endgroup\$
    – Optimizer
    Commented Sep 29, 2014 at 22:01
4
\$\begingroup\$

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

\$\endgroup\$
2
  • 1
    \$\begingroup\$ 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. \$\endgroup\$ Commented Sep 30, 2014 at 17:09
  • \$\begingroup\$ @algorithmshark No way around it, you are very right. Fixed. And thank you. \$\endgroup\$
    – AndoDaan
    Commented Sep 30, 2014 at 17:34
4
\$\begingroup\$

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
$
\$\endgroup\$
3
  • 1
    \$\begingroup\$ I don't think you need "(...)" around the $1. \$\endgroup\$
    – Dennis
    Commented Sep 30, 2014 at 16:42
  • 1
    \$\begingroup\$ Pipe-separated is fine, it meets the list-like condition of the spec. \$\endgroup\$
    – xnor
    Commented Sep 30, 2014 at 20:35
  • \$\begingroup\$ If you take input separated by newlines, you can use grep instead of egrep \$\endgroup\$
    – pxeger
    Commented Feb 26, 2023 at 15:25
4
\$\begingroup\$

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!

\$\endgroup\$
1
4
\$\begingroup\$

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

Nekomata, 2 bytes

ᵏf

Attempt This Online!

ᵏf
ᵏ   Find the first natural number n such that:
 f  the input does not contain n
\$\endgroup\$
4
\$\begingroup\$

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.

\$\endgroup\$
3
\$\begingroup\$

Ruby, 32 bytes

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

Defines a function f to be called with an array.

\$\endgroup\$
4
  • \$\begingroup\$ Any comments from the downvoter? Did I miss some part of the spec? \$\endgroup\$ Commented Sep 30, 2014 at 13:19
  • \$\begingroup\$ I doubt it. Several other answers (including mine) got a mystery downvote. \$\endgroup\$ Commented Sep 30, 2014 at 15:25
  • \$\begingroup\$ @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). \$\endgroup\$ Commented Sep 30, 2014 at 16:07
  • \$\begingroup\$ Why do you need the f=? \$\endgroup\$ Commented May 2, 2017 at 0:47
3
\$\begingroup\$

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!

\$\endgroup\$
3
\$\begingroup\$

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
\$\endgroup\$
2
  • \$\begingroup\$ 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. \$\endgroup\$
    – maxb
    Commented Nov 27, 2018 at 11:16
  • \$\begingroup\$ This was the exact solution I had (I used Z instead of J because I was lazy). \$\endgroup\$
    – maxb
    Commented Nov 28, 2018 at 7:41
3
\$\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
3
\$\begingroup\$

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!

\$\endgroup\$
3
\$\begingroup\$

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]
}
\$\endgroup\$
2
\$\begingroup\$

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

\$\endgroup\$
2
  • \$\begingroup\$ Shouldn't the ; before the input string be counted in the program itself ? \$\endgroup\$
    – Optimizer
    Commented Sep 29, 2014 at 22:20
  • 1
    \$\begingroup\$ @Optimizer, that's simulating input from stdin because the online GolfScript site doesn't support a separate input field. \$\endgroup\$ Commented Sep 29, 2014 at 22:52
2
\$\begingroup\$

Xojo, 55 bytes

dim x as int8
while a.indexOf(x)>-1
x=x+1
wend
return x
\$\endgroup\$
2
\$\begingroup\$

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.
\$\endgroup\$
1
  • \$\begingroup\$ 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. \$\endgroup\$ Commented Sep 29, 2014 at 22:38
2
\$\begingroup\$

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

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

Perl 5 -p, 28 bytes

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

Try it online!

\$\endgroup\$
2
\$\begingroup\$

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.
\$\endgroup\$
1
  • \$\begingroup\$ Can be shortened down to 24 bytes :) \$\endgroup\$
    – Julian
    Commented Nov 29, 2023 at 1:29
2
\$\begingroup\$

Prolog (SWI), 64 35 bytes

-29 bytes thanks to @Jo King

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

Try it online!

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

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
\$\endgroup\$
5
  • 1
    \$\begingroup\$ Try it Online! for 5 bytes \$\endgroup\$
    – lyxal
    Commented Sep 19, 2022 at 7:50
  • \$\begingroup\$ Try it Online! for test cases \$\endgroup\$
    – lyxal
    Commented Sep 19, 2022 at 7:50
  • \$\begingroup\$ @lyxal Smart, thank you \$\endgroup\$ Commented Sep 19, 2022 at 8:57
  • 1
    \$\begingroup\$ 4 bytes with r flag: Þ∞Fh \$\endgroup\$
    – naffetS
    Commented Sep 24, 2022 at 17:00
  • \$\begingroup\$ @Steffan That doesn't work for the [1] test case, but you can just remove the $ and from Lyxal's one and add the r flag \$\endgroup\$ Commented Sep 24, 2022 at 20:39
2
\$\begingroup\$

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

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.

\$\endgroup\$

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.