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

11
\$\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
    Sep 30 '14 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
    Sep 30 '14 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
    Oct 1 '14 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
    Oct 1 '14 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
    Oct 1 '14 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
    Sep 29 '14 at 21:47
  • \$\begingroup\$ @xnor Sadly, 20 - sourceforge.net/p/cjam/wiki/Variables \$\endgroup\$
    – Optimizer
    Sep 29 '14 at 21:48
  • \$\begingroup\$ A lucky choice! \$\endgroup\$
    – xnor
    Sep 29 '14 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\$ May 2 '17 at 0:44
  • \$\begingroup\$ Since November 2017 i.@21-.] would save 1 byte. \$\endgroup\$
    – FrownyFrog
    May 7 '18 at 16:26
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
    Sep 29 '14 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\$ Sep 30 '14 at 17:09
  • \$\begingroup\$ @algorithmshark No way around it, you are very right. Fixed. And thank you. \$\endgroup\$
    – AndoDaan
    Sep 30 '14 at 17:34
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\$ Sep 30 '14 at 13:19
  • \$\begingroup\$ I doubt it. Several other answers (including mine) got a mystery downvote. \$\endgroup\$ Sep 30 '14 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\$ Sep 30 '14 at 16:07
  • \$\begingroup\$ Why do you need the f=? \$\endgroup\$ May 2 '17 at 0:47
3
\$\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\$
2
  • 1
    \$\begingroup\$ I don't think you need "(...)" around the $1. \$\endgroup\$
    – Dennis
    Sep 30 '14 at 16:42
  • 1
    \$\begingroup\$ Pipe-separated is fine, it meets the list-like condition of the spec. \$\endgroup\$
    – xnor
    Sep 30 '14 at 20:35
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
    Sep 29 '14 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\$ Sep 29 '14 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\$ Sep 29 '14 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\$
1
\$\begingroup\$

Python, 37 characters

f=lambda a:min(set(range(21))-set(a))
\$\endgroup\$
3
  • \$\begingroup\$ Beat me by a couple of seconds. BTW, it's range(21). \$\endgroup\$
    – qwr
    Sep 29 '14 at 22:04
  • \$\begingroup\$ This seems to be the shortest solution. The recursive solution f=lambda l,i=0:i in l and f(l,i+1)or i is one char longer and the iterative solution i=0;l=input()\nwhile i in l:i+=1\nprint i is two chars longer (not storing the input makes it be taken repeatedly). Without the 20 bound, I think these approaches would prevail. \$\endgroup\$
    – xnor
    Sep 30 '14 at 20:33
  • \$\begingroup\$ Couldn't this be an anonymous function? If it could, you can save 2 bytes. \$\endgroup\$
    – univalence
    May 1 '17 at 16:10
1
\$\begingroup\$

C# - 64 chars

int f(int[] a){return Enumerable.Range(0,20).Except(a).First();}

Not always Rarely the best golfing language, but is easy to write and understand :)

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

Scala, 18 bytes

0 to 20 diff l min

l is a list of Int.

scala> val l = List(0,1,5)
l: List[Int] = List(0, 1, 5)

scala> 0 to 20 diff l min
res0: Int = 2
\$\endgroup\$
1
\$\begingroup\$

Java, 91 bytes

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

Try it online!

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

Java 7, 69 66 bytes

int c(java.util.List a){int r=0;for(;a.contains(r);r++);return r;}

-3 bytes thanks to @LeakyNun

Explanation:

Supports not only 0-20, but 0-2147483647 instead (which actually saves bytes).

int c(java.util.List a){    // Method with List parameter and integer return-type
  int r=0;                  //  Return integer
  for(;a.contains(r);r++);  //  Continue raising `r` as long as the list contains the current `r`
  return r;                 //  Return result-integer
}                           // End of method

Test code:

Try it here.

import java.util.ArrayList;
import java.util.Arrays;
class M{
  static int c(java.util.List a){int r=0;for(;a.contains(r);r++);return r;}

  public static void main(String[] a){
    System.out.println(c(Arrays.asList(1)));
    System.out.println(c(Arrays.asList(0)));
    System.out.println(c(Arrays.asList(2, 0)));
    System.out.println(c(Arrays.asList(3, 1, 0, 1, 3, 3)));
    System.out.println(c(new ArrayList()));
    System.out.println(c(Arrays.asList(1, 2, 3)));
    System.out.println(c(Arrays.asList(5, 4, 1, 5, 4, 8, 2, 1, 5, 4, 0, 7, 7)));
    System.out.println(c(Arrays.asList(3, 2, 1, 0)));
    System.out.println(c(Arrays.asList(0, 0, 1, 1, 2, 2, 3)));
    System.out.println(c(Arrays.asList(1, 0, 7, 6, 3, 11, 15, 1, 9, 2, 3, 1, 5, 2, 3, 4, 6, 8, 1, 18)));
  }
}

Output:

0
1
1
2
0
0
3
4
4
10
\$\endgroup\$
2
1
\$\begingroup\$

APL (Dyalog), 19 bytes

(0⍳⍨⊢=⍳∘⍴)∘(⊂∘⍋⌷⊢)∪

Try it online!

I am probably missing out something important here. Golfing in progress...

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

TI-BASIC, 24 bytes

:0→A                 //Store 0 to A
:Prompt X            //Prompt list X
:While not(prod(ʟX-A //While A is not missing from list X
:A+1→A               //Increment A
:End                 //End While loop
:A                   //Print A

If Prompt X is given a list instead of a single number, it will automatically create a list named X that can be accessed with ʟX.

\$\endgroup\$
1
  • \$\begingroup\$ 20 bytes using Ans: Prompt X:0:While not(prod(ʟX-Ans:Ans+1:End:Ans \$\endgroup\$ Sep 24 '18 at 9:01
1
\$\begingroup\$

Stax, 6 bytes

¢╔⌂♀╠▬

Run and debug it

Explanation

21r:IUI             # Full program, unpacked
21                  # Push 21
  r                 # Range from 0...20
   :I               # Find all elements in input that exist in range
    U               # push -1
     I              # Get index of first occurrence of
\$\endgroup\$
0
1
\$\begingroup\$

APL (Dyalog Classic), 11 bytes

f←⊃⊢~⍨0,⍳∘⍴

Try it online!

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

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

PHP, 38 Bytes

<?=min(array_diff(range(0,20),$_GET));

PHP, 39 Bytes

<?for(;in_array($i++,$_GET););echo$i-1;
\$\endgroup\$

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.