alf239 · November 5, 2012 10:52 · alf239 · Nov 21, 2012
diff --git a/robot.py b/robot.py
 #!/usr/bin/env python
 # encoding: utf-8
 """
 robot.py

 Created by Alexey Filippov on 2012-11-03.
 Copyright (c) 2012 Alexey Filippov. All rights reserved.
 """

 import sys
 import os
 import random

 def sqr(x):
    return x*x

 class Cell:
    def __init__(this, code):
        this.code = code
        this.moves = dict()
    
    def move(this, move):
        if move in this.moves:
            return this.moves[move]
        return this
    
    def canReach(this):
        visited = set()
        queue = [this]
        while True:
            c = queue.pop()
            if not c.code in visited:
                visited |= set([c.code])
                queue = queue + [x for x in c.moves.values() if not x.code in visited]
            if not queue:
                break
        return visited

    def __str__(this):
        return "%d" % (this.code)
    
    def __hash__(this):
        return this.code

 class Field:
    def __init__(this, map):
        this.code = map
        this.cells = [Cell(i) for i in range(9)]
        if 0 != (map & 0b100000000000): this.link(0, 1, 'rl')
        if 0 != (map & 0b010000000000): this.link(1, 2, 'rl')
        if 0 != (map & 0b001000000000): this.link(0, 3, 'du')
        if 0 != (map & 0b000100000000): this.link(1, 4, 'du')
        if 0 != (map & 0b000010000000): this.link(2, 5, 'du')
        if 0 != (map & 0b000001000000): this.link(3, 4, 'rl')
        if 0 != (map & 0b000000100000): this.link(4, 5, 'rl')
        if 0 != (map & 0b000000010000): this.link(3, 6, 'du')
        if 0 != (map & 0b000000001000): this.link(4, 7, 'du')
        if 0 != (map & 0b000000000100): this.link(5, 8, 'du')
        if 0 != (map & 0b000000000010): this.link(6, 7, 'rl')
        if 0 != (map & 0b000000000001): this.link(7, 8, 'rl')
    
    def link(this, f, t, m):
        this.cells[f].moves[m[0]] = this.cells[t]
        this.cells[t].moves[m[1]] = this.cells[f]
    
    def linked(this):
        return len(this.cells[0].canReach()) == 9
    
    def log(this):
        print "map", this.code
        for i in range(9):
            print this.cells[i].code, "->", [c.code for c in 
                                         this.cells[i].moves.values()]

 class Robot:
    def __init__(this, cell):
        this.c = cell
    
    def move(this, move):
        this.c = this.c.move(move)
    
    def execute(this, s):
        seen = set([this.c])
        for c in s:
            this.move(c)
            seen |= set([this.c])
        return seen

 def dna():
    return ''.join(random.choice("lrud") for n in xrange(60))

 def fields():
    return [f for f in [Field(i) for i in xrange(2**12)] if f.linked()]

 def score(program, test_set, fields = 10, positions = 3):
    passed = 0.0
    for field in random.sample(test_set, fields):
        for start in random.sample(range(9), positions):
            r = Robot(field.cells[start])
            seen = r.execute(program)
            passed += sqr(len(seen) / 9.)
    return sqr(passed / fields / positions)

 def select(colony, f):
    scores = sorted([(robot, f(robot)) for robot in colony], key = lambda s: -s[1])
    print "\n".join(["%s: %.6f" % s for s in scores[:10]])
    if test_program(scores[0][0]):
        print "Solved", scores[0][0], scores[0][1]
    else:
        scores = scores[1:]
    return [s[0] for s in scores if s[1] > random.lognormvariate(0.5, 0.2) - 1]

 def baby(a,b):
    return a[:random.randint(0, len(a) - 1)] + b[-random.randint(0,len(b)-1):]

 def grow(colony, n):
    print "survivors:", len(colony)
    num = n - len(colony)
    cl = [s for s in random.sample(colony, min(num/2, len(colony)))]
    clones = []
    for c in cl:
        i = random.randint(0, len(c))
        clones.append(c[:i] + c[i+1:])
    print "mutations:", len(clones)
    children = [baby(random.choice(colony), random.choice(colony)) 
                for i in xrange(num / 2)]
    print "children:", len(children)
    return colony + clones + children

 def genetic(test_set, n = 1000, generations = 10000):
    colony = [dna() for  i in xrange(n)]
    
    for i in xrange(generations):
        print i, "generation"
        colony = select(colony, lambda bot: score(bot, test_set))
        colony = grow(colony, n)

 def test_program(s):
    test_set = fields()
    
    for f in test_set:
        for c in xrange(9):
            r = Robot(f.cells[c])
            seen = r.execute(s)
            if (len(seen) != 9): return False
    return True

 def main():
    genetic(fields(), n = 1000)
    # print test_program("urrdludrrduddulurudullruuldrulrdrdrrdllululrruluddrlluuddurrlrrdrrrlulllrduldlrdddlrurulrllddlruurlruulurllduulrrdddlddrrdulurruldrrrdurldlurlrlrdulurddrdullldulrdruuddluddddludlldddrddrulrrluldllrdldrdrrdludrrduuulllrrdlurururdurdddurlruululuuuddrrrurduulruruulrrdddlddrrdulurrulrdldluludldruddrrldluuluduurudrdrrdrlldruuduruulldurruuluuuudlddllrlrlludrududrdurddruuuldrdrrdldrdrrurur")

 if __name__ == '__main__':
    main()
	#!/usr/bin/env python
	# encoding: utf-8
	"""
	robot.py

	Created by Alexey Filippov on 2012-11-03.
	Copyright (c) 2012 Alexey Filippov. All rights reserved.
	"""

	import sys
	import os
	import random

	def sqr(x):
	return x*x

	class Cell:
	def __init__(this, code):
	this.code = code
	this.moves = dict()

	def move(this, move):
	if move in this.moves:
	return this.moves[move]
	return this

	def canReach(this):
	visited = set()
	queue = [this]
	while True:
	c = queue.pop()
	if not c.code in visited:
	visited \|= set([c.code])
	queue = queue + [x for x in c.moves.values() if not x.code in visited]
	if not queue:
	break
	return visited

	def __str__(this):
	return "%d" % (this.code)

	def __hash__(this):
	return this.code

	class Field:
	def __init__(this, map):
	this.code = map
	this.cells = [Cell(i) for i in range(9)]
	if 0 != (map & 0b100000000000): this.link(0, 1, 'rl')
	if 0 != (map & 0b010000000000): this.link(1, 2, 'rl')
	if 0 != (map & 0b001000000000): this.link(0, 3, 'du')
	if 0 != (map & 0b000100000000): this.link(1, 4, 'du')
	if 0 != (map & 0b000010000000): this.link(2, 5, 'du')
	if 0 != (map & 0b000001000000): this.link(3, 4, 'rl')
	if 0 != (map & 0b000000100000): this.link(4, 5, 'rl')
	if 0 != (map & 0b000000010000): this.link(3, 6, 'du')
	if 0 != (map & 0b000000001000): this.link(4, 7, 'du')
	if 0 != (map & 0b000000000100): this.link(5, 8, 'du')
	if 0 != (map & 0b000000000010): this.link(6, 7, 'rl')
	if 0 != (map & 0b000000000001): this.link(7, 8, 'rl')

	def link(this, f, t, m):
	this.cells[f].moves[m[0]] = this.cells[t]
	this.cells[t].moves[m[1]] = this.cells[f]

	def linked(this):
	return len(this.cells[0].canReach()) == 9

	def log(this):
	print "map", this.code
	for i in range(9):
	print this.cells[i].code, "->", [c.code for c in
	this.cells[i].moves.values()]

	class Robot:
	def __init__(this, cell):
	this.c = cell

	def move(this, move):
	this.c = this.c.move(move)

	def execute(this, s):
	seen = set([this.c])
	for c in s:
	this.move(c)
	seen \|= set([this.c])
	return seen

	def dna():
	return ''.join(random.choice("lrud") for n in xrange(60))

	def fields():
	return [f for f in [Field(i) for i in xrange(2**12)] if f.linked()]

	def score(program, test_set, fields = 10, positions = 3):
	passed = 0.0
	for field in random.sample(test_set, fields):
	for start in random.sample(range(9), positions):
	r = Robot(field.cells[start])
	seen = r.execute(program)
	passed += sqr(len(seen) / 9.)
	return sqr(passed / fields / positions)

	def select(colony, f):
	scores = sorted([(robot, f(robot)) for robot in colony], key = lambda s: -s[1])
	print "\n".join(["%s: %.6f" % s for s in scores[:10]])
	if test_program(scores[0][0]):
	print "Solved", scores[0][0], scores[0][1]
	else:
	scores = scores[1:]
	return [s[0] for s in scores if s[1] > random.lognormvariate(0.5, 0.2) - 1]

	def baby(a,b):
	return a[:random.randint(0, len(a) - 1)] + b[-random.randint(0,len(b)-1):]

	def grow(colony, n):
	print "survivors:", len(colony)
	num = n - len(colony)
	cl = [s for s in random.sample(colony, min(num/2, len(colony)))]
	clones = []
	for c in cl:
	i = random.randint(0, len(c))
	clones.append(c[:i] + c[i+1:])
	print "mutations:", len(clones)
	children = [baby(random.choice(colony), random.choice(colony))
	for i in xrange(num / 2)]
	print "children:", len(children)
	return colony + clones + children

	def genetic(test_set, n = 1000, generations = 10000):
	colony = [dna() for i in xrange(n)]

	for i in xrange(generations):
	print i, "generation"
	colony = select(colony, lambda bot: score(bot, test_set))
	colony = grow(colony, n)

	def test_program(s):
	test_set = fields()

	for f in test_set:
	for c in xrange(9):
	r = Robot(f.cells[c])
	seen = r.execute(s)
	if (len(seen) != 9): return False
	return True

	def main():
	genetic(fields(), n = 1000)
	# print test_program("urrdludrrduddulurudullruuldrulrdrdrrdllululrruluddrlluuddurrlrrdrrrlulllrduldlrdddlrurulrllddlruurlruulurllduulrrdddlddrrdulurruldrrrdurldlurlrlrdulurddrdullldulrdruuddluddddludlldddrddrulrrluldllrdldrdrrdludrrduuulllrrdlurururdurdddurlruululuuuddrrrurduulruruulrrdddlddrrdulurrulrdldluludldruddrrldluuluduurudrdrrdrlldruuduruulldurruuluuuudlddllrlrlludrududrdurddruuuldrdrrdldrdrrurur")

	if __name__ == '__main__':
	main()