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

[Chavo]

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

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

[Sidoh]

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

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

[Sidoh]

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

Seems kind of inefficient to me.  Oh well.

An equally interesting problem (in my opinion) would be a Rubix Cube solver.  I was messing around with one of those on the internet.  It would probably be a bit more complicated since you have to translate numbers into motions.

[Nate]

Actually its probably the most logical.  Take the first word and use a dictionary to find all possible words it could be create multiple schemas, take the second word find all possiblites and find the schemas those words fit in, which will start eliminating schemas and eventually you will narrow it down to only a few possible matches or maybe just one at which point you run it through some kind of grammar check to make sure its intelligable solution.

[iago]

Yeah, that sounds like a good idea. 

But a twist: don't pick the first word, pick the longest one.  You can probably narrow down the longest one more quickly. 

[Nate]

I like that, it would produce less possibilities faster.  I would think the word with the most letter repetition might work even better though.  It would be interesting to do it many different ways and see what would work best; longest to shortest, shortest to longest, most individual letters to most repetition, most repetition to most individual letters, and so on.

[Sidoh]

I like that, it would produce less possibilities faster.  I would think the word with the most letter repetition might work even better though.  It would be interesting to do it many different ways and see what would work best; longest to shortest, shortest to longest, most individual letters to most repetition, most repetition to most individual letters, and so on.

Just kidding.

But seriously, yeah.  Just because it's the most logical doesn't mean it's the most efficient solution.  Then again, it could.  Who knows?!

I like the Rubix Cube solver better!

[iago]

I like that, it would produce less possibilities faster.  I would think the word with the most letter repetition might work even better though.  It would be interesting to do it many different ways and see what would work best; longest to shortest, shortest to longest, most individual letters to most repetition, most repetition to most individual letters, and so on.

I think you're right.  We probably need a balance between them.  Longer + more repeated letters, figure out the best way to weight it.  Then find a way to throw out proper names. 

This is seeming possible, but still tricky.  Who's up for the challenge?

[Warrior]

DUDE Sudokus FUCKING own. My friend can do a whole one in 5 minutes or less. It's like amazing.

[rabbit]

I can do the 3x3's in 5 minutes, it's not hard.  The 4x4 and 5x5 are fucking nuts though....

[Nate]

I can do a 9x9 in a couple of minutes.

[rabbit]

Wow, odds are you can't at all.  Sudokus are refered to by a single block (IE: square of 9 (in a 3x3)).  A 3x3 has 81 blocks.  A 9x9 would have 1369 blocks, which I doubt you can do in a couple minutes, much less a week.

[Nate]

I didn't know how you nummbered the blocks.  Fine i can do a 3x3 in a couple minutes.  A 9x9 would be do-able in a couple of hours.

[iago]

Ok, here's today's (or some recent day's.. it was sitting on the table) cryptoquote:

ORIU FUZFNFUP QGLJVUK.  WG
UGN NILJN NRI JVXVNI OFNR
V PEIVN ZVEFINK GS
BURIVXNRSBX WVFUNFID
-- QVNRIEFUI HIIQRIE

I think the best would to start with would be the second one, FUZFNFUP.  How many words could have the same letter in those places, plus the 2 U's? 

I agree, it seems like the #1 thing to do is to find the word with the most repeated letters, like that. 
Second step is to take the word that that helps us with the most, and so on.  WVFUNFID would be half solved after solving the second word, and so on. 

I can provide a dictionary if somebody else wants to work on a program that can solve this

<edit> Another good starting word might be BURIVXNRSBX..