#Mathematica - 238 236 225
Mathematica - 238 236 225
c:="@"~CharacterRange~"Z"~RandomChoice~28/."@"->" "
For[s=""<>c;i=0,{d,s}=Sort[{#~HammingDistance~"METHINKS IT IS LIKE A WEASEL",#}&@
StringReplace[s,_/;20Random[]<1:>c〚1〛]&~Array~100]〚1〛;
d>0Print[i++,":"s," -- score: ",28-d],]
Example output
0: CYPMEIHADXRXVTFHERYOZNRVFCSQ -- score: 0
1: CYPMEIHADIRXVTFBERYOZNRVFCSQ -- score: 1
2: CYPMEIHA IRXVTFBIRYOZNRVFCSQ -- score: 3
...
50: METHINKS IT IS LIKE A WEASEL -- score: 28