Número mínimo excluido

14

Esto está destinado a ser un código de golf fácil de tamaño de bocado.

El mex (número excluido mínimo) de una colección finita de números es el número entero no negativo más pequeño 0, 1, 2, 3, 4, ...que no aparece en la colección. En otras palabras, es el mínimo del complemento. La operación mex es fundamental para el análisis de juegos imparciales en la teoría de juegos combinatorios .

Su objetivo es escribir un programa o función con nombre para calcular el mex utilizando la menor cantidad de bytes posible.

Entrada:

Una lista de enteros no negativos en cualquier orden. Puede contener repeticiones. Para ser más concretos, la longitud de la lista y el rango permitido de elementos estarán entre 0e 20inclusive.

La definición de "lista" aquí es flexible. Cualquier estructura que represente una colección de números está bien, siempre que tenga un orden fijo de elementos y permita repeticiones. No puede incluir ninguna información auxiliar, excepto su longitud.

La entrada puede tomarse como un argumento de función o mediante STDIN.

Salida

El número excluido más pequeño. Salida o imprimirlo.

Casos de prueba

[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
xnor
fuente
2
Restringir los números a un rango fijo hace que este problema sea aún más simple.
Martin Ender
@ MartinBüttner Si la matriz contiene todos los números 0a 20, la salida correcta es 21. Voy a añadir un caso de prueba. Sí, el rango fijo definitivamente lo hace más fácil, aunque todavía se podría usar sys.maxinto 2**64si no lo especifico.
xnor
No hay necesidad de ese caso de prueba. Dijiste que la entrada solo puede contener 21 elementos.
Martin Ender
@ MartinBüttner Derecha, poste de la cerca. Gracias.
xnor
1
@KevinFegan Sí, la salida máxima posible es 20. Mi comentario fue erróneo y creo que MartinBüttner escribió.
xnor

Respuestas:

11

Pyth , 6 bytes

h-U21Q

Ejecución de ejemplo

$ pyth -c h-U21Q <<< '[5, 4, 1, 5, 4, 8, 2, 1, 5, 4, 0, 7, 7]'
3

Cómo funciona

  U21   range(21)
     Q  eval(input())
 -U21Q  setwisedifference(range(21), eval(input))          # Pyth function. Preserves order.
h-U21Q  setwisedifference(range(21), eval(input))[0]
Dennis
fuente
Cuando el conjunto se convierte en lista, ¿está siempre en orden?
xnor
La diferencia establecida de Pyth conserva el orden del primer argumento ( range(21)), que está ordenado. (Esto también significa que la explicación no es del todo precisa. Pyth y Python 3 son bastante nuevos para mí).
Dennis
1
Para aclarar, -en Pyth es en realidad un filtro: filtra el primer argumento por ausencia del segundo argumento, luego lo convierte a la forma del primer argumento (cadena, lista o conjunto).
isaacg
Además, Dennis, debería ser h-U22Qasí, dará la salida correcta de 21 en la entrada que contiene el rango completo permitido.
isaacg
@isaacg: La longitud de la lista también está limitada a 20, por lo que no puede contener los 21 números del 0 al 20.
Dennis
6

CJam, 11 8 bytes

K),l~^1<

Cómo funciona:

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"

Entrada de muestra:

[1 0 7 6 3 11 15 1 9 2 3 1 5 2 3 4 6 8 1 18]

Salida:

10

Pruébalo en línea aquí

Optimizador
fuente
¿Qué tan alto van los números de un solo carácter en CJam?
xnor
@xnor Tristemente, 20 - sourceforge.net/p/cjam/wiki/Variables
Optimizer
¡Una elección afortunada!
xnor
5

J - 13 char

f=:0{i.@21&-.

Acciones muy simples en J, y por lo tanto muy difíciles de hacer más pequeñas.

i.@21crea una lista de 0 a 20 inclusive. -.realiza set-resta la entrada de esta lista. 0{toma el primer elemento de lo que queda, es decir, el número más pequeño. f=:define una función con nombre. En la 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

Desde el lanzamiento de J806 en noviembre de 2017, existe una nueva sintaxis que nos ahorra un byte al permitirnos usar i.@21la antigua (i.21)en este contexto.

Algoritmo de tiburón
fuente
¿Necesita f=:?
Esolanging Fruit
Desde noviembre de 2017 i.@21-.]ahorraría 1 byte.
FrownyFrog
4

Golfscript 7

~21,^0=

Una versión más golfizada de la respuesta de Peter Taylor. Wiki de la comunidad ya que no tengo el representante para comentar su publicación.

La diferencia es usar el tamaño máximo de lista conocido de la pregunta en lugar de la longitud +1 para guardar un personaje y soltar el $ irrelevante.

Pruébalo en línea

paradigma
fuente
1
Maldición Golfscript por guardar 1 carácter para no leer la entrada -_-
Optimizer
4

Burlesque - 9 bytes

20rzj\\<]

Toma información de stdin en el formato {7 6 5 5 1 2 2 4 2 0}

Explicado:

 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.

Prueba algunos ejemplos:

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

AndoDaan
fuente
1
Esto no puede dar ningún resultado en la entrada {0 1 2}, porque necesita rzuno más que el número más grande. Simplemente ir directamente a 20rzj\\<]solucionar esto y ahorra un char.
algorithmshark
@algorithmshark No hay forma de evitarlo, tienes mucha razón. Fijo. Y gracias.
AndoDaan
3

Bash + coreutils, 23 bytes

seq 0 20|egrep -vwm1 $1

Esto supone una entrada como una |lista separada (canalización). P.ej:

$ ./mex.sh "5|4|1|5|4|8|2|1|5|4|0|7|7"
3
$
Trauma digital
fuente
1
No creo que necesites "(...)"en el $1.
Dennis
1
Separado por tubería está bien, cumple con la condición de lista de la especificación.
xnor
2

Ruby, 32 bytes

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

Define una función fque se llamará con una matriz.

Martin Ender
fuente
¿Algún comentario del votante? ¿Me perdí alguna parte de la especificación?
Martin Ender
Lo dudo. Varias otras respuestas (incluida la mía) obtuvieron un voto negativo misterioso.
Greg Hewgill
@ipi pero lo hace ... en exactamente el mismo formato dado en los ejemplos en las publicaciones de desafío, por ejemplo f[[0, 1]](donde los corchetes externos son la sintaxis de invocación y los corchetes internos definen la matriz).
Martin Ender
¿Por qué necesitas el f=?
Esolanging Fruit
2

GolfScript ( 10 9 bytes)

~.,),^$0=

Toma la entrada de stdin en el formato [5 4 1 5 4 8 2 1 5 4 0 7 7].

Demostración en línea

Peter Taylor
fuente
¿No debería ;contarse antes de la cadena de entrada en el propio programa?
Optimizador
1
@Optimizer, eso es simular la entrada de stdin porque el sitio de GolfScript en línea no admite un campo de entrada separado.
Peter Taylor
2

Xojo, 55 bytes

dim x as int8
while a.indexOf(x)>-1
x=x+1
wend
return x
silverpie
fuente
2

Ruby, 22

x=->n{([*0..20]-n)[0]}

Explicación

  • La entrada se toma como argumento para una lambda. Se espera una Arrayde Integers.
  • La entrada se resta de la matriz [0,1,2..20].
  • Debido a que Array [0,1,2..20]está ordenado, el primer elemento debe ser el mex.
britishtea
fuente
Dulce, ese fue mi primer intento, pero no pude lograr que la desestructuración funcionara, no pensé en rodearlo con paréntesis. Por cierto, puede usar en 20lugar de 21, porque la entrada solo puede contener 20 elementos.
Martin Ender
2

Haskell, 30

f s=filter(`notElem`s)[0..]!!0

Esto funciona para listas de todos los tamaños y listas más allá de 20. Esto puede tener 15 bytes de longitud si se importa Data.List:

f s=[0..]\\s!!0
orgulloso Haskeller
fuente
2

Esquema - 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))))

No muy competitivo Pero me gusta escribir esquema :),

Aquí está el código sin golf:

(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)
     ))
  )
)
Cruncher
fuente
1

Python, 37 caracteres

f=lambda a:min(set(range(21))-set(a))
Greg Hewgill
fuente
Golpéame por un par de segundos. Por cierto, lo es range(21).
qwr
Esta parece ser la solución más corta. La solución recursiva f=lambda l,i=0:i in l and f(l,i+1)or ies un char más larga y la solución iterativa i=0;l=input()\nwhile i in l:i+=1\nprint ies dos caracteres más larga (no almacenar la entrada hace que se tome repetidamente). Sin el 20límite, creo que estos enfoques prevalecerían.
xnor
¿No podría ser esta una función anónima? Si pudiera, puede guardar 2 bytes.
Mega Man
1

C # - 64 caracteres

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

No siempre es el mejor lenguaje de golf, pero es fácil de escribir y entender :)

DLeh
fuente
1

Scala, 18 bytes

0 to 20 diff l min

l es una lista de 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
2xsaiko
fuente
1

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;}

Pruébalo en línea!

Monja permeable
fuente
1

Java 7, 69 66 bytes

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

-3 bytes gracias a @LeakyNun

Explicación:

No solo admite 0-20, sino también 0-2147483647 (que en realidad ahorra 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

Código de prueba:

Pruébalo aquí.

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)));
  }
}

Salida:

0
1
1
2
0
0
3
4
4
10
Kevin Cruijssen
fuente
Je, bibliotecas .
Leaky Nun
1
3 bytes de descuento
Leaky Nun
1

APL (Dyalog) , 19 bytes

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

Pruébalo en línea!

Probablemente me estoy perdiendo algo importante aquí. Golf en progreso ...

Kritixi Lithos
fuente
1

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

Si Prompt Xse le da una lista en lugar de un solo número, creará automáticamente una lista con nombre a la Xque se puede acceder ʟX.

Scott Milner
fuente
20 bytes usando Ans:Prompt X:0:While not(prod(ʟX-Ans:Ans+1:End:Ans
JosiahRyanW
1

Stax , 6 bytes

¢╔⌂♀╠▬

Ejecutar y depurarlo

Explicación

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
Multi
fuente
1

Jalea , 7 bytes

Otro enfoque. Se puede usar en una cadena con cualquier arity, y no necesita separador de cadena ni nada.

‘Ṭ;0i0’

Como se garantiza que la respuesta sea inferior a 256, esto también funciona:

Jalea , 5 bytes

⁹ḶḟµḢ

Pruébalo en línea!

usuario202729
fuente
1

Powershell, 28 bytes

for(;+$i-in$args){$i++}+$i

Script de prueba:

$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"
}

Salida:

True: 0
True: 1
True: 2
True: 0
True: 0
True: 3
True: 4
True: 4
True: 10

Explicación:

  • Incremente $imientras la $argsmatriz contiene el valor entero +$i.
  • Salida de un último valor entero +$i.
mazzy
fuente
1

MathGolf , 5 4 bytes

Jr,╓

Pruébalo en línea!

Esta solución está restringida solo al rango de 0 a 20, aunque puede ampliarse fácilmente aumentando el rango inicial.

Explicación:

Jr     Range from 0 to 20
  ,    Remove elements from the input list from this range
   ╓   Return the minimum element

Alternativamente, una solución de 5 bytes para todos los números:

Åï╧▲ï

Pruébalo en línea!

Explicación:

Å  ▲   Do while true
  ╧    Does the input contain
 ï     The index of the loop?
    ï  Push the number of iterations of the last loop
Jo King
fuente
Con los nuevos cambios que (con suerte) se están agregando a TIO hoy, hay una solución de 4 bytes para este problema. Está restringido a un límite superior definido en el código, pero como MathGolf tiene un literal de 1 byte para 10 ^ 8, no debería ser notable.
maxb
Esta fue la solución exacta que tenía (usé en Zlugar de Jporque era vago).
maxb
0

Perl - 34

Aquí hay una subrutina.

sub f{$_~~@_?1:return$_ for0..20}

Prueba con:

perl -e'print f(0,1,3,4,5,6,7); sub f{$_~~@_?1:return$_ for 0..20}'
hmatt1
fuente
0

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;}

Sin golf:

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;
}
Ypnypn
fuente
Produce -1para caso de prueba [].
OldCurmudgeon
0

Cobra - 50

def f(l)
    for n in 22,if n not in l,break
    print n
Οurous
fuente
0

Javascript, 74

i=-1;a=prompt().split(',');while(i<21&&a.indexOf(String(++i))>=0);alert(i)

Agradable y simple! Tenga en cuenta el bucle while vacío.

Sean Latham
fuente
0

JavaScript (E6) 35

Función recursiva, parámetro de matriz en entrada y devolución de mex. No limitado a 20

F=(l,i=0)=>~l.indexOf(i)?F(l,++i):i

Prueba en la consola FireFox / FireBug

;[[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)))

Salida

[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
edc65
fuente
0

PHP, 38 bytes

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

PHP, 39 bytes

<?for(;in_array($i++,$_GET););echo$i-1;
Jörg Hülsermann
fuente