Interesting Problem

[iago]

In keeping with the theme of newspaper problems, somebody should write a program that solved the "cryptoquotes" found in the newspaper.  That is, sentences that have every instance of each letter replaced with another letter

HARRY LONGFELLOW
ABCCD EFGHIJKKFL

Although it is possible to do a full bruteforce, there are 26! combinations, which is an unfeasible number. 

Some things to reduce that might be to target 1-, then 2-, 3-, 4-, etc. letter words.  Also, to look for the most common letter, for pairs of letters that frequently occur, etc.

Also note that the quotes almost always contain proper names and other words you won't find in the dictionary, so the program would have to cope with that. 

[Chavo]

I can't imagine something like this not already existing.  Or is this a forum challenge thingy.....?

[Joe]

Proper names that could be guessed by someone would be in an encyclopedia. I'm sure there's one online somewhere. Hint, hint.

[iago]

I can't imagine something like this not already existing.  Or is this a forum challenge thingy.....?

I'm sure it's been done before.  But it still posts an interesting challenge. 

It's not a forum challenge (although I had considered that :)), it's just a general challenge.  If somebody is trying to think of something to implement, and they want to solve a difficult problem, this is a good one. 

The main trick is that you can't solve it the simplest possible way.  It would take 26! = 4.03291461 × 10²⁶ guesses, and that's not realistic.  So some kind of heuristical algorithm needs to be used to reduce that substantially, before it can be solved. 

It would just be neat to implement, and I doubt that any two people would implement it the same.  That's the best kind of problem :)

[mynameistmp]

That is, sentences that have every instance of each letter replaced with another letter

How long are the 'sentences' ?

[iago]

In the paper, they're usually about 3 or 4 lines, probably 5 or 6 words per line, so probably between 15 and 24 words. 

[rabbit]

Really?  The last one I saw was about 8 words, ~6 letters each.  Maybe it was just a hard one?

[deadly7]

Wouldn't it actually be 10^25, because ROT encoding to the 26th power just means going back to where you came from..That's like ROT-26 encoding "A", it would get you "A"

[iago]

Each letter can be 25 others. 

A => B, C, D, E, F, G, ..............
B => A, C, D, E, F, G, ..............
etc.

Based on that, I think it would be like 26²⁵ or something.  It's probably more complicated than that, because once A has a value, B has one less value to choose from.  So that would make it 26!....

Either way, it's an impossible number to bruteforce.

[rabbit]

It's an entirely possible number to bruteforce, it would just take a very ... long time.

[iago]

Well, everything is possible to bruteforce, but it's rather infeasible. 

It'd be interesting to find a GOOD solution to this :P

[Chavo]

It'd be interesting to find a GOOD solution to this :P

How about waiting till the next day when they publish the answer?  :P

[Sidoh]

How about waiting till the next day when they publish the answer?  :P

Pff, you're boring!

Kidding, but yeah.  Maybe I'll try to think on this.  It is a pretty neat problem. :)

[zorm]

We used to do these everyday in English class last year for fun. The method we used to solve them most often was looking at patterns in the letters of words. For example "people" is I believe the only word with a abxaxb pattern. My English teacher from last year knew a whole bunch of these and it helped lots. Once you get to this point you could likely just start filling in letters and trying to match them to actual words. You don't have to worry about names all that much because you can normally fill in all the other words and get the letters needed.

This seems like a lot of fun perhaps I'll start writing some code and see what I come up with.

[Nate]

Maybe you guys should start with something easier like sudoku's then try this.

Also you want to treat this kinda like finding collisions, find all possbilities for each word, then compare the letter = letter values between words to find what works then out but all possible working combos