Fun problem: Overlapping words

[Stuart Moore]

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.

 

[Jürgen Exner]

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

 

[Janek Schleicher]

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

 

[Anno Siegel]

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

 

[Peter Wyzl]

----- Original Message -----
From: "Stuart Moore" <[email protected]>
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
}