Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > Perl > Perl Misc > Fun problem: Overlapping words

Reply
Thread Tools

Fun problem: Overlapping words

 
 
Stuart Moore
Guest
Posts: n/a
 
      11-12-2004
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.
 
Reply With Quote
 
 
 
 
Jürgen Exner
Guest
Posts: n/a
 
      11-12-2004
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


 
Reply With Quote
 
 
 
 
Janek Schleicher
Guest
Posts: n/a
 
      11-12-2004
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
 
Reply With Quote
 
Anno Siegel
Guest
Posts: n/a
 
      11-13-2004
Stuart Moore <(E-Mail Removed)> 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
 
Reply With Quote
 
Peter Wyzl
Guest
Posts: n/a
 
      11-13-2004
----- Original Message -----
From: "Stuart Moore" <(E-Mail Removed)>
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???';


 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
3 PIX VPN questions - FUN FUN FUN frishack@gmail.com Cisco 3 03-16-2006 02:25 PM
Words Words utab C++ 6 02-16-2006 07:00 PM
Non-noise words are incorrectly recognised as noise words. Peter Strøiman ASP .Net 1 08-23-2005 01:26 PM
Fun fun fun Luke Computer Support 3 10-07-2003 03:45 PM
Re: A little bit of help regarding my linked list program required. - "words.c" - "words.c" Richard Heathfield C Programming 7 10-05-2003 02:38 PM



Advertisments