Author |
Topic: Encoding the cipher (Read 1902 times) |
|
mistaken_id
Junior Member
Posts: 132
|
 |
Encoding the cipher
« on: Aug 8th, 2010, 7:03pm » |
 Quote  Modify
|
You are given a cipher decoder dictionary which has the mappings from alphabets(non-encrypted) to their encrypted forms:
Ex: a -> ,,_
b -> ++(
And you are given a list of words ex: {apple , boy } Context list
And finally you are given the encrypted message
..--__)0 (something like that)..
So you have to decrypt the message using cipher decoder dictionary, and the decrypted word should be one of the words in the list , if more than one word in the list matches the decryption process, return the word with minimum number of alphabets
What is the efficient way to do this?
|
|
 IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender: 
Posts: 13730
|
|
Re: Encoding the cipher
« Reply #1 on: Aug 9th, 2010, 1:09am » |
Quote Modify
|
So, decrypted words have to be ones from the provided list?
Then I'd encrypt all the words, order them in order of "minimum number of alphabets " whatever that means. Then search for the encrypted words in the encrypted text.
You can use a hashmap to translate found encrypted words back to their plaintext version.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: Encoding the cipher
« Reply #2 on: Aug 9th, 2010, 1:24am » |
Quote Modify
|
It is probably overkill to encode a large dictionary to find a single word.
I would search recursively:
Given a possible decoding of a prefix of the word:
- Check what letters match the next coded characters.
- For each letter, extend the prefix, check that a word exists with this prefix.
- If the code word is exhausted, check that the prefix exists exactly as a word.
- If only one word exists, encode it and verify that it matches the complete coded word.
- If more than one word matches, call the same procedure with the extended prefix decoding.
Search greedily (the longest codes first). And among all solutions, keep the shortest one.
|
| « Last Edit: Aug 9th, 2010, 1:31am by Grimbal » |
IP Logged |
|
|
|
mistaken_id
Junior Member
Posts: 132
|
|
Re: Encoding the cipher
« Reply #3 on: Aug 10th, 2010, 7:20pm » |
Quote Modify
|
on Aug 9th, 2010, 1:24am, Grimbal wrote:It is probably overkill to encode a large dictionary to find a single word.
I would search recursively:
Given a possible decoding of a prefix of the word:
- Check what letters match the next coded characters.
- For each letter, extend the prefix, check that a word exists with this prefix.
- If the code word is exhausted, check that the prefix exists exactly as a word.
- If only one word exists, encode it and verify that it matches the complete coded word.
- If more than one word matches, call the same procedure with the extended prefix decoding.
Search greedily (the longest codes first). And among all solutions, keep the shortest one. |
|
Is there a way to improve this by using dynamic programming. I tried using DP but wasn't of much help in worst case.
|
|
IP Logged |
|
|
|
Hippo
Uberpuzzler
Gender:
Posts: 919
|
|
Re: Encoding the cipher
« Reply #4 on: Aug 10th, 2010, 11:12pm » |
Quote Modify
|
on Aug 9th, 2010, 1:24am, Grimbal wrote:It is probably overkill to encode a large dictionary to find a single word.
I would search recursively:
Given a possible decoding of a prefix of the word:
- Check what letters match the next coded characters.
- For each letter, extend the prefix, check that a word exists with this prefix.
- If the code word is exhausted, check that the prefix exists exactly as a word.
- If only one word exists, encode it and verify that it matches the complete coded word.
- If more than one word matches, call the same procedure with the extended prefix decoding.
Search greedily (the longest codes first). And among all solutions, keep the shortest one. |
|
I don't think it's an overkill. Actually I am using it for unseparated morse.
OK, if the question is formulated such that you have one encrypted word for which you are given set of possible words, than reading the input bounds running time from down to time any trivial algorithm requires.
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print