Est-ce une fonction?

47

À l'aide d'une liste de (key, value)paires, déterminez si elle représente une fonction, ce qui signifie que chaque clé correspond à une valeur cohérente. En d'autres termes, chaque fois que deux entrées ont des clés égales, elles doivent également avoir des valeurs égales. Les entrées répétées sont OK.

Par exemple:

# 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)]

Entrée: une séquence ordonnée de (key, value)paires utilisant les chiffres 1 à 9. Vous pouvez ne pas avoir besoin d'un ordre particulier. Vous pouvez également utiliser la liste de clés et la liste de valeurs comme entrées séparées.

Sortie: Une valeur cohérente pour les fonctions et une valeur cohérente différente pour les non-fonctions.

Cas de test: Les 5 premières entrées sont des fonctions, les 5 dernières ne le sont pas.

[(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)]

Les voici sous forme de deux listes d’entrées:

[[(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)]]

Classement:

Afficher l'extrait de code

code-golf decision-problem Xnor
la source
fonction surjective?
Poke
@Poke Cela n'a pas besoin d'être surjectif.
xnor
L'entrée peut-elle être deux listes de longueur égale, une pour les clés, une pour les valeurs?
Les passe-temps de Calvin
2
Est-il acceptable que les (key,value)paires soient inversées, comme dans (value,key)? Je peux raser quelques octets de ma réponse si oui.
Ymbirtt
1
@ymbirtt Oui, vous pouvez avoir les paires dans l'un ou l'autre ordre.
xnor

Réponses:

37

Python 2 , 34 octets

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

Essayez-le en ligne!

Crée un dictionnaire et un ensemble à partir de l'entrée et compare leurs longueurs.
Les dictionnaires ne peuvent pas avoir de clés dupliquées, ainsi toutes les valeurs illégales (et répétées) sont supprimées.

Barre
la source
5
Python 3, 30 octets:lambda x:not dict(x).items()^x
Veedrac
21

Haskell, 36 octets

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

Essayez-le en ligne!

Boucle extérieure (-> (k,v)) et intérieure (-> (m,n)) sur les paires et à chaque fois que vous k==mcollectez la valeur de vérité de v==n. Vérifiez si tout est vrai.

nimi
la source
Tu es trop rapide! : /
mardi
18

Brachylog , 5 4 octets

dhᵐ≠

Essayez-le en ligne!

Programme complet. Autant que je sache, la raison pour laquelle cela bat la plupart des autres langues de golf est qu’il ≠est intégré à Brachylog, alors que la plupart des autres langues de golf ont besoin de la synthétiser.

Explication

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

En tant que programme complet, nous obtenons truesi l'assertion réussit ou falseéchoue.


la source
15

Pyth , 5 octets

Je suis assez content de celui-ci.

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

Essayez-le en ligne!

notjagan
la source
9

Rétine , 25 octets

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

Essayez-le en ligne!

Le format d'entrée est {k,v},{k,v},.... Imprime 0pour les fonctions et 1pour les non-fonctions. Je pourrais économiser deux octets en utilisant des sauts de ligne au lieu des virgules dans le format d'entrée, mais c'est foiré.

Martin Ender
la source
Je pense que cela peut être qualifié de "sérieux", du moins d'un point de vue technique.
FryAmTheEggman
8

Brachylog , 13 octets

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

Essayez-le en ligne!

Explication

¬{          }      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.
Fataliser
la source
Pouvez-vous expliquer comment Ċhᵐ=et Ċtᵐ≠travailler?
CalculatriceFeline
@CalculatorFeline Les lettres majuscules sont des noms de variables. Ċest une variable spéciale appelée Couple qui est toujours préconfigurée pour être une liste de deux éléments. ᵐest un métaprédicat qui applique le prédicat immédiatement précédent ( h - headou t - tailici) à chaque élément de l'entrée (ici, Ċ). =et ≠simple vérifie que leur entrée contient tous les éléments égaux / tous différents.
Fataliser
7

MATL , 8 octets

1Z?gs2<A

Les entrées sont: un tableau avec le values, suivi d'un tableau avec le keys.

La sortie est 1pour la fonction, 0sinon.

Essayez-le en ligne! . Ou vérifiez tous les cas de test .

Explication

1Z?

Construit une matrice clairsemée. Initialement toutes les entrées contiennent 0; et 1est ajouté à chaque entrée (i, j)où jet isont l’entrée key, les valuepaires.

g

La matrice est convertie en logique; c'est-à-dire que les entrées dépassant 1(correspondant aux doublons key, valuepaires) sont définies sur 1.

s

La somme de chaque colonne est calculée. C'est le nombre de values différents pour chacun key.

2<A

Une fonction aura toutes ces sommes inférieures à 2.

Luis Mendo
la source
6

R, 33 octets

Ceci est ma version pour R. Cela tire parti de la avefonction. J'ai autorisé les entrées vides en définissant des valeurs par défaut pour les paramètres key et value. aveproduit une moyenne des valeurs pour chacune des clés. Heureusement, les moyennes sont renvoyées dans le même ordre que les valeurs d'entrée. Une comparaison avec l'entrée indique par conséquent s'il existe des valeurs différentes. Renvoie TRUEs'il s'agit d'une fonction.

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

Essayez-le en ligne!

MickyT
la source
6

05AB1E , 11 9 7 octets

2 octets sauvés grâce à kalsowerus .

Ùø¬DÙQ,

Essayez-le en ligne!

Explication

Ù           # 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
la source
@ Riley: Oui. Je suis toujours assez heureux que le cas particulier ne représente qu'un tiers du programme: P
Emigna
Je pense que vous pourriez économiser 3 octets en remplaçant `\)^par head ( ¬): TIO
kalsowerus
@kalsowerus: Malheureusement, cela casse pour le cas particulier de []:(
Emigna
@ Enigma Oh, cela a fonctionné, car lors des tests, il me restait un reste ,à la fin. Ajoutez cela et cela fonctionne d'une manière ou d'une autre avec [].
Kalsowerus
Mise à jour de TIO
kalsowerus
5

JavaScript (ES6), 45 38 octets

Enregistré 6 octets grâce à @Neil

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

Retourne falseou truepour les fonctions et les non-fonctions, respectivement.

Cela fonctionne en soustrayant constamment l'ancienne valeur de chaque fonction ( m[k]) et la nouvelle ( m[k]=vqui stocke également la nouvelle valeur). À chaque fois, il y a trois cas:

  • S'il n'y avait pas d'ancienne valeur, m[k]retourne undefined. Soustraire quoi que ce soit des undefinedrésultats NaN, ce qui est de la fausseté.
  • Si l'ancienne valeur est identique à la nouvelle, le m[k]-vrésultat 0est fausseté.
  • Si l'ancienne valeur est différente de la nouvelle, le m[k]-vrésultat est un entier non nul, ce qui est la vérité.

Par conséquent, nous devons simplement nous assurer que ce m[k]-(m[k]=v)n’est jamais la vérité.

ETHproductions
la source
1
Beaucoup trop long. Utilisez a=>!a.some(([x,y])=>m[x]-(m[x]=y),m=[]).
Neil
@Neil Dang, je savais qu'il devait y avoir un moyen d'utiliser le fait d' m[k]être indéfini ... Merci!
ETHproductions
5

Mathematica, 24 octets

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

Explication: Unionsupprime les paires dupliquées, puis#&@@@ récupère le premier élément de chaque paire (comme First/@avec moins d'octets). S'il y a une répétition dans ces premiers éléments, les paires ne font pas une fonction, nous vérifions avec UnsameQ.

(Cela pourrait avoir la plus grande densité de @caractères dans n'importe quel programme que j'ai écrit…)

Pas un arbre
la source
2
@densité = 1/4
CalculatorFeline
5

R, 36 33 octets

function(k,v)any(v[match(k,k)]-v)

Essayez-le en ligne!

fonction anonyme; retourne FALSEpour les fonctions etTRUE pour pas.

Ceci est en train d'être battu par est finalement lié à la réponse de MickyT! !

Giuseppe
la source
4

Bash + coreutils, 17

sort -u|uniq -dw1

L'entrée est donnée via STDIN. keyet valuesont Tabséparés et chaque paire est délimitée par des lignes.

sortsupprime les paires clé-valeur en double. uniq -dne génère que des doublons, ainsi la chaîne vide dans le cas d'une fonction et une chaîne non vide dans le cas contraire - lorsqu'il existe des clés en double mappées sur des valeurs différentes.

Essayez-le en ligne .

Trauma numérique
la source
4

05AB1E , 9 octets

Code:

ãü-ʒ¬_}}Ë

Explication:

ã            # 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

Utilise le codage 05AB1E . Essayez-le en ligne!

Adnan
la source
ʒJe commence à me montrer tout de suite :)
Emigna
@ Emigna Yeah haha: p, mais j'ai déjà trouvé un bug qui me fait utiliser à la }}place de }.
Adnan
4

Gelée , 6 octets

QḢ€µQ⁼

Essayez-le en ligne!

Explication

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.

Voici une autre méthode, également 6 octets:

QḢ€ṢIẠ

Essayez-le en ligne!

Au lieu de tester en supprimant les clés en double, cela trie ( Ṣ) et vérifie si la différence entre terms ( I) est tout à fait vraie ( Ạ)

fireflame241
la source
4

R , 95 66 octets

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

Enregistrement de 29 octets grâce à Jarko Dubbeldam.

Fonction anonyme. Sorties FALSEsi une fonction et TRUEsinon (désolé). Prend comme arguments une liste de clés et une liste de valeurs, comme ceci.

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

Parcourt toutes les clés et saisit la longueur de l'ensemble de valeurs uniques pour cette clé. Si anyelles sont> 1, renvoyerTRUE .

Ceci est battu par la réponse de MickyT , ainsi que par celle de Giuseppe . upvote un de ceux.

BLT
la source
Pourquoi créez-vous un cadre de données, pour ensuite référencer les vecteurs que vous venez de placer dans ce cadre de données? function(k=0,v=0)any(sapply(k,function(x){length(unique(v[k==x]))-1}))devrait accomplir la même chose.
JAD
Parce que j'apprends encore! Au moins une des autres réponses R le fait plus ou moins comme vous le décrivez.
BLT
désolé si je suis un peu dur :) votre soumission est un peu différente des autres réponses R, et si vous supprimiez le data.frame redondant, vous pourriez peut-être mieux comparer.
JAD
4

J-uby , 48 33 25 21 octets

-3 octets grâce à Jordan! 

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

Explication

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

Première approche, 33 octets

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

Celui-ci est plus long que la solution équivalente Ruby, mais c'était amusant à faire.

Tentative d'explication en se transformant en 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 }

Je pourrais économiser 2 octets avec une version plus récente en remplaçant :uniqpar~:|

Cyoce
la source
3

V , 30 octets

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

Essayez-le en ligne!

Sorties 1pour les fonctions et rien pour les non-fonctions.

DJMcMayhem
la source
3

Mathematica, 35 octets

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

Fonction pure prenant une liste de paires ordonnées comme entrée et retournant Trueou False. Exploite le fait que Union@#supprime les paires ordonnées répétées, mais <|Rule@@@#|>qu'une association supprime toutes les paires ordonnées sauf une avec un premier élément particulier. Nous pouvons donc simplement comparer les Lengths des deux sorties pour vérifier si la liste des entrées est une fonction.

Greg Martin
la source
3

Gelée , 6 octets

nþ`ḄCȦ

Essayez-le en ligne!

Comment ça fonctionne

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
la source
3

CJam , 19 17 octets

2 octets sauvés grâce à Martin Ender

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

Sorties 0pour les fonctions et 1pour les non-fonctions.

Essayez-le en ligne!

Explication

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)
Chat d'affaires
la source
3

APL (Dyalog) , 16 12 11 9 octets

(∪≡⊢)⊃¨∘∪

Essayez-le en ligne!

Explication

∪             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 0pour faux et 1pour vrai

Kritixi Lithos
la source
Whoa, tu deviens vraiment bien.
Adám
3

En fait , 4 octets

╔♂F═

Essayez-le en ligne!

Explication:

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

brainfuck , 71 octets

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

Essayez-le en ligne!

L'entrée est considérée comme une chaîne plate: par exemple, le premier cas de test serait 35356444. Pour obtenir la représentation indiquée dans la question initiale, ajoutez simplement un total de six virgules au programme aux bons endroits.

La sortie est Upour les fonctions et Vpour les non-fonctions.

Explication

Pour tout code ASCII, le point n, f (n) est stocké dans la cellule 2n + 1. Les cellules 2n et 2n + 2 sont des espaces de travail et 0, 2, 4, 6, ... 2n-2 sont une piste de chapelure pour revenir à la cellule 0. Lorsqu'il est prouvé que l'entrée n'est pas une fonction, f ( 0) est réglé sur 1 (parmi divers effets secondaires).

,                  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
la source
2

Pyth - 9 8 octets

ql.d{Ql{

L'essayer

Cela fonctionne en supprimant d’abord les paires répétées ({Q); puis il compare la longueur de la liste à la longueur d'un dictionnaire créé à partir de la liste (si la même valeur x apparaît plusieurs fois, le constructeur du dictionnaire n'utilise que le dernier, ce qui fait que le dictionnaire est plus court que la liste)

Maria
la source
2

MATL , 12 octets

iFFvXu1Z)SdA

L'entrée est une matrice à 2 colonnes, où la première colonne est la clé et la seconde est la valeur.

Essayez-le en ligne!

Explication

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
la source
2

PHP, 49 octets

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

N'imprime rien pour les fonctions et npour les non-fonctions.

utilisateur63956
la source
1

CJam , 14 11 9 octets

_&0f=__&=

Essayez-le en ligne!

Prend l'entrée en tant que tableau de paires clé / valeur sur la pile, retourne 1si l'entrée est une fonction et 0si ce n'est pas le cas.

Cette solution est basée sur l'extrait de code _&, qui dédoublonne un tableau en prenant l'intersection définie de celui-ci avec lui-même. Je le fais deux fois, d'abord sur l'entrée complète (pour supprimer toute paire clé / valeur exactement dupliquée), puis sur les clés uniquement (pour voir s'il reste des clés en double après la première déduplication).

Voici le code complet avec des commentaires:

_&           "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
la source
Pour votre information, e#voici la syntaxe de commentaire de ligne dédiée dans CJam.
Fruit d'Esolanging
1

Ruby, 39 30 29 octets

Merci à @ValueInk d' avoir économisé 9 octets!

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

Réponse du port de @ Rod's Python 2 .

Cyoce
la source
Hash[x]fonctionne aussi bien tbh
Value Ink
@ValueInk merci. Je ne sais pas pourquoi je n'y ai pas pensé.
Cyoce