Это функция?

47

По заданному списку (key, value)пар определите, представляет ли он функцию, что означает, что каждый ключ отображается в согласованное значение. Другими словами, когда две записи имеют одинаковые ключи, они также должны иметь одинаковые значения. Повторные записи в порядке.

Например:

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

Ввод: упорядоченная последовательность (key, value)пар, состоящая из цифр от 1 до 9. Вам может не потребоваться определенный порядок. В качестве альтернативы вы можете взять список ключей и список значений в качестве отдельных входов.

Вывод: непротиворечивое значение для функций и другое непротиворечивое значение для не-функций.

Тестовые случаи: первые 5 входов являются функциями, последние 5 - нет.

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

Вот они как два списка входов:

[[(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:

Показать фрагмент кода

code-golf decision-problem XNOR
источник
сюръективная функция?
Poke
@Poke Это не должно быть сюрпризом.
xnor
Может ли ввод быть двумя списками одинаковой длины, один для ключей, другой для значений?
Увлечения Кэлвина
2
Можно ли поменять (key,value)местами пары, как в (value,key)? Я могу сбрить несколько байтов своего ответа, если это так.
ymbirtt
1
@ymbirtt Да, вы можете иметь пары в любом порядке.
xnor

Ответы:

37

Python 2 , 34 байта

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

Попробуйте онлайн!

Создает словарь и набор из входных данных и сравнивает их длины.
Словари не могут иметь дублированные ключи, поэтому все недопустимые (и повторяющиеся) значения удаляются.

прут
источник
5
Python 3, 30 байт:lambda x:not dict(x).items()^x
Veedrac
21

Haskell, 36 байт

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

Попробуйте онлайн!

Внешний (-> (k,v)) и внутренний (-> (m,n)) цикл по парам и всякий раз k==m, когда собираем значение истинности v==n. Проверьте, все ли верно.

Ними
источник
Ты слишком быстр! : /
flawr
18

Брахилог , 5 4 байта

dhᵐ≠

Попробуйте онлайн!

Полная программа. Насколько я могу судить, причина, по которой он опережает большинство других языков игры в гольф, заключается в том, что ≠он встроен в брахилог, тогда как большинству других языков игры в гольф необходимо его синтезировать.

объяснение

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

Как полная программа, мы получаем, trueесли утверждение успешно, или falseесли это не удается.


источник
15

Pyth , 5 байт

Я очень доволен этим.

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

Попробуйте онлайн!

notjagan
источник
9

Сетчатка , 25 байт

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

Попробуйте онлайн!

Формат ввода есть {k,v},{k,v},.... Печать 0для функций и 1не-функций. Я мог бы сохранить два байта, используя перевод строки вместо запятых в формате ввода, но это не так.

Мартин Эндер
источник
Я полагаю, что это квалифицируется как «серьезный удар», по крайней мере, с технической точки зрения.
FryAmTheEggman
8

Брахилог , 13 байт

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

Попробуйте онлайн!

объяснение

¬{          }      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.
Fatalize
источник
Можешь объяснить как Ċhᵐ=и как Ċtᵐ≠работает?
CalculatorFeline
@CalculatorFeline Прописные буквы - это имена переменных. Ċэто специальная переменная с именем Couple, которая всегда должна быть списком из двух элементов. ᵐявляется метапредикатом, который применяет непосредственно предшествующий предикат ( h - headили t - tailздесь) к каждому элементу ввода (здесь, Ċ). =и просто ≠проверить, что их вход содержит все равные / все различные элементы.
фатализировать
7

MATL , 8 байт

1Z?gs2<A

Входные данные: массив с values, за которым следует массив с keys.

Выход 1для функции, в 0остальном.

Попробуйте онлайн! , Или проверьте все тестовые случаи .

объяснение

1Z?

Строит разреженную матрицу. Первоначально все записи содержат 0; и 1добавляются к каждой записи (i, j)где jи iявляются входными key, valueпаром.

g

Матрица преобразуется в логическую; то есть превышающие записи 1(соответствующие дубликатам key, valueпарам) устанавливаются в 1.

s

Сумма каждого столбца вычисляется. Это количество разных values для каждого key.

2<A

Функция будет иметь все такие суммы меньше, чем 2.

Луис Мендо
источник
6

R, 33 байта

Это моя версия для R. Это использует aveфункцию. Я допустил пустой ввод, установив значения по умолчанию для параметров ключа и значения. aveпроизводит среднее значение для каждого из ключей. К счастью, это возвращает средние значения в том же порядке, что и входные значения, поэтому сравнение с входными данными покажет, есть ли другие значения. Возвращает, TRUEесли это функция.

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

Попробуйте онлайн!

MickyT
источник
6

05AB1E , 11 9 7 байт

Сохранено 2 байта благодаря kalsowerus .

Ùø¬DÙQ,

Попробуйте онлайн!

объяснение

Ù           # 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
источник
@ Райли: Да. Я до сих пор очень рад, что особый случай закончился только треть программы: P
Emigna
Я думаю , что вы могли бы сэкономить 3 байта, заменив `\)^с головой ( ¬): TiO
kalsowerus
@kalsowerus: К сожалению, это прервано для особого случая []:(
Emigna
@ Enigma О, это сработало, потому что при тестировании у меня все еще оставался остаток ,в конце. Добавьте это, и тогда это так или иначе работает с [].
kalsowerus
Обновлено TIO
kalsowerus
5

JavaScript (ES6), 45 38 байт

Сохранено 6 байтов благодаря @Neil

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

Возвращает falseили trueдля функций и не-функций соответственно.

Это работает путем постоянного вычитания старого значения каждой функции ( m[k]) и нового ( m[k]=vкоторое также хранит новое значение). Каждый раз, есть три случая:

  • Если не было старого значения, m[k]возвращается undefined. Вычитание чего-либо из undefinedрезультатов приводит к NaNошибочности.
  • Если старое значение совпадает с новым, это m[k]-vприводит к 0ошибочности.
  • Если старое значение отличается от нового, в m[k]-vрезультате получается ненулевое целое число, что является правдой.

Поэтому нам просто нужно убедиться, что m[k]-(m[k]=v)это никогда не правда.

ETHproductions
источник
1
Слишком долго. Использование a=>!a.some(([x,y])=>m[x]-(m[x]=y),m=[]).
Нил
@ Нил Черт, я знал, что должен быть какой-то способ использовать m[k]быть неопределенным ... Спасибо!
ETHproductions
5

Mathematica, 24 байта

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

Объяснение: Unionудаляет дублированные пары, затем #&@@@получает первый элемент из каждой пары (как, First/@но с меньшим количеством байтов). Если есть повторение в этих первых элементах, пары не создают функцию, с которой мы проверяем UnsameQ.

(Это может иметь самую высокую плотность @символов в любой программе, которую я написал ...)

Не дерево
источник
2
@плотность =
CalculatorFeline
4

Bash + coreutils, 17

sort -u|uniq -dw1

Ввод осуществляется через STDIN. keyи valueкоторые Tabразделены и каждая пара является новой строкой с разделителями.

sortудаляет дубликаты пар ключ-значение. uniq -dвыводит только дубликаты, поэтому выводит пустую строку в случае функции и непустую строку в противном случае - при наличии дублирующихся ключей, которые отображаются на разные значения.

Попробуйте онлайн .

Цифровая травма
источник
4

05AB1E , 9 байтов

Код:

ãü-ʒ¬_}}Ë

Объяснение:

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

Использует кодировку 05AB1E . Попробуйте онлайн!

Аднан
источник
ʒ
Начинаю
@Emigna Да, хаха: р, но я уже нашел ошибку, которая заставляет меня использовать }}вместо }.
Аднан,
4

Желе , 6 байт

QḢ€µQ⁼

Попробуйте онлайн!

объяснение

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.

Вот альтернативный метод, также 6 байтов:

QḢ€ṢIẠ

Попробуйте онлайн!

Вместо того, чтобы тестировать с удалением дубликатов ключей, эта функция сортирует ( Ṣ) и проверяет, является ли разница между условиями ( I) истинной ( Ạ)

fireflame241
источник
4

R , 95 66 байт

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

Сохранено 29 байтов благодаря Jarko Dubbeldam.

Анонимная функция. Выводит, FALSEесли функция, а TRUEесли нет (извините). Принимает в качестве аргументов список ключей и список значений, вот так.

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

Перебирает все ключи и получает длину набора уникальных значений для этого ключа. Если anyиз них> 1, вернуть TRUE.

Это побито ответом MickyT , а также Джузеппе . upvote один из тех.

BLT
источник
Почему вы создаете фрейм данных только для того, чтобы ссылаться на векторы, которые вы только что поместили в этот фрейм данных? function(k=0,v=0)any(sapply(k,function(x){length(unique(v[k==x]))-1}))должен выполнить то же самое.
JAD
Потому что я все еще учусь! По крайней мере, один из других ответов R делает это более или менее так, как вы описываете.
BLT
извините, если я немного грубоват :) ваша заявка немного отличается от других ответов R, и если бы вы удалили лишнюю data.frame, вы могли бы сравнить лучше.
JAD
4

J-uby , 48 33 25 21 байт

-3 байта благодаря Джордану! 

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

объяснение

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

Первый подход, 33 байта

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

Это длиннее, чем эквивалентное решение Ruby, но было весело сделать.

Попытка объяснения путем преобразования в 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 }

Я мог бы сохранить 2 байта с более новой версией, заменив :uniqна~:|

Cyoce
источник
3

Mathematica, 35 байт

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

Чистая функция, принимающая список упорядоченных пар в качестве входных данных и возвращающих Trueили False. Использует тот факт, что Union@#удаляет повторяющиеся упорядоченные пары, но <|Rule@@@#|>(ассоциация) удаляет все, кроме одной упорядоченной пары с конкретным первым элементом. Таким образом, мы можем просто сравнить Lengths двух выходов, чтобы проверить, является ли список ввода функцией.

Грег Мартин
источник
3

Желе , 6 байт

nþ`ḄCȦ

Попробуйте онлайн!

Как это устроено

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.
Деннис
источник
3

CJam , 19 17 байт

Сохранено 2 байта благодаря Мартину Эндеру

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

Выходы 0для функций и 1не-функций.

Попробуйте онлайн!

объяснение

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)
Бизнес Кот
источник
3

APL (Dyalog) , 16 12 11 9 байтов

(∪≡⊢)⊃¨∘∪

Попробуйте онлайн!

объяснение

∪             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

Отпечатки 0за ложь и 1за правду

Kritixi Lithos
источник
Вау, ты становишься действительно хорошим.
Адам
3

брейкфук , 71 байт

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

Попробуйте онлайн!

Ввод принимается как плоская строка: например, первый тестовый пример будет 35356444. Чтобы получить представление, показанное в исходном вопросе, просто добавьте в программу шесть запятых в нужных точках.

Вывод Uдля функций и Vне-функций.

объяснение

Для любой кодовой точки ASCII n, f (n) сохраняется в ячейке 2n + 1. Ячейки 2n и 2n + 2 являются рабочим пространством, а 0, 2, 4, 6, ... 2n-2 являются цепью хлебных крошек, ведущей обратно к ячейке 0. Когда доказано, что ввод не является функцией, f ( 0) установлен в 1 (среди различных побочных эффектов).

,                  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
источник
2

Pyth - 9 8 байт

ql.d{Ql{

Попробуй

Он работает, удаляя все повторяющиеся пары первым ({Q); затем он сравнивает длину списка с длиной словаря, созданного из списка (если одно и то же значение x встречается более одного раза, конструктор словаря использует только последнее значение, в результате чего словарь короче списка)

Мария
источник
2

MATL , 12 байт

iFFvXu1Z)SdA

Входные данные представляют собой матрицу из 2 столбцов, где первый столбец является ключевым, а второй - значением.

Попробуйте онлайн!

объяснение

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?
Луис Мендо
источник
2

PHP, 49 байт

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

Ничего не печатает для функций и nне-функций.

user63956
источник
1

CJam , 14 11 9 байтов

_&0f=__&=

Попробуйте онлайн!

Принимает ввод как массив пар ключ / значение в стеке, возвращает, 1если ввод является функцией, и 0если это не так.

Это решение основано на фрагменте _&, который дедуплицирует массив, беря его пересечение с самим собой. Я делаю это дважды, сначала на полном вводе (чтобы избавиться от любых точно дублированных пар ключ / значение), а затем только на ключах (чтобы увидеть, остались ли какие-либо дубликаты ключей после первой дедупликации).

Вот полный код с комментариями:

_&           "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";
Илмари Каронен
источник
Вы знаете, e#это синтаксис выделенных комментариев в CJam.
Esolanging Fruit
1

Рубин, 39 30 29 байт

Спасибо @ValueInk за сохранение 9 байтов!

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

Порт @ Род Пита 2 ответ .

Cyoce
источник
Hash[x]работает так же хорошо, т. ч.
Value Ink
@ValueInk спасибо. Не уверен, почему я не думал об этом.
Cyoce