Programming 1 - Processing Slow

Put your programming skills to the test in these challenges.

Programming 1 - Processing Slow

Post by spike_hacker_inc on Tue May 31, 2011 4:58 pm
([msg=57936]see Programming 1 - Processing Slow[/msg])

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 8-)
spike_hacker_inc
New User
New User
 
Posts: 2
Joined: Thu Jun 25, 2009 8:09 am
Blog: View Blog (0)


Re: Programming 1 - Processing Slow

Post by Gatito on Tue May 31, 2011 5:24 pm
([msg=57938]see Re: Programming 1 - Processing Slow[/msg])

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.
User avatar
Gatito
Poster
Poster
 
Posts: 113
Joined: Tue Mar 08, 2011 12:55 pm
Blog: View Blog (0)


Re: Programming 1 - Processing Slow

Post by spike_hacker_inc on Tue May 31, 2011 6:48 pm
([msg=57945]see Re: Programming 1 - Processing Slow[/msg])

Gatito wrote: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 8-)
spike_hacker_inc
New User
New User
 
Posts: 2
Joined: Thu Jun 25, 2009 8:09 am
Blog: View Blog (0)


Re: Programming 1 - Processing Slow

Post by msbachman on Tue May 31, 2011 7:14 pm
([msg=57946]see Re: Programming 1 - Processing Slow[/msg])

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! :)
"I'm going to get into your sister. I'm going to get my hands on your daughter."
~Gatito
User avatar
msbachman
Contributor
Contributor
 
Posts: 681
Joined: Mon Jan 12, 2009 10:22 pm
Location: In the sky lol
Blog: View Blog (0)


Re: Programming 1 - Processing Slow

Post by Gatito on Tue May 31, 2011 9:38 pm
([msg=57956]see Re: Programming 1 - Processing Slow[/msg])

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.
User avatar
Gatito
Poster
Poster
 
Posts: 113
Joined: Tue Mar 08, 2011 12:55 pm
Blog: View Blog (0)


Re: Programming 1 - Processing Slow

Post by fashizzlepop on Tue May 31, 2011 11:47 pm
([msg=57960]see Re: Programming 1 - Processing Slow[/msg])

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?
The glass is neither half-full nor half-empty; it's merely twice as big as it needs to be.
User avatar
fashizzlepop
Developer
Developer
 
Posts: 2303
Joined: Sat May 24, 2008 1:20 pm
Blog: View Blog (0)



Return to Programming

Who is online

Users browsing this forum: No registered users and 0 guests