Last active
October 12, 2019 16:06
Star
You must be signed in to star a gist
Generate 4G collisions which result in constellations of stationary objects (p1, p2, p3, or p6)
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include <iostream> | |
#include <cstring> | |
#include "LifeAPI.h" | |
int main(int argc, char *argv[]) { | |
int pops[16], allpops[256]; | |
char s[1024], line[1024]; | |
s[0] = 0; | |
New(); | |
LifeState *after = NewState(); | |
LifeState *before = NewState(); | |
LifeState *g_ne = NewState("3o$2bo$bo!"); | |
LifeState *g_se = NewState("bo$2bo$3o!"); | |
LifeState *g_nw = NewState("3o$o$bo!"); | |
LifeState *g_sw = NewState("bo$o$3o!"); | |
LifeState *g1 = NewState(); | |
Copy(g1, g_ne); | |
Move(g1, -5, 5); | |
LifeIterator *g2 = NewIterator(g_ne, -25, 10, 24, 24, 4); | |
LifeIterator *g3 = NewIterator(g_nw, 4, 5, 2, 1, 19); | |
LifeIterator *g4 = NewIterator(g_nw, 4, 5, 14, 14, 4); | |
int period = 4; | |
int n = 0; | |
int ntot = 0; | |
int ng2 = 0; | |
int ng2tot = 0; | |
bool isValid = true; | |
do { | |
Copy(before, g1); | |
Join(before, g2); | |
ClearData(after); | |
Copy(after, before); | |
ng2tot++; | |
// Check for valid 2G collision | |
isValid = true; | |
for(int i=0; i<4; i++) { | |
Evolve(after, 1); | |
if (GetPop(after) != 10) { | |
isValid = false; | |
continue; | |
} | |
} | |
if (!isValid) | |
continue; | |
ng2++; | |
// printf("ng2 = %d, ng2tot = %d\n", ng2, ng2tot); | |
do { | |
do { | |
Copy(before, g1); | |
Join(before, g2); | |
Join(before, g3); | |
Join(before, g4); | |
ClearData(after); | |
Copy(after, before); | |
ntot++; | |
isValid = true; | |
for(int i=0; i<4; i++) { | |
Evolve(after, 1); | |
if (GetPop(after) != 20) { | |
isValid = false; | |
continue; | |
} | |
} | |
if (!isValid) | |
continue; | |
n++; | |
// printf("ng2 = %d, n = %d, ntot = %d\n", ng2, n, ntot); | |
Evolve(after, 60); | |
for (int i; i<140; i++) { | |
Evolve(after, 1); | |
if ((after->min < 1) || (after->max > N-2)) { | |
isValid = false; | |
continue; | |
} | |
} | |
if (!isValid) | |
continue; | |
if (GetPop(after) < 7) // All constellations with pop < 7 require <= 4G | |
continue; | |
if (after->num_emitted > 0) | |
continue; | |
ClearData(GlobalState); | |
PutState(after); // Save pattern in global state | |
Evolve(after, 6); | |
if (IsSame(after)) { // Compare with saved pattern | |
PrintRLE(before); | |
fflush(stdout); | |
break; | |
} | |
} while(Next(g4)); | |
} while(Next(g3)); | |
if (ng2tot % 24 == 0) | |
std::cerr << ng2 << " valid g2 positions out of " << ng2tot << " evaluated." << std::endl; | |
} while(Next(g2)); | |
std::cerr << n << " glider collisions tested out of " << ntot << " total." << std::endl; | |
return 0; | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
//LifeAPI provide comfortable functions (API) to manipulate, iterate, evolve, compare and report Life objects. This is mainly done | |
//in order to provide fast (using C) but still comfortable search utility. | |
//Contributors Chris Cain, Dongook Lee. | |
//Written by Michael Simkin 2014 | |
#pragma once | |
#include <stdio.h> | |
#include <stdint.h> | |
#include <stdlib.h> | |
#include <string.h> | |
#define N 64 | |
#define MAX_EMITTED 64 | |
#define PrimeN 71 | |
#define CAPTURE_COUNT 10 | |
#define MAX_ITERATIONS 200 | |
#define SUCCESS 1 | |
#define FAIL 0 | |
#define YES 1 | |
#define NO 0 | |
#ifdef _MSC_VER | |
#include <intrin.h> | |
#define __builtin_popcountll __popcnt64 | |
#endif | |
enum CopyType { COPY, OR, XOR, AND }; | |
enum EvolveType { EVOLVE, LEAVE }; | |
typedef struct | |
{ | |
char* value; | |
int size; | |
int allocated; | |
} LifeString; | |
void FreeString(LifeString* string) | |
{ | |
free(string->value); | |
free(string); | |
} | |
LifeString* NewString() | |
{ | |
LifeString* result = (LifeString*)(malloc(sizeof(LifeString))); | |
result->value = (char*)(malloc(2 * sizeof(char))); | |
result->value[0] = '\0'; | |
result->size = 1; | |
result->allocated = 1; | |
return result; | |
} | |
void Clear(LifeString* s) | |
{ | |
s->value[0] = '\0'; | |
s->size = 1; | |
} | |
void Realloc(LifeString* string) | |
{ | |
int empty = NO; | |
if(string->value[0] == '\0') | |
empty = YES; | |
if(empty == NO) | |
{ | |
string->value = (char*)(realloc(string->value, string->allocated * 2 * sizeof(char))); | |
} | |
else | |
{ | |
string->value = (char*)(malloc(string->allocated * 2 * sizeof(char))); | |
string->value[0] = '\0'; | |
} | |
string->allocated *= 2; | |
} | |
void Realloc(LifeString* string, int size) | |
{ | |
while(string->allocated <= string->size + size + 1) | |
Realloc(string); | |
} | |
void Append(LifeString* string, const char* val) | |
{ | |
Realloc(string, strlen(val)); | |
strcat(string->value, val); | |
string->size = strlen(string->value); | |
} | |
void Append(LifeString* string, int val) | |
{ | |
char str[10]; | |
sprintf(str, "%d", val); | |
Append(string, str); | |
} | |
LifeString* NewString(const char* val) | |
{ | |
LifeString* result = NewString(); | |
Append(result, val); | |
return result; | |
} | |
static LifeString* TempString = NewString(); | |
typedef struct | |
{ | |
int x; | |
int y; | |
int gen; | |
int dx; | |
int dy; | |
} EmitedGlider; | |
typedef struct | |
{ | |
int min; | |
int max; | |
int gen; | |
uint64_t state[N]; | |
EmitedGlider emittedGliders[MAX_EMITTED]; | |
int num_emitted; | |
} LifeState; | |
static LifeState* GlobalState; | |
#pragma omp threadprivate(GlobalState) | |
static LifeState* Captures[CAPTURE_COUNT]; | |
#pragma omp threadprivate(Captures) | |
static LifeState* Temp, *Temp1, *Temp2; | |
#pragma omp threadprivate(Temp, Temp1, Temp2) | |
static EmitedGlider _gliders[4]; | |
#pragma omp threadprivate(_gliders) | |
inline uint64_t CirculateLeft(uint64_t x){ | |
return (x << 1) | (x >> (63)); | |
} | |
inline uint64_t CirculateLeft(uint64_t x, int k) | |
{ | |
return (x << k) | (x >> (64 - k)); | |
} | |
inline uint64_t CirculateRight(uint64_t x, int k) | |
{ | |
return (x >> k) | (x << (64 - k)); | |
} | |
inline uint64_t CirculateRight(uint64_t x) | |
{ | |
return (x >> 1) | (x << (63)); | |
} | |
void Set(int x, int y, uint64_t *state) | |
{ | |
state[x] |= (1ULL << (y)); | |
} | |
void Erase(int x, int y, uint64_t *state) | |
{ | |
state[x] &= ~(1ULL << (y)); | |
} | |
int Get(int x, int y, uint64_t *state) | |
{ | |
return (state[x] & (1ULL << y)) >> y; | |
} | |
void SetCell(LifeState* state, int x, int y, int val) | |
{ | |
if(val == 1) | |
{ | |
Set((x + 32) % N, (y + 32) % 64, state->state); | |
} | |
if(val == 0) | |
Erase((x + 32) % 64, (y + 32) % 64, state->state); | |
} | |
int GetCell(LifeState* state, int x, int y) | |
{ | |
return Get((x + 32) % 64, (y + 32) % 64, state->state); | |
} | |
int GetCell(int x, int y) | |
{ | |
return GetCell(GlobalState, x, y); | |
} | |
void SetCell(int x, int y, int val) | |
{ | |
SetCell(GlobalState, x, y, val); | |
} | |
uint64_t GetHash(LifeState* state) | |
{ | |
uint64_t result = 0; | |
for(int i = state->min; i <= state->max; i++) | |
{ | |
result += CirculateRight(state->state[i], i); | |
result += CirculateLeft(state->state[i], (i + 8) % 47); | |
} | |
return result; | |
} | |
uint64_t GetHash() | |
{ | |
return GetHash(GlobalState); | |
} | |
void ExpandMinMax(int* min, int* max) | |
{ | |
*min -= 2; | |
*max += 2; | |
if(*min < 0) | |
(*min) = 0; | |
if(*max > N - 1) | |
(*max) = N - 1; | |
} | |
void RefitMinMax(LifeState* state) | |
{ | |
int min = state->min; | |
int max = state->max; | |
uint64_t * states = state->state; | |
for(int i = min; i <= max; i++) | |
{ | |
if(states[i] != 0) | |
{ | |
state-> min = i; | |
break; | |
} | |
} | |
for(int i = max; i >= min; i--) | |
{ | |
if(states[i] != 0) | |
{ | |
state-> max = i; | |
break; | |
} | |
} | |
ExpandMinMax(&(state-> min), &(state-> max)); | |
} | |
void RecalculateMinMax(LifeState* state) | |
{ | |
state-> min = N - 1; | |
state-> max = 0; | |
uint64_t * states = state->state; | |
for(int i = 0; i < N; i++) | |
{ | |
if(states[i] != 0) | |
{ | |
state-> min = i; | |
break; | |
} | |
} | |
for(int i = N - 1; i >= 0; i--) | |
{ | |
if(states[i] != 0) | |
{ | |
state-> max = i; | |
break; | |
} | |
} | |
ExpandMinMax(&(state-> min), &(state-> max)); | |
} | |
void Print(LifeState *state) | |
{ | |
int i, j; | |
for(i = 0; i < N; i++) | |
{ | |
for(j = 0; j < 64; j++) | |
{ | |
if(GetCell(state, j - 32, i - 32) == 0) | |
{ | |
int hor = 0; | |
int ver = 0; | |
if((i - 32) % 10 == 0) | |
hor = 1; | |
if((j - 32) % 10 == 0) | |
ver = 1; | |
if(hor == 1 && ver == 1) | |
printf ("+"); | |
else if(hor == 1) | |
printf ("-"); | |
else if(ver == 1) | |
printf ("|"); | |
else | |
printf ("."); | |
} | |
else | |
printf ("O"); | |
} | |
printf("\n"); | |
} | |
printf("\n\n\n\n\n\n"); | |
} | |
void Copy(LifeState* main, LifeState* delta, CopyType op) | |
{ | |
if(op == COPY) | |
{ | |
for(int i = 0; i < N; i++) | |
main->state[i] = delta->state[i]; | |
main->gen = delta->gen; | |
} | |
if(op == OR) | |
{ | |
for(int i = 0; i < N; i++) | |
main->state[i] |= delta->state[i]; | |
} | |
if(op == AND) | |
{ | |
for(int i = 0; i < N; i++) | |
main->state[i] &= delta->state[i]; | |
} | |
if(op == XOR) | |
{ | |
for(int i = 0; i < N; i++) | |
main->state[i] ^= delta->state[i]; | |
} | |
RecalculateMinMax(main); | |
} | |
void Copy(LifeState* main, LifeState* delta) | |
{ | |
Copy(main, delta, COPY); | |
} | |
int GetPop(LifeState* state) | |
{ | |
int pop = 0; | |
int min = state->min; | |
int max = state->max; | |
uint64_t * mainState = state->state; | |
for(int i = min; i <= max; i++) | |
{ | |
pop += __builtin_popcountll(mainState[i]); | |
} | |
return pop; | |
} | |
int GetPop() | |
{ | |
return GetPop(GlobalState); | |
} | |
int IsSame(LifeState* s1, LifeState* s2) | |
{ | |
for(int i = 0; i < N; i++) | |
if(s1->state[i] != s2->state[i]) | |
return NO; | |
return YES; | |
} | |
int IsSame(LifeState* s1) | |
{ | |
return IsSame(GlobalState, s1); | |
} | |
int IsSame(int capture_idx) | |
{ | |
return IsSame(GlobalState, Captures[capture_idx]); | |
} | |
int IsEmpty(LifeState* s) | |
{ | |
int min = s->min; | |
int max = s->max; | |
uint64_t * mainState = s->state; | |
for(int i = min; i <= max; i++) | |
{ | |
if(mainState[i] != 0LL) | |
return NO; | |
} | |
return YES; | |
} | |
int IsEmpty() | |
{ | |
return IsEmpty(GlobalState); | |
} | |
int IsEmpty(int idx) | |
{ | |
return IsEmpty(Captures[idx]); | |
} | |
int GetPop(int captureIdx) | |
{ | |
return GetPop(Captures[captureIdx]); | |
} | |
void Inverse(LifeState* state) | |
{ | |
for(int i = 0; i < N; i++) | |
{ | |
state->state[i] = ~(state->state[i]); | |
} | |
} | |
void ClearData(LifeState* state) | |
{ | |
int i; | |
for(i = 0; i < N; i++) | |
state->state[i] = 0; | |
state -> min = 0; | |
state -> max = N - 1; | |
state->gen = 0; | |
state->num_emitted = 0; | |
} | |
LifeState* NewState() | |
{ | |
LifeState* result = (LifeState*)(malloc(sizeof(LifeState))); | |
ClearData(result); | |
return result; | |
} | |
void FreeState(LifeState* state) | |
{ | |
free(state); | |
} | |
int AreEqual(LifeState* pat1, LifeState* pat2) | |
{ | |
for(int i = 0; i < N; i++) | |
if(pat1->state[i] != pat2->state[i]) | |
return NO; | |
return YES; | |
} | |
int AreEqual(LifeState* pat1) | |
{ | |
return AreEqual(GlobalState, pat1); | |
} | |
int AreEqual(int idx) | |
{ | |
return AreEqual(GlobalState, Captures[idx]); | |
} | |
int AreDisjoint(LifeState* main, LifeState* pat) | |
{ | |
int min = pat->min; | |
int max = pat->max; | |
uint64_t * patState = pat->state; | |
uint64_t * mainState = main->state; | |
for(int i = min; i <= max; i++) | |
if(((~mainState[i]) & patState[i]) != patState[i]) | |
return NO; | |
return YES; | |
} | |
int Contains(LifeState* main, LifeState* spark) | |
{ | |
int min = spark->min; | |
int max = spark->max; | |
uint64_t * mainState = main->state; | |
uint64_t * sparkState = spark->state; | |
for(int i = min; i <= max; i++) | |
if((mainState[i] & sparkState[i]) != (sparkState[i])) | |
return NO; | |
return YES; | |
} | |
int AreDisjoint(LifeState* main, LifeState* pat, int targetDx, int targetDy) | |
{ | |
int min = pat->min; | |
int max = pat->max; | |
uint64_t * patState = pat->state; | |
uint64_t * mainState = main->state; | |
int dy = (targetDy + 64) % 64; | |
for(int i = min; i <= max; i++) | |
{ | |
int curX = (N + i + targetDx) % N; | |
if(((~CirculateRight(mainState[curX], dy)) & patState[i]) != patState[i]) | |
return NO; | |
} | |
return YES; | |
} | |
int Contains(LifeState* main, LifeState* spark, int targetDx, int targetDy) | |
{ | |
int min = spark->min; | |
int max = spark->max; | |
uint64_t * mainState = main->state; | |
uint64_t * sparkState = spark->state; | |
int dy = (targetDy + 64) % 64; | |
for(int i = min; i <= max; i++) | |
{ | |
int curX = (N + i + targetDx) % N; | |
if((CirculateRight(mainState[curX], dy) & sparkState[i]) != (sparkState[i])) | |
return NO; | |
} | |
return YES; | |
} | |
int AllOn(LifeState* spark) | |
{ | |
return Contains(GlobalState, spark); | |
} | |
int AllOff(LifeState* spark) | |
{ | |
return AreDisjoint(GlobalState, spark); | |
} | |
void Reverse(uint64_t *state, int idxS, int idxE) | |
{ | |
for(int i = 0; idxS + i < idxE - i; i++) | |
{ | |
int l = idxS + i; | |
int r = idxE - i; | |
uint64_t temp = state[l]; | |
state[l] = state[r]; | |
state[r] = temp; | |
} | |
} | |
void CirculateUp(uint64_t *state, int anyk) | |
{ | |
int k = (anyk + 64 * 10) % 64; | |
Reverse(state, 0, N - 1); | |
Reverse(state, 0, k - 1); | |
Reverse(state, k, N - 1); | |
} | |
void Move(LifeState* state, int x, int y) | |
{ | |
for(int i = 0; i < N; i++) | |
{ | |
if(y < 0) | |
state->state[i] = CirculateRight(state->state[i], -y); | |
else | |
state->state[i] = CirculateRight(state->state[i], 64 - y); | |
} | |
if(x < 0) | |
CirculateUp(state->state, 64 + x); | |
else | |
CirculateUp(state->state, x); | |
state->min = 0; | |
state->max = N - 1; | |
} | |
void FlipX(LifeState* state) | |
{ | |
Reverse(state->state, 0, N - 1); | |
Move(state, 1, 0); | |
} | |
void FlipX() | |
{ | |
FlipX(GlobalState); | |
} | |
void FlipX(int idx) | |
{ | |
FlipX(Captures[idx]); | |
} | |
void Transform(LifeState* state, int dx, int dy, int dxx, int dxy, int dyx, int dyy) | |
{ | |
ClearData(Temp2); | |
ClearData(Temp1); | |
Copy(Temp1, state); | |
for(int i = 0; i < N; i++) | |
{ | |
for(int j = 0; j < 64; j++) | |
{ | |
int x = i - 32; | |
int y = j - 32; | |
int x1 = x * dxx + y * dxy; | |
int y1 = x * dyx + y * dyy; | |
int val = GetCell(Temp1, x1, y1); | |
SetCell(Temp2, x, y, val); | |
} | |
} | |
Move(Temp2, dx, dy); | |
Copy(state, Temp2); | |
RecalculateMinMax(state); | |
} | |
void Transform(LifeState* state, int dx, int dy) | |
{ | |
Move(state, dx, dy); | |
} | |
void GetBoundary(LifeState* state, LifeState* boundary) | |
{ | |
for(int i = 0; i < N; i++) { | |
uint64_t col = state->state[i]; | |
Temp->state[i] = col | CirculateLeft(col) | CirculateRight(col); | |
} | |
boundary->state[0] = Temp->state[N-1] | Temp->state[0] | Temp->state[1]; | |
for(int i = 1; i < N-1; i++) | |
boundary->state[i] = Temp->state[i-1] | Temp->state[i] | Temp->state[i+1]; | |
boundary->state[N-1] = Temp->state[N-2] | Temp->state[N-1] | Temp->state[0]; | |
for(int i = 0; i < N; i++) | |
boundary->state[i] &= ~(state->state[i]); | |
} | |
void GetBoundary(LifeState* state, int captureIdx) | |
{ | |
GetBoundary(state, Captures[captureIdx]); | |
} | |
void GetBoundary(LifeState* boundary) | |
{ | |
GetBoundary(GlobalState, boundary); | |
} | |
void GetBoundary(int captureIdx) | |
{ | |
GetBoundary(GlobalState, Captures[captureIdx]); | |
} | |
int Parse(LifeState* state, const char* rle, int starti) | |
{ | |
char ch; | |
int cnt, i, j; | |
int x, y; | |
x = 0; | |
y = 0; | |
cnt = 0; | |
ClearData(state); | |
i = starti; | |
while((ch = rle[i]) != '\0') | |
{ | |
if(ch >= '0' && ch <= '9') | |
{ | |
cnt *= 10; | |
cnt += (ch - '0'); | |
} | |
else if(ch == 'o') | |
{ | |
if(cnt == 0) | |
cnt = 1; | |
for(j = 0; j < cnt; j++) | |
{ | |
SetCell(state, x, y, 1); | |
x++; | |
} | |
cnt = 0; | |
} | |
else if(ch == 'b') | |
{ | |
if(cnt == 0) | |
cnt = 1; | |
x += cnt; | |
cnt = 0; | |
} | |
else if(ch == '$') | |
{ | |
if(cnt == 0) | |
cnt = 1; | |
if(cnt == 129) | |
return i + 1; | |
y += cnt; | |
x = 0; | |
cnt = 0; | |
} | |
else if(ch == '!') | |
{ | |
break; | |
} | |
else | |
{ | |
return -2; | |
} | |
i++; | |
} | |
state->min = 0; | |
state->max = N - 1; | |
return -1; | |
} | |
int Parse(LifeState* state, const char* rle, int dx, int dy) | |
{ | |
if(Parse(state, rle, 0) == -1) | |
{ | |
Move(state, dx, dy); | |
return SUCCESS; | |
} | |
else | |
{ | |
return FAIL; | |
} | |
} | |
int Parse(LifeState* state, const char* rle) | |
{ | |
return Parse(state, rle, 0, 0); | |
} | |
int Parse(LifeState* state, const char* rle, int dx, int dy, int dxx, int dxy, int dyx, int dyy) | |
{ | |
int result = Parse(state, rle); | |
if(result == SUCCESS) | |
Transform(state, dx, dy, dxx, dxy, dyx, dyy); | |
return result; | |
} | |
typedef struct | |
{ | |
LifeState* wanted; | |
LifeState* unwanted; | |
} LifeTarget; | |
LifeTarget* NewTarget(LifeState* wanted, LifeState* unwanted) | |
{ | |
LifeTarget* result = (LifeTarget*)(malloc(sizeof(LifeTarget))); | |
result->wanted = NewState(); | |
result->unwanted = NewState(); | |
Copy(result->wanted, wanted); | |
Copy(result->unwanted, unwanted); | |
RecalculateMinMax(result->wanted); | |
RecalculateMinMax(result->unwanted); | |
return result; | |
} | |
LifeTarget* NewTarget(LifeState* wanted) | |
{ | |
GetBoundary(wanted, Temp1); | |
return NewTarget(wanted, Temp1); | |
} | |
LifeTarget* NewTarget(const char* rle, int x, int y, int dxx, int dxy, int dyx, int dyy) | |
{ | |
int result = Parse(Temp2, rle, x, y, dxx, dxy, dyx, dyy); | |
if(result == SUCCESS) | |
{ | |
return NewTarget(Temp2); | |
} | |
return NULL; | |
} | |
LifeTarget* NewTarget(const char* rle, int x, int y) | |
{ | |
int result = Parse(Temp2, rle, x, y); | |
if(result == SUCCESS) | |
{ | |
return NewTarget(Temp2); | |
} | |
return NULL; | |
} | |
LifeTarget* NewTarget(const char* rle) | |
{ | |
return NewTarget(rle, 0, 0); | |
} | |
int Contains(LifeState* state, LifeTarget* target, int dx, int dy) | |
{ | |
if(Contains(state, target->wanted, dx, dy) == YES && AreDisjoint(state, target->unwanted, dx, dy) == YES) | |
return YES; | |
else | |
return NO; | |
} | |
int Contains(LifeState* state, LifeTarget* target) | |
{ | |
if(Contains(state, target->wanted) == YES && AreDisjoint(state, target->unwanted) == YES) | |
return YES; | |
else | |
return NO; | |
} | |
int Contains(LifeTarget* target) | |
{ | |
return Contains(GlobalState, target); | |
} | |
void FreeTarget(LifeTarget* iter) | |
{ | |
FreeState(iter -> wanted); | |
FreeState(iter -> unwanted); | |
free(iter); | |
} | |
typedef struct | |
{ | |
int* xList; | |
int* yList; | |
int len; | |
int allocated; | |
} Locator; | |
Locator* NewLocator() | |
{ | |
Locator* result = (Locator*)(malloc(sizeof(Locator))); | |
result->xList = (int*)(malloc(sizeof(int))); | |
result->yList = (int*)(malloc(sizeof(int))); | |
result->len = 0; | |
result->allocated = 1; | |
return result; | |
} | |
Locator* Realloc(Locator* locator) | |
{ | |
if(locator->allocated <= locator->len) | |
{ | |
locator->allocated *= 2; | |
locator->xList = (int*)(realloc(locator->xList, locator->allocated * sizeof(int))); | |
locator->yList = (int*)(realloc(locator->yList, locator->allocated * sizeof(int))); | |
} | |
return locator; | |
} | |
void Add(Locator* locator, int x, int y) | |
{ | |
Realloc(locator); | |
locator->xList[locator->len] = x; | |
locator->yList[locator->len] = y; | |
locator->len++; | |
} | |
Locator *State2Locator(LifeState* state) | |
{ | |
Locator* result = NewLocator(); | |
for(int j = 0; j < PrimeN; j++) | |
{ | |
for(int i = 0; i < PrimeN; i++) | |
{ | |
int x = (j * 35 + 17) % PrimeN; | |
int y = (i * 11 + 29) % PrimeN; | |
if(x >= N || y >= N) | |
continue; | |
int val = Get(x, y, state->state); | |
if(val == 1) | |
Add(result, x, y); | |
} | |
} | |
return result; | |
} | |
void ClearAtX(LifeState* state, Locator* locator, int x, uint64_t val) | |
{ | |
if(val == 0ULL) | |
return; | |
int len = locator->len; | |
int* xList = locator->xList; | |
int* yList = locator->yList; | |
for(int i = 0; i < len; i++) | |
{ | |
int idx = (x + xList[i] + N) % N; | |
int circulate = (yList[i] + 64) % 64; | |
state->state[idx] &= ~CirculateLeft(val, circulate); | |
} | |
} | |
uint64_t LocateAtX(LifeState* state, Locator* locator, int x, int negate) | |
{ | |
uint64_t result = ~0ULL; | |
int len = locator->len; | |
int* xList = locator->xList; | |
int* yList = locator->yList; | |
for(int i = 0; i < len; i++) | |
{ | |
int idx = (x + xList[i] + N) % N; | |
int circulate = (yList[i] + 64) % 64; | |
if(negate == NO) | |
result &= CirculateRight(state->state[idx], circulate); | |
else | |
result &= ~CirculateRight(state->state[idx],circulate); | |
if(result == 0ULL) | |
break; | |
} | |
return result; | |
} | |
uint64_t LocateAtX(LifeState* state, Locator* onLocator, Locator* offLocator, int x) | |
{ | |
uint64_t onLocate = LocateAtX(state, onLocator, x, NO); | |
if(onLocate == 0) | |
return 0; | |
return onLocate & LocateAtX(state, offLocator, x, YES); | |
} | |
void LocateInRange(LifeState* state, Locator* locator, LifeState* result, int minx, int maxx, int negate) | |
{ | |
for(int i = minx; i<= maxx; i++) | |
{ | |
result->state[i] = LocateAtX(state, locator, i, negate); | |
} | |
} | |
void LocateInRange(LifeState* state, Locator* onLocator, Locator* offLocator, LifeState* result, int minx, int maxx) | |
{ | |
for(int i = minx; i<= maxx; i++) | |
{ | |
result->state[i] = LocateAtX(state, onLocator, offLocator, i); | |
} | |
} | |
void Locate(LifeState* state, Locator* locator, LifeState* result) | |
{ | |
LocateInRange(state, locator, result, state->min, state->max, NO); | |
} | |
int ContainsLocator(LifeState* state, Locator* onLocator, Locator* offLocator, int minx, int maxx) | |
{ | |
for(int i = minx; i<= maxx; i++) | |
{ | |
if(LocateAtX(state, onLocator, offLocator, i) != 0) | |
return YES; | |
} | |
return NO; | |
} | |
typedef struct | |
{ | |
Locator* onLocator; | |
Locator* offLocator; | |
} TargetLocator; | |
TargetLocator* NewTargetLocator() | |
{ | |
TargetLocator* result = (TargetLocator*)(malloc(sizeof(TargetLocator))); | |
result->onLocator = NewLocator(); | |
result->offLocator = NewLocator(); | |
return result; | |
} | |
TargetLocator* Target2Locator(LifeTarget* target) | |
{ | |
TargetLocator* result = (TargetLocator*)(malloc(sizeof(TargetLocator))); | |
result->onLocator = State2Locator(target->wanted); | |
result->offLocator = State2Locator(target->unwanted); | |
return result; | |
} | |
TargetLocator* NewTargetLocator(LifeState* state) | |
{ | |
TargetLocator* result = Target2Locator(NewTarget(state)); | |
return result; | |
} | |
TargetLocator* NewTargetLocator(const char* rle) | |
{ | |
TargetLocator* result = Target2Locator(NewTarget(rle, -32, -32)); | |
return result; | |
} | |
TargetLocator* NewTargetLocator(const char* rle, int x, int y) | |
{ | |
TargetLocator* result = Target2Locator(NewTarget(rle, -32 + x, -32 + y)); | |
return result; | |
} | |
uint64_t LocateAtX(LifeState* state, TargetLocator* targetLocator, int x) | |
{ | |
return LocateAtX(state, targetLocator->onLocator, targetLocator->offLocator, x); | |
} | |
void LocateInRange(LifeState* state, TargetLocator* targetLocator, LifeState* result, int minx, int maxx) | |
{ | |
return LocateInRange(state, targetLocator->onLocator, targetLocator->offLocator, result, minx, maxx); | |
} | |
void LocateTarget(LifeState* state, TargetLocator* targetLocator, LifeState* result) | |
{ | |
LocateInRange(state, targetLocator, result, state->min, state->max); | |
} | |
void LocateTarget(TargetLocator* targetLocator, LifeState* result) | |
{ | |
LocateTarget(GlobalState, targetLocator, result); | |
} | |
int ContainsLocator(LifeState* state, TargetLocator* targetLocator) | |
{ | |
return ContainsLocator(state, targetLocator->onLocator, targetLocator->offLocator, state->min, state->max); | |
} | |
int ContainsLocator(TargetLocator* targetLocator) | |
{ | |
return ContainsLocator(GlobalState, targetLocator->onLocator, targetLocator->offLocator, GlobalState->min, GlobalState->max); | |
} | |
int ContainsLocator(TargetLocator* locs[], int n) | |
{ | |
for(int i = 0; i < n; i++) | |
if(ContainsLocator(locs[i]) == YES) | |
return YES; | |
return NO; | |
} | |
static TargetLocator* _glidersTarget[4]; | |
#pragma omp threadprivate(_glidersTarget) | |
int RemoveAtX(LifeState *state, int x, int startGiderIdx) | |
{ | |
int removed = NO; | |
for(int i = startGiderIdx; i < startGiderIdx + 2; i++) | |
{ | |
uint64_t gld = LocateAtX(state, _glidersTarget[i], x); | |
if(gld != 0) | |
{ | |
removed = YES; | |
ClearAtX(state, _glidersTarget[i]->onLocator, x, gld); | |
for(int j = 0; j < 64; j++) | |
{ | |
if(gld % 2 == 1) | |
{ | |
state->emittedGliders[state->num_emitted].x = x; | |
state->emittedGliders[state->num_emitted].y = j; | |
state->emittedGliders[state->num_emitted].gen = state->gen; | |
state->emittedGliders[state->num_emitted].dx = _gliders[i].dx; | |
state->emittedGliders[state->num_emitted].dy = _gliders[i].dy; | |
state->num_emitted++; | |
} | |
gld = gld >> 1; | |
if(gld == 0) | |
break; | |
} | |
} | |
} | |
return removed; | |
} | |
void RemoveGliders(LifeState *state) | |
{ | |
int removed = NO; | |
if(state->min <= 1) | |
if(RemoveAtX(state, 1, 0) == YES) | |
removed = YES; | |
if(state->max >= N - 2) | |
if(RemoveAtX(state, N - 2, 2) == YES) | |
removed = YES; | |
if(removed == YES) | |
RecalculateMinMax(state); | |
} | |
void inline Add(uint64_t& b1, uint64_t &b0, const uint64_t& val) | |
{ | |
b1 |= b0 & val; | |
b0 ^= val; | |
} | |
void inline Add_Init(uint64_t& b1, uint64_t& b0, const uint64_t& val) | |
{ | |
b1 = b0 & val; | |
b0 ^= val; | |
} | |
void inline Add(uint64_t& b2, uint64_t& b1, uint64_t &b0, const uint64_t& val) | |
{ | |
uint64_t t_b2 = b0 & val; | |
b2 |= t_b2 & b1; | |
b1 ^= t_b2; | |
b0 ^= val; | |
} | |
void inline Add_Init(uint64_t& b2, uint64_t& b1, uint64_t &b0, uint64_t& val) | |
{ | |
uint64_t t_b2 = b0 & val; | |
b2 = t_b2&b1; | |
b1 ^= t_b2; | |
b0 ^= val; | |
} | |
uint64_t inline Evolve(const uint64_t& temp, const uint64_t& bU0, const uint64_t& bU1, const uint64_t& bB0, const uint64_t& bB1) | |
{ | |
uint64_t sum0, sum1, sum2; | |
sum0 = CirculateLeft(temp); | |
Add_Init(sum1, sum0, CirculateRight(temp)); | |
Add(sum1, sum0, bU0); | |
Add_Init(sum2, sum1, bU1); | |
Add(sum2, sum1, sum0, bB0); | |
Add(sum2, sum1, bB1); | |
return ~sum2 & sum1 & (temp | sum0); | |
} | |
void IterateState(LifeState *lifstate) | |
{ | |
uint64_t* state = lifstate->state; | |
int min = lifstate->min; | |
int max = lifstate->max; | |
uint64_t bit0[N]; | |
uint64_t bit1[N]; | |
uint64_t tempState[N]; | |
for (int i = min; i <= max; i++) | |
{ | |
uint64_t l, r, temp; | |
temp = state[i]; | |
l = CirculateLeft(temp); | |
r = CirculateRight(temp); | |
bit0[i] = l ^ r ^ temp; | |
bit1[i] = ((l | r) & temp) | (l & r); | |
} | |
int start = min; | |
int last = max; | |
if (min == 0) | |
{ | |
tempState[0] = Evolve(state[0], 0, 0, bit0[1], bit1[1]); | |
start = 1; | |
} | |
if (max == N - 1) | |
{ | |
tempState[N - 1] = Evolve(state[N - 1], bit0[N - 2], bit1[N - 2], 0, 0); | |
last = N - 2; | |
} | |
for (int i = start; i <= last; i++) | |
tempState[i] = Evolve(state[i], bit0[i - 1], bit1[i - 1], bit0[i + 1], bit1[i + 1]); | |
int s = min + 1; | |
int e = max - 1; | |
if(s == 1) | |
s = 0; | |
if(e == N - 2) | |
e = N - 1; | |
for (int i = s; i <= e; i++) | |
{ | |
state[i] = tempState[i]; | |
} | |
RefitMinMax(lifstate); | |
lifstate->gen++; | |
} | |
LifeState* NewState(const char* rle, int dx, int dy, int dxx, int dxy, int dyx, int dyy) | |
{ | |
LifeState* result = NewState(); | |
Parse(result, rle); | |
Transform(result, dx, dy, dxx, dxy, dyx, dyy); | |
return result; | |
} | |
LifeState* NewState(const char* rle, int dx, int dy) | |
{ | |
LifeState* result = NewState(); | |
Parse(result, rle, dx, dy); | |
return result; | |
} | |
LifeState* NewState(const char* rle) | |
{ | |
return NewState(rle, 0, 0); | |
} | |
const char* GetRLE(LifeState *state) | |
{ | |
Clear(TempString); | |
int eol_count = 0; | |
for(int j = 0; j < N; j++) | |
{ | |
int last_val = -1; | |
int run_count = 0; | |
for(int i = 0; i < N; i++) | |
{ | |
int val = Get(i, j, state->state); | |
// Flush linefeeds if we find a live cell | |
if(val == 1 && eol_count > 0) | |
{ | |
if(eol_count > 1) | |
Append(TempString, eol_count); | |
Append(TempString, "$"); | |
eol_count = 0; | |
} | |
// Flush current run if val changes | |
if (val == 1 - last_val) | |
{ | |
if(run_count > 1) | |
Append(TempString, run_count); | |
Append(TempString, last_val ? "o" : "b"); | |
run_count = 0; | |
} | |
run_count++; | |
last_val = val; | |
} | |
// Flush run of live cells at end of line | |
if (last_val == 1) | |
{ | |
if(run_count > 1) | |
Append(TempString, run_count); | |
Append(TempString, "o"); | |
run_count = 0; | |
} | |
eol_count++; | |
} | |
return TempString->value; | |
} | |
void PrintRLE(LifeState *state) | |
{ | |
printf("\nx = 0, y = 0, rule = B3/S23\n%s!\n\n", GetRLE(state)); | |
} | |
void Print() | |
{ | |
Print(GlobalState); | |
} | |
void Print(int idx) | |
{ | |
Print(Captures[idx]); | |
} | |
void PrintRLE() | |
{ | |
PrintRLE(GlobalState); | |
} | |
void PrintRLE(int idx) | |
{ | |
PrintRLE(Captures[idx]); | |
} | |
void Evolve(LifeState* state, int numIters) | |
{ | |
for(int i = 0; i < numIters; i++) | |
{ | |
IterateState(state); | |
RemoveGliders(state); | |
} | |
} | |
void Evolve(LifeState* after, LifeState* before, int numIters) | |
{ | |
Copy(after, before); | |
Evolve(after, numIters); | |
} | |
namespace PRNG { | |
//Public domain PRNG by Sebastian Vigna 2014, see http://xorshift.di.unimi.it | |
uint64_t s[16] = { 0x12345678 }; | |
int p = 0; | |
uint64_t rand64() { | |
uint64_t s0 = s[ p ]; | |
uint64_t s1 = s[ p = ( p + 1 ) & 15 ]; | |
s1 ^= s1 << 31; // a | |
s1 ^= s1 >> 11; // b | |
s0 ^= s0 >> 30; // c | |
return ( s[ p ] = s0 ^ s1 ) * 1181783497276652981ULL; | |
} | |
} | |
void RandomState(LifeState* state) { | |
for (int i = 0; i < N; i++) | |
state->state[i] = PRNG::rand64(); | |
RecalculateMinMax(state); | |
} | |
void RandomState() { | |
RandomState(GlobalState); | |
} | |
void New() | |
{ | |
if(GlobalState == NULL) | |
{ | |
GlobalState = NewState(); | |
Temp = NewState(); | |
Temp1 = NewState(); | |
Temp2 = NewState(); | |
for(int i = 0; i < CAPTURE_COUNT; i++) | |
{ | |
Captures[i] = NewState(); | |
} | |
_glidersTarget[0] = NewTargetLocator("2o$obo$o!"); | |
_glidersTarget[1] = NewTargetLocator("o$obo$2o!"); | |
_glidersTarget[2] = NewTargetLocator("b2o$obo$2bo!", -2, 0); | |
_glidersTarget[3] = NewTargetLocator("2bo$obo$b2o!", -2, 0); | |
_gliders[0].dx = -1; | |
_gliders[0].dy = -1; | |
_gliders[1].dx = -1; | |
_gliders[1].dy = 1; | |
_gliders[2].dx = 1; | |
_gliders[2].dy = 1; | |
_gliders[3].dx = 1; | |
_gliders[3].dy = -1; | |
} | |
else | |
{ | |
ClearData(GlobalState); | |
} | |
} | |
void Capture(LifeState* cap, int idx) | |
{ | |
Copy(Captures[idx], cap); | |
} | |
void Capture(int idx) | |
{ | |
Copy(Captures[idx], GlobalState); | |
} | |
void Run(int numIter) | |
{ | |
Evolve(GlobalState, numIter); | |
} | |
void Join(LifeState* main, LifeState* delta) | |
{ | |
Copy(main, delta , OR); | |
} | |
void Join(LifeState* main, LifeState* delta, int dx, int dy) | |
{ | |
for(int i = delta->min; i <= delta->max; i++) | |
{ | |
int idx = (i + dx + N) % N; | |
if(dy < 0) | |
main->state[idx] |= CirculateRight(delta->state[i], -dy); | |
else | |
main->state[idx] |= CirculateRight(delta->state[i], 64 -dy); | |
} | |
main->min = 0; | |
main->max = N - 1; | |
} | |
void PutState(LifeState* state) | |
{ | |
Join(GlobalState, state); | |
} | |
void PutState(LifeState* state, int dx, int dy) | |
{ | |
Join(GlobalState, state, dx, dy); | |
} | |
void PutState(int idx) | |
{ | |
PutState(Captures[idx]); | |
} | |
void PutState(LifeState* state, int dx, int dy, int dxx, int dxy, int dyx, int dyy) | |
{ | |
ClearData(Temp); | |
Copy(Temp, state); | |
Transform(Temp, dx, dy, dxx, dxy, dyx, dyy); | |
PutState(Temp); | |
} | |
void PutState(LifeState* state, CopyType op) | |
{ | |
Copy(GlobalState, state, op); | |
} | |
int PutState(const char* rle) | |
{ | |
ClearData(Temp); | |
int result = Parse(Temp, rle); | |
if( result == SUCCESS) | |
PutState(Temp); | |
return result; | |
} | |
int PutState(const char* rle, int x, int y) | |
{ | |
ClearData(Temp); | |
int result = Parse(Temp, rle, x, y); | |
if( result == SUCCESS) | |
PutState(Temp); | |
return result; | |
} | |
int PutState(const char* rle, int dx, int dy, int dxx, int dxy, int dyx, int dyy) | |
{ | |
ClearData(Temp); | |
int result = Parse(Temp, rle); | |
if( result == SUCCESS) | |
{ | |
Transform(Temp, dx, dy, dxx, dxy, dyx, dyy); | |
PutState(Temp); | |
} | |
return result; | |
} | |
typedef struct | |
{ | |
int x; | |
int y; | |
int w; | |
int h; | |
int s; | |
LifeState* States[MAX_ITERATIONS]; | |
int curx; | |
int cury; | |
int curs; | |
} LifeIterator; | |
LifeIterator* NewIterator(LifeState* state, int x, int y, int w, int h, int s, EvolveType op) | |
{ | |
LifeIterator* result = (LifeIterator*)(malloc(sizeof(LifeIterator))); | |
result -> x = x; | |
result -> y = y; | |
result -> w = w; | |
result -> h = h; | |
result -> s = s; | |
result -> curx = x; | |
result -> cury = y; | |
result -> curs = 0; | |
state -> min = 0; | |
state -> max = N - 1; | |
ClearData(Temp); | |
Copy(Temp, state); | |
for(int i = 0; i < s; i++) | |
{ | |
result->States[i] = NewState(); | |
Copy(result->States[i], Temp); | |
if(op == EVOLVE) | |
Evolve(Temp, 1); | |
} | |
return result; | |
} | |
LifeIterator* NewIterator(LifeState* states[], int x, int y, int w, int h, int s) | |
{ | |
LifeIterator* result = NewIterator(states[0], x, y, w, h, s, LEAVE); | |
for(int i = 0; i < s; i++) | |
{ | |
result->States[i] = NewState(); | |
Copy(result->States[i], states[i]); | |
} | |
return result; | |
} | |
LifeIterator* NewIterator(LifeState* state, int x, int y, int w, int h, int s) | |
{ | |
return NewIterator(state, x, y, w, h, s, EVOLVE); | |
} | |
LifeIterator* NewIterator(LifeState* state, int x, int y, int w, int h) | |
{ | |
return NewIterator(state, x, y, w, h, 1, LEAVE); | |
} | |
LifeIterator* NewIterator(const char* rle, int x, int y, int w, int h, int s) | |
{ | |
LifeState* state = NewState(rle); | |
return NewIterator(state, x, y, w, h, s, EVOLVE); | |
} | |
LifeIterator* NewIterator(const char* rle, int x, int y, int w, int h) | |
{ | |
LifeState* state = NewState(rle); | |
return NewIterator(state, x, y, w, h); | |
} | |
LifeIterator* NewIterator(int x, int y, int w, int h) | |
{ | |
ClearData(Temp); | |
return NewIterator(Temp, x, y, w, h, 1); | |
} | |
void Print(LifeIterator* iter) | |
{ | |
printf("\n(%d, %d, %d)", iter->curx, iter->cury, iter->curs); | |
} | |
void Print(LifeIterator* iter[], int numIters) | |
{ | |
for(int i = 0; i < numIters; i++) | |
Print(iter[i]); | |
} | |
void Print(LifeIterator* iter, const char* name) | |
{ | |
printf("\nSetCurrent(%s, %d, %d, %d);", name, iter->curx, iter->cury, iter->curs); | |
} | |
void Reset(LifeIterator* iter) | |
{ | |
iter -> curx = iter -> x; | |
iter -> cury = iter -> y; | |
iter -> curs = 0; | |
} | |
int Next(LifeIterator* iter) | |
{ | |
(iter -> curs)++; | |
if((iter -> curs) < (iter->s)) | |
return SUCCESS; | |
(iter -> curs) = 0; | |
(iter -> curx)++; | |
if((iter -> curx) < (iter->x) + (iter->w)) | |
return SUCCESS; | |
iter -> curx = iter->x; | |
(iter -> cury)++; | |
if((iter -> cury) < (iter->y) + (iter->h)) | |
return SUCCESS; | |
Reset(iter); | |
return FAIL; | |
} | |
int Next(LifeIterator *iter1[], int numIters, int toPrint) | |
{ | |
for(int i = 0; i < numIters; i++) | |
{ | |
if(toPrint == YES) | |
{ | |
if(i == numIters - 1) | |
Print(iter1[i]); | |
} | |
if(Next(iter1[i]) == SUCCESS) | |
return SUCCESS; | |
} | |
return FAIL; | |
} | |
int Next(LifeIterator *iter1, LifeIterator *iter2, int toPrint) | |
{ | |
LifeIterator *iters[] = {iter1, iter2}; | |
return Next(iters, 2, toPrint); | |
} | |
int Next(LifeIterator *iter1, LifeIterator *iter2) | |
{ | |
return Next(iter1, iter2, YES); | |
} | |
int Next(LifeIterator *iter1, LifeIterator *iter2, LifeIterator *iter3, int toPrint) | |
{ | |
LifeIterator *iters[] = {iter1, iter2, iter3}; | |
return Next(iters, 3, toPrint); | |
} | |
int Next(LifeIterator *iter1, LifeIterator *iter2, LifeIterator *iter3) | |
{ | |
return Next(iter1, iter2, iter3, YES); | |
} | |
int Next(LifeIterator *iter1, LifeIterator *iter2, LifeIterator *iter3, LifeIterator *iter4, int toPrint) | |
{ | |
LifeIterator *iters[] = {iter1, iter2, iter3, iter4}; | |
return Next(iters, 4, toPrint); | |
} | |
int Next(LifeIterator *iter1, LifeIterator *iter2, LifeIterator *iter3, LifeIterator *iter4) | |
{ | |
return Next(iter1, iter2, iter3, iter4, YES); | |
} | |
int Next(LifeIterator *iter1, LifeIterator *iter2, LifeIterator *iter3, LifeIterator *iter4, LifeIterator *iter5, int toPrint) | |
{ | |
LifeIterator *iters[] = {iter1, iter2, iter3, iter4, iter5}; | |
return Next(iters, 5, toPrint); | |
} | |
int Next(LifeIterator *iter1, LifeIterator *iter2, LifeIterator *iter3, LifeIterator *iter4, LifeIterator *iter5) | |
{ | |
return Next(iter1, iter2, iter3, iter4, iter5, YES); | |
} | |
int Next(LifeIterator *iter1, LifeIterator *iter2, LifeIterator *iter3, LifeIterator *iter4, LifeIterator *iter5, LifeIterator *iter6, int toPrint) | |
{ | |
LifeIterator *iters[] = {iter1, iter2, iter3, iter4, iter5, iter6}; | |
return Next(iters, 6, toPrint); | |
} | |
int Next(LifeIterator *iter1, LifeIterator *iter2, LifeIterator *iter3, LifeIterator *iter4, LifeIterator *iter5, LifeIterator *iter6) | |
{ | |
return Next(iter1, iter2, iter3, iter4, iter5, iter6, YES); | |
} | |
int Next(LifeIterator *iter1[], int numIters) | |
{ | |
return Next(iter1, numIters, YES); | |
} | |
void FreeIterator(LifeIterator* iter) | |
{ | |
for(int i = 0; i < iter->s; i++) | |
FreeState(iter->States[i]); | |
free(iter); | |
} | |
void Join(LifeState* state, LifeIterator* iter) | |
{ | |
Join(state, iter->States[iter -> curs], iter->curx, iter->cury); | |
} | |
void PutState(LifeIterator* iter) | |
{ | |
Join(GlobalState, iter->States[iter -> curs], iter->curx, iter->cury); | |
} | |
void SetCurrent(LifeIterator* iter, int curx, int cury, int curs) | |
{ | |
iter -> curx = curx; | |
iter -> cury = cury; | |
iter -> curs = curs; | |
} | |
int Validate(LifeIterator *iter1, LifeIterator *iter2) | |
{ | |
if(iter1->curx > iter2->curx) | |
return SUCCESS; | |
if(iter1->curx < iter2->curx) | |
return FAIL; | |
if(iter1->cury > iter2->cury) | |
return SUCCESS; | |
if(iter1->cury < iter2->cury) | |
return FAIL; | |
if(iter1->curs > iter2->curs) | |
return SUCCESS; | |
return FAIL; | |
} | |
int Validate(LifeIterator *iter1, LifeIterator *iter2, LifeIterator *iter3) | |
{ | |
if(Validate(iter1, iter2) == FAIL) | |
return FAIL; | |
if(Validate(iter2, iter3) == FAIL) | |
return FAIL; | |
return SUCCESS; | |
} | |
int Validate(LifeIterator *iters[], int iterCount) | |
{ | |
for(int i = 0; i < iterCount - 1; i++) | |
if(Validate(iters[i], iters[i + 1]) == FAIL) | |
return FAIL; | |
return SUCCESS; | |
} | |
typedef struct | |
{ | |
LifeState** results; | |
int size; | |
int allocated; | |
} LifeResults; | |
LifeResults* NewResults() | |
{ | |
LifeResults* result = (LifeResults*)(malloc(sizeof(LifeResults))); | |
result->results = (LifeState**)(malloc(10 * sizeof(LifeState*))); | |
for(int i = 0; i < 10; i++) | |
{ | |
(result->results)[i] = NewState(); | |
} | |
result->allocated = 10; | |
result->size = 0; | |
return result; | |
} | |
void Add(LifeResults* results, LifeState* state) | |
{ | |
if(results->size == results->allocated) | |
{ | |
results->results = (LifeState**)(realloc(results->results, results->allocated * 2 * sizeof(LifeState*))); | |
results->allocated *= 2; | |
for(int i = results->size; i < 2 * (results->size); i++) | |
{ | |
(results->results)[i] = NewState(); | |
} | |
} | |
Copy((results->results)[results->size], state); | |
results->size++; | |
} | |
void Add(LifeResults* results) | |
{ | |
Add(results, GlobalState); | |
} | |
char* ReadFile(const char *filePath) | |
{ | |
char* buffer = (char*) malloc(1); | |
buffer[0] = '\0'; | |
long length; | |
FILE * f = fopen (filePath, "r"); | |
if (f) | |
{ | |
fseek (f, 0, SEEK_END); | |
length = ftell (f); | |
fseek (f, 0, SEEK_SET); | |
buffer = (char*)realloc (buffer, length); | |
if (buffer) | |
{ | |
fread(buffer, 1, length, f); | |
} | |
fclose (f); | |
} | |
return buffer; | |
} | |
void SaveResults(LifeResults* results, const char* filePath) | |
{ | |
FILE *f; | |
f = fopen(filePath, "wb"); | |
for(int i = 0; i < results->size; i++) | |
{ | |
fputs(GetRLE((results->results)[i]), f); | |
fprintf(f, "129$"); | |
} | |
fclose(f); | |
} | |
LifeResults* LoadResults(const char* filePath) | |
{ | |
LifeResults* results = NewResults(); | |
char* rle = ReadFile(filePath); | |
int idx = 0; | |
while(rle[idx] != '\0') | |
{ | |
ClearData(Temp); | |
idx = Parse(Temp, rle, idx); | |
Move(Temp, -32, -32); | |
Add(results, Temp); | |
} | |
free(rle); | |
return results; | |
} | |
typedef struct | |
{ | |
int minx; | |
int maxx; | |
uint64_t minVal; | |
uint64_t maxVal; | |
} LifeBox; | |
LifeBox* NewBox() | |
{ | |
LifeBox* result = (LifeBox*)(malloc(sizeof(LifeBox))); | |
result->minx = 0; | |
result->maxx = 0; | |
result->minVal = 1ULL; | |
result->maxVal = 1ULL; | |
return result; | |
} | |
LifeBox* NewBox(int minx, int miny, int maxx, int maxy) | |
{ | |
LifeBox* result = (LifeBox*)(malloc(sizeof(LifeBox))); | |
result->minx = minx + 32; | |
result->maxx = maxx + 32; | |
result->minVal = 1ULL << (miny + 32); | |
result->maxVal = 1ULL << (maxy + 32); | |
return result; | |
} | |
int StateWidth(LifeState* state) | |
{ | |
RefitMinMax(state); | |
return state->max - state->min + 1; | |
} | |
int BoxWidth(LifeBox* box) | |
{ | |
return box->maxx - box->minx + 1; | |
} | |
int BoxX(LifeBox* box) | |
{ | |
return box->minx; | |
} | |
int BoxY(LifeBox* box) | |
{ | |
uint64_t tmp = 1ULL; | |
for(int i = 0; i < N; i++) | |
{ | |
if(tmp == box->minVal) | |
return i; | |
tmp <<= 1; | |
} | |
} | |
int BoxHeight(LifeBox* box) | |
{ | |
int miny; | |
uint64_t tmp = 1ULL; | |
for(int i = 0; i <= N; i++) | |
{ | |
if(tmp == box->minVal) | |
miny = i; | |
if(tmp == box->maxVal) | |
{ | |
return i - miny + 1; | |
} | |
tmp <<= 1; | |
} | |
return -1; | |
} | |
int IsInside(LifeState* state, LifeBox* box) | |
{ | |
for(int i = state->min; i <= state->max; i++) | |
{ | |
uint64_t curVal = state->state[i]; | |
if(curVal == 0) | |
continue; | |
if(curVal > box->maxVal || curVal < box->minVal) | |
return NO; | |
if(i < box->minx) | |
return NO; | |
if(i > box->maxx) | |
return NO; | |
} | |
return YES; | |
} | |
int GetBoundingBox(LifeState* state, LifeBox* box) | |
{ | |
if(IsEmpty(state)) | |
return FAIL; | |
RefitMinMax(state); | |
uint64_t or_all = 0LL; | |
for(int i = state->min; i <= state->max; i++) | |
{ | |
or_all |= state->state[i]; | |
} | |
if(state->min == 0) | |
{ | |
if(state->state[0] != 0) | |
box->minx = 0; | |
else if(state->state[1] != 0) | |
box->minx = 1; | |
} | |
else | |
{ | |
box->minx = state->min + 2; | |
} | |
if(state->max == N - 1) | |
{ | |
if(state->state[N - 1] != 0) | |
box->maxx = N - 1; | |
else if(state->state[N - 2] != 0) | |
box->maxx = N - 2; | |
} | |
else | |
{ | |
box->maxx = state->max - 2; | |
} | |
box->minVal = 1ULL; | |
box->maxVal = 1ULL << 63; | |
//example 0011001000 | |
//get 0000001000, 0010000000 | |
while( (box->minVal & or_all) == 0) | |
box->minVal <<= 1; | |
while( (box->maxVal & or_all) == 0) | |
box->maxVal >>= 1; | |
return SUCCESS; | |
} | |
int IsInside(LifeBox* box) | |
{ | |
return IsInside(GlobalState, box); | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment