Hunting wrote: ↑November 12th, 2020, 8:48 am
How does the catalyst search program in your simulator work?
Essentially, you need to specify a search area so for this search it was something like
Code: Select all
x = 37, y = 37, rule = B2n3/S23-qHistory
33.4A2$28.2A.3A$27.A2.2A$26.A$24.2A$24.2A2$24.A3.A$24.A3.A$25.A.A$25.
A2$24.2A$20.A$19.A.2A$18.A3.A$17.A$17.A.2A.A$13.A7.2A$11.5A.A$10.A2.A
$10.A2.A2.2A$8B3.A.A$9B4.3A$10B4.A$11B$12B$13B$13B$14B$14B$14B$14B$14B
$14B$14B!
A list of catalysts to use are provided so for this search it was
Code: Select all
oo$oo!
bo$obo$obo$bo!
boo$obo$bob!
bo$obo$bo!
b2o$o2bo$o2bo$b2o!
b2o$o2bo$bobo$2bo!
3bo$b3o$o$b3o$3bo!
2o$obo$2bo$bo$b2o!
bo$obo$o2bo$bobo$2bo!
The program randomly selects n catalysts from the list (the user specifies n, I chose 3) and they are placed in the search area. The catalysts are also randomly flipped and rotated. Of course, some may overlap and but most overlapping catalysts don't turn out to be classified as catalysts so its not a big deal. This problem can be solved by simply stepping the simulation forward by 1 generation and checking that the pattern does not change (assuming stable catalysts).
The catalyst and the target pattern are stepped forward g generations (in this case, g = 50). Every generation, each catalyst is checked if it has changed. This is done by checking if a spark or something has entered the "neighbourhood" of the catalyst. This "neighbourhood" can be obtained by running 1 round of BFS on each cell of the catalyst with the cells being connected to their neighbours.
If a catalyst is interacted with, a counter is incremented and an interacted flag associated with the catalyst is set to true.
If an interacted catalyst regenerates, a counter is incremented and the regenerated flag associated with the catalyst is set to true.
If at least one catalyst has been interacted with and all catalysts have regenerated, it is a valid catalyst and it is added to the search results.
Repeat time is computed as the time between the first interaction and the last catalyst regenerating.
The search results are saved in a *.csv file periodically (if you run from CMD) or shown in a table (if you run from the GUI).
So its basically CatForce without the brute force. I may add brute force in the future but not for quite sometime (mostly because I have not worked out how to do it).
Also here's the code because why not
Code: Select all
package sample.model.search.catsrc;
import sample.model.Coordinate;
import sample.model.patterns.Catalyst;
import sample.model.search.SearchProgram;
import sample.model.simulation.Grid;
import sample.model.simulation.Simulator;
import java.io.File;
import java.io.FileWriter;
import java.io.IOException;
import java.util.*;
import java.util.logging.Level;
import java.util.logging.LogManager;
import java.util.logging.Logger;
class PlacedCatalyst {
private boolean interacted = false;
private boolean regenerated = false;
private final int hash;
private final Coordinate startCoordinate;
private final List<Coordinate> coordinateList;
public PlacedCatalyst(int hash, Coordinate startCoordinate, List<Coordinate> coordinateList) {
this.hash = hash;
this.startCoordinate = startCoordinate;
this.coordinateList = coordinateList;
}
public int getHash() {
return hash;
}
public Coordinate getStartCoordinate() {
return startCoordinate;
}
public List<Coordinate> getCoordinateList() {
return coordinateList;
}
public boolean hasInteracted() {
return interacted;
}
public boolean hasRegenerated() {
return regenerated;
}
public void setInteracted(boolean interacted) {
this.interacted = interacted;
}
public void setRegenerated(boolean regenerated) {
this.regenerated = regenerated;
}
}
public class CatalystSearch extends SearchProgram {
private Set<Catalyst> known;
private final Random random = new Random();
public CatalystSearch(CatalystSearchParameters parameters) {
super(parameters);
}
@Override
public void search(int num) {
Simulator simulator;
CatalystSearchParameters searchParameters = (CatalystSearchParameters) this.searchParameters;
if (searchParameters.getBruteForce()) {
// TODO (Brute force)
} else {
known = new HashSet<>();
searchResults = new ArrayList<>(); // Initialise search results
long startTime = System.currentTimeMillis();
int initialGeneration = -1, repeatTime = -1;
int hash, numRegen = 0, numInteracted = 0;
List<PlacedCatalyst> placedCatalysts;
for (int i = 0; i < num; i++) {
simulator = new Simulator(searchParameters.getRule());
initialGeneration = -1;
placedCatalysts = randomAddCatalyst(simulator, searchParameters);
if (placedCatalysts == null) continue; // The catalysts overlap and are not still lives
// Inserting the target
simulator.insertCells(searchParameters.getTarget(), new Coordinate());
Grid original = simulator.deepCopy();
for (int j = 0; j < searchParameters.getMaxRepeatTime(); j++) {
simulator.step();
numRegen = 0;
numInteracted = 0;
for (PlacedCatalyst catalyst: placedCatalysts) {
hash = simulator.hashCode(catalyst.getCoordinateList(), catalyst.getStartCoordinate());
if (hash != catalyst.getHash() && !catalyst.hasInteracted()) {
catalyst.setInteracted(true);
if (initialGeneration == -1) initialGeneration = simulator.getGeneration();
} else if (hash == catalyst.getHash() && catalyst.hasInteracted() &&
!catalyst.hasRegenerated()) {
catalyst.setRegenerated(true);
repeatTime = simulator.getGeneration() - initialGeneration;
}
// To consider a catalyst valid,
// 1. At least one of the sub-catalysts must have been interacted with
// 2. All interacted catalysts must have been regenerated
if (catalyst.hasInteracted()) numInteracted++;
if (catalyst.hasInteracted() && catalyst.hasRegenerated()) numRegen++;
}
// Every single catalyst regenerated
if (numRegen == numInteracted && numInteracted >= 1) {
Catalyst catalyst = new Catalyst(simulator.getRule(), original, repeatTime);
add(searchResults, catalyst);
break;
}
}
synchronized (this) { // To avoid race conditions
if (numSearched % 5000 == 0 && numSearched != 0) {
System.out.println(numSearched + " potential catalysts searched (" +
5000000 / (System.currentTimeMillis() - startTime) +
" potential catalysts/s), " + searchResults.size() + " catalysts found!");
startTime = System.currentTimeMillis();
}
numSearched++;
}
}
}
}
@Override
public boolean writeToFile(File file) {
try {
FileWriter fileWriter = new FileWriter(file);
fileWriter.write("# Running search in " + ((CatalystSearchParameters) searchParameters).getRule() +
"\n");
fileWriter.write("Catalyst,RLE\n");
for (int i = 0; i < searchResults.size(); i++) {
fileWriter.write(searchResults.get(i) + "," + searchResults.get(i).toRLE() + "\n");
}
fileWriter.close();
return true;
} catch (IOException exception) {
LogManager.getLogManager().getLogger(Logger.GLOBAL_LOGGER_NAME).
log(Level.WARNING, exception.getMessage());
return false;
}
}
private List<PlacedCatalyst> randomAddCatalyst(Simulator grid, CatalystSearchParameters searchParameters) {
int index;
Grid catalyst;
Coordinate coordinate;
ArrayList<PlacedCatalyst> placedCatalysts = new ArrayList<>();
for (int i = 0; i < searchParameters.getNumCatalysts(); i++) {
index = random.nextInt(searchParameters.getCoordinateList().size());
coordinate = searchParameters.getCoordinateList().get(index);
index = random.nextInt(searchParameters.getCatalysts().size());
catalyst = searchParameters.getCatalysts().get(index).deepCopy();
if (searchParameters.getRotateCatalyst()) {
catalyst.updateBounds();
for (int j = 0; j < random.nextInt(4); j++)
catalyst.rotateCW(catalyst.getBounds().getValue0(), catalyst.getBounds().getValue1());
}
if (searchParameters.getFlipCatalyst()) {
catalyst.updateBounds();
int randomInt = random.nextInt(4);
if (randomInt == 0) {
catalyst.reflectCellsX(catalyst.getBounds().getValue0(), catalyst.getBounds().getValue1());
} else if (randomInt == 1) {
catalyst.reflectCellsY(catalyst.getBounds().getValue0(), catalyst.getBounds().getValue1());
} else if (randomInt == 2) {
catalyst.reflectCellsX(catalyst.getBounds().getValue0(), catalyst.getBounds().getValue1());
catalyst.reflectCellsY(catalyst.getBounds().getValue0(), catalyst.getBounds().getValue1());
}
}
grid.insertCells(catalyst, coordinate);
List<Coordinate> bfsResult = catalyst.bfs(1, searchParameters.getRule().getNeighbourhood());
Coordinate coordinate3 = new Coordinate();
for (Coordinate coordinate2: bfsResult) {
if (coordinate3.getX() > coordinate2.getX())
coordinate3 = new Coordinate(coordinate2.getX(), coordinate3.getY());
if (coordinate3.getY() > coordinate2.getY())
coordinate3 = new Coordinate(coordinate3.getX(), coordinate2.getY());
}
int hash = catalyst.hashCode(bfsResult, coordinate3);
for (int j = 0; j < bfsResult.size(); j++) bfsResult.set(j, bfsResult.get(j).add(coordinate));
for (Coordinate coordinate2: bfsResult) {
if (coordinate.getX() > coordinate2.getX())
coordinate = new Coordinate(coordinate2.getX(), coordinate.getY());
if (coordinate.getY() > coordinate2.getY())
coordinate = new Coordinate(coordinate.getX(), coordinate2.getY());
}
placedCatalysts.add(new PlacedCatalyst(hash, coordinate, bfsResult));
}
// if (!grid.identify(2).toString().equals("Still Life")) {
// return null;
// }
return placedCatalysts;
}
}
