Matching words and letters

Discussion in 'Perl Misc' started by Sandman, Dec 8, 2004.

  1. Sandman

    Sandman Guest

    I just can't seem to wrap my mind around how to attack this problem in the best
    way, so I thought I'd just post here and see if anyone here has done something
    similar and/or has a logical solution to it.

    I have a series of letters, say "kljetilamnop", then I have a big textfile with
    legit words, but let's use a short one here:

    mall
    bill
    kill
    lot
    pile
    antilope
    hello

    Now, I want to cycle through this word list and match it to the letters, and
    return true if the word can be formed by the letters. So, the above would
    return:

    mall
    kill
    lot
    antilope

    The result is to be used in a Scrabble-like fashion, which leads me to the
    other part of my problem. When matching these words, I need to be able to
    specify that some of the characters are "locked" in their position. So, lets
    say that the letter "k" in the letter string is a fixed letter, then the only
    result would be "kill" of course. I imagine that this would be easiest if I fed
    the function the string and also the locked position in an array (1,6,8 for
    example).

    Anyway, this could easily become really complex, and if I just get the basic
    scrambled-letters to match to words, I think I can manage my way from there.
    So, any help appreciated.

    --
    Sandman[.net]
     
    Sandman, Dec 8, 2004
    #1
    1. Advertising

  2. Sandman

    Jim Keenan Guest

    Sandman wrote:


    >
    > Anyway, this could easily become really complex, and if I just get the basic
    > scrambled-letters to match to words, I think I can manage my way from there.
    > So, any help appreciated.
    >

    See if the is_LsubsetR() method of my CPAN module List::Compare
    (http://search.cpan.org/~jkeenan/List-Compare-0.31/Compare.pm) is useful
    to you.

    jimk
     
    Jim Keenan, Dec 8, 2004
    #2
    1. Advertising

  3. Sandman <> wrote in
    news::

    > I have a series of letters, say "kljetilamnop", then I have a big
    > textfile with legit words, but let's use a short one here:
    >
    > mall
    > bill
    > kill
    > lot
    > pile
    > antilope
    > hello
    >
    > Now, I want to cycle through this word list and match it to the
    > letters, and return true if the word can be formed by the letters. So,
    > the above would return:
    >
    > mall
    > kill
    > lot
    > antilope


    pile should be in that list as well.

    Now, undoubtedly, there is a better way to do this, but here is something
    that works for the data you posted:

    #! /usr/bin/perl

    use strict;
    use warnings;

    use Data::Dumper;

    my $source = normalize('kljetilamnop');

    LINE: while(my $word = <DATA>) {
    chomp $word;
    my $target = normalize($word);
    for my $c (keys %{ $target }) {
    next LINE unless(
    defined($source->{$c}) && ($source->{$c} >= $target->{$c})
    );
    }
    print "$word\n";
    }

    sub normalize {
    my ($string) = @_;
    my @letters = split //, $string;
    my %count;
    $count{$_}++ for (@letters);
    return \%count;
    }



    __DATA__
    mall
    bill
    kill
    lot
    pile
    antilope
    hello

    D:\Home\Dload>perl rs.pl
    mall
    kill
    lot
    pile
    antilope

    > which leads me to the other part of my problem.


    I am going to ignore that part.

    > So, any help appreciated.


    Hope this helps.

    Sinan.
     
    A. Sinan Unur, Dec 9, 2004
    #3
  4. Sandman

    Anno Siegel Guest

    Sandman <> wrote in comp.lang.perl.misc:
    > I just can't seem to wrap my mind around how to attack this problem in the best
    > way, so I thought I'd just post here and see if anyone here has done something
    > similar and/or has a logical solution to it.
    >
    > I have a series of letters, say "kljetilamnop", then I have a big textfile with
    > legit words, but let's use a short one here:
    >
    > mall
    > bill
    > kill
    > lot
    > pile
    > antilope
    > hello
    >
    > Now, I want to cycle through this word list and match it to the letters, and
    > return true if the word can be formed by the letters. So, the above would
    > return:
    >
    > mall
    > kill
    > lot
    > antilope


    [snip other requirements]

    One way of looking at this is to consider a string (word, or list of
    available letters) as a multiset of its letters. A multiset is like
    a set, but each element can appear with a multiplicity. The bag of
    available letters, for instance, would contain each letter of
    "kjetiamnop" once and the letter "l" twice.

    A word can be built from the given letters when its bag is contained
    (in the obvious sense of multisets) in the bag of given letters.

    Fortunately, there is a CPAN module that implements bags. Unfortunately,
    the implementation doesn't have a "contained" method, so we'll have to
    extend the class. Fortunately, the class is well-written, so inheritance
    makes this easy:


    #!/usr/local/bin/perl
    use strict; use warnings; $| = 1;

    my $letters = CBag->new->insert( map { $_ => 1 } split //, 'kljetilamnop');

    while ( <DATA> ) {
    chomp;
    my $word = CBag->new->insert( map { $_ => 1 } split //);
    print "$_\n" if $word <= $letters;
    }

    # Extend Set::Bag to support comparison
    {{
    package CBag;
    use base 'Set::Bag';

    sub contained {
    my ( $bag, $other) = @_;
    for ( $bag->elements ) {
    return 0 if $bag->grab( $_) > ( $other->grab( $_) || 0);
    }
    return 1;
    }

    use overload(
    '<=' => 'contained',
    );

    }}

    __DATA__
    mall
    bill
    kill
    lot
    pile
    antilope
    hello
     
    Anno Siegel, Dec 9, 2004
    #4
  5. Sandman wrote:

    [ elaborate problem description deleted ]

    A very simple/simplistic solution:

    my @words = qw(mall bill kill lot pile antilope hello);
    my $fixed = 'k';
    my $set = 'ljetilamnop' . $fixed;

    foreach (@words) {
    print "$_\n" if m/[$fixed]/ && m/^[$set]*$/;
    }

    --
    Josef Möllers (Pinguinpfleger bei FSC)
    If failure had no penalty success would not be a prize
    -- T. Pratchett
     
    Josef Moellers, Dec 9, 2004
    #5
  6. Josef Moellers <> wrote in
    news:cp9ega$6bb$-siemens.com:

    > Sandman wrote:
    >
    > [ elaborate problem description deleted ]
    >
    > A very simple/simplistic solution:
    >
    > my @words = qw(mall bill kill lot pile antilope hello);
    > my $fixed = 'k';
    > my $set = 'ljetilamnop' . $fixed;
    >
    > foreach (@words) {
    > print "$_\n" if m/[$fixed]/ && m/^[$set]*$/;
    > }
    >


    How is this a solution?

    D:\Home>perl tttt.pl
    kill

    Sinan
     
    A. Sinan Unur, Dec 10, 2004
    #6
  7. Sandman

    Sandman Guest

    In article <Xns95B9F00E0493asu1cornelledu@132.236.56.8>,
    "A. Sinan Unur" <> wrote:

    > pile should be in that list as well.


    Yes, sorry. :)

    > Now, undoubtedly, there is a better way to do this, but here is something
    > that works for the data you posted:


    Yes, and I've adapted it for my uses - it works great!

    ##########################

    #!/usr/bin/perl
    use strict;
    use warnings;
    use Data::Dumper;
    exit unless $ARGV[0];
    $|=1; # Dont buffer output

    my %words;

    open(FILE, "</home/sandman/conf/rim.db"); # file with legal words
    while (<FILE>)
    {
    chomp;
    my @list=split (/\t/);
    foreach (@list){
    # no need to include too long words.
    next if length($_) > (length($ARGV[0])+1);
    # And we don't care for too short words
    next if length($_) < 3;
    $words{lc($_)}++;
    }
    }

    my $source = normalize($ARGV[0]);
    my $prnr;
    my $word;

    LINE: foreach $word (keys %words){
    chomp $word;
    my $target = normalize($word);
    for my $c (keys %{ $target }) {
    next LINE unless(
    defined($source->{$c}) && ($source->{$c} >= $target->{$c})
    );
    }
    my @input = split //, $ARGV[0];
    my @match = split //, $word;
    if ($ARGV[1]){
    foreach (split /,/, $ARGV[1]){
    # for every fixed position
    next LINE unless $input[($_-1)] eq $match[$_-1];
    }
    }
    printf "%-12s ", $word;
    $prnr++;
    print "\n" if ($prnr % 6) == 0;
    }
    print "\n";

    sub normalize {
    my ($string) = @_;
    my @letters = split //, $string;
    my %count;
    $count{$_}++ for (@letters);
    return \%count;
    }

    ##########################

    sandman~> alfapet kamrslsi 1,2
    kali kams kari karl karm kass
    kal kam kar kas

    ##########################

    These are swedish words, so it's quite correct.

    Thank you!

    --
    Sandman[.net]
     
    Sandman, Dec 10, 2004
    #7
  8. Sandman

    Anno Siegel Guest

    Sandman <> wrote in comp.lang.perl.misc:
    > I just can't seem to wrap my mind around how to attack this problem in the best
    > way, so I thought I'd just post here and see if anyone here has done something
    > similar and/or has a logical solution to it.
    >
    > I have a series of letters, say "kljetilamnop", then I have a big textfile with
    > legit words, but let's use a short one here:
    >
    > mall
    > bill
    > kill
    > lot
    > pile
    > antilope
    > hello
    >
    > Now, I want to cycle through this word list and match it to the letters, and
    > return true if the word can be formed by the letters. So, the above would
    > return:
    >
    > mall
    > kill
    > lot
    > antilope


    Yet another way:

    while ( <DATA> ) {
    chomp;
    ( my $x = $_) =~ tr/kljetilamnop//d;
    print "$_\n" unless length $x;
    }

    Anno
     
    Anno Siegel, Dec 10, 2004
    #8
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. r holland
    Replies:
    7
    Views:
    288
    Michael Sparks
    Aug 23, 2004
  2. Ivan Shevanski

    noob question Letters in words?

    Ivan Shevanski, Oct 8, 2005, in forum: Python
    Replies:
    8
    Views:
    297
    Clint Norton
    Oct 9, 2005
  3. Ivan Shevanski

    Re: noob question Letters in words?

    Ivan Shevanski, Oct 8, 2005, in forum: Python
    Replies:
    2
    Views:
    239
    Steven D'Aprano
    Oct 8, 2005
  4. Merrigan
    Replies:
    4
    Views:
    575
    Chris
    Dec 14, 2007
  5. Venugopal
    Replies:
    11
    Views:
    1,534
    Tassilo v. Parseval
    Nov 5, 2003
Loading...

Share This Page