Fun problem: Overlapping words

Discussion in 'Perl Misc' started by Stuart Moore, Nov 12, 2004.

  1. Stuart Moore

    Stuart Moore Guest

    A bit of a poser for anyone bored:

    I was chatting with some friends, and we were trying to work out
    suitable strings of letters which could have spaces and punctuation in
    different places to produce different sentences

    e.g.

    Therestopenlarge

    parses to

    There stop enlarge
    or
    The rest open large

    Anyone have an idea of a good perl program to work these out? My
    thoughts so far involved grabbing words from /usr/share/dict/words (or
    whatever the equivalent is on your system) and loading them into a hash
    so it's quick to see if foo is a word; choosing one at random (e.g.
    there); trying to find a subword (e.g. the), then looking for a word
    starting with the difference (e.g. re.*) until you end up with a
    suitable string. Then repeat.

    My hope is to find some that make sense, but I'm not optimistic.

    Hope that some of you are interested by the challenge.
    Stuart Moore, Nov 12, 2004
    #1
    1. Advertising

  2. Stuart Moore wrote:
    > A bit of a poser for anyone bored:
    >
    > I was chatting with some friends, and we were trying to work out
    > suitable strings of letters which could have spaces and punctuation in
    > different places to produce different sentences
    >
    > e.g.
    >
    > Therestopenlarge
    >
    > parses to
    >
    > There stop enlarge
    > or
    > The rest open large
    >
    > Anyone have an idea of a good perl program to work these out? My
    > thoughts so far involved grabbing words from /usr/share/dict/words (or
    > whatever the equivalent is on your system) and loading them into a
    > hash so it's quick to see if foo is a word; choosing one at random
    > (e.g. there); trying to find a subword (e.g. the), then looking for a
    > word starting with the difference (e.g. re.*) until you end up with a
    > suitable string. Then repeat.
    >
    > My hope is to find some that make sense, but I'm not optimistic.
    >
    > Hope that some of you are interested by the challenge.


    Well, this has little to do with Perl, but an exhaustive brute force search
    should be easy to implement.
    - sort all your words by length, shortest first.
    - try to match each word against the beginning of the string.
    - when you found a match try matching the rest of the string over again;
    - if the rest of the string resolves, then you found a solution
    - if the rest of the string doesn't resolve, then continue searching for
    a different matching beginning

    Of course this is probably not the smartest approach. After all this looks
    like an NP-complete problem.

    jue
    Jürgen Exner, Nov 12, 2004
    #2
    1. Advertising

  3. On Fri, 12 Nov 2004 17:12:22 +0000, Stuart Moore wrote:

    > I was chatting with some friends, and we were trying to work out suitable
    > strings of letters which could have spaces and punctuation in different
    > places to produce different sentences
    >
    > e.g.
    >
    > Therestopenlarge
    >
    > parses to
    >
    > There stop enlarge
    > or
    > The rest open large


    It might be only a beginning, but the following snippet finds at least one
    of these solutions at my system:

    #!/usr/bin/perl

    use strict;
    use warnings;

    open WORDS,'<','/usr/share/dict/american-english' or die "Can't open word list";
    chomp( my @word = sort {- (length($a) <=> length($b))} (<WORDS>) );
    close WORDS;

    my $string = 'Therestopenlarge';

    foreach (grep $_, @word) {
    $string =~ s/(\A[^{]*|\}[^{]*)($_)/$1\{$2\}/gsi;
    }

    $string =~ tr/}{/ /d;

    print $string;


    Of course this snippet isn't very optimized (but for at least quick
    written), and it prefers to find long words instead of short words.

    (An idea to find alternative solutions might be to remove brackets around
    some (or all) words after finding a solution und restart the algorithm
    without an already found word, so it has to find another solution - but in
    my opinion it's your problem to do it as it is also your problem :))


    Greetings,
    Janek
    Janek Schleicher, Nov 12, 2004
    #3
  4. Stuart Moore

    Anno Siegel Guest

    Stuart Moore <> wrote in comp.lang.perl.misc:
    > A bit of a poser for anyone bored:
    >
    > I was chatting with some friends, and we were trying to work out
    > suitable strings of letters which could have spaces and punctuation in
    > different places to produce different sentences
    >
    > e.g.
    >
    > Therestopenlarge
    >
    > parses to
    >
    > There stop enlarge
    > or
    > The rest open large
    >
    > Anyone have an idea of a good perl program to work these out? My
    > thoughts so far involved grabbing words from /usr/share/dict/words (or
    > whatever the equivalent is on your system) and loading them into a hash
    > so it's quick to see if foo is a word; choosing one at random (e.g.
    > there); trying to find a subword (e.g. the), then looking for a word
    > starting with the difference (e.g. re.*) until you end up with a
    > suitable string. Then repeat.
    >
    > My hope is to find some that make sense, but I'm not optimistic.


    I think the basic problem is to find, in a large word list, all
    words that begin with a given string (whether itself a word or not).
    If that is taken as a basic operation, an algorithm shouldn't be
    too hard to work out (though I haven't done it).

    That would suggest a trie (no typo) structure, which supports
    exactly this retrieval by prefix. There are a few modules on
    CPAN that implement tries. Could be interesting how they hold
    up against /usr/dict/words.

    Anno
    Anno Siegel, Nov 13, 2004
    #4
  5. Stuart Moore

    Peter Wyzl Guest

    ----- Original Message -----
    From: "Stuart Moore" <>
    Newsgroups: comp.lang.perl.misc
    Sent: Saturday, November 13, 2004 2:42 AM
    Subject: Fun problem: Overlapping words


    >A bit of a poser for anyone bored:
    >
    > I was chatting with some friends, and we were trying to work out suitable
    > strings of letters which could have spaces and punctuation in different
    > places to produce different sentences
    >
    > e.g.
    >
    > Therestopenlarge
    >
    > parses to
    >
    > There stop enlarge
    > or
    > The rest open large


    Also

    Theres to pen large

    I wrote a program once (a couple of years ago) to solve the '9 letter
    square' problem where you are given 9 letters in a 3 x 3 square and tasked
    with making all possible words from the combinations. Also to find the 9
    letter 'root' word.

    The requirements are : each letter can be used only once, The centre letter
    must be used in each word, all words must be 4 letters or more long. There
    is also an added requirement that no pronouns are valid and all words must
    be found in a standard dictionary (in this case the compton was defined as
    the standard).

    I post the code below out of interest. Maybe it will give you some starting
    ideas, comments welcome. (Some 'prettying' functions have been removed from
    the actual program in the interests of brevity)

    #!/usr/bin/perl -w
    use strict;
    usage();

    my ($min, $max,) = (4, 9, ); # set defaults

    my @letters = getletters();

    unless ((scalar @letters) == $max){
    error('Incorrect number of letters!');
    print scalar @letters, $max;
    getletters();
    }

    my @words = words();

    my @results;
    for (@words){
    next unless m/$letters[4]/;
    my @test = @letters;
    my @word = split //,$_;
    my $length = scalar @word;
    my $match = 0;
    foreach my $letter (@word){
    my $testpos = 0;
    foreach my $test (@test){
    if ($letter eq $test){
    $match += 1;
    splice @test, $testpos, 1;
    last;
    }
    $testpos++;
    }
    }
    if ($match == $length){
    push @results, $_;
    }
    }

    @results = sort @results;

    my $i = 0;
    print "\nNumber of words is ", scalar @results, "\n";
    foreach my $word (@results){
    print "$word\n";
    $i++;
    if ($i == 20){
    print "Press Enter to display more\n";
    <STDIN>;
    $i = 0;
    }
    }

    print "Press Enter to close\n";
    <STDIN>;
    exit 1;

    #######
    # subs

    sub getletters{
    print "Input the source letters :\n";
    chomp ($_ = <STDIN>);
    return (split //);
    }

    sub words { # puzzwords.txt contains my dictionary
    open (IN, '<puzzwords.txt') or die "Can't read word file $!\n";
    my @words;
    while (<IN>){
    chomp;
    if ((length $_) < $min){
    next;
    }
    if ((length $_) > $max){
    next;
    }
    push @words, $_;
    }
    return @words;
    }

    sub error{
    my $error = shift;
    print "\n$error\n\n";
    usage();
    }

    sub usage{
    print <<USAGE;
    Puzzwords V 1.0 by Peter Green\npeter\@arafura.net.au
    puzzwords.exe [-s, -g]
    No option default is Solve min length 4 max length 9
    Input number of letters must be the same as the maximum word size (default
    9)
    Option -s to specify a different minimum and maximum word size when solving
    Default is min 4 and max 9
    USAGE
    }

    --
    Wyzelli
    print 'qwerty is a word???';
    Peter Wyzl, Nov 13, 2004
    #5
    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,085
    Peter Strøiman
    Aug 23, 2005
  2. Andy Fish
    Replies:
    65
    Views:
    1,740
    Mabden
    May 18, 2004
  3. Richard Heathfield
    Replies:
    7
    Views:
    361
    Barry Schwarz
    Oct 5, 2003
  4. dolphin
    Replies:
    4
    Views:
    317
    Jorgen Grahn
    Aug 25, 2007
  5. er
    Replies:
    2
    Views:
    504
Loading...

Share This Page