''' Created on Jan 11, 2015 @author: Brett Paufler Copyright Brett Paufler This is just a tree sample, exploration Can likely kill with no ill effects Already pushed to web as much as is getting pushed ADD ((())) Parser as well to the end ''' import operator import random import copy #vals = [1, 2, 3, 4, 5] #op = [operator.add, operator.sub] #a,b,c,d,e,f = 1,2,3,4,5,6 #a = [p,b,b] #aL = [m, 5, [p, [p,a,a],[p,a,a]]] def parse_list2(a): '''This doesn't work so well ''' bA = copy.deepcopy(a) for b in bA: if isinstance(b,list): return parse_list2(b) return bA[0](bA[1],bA[2]) def parse_list(a): ''' ''' a = copy.deepcopy(a) for n in [0,1,2]: if isinstance(a[n], list): a[n] = parse_list(a[n]) r = a[0](a[1],a[2]) return r def count_nodes(aL,count=1): '''number of nodes in tree ''' for n in [1,2]: if isinstance(aL[n],list): count += count_nodes(aL[n]) return count def number_nodes(aL,count=0): '''returns numbered node array, and count, could likely reduce libary to this with two helpers ''' aN = [] for n in [0,1,2]: if callable(aL[n]): aN.append(count) count += 1 elif isinstance(aL[n], list): temp,count = number_nodes(aL[n], count) aN.append(temp) return aN,count def replace_node(aL,newNode,node): ''' ''' for n in [0,1,2]: if callable(aL[n]): if node == 0: aL[node] = newNode node -= 1 elif isinstance(aL[n], list): aL[n],node = replace_node(aL[n],newNode,node) return aL,node def count_leafs(aL,count=2): '''number of leafs in tree ''' for n in [1,2]: if isinstance(aL[n],list): count += count_nodes(aL[n]) return count def number_leafs(aL, count=0): '''returns a numbered structure of the leafs ''' for n in [1,2]: if isinstance(aL[n],int): aL[n] = count count += 1 if isinstance(aL[n],list): aL[n],count = number_leafs(aL[n],count) return aL,count def replace_leaf(aL,v,leaf): '''replaces al[leaf] with v returns aL, leaf final leaf + numberNodes == 0 or something is wrong ''' for n in [1,2]: if isinstance(aL[n],int): if leaf == 0: aL[n] = v leaf -= 1 elif isinstance(aL[n],list): aL[n],leaf = replace_leaf(aL[n], v, leaf) return aL,leaf def random_leaf_to_node(aThis,newNode): ''' ''' leaf = count_leafs(aThis[:]) r = random.randint(0,leaf-1) aThis,leaf = replace_leaf(aThis[:],newNode, r) return aThis def replace_node_with_leaf(aL,newLeaf,node): '''replaces a node with a leaf ''' for n in [0,1,2]: if callable(aL[n]): if node == 0: node -= 1 return newLeaf, node #aL[node] = newNode else: node -= 1 elif isinstance(aL[n], list): aL[n],node = replace_node_with_leaf(aL[n],newLeaf,node) return aL,node def random_node_to_leaf(aL,newLeaf): ''' ''' aL = copy.deepcopy(aL) if count_nodes(aL) == 1: return aL r = random.randint(1,count_nodes(aL)) aL, _ = replace_node_with_leaf(aL, newLeaf, r) return aL def simple_random_node(): '''returns a simple random node of form [operator, int,int] ''' return [random.choice([operator.add, operator.sub, operator.mul]), random.randint(0,9), random.randint(0,9)] def random_change(inL): '''makes a random change to a list tree ''' return random.choice([random_node_to_leaf(inL, random.randint(0,99)), random_leaf_to_node(inL, simple_random_node())]) #print "random_change: %s" % str(x) #return x def find_solution(listIn, goal, count=0): aL = copy.deepcopy(listIn) count += 1 print "\ncount: %d" % count if count > 750: return aL, goal, count vA = parse_list(aL[:]) print "vA:%d \t%s" % (vA,aL) vA = parse_list(aL[:]) print "vA:%d \t%s" % (vA,aL) print "vA:%d \t%s" % (vA,aL) #bL = random_leaf_to_node(copy.deepcopy(listIn),simple_random_node()) bL = random_change(copy.deepcopy(listIn)) print "vA:%d \t%s" % (vA,aL) vB = parse_list(bL) print "vA:%d \t%s" % (vA,aL) print "vB:%d \t%s" % (vB,bL) if vB == goal: return bL,goal,count a = abs(goal - vA) b = abs(goal - vB) if a <= b: print "RETURN aL: %s" % aL[:] return find_solution(aL[:],goal,count) else: print "RETURN bL: %s" % bL[:] return find_solution(bL[:],goal,count) def genetic_this_or_that(seed=[operator.add,1,1], goal=1018 ): '''finds an iterative of form discussed that when parsed equals the goal ''' currentBest = copy.deepcopy(seed) cB = parse_list(currentBest) if cB == goal: return currentBest nextTry = random_change(copy.deepcopy(seed)) nT = parse_list(nextTry) if abs(goal - cB) <= abs(goal - nT): print "RETURN currentBest: %s" % currentBest return genetic_this_or_that(currentBest,goal) else: print "RETURN nextTry: %s" % nextTry return genetic_this_or_that(nextTry,goal) ''' goal=10 #goal=1018 solutionSet = genetic_this_or_that(goal=goal) print "\n\n%d Reached:\n%s" % (goal, solutionSet) #solutionSet,goal = genetic_this_or_that() #print "\n\n%d Reached:\n%s" % (goal, solutionSet) '''