Programming 1 - Processing Slow

[spike_hacker_inc]

Hey there guys,

I have written an algorithm that seems to work with the unjumbling of the words in c++.... My only problem is it seems to process really really slow! I have written something basically the same in VB.Net but it also seems to work slow!

So I'm not sure exactly how to go about speeding up the process of the comparison between words, without posting my code. So was wondering if maybe someone can give me a hint as in what I may be doing wrong, if maybe you have come across the same issue.

Any other help will be greatly appreciated...
Peace Out

[Gatito]

You don't have to post your code here ( but then again if it does not work it wouldn't be a big spoiler), on the other side I don't think it would be a problem describing how your algorithm works. Otherwise I doubt you could get help about your own method.

Just my wild guess are you using some kind of word permutation? If used incorrectly it could lead to some wasted time although I can't tell how much that would possibly be.

[spike_hacker_inc]

You don't have to post your code here ( but then again if it does not work it wouldn't be a big spoiler), on the other side I don't think it would be a problem describing how your algorithm works. Otherwise I doubt you could get help about your own method.

Just my wild guess are you using some kind of word permutation? If used incorrectly it could lead to some wasted time although I can't tell how much that would possibly be.

Sup man, thanks for the reply.

I would reckon it is a spoiler because it DOES work, the only problem is that it works very slowly... And yes I am using permutation...

My programs basic logic is:
- Get the scrambled word (Eg. "spwnsae")
- Get scrambled word size
- Get word from wordlist.txt
- Permute scrambled word
- Compare worlist word to new permuted word

That's basically it...Here's some pseudo for my recursion:

Code: Select all

recurse(width, position+1,baseString+jumbledWord[i],wordSize)
for i < wordSize
   if position < width
     recurse(width, position+1, baseString+jumbledWord[i],wordSize)
checkPassword(baseString+jumbledWord[i])

If you need anything else, just let me know

Peace Out

[msbachman]

Instead of going about it how you're doing it, you could try an operation on both the scrambled word and each word from the wordlist that would return the same result if the two words are scrambled versions of one another.

Think of it like this:

Code: Select all

if f(wordlistword) == f(scrambledword):
    print(wordlistword)


In short, there's a way to go about this where you don't have to scramble shit all over the place. Scramble with purpose!

[Gatito]

Just for curiosity I did some benchmarks on using recursion.

HERE ARE THE HARD FACTS:

There are a total of 1275±1 words in the list made of:
685 6-letter words T=1.4 s
385 7-letter words T=13.4 s
204 8-letter words T=141.0 s
just a 9-letter word T=15.6 s (and that being "phurivdli" but later about it).

You ask what T is? For example you want to find the unscrambled version of "vedser" which is made of 6 letters. In that case :
T = [Time recursion needs to find all permutations for 6 character long string] X [Number of 6-letter words in the list].
So basically T is the worst time my PC needs for finding the answer for a word without including the time needed for reading through the list and comparing the strings which isn't that much anyways.

And Probability Theory tells us the average time for unscrambling 10 words is more than 2 minutes (if words are picked randomly). So recursion is too time-costly for this challenge, you have to find some other algorithm (see post above).

HERE ARE THE FUN FACTS:

What is phurivdli anyways? A search with google wielded some funny results, every link pointed to a site/forum which had to do with this very challenge, lol.

[fashizzlepop]

Yes, there are much easier ways to find matches.

What would a match have in common, EVERYTIME?

Think about this... what IS an anagram? How many possible answers can each scrambled word have given THIS specific list?