Beefy Boxes and Bandwidth Generously Provided by pair Networks
The stupid question is the question not asked
 
PerlMonks  

Re^4: Challenge: 8 Letters, Most Words

by Limbic~Region (Chancellor)
on Oct 05, 2013 at 00:17 UTC ( #1056961=note: print w/ replies, xml ) Need Help??


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

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


Comment on Re^4: Challenge: 8 Letters, Most Words
Re^5: Challenge: 8 Letters, Most Words
by choroba (Canon) on Oct 05, 2013 at 00:31 UTC
    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

Re^5: Challenge: 8 Letters, Most Words
by LanX (Canon) on Oct 05, 2013 at 00:39 UTC
    > 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

        Yeah I agree about 12_461_993

        Anyway you don't need to check against all words in the dictionary, only taking the (at most) 256 subsets of a potential 8 letter combination. (less if letters are repeated)

        This can be done in a lookup in a prepared count-hash with normalized keys.

        Cheers Rolf

        ( addicted to the Perl Programming Language)

Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://1056961]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others about the Monastery: (16)
As of 2015-07-07 13:09 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    The top three priorities of my open tasks are (in descending order of likelihood to be worked on) ...









    Results (88 votes), past polls