66
\$\begingroup\$

Richard Dawkins in his book The Blind Watchmaker, describes a Weasel program. The algorithm can be described as follows:

  1. Start with a random string of 28 characters. Valid characters are all upppercase letters, and space.

  2. Make 100 copies of that string, with a 5% chance per character of that character being replaced with a random character.

  3. Compare each new string with the target "METHINKS IT IS LIKE A WEASEL", and give each a score according to the number of letters in the string which are correct and in the correct position.

  4. If any of the new strings has a perfect score (28), halt.

  5. Choose the highest-scoring string from step 3. How you work out a tie is up to you, but only one string may be chosen. Take the chosen string and go to step 2.

The winner will be the shortest code snippet to get to the correct answer while printing the highest-scoring string of each generation in the following format:

answers in this format please

If people could help by checking other peoples answers would be very helpful!

\$\endgroup\$
  • 4
    \$\begingroup\$ Which characters are allowed? Unicode? Lowercase? \$\endgroup\$ – Oriol Jan 3 '14 at 17:42
  • 4
    \$\begingroup\$ Ah, I love Dawkins. Beauty, and feasibility of evolution shown in a simple algorithm. \$\endgroup\$ – Cruncher Jan 3 '14 at 18:16
  • \$\begingroup\$ May step 4 be better replaced with "step 1.5) If the new strings has a perfect score (28), halt" and "step 4) Take the highest scoring string, and go to step 1.5."? That is, if the initial random string is a winner, need we fan out? \$\endgroup\$ – Rob Starling Jan 3 '14 at 18:21
  • 1
    \$\begingroup\$ I'm a bit confused as to the order of operations here. Is the intent that we make 100 new strings, based on the original string? Or is it 100 new strings, with the first string being based on the original, and each subsequent string based on the previous string? The algorithm description seems to imply the former, while the sample output appears to be of the latter. \$\endgroup\$ – Iszi Jan 6 '14 at 19:18
  • 2
    \$\begingroup\$ The instructions are pretty clear, but what if the original string is the target? \$\endgroup\$ – Christian Palmstierna Jan 8 '14 at 15:41

41 Answers 41

0
\$\begingroup\$

GolfScript 207

{91,{64>},32+''+27rand=}:g;'METHINKS IT IS LIKE A WEASEL':s;{`{\.@\=s@==}+s,,\%{+}*}:c;0:k;{k):k\.': '@@c' -- score: '\++++n+}:f;[{g}]28*{~}%{s=!}{{`100,\{\;{100rand 5>{ }{;g}if}%''+}+}~%{c}$)\;{ }%}/{f}/s f

Below is a slightly unpacked version of the above GolfScript with explanation. Since I don't think it could beat the APL or some other answers, I didn't bother to truly minify it. I think that with inlining variable declarations, eliminating unnecessary variables, and other such tricks, this code could achieve approximately 190 characters without really changing the algorithm. I think about about 10-15 characters could be removed if I better sorted out the conversion between arrays of ASCII values and strings.

#g is a function that returns the ASCII value of a random character or space. 
#The ASCII values for capital letters are 65-90, and 32 is space.
{91,{64>},32+''+27rand=}:g; 

#s is the string of interest.
'METHINKS IT IS LIKE A WEASEL':s;

#c is a function that returns the 'score' of a given string
#(the number of correct characters in the correct place).
{`{\.@\=s@==}+s,,\%{+}*}:c;

#t is a function that transforms a given string according to 
#the specification (by replacing characters with a random character 5% of the times).
{{100rand 5>{ }{;g}if}%''+}:t;

#i is the initial random string.
[{g}]28*{~}%:i;

#Use '/' to unfold the initial value until the string is equal to the string of interest.
#Every loop, do the transformation 100 times, then sort by score c, and then take the top scoring string.
#Aggregate the results into an array a.
i{s=!}{{`100,\{\;t}+}~%{c}$)\;{ }%}/:a;

#Instantiate a counter variable k
0:k;

#f is the formatting function, that takes a string and formats it according to the spec.
{k):k\.': '@@c' -- score: '\++++n+}:f;

#Format every string in the array, and then format the string of interest
a{f}/
s f
\$\endgroup\$
0
\$\begingroup\$

Golfscript (168 167)

:x;0['METHINKS IT IS LIKE A WEASEL'{}/]:o{;{27rand.!96*+64^}:r~}%{o=!}{100,{;.{20rand{}{;r}if}%}%{{[o\]zip{~=},,}:s~}$)@;\;x 2$+': '+1$+' -- score: '+1$s+n+:x;\)\}/;;x

Sadly, I can't seem to compress it quite to APL's level, but it's afaict currently a shared second place.

This is what it does;

# Grab the empty parameter string as initially empty output string.
:x;
# Start count at row #0
0
# Store the target string as an array in 'o'
['METHINKS IT IS LIKE A WEASEL'{}/]:o
# Create a random starting string, and define 'r' as a function generating a random char.
{;{27rand.!96*+64^}:r~}%
# Unfold as long as the latest string is different from the target string.
{o=!}
{
  // Generate 100 strings, sort by score and keep the highest.
  100,{;.{20rand{}{;r}if}%}%{{[o\]zip{~=},,}:s~}$)@;\;
  // Append the row to the output string, and increase the row number    
  x 2$+': '+1$+' -- score: '+1$s+n+:x;\)\
}/
// Clean some junk on the stack
;; 
// Output string
x
\$\endgroup\$
0
\$\begingroup\$

R, 291 characters

Longer than the previously proposed R answer but significantly different to be (I think) of interest:

a=sample;b=a(c<-c(LETTERS,' '),28,T);d=0;h=function(x)sum(x==strsplit("METHINKS IT IS LIKE A WEASEL",'')[[1]]);while(h(b)!=28){if(d){f=replicate(100,{e=runif(28)>.05;S=a(c,28,T);S[e]=b[e];S});g=f[,which.max(apply(f,2,h))];if(h(g)>h(b))b=g};cat(d,': ',b,' -- score: ',h(b),'\n',sep='');d=d+1}

With indentations:

a=sample
b=a(c<-c(LETTERS,' '),28,T)
d=0
h=function(x)sum(x==strsplit("METHINKS IT IS LIKE A WEASEL",'')[[1]])
while(h(b)!=28){
    if(d){
        f=replicate(100,{e=runif(28)>.05;S=a(c,28,T);S[e]=b[e];S})
        g=f[,which.max(apply(f,2,h))]
        if(h(g)>h(b))b=g
        }
    cat(d,': ',b,' -- score: ',h(b),'\n',sep='')
    d=d+1
    }

Outputs:

0: OUZ IT HNGNMSKIHSMCQUGXTOYVZ -- score: 1
1: OUZ IT HNGNMSKYHSMCQUGWXOYVZ -- score: 2
2: OUZ IT HNGNMSKYLSMCQUGWXOYVZ -- score: 3
3: OUZ IT HNGNMSKYLSMC UGWXOYVZ -- score: 4
...
68: METHINKS IT ES LIKE A WEASEL -- score: 27
69: METHINKS IT ES LIKE A WEASEL -- score: 27
70: METHINKS IT IS LIKE A WEASEL -- score: 28

The key here is the line f=replicate(100,{e=runif(28)>.05;S=a(c,28,T);S[e]=b[e];S}):
e=runif(28)>.05 draws randomly 28 numbers between 0 and 1 on a uniform distribution, and gives TRUE if over 5% and FALSE if under 5%. S=a(c,28,T) draws 28 new letters/spaces, while S[e]=b[e] replaces those for which the value was over 5% by the corresponding letter from the previous generation (i .e. those for which the value was less than 5% are therefore new).Then we replicate the operation 100 times. On the following line (g=f[,which.max(apply(f,2,h))]) we compute the score for each of the 100 replicates and keep the one that has the maximum score (in case of equality the first one is kept) to be compared with the previous generation.

\$\endgroup\$
0
\$\begingroup\$

C 331

Another C solution that comes out to 331 characters. I think I might be able to improve it if I look a bit closer. Anyway the solution follows:

char l[29],b[29],*a="ABCDEFGHIJKLMNOPQRSTUVWXYZ ",i,j,*t="METHINKS IT IS LIKE A WEASEL",s,m=0;main(){for(i=0;i<28;i++)l[i]=a[rand()%27];while(strcpy(l,b))for(i=0;i<100;i++){for(j=s=0;j<28;j++){if(rand()%20==0)l[j]=a[rand()%27];if(l[j]==t[j])s++;}printf("%s -- score: %d\n",l,s);if(s>m){m=s;strcpy(b,l);}if(!strcmp(b,t))goto e;}e:;}
\$\endgroup\$
0
\$\begingroup\$

Groovy: 314

def(r,o,g)=[new Random(),{(0..27).sum{x->"METHINKS IT IS LIKE A WEASEL"[x]==it[x]?1:0}},0]
def q={([' ']+('A'..'Z'))[r.nextInt(27)]}
def s=q()*28
for(;;){println"${g++}: $s -- score: ${o(s)}"
if(o(s)==28)break
s=([s]*100).collect{it.collect{5>r.nextInt(100)?q():it}.sum()}.groupBy{o(it)}.max{it.key}.value[0]}

Output:

0:                              -- score: 5
1:          B               S   -- score: 6
2:  E       B               S M -- score: 7
3:  E       B               S M -- score: 7
4:  E       BT      X       S M -- score: 8
...
68: METHINKS IT IS LIKE L WEASEL -- score: 27
69: METHINKS IT IS LIKE L WEASEL -- score: 27
70: METHINKS IT IS LIKE L WEASEL -- score: 27
71: METHINKS IT IS LIKE L WEASEL -- score: 27
72: METHINKS IT IS LIKE A WEASEL -- score: 28

I feel like this is cheating so I'm not counting it as my 'real' answer; but I can save a few chars by passing "METHINKS IT IS LIKE A WEASEL" and " -- score: " as arguments to my script. Although technically it is 'externalizing strings'... which everyone knows is good practice :).

Groovy: 290

def(r,o,g)=[new Random(),{(0..27).sum{x->args[0][x]==it[x]?1:0}},0]
def q={([' ']+('A'..'Z'))[r.nextInt(27)]}
def s=q()*28
for(;;){println"${g++}: $s${args[1]}${o(s)}"
if(o(s)==28)break
s=([s]*100).collect{it.collect{5>r.nextInt(100)?q():it}.sum()}.groupBy{o(it)}.max{it.key}.value[0]}

Run like groovy script.groovy "METHINKS IT IS LIKE A WEASEL" " -- score: "

\$\endgroup\$
0
\$\begingroup\$

Haskell - 420 characters

This is more verbose than most; I'd put that down to my inexperience with randomness in haskell and proper use of monads.

import System.Random
r=randomRIO
z=zipWith
c=fmap((' ':['A'..'Z'])!!)$r(0,26)
y=(i.).replicate
i=mapM id
s=sum.z((fromEnum.).(==))"METHINKS IT IS LIKE A WEASEL"
u a n|n==0=c|True=return a
b n a|s n>s a=n|True=a
g=fmap(foldr1 b).y 100.mapM((r(0,20)>>=).u)
e x=do n<-g$x!!0;if(s$x!!0)==28 then return(n:x)else e(n:x)
main=y 28 c>>=(\a->e[a])>>=(i.z(\n x->putStrLn$shows n$": "++x++" -- score: "++(show$s x))[0..]).reverse
\$\endgroup\$
0
\$\begingroup\$

Javascript (411 389 376)

Shorter than some, longer than most.. [Methinks it will end.] EDIT: it wasn't ending due to an error. fixed it and ended up dropping the count too -- cool.

t='METHINKS IT IS LIKE A WEASEL';z=0;m=Math.random;r=function(){n=Math.floor(m()*27);return n?String.fromCharCode(64+n):' '};for(s='';s.length<28;s+=r());while(z<28){a=[s];while(a.length<100){x='';while(x.length<28){x+=m()>=.95?r():s.substr(x.length,1)}a.push(x)}for(i=0;i<100;i++){b=0;for(j=0;j<28;j++){b+=a[i][j]==t[j]?1:0;}if(b>z){alert(a[i]+' -- score: '+b);z=b;s=a[i]}}};

expanded:

t = 'METHINKS IT IS LIKE A WEASEL';
z = 0;
m = Math.random;
r = function(){
    n = Math.floor(m()*27);
    return n ? String.fromCharCode(64+n) : ' '
};
for(s='';s.length<28;s+=r());
while( z < 28 ){
    a = [s];
    while( a.length < 100 ){
        x = '';
        while( x.length < 28 ){
            x += m() >= .95 ? r() : s.substr(x.length, 1)
        }
        a.push(x)
    }
    for( i = 0; i < 100; i++ ){
        b = 0;
        for( j = 0; j < 28; j++ ){
            b += a[i][j] == t[j] ? 1 : 0;
        }
        if( b > z ){
            console.log( a[i] + ' -- score: ' + b);
            z = b;
            s = a[i]
        }
    }
};


[original:]

t='METHINKS IT IS LIKE A WEASEL';s='';z=0;m=Math.random;r=function(){n=Math.floor(m()*27);return n?String.fromCharCode(64+n):' '};c=function(){a=[s];while(a.length<100){x='';while(x.length<28){x+=m()>=.95?r():s.substr(x.length?x.length-1:0,1)}a.push(x)}for(i=0;i<100;i++){b=0;for(j=0;j<28;j++){b+=a[i][j]==t[j]?1:0;}if(b>z){alert(a[i]+' -- score: '+b);z=b;s=a[i]}i++}};while(s.length<28){s+=r()}while(z<28){c()}
\$\endgroup\$
0
\$\begingroup\$

Racket: 426 422 bytes

(let*((r random)(m map)(L" ABCDEFGHIJKLMONPQRSTUVWXYZ")(P(string->list"METHINKS IT IS LIKE A WEASEL"))(c(λ(l p)(m(λ(x)(if(<(r)p)(string-ref L(r 27))x))l)))(s(λ(l P p)(cons(foldl(λ(x y a)(if(eqv? x y)(+ a 1)a))0 l P)l))))(let r((g 0)(o (c P 1)))(let*((o(sort(m(λ(x)(s(c o 0.05)P 0))(range 100))(λ g(apply >(m car g)))))(p(caar o))(c(cdar o)))(printf"~a: ~a -- score: ~a
"g(list->string c)p)(if(= p 28)p(r(+ g 1)c)))))

Ungolfed:

(let* ((r random)
       (m map)
       (L " ABCDEFGHIJKLMONPQRSTUVWXYZ")
       (P (string->list "METHINKS IT IS LIKE A WEASEL"))
       (c (λ (l p) 
            (m (λ (x)
                 (if (< (r) p)
                     (string-ref L (r 27))
                     x))
               l)))
       (s (λ (l P p)
            (cons (foldl (λ (x y a)
                           (if (eqv? x y)
                               (+ a 1)
                               a))
                         0 
                         l 
                         P)
                  l))))
  (let r ((g 0) (o (c P 1)))
    (let* ((o (sort (m (λ (x)
                         (s(c o 0.05)P 0))
                       (range 100))
                    (λ g
                      (apply >(m car g)))))
           (p (caar o))
           (c (cdar o)))
      (printf"~a: ~a -- score: ~a\n" g (list->string c) p)
      (if (= p 28)
          p
          (r (+ g 1) c)))))
\$\endgroup\$
0
\$\begingroup\$

C++ 668

Not really short, but the only one in c++. (:

#include "stdafx.h"
using namespace std;int _tmain(){srand(time(NULL));string z="METHINKS IT IS LIKE A WEASEL";string a(28,' ');for(int i=0;i<28;++i){a[i]='A'+(rand()%26);}while(1){vector<std::pair<int,string>>d;for(int i=0;i<100;++i){d.push_back(std::pair<int,string>(0,""));for(int j=0;j<28;++j){int b=rand()%100;if(b<6){if(b<2){d[i].second+=' ';}else{d[i].second+='A'+(rand()%26);}}else {d[i].second+=a[j];}}}for(int i=0;i<100;++i){for(int j=0;j<28;++j){if(d[i].second[j]==z[j]){d[i].first++;}}}int y=0;for(int i=0;i<100;++i){if(d[i].first==28){cout<<d[i].second<<" "<<d[i].first;exit(1);}else if(d[i].first>y){y=d[i].first;a=d[i].second;}}cout<<a<<" "<<y<<endl;}}

more readable version:

#include "stdafx.h"
#include <string>
#include <stdlib.h>
#include <vector>
#include <iostream>
#include <time.h>
using namespace std;


int _tmain()
{
  srand(time(NULL));
  string z = "METHINKS IT IS LIKE A WEASEL";
  string a(28, ' ');
  for (int i = 0; i < 28; ++i)
  {
    a[i] = 'A' + (rand() % 26);
  }
  while(1)
  {
    vector<std::pair<int, string >> d;
    for (int i = 0; i < 100; ++i)
    {
      d.push_back(std::pair<int, string>(0, ""));
      for (int j = 0; j < 28; ++j)
      {
        int b = rand() % 100;
        if (b < 6)
        {
          if (b < 2)
          {
            d[i].second += ' ';
          }
          else {
            d[i].second += 'A' + (rand() % 26);
          }
        }
        else {
          d[i].second += a[j];
        }
      }
    }
    for (int i = 0; i < 100; ++i)
    {
      for (int j = 0; j < 28; ++j)
      {
        if (d[i].second[j] == z[j])
        {
          d[i].first++;
        }
      }
    }
    int y = 0;
    for (int i = 0; i < 100; ++i)
    {
      if (d[i].first == 28)
      {
        cout << d[i].second << " " << d[i].first;
        exit(1);
      }
      else if (d[i].first > y)
      {
        y = d[i].first;
        a = d[i].second;
      }
    }
    cout << a << " " << y << endl;
  }
}

Output:

VEBVTEWX CEWMYLTAJTYPFYYXBDQ 2
 EBVTEWX CEWMYLTAJT PFYYXBDQ 3
 EBVTEKX CEWMYLTAJT PFYYXBDQ 4
 EBVTEKX CEWM  TAJT PFYYXBDQ 5
 EBVTEKX CE M  TAJT P YYX DQ 7
MEPVTEKX CE M  TAJT P YY  D  8
MEPVT KX CE M  TAJT A YY  D  9
MEPVI KX CE M  UAJT A YY  D  10
MEPSI KX CE M  UAJT A YY  D  10
MEPSI K  CE M  UAJE A YY  DE 11
MEPSI K  CE M  UAJE A YY  DL 12
MEPPI K  CE I  UDJE A YY  DL 13
MEPRI K  CE IS UDJE A YY  DL 14
MEPRI K  CE IS UDJE A  Y  DL 14
MEPHI K  CE IS UDJE A  Y  DL 15
MEPHI K  CE IS UDJE A  Y  DL 15
MEPHI K  CE IS RDBE A  E  DL 16
MEPHIQK  CE IS RD E A  E  DL 16
MEPHIQK  CE IS RD E A  E  DL 16
ME HIQK  CE IS RDXE A  E  DL 16
ME HIQK  CE IS W XE A  E  DL 16
ME HIQK  CE IS W XE A  E  EL 17
ME HIQK  CE IS W XE A  E  EL 17
ME HIQK  CE IS   XE A  E  EL 17
MEGHIQK  CE IS   XE A WEO EL 18
MEGHIQK  CE IS   XE A WEO EL 18
MEGHIQK  CE IS   XE A WEO EL 18
MEGHIQK  CE IS   XE A WE  EL 18
MEGHIQK  CE IS   XE A WE SEL 19
MEGHIQK  CE IS L XE A WE SEL 20
MEGHINK  CE IS L XE A WE SEL 21
MEGHINK  CE IS L XE A WE SEL 21
MEGHINK  CN IS L XE A WEASEL 22
MEGHINK   H IS L XE A WEASEL 22
MEGHINK   H IS L XE A WEASEL 22
METHINK   H IS L XE A WEASEL 23
METHINK   H IS L XE A WEASEL 23
METHINK   H IS L XE A WEASEL 23
METHINK   H IS L XE A WEASEL 23
METHINK   H IS L XE A WEASEL 23
METHINK   H IS L XE A WEASEL 23
METHINK  ZH IS L XE A WEASEL 23
METHINK  ZH IS LIXE A WEASEL 24
METHINK  ZH IS LIKE A WEASEL 25
METHINKD ZH IS LIKE A WEASEL 25
METHINKD ZH IS LIKE A WEASEL 25
METHINKD ZH IS LIKE A WEASEL 25
METHINKD ZH IS LIKE A WEASEL 25
METHINKD ZT IS LIKE A WEASEL 26
METHINKD ZT IS LIKE A WEASEL 26
METHINKD ZT IS LIKE A WEASEL 26
METHINKS ZT IS LIKE A WEASEL 27
METHINKS IT IS LIKE A WEASEL 28
\$\endgroup\$
0
\$\begingroup\$

JavaScript (Node.js), 328 bytes

t="METHINKS IT IS LIKE A WEASEL";z=0;m=Math.random;r=_=>(n=0|27*m())?String.fromCharCode(64+n):" ";for(s="";28>s[l="length"];s+=r())for(;28>z;){for(a=[s];100>a[l];){for(x="";28>x[l];)x+=.95<=m()?r():s.substr(x[l],1);a.push(x)}for(i=0;100>i;i++){for(j=b=0;28>j;j++)b+=a[i][j]==t[j];b>z&&(alert(a[i]+" -- score: "+b),z=b,s=a[i])}}

Try it online!

This is rather long and can be shortened, just haven't gotten around to that.


Explanation :

This is not exactly an explanation but it is better indented and can

t = "METHINKS IT IS LIKE A WEASEL";
z = 0;
m = Math.random;
r = _ => (n = 0 | 27 * m()) ? String.fromCharCode(64 + n) : " ";
for (s = ""; 28 > s[l = "length"]; s += r())
	for (; 28 > z;) {
		for (a = [s]; 100 > a[l];) {
			for (x = ""; 28 > x[l];) x += .95 <= m() ? r() : s.substr(x[l], 1);
			a.push(x)
		}
		for (i = 0; 100 > i; i++) {
			for (j = b = 0; 28 > j; j++) b += a[i][j] == t[j];
			b > z && (alert(a[i] + " -- score: " + b), z = b, s = a[i])
		}
	}

\$\endgroup\$
0
\$\begingroup\$

Pyth, 116 bytes

Ls.bqNY"METHINKS IT IS LIKE A WEASEL"bj.e%"%d: %s -- score: %s"[ksbyb).W<yeH28+Z]eoyNmmO.[O+r1G\ k20eZ100]mO+r1G\ 28

Try it online.

Ls.bqNY"..."bj.e%"..."[ksbyb).W<yeH28+Z]eoyNmmO.[O+r1G\ k20eZ100]mO+r1G\ 28   

L                                                                             Define fitness function, y(b):
       "..."                                                                    The target string
  .b        b                                                                   Map over characters of the above and b:
    qNY                                                                           Are they equal? True = 1, False = 0
 s                                                                              Take the sum
                                                                    r1G       The uppercase alphabet
                                                                   +   \      Append a space
                                                                  O           Choose one at random
                                                                ]m       28   Create an array of 28 of the above, wrap in array
                             .W                                               Functional while, with above as initial value
                                                                                Continue condition (current value = H):
                                 eH                                               Last value of H
                                y                                                 Apply fitness function to the above
                               <   28                                             Check the above is less than 28
                                                                                Function body (current value = Z)
                                             m             eZ                     Map each character (as k) in the last value in Z over:
                                                 O+r1G\                             Choose random char/space (as above)
                                               .[       k20                         Pad the above to length 20 using k
                                              O                                     Choose one of the above at random
                                            m                100                  Do the above 100 times
                                         oyN                                      Order the above by the fitness function
                                       ]e                                         Take the last of the above, wrap in array
                                     +Z                                           Append to Z
                                                                              Return value of while is array of all steps taken
              .e                                                              Map each entry with its index over:
                       k                                                        Current index
                        sb                                                      Current entry joined on empty string
                          yb                                                    Fitness of current entry
                      [     )                                                   Wrap the above 3 results in an array
                %"..."                                                          String formatting using the output string
             j                                                                Join on newlines, implicit output
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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