Re^7: Challenge: 8 Letters, Most Words

by choroba (Bishop)
 on Oct 05, 2013 at 08:22 UTC ( #1057013=note: print w/replies, xml ) Need Help??

in reply to Re^6: Challenge: 8 Letters, Most Words
in thread Challenge: 8 Letters, Most Words

Something like the following? It slows the algorithm terribly, though...
```#!/usr/bin/perl
use warnings;
use strict;
use feature qw(say);

my %lc_words;
my \$dict = shift;
my \$FH;
open \$FH, '<', \$dict or \$FH = *DATA;

while (<\$FH>) {
chomp;
next if length > 8;
my \$lc = lc;
\$lc_words{\$lc} = 1;
}
say scalar keys %lc_words;

my %sorted_count;

for (keys %lc_words) {
my @letters = sort split //;
my \$sorted  = join q(), @letters;
\$sorted_count{\$sorted}++;
}
say "\$_: \$sorted_count{\$_}"
for sort { \$sorted_count{\$a} <=> \$sorted_count{\$b} }
keys %sorted_count;

print '-' x 78, "\n";

my %summed = %sorted_count;
for my \$length (1 .. 7) {
warn \$length;
for my \$sorted (grep \$length == length, keys %sorted_count) {
my \$regex = join '.*', split //, \$sorted;
for my \$longer (grep \$length < length, keys %sorted_count) {
\$summed{\$longer} += \$sorted_count{\$sorted} if \$longer =~ \$
+regex;
}
}
}

sub merge {
my (\$str1, \$str2) = @_;
my \$merged = q();
while(length \$str1 . \$str2) {
my \$char1 = substr \$str1, 0, 1;
my \$char2 = substr \$str2, 0, 1;
if (\$char1 eq \$char2) {
\$merged .= substr \$str1, 0, 1, q();
substr \$str2, 0, 1, q();
} elsif (\$char1 ne q() and \$char1 lt \$char2 or \$char2 eq q())
+{
\$merged .= substr \$str1, 0, 1, q();
} else {
\$merged .= substr \$str2, 0, 1, q();
}
return if length \$merged > 8;
}
return \$merged;
}

warn "Merging...\n";
while (1) {
my @shorter = grep 8 > length, keys %summed;
for my \$str1 (@shorter) {
for my \$str2 (@shorter) {
next if \$str1 le \$str2;
my \$merged = merge(\$str1, \$str2);
if (defined \$merged
and \$str1 ne \$merged
and \$str2 ne \$merged) {
next if exists \$summed{\$merged};
\$summed{\$merged} = \$summed{\$str1} + \$summed{\$str2};
}
}
}
}

say "\$_: \$summed{\$_}"
for sort { \$summed{\$a} <=> \$summed{\$b} }
keys %summed;

__DATA__
abcd
acdb
dabc
efgh
fgeh
hegf
egfh
fegh
abcdxy
efghlm
لսႽ† ᥲᥒ⚪⟊Ⴙᘓᖇ Ꮅᘓᖇ⎱ Ⴙᥲ𝇋ƙᘓᖇ

Replies are listed 'Best First'.
Re^8: Challenge: 8 Letters, Most Words
by choroba (Bishop) on Oct 05, 2013 at 11:28 UTC
Another idea: preprocess the input, adding all the combinations of the shorter words. Then run the original code without postprocessing. I will try to test it later, not much time at the moment...
لսႽ† ᥲᥒ⚪⟊Ⴙᘓᖇ Ꮅᘓᖇ⎱ Ⴙᥲ𝇋ƙᘓᖇ

Create A New User
Node Status?
node history
Node Type: note [id://1057013]
help
Chatterbox?
and all is quiet...

How do I use this? | Other CB clients
Other Users?
Others wandering the Monastery: (9)
As of 2018-01-22 21:26 GMT
Sections?
Information?
Find Nodes?
Leftovers?
Voting Booth?
How did you see in the new year?

Results (237 votes). Check out past polls.

Notices?