47
\$\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\$
  • \$\begingroup\$ surjective function? \$\endgroup\$ – Poke May 4 '17 at 20:50
  • \$\begingroup\$ @Poke It doesn't have to be surjective. \$\endgroup\$ – xnor May 4 '17 at 20:54
  • \$\begingroup\$ Could the input be two lists of equal length, one for keys one for values? \$\endgroup\$ – Calvin's Hobbies May 4 '17 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 '17 at 9:41
  • 1
    \$\begingroup\$ @ymbirtt Yes, you can have the pairs be in either order. \$\endgroup\$ – xnor May 6 '17 at 18:22

43 Answers 43

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\$
  • \$\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 '17 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 '17 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 '17 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 '17 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 '17 at 0:26
1
\$\begingroup\$

JavaScript (ES6) from ETHproductions', 35 bytes

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

Jelly, 5 bytes

ĠịE€Ạ

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

Try it online!

\$\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\$
  • \$\begingroup\$ All you need is i=input();print len(set(i))==len(i). The list comprehension is unnecessary \$\endgroup\$ – Cyoce May 5 '17 at 21:39
  • \$\begingroup\$ You have one unnecessary space, you could shorten j[0] for to j[0]for. \$\endgroup\$ – Zacharý May 6 '17 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\$
  • \$\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 '17 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\$

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\$
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\$
  • 1
    \$\begingroup\$ You can also convert to hash with to.h method: 19 bytes \$\endgroup\$ – Kirill L. Apr 25 '18 at 17:41
  • \$\begingroup\$ Nice! That's Ruby 2+, I think. \$\endgroup\$ – histocrat Apr 25 '18 at 17:59
0
\$\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\$

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.