#!/usr/bin/perl

use strict;
use warnings;

my @alphabets = "A" .. "Z";
my @strings   = ();
my $goal      = "METHINKSITISAWEASEL";

sub random_int($) { int rand shift }

sub similarity($) {
    my $str   = shift;
    my $score = 0;

    for ( 0 .. length($str) - 1 ) {
        $score++ if substr( $str, $_, 1 ) eq substr( $goal, $_, 1 );
    }
    return $score;
}

sub derive_string($) {
    my $origin_string   = shift;
    my @derived_strings = ();
    for ( 1 .. 10 ) {
        my $derived_string = $origin_string;
        substr( $derived_string, random_int length $origin_string, 1 ) =
          $alphabets[ random_int @alphabets ];
        push @derived_strings, $derived_string;
    }

    return @derived_strings;
}

for ( 1 .. 300 ) {
    my $string = "";
    $string .= $alphabets[ random_int @alphabets ] for 1 .. length $goal;
    push @strings, $string;
}

my $count = 0;
until ( $strings[0] eq $goal ) {
    my @next_gen = ();
    print $count++, ": ", $strings[0], "\n";
    push @next_gen, derive_string $_ for @strings;
    @strings =
      ( map { $_->[1] }
          sort { $b->[0] <=> $a->[0] } map { [ similarity $_, $_ ] } @next_gen )
      [ 0 .. 299 ];
}

print $count, ": ", $strings[0], "\n";