| [reply] |
> This looks like a multiple-constrained Knapsack problem.
Yes, kind off.
> All bets are off...
Well IMHO the multidimensionality makes it much easier to solve.
The trick is always to always concentrate on the smallest dimension.
E.g. there is no V allowed, about 6 dog-names have a V, so they can be excluded right away for the rest of the search.
Then there is only 1 Z allowed, only about 7 dog-names include a Z.
After trying each Z-names out in the first level, all other Z-Names must be excluded for the next levels.
And trying one Z-name also diminishes other characters which become minimal now, so other names can be excluded for the subtree. (e.g. Xoloitzcuintli includes an X, but only one X was allowed, all other X-names must be excluded now, and so on)
IMHO the search tree becomes comparatively small with this strategy. (brute force has a worst case of faculty(n) combinations to check with n=100 here)
Cheers Rolf
( addicted to the Perl Programming Language)
| [reply]
[d/l]
[select] |
A bit more experimentation with sorting and scoring functions has (sadly) lead me to the conclusion that the fast performance of my posted code is more of an accident rather than due to a great algorithm, i.e. it works very well for this data set but not necessarily on others. So be careful before you bet too much on it...
| [reply] |
I noticed it too, that you score caps only. That said, if you score by length, it works nicely as well.
Another smart thing is to remove impossible words at earliest opportunity.
DOG: for my $dog (@_) {
my $remaining = $letters;
$remaining =~ s/$_//i or next DOG for split //, $dog;
push @remain, $remaining;
push @dogs, $dog;
}
while( my $dog = shift @dogs ) {
dogtree( "$tree $dog", shift @remain, @dogs );
}
The given puzzle solves in 1-2 secs, and takes about 3 minutes for a full pass (return instead of exit).
Only one solution exists. A letter set such as
"A(11),B(3),C(2),D(8),E(6),F(1),H(8),I(10),J(1),K(1),L(6),M(1),N(10),O(9),P(2),R(7),S(6),T(9),U(7),V(1),W(1),X(1),Z(2)";
takes some 20 times longer... | [reply]
[d/l]
[select] |
