É um substantivo ou não?

22

Dada uma string como entrada, determine se é um substantivo ou não.

Você será pontuado nas 1000 palavras em inglês mais comuns, por quantas você rotula corretamente como um substantivo ou não.

O programa ou função que classificar corretamente a maioria dessas palavras em 50 bytes ou menos vencerá.

Substantivos

Um substantivo é uma palavra que representa uma coisa, normalmente. Fica mais complexo, mas essa é a ideia básica.

Nos casos em que uma palavra poderia ser um substantivo ou alguma outra parte do discurso, eu a classifiquei como substantivo, mesmo que esse seja um uso raro. Ou, na verdade, deixei este site fazer isso por mim.

As palavras nas quais você será pontuado são essas 1000 palavras comuns , que são da Wikipedia simples , com "dois" e "uma vez" adicionados. Desses, esses são os 586 substantivos e esses são os 414 não-substantivos . Você pode encontrar todas as três listas aqui . Observe que todas essas entradas estão em minúsculas. Essas listas são finais - não tente discutir gramática.

Seu programa será considerado correto se gerar um truthy resultado de uma entrada que é um substantivo, e um resultado Falsas de uma entrada que não é um substantivo.

Sutilezas:

Os programas devem ter uma saída determinística. Se você deseja usar a aleatoriedade, semeie-a. Os programas não têm permissão para usar listas de substantivos embutidas ou outras funcionalidades integradas de parte da fala.

Exemplos:

a: noun
act: noun
active: noun
about: non-noun
above: non-noun
across: non-noun

Indique qual é a taxa de sucesso do seu programa na sua resposta. O programa ou função de no máximo 50 bytes com a maior taxa de sucesso vence. Em caso de empate, a menor contagem de bytes determinará um vencedor. Boa sorte!

code-challenge decision-problem natural-language test-battery isaacg
fonte

Respostas:

13

JavaScript (ES6), 43 bytes, 622 630 633

Só para fazer a bola rolar. Retorna 1para substantivos, 0para não substantivos.

s=>2552>>s.length&/^[bcdf-mp-tvwy]/.test(s)

Quão?

Apostamos no substantivo se as duas condições a seguir forem atendidas:

  1. O comprimento da palavra é 3, 4, 5, 6, 7, 8 ou 11. Isso é feito deslocando o número binário 100111111000 (2552 como decimal).
  2. A palavra começa com uma destas letras: bcdfghijklmpqrstvwy
Arnauld
fonte
Assim como eu estava prestes a comentar, com o JS especificamente em mente, que o limite de bytes era muito restritivo, você publica isso! Eu estava pensando, sem olhar para a lista, que uma pontuação melhor que 586 poderia ser possível testando a primeira letra ou 2 em cada palavra. Bem feito :)
Shaggy
Uma explicação seria legal para pessoas menos familiarizadas com o Javascript. Tanto quanto posso dizer, isso verifica se o comprimento da palavra é 3, 4, 5, 6, 7, 8 ou 11, e a palavra também começa com um de um conjunto de letras?
Isaacg
@isaacg Isso está correto. Explicação adicionada.
Arnauld
4
Observe que a classe de caracteres [bcdf-mp-tvwy]é equivalente à classe [^aenouxz]. Uma alteração economizaria 4 bytes, os quais poderiam ser capitalizados.
fireflame241
@ fireflame241 Muito verdade. E isso pode ser reduzido, [^aenouz]porque não temos nenhuma palavra que comece com a x.
Arnauld
11

Geléia , 48 bytes, pontuação 731

Esta é a minha primeira resposta em Jelly e tive muitos problemas para montar isso. Ah, bem ... isso foi divertido. :-)

O‘ḅ⁹%⁽€Oæ»4“Ạ$ⱮẊḲḲLÑMṆụ⁻ẉṂ`ŻvḤæɠ5ṭȯƁU*×TdƲḥ`’æ»Ḃ

1 byte salvo graças a @JonathanAllan

Experimente online!

Conjuntos de análise e detalhamento

  • Não substantivos identificados corretamente como não substantivos: 265/414 (64%)
  • Substantivos identificados corretamente como substantivos: 466/586 (79,5%)

Quão?

Primeiro calculamos um hash da string de entrada:

  • convertendo-o em um inteiro, interpretando cada ponto de código como um dígito de 256 base
  • aplicação do módulo 4080 (escolhido como o valor mais eficiente com não mais de 12 bits)
  • mantendo os 8 bits mais significativos do resultado

Isso nos deixa com um índice em [0 ... 255] e, portanto, divide todas as palavras em 256 grupos.

Para cada grupo de palavras, pré-calculamos uma flag binária, que é 1se o grupo contiver mais substantivos que não substantivos, e 0caso contrário. Isso leva a um número N de 256 bits que vamos usar como uma tabela de pesquisa. Nós o armazenamos como uma string codificada na base 250.

A seguir é a representação binária de N .

1000011000001011000101111011111001001101110010101101110010001101
0000010001101010010111110001110010010101110110110010111111010000
0001111010011110000110101011111000011110111011010011011110101100
1010010110101111000010101000101100000001110110100011111000101010

Que pode ser armazenado como “Ạ$ⱮẊḲḲLÑMṆụ⁻ẉṂ`ŻvḤæɠ5ṭȯƁU*×TdƲḥ`’no Jelly.

Daí o código:

O‘ḅ⁹%⁽€Oæ»4“Ạ$ⱮẊḲḲLÑMṆụ⁻ẉṂ`ŻvḤæɠ5ṭȯƁU*×TdƲḥ`’æ»Ḃ    main link

O                                                   convert the input string to a list of
                                                    code points
 ‘                                                  increment each of them
  ḅ⁹                                                convert from base 256 to an integer
    %⁽€O                                            modulo 4080
        æ»4                                         drop the 4 least significant bits
           “Ạ$ⱮẊḲḲLÑMṆụ⁻ẉṂ`ŻvḤæɠ5ṭȯƁU*×TdƲḥ`’æ»     right shift N by this amount
                                               Ḃ    test the least significant bit
Arnauld
fonte
Bom trabalho! Salvar um byte para boot com O‘ḅ⁹%⁽€Oæ»4“Ạ$ⱮẊḲḲLÑMṆụ⁻ẉṂ`ŻvḤæɠ5ṭȯƁU*×TdƲḥ`’æ»Ḃ(note também que você pode usar o rodapé na TIO, eu iria com Ç€¬S,Le Ç€S,Lpara seus dois conjuntos de testes.
Jonathan Allan
@ JonathanAllan Obrigado pelas dicas!
Arnauld
10

JavaScript (ES6), 50 bytes, pontuação 693

s=>!/^([aouz]|th|..$)|e.+[ey]|[flo].r|a.p/.test(s)

Apenas procurando por possíveis padrões que os não substantivos tenham e que os substantivos não.

Os substantivos não contêm mais frequentemente:

  1. a, o, u ou z como a primeira letra.
  2. º como as duas primeiras letras.
  3. Apenas duas letras. [Pense em pronomes (eu, nós, ele, ele) e preposições (de, para, em, em, por, em, em, ...).]
  4. e , seguido por uma ou mais letras, seguido por e ou y .
  5. f, l ou o , seguido por qualquer letra, seguida de r .
  6. a , seguido por qualquer letra, seguido de p .

Snippet:

Mostrar snippet de código

Rick Hitchcock
fonte
Acredito que você pode salvar um byte alterando o primeiro regex para /h|n/(ou executando /^.[hn]/.test(s)) e outro alterando s[2]>''para !!s[2]ou 2 in s.
ETHproductions
Obrigado, @ETHproductions. Posso usar suas sugestões e combinar os dois testes para economizar vários bytes, o que me permitiu adicionar código para melhorar minha pontuação.
Rick Hitchcock
Não é a.predundante, pois você já possui [aouz]?
AdmBorkBork
@AdmBorkBork, a um em [aouz]é igualado apenas quando no início da cadeia. Por qualquer motivo, o teste para a.p qualquer lugar da string melhora a pontuação.
Rick Hitchcock
10

Geléia , 50 bytes , pontuação 763

Usando um hash agora (bem como a resposta da geléia de Arnauld )

OP%⁽Wpị“!ḋGẠ⁻Ṭȥʋt|Ḥ\⁾°½İ@G2ḂƑ½ịʂ¶ɦḲ⁷³Hz~⁵p9)⁹ƙ¿’B¤

Experimente Online!

250/414 para Não-substantivos
513/586 para Substantivos
Total = 250 + 513 = 763.

Quão?

Constrói uma tabela com 308 entradas, 1 (identificando um substantivo) ou 0 (identificando um não substantivo) e indexa-a usando uma chave fornecida por uma função hash que utiliza o produto dos ordinais da palavra de entrada:

OP%⁽Wpị“!ḋGẠ⁻Ṭȥʋt|Ḥ\⁾°½İ@G2ḂƑ½ịʂ¶ɦḲ⁷³Hz~⁵p9)⁹ƙ¿’B¤ - Link: list of characters, word
O                                                  - convert to ordinals
 P                                                 - product
   ⁽Wp                                             - base 250 number = 22863
  %                                                - modulo (by 22863)
                                                 ¤ - nilad plus link(s) as a nilad:
       “!ḋGẠ⁻Ṭȥʋt|Ḥ\⁾°½İ@G2ḂƑ½ịʂ¶ɦḲ⁷³Hz~⁵p9)⁹ƙ¿’   -   base 250 number
                                                B  -   as a binary list (308 bits)
      ị                                            - index into (1-indexed and modular,
                                                  -   so adds another modulo by 308)

Anterior:  50  47 bytes , pontuação 684

ḣ3Ẇf“QṘ°ḂżÐŒ#ḍæ09»s2¤Ȧ¬ȧØY⁾niyṖf⁽ż2ị$
0,-2ịE¬ȧÇ

Um link monádico que pega uma palavra e retorna uma lista de um caractere (verdade) se a palavra é identificada como um substantivo, ou uma lista vazia ou zero (ambos falsey), se não for.

Experimente online! (o rodapé executa um if else no resultado para imprimirNounouNon-Noun)
... ou veja o programa de pontuação (contabiliza índices de verdade nas duas listas e depois calcula a pontuação).

Repartição da pontuação: 462/586 substantivos identificados corretamente (124 incorretos), 222/414 não substantivos corretamente identificados (192 incorretos) - total correto = 684/1000.

Quão?

Acho que não é um substantivo se ...

  • o último caractere e o caractere dois antes disso são iguais (com indexação modular e com base em 1)
  • um dos dois primeiros substrings de comprimento 2 está em:
    'be', 'th', 'le', 'he', 'm ', 'ev', 'et', 's ', 'fl', 'ax', 'en', 'fo', 'am', 'az' (nota: 'm 'e's ' está aqui apenas para facilitar a compactação, mas eles nunca aparecem de qualquer maneira)
  • A -299 º índice (com modular e 1 à base de indexação) é qualquer um:
    aenouyz(embora este é implementado inversamente e com letras maiúsculas em excesso)
    ... desde que as palavras têm comprimento entre 1 e 11 a -299 º índice é equivalente para usar o comprimento para mapear o mapeamento:{7:2; 8:5; 9:7; 11:9; else 1}

ḣ3Ẇf“QṘ°ḂżÐŒ#ḍæ09»s2¤Ȧ¬ȧØY⁾niyṖf⁽ż2ị$ - Link 1: list of characters, word
ḣ3                                    - head to index 3 (1st 3 characters, like 'abc')
  Ẇ                                   - all sublists (['a','b','c','ab','bc','abc']
                    ¤                 - nilad followed by link(s) as a nilad:
    “QṘ°ḂżÐŒ#ḍæ09»                    - compression of "bethlehem evets flaxenfoamaz"
                  s2                  - split into chunks of 2:
                                      -   be,th,le,he,m ,ev,et,s ,fl,ax,en,fo,am,az
   f                                  - filter keep (can only match 'ab' or 'bc')
                     Ȧ                - any and all (0 if empty, 1 if not)
                      ¬               - logical not
                        ØY            - consonant -y yield = "BCD...WXZbcd...wxz"
                          ⁾ni         - character pair = "ni" (no shrubbery for you!)
                             y        - translate (exchange the n for an i)
                              Ṗ       - pop (remove the z)
                       ȧ              - logical and
                                    $ - last two links as a monad:
                                ⁽ż2   -   base 250 literal = -299
                                   ị  -   index into the word
                               f      - filter keep

0,-2ịE¬ȧÇ - Main link: list of characters, word
0,-2      - pair zero with -2 = [0,-2]
    ị     - index into the word (last character and the one before the one before that)
     E    - all (both) equal?
      ¬   - logical not
        Ç - call the last link (1) as a monad
       ȧ  - logical and

13 bytes, pontuação: 638

Uma primeira festança rápida (estendida acima)

ØY⁾niyṖf⁽ż2ị$
Jonathan Allan
fonte
0,-2não significa que pair zero with -2isso significaliteral [0, -2]
Erik o Outgolfer
Mas é o mesmo efeito: p
Jonathan Allan
não, não 0,-2é um nilad, não é separado (0)(,)(-2)... é claro que é o mesmo efeito neste caso, mas nem sempre. Aprendi isso da maneira mais difícil ... e, seja qual for o caso, prefiro explicar o que realmente acontece, em vez de algo com o mesmo efeito ou algo assim.
Erik the Outgolfer
Se eu tivesse escrito "junção" em vez de "par", você teria comentado "nenhuma junção é j"?
Jonathan Allan
Eu posso ser um pouco pedante, mas pairou joinsão obviamente maneiras erradas de expressá-lo, uma vez que, 0,-2,-6por exemplo, não significa, pair 0 with -2 and then pair that with -6 = [[0, -2], -6]mas significa literal [0, -2, -6]. Entendi , o , átomo e o ...,...(,...(...)) literal são confusos ... mas stilll 0,-2,-6não é exatamente o mesmo que 0,-2;-6o primeiro é um link e o segundo, três links.
Erik the Outgolfer
2

Julia 34bytes, 609

f(w)=hash(w)&0x0800000000004808>0

Eu queria economizar em caracteres usando o hash embutido. Eu sinto que deve haver uma maneira de fazer isso melhor. Julia simplesmente não é amigável o suficiente com as operações de troca de bits que quero usar para melhorar isso, eu acho.

Encontrar máscaras de bits adequadas para o hash separá-las é um jogo interessante.

Lyndon White
fonte
Melhor solução;)
tamasgal 15/08
2

Python 2 , 50 bytes, precisão: 596

lambda x:2<len(x)<7 or x[0]in"abcgmprs"or"st" in x

Experimente online!

Simplesmente verifica a primeira letra, o comprimento e se "st" está na palavra Code assume que a palavra está definida como x (Edit: Graças a issacg por corrigir o código do snippet para funcionar)

Husnain Raza
fonte
Olá, seja bem-vindo ao site. Embora isso seja interessante, é necessário que os envios sejam de promoção ou de programas completos. Este é um trecho, que não é permitido. Veja isso Experimente online! link para uma maneira de converter esse snippet em uma função enquanto ainda executa o mesmo código.
Isaacg
2

Haskell, 36 bytes, 626 631

f x=length x>2&&x!!0`notElem`"aenou"
BlackCap
fonte
643 se alguém tiver um idioma mais curto:length x>2&&(x!!0`notElem`"aenou"||x!!1`elem`"acqrsty")
BlackCap 18/08
2

Implementação de porta lógica em dois níveis, não 50 bytes, pontuação 1000

  1. Basta conectar a representação binária da palavra dada às 88 entradas

    1. complete a palavra de entrada com espaços à direita se o comprimento da palavra for menor que 11
    2. Código ASCII de 8 bits para cada letra da palavra de entrada

  2. O circuito retorna 1 se a palavra é um substantivo e retorna 0 se não

  3. As linhas tracejadas azuis são para entradas nunca usadas

Essa implementação precisa

  1. 48 transistores para codificar todas as portas dos inversores
  2. 1100 transistores para codificar todas as portas AND
  3. 154 transistores para codificar a porta OR
  4. Total de 1302 transistores que representam menos de 28 bytes.

Algumas medições

  1. Um portão inversor precisa de 1 transistor
  2. Um OR simples de 2 entradas porta precisa de 2 transistores
  3. Um portão AND simples de 2 entradas precisa de 2 transistores
  4. Um bit precisa de 6 transistores

insira a descrição da imagem aqui

Circuit.pdf em resolução total aqui

Circuit.png em resolução total aqui

mdahmoune
fonte
2
Você poderia explicar exatamente qual é o seu sistema para codificar esse circuito em bytes? Estou muito confuso como você afirma usar 28 * 8/1302 = 0,17 bits por transistor.
Isaacg
Como minha solução é uma solução de computador de nível muito baixo (hardware em vez de software), baseei meu byte contando em transistores. Do ponto de vista do hardware, um BIT é codificado por 6 transistores, portanto, podemos assumir que um transistor represente 1/6 bits (cerca de 0,17).
Mdahmoune
1
Eu entendo o seu ponto de vista, no entanto, a 50 bytes necessidades de código-fonte de existir em algum lugar em um hardware de concreto (transistores em geral)
mdahmoune
1
Não é apenas um ponto de vista - é um requisito do desafio. Marque sua resposta como não concorrente, pois ela não atende aos requisitos para competir nesse desafio.
Isaacg
2
Uma codificação binária simples e não compactada das informações necessárias para recriar essa solução pode usar 2 bits para o tipo de cada porta lógica (3 portas diferentes) e 10 bits para cada endereço das entradas e saídas de cada porta lógica (675 portas mais entradas e saídas). 2 * (48 + 550 + 77) + 10 * (2 * 48 + 3 * (550 + 77)) = 21120 bits = 2640 bytes.
Nnnes
1

Python 3, 50 bytes, pontuação 602

Python não é a linguagem mais detalhada, mas 50 bytes são difíceis.

lambda x:all(x.count(y)<1for y in["ful","y","er"])
L3viathan
fonte