Isso é uma função?

47

Dada uma lista de (key, value)pares, determine se ela representa uma função, o que significa que cada tecla é mapeada para um valor consistente. Em outras palavras, sempre que duas entradas tiverem chaves iguais, elas também deverão ter valores iguais. Entradas repetidas estão OK.

Por exemplo:

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

Entrada: uma sequência ordenada de (key, value)pares usando os dígitos de 1 a 9. Você pode não precisar de uma ordem específica. Como alternativa, você pode tomar a lista de chaves e a lista de valores como entradas separadas.

Saída: um valor consistente para funções e um valor consistente diferente para não-funções.

Casos de teste: As 5 primeiras entradas são funções, as 5 últimas não.

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

Aqui estão elas como duas listas de entradas:

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

Entre os melhores:

Mostrar snippet de código

code-golf decision-problem xnor
fonte
função adjetiva?
puxão
@ Poké Não precisa ser surjetivo.
Xnor
A entrada poderia ser duas listas de igual comprimento, uma para chaves e outra para valores?
Hobbies de Calvin
2
É certo que os (key,value)pares sejam revertidos, como em (value,key)? Posso raspar alguns bytes da minha resposta, se for o caso.
Ymbirtt #
1
@ymbirtt Sim, você pode ter os pares em qualquer ordem.
Xnor

Respostas:

37

Python 2 , 34 bytes

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

Experimente online!

Cria um dicionário e um conjunto a partir da entrada e compara seus comprimentos.
Os dicionários não podem ter chaves duplicadas; portanto, todos os valores ilegais (e repetidos) são removidos.

Cajado
fonte
5
Python 3, 30 bytes:lambda x:not dict(x).items()^x
Veedrac 8/17/17
21

Haskell, 36 bytes

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

Experimente online!

Loop externo (-> (k,v)) e interno (-> (m,n)) sobre os pares e sempre que k==m, colete o valor de verdade de v==n. Verifique se tudo é verdade.

nimi
fonte
Você é muito rápido! : /
flawr
18

Braquilog , 5 4 bytes

dhᵐ≠

Experimente online!

Programa completo. Até onde eu sei, a razão pela qual isso está superando a maioria das outras línguas de golfe é que ela ≠está embutida no Brachylog, enquanto a maioria das outras línguas de golfe precisa sintetizá-la.

Explicação

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

Como um programa completo, obtemos truese a afirmação é bem-sucedida ou falsese falha.


fonte
15

Pitão , 5 bytes

Estou muito feliz com este.

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

Experimente online!

notjagan
fonte
9

Retina , 25 bytes

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

Experimente online!

O formato de entrada é {k,v},{k,v},.... Imprime 0para funções e 1para não funções. Eu poderia salvar dois bytes usando linefeeds em vez de vírgulas no formato de entrada, mas isso é uma bagunça.

Martin Ender
fonte
Acredito que se qualifique como "seriamente maluco", pelo menos do ponto de vista técnico.
FryAmTheEggman
8

Braquilog , 13 bytes

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

Experimente online!

Explicação

¬{          }      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.
Fatalizar
fonte
Você pode explicar como Ċhᵐ=e Ċtᵐ≠trabalhar?
CalculatorFeline
@CalculatorFeline Letras maiúsculas são nomes de variáveis. Ċé uma variável especial chamada Couple, que é sempre pré-restringida para ser uma lista de dois elementos. ᵐé um metapredicado que aplica o predicado imediatamente anterior ( h - headou t - tailaqui) a cada elemento da entrada (aqui Ċ). =e ≠simpl verifique se sua entrada contém todos os elementos iguais / todos diferentes.
Fatalize
7

MATL , 8 bytes

1Z?gs2<A

As entradas são: uma matriz com os values, seguida por uma matriz com os keys.

A saída é 1para função, caso 0contrário.

Experimente online! . Ou verifique todos os casos de teste .

Explicação

1Z?

Constrói uma matriz esparsa. Inicialmente todas as entradas contêm 0; e 1é adicionado a cada entrada (i, j), onde je ié o de entrada key, valuepares.

g

A matriz é convertida em lógica; isto é, entradas superior 1(correspondente a duplicar key, valuepares) são ajustados para 1.

s

A soma de cada coluna é calculada. Este é o número de values diferentes para cada um key.

2<A

Uma função terá todas essas somas inferiores a 2.

Luis Mendo
fonte
6

R, 33 bytes

Esta é a minha versão para R. Isso tira proveito da avefunção. Eu permiti a entrada vazia, definindo padrões nos parâmetros de chave e valor. aveestá produzindo uma média dos valores para cada uma das chaves. Felizmente, isso retorna as médias na mesma ordem que os valores de entrada; portanto, uma comparação com a entrada indicará se existem valores diferentes. Retorna TRUEse for uma função.

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

Experimente online!

MickyT
fonte
6

05AB1E , 11 9 7 bytes

Economizou 2 bytes graças a kalsowerus .

Ùø¬DÙQ,

Experimente online!

Explicação

Ù           # 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
fonte
@Riley: Sim. Ainda estou muito feliz que o caso especial tenha acabado com apenas um terço do programa: P
Emigna
Eu acho que você poderia economizar 3 bytes, substituindo `\)^com cabeça ( ¬): TIO
kalsowerus
@kalsowerus: Infelizmente isso quebra no caso especial de []:(
Emigna
@Enigma Oh, funcionou, porque durante os testes eu ainda tinha uma sobra ,no final. Adicione isso e, de alguma forma, ele funciona [].
Ksowerus
Atualizado TIO
kalsowerus
5

JavaScript (ES6), 45 38 bytes

Guardado 6 bytes graças a @Neil

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

Retorna falseou truepara funções e não funções, respectivamente.

Isso funciona subtraindo constantemente o valor antigo de cada função ( m[k]) e o novo ( m[k]=vque também armazena o novo valor). Cada vez, há três casos:

  • Se não houvesse valor antigo, m[k]retornaria undefined. Subtrair qualquer coisa dos undefinedresultados em NaN, o que é falso.
  • Se o valor antigo for o mesmo que o novo, m[k]-vresulta em 0, o que é falso.
  • Se o valor antigo for diferente do novo, m[k]-vresulta em um número inteiro diferente de zero, que é verdadeiro.

Portanto, precisamos apenas garantir que isso m[k]-(m[k]=v)nunca seja verdade.

ETHproductions
fonte
1
Demasiado longo. Use a=>!a.some(([x,y])=>m[x]-(m[x]=y),m=[]).
Neil
@ Neil Dang, eu sabia que tinha que haver alguma maneira de utilizar m[k]a indefinição ... Obrigado!
ETHproductions
5

Mathematica, 24 bytes

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

Explicação: Unionexclui pares duplicados e #&@@@obtém o primeiro elemento de cada par (como First/@mas com menos bytes). Se houver alguma repetição nesses primeiros elementos, os pares não fazem uma função, com a qual verificamos UnsameQ.

(Isso pode ter a maior densidade de @caracteres em qualquer programa que eu escrevi ...)

Não é uma árvore
fonte
2
@densidade = 04/01
CalculatorFeline
5

R, 36 33 bytes

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

Experimente online!

função anônima; retorna FALSEpara funções e TRUEpara não.

Isso está sendo derrotado e finalmente está empatado com a resposta de MickyT! !

Giuseppe
fonte
4

Bash + coreutils, 17

sort -u|uniq -dw1

A entrada é fornecida via STDIN. keye valuesão Tabseparados e cada par é delimitado por nova linha.

sortremove os pares de valores-chave duplicados. uniq -dsomente gera duplicatas e, portanto, gera a sequência vazia no caso de uma função e, caso contrário, uma sequência não vazia - quando houver chaves duplicadas que mapeiam para valores diferentes.

Experimente online .

Trauma Digital
fonte
4

05AB1E , 9 bytes

Código:

ãü-ʒ¬_}}Ë

Explicação:

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

Usa a codificação 05AB1E . Experimente online!

Adnan
fonte
Começar a mostrar ʒimediatamente vejo :)
Emigna
@ Emigna Sim haha: p, mas eu já encontrei um bug que me faz usar em }}vez de }.
Adnan
4

Gelatina , 6 bytes

QḢ€µQ⁼

Experimente online!

Explicação

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.

Aqui está um método alternativo, também com 6 bytes:

QḢ€ṢIẠ

Experimente online!

Em vez de testar com a remoção de chaves duplicadas, isso classifica ( Ṣ) e verifica se a diferença entre os termos ( I) é verdadeira ( Ạ)

fireflame241
fonte
4

R , 95 66 bytes

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

Economizou 29 bytes graças a Jarko Dubbeldam.

Função anônima. Saída FALSEse uma função e TRUEse não (desculpe). Assume como argumentos uma lista de chaves e uma lista de valores, assim.

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

Passa por todas as chaves e agarra o comprimento do conjunto de valores exclusivos para essa chave. Se anyeles forem> 1, retorne TRUE.

Isso está sendo derrotado pela resposta de MickyT e também pela de Giuseppe . votou um deles.

BLT
fonte
Por que você está criando um quadro de dados, apenas para fazer referência aos vetores que você acabou de colocar nesse quadro de dados? function(k=0,v=0)any(sapply(k,function(x){length(unique(v[k==x]))-1}))deve realizar a mesma coisa.
JAD
Porque eu ainda estou aprendendo! Pelo menos uma das outras respostas R faz mais ou menos como você descreve.
BLT
desculpe se eu fui um pouco severo :) sua submissão é um pouco diferente das outras respostas R, e se você cortasse o data.frame redundante, poderá comparar melhor.
JAD
4

J-uby , 48 33 25 21 bytes

-3 bytes graças à Jordânia! 

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

Explicação

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

Primeira abordagem, 33 bytes

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

Este é mais longo que a solução Ruby equivalente, mas foi divertido de fazer.

Tentativa de explicação, transformando em 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 }

Eu poderia salvar 2 bytes com uma versão mais recente substituindo :uniqpor~:|

Cyoce
fonte
3

V , 30 bytes

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

Experimente online!

Saídas 1para funções e nada para não-funções.

DJMcMayhem
fonte
3

Mathematica, 35 bytes

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

Função pura pegando uma lista de pares ordenados como entrada e retorno Trueou False. Explora o fato de Union@#excluir pares ordenados repetidos, mas <|Rule@@@#|>(uma associação) exclui todos, exceto um par ordenado, com um primeiro elemento específico. Portanto, podemos apenas comparar os Lengths das duas saídas para verificar se a lista de entrada é uma função.

Greg Martin
fonte
3

Gelatina , 6 bytes

nþ`ḄCȦ

Experimente online!

Como funciona

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.
Dennis
fonte
3

CJam , 19 17 bytes

Economizou 2 bytes graças a Martin Ender

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

Saídas 0para funções e 1para não funções.

Experimente online!

Explicação

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)
Gato de negócios
fonte
3

APL (Dyalog) , 16 12 11 9 bytes

(∪≡⊢)⊃¨∘∪

Experimente online!

Explicação

∪             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

Imprime 0para falso e 1verdadeiro

Kritixi Lithos
fonte
Você está ficando muito bom.
Adám
3

Na verdade , 4 bytes

╔♂F═

Experimente online!

Explicação:

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

brainfuck , 71 bytes

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

Experimente online!

A entrada é tomada como uma sequência simples: por exemplo, o primeiro caso de teste seria 35356444. Para obter a representação mostrada na pergunta original, basta adicionar um total de seis vírgulas ao programa nos pontos corretos.

A saída é Upara funções e Vpara não funções.

Explicação

Para qualquer ponto de código ASCII n, f (n) é armazenado na célula 2n + 1. As células 2n e 2n + 2 são espaço de trabalho e 0, 2, 4, 6, ... 2n-2 são uma trilha de migalhas de pão para levar de volta à célula 0. Quando a entrada é comprovadamente não uma função, f ( 0) está definido como 1 (entre vários efeitos colaterais).

,                  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
fonte
2

Perl 6 , 38 bytes

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

Tente

Brad Gilbert b2gills
fonte
2

Pitão - 9 8 bytes

ql.d{Ql{

Tente

Funciona removendo quaisquer pares repetidos primeiro ({Q); depois, compara o comprimento da lista com o comprimento de um dicionário criado a partir da lista (se o mesmo valor x ocorrer mais de uma vez, o construtor do dicionário usará apenas o último, resultando em que o dicionário seja mais curto que a lista)

Maria
fonte
2

MATL , 12 bytes

iFFvXu1Z)SdA

A entrada é uma matriz de 2 colunas, onde a primeira coluna é a chave e a segunda é o valor.

Experimente online!

Explicação

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?
Luis Mendo
fonte
2

PHP, 49 bytes

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

Não imprime nada para funções e npara não funções.

user63956
fonte
1

CJam , 14 11 9 bytes

_&0f=__&=

Experimente online!

Recebe a entrada como uma matriz de pares de chave / valor na pilha, retorna 1se a entrada é uma função e 0se não for.

Essa solução é baseada no snippet _&, que desduplica uma matriz, levando consigo a interseção definida. Faço isso duas vezes, primeiro na entrada completa (para livrar-se de quaisquer pares de chaves / valores exatamente duplicados) e depois apenas nas chaves (para ver se ainda restam algumas chaves duplicadas após a primeira desduplicação).

Aqui está o código completo com comentários:

_&           "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";
Ilmari Karonen
fonte
Só para você saber, e#é a sintaxe de comentário de linha dedicada no CJam.
Esolanging Fruit
1

Ruby, 39 30 29 Bytes

Obrigado a @ValueInk por salvar 9 bytes!

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

Porto da resposta do @ Rod's Python 2 .

Cyoce
fonte
Hash[x]funciona tão bem tbh
Value Ink
@ValueInk thanks. Não sei por que não pensei nisso.
Cyoce 5/05