14
\$\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\$
  • 2
    \$\begingroup\$ Restricting the numbers to a fixed range makes this problem even simpler. \$\endgroup\$ – Martin Ender 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\$ – Martin Ender 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]
| improve this answer | |
\$\endgroup\$
  • \$\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

| improve this answer | |
\$\endgroup\$
  • \$\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.

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Do you need f=:? \$\endgroup\$ – Esolanging Fruit 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
    \$\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\\<]

| improve this answer | |
\$\endgroup\$
  • 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\$ – algorithmshark 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\$

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
$
| improve this answer | |
\$\endgroup\$
  • 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\$

Ruby, 32 bytes

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

Defines a function f to be called with an array.

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Any comments from the downvoter? Did I miss some part of the spec? \$\endgroup\$ – Martin Ender Sep 30 '14 at 13:19
  • \$\begingroup\$ I doubt it. Several other answers (including mine) got a mystery downvote. \$\endgroup\$ – Greg Hewgill 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\$ – Martin Ender Sep 30 '14 at 16:07
  • \$\begingroup\$ Why do you need the f=? \$\endgroup\$ – Esolanging Fruit May 2 '17 at 0:47
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

| improve this answer | |
\$\endgroup\$
  • \$\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\$ – Peter Taylor 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
| improve this answer | |
\$\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.
| improve this answer | |
\$\endgroup\$
  • \$\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\$ – Martin Ender 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
| improve this answer | |
\$\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)
     ))
  )
)
| improve this answer | |
\$\endgroup\$
1
\$\begingroup\$

Python, 37 characters

f=lambda a:min(set(range(21))-set(a))
| improve this answer | |
\$\endgroup\$
  • \$\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\$ – Mega Man 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 :)

| improve this answer | |
\$\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
| improve this answer | |
\$\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!

| improve this answer | |
\$\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
| improve this answer | |
\$\endgroup\$
1
\$\begingroup\$

APL (Dyalog), 19 bytes

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

Try it online!

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

| improve this answer | |
\$\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.

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ 20 bytes using Ans: Prompt X:0:While not(prod(ʟX-Ans:Ans+1:End:Ans \$\endgroup\$ – JosiahRyanW 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
| improve this answer | |
\$\endgroup\$
1
\$\begingroup\$

APL (Dyalog Classic), 11 bytes

f←⊃⊢~⍨0,⍳∘⍴

Try it online!

| improve this answer | |
\$\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!

| improve this answer | |
\$\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.
| improve this answer | |
\$\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
| improve this answer | |
\$\endgroup\$
  • \$\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}'
| improve this answer | |
\$\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;
}
| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Produces -1 for test case []. \$\endgroup\$ – OldCurmudgeon 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
| improve this answer | |
\$\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.

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

PHP, 38 Bytes

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

PHP, 39 Bytes

<?for(;in_array($i++,$_GET););echo$i-1;
| improve this answer | |
\$\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.