Cryptogram

[Church]

Well i was looking in the paper the other day and they have this Word puzzle with a bunch of letters used to figure out what the quote of some famous guy was.

Basically they take every letter of the alphabet and just change them and print it out and you use that to figure out what the quote was and by whom.

I thought it would be a fun project to create a program that pretty much brute forces it. A User could Enter the cyrptograph and it would run through a list of Articles and words to put out a bunch of test possibilities.

I'd imagine this might take a little while to make but it seems like a fun project.. well at the moment heh.

Anyway my major conceptual problem is with how i'm going to load the words in for the program. Should they be in a excel sheet? In which case i might have an easier time with Visual Basic.. I'm not all that proficient with using Excel Sheets..

Or i could have a bunch of words listed in files. And then load them into an Array for each letter of the Alphabet. Leaving an Array for Articles to make things quicker right off the bat.

I could just load them all into one array and then make a bunch of array's of pointers for organizing them.. I don't know there's a few methods popping into my head.

I haven't actually made a program like this out side of class before but it seems like it would be a neat project. Anyway any advice would be appreciated. Oh and if anyone knows where i can find a list of words? I would imagine there's some floating around from when Brute Forcing was Popular.. when it was or if it still is? I don't know.

I was thinking about just making a program to scrape a bunch of words off of some random website like dictionary.com or something and then i realized.. i had no idea how to do that lol.

Anyway, Help would be Greatly Appreciated!

[tux4life]

I would store the words in a plain text file and read them into a vector :)

[iamthwee]

@tux4life, did you think you're in le c++ forums.

[Church]

I haven't taken a C++ class yet, all i know is C. I will be taking one in a few semester's though but i can always redo the project then if i'm really THAT in to it.

[iamthwee]

Is there an online version of this puzzle, i still don't understand what you're tryin to do.

[s_sridhar]

You can use fgets and fputs to get a bunch of words and then compare. A text file is enough i think.

[Church]

had to look around a bit:
http://www.wordplays.com/p/crypto

That's a cryptogram

[iamthwee]

In that case this is really easy to solve.

Think about how you would do this on paper first.

You don't need excel spread sheet, or any other file input.

Post some code and we will help you along.

[jephthah]

there are 26*26=676 permutations. that's easy to "brute force" the trickier part will be getting the computer to recognize when the solution has been found.

a possible intermediate stage to this program could be to allow the user to choose which letters are substituted, updating the output each time. this would not be so much of a "solver" as more of a "helper" program to allow a user the ability to quickly find solutions by examining which substitutions work and which don't

the whole theory of how to solve these "cryptoquotes" is to start with the small words, 1 and 2 and 3 letter words such as "A", "I", "IF", "OF", "OR", "AND", "THE"... then the larger words start to fall into place.

[NeoKyrgyz]

It seems for me that this problem is not solvable. You would never know whether you have hit true solution or not. Besides character permutations there will be word permutations also. But as suggested above you can give possible words (which is estimated to be huge, but helpful)
Also if performance is important for you try to use "Knuth-Morris-Pratt string matching" rather than straight comparison. Or you can adapt this algorithm to your problem somehow.

[jephthah]

of course its solvable.

it's a trivial matter to "brute force" 676 total permutations, and only slightly more complicated to do a few dictionary matches on each potential solution.

anyhow, if it's as you say "not solvable" the why the hell bother to suggest using Knuth-Morris-Pratt algorithm ... an algorithm which is completely inappropriate to the problem, in the first place?

.

[NeoKyrgyz]

It seems you didn't understand the problem itself. Just a reminder for you:

Well i was looking in the paper the other day and they have this Word puzzle with a bunch of letters used to figure out what the quote of some famous guy was.

Basically they take every letter of the alphabet and just change them and print it out and you use that to figure out what the quote was and by whom.

of course its solvable.

it's a trivial matter to "brute force" 676 total permutations, and only slightly more complicated to do a few dictionary matches on each potential solution.
.

How would you know which one is the solution to the problem? You are not brute forcing to make a word only, but also you are brute forcing to make a sentence .

Example:
kdait ern

Possible solutions:
drink ate
drink tea

Even for a simple example like above there are two possible solutions. (There might be others) If you would implement such an intelligent program that will tell which one of the above is quot of some famous guy, then you would make a huge contribution to AI.

Even if you keep some kind of database of quotes, it'll NOT fully solve the problem, since there is not a global/magic database which contains all possible quotes of all possible famous guys ( at least I don't know). But it can help to make your program more intelligent.
My point is that number of possible sentences and number of quotes that exist is not predictable.
So problem is not solvable. It's ambiguous.

By helper function, I meant to print all possible combination (two sentences above) and make user to decide which one is a quot of some famous guy.

.

anyhow, if it's as you say "not solvable" the why the hell bother to suggest using Knuth-Morris-Pratt algorithm ... an algorithm which is completely inappropriate to the problem, in the first place?

.

1)
Looking whether a sentence, word combination you've constructed is in a file of quotes (to make you program more intelligent, and eliminate some dummy combination) you should/must use above algorithm.

2)
Since you are finding/(brute forcing) a possible word in a dictionary (to check whether it's really valid word in a language) you have to use above algorithm (assuming dictionary is not sorted).

There might be other places where you might need/(adapt) KMP algorithm (or variation of it)

[Church]

Well i was never that great on String manipulation, i thought this little side project might help me out a bit.

It isn't going to complete all the puzzles but hopefully it will come close. Unless i came up with a list of every person that was ever quotable then the names of the people would be impossible.

Oh and i'm pretty sure the paper is putting out sentences that are capable of being Deciphered. Or at least ones longer then 2 words.

Now anyone know where i can find a list of words? or how to write a program that can scrape an online dictionary or something? Is it even possible in C?

Maybe i can just have it figure out all possible combinations of articles? you know "if" "and" "or" "at" "the" err whatever, short words. I dunno, got finals coming up so i'll probably start in a couple of weeks.

[jephthah]

oh dear... i've made a fatal mistake. the number of permutations is not "26*26", but is actually "26!"

which is a ridiculously huge number.

my apologies to NeoKyrgyz.. i think he is more capable than I am to speak on this subject.

and maybe if i shut up for a moment, i might learn something.

[NeoKyrgyz]

Church
Google using keywords "free download english dictionary words for brute forcing" there will be tones of free downloadable dictionaries.

jephthah:

my apologies to NeoKyrgyz..

No problem

oh dear... i've made a fatal mistake. the number of permutations is not "26*26", but is actually "26!"

Number of permutations does not depend on the number of characters in the alphabet, it depends on the number of character in the question. So it would be "n!" (where n is number of character in the question/quot).
Don't you think so?
It's possible to decrease this number a little by optmizing dummy permutation, but this is general tendency. (Order of (n!)).