Skip to content

Instantly share code, notes, and snippets.

@Genki-S
Last active August 29, 2015 14:08
Show Gist options
  • Save Genki-S/a474487ef4fd49818111 to your computer and use it in GitHub Desktop.
Save Genki-S/a474487ef4fd49818111 to your computer and use it in GitHub Desktop.
coderunner 2014 qualification A
require 'open-uri'
TOKEN = "CDC4L3EA1BEVS662EP0MALI7UVC8L357"
class GA
GENES_LIMIT = 100
SELECTION_COUNT = 50
CROSSOVER_COUNT = 45
RANDOM_COUNT = 5
MUTATION_PERCENTAGE = 30
GENETICS = ['A', 'B', 'C', 'D']
GENE_LENGTH = 50
class TooFrequentAccessError < RuntimeError; end
class InvalidTokenError < RuntimeError; end
class InvalidStringError < RuntimeError; end
class CrossoverError < RuntimeError; end
def self.fitness(gene)
url = "https://game.coderunner.jp/q?str=#{gene}&token=#{TOKEN}"
begin
p url
response = open(url)
# raise TooFrequentAccessError if response == 'Too Frequent Access'
# raise InvalidTokenError if response == 'Invalid Token'
# raise InvalidStringError if response == 'Invalid String'
# rescue InvalidTokenError => e
rescue OpenURI::HTTPError => e
if e.io.string == 'Too Frequent Access'
puts 'Waiting 1s due to TooFrequentAccessError...'
sleep 1
retry
else
raise RuntimeError
end
end
fitness = response.string.to_i
sleep 1
fitness
end
def initialize
@genes = []
@genes = random_genes(GENES_LIMIT)
end
def start
puts "GENES_LIMIT: #{GENES_LIMIT}"
puts "SELECTION_COUNT: #{SELECTION_COUNT}"
puts "CROSSOVER_COUNT: #{CROSSOVER_COUNT}"
puts "RANDOM_COUNT: #{RANDOM_COUNT}"
puts "MUTATION_PERCENTAGE: #{MUTATION_PERCENTAGE}"
i = 0
while true do
evolve
File.open("generation_#{i}.marshal", "w") { |f| Marshal.dump(self, f) }
i += 1
puts 'Eletes:'
p @eletes_with_fitness
end
end
def evolve
next_genes = []
eletes = select_eletes(SELECTION_COUNT)
next_genes += eletes
next_genes += crossover(eletes, CROSSOVER_COUNT)
next_genes += random_genes(RANDOM_COUNT)
@genes = next_genes
@genes.uniq!
@genes += random_genes(GENES_LIMIT - @genes.size)
mutate
end
def mutate
@genes.map do |gene|
return unless (1..100).to_a.sample <= MUTATION_PERCENTAGE
index = (0...GENE_LENGTH).to_a.sample
gene[index] = GENETICS.sample
end
end
def select_eletes(count)
# save it to instance var for debugging purpose
@eletes_with_fitness = genes_with_fitness.sort{ |x, y| x[1] <=> y[1] }.reverse.first(count)
@eletes_with_fitness.map(&:first)
end
def genes_with_fitness
@genes.dup.map do |gene|
[gene, GA.fitness(gene)]
end
end
def crossover(eletes, limit)
children = []
while children.size < limit do
split_index = (1...GENE_LENGTH).to_a.sample
father, mother = eletes.sample(2)
child = father[0...split_index] + mother[split_index..-1]
raise CrossoverError unless child.length == GENE_LENGTH
children << child
end
children
end
def random_genes(count)
(0...count).to_a.map { random_gene }
end
def random_gene
gene = ''
GENE_LENGTH.times do
gene += GENETICS.sample
end
gene
end
end
# ga = GA.new
# ga.start
ga = File.open("save_3/generation_2.marshal", "r"){|from_file| Marshal.load(from_file)}
ga.start
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment