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

Perl 6, 38 bytes

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

Try it

Answer 28

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)

Answer 29

MATL, 12 bytes

iFFvXu1Z)SdA

The input is 2-column matrix, where the first column is key and the second is value.

Try it online!

Explanation

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?

Answer 30

PHP, 49 bytes

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

Prints nothing for functions and n for non-functions.