Is this a function?

Question

Given a list of (key, value) pairs, determine whether it represents a function, meaning that each key maps to a consistent value. In other words, whenever two entries have equal keys, they must also have equal values. Repeated entries are OK.

For example:

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

Input: An ordered sequence of (key, value) pairs using digits 1 to 9. You may not require a particular ordering. You may alternatively take the key list and value list as separate inputs.

Output: A consistent value for functions, and a different consistent value for non-functions.

Test cases: The first 5 inputs are functions, the last 5 are not.

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

Here they are as two lists of inputs:

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

---

Leaderboard:

var QUESTION_ID=118960,OVERRIDE_USER=20260;function answersUrl(e){return"https://api.stackexchange.com/2.2/questions/118960/answers?page="+e+"&pagesize=100&order=desc&sort=creation&site=codegolf&filter="+ANSWER_FILTER}function commentUrl(e,s){return"https://api.stackexchange.com/2.2/answers/"+s.join(";")+"/comments?page="+e+"&pagesize=100&order=desc&sort=creation&site=codegolf&filter="+COMMENT_FILTER}function getAnswers(){jQuery.ajax({url:answersUrl(answer_page++),method:"get",dataType:"jsonp",crossDomain:!0,success:function(e){answers.push.apply(answers,e.items),answers_hash=[],answer_ids=[],e.items.forEach(function(e){e.comments=[];var s=+e.share_link.match(/\d+/);answer_ids.push(s),answers_hash[s]=e}),e.has_more||(more_answers=!1),comment_page=1,getComments()}})}function getComments(){jQuery.ajax({url:commentUrl(comment_page++,answer_ids),method:"get",dataType:"jsonp",crossDomain:!0,success:function(e){e.items.forEach(function(e){e.owner.user_id===OVERRIDE_USER&&answers_hash[e.post_id].comments.push(e)}),e.has_more?getComments():more_answers?getAnswers():process()}})}function getAuthorName(e){return e.owner.display_name}function process(){var e=[];answers.forEach(function(s){var r=s.body;s.comments.forEach(function(e){OVERRIDE_REG.test(e.body)&&(r="<h1>"+e.body.replace(OVERRIDE_REG,"")+"</h1>")});var a=r.match(SCORE_REG);a&&e.push({user:getAuthorName(s),size:+a[2],language:a[1],link:s.share_link})}),e.sort(function(e,s){var r=e.size,a=s.size;return r-a});var s={},r=1,a=null,n=1;e.forEach(function(e){e.size!=a&&(n=r),a=e.size,++r;var t=jQuery("#answer-template").html();t=t.replace("{{PLACE}}",n+".").replace("{{NAME}}",e.user).replace("{{LANGUAGE}}",e.language).replace("{{SIZE}}",e.size).replace("{{LINK}}",e.link),t=jQuery(t),jQuery("#answers").append(t);var o=e.language;/<a/.test(o)&&(o=jQuery(o).text()),s[o]=s[o]||{lang:e.language,user:e.user,size:e.size,link:e.link}});var t=[];for(var o in s)s.hasOwnProperty(o)&&t.push(s[o]);t.sort(function(e,s){return e.lang>s.lang?1:e.lang<s.lang?-1:0});for(var c=0;c<t.length;++c){var i=jQuery("#language-template").html(),o=t[c];i=i.replace("{{LANGUAGE}}",o.lang).replace("{{NAME}}",o.user).replace("{{SIZE}}",o.size).replace("{{LINK}}",o.link),i=jQuery(i),jQuery("#languages").append(i)}}var ANSWER_FILTER="!t)IWYnsLAZle2tQ3KqrVveCRJfxcRLe",COMMENT_FILTER="!)Q2B_A2kjfAiU78X(md6BoYk",answers=[],answers_hash,answer_ids,answer_page=1,more_answers=!0,comment_page;getAnswers();var SCORE_REG=/<h\d>\s*([^\n,]*[^\s,]),.*?(\d+)(?=[^\n\d<>]*(?:<(?:s>[^\n<>]*<\/s>|[^\n<>]+>)[^\n\d<>]*)*<\/h\d>)/,OVERRIDE_REG=/^Override\s*header:\s*/i;

body{text-align:left!important}#answer-list,#language-list{padding:10px;width:290px;float:left}table thead{font-weight:700}table td{padding:5px}

<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script> <link rel="stylesheet" type="text/css" href="//cdn.sstatic.net/codegolf/all.css?v=83c949450c8b"> <div id="answer-list"> <h2>Leaderboard</h2> <table class="answer-list"> <thead> <tr><td></td><td>Author</td><td>Language</td><td>Size</td></tr></thead> <tbody id="answers"> </tbody> </table> </div><div id="language-list"> <h2>Winners by Language</h2> <table class="language-list"> <thead> <tr><td>Language</td><td>User</td><td>Score</td></tr></thead> <tbody id="languages"> </tbody> </table> </div><table style="display: none"> <tbody id="answer-template"> <tr><td>{{PLACE}}</td><td>{{NAME}}</td><td>{{LANGUAGE}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr></tbody> </table> <table style="display: none"> <tbody id="language-template"> <tr><td>{{LANGUAGE}}</td><td>{{NAME}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr></tbody> </table>

Answer 1

Python 2, 34 bytes

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

Try it online!

Creates a Dictionary and a Set from the input and compare their lengths.
Dictionaries can't have duplicated keys, so all the illegal (and repeated) values are removed.

Answer 2

Haskell, 36 bytes

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

Try it online!

Outer (->(k,v)) and inner (-> (m,n)) loop over the pairs and whenever k==m, collect the truth value of v==n. Check if all are true.

Answer 3

Brachylog, 5 4 bytes

dhᵐ≠

Try it online!

Full program. As far as I can tell, the reason that this is beating most other golfing languages is that ≠ is a builtin in Brachylog, whereas most of the other golfing languages need to synthesize it.

Explanation

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

As a full program, we get true if the assertion succeeds, or false if it fails.

Answer 4

Pyth, 5 bytes

I'm pretty happy with this one.

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

Try it online!

Answer 5

Retina, 25 bytes

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

Try it online!

Input format is {k,v},{k,v},.... Prints 0 for functions and 1 for non-functions. I could save two bytes by using linefeeds instead of the commas in the input format, but that's messed up.

Answer 6

Brachylog, 13 bytes

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

Try it online!

Explanation

¬{          }      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.

Answer 7

MATL, 8 bytes

1Z?gs2<A

Inputs are: an array with the values, followed by an array with the keys.

Output is 1 for function, 0 otherswise.

Try it online!. Or verify all test cases.

Explanation

1Z?

Builds a sparse matrix. Initially all entries contain 0; and 1 is added to each entry (i, j) where j and i are the input key, value pairs.

g

The matrix is converted to logical; that is, entries exceeding 1 (corresponding to duplicate key, value pairs) are set to 1.

s

The sum of each column is computed. This is the number of different values for each key.

2<A

A function will have all such sums less than 2.

Answer 8

05AB1E, 11 9 7 bytes

Saved 2 bytes thanks to kalsowerus.

Ùø¬DÙQ,

Try it online!

Explanation

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

Answer 9

R, 33 bytes

This is my version for R. This takes advantage of the ave function. I have allowed for empty input by setting defaults on the key and value parameters. ave is producing a mean of the values for each of the keys. Fortunately this returns the means in the same order as the input values, so a comparison to the input will indicate if there is different values. Returns TRUE if it is a function.

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

Try it online!

Answer 10

JavaScript (ES6), 45 38 bytes

Saved 6 bytes thanks to @Neil

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

Returns false or true for functions and non-functions, respectively.

This works by constantly subtracting the old value of each function (m[k]) and the new one (m[k]=v, which also stores the new value). Each time, there are three cases:

• If there was no old value, m[k] returns undefined. Subtracting anything from undefined results in NaN, which is falsy.
• If the old value is the same as the new one, m[k]-v results in 0, which is falsy.
• If the old value is different from the new one, m[k]-v results in a non-zero integer, which is truthy.

Therefore, we just have to make sure that m[k]-(m[k]=v) is never truthy.

Answer 11

Mathematica, 24 bytes

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

Explanation: Union deletes duplicated pairs, then #&@@@ gets the first element from each pair (like First/@ but with fewer bytes). If there is any repetition in these first elements, the pairs don't make a function, which we check with UnsameQ.

(This might have the highest density of @ characters in any program I've written…)

Answer 12

J-uby, 48 33 25 21 bytes

-3 bytes thanks to Jordan!

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

Explanation

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

First Approach, 33 bytes

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

This one is longer than the equivalent Ruby solution, but it was fun to make.

Attempt of explanation by transforming to 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 }                             

I could save 2 bytes with a newer version by replacing :uniq with ~:|

Answer 13

Bash + coreutils, 17

sort -u|uniq -dw1

Input is given via STDIN. key and value are Tab separated and each pair is newline-delimited.

sort removes the duplicate key-value pairs. uniq -d only outputs duplicates, and so outputs the empty string in the case of a function, and a non-empty string otherwise - when there are duplicate keys that map to different values.

Try it online.

Answer 14

05AB1E, 9 bytes

Code:

ãü-ʒ¬_}}Ë

Explanation:

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

Uses the 05AB1E encoding. Try it online!

Answer 15

Jelly, 6 bytes

nþ`ḄCȦ

Try it online!

How it works

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.

Answer 16

Jelly, 6 bytes

QḢ€µQ⁼

Try it online!

Explanation

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.

Here is an alternate method, also 6 bytes:

QḢ€ṢIẠ

Try it online!

Instead of testing with removing duplicate keys, this sorts (Ṣ) and checks if the difference between terms (I) is all truthy (Ạ)

Answer 17

Actually, 4 bytes

╔♂F═

Try it online!

Explanation:

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

Answer 18

R, 36 33 bytes

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

Try it online!

anonymous function; returns FALSE for functions and TRUE for not.

This is being beaten by is finally tied with MickyT's answer!!

Answer 19

K (ngn/k), 11 bytes

{r~?r:*'?x}

Try it online!

Port of chunes' factor answer.

Explanation

{r~?r:*'?x}

{         }     /function
        ?x      /distinct values
      *'        /first value of each
    r:          /store in r
 r~?            /is distinct?

Answer 20

V, 30 bytes

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

Try it online!

Outputs 1 for functions and nothing for non-functions.

Answer 21

Mathematica, 35 bytes

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

Pure function taking a list of ordered pairs as input and returning True or False. Exploits the fact that Union@# deletes repeated ordered pairs, but <|Rule@@@#|> (an association) deletes all but one ordered pair with a particular first element. So we can just compare the Lengths of the two outputs to check whether the input list is a function.

Answer 22

CJam, 19 17 bytes

Saved 2 bytes thanks to Martin Ender

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

Outputs 0 for functions and 1 for non-functions.

Try it online!

Explanation

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)

Answer 23

APL (Dyalog), 16 12 11 9 bytes

(∪≡⊢)⊃¨∘∪

Try it online!

Explanation

∪             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

Prints 0 for false and 1 for true

Answer 24

R, 95 66 bytes

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

Saved 29 bytes thanks to Jarko Dubbeldam.

Anonymous function. Outputs FALSE if a function and TRUE if not (sorry). Takes as arguments a list of keys and a list of values, like so.

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

Loops through all keys and grabs the length of the set of unique values for that key. If any of them are > 1, return TRUE.

This is being beaten by MickyT's answer, and also Giuseppe's. upvote one of those.

Answer 25

brainfuck, 71 bytes

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

Try it online!

Input is taken as a flat string: for instance, the first test case would be 35356444. To get the representation shown in the original question, simply add a total of six commas to the program at the right points.

Output is U for functions and V for non-functions.

Explanation

For any ASCII code point n, f(n) is stored at cell 2n+1. Cells 2n and 2n+2 are working space, and 0, 2, 4, 6, ... 2n-2 are a trail of breadcrumbs to lead back to cell 0. When the input is proven not to be a function, f(0) is set to 1 (among various side effects).

,                  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

Answer 26

Desmos, 46 bytes

U=L.unique
f(L)=0^{U.length-U.x.unique.length}

Function returning 1 for functions and 0 for non-functions.

Equivalent, but slightly longer:

f(L)=0^{L.unique.length-L.unique.x.unique.length}

Try it on Desmos!

Answer 27

Factor, 28 bytes

[ members keys all-unique? ]

Try it online!

• members Get the unique elements
• keys Get the keys of an associative array as a sequence
• all-unique? Are they all unique?

             ! { { 1 2 } { 2 1 } { 5 2 } { 1 2 } { 2 5 } }
members      ! { { 1 2 } { 2 1 } { 5 2 } { 2 5 } }
keys         ! { 1 2 5 2 }
all-unique?  ! f

Answer 28

Julia, 14 bytes

!x=x⊆Dict(x)

Attempt This Online!

Answer 29

Perl 6, 38 bytes

!*.unique(:as(~*)).repeated(:as(*[0]))

Try it

Answer 30

Pyth - 9 8 bytes

ql.d{Ql{

Try it

It works by removing any repeated pairs first ({Q); then it compares the length of the list to the length of a dictionary created from the list (if the same x value occurs more than once, the dictionary constructor uses only the last one, resulting in the dictionary being shorter than the list)