Est-ce un nom ou non?

22

Étant donné une chaîne en entrée, déterminez s'il s'agit d'un nom ou non.

Vous serez noté sur les 1000 mots anglais les plus courants, par combien vous étiquetez correctement comme nom ou non.

Le programme ou la fonction qui classe correctement la plupart de ces mots dans 50 octets ou moins gagnera.

Noms

Un nom est un mot qui représente une chose, généralement. Cela devient plus complexe, mais c'est l'idée de base.

Dans les cas où un mot pourrait être un nom ou une autre partie du discours, je l'ai classé comme un nom, même si c'est un usage rare. Ou en fait, je laisse ce site le faire pour moi.

Les mots sur lesquels vous serez noté sont ces 1000 mots courants , qui viennent de Wikipédia simple , avec "deux" et "une fois" ajoutés. De ceux-ci, ce sont les 586 noms , et ce sont les 414 non-noms . Vous pouvez trouver les trois listes ici . Notez que toutes ces entrées sont en minuscules. Ces listes sont définitives - n'essayez pas d'argumenter la grammaire.

Votre programme sera considéré comme correct s'il génère un résultat véridique sur une entrée qui est un nom et un résultat faux sur une entrée qui n'est pas un nom.

Subtilités:

Les programmes doivent avoir une sortie déterministe. Si vous voulez utiliser l'aléatoire, semez-le. Les programmes ne sont pas autorisés à utiliser des listes de noms intégrées ou d'autres fonctionnalités intégrées de partie du discours.

Exemples:

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

Veuillez indiquer le taux de réussite de votre programme dans votre réponse. Le programme ou la fonction d'au plus 50 octets avec le taux de réussite le plus élevé l'emporte. En cas d'égalité, le nombre d'octets le plus bas déterminera un gagnant. Bonne chance!

code-challenge decision-problem natural-language test-battery isaacg
la source

Réponses:

13

JavaScript (ES6), 43 octets, 622 630 633

Juste pour faire rouler la balle. Renvoie 1pour les noms, 0pour les non-noms.

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

Comment?

Nous parions sur le nom si les deux conditions suivantes sont remplies:

  1. La longueur du mot est 3, 4, 5, 6, 7, 8 ou 11. Cela se fait en décalant vers la droite le nombre binaire 100111111000 (2552 comme décimal).
  2. Le mot commence par l'une de ces lettres: bcdfghijklmpqrstvwy
Arnauld
la source
Juste au moment où j'allais commenter, avec JS spécifiquement à l'esprit, que la limite d'octets était beaucoup trop restrictive, vous postez ceci! Je pensais, sans avoir regardé la liste, qu'un meilleur score que 586 pourrait simplement être possible en testant la première lettre ou 2 dans chaque mot. Bien joué :)
Shaggy
Une explication serait bien, pour les personnes moins familiarisées avec Javascript. Pour autant que je sache, cela vérifie si la longueur du mot est 3, 4, 5, 6, 7, 8 ou 11, et le mot commence également par l'une d'un ensemble de lettres?
isaacg
@isaacg C'est exact. Explication ajoutée.
Arnauld
4
Notez que la classe de caractères [bcdf-mp-tvwy]est équivalente à la classe [^aenouxz]. Une modification permettrait d'économiser 4 octets, qui pourraient être capitalisés.
fireflame241
@ fireflame241 Très vrai. Et cela peut même être raccourci [^aenouz]car nous n'avons pas de mot commençant par a x.
Arnauld
11

Gelée , 48 octets, score 731

C'est ma toute première réponse dans Jelly et j'ai eu beaucoup de mal à mettre cela ensemble. Ah bien ... c'était amusant. :-)

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

1 octet enregistré grâce à @JonathanAllan

Essayez-le en ligne!

Ventilation et suites de tests

  • Non-noms correctement identifiés comme non-noms: 265/414 (64%)
  • Noms correctement identifiés comme noms: 466/586 (79,5%)

Comment?

Nous calculons d'abord un hachage de la chaîne d'entrée par:

  • le convertir en un entier en interprétant chaque point de code comme un chiffre de base 256
  • appliquer le modulo 4080 (choisi comme la valeur la plus efficace avec pas plus de 12 bits)
  • conserver les 8 bits les plus significatifs du résultat

Cela nous laisse un index dans [0 ... 255] et divise ainsi tous les mots en 256 groupes.

Pour chaque groupe de mots, nous pré-calculons un drapeau binaire qui est 1si le groupe contient plus de noms que de non-noms, et 0sinon. Cela conduit à un nombre N de 256 bits que nous allons utiliser comme table de recherche. Nous le stockons en tant que chaîne encodée en base 250.

Ci - dessous est la représentation binaire de N .

1000011000001011000101111011111001001101110010101101110010001101
0000010001101010010111110001110010010101110110110010111111010000
0001111010011110000110101011111000011110111011010011011110101100
1010010110101111000010101000101100000001110110100011111000101010

Qui peut être stocké comme “Ạ$ⱮẊḲḲLÑMṆụ⁻ẉṂ`ŻvḤæɠ5ṭȯƁU*×TdƲḥ`’dans Jelly.

D'où le code:

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
la source
Bon travail! Enregistrez un octet pour démarrer O‘ḅ⁹%⁽€Oæ»4“Ạ$ⱮẊḲḲLÑMṆụ⁻ẉṂ`ŻvḤæɠ5ṭȯƁU*×TdƲḥ`’æ»Ḃ(notez également que vous pouvez utiliser le pied de page sur TIO, j'irais avec Ç€¬S,Let Ç€S,Lpour vos deux suites de tests.
Jonathan Allan
@JonathanAllan Merci pour les conseils!
Arnauld
10

JavaScript (ES6), 50 octets, score 693

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

Il suffit de rechercher tous les modèles possibles que les non-noms ont que les noms n'ont pas.

Les non-noms contiennent plus souvent:

  1. a, o, u ou z comme première lettre.
  2. e comme les deux premières lettres.
  3. Deux lettres seulement. [Pensez aux pronoms (moi, nous, nous, lui, il) et aux prépositions (de, à, dans, sur, par, à, en haut, ...).]
  4. e , suivi d'une ou plusieurs lettres, suivi de e ou y .
  5. f, l ou o , suivi d'une lettre, suivi de r .
  6. a , suivi d'une lettre, suivi de p .

Fragment:

Afficher l'extrait de code

Rick Hitchcock
la source
Je crois que vous pouvez enregistrer un octet en changeant le premier regex en /h|n/(ou en faisant /^.[hn]/.test(s)), et un autre en changeant s[2]>''en soit !!s[2]ou 2 in s.
ETHproductions
Merci, @ETHproductions. Je peux utiliser vos suggestions et combiner les deux tests pour économiser un tas d'octets, ce qui m'a permis d'ajouter du code pour améliorer mon score.
Rick Hitchcock
N'est-ce pas a.predondant puisque vous l'avez déjà fait [aouz]?
AdmBorkBork
@AdmBorkBork, le a in [aouz]n'est mis en correspondance qu'au début de la chaîne. Pour une raison quelconque, tester a.p n'importe où dans la chaîne améliore le score.
Rick Hitchcock
10

Gelée , 50 octets , score 763

Utiliser un hachage maintenant (un peu comme la réponse d'Arnauld Jelly )

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

Essayez-le en ligne!

250/414 pour non-noms
513/586 pour les noms
Total = 250 + 513 = 763.

Comment?

Construit une table avec 308 entrées, soit 1 (identifiant un nom) ou 0 (identifiant un non-nom) et les indexe à l'aide d'une clé fournie par une fonction de hachage qui utilise le produit des ordinaux du mot d'entrée:

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)

Précédent:  50  47 octets , score 684

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

Un lien monadique prenant un mot et renvoyant une liste d'un caractère (véridique) si le mot est identifié comme un nom, ou une liste vide ou zéro (les deux falsey) s'il ne l'est pas.

Essayez-le en ligne! (le pied de page effectue un if else sur le résultat à imprimerNounouNon-Noun)
... ou voir le programme de notation (compte les index véridiques sur les deux listes, puis calcule le score).

Répartition des scores: 462/586 noms correctement identifiés (124 incorrects), 222/414 non-noms correctement identifiés (192 incorrects) - total correct = 684/1 000.

Comment?

Je suppose que ce n'est pas un nom si ...

  • le dernier caractère et le caractère deux avant qui sont égaux (avec indexation modulaire et basée sur 1)
  • l'une des deux premières sous-chaînes de longueur 2 se trouve dans:
    'be', 'th', 'le', 'he', 'm ', 'ev', 'et', 's ', 'fl', 'ax', 'en', 'fo', 'am', 'az' (remarque: 'm 'et's ' ne sont là que pour faciliter la compression, mais elles n'apparaissent jamais de toute façon)
  • L' indice -299 ème (avec indexation modulaire et basée sur 1) est l'un des:
    aenouyz(bien que cela soit implémenté inversement et avec des majuscules en excès)
    ... puisque les mots ont tous une longueur comprise entre 1 et 11, l' indice -299 ème est équivalent à utiliser la longueur pour indexer le mappage:{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 octets, score: 638

Un premier coup bas (étendu ci-dessus)

ØY⁾niyṖf⁽ż2ị$
Jonathan Allan
la source
0,-2ne veut pas dire que pair zero with -2cela signifieliteral [0, -2]
Erik the Outgolfer
Mais c'est le même effet: p
Jonathan Allan
non ce n'est pas 0,-2un nilad, pas séparé (0)(,)(-2)... bien sûr c'est le même effet dans ce cas mais pas toujours. J'ai appris à la dure ... et quoi qu'il en soit, je préférerais de toute façon expliquer ce qui se passe réellement au lieu de quelque chose avec le même effet ou quelque chose.
Erik the Outgolfer
Si j'avais écrit «joindre» plutôt que «paire», auriez-vous commenté «aucune jointure n'est j»?
Jonathan Allan
Je pourrais être un peu pédant, mais pairou joinsont évidemment de mauvaises manières de le formuler, car 0,-2,-6par exemple ne signifie pas pair 0 with -2 and then pair that with -6 = [[0, -2], -6]mais signifie plutôt literal [0, -2, -6]. Je comprends, l' , atome et le ...,...(,...(...)) littéral prêtent à confusion ... mais ce 0,-2,-6n'est pas tout à fait la même chose 0,-2;-6puisque le premier est à 1 lien et le dernier à 3 liens.
Erik the Outgolfer
2

Julia 34 octets, 609

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

Je voulais économiser sur les personnages en utilisant le hachage intégré. J'ai l'impression qu'il doit y avoir un moyen de faire mieux. Julia n'est tout simplement pas assez amicale avec les opérations de frappe que je veux utiliser pour améliorer cela, je pense.

Trouver des masques de bit appropriés pour le hachage pour les séparer est un jeu intéressant.

Lyndon White
la source
Meilleure solution;)
tamasgal
2

Python 2 , 50 octets, précision: 596

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

Essayez-le en ligne!

Vérifie simplement la première lettre, la longueur et si "st" est dans le mot Code suppose que le mot est défini comme x (Edit: Merci à issacg pour la correction du code de l'extrait à la fonction)

Husnain Raza
la source
Salut, bienvenue sur le site. Bien que cela soit intéressant, les soumissions doivent être des fuctions ou des programmes complets. Il s'agit d'un extrait de code, qui n'est pas autorisé. Voir ceci Essayez-le en ligne! lien pour un moyen de convertir cet extrait de code en une fonction tout en exécutant le même code.
isaacg
2

Haskell, 36 octets, 626 631

f x=length x>2&&x!!0`notElem`"aenou"
BlackCap
la source
643 si quelqu'un a une langue plus courte: length x>2&&(x!!0`notElem`"aenou"||x!!1`elem`"acqrsty")
BlackCap
2

Implémentation de la porte logique à 2 niveaux, pas 50 octets, score 1000

  1. Branchez simplement la représentation binaire du mot donné aux 88 entrées

    1. compléter le mot saisi par des espaces à droite si la longueur du mot est inférieure à 11
    2. Code ASCII 8 bits pour chaque lettre du mot d'entrée

  2. Le circuit renvoie 1 si le mot est un nom et renvoie 0 sinon

  3. Les lignes pointillées bleues correspondent aux entrées jamais utilisées

Cette mise en œuvre a besoin

  1. 48 transistors pour coder toutes les portes des onduleurs
  2. 1100 transistors pour coder toutes les portes ET
  3. 154 transistors pour coder la porte OU
  4. Total de 1302 transistors, ce qui représente moins de 28 octets.

Quelques mesures

  1. Un porte inverseuse nécessite 1 transistor
  2. Un simple 2 entrées porte OU nécessite 2 transistors
  3. Un simple 2 entrées porte ET nécessite 2 transistors
  4. Un bit a besoin de 6 transistors

entrez la description de l'image ici

Circuit.pdf en pleine résolution ici

Circuit.png pleine résolution ici

mdahmoune
la source
2
Pourriez-vous expliquer exactement quel est votre système de codage de ce circuit en octets? Je suis très confus sur la façon dont vous prétendez utiliser 28 * 8/1302 = 0,17 bits par transistor.
isaacg
Comme ma solution est une solution informatique de très bas niveau (matériel plutôt que logiciel) j'ai basé mon octet en comptant sur des transistors. Du point de vue matériel, un BIT est codé par 6 transistors, nous pouvons donc supposer qu'un transistor représente 1/6 bit (environ 0,17).
mdahmoune
1
Je comprends votre point de vue, mais la source de code de 50 octets doit exister quelque part sur un matériel concret (transistors en général)
mdahmoune
1
Ce n'est pas seulement un point de vue - c'est une exigence du défi. Veuillez marquer votre réponse comme non concurrente, car elle ne répond pas aux exigences pour participer à ce défi.
isaacg
2
Un codage binaire simple et non compressé des informations requises pour recréer cette solution pourrait utiliser 2 bits pour le type de chaque porte logique (3 portes différentes) et 10 bits pour chaque adresse des entrées et sorties de chaque porte logique (675 portes plus entrées et sorties). 2 * (48 + 550 + 77) + 10 * (2 * 48 + 3 * (550 + 77)) = 21120 bits = 2640 octets.
Nnnes
1

Python 3, 50 octets, score 602

Python n'est pas le langage le plus verbeux, mais 50 octets est difficile.

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