¿Es esta una función?

47

Dada una lista de (key, value)pares, determine si representa una función, lo que significa que cada tecla se asigna a un valor consistente. En otras palabras, siempre que dos entradas tengan claves iguales, también deben tener valores iguales. Las entradas repetidas están bien.

Por ejemplo:

# Not a function: 3 maps to both 1 and 6
[(3,1), (2,5), (3,6)]

# Function: It's OK that (3,5) is listed twice, and that both 6 and 4 both map to 4
[(3,5), (3,5), (6,4), (4,4)]

Entrada: una secuencia ordenada de (key, value)pares usando los dígitos del 1 al 9. Es posible que no requiera un pedido particular. Alternativamente, puede tomar la lista de claves y la lista de valores como entradas separadas.

Salida: un valor coherente para funciones y un valor coherente diferente para no funciones.

Casos de prueba: las primeras 5 entradas son funciones, las últimas 5 no lo son.

[(3, 5), (3, 5), (6, 4), (4, 4)]
[(9, 4), (1, 4), (2, 4)]
[]
[(1, 1)]
[(1, 2), (2, 1)]

[(3, 1), (2, 5), (3, 6)]
[(1, 2), (2, 1), (5, 2), (1, 2), (2, 5)]
[(8, 8), (8, 8), (8, 9), (8, 9)]
[(1, 2), (1, 3), (1, 4)]
[(1, 2), (1, 3), (2, 3), (2, 4)]

Aquí están como dos listas de entradas:

[[(3, 5), (3, 5), (6, 4), (4, 4)], [(9, 4), (1, 4), (2, 4)], [], [(1, 1)], [(1, 2), (2, 1)]]
[[(3, 1), (2, 5), (3, 6)], [(1, 2), (2, 1), (5, 2), (1, 2), (2, 5)], [(8, 8), (8, 8), (8, 9), (8, 9)], [(1, 2), (1, 3), (1, 4)], [(1, 2), (1, 3), (2, 3), (2, 4)]]

Tabla de clasificación:

Mostrar fragmento de código

code-golf decision-problem xnor
fuente
función surjective?
Poke
@Poke No tiene que ser sobreyectivo.
xnor
¿Podría la entrada ser dos listas de igual longitud, una para las claves y otra para los valores?
Hobbies de Calvin
2
¿Está bien que los (key,value)pares se inviertan, como en (value,key)? Puedo eliminar algunos bytes de mi respuesta si es así.
ymbirtt
1
@ymbirtt Sí, puede hacer que los pares estén en cualquier orden.
xnor

Respuestas:

37

Python 2 , 34 bytes

lambda x:len(dict(x))==len(set(x))

Pruébalo en línea!

Crea un Diccionario y un Conjunto a partir de la entrada y compara sus longitudes.
Los diccionarios no pueden tener claves duplicadas, por lo que se eliminan todos los valores ilegales (y repetidos).

varilla
fuente
55
Python 3, 30 bytes:lambda x:not dict(x).items()^x
Veedrac
21

Haskell, 36 bytes

f x=and[v==n|(k,v)<-x,(m,n)<-x,k==m]

Pruébalo en línea!

El bucle externo (-> (k,v)) y el interno (-> (m,n)) sobre los pares y siempre que sea k==m, recojan el valor de verdad de v==n. Comprueba si todo es verdad.

nimi
fuente
Eres muy rápido! : /
flawr
18

Brachylog , 5 4 bytes

dhᵐ≠

Pruébalo en línea!

Programa completo Por lo que puedo decir, la razón por la que esto está superando a la mayoría de los otros idiomas de golf es que ≠está incluido en Brachylog, mientras que la mayoría de los otros idiomas de golf necesitan sintetizarlo.

Explicación

dhᵐ≠
d     On the list of all unique elements of {the input},
 h    take the first element
  ᵐ     of each of those elements
   ≠  and assert that all those elements are different

Como programa completo, obtenemos truesi la afirmación tiene éxito o falsesi falla.


fuente
15

Pyth , 5 bytes

Estoy bastante feliz con este.

{IhM{
       implicit input
    {  removes duplicate pairs
  hM   first element of each pair
{I     checks invariance over deduplication (i.e. checks if no duplicates)

Pruébalo en línea!

notjagan
fuente
9

Retina , 25 bytes

1`({\d+,)(\d+}).*\1(?!\2)

Pruébalo en línea!

El formato de entrada es {k,v},{k,v},.... Imprime 0para funciones y 1para no funciones. Podría guardar dos bytes usando saltos de línea en lugar de las comas en el formato de entrada, pero eso está mal.

Martin Ender
fuente
Creo que califica como "seriamente loco", al menos desde un punto de vista técnico.
FryAmTheEggman
8

Brachylog , 13 bytes

¬{⊇Ċhᵐ=∧Ċtᵐ≠}

Pruébalo en línea!

Explicación

¬{          }      It is impossible...
  ⊇Ċ               ...to find a subset of length 2 of the input...
   Ċhᵐ=            ...for which both elements have the same head...
       ∧           ...and...
        Ċtᵐ≠       ...have different tails.
Fatalizar
fuente
¿Puedes explicar cómo Ċhᵐ=y Ċtᵐ≠trabajar?
CalculatorFeline
@CalculatorFeline Las letras mayúsculas son nombres de variables. Ċes una variable especial llamada Pareja que siempre está precontratada para ser una lista de dos elementos. ᵐes un metapredicado que aplica el predicado inmediatamente anterior ( h - heado t - tailaquí) a cada elemento de la entrada (aquí, Ċ). =y ≠simplifique que su entrada contenga todos los elementos iguales / diferentes.
Fatalize
7

MATL , 8 bytes

1Z?gs2<A

Las entradas son: una matriz con la values, seguida de una matriz con la keys.

La salida es 1para la función, de lo 0contrario.

Pruébalo en línea! . O verificar todos los casos de prueba .

Explicación

1Z?

Construye una matriz dispersa. Inicialmente todas las entradas contienen 0; y 1se agrega a cada entrada (i, j)donde jy ison la entrada key, valuepares.

g

La matriz se convierte en lógica; es decir, las entradas superior 1(correspondiente a duplicar key, valuepares) se establecen a 1.

s

Se calcula la suma de cada columna. Este es el número de diferentes values para cada uno key.

2<A

Una función tendrá todas esas sumas menos que 2.

Luis Mendo
fuente
6

R, 33 bytes

Esta es mi versión para R. Esto aprovecha la avefunción. He permitido la entrada vacía al establecer valores predeterminados en los parámetros clave y de valor. aveestá produciendo una media de los valores para cada una de las claves. Afortunadamente, esto devuelve las medias en el mismo orden que los valores de entrada, por lo que una comparación con la entrada indicará si hay valores diferentes. Devuelve TRUEsi es una función.

function(k=0,v=0)all(ave(v,k)==v)

Pruébalo en línea!

MickyT
fuente
6

05AB1E , 11 9 7 bytes

Guardado 2 bytes gracias a kalsowerus .

Ùø¬DÙQ,

Pruébalo en línea!

Explicación

Ù           # remove duplicates
 ø          # zip
  ¬         # get the first element of the list (keys)
   D        # duplicate list of keys
    Ù       # remove duplicates in the copy
     Q      # compare for equality
      ,     # explicitly print result
Emigna
fuente
@Riley: Sí. Todavía estoy bastante contento de que el caso especial solo haya terminado un tercio del programa: P
Emigna
Creo que podría ahorrar 3 bytes reemplazando `\)^con head ( ¬): TIO
kalsowerus
@kalsowerus: Desafortunadamente eso se rompe para el caso especial de []:(
Emigna
@ Enigma Oh, funcionó porque al probar todavía me quedaban restos ,al final. Agregue eso y luego de alguna manera funciona [].
kalsowerus
TIO
kalsowerus
5

JavaScript (ES6), 45 38 bytes

Guardado 6 bytes gracias a @Neil

a=>a.some(([k,v])=>m[k]-(m[k]=v),m={})

Devuelve falseo truepara funciones y no funciones, respectivamente.

Esto funciona restando constantemente el valor anterior de cada función ( m[k]) y la nueva ( m[k]=vque también almacena el nuevo valor). Cada vez, hay tres casos:

  • Si no había un valor antiguo, m[k]devuelve undefined. Restando cualquier cosa de los undefinedresultados NaN, lo cual es falso.
  • Si el valor anterior es el mismo que el nuevo, m[k]-vda como resultado 0, lo cual es falso.
  • Si el valor anterior es diferente del nuevo, m[k]-vda como resultado un número entero distinto de cero, lo cual es verdadero.

Por lo tanto, solo tenemos que asegurarnos de que m[k]-(m[k]=v)nunca sea verdad.

ETHproducciones
fuente
1
Demasiado tiempo. Uso a=>!a.some(([x,y])=>m[x]-(m[x]=y),m=[]).
Neil
@Neil Dang it, sabía que tenía que haber alguna forma de utilizar m[k]ser indefinido ... ¡Gracias!
ETHproductions
5

Mathematica, 24 bytes

UnsameQ@@(#&@@@Union@#)&

Explicación: Unionelimina pares duplicados, luego #&@@@obtiene el primer elemento de cada par (como First/@pero con menos bytes). Si hay alguna repetición en estos primeros elementos, los pares no hacen una función, con lo que verificamos UnsameQ.

(Esto podría tener la mayor densidad de @caracteres en cualquier programa que haya escrito ...)

No un arbol
fuente
2
@densidad = 1/4
CalculatorFeline
4

Bash + coreutils, 17

sort -u|uniq -dw1

La entrada se proporciona a través de STDIN. keyy valueestán Tabseparados y cada par está delimitado por nueva línea.

sortelimina los pares duplicados de clave-valor. uniq -dsolo genera duplicados y, por lo tanto, genera la cadena vacía en el caso de una función y, de lo contrario, una cadena no vacía, cuando hay claves duplicadas que se asignan a valores diferentes.

Pruébalo en línea .

Trauma digital
fuente
4

05AB1E , 9 bytes

Código:

ãü-ʒ¬_}}Ë

Explicación:

ã            # Cartesian product with itself
 ü-          # Pairwise subtraction
   ʒ  }}     # Filter out elements where the following is not true:
    ¬_       #   Check whether the first digit is 0
        Ë    # Check if all equal

Utiliza la codificación 05AB1E . Pruébalo en línea!

Adnan
fuente
Llegar a presumir de ʒinmediato ya veo :)
Emigna
@Emigna Sí, jaja: p, pero ya encontré un error que hace que lo use en }}lugar de hacerlo }.
Adnan
4

Jalea , 6 bytes

QḢ€µQ⁼

Pruébalo en línea!

Explicación

QḢ€µQ⁼
Q      - Remove duplicate pairs
 Ḣ€    - Retrieve the first element of each pair
   µ   - On the output of what came before..
     ⁼ - Are the following two equal (bit returned)?
    Q  - The output with duplicates removed
       - (implicit) the output.

Aquí hay un método alternativo, también de 6 bytes:

QḢ€ṢIẠ

Pruébalo en línea!

En lugar de probar con la eliminación de claves duplicadas, esto ordena ( Ṣ) y comprueba si la diferencia entre los términos ( I) es verdadera ( Ạ)

fireflame241
fuente
4

R , 95 66 bytes

function(k,v)any(sapply(k,function(x){length(unique(v[k==x]))-1}))

Guardado 29 bytes gracias a Jarko Dubbeldam.

Función anónima. Salidas FALSEsi una función y TRUEsi no (lo siento). Toma como argumentos una lista de claves y una lista de valores, así.

> f(c(1,2,5,1,2),c(2,1,2,2,5))
[1] TRUE # not a function

Recorre todas las claves y toma la longitud del conjunto de valores únicos para esa clave. Si anyde ellos son> 1, regrese TRUE.

Esto está siendo superado por la respuesta de MickyT , y también por la de Giuseppe . Vota uno de esos.

BLT
fuente
¿Por qué está creando un marco de datos, solo para luego hacer referencia a los vectores que acaba de poner en ese marco de datos? function(k=0,v=0)any(sapply(k,function(x){length(unique(v[k==x]))-1}))Debería lograr lo mismo.
JAD
¡Porque todavía estoy aprendiendo! Al menos una de las otras respuestas R lo hace más o menos como usted describe.
BLT
lo siento si salí un poco duro :) su presentación es un poco diferente a las otras respuestas R, y si tuviera que cortar el marco de datos redundante, podría comparar mejor.
JAD
4

J-uby , 48 33 25 21 bytes

-3 bytes gracias a Jordan! 

:size*:==%[:to_h,~:|]

Explicación

:size*:==%[:to_h,~:|]

# "readable"
(:size * :==) % [:to_h, ~:|]

# transform :% to explicit lambda
->(x){ (:size * :==).(:to_h ^ x, ~:| ^ x)

# apply explicit x to functions
->(x){ (:size * :==).(x.to_h, x|x) }

# expand :* (map over arguments)
->(x){ :==.(:size.(x.to_h), :size.(x|x) }

# simplify symbol calls to method calls
->(x){ x.to_h.size == (x|x).size }

# :| is set union for arrays; x|x just removes duplicates, like :uniq but shorter
->(x){ x.to_h.size == x.uniq.size }

Primer enfoque, 33 bytes

-[:[]&Hash,:uniq]|:*&:size|:/&:==

Esta es más larga que la solución Ruby equivalente, pero fue divertido de hacer.

Intento de explicación transformando a Ruby:

-[:[]&Hash,:uniq]|:*&:size|:/&:==

# "readable"
-[:[] & Hash, :uniq] | (:* & :size) | (:/ & :==)                  

# turn into explicit lambda
->(x){ (:/ & :==) ^ ((:* & :size) ^ (-[:[] & Hash, :uniq] ^ x)) } 

# simplify expressions now that we have an explicit x
->(x){ :== / (:size * [Hash[x], x.uniq]) }                          

# translate to equivalent Ruby code
->(x) { [Hash[x], x.uniq].map(&:size).reduce(:==) }               

# simplify reduce over explicit array
->(x) { Hash[x].size == x.uniq.size }

Podría ahorrar 2 bytes con una versión más nueva reemplazando :uniqpor~:|

Cyoce
fuente
3

V , 30 bytes

Úç^¨.*©î±$/d
ÎwD
ç/HdG
Íî
Ò1lD

Pruébalo en línea!

Salidas 1para funciones y nada para no funciones.

DJMcMayhem
fuente
3

Mathematica, 35 bytes

(l=Length)@Union@#==l@<|Rule@@@#|>&

Función pura que toma una lista de pares ordenados como entrada y retorno Trueo False. Explota el hecho de que Union@#elimina pares ordenados repetidos, pero <|Rule@@@#|>(una asociación) elimina todos los pares ordenados menos uno con un primer elemento en particular. Por lo tanto, solo podemos comparar los Lengths de las dos salidas para verificar si la lista de entradas es una función.

Greg Martin
fuente
3

Jalea , 6 bytes

nþ`ḄCȦ

Pruébalo en línea!

Cómo funciona

nþ`ḄCȦ  Main link. Argument: M (n×2 matrix)

nþ`     Construct the table of (a != b, c != d) with (a, b) and (c, d) in M.
   Ḅ    Unbinary; map (0, 0), (0, 1), (1, 0), (1, 1) to 0, 1, 2, 3 (resp.).
    C   Complement; map each resulting integer x to 1 - x.
     Ȧ  All; test if all resulting integers are non-zero.
Dennis
fuente
3

CJam , 19 17 bytes

Guardado 2 bytes gracias a Martin Ender

0l~$2ew{:.=~!&|}/

Salidas 0para funciones y 1para no funciones.

Pruébalo en línea!

Explicación

0                     e# Push a 0. We need it for later.
 l~                   e# Read and eval a line of input.
   $                  e# Sort it by the keys.
    2ew               e# Get all consecutive pairs of the sorted list.
       {              e# For each pair of pairs:
        :.=           e#  Check if the keys are equal and if the values are equal.
           ~!&        e#  Determine if the keys are equal AND the values are not equal.
              |       e#  OR with 0. If any pair indicates that the input is not a function,
                      e#  this will become 1 (and remain 1), otherwise it will be 0.
               }/     e# (end block)
Gato de negocios
fuente
3

APL (Dyalog) , 16 12 11 9 bytes

(∪≡⊢)⊃¨∘∪

Pruébalo en línea!

Explicación

∪             Unique, remove duplicates; (3 5) (3 5) => (3 5)
¨∘            For each element
⊃             Pick the first sub element (3 5) (2 3) => 3 

 ≡            Check whether the arguments (listed below) are the same
  ⊢           The right argument
∪             And the right argument with duplicates removed

Imprime 0para falso y 1para verdadero

Kritixi Lithos
fuente
Whoa, te estás volviendo realmente bueno.
Adám
3

En realidad , 4 bytes

╔♂F═

Pruébalo en línea!

Explicación:

╔♂F═
╔     uniquify (remove duplicate pairs)
 ♂F   take first items in each pair (keys)
   ═  are all of the keys unique?
Mego
fuente
3

brainfuck , 71 bytes

,[[-[->>+<<]+>>],>[[->+<<->]<[<<]>]>[-<+>]<<[->+<]+[-<<]>>,]-[--->+<]>.

Pruébalo en línea!

La entrada se toma como una cadena plana: por ejemplo, el primer caso de prueba sería 35356444. Para obtener la representación que se muestra en la pregunta original, simplemente agregue un total de seis comas al programa en los puntos correctos.

La salida es Upara funciones y Vpara no funciones.

Explicación

Para cualquier punto de código ASCII n, f (n) se almacena en la celda 2n + 1. Las celdas 2n y 2n + 2 son espacio de trabajo, y 0, 2, 4, 6, ... 2n-2 son un rastro de migas de pan para conducir de regreso a la celda 0. Cuando se demuestra que la entrada no es una función, f ( 0) se establece en 1 (entre varios efectos secundarios).

,                  input first key
[                  start main loop
 [-[->>+<<]+>>]    move to cell 2n, leaving a trail of breadcrumbs
 ,                 input value corresponding to current key
 >[                if key already has a value:
   [->+<<->]<      copy existing value, and compare to new value
   [<<]            if values are different, go to cell -2
   >               go back to cell 2n+1 (or -1 if mismatch)
 ]
 >[-<+>]           move existing value back to cell 2n+1 (NOP if no existing value, move the 1 from cell 0 to cell -1 if mismatch)
 <<[->+<]          copy new value to cell 2n+1 (NOP if there was already a value)
 +[-<<]>>          follow breadcrumbs back to cell 0 (NOP if mismatch)
 ,                 input next key
]                  (if mismatch, cell -2 becomes the next "cell 0", and the next key is also effectively changed by the breadcrumbs left lying around)
-[--->+<]>.        add 85 to cell 1 and output the result
Nitrodon
fuente
2

Pyth - 9 8 bytes

ql.d{Ql{

Intentalo

Funciona eliminando los pares repetidos primero ({Q); luego compara la longitud de la lista con la longitud de un diccionario creado a partir de la lista (si el mismo valor x aparece más de una vez, el constructor del diccionario usa solo el último, lo que hace que el diccionario sea más corto que la lista)

Maria
fuente
2

MATL , 12 bytes

iFFvXu1Z)SdA

La entrada es matriz de 2 columnas, donde la primera columna es clave y la segunda es valor.

Pruébalo en línea!

Explicación

i     % Input: 2-column matrix
FFv   % Postpend a row with two zeros. This handles the empty case
Xu    % Unique rows. This removes duplicate (key, value) pairs
1Z)   % Select first column, that is, key. We need to check if all
      % keys surviving at this point are different
S     % Sort
d     % Consecutive differences
A     % Are all values nonzero?
Luis Mendo
fuente
2

PHP, 49 bytes

foreach($_GET as[$x,$y])($$x=$$x??$y)-$y&&die(n);

No imprime nada para funciones y npara no funciones.

usuario63956
fuente
1

CJam , 14 11 9 bytes

_&0f=__&=

Pruébalo en línea!

Toma la entrada como una matriz de pares clave / valor en la pila, devuelve 1si la entrada es una función y 0si no lo es.

Esta solución se basa en el fragmento _&, que elimina la duplicación de una matriz al tomar la intersección establecida con ella misma. Hago esto dos veces, primero en la entrada completa (para deshacerme de cualquier par clave / valor exactamente duplicado) y luego solo en las teclas (para ver si aún quedan claves duplicadas después de la primera desduplicación).

Aquí está el código completo con comentarios:

_&           "remove duplicate key/value pairs from input";
  0f=        "remove the values, leaving only the keys";
     _       "make a copy of the array of keys";
      _&     "remove duplicate keys from the copy";
        =    "compare the de-duplicated key array with the original";
Ilmari Karonen
fuente
Para que lo sepas, e#es la sintaxis de comentarios de línea dedicada en CJam.
Esolanging Fruit
1

Rubí, 39 30 29 bytes

¡Gracias a @ValueInk por guardar 9 bytes!

->x{Hash[x].size==(x|x).size}

Puerto de la respuesta de @ Rod's Python 2 .

Cyoce
fuente
Hash[x]funciona igual de bien tbh
Value Ink
@ValueInk gracias. No estoy seguro de por qué no pensé en eso.
Cyoce