Programming 1

Put your programming skills to the test in these challenges.

Re: Programming 1

Post by Learning_Noob on Sun Jan 05, 2014 11:39 pm
([msg=78757]see Re: Programming 1[/msg])

Still working as of 1/5/2014; the sorted tip was very helpful for python

For any other python users out there, i'm curious why EOF (during stdin) can seldom hang on eclipse > pydev > for windows. Seems rather daunting as i was hoping to run one window rather than having to fumble windows. The only thing i could dig up on google may relate to deliminators on reading each string? E.g. EOF in an interactive session would need to follow the enter key (or so i've read for py 2.7)?

Definitely a great warmup after being absent for a while, looking forward to the next challenge
Learning_Noob
New User
New User
 
Posts: 2
Joined: Sun Apr 15, 2012 8:30 pm
Blog: View Blog (0)


Re: Programming 1

Post by Bl4ckPh0enix on Sun Feb 16, 2014 9:34 am
([msg=79505]see Re: Programming 1[/msg])

I passed the whole last night thinking.
THIS DEFINETELY CONTAINS A SPOILER
So i did it in python, and my algorithm steps where those:

  • Create a words.txt file where i would paste the provided list of scrabbled words

  • Grab each line from wordlist.txt and append it in a wordlist array, same with words.txt and words array . Before appending lines in those arrays, remove \n\t\r characters and spaces (because pasting the list from hts to the words.txt could be messy)
  • For each element of words array, scan the wordlist array and: if the scrabbled word is of the same length as the unscrabbled word
  • Then for each element (character) of the scrabbled word if it exists in the unscrabbled word DELETE the character from the position in which it was found in the unscrabbled word and now get back to the loop with the new (without the deleted character) unscrabbled word
  • When this new unscrabbled word is equal to a zero length string ( == '' ) you can be sure that you got the right word

I dont know if there is any case in which those steps could return a false answer.

but i am almost sure that this is not the only solution and i would like it if any of you could post or pm me other ideas.

-- Sun Feb 16, 2014 5:29 pm --

Second solution!
It's a bit more mathematical...
It's based on the uniqueness of the factorisation of an integer into product of prime numbers.
Bl4ckPh0enix
New User
New User
 
Posts: 3
Joined: Sun Aug 04, 2013 7:22 pm
Blog: View Blog (0)


Re: Programming 1

Post by malleablizing on Fri May 30, 2014 7:57 pm
([msg=81097]see Re: Programming 1[/msg])

Here's another approach:

1. Reorder the characters in each word in the wordlist, alphabetically. Use the reordered words as keys for a treemap, and the original words as values.
2. Do the same reordering for the scrambled words. This should produce the same string as the key for the unscrambled words in the treemap
3. Print values using the key

I did this in Java and only had to write a few lines of code. The algorithm should be very simple. :)
malleablizing
New User
New User
 
Posts: 2
Joined: Mon Jul 09, 2012 4:46 am
Blog: View Blog (0)


Re: Programming 1

Post by akorshikai on Sat Jun 28, 2014 8:32 pm
([msg=81856]see Re: Programming 1[/msg])

I'd like to share how I did this, and apologize if it's already been posted (I haven't read through all 28 pages of comments).

To better understand the problem, recognize that a series of scrambled letters corresponds to a single word. Therefore, we can assume we will not encounter "listen" and "silent", which are the same length and use the same letters.

I opted to take a psuedo hashing approach. I assigned each character and number 0-9 to a prime number, beginning with 2 and going up to somewhere in the mid hundreds. I read in each character from the word on the list and multiplied the corresponding character's value to the preceding character until there were no more characters left to read in using "long long int" (the values get pretty high). This creates a numeric index for each word on the list that is unique, no matter the order of the characters that you read in, by taking advantage of mathematical properties associated with prime numbers.

Next, I setup the necessary comparison function that will read in the 10 random scrambled words provided by HTS to compute their psuedo hash. Lastly, the HTS scrambled word hashes are compared to those of the wordlist and when they match, the corresponding word from the original wordlist is output to a file, separated by a comma so that all I've got left to do is ctrl+a, ctrl+c, ctrl+v. It's basically what all the other password crackers do when brute-forcing. Language I did this in was C++.
akorshikai
New User
New User
 
Posts: 24
Joined: Sat Jun 28, 2014 8:21 pm
Blog: View Blog (0)


Previous

Return to Programming

Who is online

Users browsing this forum: No registered users and 0 guests