fork(2) download 
  1. -- shredsolver.hs
  2. --
  3. -- this is part two of the optional programming assignment for the
  4. -- Stanford Univerity Introduction to Artificial Intelligence class,
  5. -- which was to decode a message which was shredded into a random jumble of
  6. -- strips.
  7. --
  8. -- The approach taken was to greedily combine strips from left to right 
  9. -- until all strips have been used. That is, we choose an initial starting strip,
  10. -- then try all remaining strips, and choose the one that results in the
  11. -- highest score for the combined strips based on trigram frequency, then
  12. -- repeat until all strips used.
  13. -- We then repeat, this time choosing the starting strip from each of the candidates,
  14. -- and the result with the best score is our winner.
  15. --
  16. -- To arrive at the correct result required some tweaking of the scoring.
  17. -- In my first attempt, the first 15 or so strips would be correct but the last 4 would be 
  18. -- jumbled... I think this was because the last line is mostly blank, which 
  19. -- upset the scoring, which was based on the sum of the log probability score 
  20. -- for each row. Using only the first 6 out of 8 rows for scoring improved this
  21. -- significantly, however the correct answer was actually the third highest scoring result.
  22. -- The other two were almost correct but started with a column of spaces.
  23. -- Tweaking the scoring code to punish rows with a leading space ( assuming the text
  24. -- is left justified) brought the correct answer to the top of the list.
  25. --
  26. -- source for trigram data is here: http://h...content-available-to-author-only...l.org/~cowan/trigrams
  27. -- the trigram data is read from std input
  28. --
  29. -- PAC 28th January, 2012
  30.  
  31. import Data.Char (isLetter, toUpper, isSpace)
  32. import Data.List (sortBy, delete)
  33. import Data.Ord (comparing)
  34. import qualified Data.Map as M
  35. import System.IO
  36. import System.Environment
  37. import Control.Monad
  38.  
  39. -- the code to break
  40.  
  41. defaultShreddedMsg = "de|  | f|Cl|nf|ed|au| i|ti|  |ma|ha|or|nn|ou| S|on|nd|on\n\
  42.  \ry|  |is|th|is| b|eo|as|  |  |f |wh| o|ic| t|, |  |he|h \n\
  43.  \ab|  |la|pr|od|ge|ob| m|an|  |s |is|el|ti|ng|il|d |ua|c \n\
  44.  \he|  |ea|of|ho| m| t|et|ha|  | t|od|ds|e |ki| c|t |ng|br\n\
  45.  \wo|m,|to|yo|hi|ve|u | t|ob|  |pr|d |s |us| s|ul|le|ol|e \n\
  46.  \ t|ca| t|wi| M|d |th|\"A|ma|l |he| p|at|ap|it|he|ti|le|er\n\
  47.  \ry|d |un|Th|\" |io|eo|n,|is|  |bl|f |pu|Co|ic| o|he|at|mm\n\
  48.  \hi|  |  |in|  |  | t|  |  |  |  |ye|  |ar|  |s |  |  |. "
  49.  
  50. -- define a datatype for our map of trigram frequencies for clarity
  51. type TrigramFrequencies = M.Map String Int
  52.  
  53. -- a strip of our shredded message is simply a list of strings
  54. type Strip = [String]
  55.  
  56. -- ShredState encapsulates the score for the current strip, and the remaining strips to be matched
  57. type ShredState = ( Double, Strip, [Strip] )
  58.  
  59. -- helper function for creating a ShredState
  60. makeShredState::Double -> Strip -> [Strip] -> ShredState
  61. makeShredState score strip strips = (score, strip, strips)
  62.  
  63. -- define an infinitely long empty strip which will be useful for our initial state
  64. -- don't you love lazy evaluation?
  65. emptyStrip  = [ [] | x <- [0..] ]
  66.  
  67. -- function returns our initial state 
  68. initialState strips = makeShredState 0 emptyStrip strips
  69.  
  70. -- helpers for dealing with ShredStates
  71.  
  72. getDecodedMessageStrip:: ShredState -> Strip
  73. getDecodedMessageStrip ( _, b, _ ) = b
  74.  
  75. getRemainingStrips:: ShredState -> [Strip]
  76. getRemainingStrips ( _, _, c ) = c
  77.  
  78. -- helper for sorting a list of ShredStates in descending order of score
  79. onScore:: ShredState -> ShredState -> Ordering
  80. onScore ( a,_,_) (b,_,_) 
  81.                                     | a > b = LT
  82.                                     | a < b = GT
  83.                                     | a == b = EQ
  84.  
  85. -- splits a delimited string into a list of string representing the text found between the delimiters
  86. split :: Char -> String -> [String]
  87. split delim [] = [""]
  88. split delim (c:cs)
  89.    | c == delim = "" : rest
  90.    | otherwise = (c : head rest) : tail rest
  91.    where
  92.        rest = split delim cs
  93.  
  94. --parse the shredded msg string into a more computer friendly form
  95. --firstParse converts the input to a list of lines, where each lines is a list of strings
  96. --representing the strings appearing on each strip that makes up the line
  97. makeStrips:: String -> [Strip]
  98. makeStrips str = [ map ( !! index ) (firstParse str) | index <- [ 0 .. (length $ head $ firstParse str) - 1] ]
  99. 				where 
  100. 						firstParse = map (split '|') . lines
  101.  
  102. join2Strips::Strip -> Strip ->Strip
  103. join2Strips = zipWith joinRowsOfStrip
  104.                     where joinRowsOfStrip r1 r2 = r1 ++ "|" ++ r2
  105.  
  106. -- just to check we parsed the strips correctly
  107. joinManyStrips::[Strip] -> Strip
  108. joinManyStrips [x] = x
  109. joinManyStrips (x:y:z) = joinManyStrips ((join2Strips x y):z)
  110.  
  111. --parse a line from the trigams data file into a tuple of trigram and frequency per 10000 words
  112. parseTrigram:: String -> [ (String,Int) ]
  113. parseTrigram contents = [ lineToTuple( words x ) | x <- lines(contents), head x /= ';' ]
  114.       where lineToTuple [ trigram, frequency ] = ( trigram, read frequency :: Int)
  115.  
  116. -- loads the trigram frequency data into a Map for fast lookup
  117. -- source for trigram data is here: http://h...content-available-to-author-only...l.org/~cowan/trigrams
  118. -- we read it in from stdin
  119. -- returns an IO action yielding a Map containing a trigram and it's frequency per 10000 words
  120. loadTrigrams:: IO (TrigramFrequencies)
  121. loadTrigrams = fmap (M.fromList . parseTrigram) $ getContents
  122.  
  123. -- preprocess our string for trigram lookup. Converts all non letters to # and the rest to uppercase
  124. preprocessText:: String -> String
  125. preprocessText text = map processChar text
  126.          where processChar c = if isLetter c then toUpper c else '#'
  127.  
  128. -- split a string into character trigrams
  129. splitIntoTrigrams:: String -> [String] 
  130. splitIntoTrigrams str = [ take 3 $ drop x str | x <- [ 0 .. (length str - 3) ] ]
  131.  
  132. -- lookup the trigram frequencies per 10000 words. If not found it will return 0
  133. lookupTrigramFrequency:: TrigramFrequencies -> String -> Int
  134. lookupTrigramFrequency trigramFrequencies trigram = M.findWithDefault 0 trigram trigramFrequencies
  135.  
  136. -- converts a letter frequency into a probability using laplace smoothing so we don't end up with
  137. -- trigrams that were not found borking our calculations (due to multiplying by 0)
  138. laplaceSmoothedProbability:: Int -> Int -> Int -> Double
  139. laplaceSmoothedProbability frequency totalCategories k = (fromIntegral(frequency) + fromIntegral(k))/(10000.0 + fromIntegral(k)*fromIntegral(totalCategories))
  140.  
  141. -- returns the log of the probability for a trigram. We use logs so we don't endup dealing with
  142. -- really small numbers caused by multiplying small numbers. We can just sum the logs instead.
  143. calcLogOfSmoothedProbabilityForTrigram:: TrigramFrequencies -> String -> Double 
  144. calcLogOfSmoothedProbabilityForTrigram trigramFrequencies trigram = log $ laplaceSmoothedProbability score numClasses k
  145.                                                                             where score = lookupTrigramFrequency trigramFrequencies $ preprocessText trigram
  146.                                                                                   numClasses = M.size trigramFrequencies
  147.                                                                                   k = 1
  148.  
  149. -- calculates the score for a string based on the probabilities of all the trigrams it contains
  150. scoreString:: TrigramFrequencies -> String -> Double
  151. scoreString trigramFrequencies  =  sum . map ( calcLogOfSmoothedProbabilityForTrigram trigramFrequencies ) . splitIntoTrigrams  
  152.  
  153. -- this function attempts to mark down strings that begin with spaces. We are making the assumption that the text is 
  154. -- left justified.
  155. scoreStringPunishLeadingSpaces:: TrigramFrequencies -> String -> Double
  156. scoreStringPunishLeadingSpaces trigramFrequencies str = if (isSpace $ head str ) then ((scoreString trigramFrequencies str) + log 0.0000001) else (scoreString trigramFrequencies str)
  157.  
  158. --takes two strips and joins them to produce a wider strip with the first strip to the left of the second strip
  159. combineStrips::Strip -> Strip ->Strip
  160. combineStrips  = zipWith (++)
  161.  
  162. -- take the product of the probabilities for each row of the strip in order to give the strip a score
  163. -- just use the first 6 rows as they are the complete lines (no partial lines), which seems to give a better result
  164. scoreStrip:: TrigramFrequencies -> Strip -> Double
  165. scoreStrip trigramFrequencies = sum . take 6. map (scoreStringPunishLeadingSpaces trigramFrequencies)
  166.  
  167. -- expand the existing strip with each of the candidate strips and score it
  168. -- result is a list of ShredStates, each one step closer to our goal, scored from most likely to least likeley
  169. expandShredState::TrigramFrequencies -> ShredState -> [ShredState]
  170. expandShredState trigramFrequencies state = sortBy onScore $ zip3 score combined remainingStrips
  171.                                             where combined = map (combineStrips (getDecodedMessageStrip state)) (getRemainingStrips state)
  172.                                                   score = map (scoreStrip trigramFrequencies) combined
  173.                                                   remainingStrips = [ delete x (getRemainingStrips state) | x <- (getRemainingStrips state) ]
  174.  
  175. -- chooses the best expansion of the current state, ie: the one with the highest trigram score
  176. chooseBestExpansion:: TrigramFrequencies -> ShredState -> ShredState
  177. chooseBestExpansion trigramFrequencies state = head $ expandShredState trigramFrequencies state
  178.  
  179. -- greedily combine strips, building on the most likely expansion at each level
  180. matchAll:: TrigramFrequencies -> ShredState -> ShredState
  181. matchAll trigramFrequencies ( score, existingStrip, [] ) = ( score, existingStrip, [] ) 
  182. matchAll trigramFrequencies state = matchAll trigramFrequencies $ chooseBestExpansion trigramFrequencies state
  183.  
  184. -- try starting with each strip and see what falls out 
  185. startWithEachStripThenMatchAll trigramFrequencies strips =  sortBy onScore $ [ matchAll trigramFrequencies state | state <- expandShredState trigramFrequencies $ initialState strips ]
  186.  
  187. -- displays the string along with its score
  188. displayScoredMsg:: (Double, Strip, [Strip] ) -> IO ()
  189. displayScoredMsg (score, strip, strips) = do
  190.                                             putStr "score: "
  191.                                             putStrLn $ show score 
  192.                                             putStrLn ""
  193.                                             putStrLn $ unlines strip
  194.  
  195. -- parse arguments, if no supplied use default
  196. parseArgs:: [String] -> String
  197. parseArgs args = if null args then defaultShreddedMsg else head args
  198.  
  199. -- entry point
  200. main = do 
  201. 		trigramFrequencies <- loadTrigrams  
  202. 		args <- getArgs
  203. 		let msg = parseArgs args
  204.           	putStrLn "Shredded Message Solver (ai-class)\n"
  205. 		let strips = makeStrips msg
  206. 		putStrLn  "shredded message:"
  207. 		putStrLn $  unlines $ joinManyStrips strips
  208. 		putStrLn "Top 3 results..."
  209. 		mapM_ displayScoredMsg $ take 3 $ startWithEachStripThenMatchAll trigramFrequencies strips
  210.  
  211.  
  212.  
Success #stdin #stdout 0.51s 3812KB
comments (?)
stdin 
; English trigram frequency table
;
; This table is in the public domain, and is derived from the Brown Corpus.
; # signifies a word boundary, where words are defined as sequences of letters
;   bounded by non-letters (hence the high frequency of #S#, based on "'s").
; The numbers are frequency of the trigram in Brown per 10,000 words.
; Trigrams less frequent than that are omitted.
;
;
#TH	230
THE	192
HE#	172
#S#	129
ED#	86
#OF	81
#AN	78
OF#	77
ND#	75
#IN	71
AND	70
#TO	64
ING	62
NG#	62
ER#	61
TO#	58
ON#	58
IN#	54
IS#	49
#A#	48
#CO	47
ES#	47
ION	47
RE#	46
AS#	42
AT#	41
ENT	38
#BE	38
TIO	37
OR#	37
#HE	36
#RE	34
LY#	34
#HA	33
HER	32
FOR	32
#FO	31
#WA	31
EN#	31
AL#	30
AN#	30
#WH	29
NT#	28
#MA	27
#WI	27
HAT	27
TER	26
THA	26
ST#	26
ATI	26
HIS	26
#ON	26
ERE	26
#PR	25
#ST	25
#HI	25
TH#	25
LL#	24
#IT	23
LE#	23
CE#	23
#IS	23
#NO	23
TS#	23
ATE	22
IT#	22
VE#	22
SE#	21
ALL	21
WAS	20
UT#	20
VER	20
#SE	20
#AS	20
#WE	20
#DE	19
#CA	19
RS#	19
CH#	19
ME#	19
CON	19
ITH	18
LD#	18
THI	18
RES	18
#SO	18
TED	18
#MO	18
NCE	17
WIT	17
#SH	17
ERS	17
MEN	17
NE#	17
#AR	16
NS#	16
ONS	16
ARE	16
#DI	16
#AL	16
PRO	16
RY#	16
REA	15
EVE	15
#FR	15
STA	15
#WO	15
TE#	15
#LI	15
ESS	15
AD#	15
#SU	14
COM	14
#AT	14
IVE	14
#BU	14
#PA	14
TY#	14
#ME	14
ONE	14
BE#	14
EST	14
EAR	14
NOT	13
AY#	13
#FI	13
PER	13
OUT	13
INT	13
#SA	13
ECT	13
OT#	13
ILL	13
OME	12
#PO	12
MAN	12
#NE	12
#OR	12
#CH	12
IST	12
#HO	12
#DO	12
ICA	12
AVE	12
GHT	11
BY#	11
TIN	11
OUL	11
OM#	11
AIN	11
IGH	11
OVE	11
IDE	11
SS#	11
#UN	11
ULD	11
#EX	11
INE	11
#BY	11
DER	11
#LO	11
ORE	11
CTI	11
STR	11
#YO	10
#FA	10
NTE	10
EY#	10
ROM	10
RED	10
#LE	10
#I#	10
#PE	10
OUR	10
RAT	10
OUN	10
#LA	10
HAD	10
#TR	10
BLE	10
PRE	10
HIN	10
WHI	10
AR#	10
OTH	10
STI	10
#MI	10
FRO	10
TRA	10
YOU	10
STE	10
OW#	10
#SI	10
ITI	10
UND	10
BUT	10
ET#	10
CAL	9
ANT	9
ART	9
IC#	9
HOU	9
GE#	9
HAN	9
#GR	9
WER	9
#BA	9
ERI	9
ACT	9
ORT	9
DE#	9
COU	9
URE	9
NTI	9
TUR	9
SHE	9
TIC	9
HAV	9
HEN	9
IND	9
ERA	9
HT#	9
ENC	9
#GO	9
#BO	9
EEN	8
THO	8
HIC	8
#OU	8
US#	8
AME	8
OUS	8
DS#	8
PAR	8
ITY	8
ID#	8
NDE	8
ROU	8
WHE	8
UGH	8
#EN	8
RIN	8
ICH	8
#TE	8
USE	8
IES	8
LIN	8
CAN	8
TEN	8
EAS	8
TOR	8
MIN	7
#AC	7
NED	7
UST	7
EAT	7
KE#	7
PLA	7
HEY	7
SSI	7
#SP	7
ARD	7
TAT	7
LIT	7
OUG	7
NAL	7
#PL	7
AGE	7
MOR	7
LES	7
IR#	7
ANC	7
ABL	7
LLY	7
END	7
WOR	7
DEN	7
RD#	7
AST	7
ITE	7
#FE	7
#RA	7
ELL	7
NY#	7
#CL	7
#BR	7
TTE	7
ESE	7
ANY	7
CK#	7
#EV	7
VEN	7
RT#	7
OU#	7
IAL	7
PLE	6
DIN	6
OSE	6
EW#	6
#TA	6
CES	6
OWN	6
ONT	6
ASS	6
REC	6
INC	6
RAN	6
INS	6
#MU	6
SIN	6
NIN	6
SED	6
TAN	6
#AB	6
LAT	6
LAN	6
NAT	6
HIM	6
IME	6
#DA	6
CHA	6
NTS	6
CT#	6
ONG	6
EAD	6
REN	6
SO#	6
SHO	6
TIM	6
EME	6
RIE	6
ICE	6
SIO	6
UR#	6
LLE	6
REE	6
DIS	6
WHO	6
LEA	6
OST	6
LED	6
RAL	6
EM#	6
TIV	6
NES	6
#RO	6
CHE	6
GH#	6
BER	6
WN#	6
ONA	6
HES	6
IM#	6
LS#	6
ACE	6
APP	6
#TI	6
HAS	6
SOM	6
SON	6
WIL	6
AKE	6
RIC	6
TRI	6
ERN	5
HEI	5
POS	5
SEN	5
WE#	5
WOU	5
ACH	5
GRE	5
#AF	5
ADE	5
UNI	5
MER	5
KIN	5
#GE	5
TES	5
STO	5
SPE	5
ITS	5
NOW	5
OMP	5
OPE	5
EIR	5
NDI	5
ENE	5
#UP	5
#SC	5
EE#	5
IRE	5
HEA	5
CHI	5
POR	5
ACK	5
#YE	5
BEE	5
OD#	5
NER	5
DED	5
#PU	5
#EA	5
LAR	5
CAT	5
SEL	5
#AD	5
RIT	5
ATT	5
SID	5
ORM	5
GRA	5
ABO	5
UNT	5
HAR	5
#US	5
MAT	5
OLD	5
NGE	5
NEW	5
ANG	5
UCH	5
ANS	5
#AG	5
NST	5
#NA	5
#DR	5
ENS	5
ORD	5
THR	5
DES	5
UP#	5
ELY	5
MS#	5
HOW	5
HEM	5
EXP	5
NSI	5
#AP	5
AID	5
INA	5
ILE	5
ECO	4
ARI	4
LOW	4
ALI	4
MON	4
#IM	4
SER	4
MPL	4
SIT	4
CEN	4
UAL	4
ERY	4
NO#	4
FIC	4
WAR	4
MAR	4
TAL	4
HO#	4
IEN	4
PEN	4
SEE	4
WAY	4
ARY	4
#CR	4
#AM	4
OWE	4
ISH	4
LIC	4
SES	4
PRI	4
NTR	4
ATH	4
EAC	4
SSE	4
OMM	4
ELE	4
NLY	4
ERT	4
OOD	4
SUR	4
LON	4
#CE	4
IF#	4
TAI	4
#RI	4
ASE	4
WHA	4
INI	4
#IF	4
FAC	4
#OT	4
DAY	4
ALS	4
CRE	4
OND	4
VEL	4
ELI	4
OOK	4
NTO	4
BOU	4
OLL	4
RAC	4
PEC	4
IMP	4
ILI	4
CIA	4
REL	4
NIT	4
#VI	4
MIL	4
FIR	4
HIL	4
TRO	4
KED	4
FFE	4
GEN	4
#JU	4
TRE	4
ARS	4
RIS	4
EAL	4
NTA	4
CAR	4
RST	4
MED	4
#TW	4
LF#	4
EL#	4
LAS	4
#T#	4
FER	4
FIN	4
TLE	4
#KN	4
DY#	4
#OP	4
#QU	4
LIS	4
MBE	4
IKE	4
EED	4
SAI	4
RTI	4
MOS	4
TLY	4
RN#	3
TIE	3
ITT	3
ORK	3
SHI	3
#VE	3
ORI	3
IVI	3
ETE	3
REP	3
YEA	3
LLI	3
QUI	3
GER	3
REM	3
OLI	3
HED	3
NDS	3
ANI	3
TEM	3
UE#	3
#FU	3
PPE	3
FTE	3
GS#	3
GIN	3
COR	3
GRO	3
#GA	3
RK#	3
VES	3
OFF	3
VED	3
ONL	3
ETH	3
OIN	3
ERV	3
YS#	3
IAN	3
DUC	3
ESI	3
RIA	3
MET	3
TIL	3
MUS	3
ISE	3
ONC	3
RGE	3
CER	3
ULT	3
FUL	3
#OV	3
SUC	3
ULA	3
LIE	3
#PI	3
QUE	3
RET	3
ARR	3
LIK	3
TAR	3
TEL	3
SH#	3
COL	3
USI	3
BEC	3
TRU	3
WIN	3
MY#	3
IRS	3
IED	3
LAC	3
#VA	3
ETT	3
ITA	3
EQU	3
HOL	3
LOO	3
#GI	3
ORS	3
RSE	3
LET	3
IGN	3
IOU	3
TON	3
MAY	3
VIN	3
ERM	3
ROP	3
TOO	3
#BI	3
OSS	3
RTH	3
MIS	3
IL#	3
#HU	3
ISS	3
MES	3
ECE	3
ECI	3
OTE	3
#FL	3
URN	3
AM#	3
CLE	3
CHO	3
RAI	3
ICI	3
#BL	3
RON	3
AIL	3
PON	3
NGS	3
#JO	3
TWO	3
ARL	3
AIR	3
BLI	3
ELF	3
CED	3
SEC	3
GET	3
#EL	3
HOS	3
PEA	3
LIG	3
NSE	3
#CU	3
LLO	3
CTE	3
ISI	3
EAN	3
RCH	3
WO#	3
UES	3
HEL	3
ATU	3
#MY	3
DIT	3
EDI	3
KS#	3
MAL	3
HRO	3
VID	3
CUL	3
ANN	3
RTA	3
HOR	3
DID	3
DO#	3
UTI	3
RIG	3
RMA	3
#RU	3
LEC	3
NIS	3
AFT	3
AYS	3
WEL	3
CLA	3
ETI	3
POL	3
PS#	3
GES	3
IZE	3
ROV	3
DEA	3
FFI	3
SHA	3
WEE	3
SIS	3
RAD	2
AUS	2
OMI	2
ARK	2
ECA	2
GAI	2
KNO	2
#DU	2
NOR	2
URI	2
RNE	2
MEA	2
EPT	2
XPE	2
ALE	2
EMB	2
UCT	2
DOW	2
ACC	2
ICT	2
#CI	2
UTH	2
AGA	2
RIO	2
RCE	2
ADI	2
EET	2
#MR	2
URS	2
ARG	2
CAU	2
ROW	2
ESP	2
LEN	2
TTL	2
EMP	2
STU	2
TAK	2
LOS	2
ARA	2
ILD	2
PAT	2
FOU	2
BRO	2
TCH	2
TIT	2
MAK	2
EFO	2
EXT	2
NNE	2
RM#	2
ICK	2
CIE	2
SOU	2
PED	2
QUA	2
MIT	2
SPO	2
OL#	2
IMA	2
FRE	2
BET	2
IFI	2
OLE	2
BAC	2
SIG	2
ASI	2
MAD	2
OOL	2
STS	2
SCH	2
ENG	2
RDE	2
ROB	2
HOO	2
ELO	2
IAT	2
BRI	2
CIT	2
UBL	2
MPA	2
BIL	2
ORY	2
NCI	2
#SL	2
VAL	2
LT#	2
CAM	2
OCK	2
RRI	2
RTE	2
RLY	2
DIC	2
ITU	2
HAL	2
DRE	2
ORA	2
RAM	2
IFF	2
#EM	2
OK#	2
JUS	2
REF	2
OLO	2
CUR	2
LSO	2
FE#	2
REV	2
MPO	2
#KI	2
#OB	2
#SM	2
LEM	2
ULL	2
EMA	2
ARM	2
SUP	2
NGL	2
TAB	2
EVI	2
OVI	2
UDE	2
DON	2
NIC	2
LAY	2
REG	2
UTE	2
IBL	2
ROS	2
RRE	2
YIN	2
IFE	2
OCI	2
#TU	2
TUD	2
EIN	2
BEL	2
UNC	2
URA	2
TRY	2
VIS	2
#PH	2
CAS	2
ISC	2
TIA	2
PIN	2
#WR	2
LIF	2
RIV	2
SOC	2
GAN	2
EMS	2
ALT	2
NTL	2
PAN	2
SUB	2
#KE	2
#SY	2
PE#	2
DEC	2
CKE	2
GO#	2
CTO	2
FEE	2
EFF	2
CTU	2
HOM	2
HAP	2
UL#	2
CRI	2
DEV	2
#AU	2
ELA	2
ROO	2
#NU	2
AF#	2
AMP	2
LER	2
PPO	2
LOC	2
AMI	2
FF#	2
ILY	2
OSI	2
EGA	2
SIB	2
#NI	2
NDA	2
GIV	2
VIC	2
HIG	2
EMO	2
ROA	2
SIC	2
IA#	2
#ES	2
DIF	2
PAS	2
CLU	2
MME	2
TIS	2
TWE	2
DEP	2
NK#	2
TUA	2
LEG	2
IP#	2
ANO	2
CY#	2
SPI	2
PLI	2
NEE	2
NCH	2
#VO	2
ATO	2
#GU	2
GED	2
ANE	2
OGR	2
EEM	2
IMI	2
CLO	2
SOL	2
INK	2
RDS	2
BEF	2
MIC	2
ROD	2
CTS	2
DIE	2
#OW	2
BOR	2
HRE	2
MEM	2
TEE	2
BOT	2
HIP	2
ROC	2
SET	2
ROL	2
DGE	2
ODE	2
ENI	2
DIA	2
ANA	2
UMB	2
#EF	2
AUT	2
SAM	2
MOT	2
SSU	2
IET	2
URT	2
WS#	2
EIG	2
JEC	2
ORG	2
RNI	2
TTI	2
KEN	2
ORL	2
RUS	2
RVE	2
BAS	2
MOV	2
FIE	2
OKE	1
ELD	1
WAT	1
ORN	1
INF	1
OTI	1
PT#	1
UPP	1
MAI	1
GOO	1
MUC	1
EGI	1
TOW	1
POI	1
EOP	1
#OL	1
OPL	1
AVI	1
ROG	1
PTI	1
SMA	1
SEA	1
ROT	1
ETA	1
EDU	1
URC	1
UME	1
FT#	1
RMI	1
FAR	1
CEP	1
PUB	1
PEO	1
CRO	1
LOR	1
RIB	1
LUE	1
SCO	1
NEV	1
EXC	1
EEP	1
RTS	1
MOU	1
LVE	1
RVI	1
APE	1
ISM	1
LOG	1
ERC	1
MSE	1
LOP	1
FEC	1
RSO	1
#JA	1
EPA	1
LAI	1
RLD	1
TEA	1
RKE	1
UNG	1
YST	1
AW#	1
ADD	1
SCR	1
RIM	1
DIV	1
ODU	1
#ED	1
LIV	1
OLU	1
RAG	1
ASH	1
UM#	1
OES	1
INV	1
HY#	1
ONO	1
INU	1
DEL	1
TOM	1
VOL	1
CAP	1
ONI	1
ICU	1
OOR	1
#AI	1
DUR	1
BAN	1
EEL	1
OMA	1
TME	1
ANK	1
ARC	1
PAI	1
OPP	1
BLY	1
UIT	1
EXA	1
LIA	1
VIE	1
OO#	1
WAL	1
SAY	1
OCA	1
SAL	1
ERR	1
#SW	1
DIR	1
NUM	1
CCE	1
EDE	1
MR#	1
AWA	1
LLA	1
FOL	1
ORC	1
GAT	1
OAD	1
AMO	1
OP#	1
DEM	1
EEK	1
DET	1
BUR	1
SIM	1
PIC	1
RME	1
IE#	1
MAG	1
PUT	1
MUN	1
#ID	1
NTH	1
MPE	1
RUC	1
SAN	1
KER	1
NME	1
WED	1
ETW	1
ASK	1
#AW	1
ELS	1
SM#	1
SUM	1
FRA	1
SSA	1
NCL	1
SLA	1
RAP	1
OUP	1
CRA	1
NOM	1
BEI	1
PIT	1
HUR	1
ARO	1
ZED	1
RID	1
EAK	1
FRI	1
ALO	1
MIG	1
BEA	1
MMU	1
WRI	1
IMS	1
TEC	1
PPR	1
ONF	1
HIT	1
UAT	1
IER	1
NVE	1
SOR	1
EP#	1
PPL	1
REQ	1
BAR	1
EMI	1
FAI	1
EA#	1
NNI	1
EFE	1
ENO	1
WEN	1
NDU	1
ERF	1
DRI	1
NOU	1
LAB	1
BRA	1
WAN	1
EGR	1
RTY	1
PUR	1
DAR	1
ALK	1
GOV	1
ETS	1
LLS	1
SEV	1
BEG	1
ARN	1
ASO	1
ESU	1
#GL	1
UAR	1
WIS	1
MAS	1
LIZ	1
UDI	1
GAR	1
PUL	1
DAN	1
VIT	1
DEF	1
NEA	1
PAC	1
BAL	1
OCE	1
VAR	1
BUS	1
CS#	1
IEV	1
ILA	1
NIO	1
NAR	1
OOM	1
SUL	1
BOD	1
SIV	1
DN#	1
TAG	1
OBL	1
NAM	1
DLE	1
ECH	1
TIF	1
ORR	1
UEN	1
DAT	1
UN#	1
#AV	1
CIS	1
VIO	1
PHI	1
TOP	1
NEC	1
#JE	1
FIG	1
KET	1
EAV	1
VAN	1
UIL	1
SCI	1
KNE	1
AFF	1
DLY	1
LDE	1
RDI	1
SPA	1
ESC	1
INN	1
AKI	1
IGI	1
FIL	1
NGT	1
LUS	1
ZE#	1
ENA	1
ERG	1
BES	1
CCO	1
#OC	1
LUM	1
ALM	1
FEL	1
LIM	1
CUS	1
IBE	1
NIG	1
NDO	1
NCR	1
VIL	1
LEV	1
ELT	1
CIP	1
NCO	1
EPE	1
SCA	1
HON	1
ICS	1
CHU	1
#EI	1
RNA	1
EYE	1
PLO	1
CIN	1
UIR	1
DRA	1
FAM	1
OTT	1
OWI	1
LOT	1
NAN	1
BOA	1
RUN	1
YES	1
HUS	1
ODY	1
BJE	1
ATC	1
GLE	1
BED	1
URR	1
FEW	1
TOL	1
ALU	1
HOP	1
SAT	1
SLY	1
NFO	1
NIZ	1
SSO	1
DOM	1
OON	1
LAW	1
GUE	1
SYS	1
IRI	1
MOD	1
OWS	1
BIT	1
RAB	1
IZA	1
PRA	1
FUN	1
IVA	1
PHO	1
EES	1
RSI	1
ERO	1
USS	1
RMS	1
VAT	1
NNO	1
GGE	1
DDE	1
WES	1
FLO	1
#LU	1
OWA	1
POW	1
ELP	1
CEL	1
IEL	1
ADV	1
GNI	1
RIL	1
ACI	1
HOT	1
NEY	1
BRE	1
ABI	1
COS	1
FLE	1
YTH	1
PME	1
LUD	1
RGA	1
NGI	1
#SK	1
IFT	1
ALA	1
PIR	1
MMI	1
UCE	1
EAM	1
TAC	1
DOE	1
SUA	1
GOT	1
EPO	1
OOT	1
DUA	1
COV	1
AGO	1
MPT	1
#EY	1
CCU	1
#EQ	1
SWE	1
IOR	1
KES	1
PLY	1
LDI	1
EER	1
WEA	1
HUM	1
#D#	1
BLA	1
GLA	1
RAS	1
HIR	1
ALF	1
USL	1
RRO	1
OCC	1
OHN	1
CUT	1
AYE	1
WEV	1
ADY	1
BUI	1
RIP	1
SKE	1
ONV	1
NON	1
TA#	1
THU	1
PET	1
LOU	1
APA	1
HOD	1
NTU	1
ECU	1
HIE	1
RNM	1
AUG	1
LTH	1
UFF	1
EFU	1
IBI	1
MPR	1
ASU	1
#EC	1
GN#	1
OFT	1
NIF	1
ZAT	1
RAR	1
GIO	1
BLO	1
IEF	1
AIT	1
MRS	1
EK#	1
ERL	1
EXI	1
NA#	1
HET	1
UCK	1
USH	1
ENN	1
YED	1
DUS	1
NET	1
ECR	1
BIN	1
MUL	1
IG#	1
UPO	1
COO	1
IRT	1
NCT	1
XCE	1
HUN	1
RA#	1
OUB	1
PHY	1
JOH	1
#TY	1
RPO	1
TYP	1
URY	1
OY#	1
OAT	1
EGE	1
RTU	1
TIR	1
CHR	1
RRY	1
LOV	1
HRI	1
LUT	1
FUR	1
SKI	1
PAL	1
FEA	1
EFT	1
ADM	1
EIT	1
NTY	1
URP	1
BOO	1
IMM	1
GIC	1
XAM	1
LEF	1
ACR	1
EOR	1
TUT	1
FOO	1
AVA	1
CEI	1
IRL	1
KEE	1
POT	1
UGG	1
LIO	1
LTE	1
OGI	1
OAR	1
IEW	1
XT#	1
LMO	1
SIA	1
ETY	1
PHE	1
NGR	1
DMI	1
AMA	1
PIE	1
HTE	1
#M#	1
NEL	1
DRO	1
stdout 
Shredded Message Solver (ai-class)

shredded message:
de|  | f|Cl|nf|ed|au| i|ti|  |ma|ha|or|nn|ou| S|on|nd|on
ry|  |is|th|is| b|eo|as|  |  |f |wh| o|ic| t|, |  |he|h 
ab|  |la|pr|od|ge|ob| m|an|  |s |is|el|ti|ng|il|d |ua|c 
he|  |ea|of|ho| m| t|et|ha|  | t|od|ds|e |ki| c|t |ng|br
wo|m,|to|yo|hi|ve|u | t|ob|  |pr|d |s |us| s|ul|le|ol|e 
 t|ca| t|wi| M|d |th|"A|ma|l |he| p|at|ap|it|he|ti|le|er
ry|d |un|Th|" |io|eo|n,|is|  |bl|f |pu|Co|ic| o|he|at|mm
hi|  |  |in|  |  | t|  |  |  |  |ye|  |ar|  |s |  |  |. 

Top 3 results...
score: -1619.5501131298224

Claude Shannon founded information    
theory, which is the basis of         
probabilistic language models and     
of the code breaking methods that     
you would use to solve this problem,  
with the paper titled "A Mathematical 
Theory of Communication," published   
in this year.                         

score: -1631.76535223795

nnon founded informationClaude Sha    
ich is the basis of     theory, wh    
tic language models and probabilis    
e breaking methods that of the cod    
use to solve this probleyou would   m,
aper titled "A Mathematiwith the pl ca
Communication," publisheTheory of   d 
ar.                     in this ye    

score: -1632.7894584577352

nded informationClaude Shannon fou    
he basis of     theory, which is t    
uage models and probabilistic lang    
ng methods that of the code breaki    
olve this probleyou would use to s  m,
led "A Mathematiwith the paper titl ca
ation," publisheTheory of Communic  d 
                in this year.
https://ideone.com/XJVvf
language:
Haskell (ghc 8.4.4)
created:
12 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!