12
$\begingroup$

I did something funny. I took a simple phrase.

HELLO, WORLD!

I generated all rotations of the string.

HELLO, WORLD!
ELLO, WORLD!H
LLO, WORLD!HE
LO, WORLD!HEL
O, WORLD!HELL
, WORLD!HELLO
 WORLD!HELLO,
WORLD!HELLO, 
ORLD!HELLO, W
RLD!HELLO, WO
LD!HELLO, WOR
D!HELLO, WORL
!HELLO, WORLD

Then I sorted the strings.

 WORLD!HELLO,
!HELLO, WORLD
, WORLD!HELLO
D!HELLO, WORL
ELLO, WORLD!H
HELLO, WORLD!
LD!HELLO, WOR
LLO, WORLD!HE
LO, WORLD!HEL
O, WORLD!HELL
ORLD!HELLO, W
RLD!HELLO, WO
WORLD!HELLO,

And I collected the last character of each line. I got the string:

",DOLH!RELLWO "

As you can see, it is the original message scrambled. But this was just an example. I did the same thing with a much longer message and I got the following string:

"DFKDKKWHKAADD  UDD  UUUU LLOOOOIC?CCCC CCCCUU OOOOWWWWWCHMHHHHOOO     "

Can you tell me what the message was?

Improve this question
$\endgroup$
4
  • 1
    $\begingroup$ How exactly are you sorting the strings? By ASCII value? $\endgroup$
    – mdc32
    Dec 20, 2014 at 18:19
  • $\begingroup$ Actually Unicode, but it comes to the same. $\endgroup$
    – Florian F
    Dec 20, 2014 at 19:23
  • 1
    $\begingroup$ I don't care about points, but: "I accepted pacoverflow's answer because it was given first. Even though Lopsy's answer is more informative." - what website am I on $\endgroup$
    – Lopsy
    Dec 20, 2014 at 23:29
  • $\begingroup$ You got a point. $\endgroup$
    – Florian F
    Dec 21, 2014 at 2:40

2 Answers 2

Reset to default
22
$\begingroup$

This procedure is called the Burrows-Wheeler transform. It is useful for data compression, because if the starting text contains many identical substrings ("the", "and", ...), then the Burrows-Wheeler transformation will contain many runs of identical characters.

Applying the inverse algorithm on that Wikipedia page, with a suitable guess of the location of the end-of-file marker "|", gives the answer:

HOW MUCH WOOD WOULD A WOODCHUCK CHUCK IF A WOODCHUCK COULD CHUCK WOOD?

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ Many thanks for the Wikipedia reference; I'd never heard of this one before and it's a cute and somewhat surprising (to me) result. $\endgroup$
    – keshlam
    Dec 21, 2014 at 3:25
9
$\begingroup$

The answer is:

HOW MUCH WOOD WOULD A WOODCHUCK CHUCK IF A WOODCHUCK COULD CHUCK WOOD?

All of the rotations of the string are:

HOW MUCH WOOD WOULD A WOODCHUCK CHUCK IF A WOODCHUCK COULD CHUCK WOOD?
OW MUCH WOOD WOULD A WOODCHUCK CHUCK IF A WOODCHUCK COULD CHUCK WOOD?H
W MUCH WOOD WOULD A WOODCHUCK CHUCK IF A WOODCHUCK COULD CHUCK WOOD?HO
 MUCH WOOD WOULD A WOODCHUCK CHUCK IF A WOODCHUCK COULD CHUCK WOOD?HOW
MUCH WOOD WOULD A WOODCHUCK CHUCK IF A WOODCHUCK COULD CHUCK WOOD?HOW 
UCH WOOD WOULD A WOODCHUCK CHUCK IF A WOODCHUCK COULD CHUCK WOOD?HOW M
CH WOOD WOULD A WOODCHUCK CHUCK IF A WOODCHUCK COULD CHUCK WOOD?HOW MU
H WOOD WOULD A WOODCHUCK CHUCK IF A WOODCHUCK COULD CHUCK WOOD?HOW MUC
 WOOD WOULD A WOODCHUCK CHUCK IF A WOODCHUCK COULD CHUCK WOOD?HOW MUCH
WOOD WOULD A WOODCHUCK CHUCK IF A WOODCHUCK COULD CHUCK WOOD?HOW MUCH 
OOD WOULD A WOODCHUCK CHUCK IF A WOODCHUCK COULD CHUCK WOOD?HOW MUCH W
OD WOULD A WOODCHUCK CHUCK IF A WOODCHUCK COULD CHUCK WOOD?HOW MUCH WO
D WOULD A WOODCHUCK CHUCK IF A WOODCHUCK COULD CHUCK WOOD?HOW MUCH WOO
 WOULD A WOODCHUCK CHUCK IF A WOODCHUCK COULD CHUCK WOOD?HOW MUCH WOOD
WOULD A WOODCHUCK CHUCK IF A WOODCHUCK COULD CHUCK WOOD?HOW MUCH WOOD 
OULD A WOODCHUCK CHUCK IF A WOODCHUCK COULD CHUCK WOOD?HOW MUCH WOOD W
ULD A WOODCHUCK CHUCK IF A WOODCHUCK COULD CHUCK WOOD?HOW MUCH WOOD WO
LD A WOODCHUCK CHUCK IF A WOODCHUCK COULD CHUCK WOOD?HOW MUCH WOOD WOU
D A WOODCHUCK CHUCK IF A WOODCHUCK COULD CHUCK WOOD?HOW MUCH WOOD WOUL
 A WOODCHUCK CHUCK IF A WOODCHUCK COULD CHUCK WOOD?HOW MUCH WOOD WOULD
A WOODCHUCK CHUCK IF A WOODCHUCK COULD CHUCK WOOD?HOW MUCH WOOD WOULD 
 WOODCHUCK CHUCK IF A WOODCHUCK COULD CHUCK WOOD?HOW MUCH WOOD WOULD A
WOODCHUCK CHUCK IF A WOODCHUCK COULD CHUCK WOOD?HOW MUCH WOOD WOULD A 
OODCHUCK CHUCK IF A WOODCHUCK COULD CHUCK WOOD?HOW MUCH WOOD WOULD A W
ODCHUCK CHUCK IF A WOODCHUCK COULD CHUCK WOOD?HOW MUCH WOOD WOULD A WO
DCHUCK CHUCK IF A WOODCHUCK COULD CHUCK WOOD?HOW MUCH WOOD WOULD A WOO
CHUCK CHUCK IF A WOODCHUCK COULD CHUCK WOOD?HOW MUCH WOOD WOULD A WOOD
HUCK CHUCK IF A WOODCHUCK COULD CHUCK WOOD?HOW MUCH WOOD WOULD A WOODC
UCK CHUCK IF A WOODCHUCK COULD CHUCK WOOD?HOW MUCH WOOD WOULD A WOODCH
CK CHUCK IF A WOODCHUCK COULD CHUCK WOOD?HOW MUCH WOOD WOULD A WOODCHU
K CHUCK IF A WOODCHUCK COULD CHUCK WOOD?HOW MUCH WOOD WOULD A WOODCHUC
 CHUCK IF A WOODCHUCK COULD CHUCK WOOD?HOW MUCH WOOD WOULD A WOODCHUCK
CHUCK IF A WOODCHUCK COULD CHUCK WOOD?HOW MUCH WOOD WOULD A WOODCHUCK 
HUCK IF A WOODCHUCK COULD CHUCK WOOD?HOW MUCH WOOD WOULD A WOODCHUCK C
UCK IF A WOODCHUCK COULD CHUCK WOOD?HOW MUCH WOOD WOULD A WOODCHUCK CH
CK IF A WOODCHUCK COULD CHUCK WOOD?HOW MUCH WOOD WOULD A WOODCHUCK CHU
K IF A WOODCHUCK COULD CHUCK WOOD?HOW MUCH WOOD WOULD A WOODCHUCK CHUC
 IF A WOODCHUCK COULD CHUCK WOOD?HOW MUCH WOOD WOULD A WOODCHUCK CHUCK
IF A WOODCHUCK COULD CHUCK WOOD?HOW MUCH WOOD WOULD A WOODCHUCK CHUCK 
F A WOODCHUCK COULD CHUCK WOOD?HOW MUCH WOOD WOULD A WOODCHUCK CHUCK I
 A WOODCHUCK COULD CHUCK WOOD?HOW MUCH WOOD WOULD A WOODCHUCK CHUCK IF
A WOODCHUCK COULD CHUCK WOOD?HOW MUCH WOOD WOULD A WOODCHUCK CHUCK IF 
 WOODCHUCK COULD CHUCK WOOD?HOW MUCH WOOD WOULD A WOODCHUCK CHUCK IF A
WOODCHUCK COULD CHUCK WOOD?HOW MUCH WOOD WOULD A WOODCHUCK CHUCK IF A 
OODCHUCK COULD CHUCK WOOD?HOW MUCH WOOD WOULD A WOODCHUCK CHUCK IF A W
ODCHUCK COULD CHUCK WOOD?HOW MUCH WOOD WOULD A WOODCHUCK CHUCK IF A WO
DCHUCK COULD CHUCK WOOD?HOW MUCH WOOD WOULD A WOODCHUCK CHUCK IF A WOO
CHUCK COULD CHUCK WOOD?HOW MUCH WOOD WOULD A WOODCHUCK CHUCK IF A WOOD
HUCK COULD CHUCK WOOD?HOW MUCH WOOD WOULD A WOODCHUCK CHUCK IF A WOODC
UCK COULD CHUCK WOOD?HOW MUCH WOOD WOULD A WOODCHUCK CHUCK IF A WOODCH
CK COULD CHUCK WOOD?HOW MUCH WOOD WOULD A WOODCHUCK CHUCK IF A WOODCHU
K COULD CHUCK WOOD?HOW MUCH WOOD WOULD A WOODCHUCK CHUCK IF A WOODCHUC
 COULD CHUCK WOOD?HOW MUCH WOOD WOULD A WOODCHUCK CHUCK IF A WOODCHUCK
COULD CHUCK WOOD?HOW MUCH WOOD WOULD A WOODCHUCK CHUCK IF A WOODCHUCK 
OULD CHUCK WOOD?HOW MUCH WOOD WOULD A WOODCHUCK CHUCK IF A WOODCHUCK C
ULD CHUCK WOOD?HOW MUCH WOOD WOULD A WOODCHUCK CHUCK IF A WOODCHUCK CO
LD CHUCK WOOD?HOW MUCH WOOD WOULD A WOODCHUCK CHUCK IF A WOODCHUCK COU
D CHUCK WOOD?HOW MUCH WOOD WOULD A WOODCHUCK CHUCK IF A WOODCHUCK COUL
 CHUCK WOOD?HOW MUCH WOOD WOULD A WOODCHUCK CHUCK IF A WOODCHUCK COULD
CHUCK WOOD?HOW MUCH WOOD WOULD A WOODCHUCK CHUCK IF A WOODCHUCK COULD 
HUCK WOOD?HOW MUCH WOOD WOULD A WOODCHUCK CHUCK IF A WOODCHUCK COULD C
UCK WOOD?HOW MUCH WOOD WOULD A WOODCHUCK CHUCK IF A WOODCHUCK COULD CH
CK WOOD?HOW MUCH WOOD WOULD A WOODCHUCK CHUCK IF A WOODCHUCK COULD CHU
K WOOD?HOW MUCH WOOD WOULD A WOODCHUCK CHUCK IF A WOODCHUCK COULD CHUC
 WOOD?HOW MUCH WOOD WOULD A WOODCHUCK CHUCK IF A WOODCHUCK COULD CHUCK
WOOD?HOW MUCH WOOD WOULD A WOODCHUCK CHUCK IF A WOODCHUCK COULD CHUCK 
OOD?HOW MUCH WOOD WOULD A WOODCHUCK CHUCK IF A WOODCHUCK COULD CHUCK W
OD?HOW MUCH WOOD WOULD A WOODCHUCK CHUCK IF A WOODCHUCK COULD CHUCK WO
D?HOW MUCH WOOD WOULD A WOODCHUCK CHUCK IF A WOODCHUCK COULD CHUCK WOO
?HOW MUCH WOOD WOULD A WOODCHUCK CHUCK IF A WOODCHUCK COULD CHUCK WOOD

The sorted strings are:

 A WOODCHUCK CHUCK IF A WOODCHUCK COULD CHUCK WOOD?HOW MUCH WOOD WOULD
 A WOODCHUCK COULD CHUCK WOOD?HOW MUCH WOOD WOULD A WOODCHUCK CHUCK IF
 CHUCK IF A WOODCHUCK COULD CHUCK WOOD?HOW MUCH WOOD WOULD A WOODCHUCK
 CHUCK WOOD?HOW MUCH WOOD WOULD A WOODCHUCK CHUCK IF A WOODCHUCK COULD
 COULD CHUCK WOOD?HOW MUCH WOOD WOULD A WOODCHUCK CHUCK IF A WOODCHUCK
 IF A WOODCHUCK COULD CHUCK WOOD?HOW MUCH WOOD WOULD A WOODCHUCK CHUCK
 MUCH WOOD WOULD A WOODCHUCK CHUCK IF A WOODCHUCK COULD CHUCK WOOD?HOW
 WOOD WOULD A WOODCHUCK CHUCK IF A WOODCHUCK COULD CHUCK WOOD?HOW MUCH
 WOOD?HOW MUCH WOOD WOULD A WOODCHUCK CHUCK IF A WOODCHUCK COULD CHUCK
 WOODCHUCK CHUCK IF A WOODCHUCK COULD CHUCK WOOD?HOW MUCH WOOD WOULD A
 WOODCHUCK COULD CHUCK WOOD?HOW MUCH WOOD WOULD A WOODCHUCK CHUCK IF A
 WOULD A WOODCHUCK CHUCK IF A WOODCHUCK COULD CHUCK WOOD?HOW MUCH WOOD
?HOW MUCH WOOD WOULD A WOODCHUCK CHUCK IF A WOODCHUCK COULD CHUCK WOOD
A WOODCHUCK CHUCK IF A WOODCHUCK COULD CHUCK WOOD?HOW MUCH WOOD WOULD 
A WOODCHUCK COULD CHUCK WOOD?HOW MUCH WOOD WOULD A WOODCHUCK CHUCK IF 
CH WOOD WOULD A WOODCHUCK CHUCK IF A WOODCHUCK COULD CHUCK WOOD?HOW MU
CHUCK CHUCK IF A WOODCHUCK COULD CHUCK WOOD?HOW MUCH WOOD WOULD A WOOD
CHUCK COULD CHUCK WOOD?HOW MUCH WOOD WOULD A WOODCHUCK CHUCK IF A WOOD
CHUCK IF A WOODCHUCK COULD CHUCK WOOD?HOW MUCH WOOD WOULD A WOODCHUCK 
CHUCK WOOD?HOW MUCH WOOD WOULD A WOODCHUCK CHUCK IF A WOODCHUCK COULD 
CK CHUCK IF A WOODCHUCK COULD CHUCK WOOD?HOW MUCH WOOD WOULD A WOODCHU
CK COULD CHUCK WOOD?HOW MUCH WOOD WOULD A WOODCHUCK CHUCK IF A WOODCHU
CK IF A WOODCHUCK COULD CHUCK WOOD?HOW MUCH WOOD WOULD A WOODCHUCK CHU
CK WOOD?HOW MUCH WOOD WOULD A WOODCHUCK CHUCK IF A WOODCHUCK COULD CHU
COULD CHUCK WOOD?HOW MUCH WOOD WOULD A WOODCHUCK CHUCK IF A WOODCHUCK 
D A WOODCHUCK CHUCK IF A WOODCHUCK COULD CHUCK WOOD?HOW MUCH WOOD WOUL
D CHUCK WOOD?HOW MUCH WOOD WOULD A WOODCHUCK CHUCK IF A WOODCHUCK COUL
D WOULD A WOODCHUCK CHUCK IF A WOODCHUCK COULD CHUCK WOOD?HOW MUCH WOO
D?HOW MUCH WOOD WOULD A WOODCHUCK CHUCK IF A WOODCHUCK COULD CHUCK WOO
DCHUCK CHUCK IF A WOODCHUCK COULD CHUCK WOOD?HOW MUCH WOOD WOULD A WOO
DCHUCK COULD CHUCK WOOD?HOW MUCH WOOD WOULD A WOODCHUCK CHUCK IF A WOO
F A WOODCHUCK COULD CHUCK WOOD?HOW MUCH WOOD WOULD A WOODCHUCK CHUCK I
H WOOD WOULD A WOODCHUCK CHUCK IF A WOODCHUCK COULD CHUCK WOOD?HOW MUC
HOW MUCH WOOD WOULD A WOODCHUCK CHUCK IF A WOODCHUCK COULD CHUCK WOOD?
HUCK CHUCK IF A WOODCHUCK COULD CHUCK WOOD?HOW MUCH WOOD WOULD A WOODC
HUCK COULD CHUCK WOOD?HOW MUCH WOOD WOULD A WOODCHUCK CHUCK IF A WOODC
HUCK IF A WOODCHUCK COULD CHUCK WOOD?HOW MUCH WOOD WOULD A WOODCHUCK C
HUCK WOOD?HOW MUCH WOOD WOULD A WOODCHUCK CHUCK IF A WOODCHUCK COULD C
IF A WOODCHUCK COULD CHUCK WOOD?HOW MUCH WOOD WOULD A WOODCHUCK CHUCK 
K CHUCK IF A WOODCHUCK COULD CHUCK WOOD?HOW MUCH WOOD WOULD A WOODCHUC
K COULD CHUCK WOOD?HOW MUCH WOOD WOULD A WOODCHUCK CHUCK IF A WOODCHUC
K IF A WOODCHUCK COULD CHUCK WOOD?HOW MUCH WOOD WOULD A WOODCHUCK CHUC
K WOOD?HOW MUCH WOOD WOULD A WOODCHUCK CHUCK IF A WOODCHUCK COULD CHUC
LD A WOODCHUCK CHUCK IF A WOODCHUCK COULD CHUCK WOOD?HOW MUCH WOOD WOU
LD CHUCK WOOD?HOW MUCH WOOD WOULD A WOODCHUCK CHUCK IF A WOODCHUCK COU
MUCH WOOD WOULD A WOODCHUCK CHUCK IF A WOODCHUCK COULD CHUCK WOOD?HOW 
OD WOULD A WOODCHUCK CHUCK IF A WOODCHUCK COULD CHUCK WOOD?HOW MUCH WO
OD?HOW MUCH WOOD WOULD A WOODCHUCK CHUCK IF A WOODCHUCK COULD CHUCK WO
ODCHUCK CHUCK IF A WOODCHUCK COULD CHUCK WOOD?HOW MUCH WOOD WOULD A WO
ODCHUCK COULD CHUCK WOOD?HOW MUCH WOOD WOULD A WOODCHUCK CHUCK IF A WO
OOD WOULD A WOODCHUCK CHUCK IF A WOODCHUCK COULD CHUCK WOOD?HOW MUCH W
OOD?HOW MUCH WOOD WOULD A WOODCHUCK CHUCK IF A WOODCHUCK COULD CHUCK W
OODCHUCK CHUCK IF A WOODCHUCK COULD CHUCK WOOD?HOW MUCH WOOD WOULD A W
OODCHUCK COULD CHUCK WOOD?HOW MUCH WOOD WOULD A WOODCHUCK CHUCK IF A W
OULD A WOODCHUCK CHUCK IF A WOODCHUCK COULD CHUCK WOOD?HOW MUCH WOOD W
OULD CHUCK WOOD?HOW MUCH WOOD WOULD A WOODCHUCK CHUCK IF A WOODCHUCK C
OW MUCH WOOD WOULD A WOODCHUCK CHUCK IF A WOODCHUCK COULD CHUCK WOOD?H
UCH WOOD WOULD A WOODCHUCK CHUCK IF A WOODCHUCK COULD CHUCK WOOD?HOW M
UCK CHUCK IF A WOODCHUCK COULD CHUCK WOOD?HOW MUCH WOOD WOULD A WOODCH
UCK COULD CHUCK WOOD?HOW MUCH WOOD WOULD A WOODCHUCK CHUCK IF A WOODCH
UCK IF A WOODCHUCK COULD CHUCK WOOD?HOW MUCH WOOD WOULD A WOODCHUCK CH
UCK WOOD?HOW MUCH WOOD WOULD A WOODCHUCK CHUCK IF A WOODCHUCK COULD CH
ULD A WOODCHUCK CHUCK IF A WOODCHUCK COULD CHUCK WOOD?HOW MUCH WOOD WO
ULD CHUCK WOOD?HOW MUCH WOOD WOULD A WOODCHUCK CHUCK IF A WOODCHUCK CO
W MUCH WOOD WOULD A WOODCHUCK CHUCK IF A WOODCHUCK COULD CHUCK WOOD?HO
WOOD WOULD A WOODCHUCK CHUCK IF A WOODCHUCK COULD CHUCK WOOD?HOW MUCH 
WOOD?HOW MUCH WOOD WOULD A WOODCHUCK CHUCK IF A WOODCHUCK COULD CHUCK 
WOODCHUCK CHUCK IF A WOODCHUCK COULD CHUCK WOOD?HOW MUCH WOOD WOULD A 
WOODCHUCK COULD CHUCK WOOD?HOW MUCH WOOD WOULD A WOODCHUCK CHUCK IF A 
WOULD A WOODCHUCK CHUCK IF A WOODCHUCK COULD CHUCK WOOD?HOW MUCH WOOD
Improve this answer
$\endgroup$
3
  • $\begingroup$ God. So close. I had most of the words but not the general concept. $\endgroup$
    – mdc32
    Dec 20, 2014 at 18:34
  • $\begingroup$ Those enormous data dumps are not enlightening at all. It'd be great if you deleted them and replaced them with an explanation of how you unscrambled the message. $\endgroup$
    – Lopsy
    Dec 20, 2014 at 22:12
  • 2
    $\begingroup$ @Lopsy The data dumps are just to prove that the answer indeed forms the scrambled string. I wanted to provide the same steps that the OP provided for "HELLO, WORLD!" I did not use any techniques to get the answer. I just looked at the scrambled string and thought it might be "HOW MUCH WOOD WOULD..." and then I verified that it was. I'm a good Scrabble player. :) $\endgroup$
    – pacoverflow
    Dec 20, 2014 at 23:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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