# Descramble the scrambled text

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?

• How exactly are you sorting the strings? By ASCII value? – mdc32 Dec 20 '14 at 18:19
• Actually Unicode, but it comes to the same. – Florian F Dec 20 '14 at 19:23
• 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 – Lopsy Dec 20 '14 at 23:29
• You got a point. – Florian F Dec 21 '14 at 2:40

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?

• 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. – keshlam Dec 21 '14 at 3:25

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

• God. So close. I had most of the words but not the general concept. – mdc32 Dec 20 '14 at 18:34
• 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. – Lopsy Dec 20 '14 at 22:12
• @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. :) – pacoverflow Dec 20 '14 at 23:24