Code Challenge - Paint Cans!!!

gistfile1.rb

require 'benchmark'

CANS = [1, 2, 4, 10, 15]
PRICES = {1 => 4, 2 => 5, 4 => 6, 10 => 11, 15 => 15}

RANDOM = Random.new

class Mutation
  attr_accessor :cans

  def self.first_valid_combination(qty)
    mut = Mutation.new(qty)
    while mut.qty < qty
      mut.cans << 15
    end

    mut
  end

  def initialize(target)
    @cans = []
    @target = target
  end

  def give_birth
    child = Mutation.new @target
    child.cans = @cans.dup
    child.mutate
    child
  end

  def mutate
    case RANDOM.rand(0..3)
      when 1
        to_add = RANDOM.rand(0..CANS.length - 1)
        @cans << CANS[to_add]
      when 2
        to_remove = RANDOM.rand([email protected])
        @cans.delete_at(to_remove)
      when 3
        to_change = RANDOM.rand([email protected])
        to_add = RANDOM.rand(0..CANS.length - 1)

        @cans[to_change] = CANS[to_add]
    end
  end

  MAX_FITNESS = 100000000000

  def fitness
    qty >= @target ? cost : MAX_FITNESS
  end

  def cost
    @cans.collect { |can| PRICES[can] }.reduce(0, :+)
  end

  def qty
    @cans.reduce(0, :+)
  end
end

def find_fittest_in_batch(parent, size, depth)
  return parent if depth == 0
  depth -= 1

  fittest = parent
  (0..size).each do
    child = fittest.give_birth
    best_child = find_fittest_in_batch(child, size, depth)
    if best_child.fitness < fittest.fitness
      fittest = best_child
    end

    if child.fitness < fittest.fitness
      fittest = child
    end
  end

  fittest
end

def calculate_cans(qty)

  parent = Mutation.first_valid_combination(qty)

  fittest = find_fittest_in_batch(parent, 15, 3)

  puts "Aimed to get #{qty} and got #{fittest.qty}"
  puts fittest.fitness.to_s

end

def run(qty)
  Benchmark.measure {calculate_cans(qty)}
end