import sys # add lifelib and golchemy to path here. # if you don't have golchemy, comment out TransformBy() # and self.center, and it should work ok anyways. # Also, this is very rough around the edges: currently it's reporting # each solution 4 times. from math import ceil import lifelib from golchemy.basics import * sess = lifelib.load_rules("b3s23") lt = sess.lifetree(n_layers=1) from copy import copy # maybe I should just use golchemy's linear transformation stuff. class Catalyst: def __init__(self, lifeHistoryRLE, absenceInterval): self.absenceInterval = absenceInterval patRLE = lifeHistoryRLE patSubstitutions = [('A', 'o'), ('B', 'b'),('C', 'o'), ('D', 'b'), ('E', 'o'), ('.', 'b'),('LifeHistory', 'B3/S23'), ] for pair in patSubstitutions: patRLE = patRLE.replace(*pair) self.pat = lt.pattern(patRLE) reqRLE = lifeHistoryRLE reqSubstitutions = [('A', 'o'), ('B', 'b'), ('C', 'b'), ('D', 'b'), ('E', 'b'), ('.', 'b'), ('LifeHistory', 'B3/S23')] for pair in reqSubstitutions: reqRLE = reqRLE.replace(*pair) self.required = lt.pattern(reqRLE) # center it [x,y,w,h] = self.pat.bounding_box self.pat = self.pat.shift(-1*ceil(x+w/2)//1, -1*ceil(y+h/2)//1) self.required = self.required.shift(-1*ceil(x+w/2)//1, -1*ceil(y+h/2)//1) # compute the center. [x,y,w,h] = self.pat.bounding_box self.center = Vec(x+(w-1)/2, y + (h-1)/2) if self.required.population > self.pat.population // 2: self.symmetries = self.required.symmetries self.symClasses = self.required.symmetry_classes else: difference = self.pat-self.required self.symmetries = difference.symmetries self.symClasses = difference.symmetry_classes self.reactionMask = self.pat.convolve(lt.pattern("x=5, y=5, rule = B3/S23\nb3o$5o$5o$5o$b3o!").shift(-2,-2)).transform("rot180") self.halo = self.pat.convolve(lt.pattern("x=3, y=3, rule = B3/S23\n3o$3o$3o!").shift(-1,-1)) self.halo -= self.pat # gives all positions of catalyst such that it might react with a cell at (0,0) # could store it as a numpy array instead # automatically work out boat-bit possibilities. # right now, if you have multiple spots in the same orientation where # a boat-bit could form, it'll probably do all of them, not each of them boatBitPossible = 'x = 6, y = 6, rule = B3/S23\n4$2b2o$2bo!' boatBit = 'x = 7, y = 6, rule = B3/S23\n3bo$2bobo$2b2o2$2b2o$2bo!' self.forbidden = [] for orientation in ["rot270", "rot180", "rot90", "identity", "flip_x", "flip_y", "swap_xy", "swap_xy_flip"]: if self.pat.replace(boatBitPossible, boatBit, orientations = [orientation]) != self.pat: self.forbidden.append(self.pat.replace(boatBitPossible, boatBit, orientations = [orientation])) # automatically work out glider-eating possibilities? def TransformBy(self, T): for q in self.symClasses: if q.inverse() * T.lin in self.symmetries: v = T*self.center - q*self.center + T.offset v.x = int(v.x) v.y = int(v.y) return Transform(q, v) class OrientedCatalyst: def __init__(self, catalyst, linearTransf): self.imageOf = linearTransf self.pat = linearTransf*catalyst.pat self.required = linearTransf*catalyst.required self.reactionMask = linearTransf*catalyst.reactionMask self.halo = linearTransf*catalyst.halo self.forbidden = [linearTransf*forbidden for forbidden in catalyst.forbidden] self.absenceInterval = catalyst.absenceInterval def XYBounds(pat): bbox = pat.bounding_box return [bbox[0], bbox[1], sum(bbox[::2])-1, sum(bbox[1::2])-1] # could be made faster if we assume catalysts are convex, ie # if it overlaps at (x,y) and at (x,y+10) then it overlaps for all # intermediate y-values. class Configuration(object): def __init__(self, startPat, startGen): self.startingCatalysts = lt.pattern('') self.gen = startGen self.state = startPat.__copy__() #self.catalystState = lt.pattern('') self.catalystsPlaced = [] self.catalystLocations = [] def PlaceCatalyst(self,orientedCat, s, x, y): toReturn = Configuration(self.state, self.gen) toReturn.state += orientedCat.pat.shift(x,y) toReturn.startingCatalysts = self.startingCatalysts + orientedCat.pat.shift(x,y) # this one could also be problematic: make sure the catalyst objects inside the lists get copied toReturn.catalystsPlaced = copy(self.catalystsPlaced) + [s] toReturn.catalystLocations = copy(self.catalystLocations)+[(x,y)] return toReturn def CopyPatList(listOfPatterns): return [pat.__copy__() for pat in listOfPatterns] class CatalystSearcher: def __init__(self, pat, offset, searchArea, numCats, timingParams, stable, catInput): #, outfile): self.startPat = lt.pattern(pat).shift(*offset) solidRectRLE = f'x = {searchArea[2]}, y = {searchArea[3]}\n' solidRectRLE += '$'.join(searchArea[3]*[f'{searchArea[2]}o']) + '!' self.searchArea = lt.pattern(solidRectRLE).shift(*searchArea[:2]) self.numCatalysts = numCats if len(timingParams) == 2: [self.startGen, self.maxGen] = timingParams self.lastGen = self.maxGen else: [self.startGen, self.lastGen, self.maxGen] = timingParams self.stableInterval = stable #self.output = outfile unorientedCatalysts = [Catalyst(*params) for params in catInput] self.results = [] self.InitializeCatalysts(unorientedCatalysts) #debugging catalystSummary = lt.pattern('') for cat in self.catalysts: catalystSummary += cat.pat catalystSummary += cat.required.shift(0,10) catalystSummary += cat.halo.shift(0,20) catalystSummary += cat.reactionMask.shift(0,30) catalystSummary = catalystSummary.shift(-10,0) print('Catalyst info') print(catalystSummary.rle_string()) def InitializeCatalysts(self, unorientedCatalysts): self.catalysts = [] for cat in unorientedCatalysts: self.catalysts+=[OrientedCatalyst(cat, orientation) for orientation in cat.symClasses] self.catalystCollisionMasks = {} for i in range(len(self.catalysts)): for j in range(len(self.catalysts)): firstCat, secondCat = self.catalysts[i], self.catalysts[j] # put first at (0,0), what positions of the 2nd will react/overlap? [xMinFirst, xMaxFirst, yMinFirst, yMaxFirst] = XYBounds(firstCat.pat) [xMinSecond, xMaxSecond, yMinSecond, yMaxSecond] = XYBounds(secondCat.pat) catCollisionMask = lt.pattern('') for x in range(xMinFirst-xMaxSecond-3, xMaxFirst-xMinSecond+4): for y in range(yMinFirst-yMaxSecond-3, yMaxFirst-yMinSecond+4): shiftedSecondCat = secondCat.pat.shift(x,y) if (shiftedSecondCat & firstCat.pat).nonempty(): catCollisionMask[x,y] = 1 else: combined = shiftedSecondCat + firstCat.pat if combined[1] != combined[0]: catCollisionMask[x,y] = 1 self.catalystCollisionMasks[(i,j)] = catCollisionMask def Search(self): config = Configuration(self.startPat, self.startGen) masks = [self.startPat.convolve(cat.reactionMask) for cat in self.catalysts] required = lt.pattern('') history = self.startPat.__copy__() self.RecursiveSearch(config, required, history, masks, [], [], [], [], [], []) def RecursiveSearch(self, config, required, history, masks, shiftedTargets, shiftedHalos, reacted, recovered, absentTime, recoveredTime): #if len(config.catalystsPlaced) == 1 and config.gen >18: # print(required.rle_string()) for g in range(config.gen, self.maxGen): if len(config.catalystsPlaced) == 0 and g > self.lastGen: if len(config.catalystsPlaced) == 1: print(f'exited at gen {g}, b/c no catalysts had been placed') return if not (required <= config.state): if len(config.catalystsPlaced) == 1: print(f'exited at gen {g}, b/c required was destroyed') return for i in range(len(config.catalystsPlaced)): if shiftedTargets[i] <= config.state and (shiftedHalos[i] & config.state).empty(): absentTime[i] = 0 recoveredTime[i] += 1 else: reacted[i] = True recoveredTime[i] = 0 absentTime[i] += 1 if reacted[i] and recoveredTime[i] > self.stableInterval: recovered[i] = True elif absentTime[i] > self.catalysts[config.catalystsPlaced[i]].absenceInterval: if len(config.catalystsPlaced) == 1: print(f'exited at gen {g}, b/c catalyst was absent for too long') return newCells = config.state - history if g >= self.startGen and len(config.catalystsPlaced) < self.numCatalysts: if not newCells.empty(): for s in range(len(self.catalysts)): catalyst = self.catalysts[s] newPlacements = ((catalyst.reactionMask).convolve(newCells)) & self.searchArea newPlacements -= masks[s] while(newPlacements.nonempty()): placement = newPlacements.firstcell newPlacements[placement] = 0 newConfig = config.PlaceCatalyst(catalyst, s, *placement) assert(len(newConfig.catalystsPlaced) == len(config.catalystsPlaced)+1) newRequired = required + catalyst.required.shift(*placement).__copy__() lookahead = newConfig.state.advance(4) # is there a difference between this vs advance 2, check, advance 2? if (newRequired <= lookahead): newShiftedTargets = CopyPatList(shiftedTargets)+[catalyst.pat.shift(*placement).__copy__()] newHalos = CopyPatList(shiftedHalos) + [catalyst.halo.__copy__()] newHistory = history + catalyst.pat.shift(*placement) newMasks = CopyPatList(masks) newReacted = copy(reacted) + [False] newRecovered = copy(recovered)+ [False] newAbsentTime = copy(absentTime) + [0] newRecoveredTime = copy(recoveredTime) + [0] for i in range(len(self.catalysts)): newMasks[i] += self.catalystCollisionMasks[(s,i)].shift(*placement) if(len(config.catalystsPlaced) == 0): print(f' Placing catalyst {s} at {placement} and calling recursive search...', end = '') self.RecursiveSearch(newConfig, newRequired, newHistory, newMasks, newShiftedTargets, newHalos, newReacted, newRecovered, newAbsentTime, newRecoveredTime) masks[s][placement] = 1 elif g < self.startGen: for i in range(len(self.catalysts)): masks[i] += (self.catalysts[i].reactionMask).convolve(config.state) if len(config.catalystsPlaced) == self.numCatalysts and all(recovered): print('solution found:') initState= config.startingCatalysts+self.startPat self.results.append(initState.rle_string()) print(initState.rle_string()) return history += newCells config.state = config.state.advance(1) config.gen += 1 if(len(config.catalystsPlaced) == 0): print(f'Done with gen {g}') if(len(config.catalystsPlaced) == 1): print('Reached max gen') return # next thing: search result infrastructure. catInputs = [('x = 4, y = 4, rule = LifeHistory\nEA$A$.3A$3.A!', 15),('x = 2, y = 2, rule = LifeHistory\nEA$2E!', 15)] herschel_predecessor_rle = 'x = 5, y = 6, rule = B3/S23\nbo$b3o$b3o$o3bo$4o$ob2o!' test = CatalystSearcher(herschel_predecessor_rle, [-15,-3], [-30, -30, 60, 60], 2, [5,25,80], 15, catInputs) test.Search() combined = lt.pattern('') for i in range(len(test.results)): combined += lt.pattern(test.results[i]).shift((i%5)*40, (i//5)*40) print(combined.rle_string())