56
\$\begingroup\$

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>

\$\endgroup\$
10
  • \$\begingroup\$ surjective function? \$\endgroup\$
    – Poke
    May 4, 2017 at 20:50
  • \$\begingroup\$ @Poke It doesn't have to be surjective. \$\endgroup\$
    – xnor
    May 4, 2017 at 20:54
  • \$\begingroup\$ Could the input be two lists of equal length, one for keys one for values? \$\endgroup\$ May 4, 2017 at 21:19
  • 2
    \$\begingroup\$ Is it OK for the (key,value) pairs to be reversed, as in (value,key)? I can shave a few bytes off my answer if so. \$\endgroup\$
    – ymbirtt
    May 6, 2017 at 9:41
  • 1
    \$\begingroup\$ @ymbirtt Yes, you can have the pairs be in either order. \$\endgroup\$
    – xnor
    May 6, 2017 at 18:22

51 Answers 51

1
2
2
\$\begingroup\$

JavaScript (ES6) from ETHproductions', 35 bytes

a=>a.some(([k,v])=>a[~k]-(a[~k]=v))
\$\endgroup\$
2
\$\begingroup\$

Jelly, 5 bytes

ĠịE€Ạ

Takes input as a list of keys and a list of values.

Try it online!

\$\endgroup\$
2
\$\begingroup\$

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
\$\endgroup\$
2
\$\begingroup\$

Julia, 14 bytes

!x=x⊆Dict(x)

Attempt This Online!

\$\endgroup\$
1
\$\begingroup\$

CJam, 14 11 9 bytes

_&0f=__&=

Try it online!

Takes input as an array of key/value pairs on the stack, returns 1 if the input is a function, and 0 if it's not.

This solution is based on the snippet _&, which de-duplicates an array by taking the set intersection of it with itself. I do this twice, first on the full input (to get rid of any exactly duplicated key/value pairs) and then on just the keys (to see if there are any duplicate keys still left after the first de-duplication).

Here's the full code with comments:

_&           "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";
\$\endgroup\$
1
  • \$\begingroup\$ Just so you know, e# is the dedicated line comment syntax in CJam. \$\endgroup\$ May 25, 2017 at 1:34
1
\$\begingroup\$

Ruby, 39 30 29 Bytes

Thanks to @ValueInk for saving 9 bytes!

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

Port of @Rod's Python 2 answer.

\$\endgroup\$
2
  • \$\begingroup\$ Hash[x] works just as well tbh \$\endgroup\$
    – Value Ink
    May 5, 2017 at 19:46
  • \$\begingroup\$ @ValueInk thanks. Not sure why I didn't think about that. \$\endgroup\$
    – Cyoce
    May 5, 2017 at 21:11
1
\$\begingroup\$

Ruby, 24 Bytes

->x{!x.uniq.uniq! &:pop}

Note that this only works if the points are given in [value, key] order, i.e. backwards. To be used like:

f = ->x{!x.uniq.uniq! &:pop}
p f.([[1,3], [5,2], [6,3]])
p f.([[5,3], [5,3], [4,6], [4,4]])

One of the funky quirks of uniq! is that it returns nil if no changes are made and the modified array if changes are made. If everything's already unique, you get a false-y value.

You asked for consistent values, so this gives a consistent true and false. If you're happy to just get a truthy value for one case and a falsey value for the other then we can save a byte by removing the first !.

\$\endgroup\$
1
\$\begingroup\$

Python 3, 32 30 29 bytes

Thanks MD XF for saving 2 bytes with a different approach, and xnor for another byte with yet another approach

lambda x:{*x}>dict(x).items()

Try it online!

Prints False for yes, True for no.

lambda x:not dict(x).items()^x

Try it online!

Also 30 bytes:

lambda x:not x-dict(x).items()

Try it online!

Alternatively (thanks xnor):

lambda x:{*x}<=dict(x).items()

Try it online!

\$\endgroup\$
5
  • \$\begingroup\$ Interesting, I did not expect dict(x).items() to allow set operations with a list. I think you can cut a byte with lambda x:{*x}>dict(x).items(). \$\endgroup\$
    – xnor
    May 31, 2017 at 18:58
  • \$\begingroup\$ @xnor That prints False instead of True and vice versa, I'm not sure if that's allowed, and <= doesn't save a byte \$\endgroup\$
    – ASCII-only
    May 31, 2017 at 22:02
  • \$\begingroup\$ @ASCII-only I'm allowing any consistent values for the two cases, based on feedback from this meta question. \$\endgroup\$
    – xnor
    Jun 1, 2017 at 0:12
  • \$\begingroup\$ @xnor well if set() is allowed as the only truthy value then I can just remove not \$\endgroup\$
    – ASCII-only
    Jun 1, 2017 at 0:20
  • \$\begingroup\$ @ASCII-only No, in this spec the yes-values need to be consistent and the no-values also need to be be consistent. \$\endgroup\$
    – xnor
    Jun 1, 2017 at 0:26
1
\$\begingroup\$

Husk, 5 bytes

S=ü←u

Try it online!

Explanation

S=ü←u  -- example input: [(3,5),(3,5),(6,4),(4,4)]
    u  -- remove duplicates: [(3,5),(6,4),(4,4)]
S      -- is it ..
 =     -- .. equal to it
  ü    -- | remove duplicates by
   ←   -- | | first element (key): [3,6,4]
       -- | : [(3,5),(6,4),(4,4)]
       -- : 1

Alternative, 5 bytes

This one might be cheating, since it assumes that the pairs are ordered by their keys which imo would make more sense:

ΛË→ġ←

Try it online!

Explanation

Note that all non-zero integers in Husk are truthy:

ΛË→ġ←  -- example input: [(3,5),(3,5),(6,4),(4,4)]
   ġ   -- group elements by
    ←  -- | first element (key): [3,3,6,4]
       -- : [[(3,5),(3,5)],[(6,4)],[(4,4)]]
Λ      -- do all elements satisfy
 Ë     -- | all elements equal by
  →    -- | | second element (value): [[5,5],[4],[4]]
       -- : [3,2,2]
       -- : 4
\$\endgroup\$
1
  • \$\begingroup\$ Swapping ġ (groups elements that are adjacent) for k (groups even non-adjacent elements) avoids the ordering restriction for the second one... \$\endgroup\$ May 3 at 7:33
1
\$\begingroup\$

GolfScript, 30 17 14 12 bytes

~.|{0=}%..|=

Try it online!

Outputs 1 for true, 0 for false.

Explanation:

~.|{0=}%..|= Full program, implicit input
             Stack: "[[3 5] [3 5] [6 4] [4 4]]"
~            Evaluate input
             Stack: [[3 5] [3 5] [6 4] [4 4]]
 .|          Make unique with setwise or with itself
             Stack: [[3 5] [6 4] [4 4]]
   {0=}%     Get first element of each
             Stack: [3 6 4]
        ..|  Duplicate and make unique again
             Stack: [3 6 4] [3 6 4]
           = Compare
             Stack: 1
             Implicit output
\$\endgroup\$
1
\$\begingroup\$

Javascript, 41

v=>!v.some(([a,b])=>new Map(v).get(a)!=b)

const F = v=>!v.some(([a,b])=>new Map(v).get(a)!=b)


// Helper code to display test results on page

const $ = s => document.querySelector(s);

const displayArea = $("#displayArea");

const testFunctions = [
  [
    [3, 5],
    [3, 5],
    [6, 4],
    [4, 4]
  ],
  [
    [9, 4],
    [1, 4],
    [2, 4]
  ],
  [],
  [
    [1, 1]
  ],
  [
    [1, 2],
    [2, 1]
  ]
];
const testNotFunctions = [
  [
    [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]
  ]
];

function println(text) {
  displayArea.append(text);
  displayArea.append(document.createElement("br"));
}

testFunctions.forEach(value => println(JSON.stringify(value) + F(value)));

println("");

testNotFunctions.forEach(value => println(JSON.stringify(value) + F(value)));
<div id="displayArea"></div>

\$\endgroup\$
1
\$\begingroup\$

Pip -x, 10 bytes

UQa#=UQaZb

Takes input as two command-line arguments: a key list and a value list. Attempt This Online!

Explanation

UQa#=UQaZb
  a         The key list
UQ          Uniquified
   #=       Is the same length as
       a    The key list
        Z   Zipped with
         b  The value list
     UQ     Uniquified
\$\endgroup\$
1
\$\begingroup\$

Vyxal, 5 bytes

UvhÞu

Try it Online!

Port of chunes' factor answer

U     # Uniquify
 vh   # Get the first of each
   Þu # Are they all unique?
\$\endgroup\$
1
\$\begingroup\$

PowerShell for Windows, 40 bytes

!($args|sort -u|group{$_[0]}|? c* -gt 1)

Try it online!

Where c* is the shortcut for the count property.

\$\endgroup\$
0
\$\begingroup\$

Python 2, 55 bytes

i=[j[0] for j in set(input())];print len(set(i))==len(i)

Try it online!

\$\endgroup\$
2
  • \$\begingroup\$ All you need is i=input();print len(set(i))==len(i). The list comprehension is unnecessary \$\endgroup\$
    – Cyoce
    May 5, 2017 at 21:39
  • \$\begingroup\$ You have one unnecessary space, you could shorten j[0] for to j[0]for. \$\endgroup\$
    – Adalynn
    May 6, 2017 at 17:23
0
\$\begingroup\$

PHP, 83 Bytes

prints 1 for function and nothing for non functions

<?$r=[];foreach($_GET as$v)in_array($v,$r)?:$k[($r[]=$v)[0]]++;echo max($k?:[1])<2;

Testcases

\$\endgroup\$
0
\$\begingroup\$

C (gcc), 95 94 bytes

Thanks to @hvd for saving a byte!

i;r,l;f(int*k,int*v){int m[10]={0};for(r=i=0;l=k[i];++i)!m[l]?m[l]=v[i]:v[i]-m[l]?++r:0;r=!r;}

Takes input as pointers to two zero-terminated arrays.

Try it online!

\$\endgroup\$
1
  • \$\begingroup\$ You can save a byte by turning the m[l] condition to !m[l] and swapping the other operands: you can then get rid of the parentheses. \$\endgroup\$
    – hvd
    May 6, 2017 at 8:58
0
\$\begingroup\$

JS (ES5), 75 bytes

c=function (a){m={};for(i=0;i<a.length;i++)if(m[a[i]]-(m[a[i]]=i))return 1}
\$\endgroup\$
0
\$\begingroup\$

Befunge-98, 40 bytes

&:#@!#._:&:a1p1g:9`3j>;#_-3j@.1_#;$a1g1p

Try it online!

Input consists of zero-terminated sequence of numbers v₁ k₁ v₂ k₂ v₃ k₃ …, output is 0 if the sequence represents a function, 1 if not.

Explanation

Key-value pairs are stored in the funge space on the second row (immediately below the program code).

&:#@!#._:&:a1p1g:9`3j>;#_-3j@.1_#;$a1g1p
&                                         S: v = read()
 :# !# _                                  if v != 0 goto N
   @ #.                                   return v
         &:a1p1g                          N: k = read(), m[10] = k, w = m[k]
                 9`3j>;#_        ;        if w > 9 goto P
        :       :        -3j   _#         if v == w goto P
                            @.1           return 1
                                  $a1g1p  P: m[v] = m[10], goto S

w > 9 in the fifth line is a shortcut for w == 32 which is the value of an uninitialized cell.

\$\endgroup\$
0
\$\begingroup\$

Java 8, 74 bytes

This is a lambda from Iterable<int[]> or int[][] to int or Integer (1 indicates function, 0 non-function). It checks each pair of mappings for compliance.

l->{for(int[]a:l)for(int[]b:l)if(a[0]==b[0]&a[1]!=b[1])return 0;return 1;}

Try It Online

\$\endgroup\$
0
\$\begingroup\$

Ruby 1.9+, 20 bytes

->a{a|a==[*Hash[a]]}

In recent versions of Ruby, converting an array to a hash (dictionary) and then back preserves its order, so we can do an equality comparison instead of using .size. Otherwise this is similar to the more general Ruby answer, including the trick of removing duplicates by unioning the input array with itself.

\$\endgroup\$
2
  • 1
    \$\begingroup\$ You can also convert to hash with to.h method: 19 bytes \$\endgroup\$
    – Kirill L.
    Apr 25, 2018 at 17:41
  • \$\begingroup\$ Nice! That's Ruby 2+, I think. \$\endgroup\$
    – histocrat
    Apr 25, 2018 at 17:59
1
2

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.