6
votes

Trouvez le mot avec la plupart des lettres en commun avec d'autres mots

Je veux Perl (5.8.8) Pour savoir quel mot a le plus de lettres en commun avec les autres mots dans une matrice - mais seulement des lettres au même endroit. (Et de préférence sans utiliser de libs.)

Prenez cette liste de mots comme exemple: p>

  • Baker LI>
  • Saler Li>
  • Baler Li>
  • CARER LI>
  • ruffr li> ul>

    Son baller est le mot qui a le plus de lettres en commun avec les autres. Il correspond à Baxer à Baker, Xaler in Saler, Xaxer à Career et XXXXR à Ruffr. P>

    Je veux Perl de trouver ce mot pour moi dans une liste arbitraire de mots avec la même longueur et le même cas. On dirait que j'ai frappé le mur ici, alors l'aide est très appréciée! P>

    Ce que j'ai essayé jusqu'à présent h2>

    N'ayez pas vraiment une grande partie d'un script pour le moment:

    #!/usr/bin/perl
    # See if one word has equal letters as the other, and how many of them are equal
    use strict;
    use warnings; 
    
    my $checkword = "APPRECIATION"; # the word to be checked
    my $match = 4; # equal to the match you got from testing your checkword
    my @checkletters = split(//, $checkword); #/
    
    my @wordlist = qw(
        PARTNERSHIPS
        REPRIMANDING
        CIVILIZATION
        APPRECIATION
        CONVERSATION
        CIRCUMSTANCE
        PURIFICATION
        SECLUSIONIST
        CONSTRUCTION
        DISAPPEARING
        TRANSMISSION
        APPREHENSIVE
        ENCOUNTERING
    );
    
    print "$checkword has $match letters in common with:\n";
    
    foreach my $word (@wordlist) {
        next if $word eq $checkword;
        my @letters = split(//, $word);
        my $length = @letters; # determine length of array (how many letters to check)
    
        my $eq_letters = 0; # reset to 0 for every new word to be tested
        for (my $i = 0; $i < $length; $i++) {
            if ($letters[$i] eq $checkletters[$i]) {
                $eq_letters++;
            }
        }
        if ($eq_letters == $match) {
            print "$word\n";
        }
    }
    # Now to make a script on to find the best word to check in the first place...
    


3 commentaires

Pouvez-vous nous montrer votre script, nous avons donc quelque chose à faire?


Peut-être que le moyen le plus simple de résoudre ce problème est de calculer le Hamming Distance entre les mots. Cependant, je me demande s'il ne peut comparer que deux et deux mots ...


J'ai examiné la FAQ sur le piratage et cela semble être une tâche prolog serait applicable à Perl Thoug.


8 Réponses :


2
votes

Je n'ai pas touché Perl depuis un moment, alors pseudo-code c'est. Ce n'est pas l'algorithme le plus rapide, mais cela fonctionnera bien pour une petite quantité de mots. XXX

Désolé pour le manque de Perl, mais si vous le codez dans Perl, cela devrait fonctionner comme Un charme.

Remarque rapide sur l'exécution: cela fonctionnera dans le temps number_of_words ^ 2 * longueur_of_words , donc sur une liste de 100 mots, chacun de 10 caractères, Cela fonctionnera dans 100 000 cycles, ce qui est adéquat pour la plupart des applications.


3 commentaires

Cool! Je pense que c'est l'approche que j'ai utilisée dans ma propre tentative de répondre à la question. Cependant, après avoir lu sur le sujet, je me demande maintenant comment vous pourriez faire le modèle dans une recherche de style arborescent ternraine?


Je suis sûr qu'il y a des tonnes de façons d'y aller ... et je serais heureux de l'explorer. En tant que simple question à vous: quelle est l'ampleur de l'entrée que vous envisagez? Quel niveau d'efficacité espérez-vous réaliser?


Je réalise que la portée de ce projet ne vaut pas la peine, mais pour le plaisir, disons beaucoup!



5
votes

comme point de départ, vous pouvez vérifier efficacement le nombre de lettres qu'ils ont en commun avec: xxx

mais ce n'est utile que si vous bouclez toutes les paires de mots possibles, quelque chose qui ' T nécessaire dans ce cas: xxx


12 commentaires

J'ai vraiment apprécié de taper la logique et de voir un exemple de travail de Lingua :: fr :: inflectez. Mais j'ai une question. Maintenant que vous savez combien de lettres communes chaque mot a, comment déterminez-vous quel mot correspondait au plus de lignes de chaque position de Colunn? Vous n'avez pas besoin de garder un score cumulatif du nombre de lignes correspondant à chaque colonne? (Peut-être que je rends la spécification trop difficile).


LINGUA :: EN :: L'influence facilite la pluralisation; Exemple plus complexe: impression infléchissez ("Num ($ _) pl_n (Nation) PL_V (endosses) mais PL_V (n'est pas) approuvé") pour 0..2


J'aime vraiment celui-ci, et surtout la première ligne, car c'est un moyen élégant de comparer deux mots. Maintenant, comparer le mot de liste pour que le mot pour trouver le mot qui a le plus de lettres en commun à la même position de lettre, c'est-à-dire le mot qui a le plus en commun avec les autres mots à la lettre POS 0, puis la lettre pos 1, et ainsi au. La lib ne travaille pas sur mon Mac, ...


"The Lib" Être Lingua :: EN :: Inflectez-vous? Ce n'est pas du tout essentiel ici, mais je me demande ce que "ne fonctionne pas" signifie?


Wow, oui! Merci beaucoup! : D seulement problème maintenant, est-ce que je ne comprends pas la moitié de ce que vous avez fait ... Je suis un noob! La lib n'est tout simplement pas installée, mais là encore, c'est pour le meilleur si vous n'avez pas à installer des choses pour effectuer un travail de script.


@Kebman: Regardez-la un peu à la fois; Démarrage de données de données avec par exemple. Données d'impression :: Dumper :: Dumper (\% max_common_letters_words) Pour voir quelles données il se rassemble; Demandez ici si un bit en particulier vous souche


Re: Installation, c'est aussi mieux si vous utilisez le code testé par d'autres personnes au lieu de réécrire les choses (ou souvent dans le cas de la pluralisation correcte, laissant votre script marginalement faux) :)


Utilisation de ($ Word1 ^ $ Word2) est un piratage propre, mais il ne fonctionnera que pour les caractères ASCII. Une fois vos données contenant des caractères Unicode multibyte (E.G.: Voyeuses accentuées), les caractères des mots étant comparés se terminent malalignés.


Ongled mclean: pas vrai (tant que Perl sait que les données de caractère)


@ysth: J'essaie d'apprendre de votre code (bien fait), j'ai essayé d'utiliser une HOH dans mon ANS, mais vous éliminez la cascade de la boucle (je pense en utilisant un hohoa?). (1) est push @ {$ max_common ... juste un moyen d'utiliser la poussée pour un hachage (c'est une "tranche" à droite)? (2) J'ai gardé «se perdre» lors de la réflexion sur ma structure de données et «où j'étais» (surtout pendant le tri), faites-vous d'aller mieux avec l'expérience (ou des conseils)? MERCI!


PUSH @ {...} ajoute à un tableau dont la référence est donnée sur le bloc (dans ce cas où se trouve la valeur d'une HOH, donnant à une hohoa). Cela peut également autovivifier, mais dans ce code ne le fera jamais. Donc, non, il n'y a pas de tranches ici. Il aide à avoir fermement la source de données à l'esprit lorsque vous regardez le code; Entrantez avec le débogueur et inspecter comme vous pouvez vous aider.


@ysth: excuses, avant de prétendre que le truc Xor n'a pas fonctionné avec des données non ASCII, je l'ai testé. Malheureusement, mon test utilisé '\ x {101}' au lieu de "\ x {101}" - oups.



4
votes

Voici un script complet. Il utilise la même idée que YSTH mentionné (bien que je l'avais indépendamment). Utilisez Bitwise Xor pour combiner les chaînes, puis compter le nombre de nuls dans le résultat. Tant que vos chaînes sont ASCII, cela vous dira combien de lettres assorties. (Cette comparaison est sensible à la casse, et je ne suis pas sûr de ce qui se passerait si les chaînes étaient UTF-8. Probablement rien de bon.) XXX


0 commentaires

7
votes

Voici un moyen. Après avoir relu votre spécification plusieurs fois, je pense que c'est ce que vous recherchez.

Il convient de mentionner qu'il est possible qu'il y aura plus d'un mot avec un score supérieur égal. De votre liste Il n'y a qu'un seul gagnant, mais il est possible qu'à des listes plus longues, il y aura plusieurs mots tout aussi gagnants. Cette solution traite de cela. De plus, si je comprends bien, vous ne comptez que des correspondances uniquement si elles se produisent dans la même colonne par mot. Si tel est le cas, voici une solution de travail: p>

Testing force method: 39 matches.
APPRECIATION
Testing hash  method: 39 matches.
APPRECIATION
        Rate Force  Hash
Force 2358/s    --  -74%
Hash  9132/s  287%    --


6 commentaires

Tu as tout à fait raison! Ce sont le genre de matchs que je suis après. Cependant, j'aimerais vraiment une version qui fonctionne avec Perl version 5.8.8.


Sortez la ligne qui dit Utiliser 5.012; Remplacer les instructions " " "" < Imprimer ", et mettez un \ \ n nouvelle ligne, comme ceci: Imprimer "mots avec la plupart des correspondances: \ n"; Imprimer "$ \ n" pour @words [@max_ixs]; . Maintenant, vous avez une version qui fonctionne pour 5.8.8! J'espère que vous trouverez une utilisation amusante pour cela. Je n'ai pas compris quel problème vous résolvez avec cela, mais c'était une diversion amusante déterminant la logique.


Merci beaucoup! : D Voici ce que je veux résoudre: Gamefaqs.com/pc/ 918428-Fallout-3 / FAQ / 54644 Maintenant je me demande, pouvez-vous supprimer la lib? Ou est-ce par défaut avec la plupart des installations Perl?


La seule chose qui se fait avec la liste :: Utils trouve le max. Vous pouvez faire la même chose en mettant les lignes suivantes dans le code (et en supprimant le My $ max = max = max (... ligne): juste avant " mon @scores; ", mettre" mon $ max = 0; "juste avant" push @scores ... "Mettez $ max = ($ SCORE> $ max = )? $ Score: $ max; . Enfin, supprimez la liste Liste d'utilisation :: Utils .. Ligne. Quelque chose d'autre avant que ma réponse puisse répondre à vos besoins? Amusez-vous.


Nah, homme. C'est génial! : D Maintenant, j'ai juste besoin de bricoler les différentes manières de le faire pour apprendre comment cela fonctionne. Je suppose que je n'aurais pas posté ici n'étant pas pour cela, j'ai encore beaucoup à apprendre. Merci encore! :)


Je me demande, cela pourrait-il être rendu encore plus efficace avec un arbre de recherche ternaire?



0
votes

Vous pouvez le faire, à l'aide d'un truc de regex sale pour exécuter du code si une lettre correspond à sa place, mais pas autrement, heureusement, il est très facile de construire les expressions que vous allez:

Un exemple d'expression régulière est: < / p> xxx

ceci peut être rapide ou ne peut pas être rapide. xxx

Utiliser XOR Trick sera rapide mais suppose beaucoup de choses sur la gamme des caractères que vous pourriez rencontrer. Il y a de nombreuses façons dans lesquelles UTF-8 va rompre avec ce cas.


3 commentaires

Pas besoin d'une solution O (n ** 2) ici (que le XOR aurait également été); Je pense que ce double compte si une lettre de votre mot correspond à plusieurs candidats. En outre, ^ devrait fonctionner simplement bien sur UTF8.


Relire la question, il devrait compter plusieurs fois si une lettre du mot correspond à plusieurs autres mots, désolé.


Oui, c'était un joli petit casse-tête quand même. J'aime la meilleure approche de hachage et j'aurais vraiment dû essayer d'abord.



1
votes

Voici ma tentative d'une réponse. Cela vous permettra également de voir chaque match individuel si vous en avez besoin. (c.-à-d. Baler correspond à 4 caractères de Baker). edit : il attrape maintenant tous les matchs s'il y a une cravate entre les mots (j'ai ajouté "Caker" à la liste à tester). XXX

La sortie est simplement: Caker Baller and Baker.

Le hachage % Wordcomparison ressemble à: xxx


0 commentaires

1
votes

Voici une version qui s'appuie sur la transposition des mots afin de compter les caractères identiques. J'ai utilisé les mots de votre comparaison initiale, pas le code.

Ceci devrait fonctionner avec n'importe quel mot de longueur, et toute liste de longueur. La sortie est la suivante: xxx

le code: xxx


0 commentaires

0
votes

Merci beaucoup à tous les contributeurs! Vous m'avez certainement montré que j'ai encore beaucoup à apprendre, mais vous m'avez également aidé énormément pour travailler ma propre réponse. Je viens de le mettre ici pour référence et commentaires possibles, car il y a probablement de meilleures façons de le faire. Pour moi, c'était l'approche la plus simple et la plus simple que je puisse trouver moi-même. Enjã¸y! :) xxx

Lors de l'exécution, le script donne les éléments suivants: xxx


0 commentaires