regex for finding jumbled words

Discussion in 'Perl Misc' started by sso, Mar 11, 2009.

  1. sso

    sso Guest

    Hi, I need help figuring out the regex that would find if a word can
    be made from another word.
    For example

    apple could make pal, lap, leap
    it could not make all or peel

    Suggestions?
     
    sso, Mar 11, 2009
    #1
    1. Advertising

  2. On Mar 11, 1:00 pm, sso <> wrote:
    > Hi, I need help figuring out the regex that would find if a word can
    > be made from another word.
    > For example
    >
    > apple  could make  pal, lap, leap
    > it could not make all or peel
    >
    > Suggestions?



    Regex might not be the best strategy here.
    I'd try counting the letters into a hash,
    keyed by letter. Then you can generate a similar
    hash for words to test and loop through the keys
    to check if 'apple' has the right number of each
    letter needed to make the word in question.

    This could be very slow.

    lxt
     
    luser-ex-troll, Mar 11, 2009
    #2
    1. Advertising

  3. sso <> wrote in news:2c7d33c6-4f00-4c19-b81a-
    :

    > Hi, I need help figuring out the regex that would find if a word can
    > be made from another word.
    > For example
    >
    > apple could make pal, lap, leap
    > it could not make all or peel


    Here is a fish:

    #!/usr/bin/perl

    use strict;
    use warnings;

    my $src = 'apple';
    my @targets = qw( pal lap leap all peel );

    for my $target ( @targets ) {
    printf("'%s' %s be made from '%s'\n",
    $target,
    check( $src, $target ) ? 'can' : 'cannot',
    $src
    );
    }

    sub check {
    my ($src, $target) = @_;

    my %src;
    ++ $src{ $_ } for split //, $src;

    my @target = split //, $target;

    for my $x ( @target ) {
    return unless exists $src{ $x };
    return unless $src{ $x }--;
    }
    return 1;
    }

    __END__

    C:\DOCUME~1\asu1\LOCALS~1\Temp> t
    'pal' can be made from 'apple'
    'lap' can be made from 'apple'
    'leap' can be made from 'apple'
    'all' cannot be made from 'apple'
    'peel' cannot be made from 'apple'

    --
    A. Sinan Unur <>
    (remove .invalid and reverse each component for email address)

    comp.lang.perl.misc guidelines on the WWW:
    http://www.rehabitation.com/clpmisc/
     
    A. Sinan Unur, Mar 11, 2009
    #3
  4. sso

    C.DeRykuks Guest

    On Mar 11, 2:12 pm, luser-ex-troll <> wrote:
    > On Mar 11, 1:00 pm, sso <> wrote:
    >
    > > Hi, I need help figuring out the regex that would find if a word can
    > > be made from another word.
    > > For example

    >
    > > apple  could make  pal, lap, leap
    > > it could not make all or peel

    >
    > > Suggestions?

    >
    > Regex might not be the best strategy here.
    > I'd try counting the letters into a hash,
    > keyed by letter. Then you can generate a similar
    > hash for words to test and loop through the keys
    > to check if 'apple' has the right number of each
    > letter needed to make the word in question.
    >
    > This could be very slow.



    Another regex possibility:

    my $src = 'apple';
    my $src_sort = join '', sort split //, $src;
    my @targets = qw( pal lap leap all peel );

    for my $target ( @targets ) {
    my $target_re = join '.*?',
    sort split //,$target;
    printf( "'%s' %s be made from '%s'\n\n",
    $target,
    $src_sort =~ /$target_re/
    ? 'can' : 'cannot', $src
    );
    }

    --
    Charles DeRykus
     
    C.DeRykuks, Mar 14, 2009
    #4
  5. sso

    Guest

    On Sat, 14 Mar 2009 13:16:37 -0700 (PDT), "C.DeRykuks" <> wrote:

    >On Mar 11, 2:12 pm, luser-ex-troll <> wrote:
    >> On Mar 11, 1:00 pm, sso <> wrote:
    >>
    >> > Hi, I need help figuring out the regex that would find if a word can
    >> > be made from another word.
    >> > For example

    >>
    >> > apple  could make  pal, lap, leap
    >> > it could not make all or peel

    >>
    >> > Suggestions?

    >>
    >> Regex might not be the best strategy here.
    >> I'd try counting the letters into a hash,
    >> keyed by letter. Then you can generate a similar
    >> hash for words to test and loop through the keys
    >> to check if 'apple' has the right number of each
    >> letter needed to make the word in question.
    >>
    >> This could be very slow.

    >
    >
    >Another regex possibility:
    >
    >my $src = 'apple';
    >my $src_sort = join '', sort split //, $src;
    >my @targets = qw( pal lap leap all peel );

    ^^^^^^^^
    What is this? The example is ficticious. It has nothing
    to do with a solution, its just an example. Throw away the
    example, then answer the OP's question.

    -sln
     
    , Mar 14, 2009
    #5
  6. sso

    C.DeRykuks Guest

    On Mar 14, 2:29 pm, wrote:
    > On Sat, 14 Mar 2009 13:16:37 -0700 (PDT), "C.DeRykuks" <> wrote:
    > >On Mar 11, 2:12 pm, luser-ex-troll <> wrote:
    > >> On Mar 11, 1:00 pm, sso <> wrote:

    >
    > >> > Hi, I need help figuring out the regex that would find if a word can
    > >> > be made from another word.
    > >> > For example

    >
    > >> > apple  could make  pal, lap, leap
    > >> > it could not make all or peel

    >
    > >> > Suggestions?

    >
    > >> Regex might not be the best strategy here.
    > >> I'd try counting the letters into a hash,
    > >> keyed by letter. Then you can generate a similar
    > >> hash for words to test and loop through the keys
    > >> to check if 'apple' has the right number of each
    > >> letter needed to make the word in question.

    >
    > >> This could be very slow.

    >
    > >Another regex possibility:

    >
    > >my $src = 'apple';
    > >my $src_sort = join '', sort split //, $src;
    > >my @targets = qw( pal lap leap all peel );

    >
    >     ^^^^^^^^
    > What is this? The example is ficticious. It has nothing
    > to do with a solution, its just an example. Throw away the
    > example, then answer the OP's question.


    Check the OP's original question. I used his example.

    --
    Charles DeRykus
     
    C.DeRykuks, Mar 15, 2009
    #6
  7. "C.DeRykuks" <> wrote in
    news::

    > On Mar 11, 2:12 pm, luser-ex-troll <> wrote:
    >> On Mar 11, 1:00 pm, sso <> wrote:
    >>
    >> > Hi, I need help figuring out the regex that would find if a word
    >> > can be made from another word.
    >> > For example

    >>
    >> > apple  could make  pal, lap, leap
    >> > it could not make all or peel

    >>

    ....

    >> Regex might not be the best strategy here.


    ....


    > Another regex possibility:
    >
    > my $src = 'apple';
    > my $src_sort = join '', sort split //, $src;
    > my @targets = qw( pal lap leap all peel );
    >
    > for my $target ( @targets ) {
    > my $target_re = join '.*?',
    > sort split //,$target;
    > printf( "'%s' %s be made from '%s'\n\n",
    > $target,
    > $src_sort =~ /$target_re/
    > ? 'can' : 'cannot', $src
    > );
    > }


    Looks clever, but there is a significant disadvantage for what I
    perceive to be the requested usage scenario. In your version, a new
    regex needs to be computed from scratch each time a word is checked.

    Anyhow, here is a version that overcomes that deficiency. I don't think
    it would be very slow either.

    #!/usr/bin/perl

    use strict;
    use warnings;

    my $src = 'apple';
    my $src_re = qr{
    \A@{[ join '', map { "$_?" } sort split //, $src ]}\z
    }x;

    my @targets = qw( pal lap leap all peel );

    for my $target ( @targets ) {
    my $target_canon = join '', sort split //, $target;

    printf( "'%s' %s be made from '%s'\n\n",
    $target,
    $target_canon =~ $src_re ? 'can' : 'cannot',
    $src,
    );
    }

    __END__
    C:\DOCUME~1\asu1\LOCALS~1\Temp> s
    'pal' can be made from 'apple'

    'lap' can be made from 'apple'

    'leap' can be made from 'apple'

    'all' cannot be made from 'apple'

    'peel' cannot be made from 'apple'

    C:\DOCUME~1\asu1\LOCALS~1\Temp> t
    Rate re with_hash re_o
    re 9335/s -- -40% -43%
    with_hash 15512/s 66% -- -6%
    re_o 16469/s 76% 6% --

    #!/usr/bin/perl

    use strict;
    use warnings;

    use Benchmark qw( cmpthese );

    cmpthese -1, {

    with_hash => sub {
    my $src = 'apple';
    my @targets = qw( pal lap leap all peel );
    my %src;
    ++ $src{ $_ } for split //, $src;

    my $hash_checker = sub {
    my ($target) = @_;
    my @target = split //, $target;
    for my $x ( @target ) {
    return unless exists $src{ $x };
    return unless $src{ $x }--;
    }
    return 1;
    };

    for my $target ( @targets ) {
    my $x = $hash_checker->( $target );
    }
    },

    re => sub {
    my $src = 'apple';
    my $src_sort = join '', sort split //, $src;
    my @targets = qw( pal lap leap all peel );

    my $re_checker = sub {
    my ($target) = @_;
    my $target_re = join '.*?', sort split //,$target;
    $src_sort =~ /$target_re/;
    };

    for my $target ( @targets ) {
    my $x = $re_checker->( $target );
    }
    },

    re_o => sub {
    my $src = 'apple';
    my $src_re = qr{
    \A@{[ join '', map { "$_?" } sort split //, lc $src ]}\z
    }x;

    my @targets = qw( pal lap leap all peel );

    for my $target ( @targets ) {
    my $target_canon = join '', sort split //, lc $target;
    my $x = ( $target_canon =~ $src_re );
    }
    },
    };


    __END__

    --
    A. Sinan Unur <>
    (remove .invalid and reverse each component for email address)

    comp.lang.perl.misc guidelines on the WWW:
    http://www.rehabitation.com/clpmisc/
     
    A. Sinan Unur, Mar 15, 2009
    #7
  8. sso

    C.DeRykuks Guest

    On Mar 14, 5:29 pm, "A. Sinan Unur" <> wrote:
    > "C.DeRykuks" <> wrote innews::
    >
    > > On Mar 11, 2:12 pm, luser-ex-troll <> wrote:
    > >> On Mar 11, 1:00 pm, sso <> wrote:

    >
    > >> > Hi, I need help figuring out the regex that would find if a word
    > >> > can be made from another word.
    > >> > For example

    >
    > >> > apple  could make  pal, lap, leap
    > >> > it could not make all or peel

    >
    >> ...

    > Anyhow, here is a version that overcomes that deficiency. I don't think
    > it would be very slow either.


    Nice.

    --
    Charles DeRykus
     
    C.DeRykuks, Mar 16, 2009
    #8
  9. "C.DeRykuks" <> wrote in
    news::

    > On Mar 14, 5:29 pm, "A. Sinan Unur" <> wrote:
    >> "C.DeRykuks" <> wrote
    >> innews:5e9cf87b-bb56-4

    > :
    >>
    >> > On Mar 11, 2:12 pm, luser-ex-troll <> wrote:
    >> >> On Mar 11, 1:00 pm, sso <> wrote:

    >>
    >> >> > Hi, I need help figuring out the regex that would find if a word
    >> >> > can be made from another word.
    >> >> > For example

    >>
    >> >> > apple  could make  pal, lap, leap
    >> >> > it could not make all or peel

    >>
    >>> ...

    >> Anyhow, here is a version that overcomes that deficiency. I don't
    >> think it would be very slow either.

    >
    > Nice.


    Thanks. Your code was the inspiration that helped me see the regex
    equivalent of my earlier hash based solution.

    Sinan

    --
    A. Sinan Unur <>
    (remove .invalid and reverse each component for email address)

    comp.lang.perl.misc guidelines on the WWW:
    http://www.rehabitation.com/clpmisc/
     
    A. Sinan Unur, Mar 16, 2009
    #9
    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. Peter Strøiman
    Replies:
    1
    Views:
    2,092
    Peter Strøiman
    Aug 23, 2005
  2. Richard Heathfield
    Replies:
    7
    Views:
    365
    Barry Schwarz
    Oct 5, 2003
  3. Christoph Pingel

    regex-strategy for finding *similar* words?

    Christoph Pingel, Nov 18, 2004, in forum: Python
    Replies:
    6
    Views:
    643
    Christoph Pingel
    Nov 19, 2004
  4. utab

    Words Words

    utab, Feb 16, 2006, in forum: C++
    Replies:
    6
    Views:
    428
    Daniel T.
    Feb 16, 2006
  5. Neo
    Replies:
    3
    Views:
    569
Loading...

Share This Page