Take the 2-minute tour ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

My goal is to present the player with a scrambled word that should be reordered back into the original form:

OELHL --> HELLO

I want a scrambling algorithm that takes any given word(>3or4 letters, may contain spaces) and turns it into the least recognizable form.

While randomly moving every letter around certainly works, I noticed that not all shuffles are equal, some are more recognizable than others. I am posting this question in case someone knows of a better algorithm (maybe based on linguistics) that ~~guarantees least recognizable form.

share|improve this question
3  
Maybe you could try make sure no letter stays in its original position? –  user1306322 Mar 23 '13 at 9:27
2  
3  
"least recognizable form" How do you define that? Recognizable to whom? –  Nicol Bolas Mar 23 '13 at 11:41
1  
@Nicol Bolas its the shuffled form that makes it most difficult to guess what the ordered word is by just looking at it. –  user26471 Mar 23 '13 at 11:52
4  
@nicolbolas I think the point of the question is to ask if there has been any research or whatever along those lines to form general best practices for that kind of problem. –  Tetrad Mar 23 '13 at 13:05
show 4 more comments

2 Answers 2

up vote 26 down vote accepted

Wihle the plpuoar "Cmairbgde Uirenvtisy" sduty was lkiely a haox, trehe has been smoe resaerch itno tihs tpoic.

Tihs sduty sohws taht arpapent lteter szie pyals a rloe. The use of wpckelgraihs attmepts to debcrise the relationship beewten stes of letrets to undtrseand the pniot at wihch a wrod is undersootd.

So how to dlveeop tihs itno an aglorithm? I tnihk trehe are smoe baisc stspe:

  1. Asisgn a szie vlaue to ecah leettr
  2. For a gievn wdro:
    1. Rembmeer the szie vaule for ecah leettr posioitn.
    2. Raniomdze the letters wtih the folwoling resrtictions:
    3. Don't aollw the frist and lsat leettr to remian in tehir retpecsive potision
    4. Attempt to aiovd planicg lertets itno the "solt" of thier smae szie.

Tehre are otehr sttaregies you can emlpoy, thuogh I hvae no raseerch to bcak up the foollwing, jsut my tsoughth:

  • Aptemtt to maxzmiie the Leveishtenn ditsance between the oiigrnal and modefiid wrod. Tihs colud maxiimze the diuficflty for reczgnioing the wrod. (Pehraps use Seeuqnce Alimngent)
  • Reverse the odrer of the ltteers berofe scramilbng, tehn mvoe ecah ltteer jsut a few sapces form its onigiral position. (Mbyae slhgitly sclambred bacwkards wrod is mroe diffucilt?)

Need a translation?


While the popular "Cmabrigde Uinervtisy" study was likely a hoax, there has been some research into this topic.

This study shows that apparent letter size plays a role. The use of wickelgraphs attempts to describe the relationship between sets of letters to understand the point at which a word is understood.

So how to develop this into an algorithm? I think there are some basic steps:

  1. Assign a size value to each letter
  2. For a given word:
    1. Remember the size value for each letter position.
    2. Randomize the letters with the following restrictions:
    3. Don't allow the first and last letter to remain in their respective position
    4. Attempt to avoid placing letters into the "slot" of their same size.

There are other strategies you can employ, though I have no research to back up the following, just my thoughts:

  • Attempt to maximize the Levenshtein distance between the original and modified word. This could maximize the difficulty for recognizing the word. (Perhaps use Sequence Alignment)
  • Reverse the order of the letters before scrambling, then move each letter just a few spaces from its original position. (Maybe slightly scrambled backwards word is more difficult?)
share|improve this answer
5  
I was going to +1 until I saw that you provided a translation. ;) –  Trevor Powell Mar 24 '13 at 3:36
1  
Best application of a style to an answer EVER! :) –  Tim Holt Mar 24 '13 at 4:33
    
I've never lol'd so hard this year. –  unixunited Mar 24 '13 at 7:01
    
+1 to this excellent, excellent and excellent answer. –  Md. Mahbubur R. Aaman Mar 24 '13 at 11:03
add comment

This is not a universal solution but often if there is a word that is an anagram rather than a scramble this makes finding the original word harder. Once your brain is locked onto the original word it's hard to get that word out of your head.

i.e. decree -> recede might be harder than ecdeer -> recede.

One further point (though I'm not sure how to implement it) is to remove common pairs of letters. If an anagram has 'q' and 'u' in the answer, you want to separate them in the question. other examples might include 'th', 'ing' etc. Conversely if the letters 't' and 'h' are in the answer but not next each other, putting them together in the question makes it harder; your brain automatically thinks of words with 'th' in them.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.