hello-algo.rb

#!/usr/bin/ruby

# This is a port of my previous hello-algo program,
# which was written in Common Lisp
#
# Written by Fredrik A. Madsen-Malmo

# init all global variables
# doesn't look as good if you include \t and \n in CHARS

# first command argument without newlines and tabs
TARGET = ARGV[0] ? ARGV[0].gsub(/[\t\n]/, " ") : "Hello, World!"
POP_SIZE = ARGV[1] ? ARGV[1].to_i : 100

# alphanumeric chars and a space
CHARS = (0..9).to_a + ('A'..'z').to_a + ('!'..'?').to_a << " "

$population = Array.new

# get a random string that is x length
def random_string (length)
  (0...length).map{ |x| ::CHARS.sample }.join
end

# calculate the score of str1 based on the inequality from str2
def hamming_distance (str)
  # exit if the length of the strings isn't the same
  return nil if str.length != TARGET.length

  return str.split('').each_with_index.map do |x, i|
    x == TARGET[i]
  end.select { |x| x == false }.length
end

# replace chars in a string with random chars. p = 1/str.length
def mutate (str)
  str.split('').map do |x|
    rand(str.length ** 0.9) == 0 ? random_string(1) : x
  end.join
end

# get the n best entries from pop based on lowest fitness
def best_population (n)
  # sort on second position in the $population array (hamming_distance)
  $population.sort_by { |p| p[1] }[0...n]
end

# concat strings
def crossover (str1, str2)
  break_point = (str1.length*0.25).round
  return [str1[0...break_point] + str2[break_point..-1],
          str2[0...break_point] + str1[break_point..-1]]
end

# add random entry to $population until it reaches the specified p size
def start
  loop do
    # stop when specified population size is met
    break if $population.size == POP_SIZE

    _new = random_string TARGET.length

    # append the random string and its hamming_distance to the $population array
    $population << [_new, hamming_distance(_new)]
  end

  evolve
end

def gen_new_pop
  new_pop = Array.new

  # fill the new array with crossover from the best two entries in population
  new_pop.concat(crossover(*best_population(2).map do |x|
                         x.first
                       end)) until new_pop.size == POP_SIZE

  # mutate each entry in new_pop
  new_pop.map! { |x| mutate x }
  
  # set $population to the new_pop entries along with their hamming_distance
  $population = new_pop.map { |x| [x, hamming_distance(x)] }
end

def evolve
  gens = 0
  loop do
    # clear on *nix or windows
    system 'clear' or system 'cls'
    best = best_population(1)[0]

    percent = ((TARGET.length - best[1])/TARGET.length.to_f*100).to_i

    # print progressbar, which gen we're on and the currently best string
    puts "#{"\e[42m \e[0m" * (percent)}#{"\e[41m \e[0m" * (100-percent)} \
\e[1m#{percent}%\e[22m\n\n"
    puts "\e[7mGeneration \e[1m#{gens}\e[22m\e[27m\n\n"
    puts best[0]

    # break if there are no errors
    break if best[1] == 0
    gen_new_pop

    gens += 1
  end

  puts "Finished!"
end

# start the program
start