No such thing as a small change PerlMonks

### Re^3: Challenge: 8 Letters, Most Words

by TJPride (Pilgrim)
 on Oct 04, 2013 at 22:09 UTC ( #1056944=note: print w/replies, xml ) Need Help??

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

Capitalization may not matter, but dupes do, and there are often multiple versions of the same word. I suppose I could have just lowercased everything and then deduped. The word list is largely irrelevant, though - the important thing is the algorithm.

What do you mean by brute force, exactly? There are far too many possible letter combinations to just check each one.

Replies are listed 'Best First'.
Re^4: Challenge: 8 Letters, Most Words
by Limbic~Region (Chancellor) on Oct 05, 2013 at 00:17 UTC
TJPride,
What do you mean by brute force, exactly? There are far too many possible letter combinations to just check each one.

As I pointed out elsewhere in this thread, you don't need to check all 26^8 possibilities since order of letters doesn't matter. That leaves 13_884_156 possible 8 letter combinations. Since I am using a specific dictionary and no word allows a single letter to repeat more than 5 times, I can further reduce that down to 12_461_993. Since my word list contains 40,933 words, that means I am up to 510_106_759_469 checks. In order to finish in under 24 hours, I will need to be able to do 5.9 million checks per second. I hope my C skills are up for the challenge (stay tuned).

Cheers - L~R

I am not sure whether my solution is correct, but if it is, it is much faster, because it only checks the possible combinations, not all of them.
لսႽ† ᥲᥒ⚪⟊Ⴙᘓᖇ Ꮅᘓᖇ⎱ Ⴙᥲ𝇋ƙᘓᖇ
choroba,
I intentionally chose not to review anyone else's code until after mine was finished (20 minutes ago). I peeked at something BrowserUk put up simply because he said it was brute force and then indicated it finished in a few seconds. It is pretty late here but I will check out solutions tomorrow. Feel free to critique mine before then :-D

Cheers - L~R

> That leaves 13_884_156 possible 8 letter combinations. Since I am using a specific dictionary and no word allows a single letter to repeat more than 5 times,

I think pre-investigating the dictionary should dramatically limit this number.

Just find the real maximum repetition for each letter.

Cheers Rolf

( addicted to the Perl Programming Language)

LanX,
I did that but it didn't reduce it dramatically. As I pointed out elsewhere, that only gets it down to 12_461_993.

Cheers - L~R

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

How do I use this? | Other CB clients
Other Users?
Others browsing the Monastery: (9)
As of 2018-04-19 21:39 GMT
Sections?
Information?
Find Nodes?
Leftovers?
Voting Booth?
My travels bear the most uncanny semblance to ...

Results (75 votes). Check out past polls.

Notices?