Skip to content

Instantly share code, notes, and snippets.

@Rogerup

Rogerup/life.cpp

Last active April 14, 2023 12:45
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save Rogerup/0c37c4f2535ec2de10a606a33e724bf1 to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save Rogerup/0c37c4f2535ec2de10a606a33e724bf1 to your computer and use it in GitHub Desktop.
Download ZIP
Raw
life.cpp
#include <bits/stdc++.h> // Compile: g++ -O3 -march=native -fomit-frame-pointer life.cpp -o life.exe
using namespace std;
#define MAX_SIZE (2558 + 2) // 2558 + walls in each edge
#define DSTEP 1024
#define PARENT_SIZE (DSTEP/4 * (ly+2) * (lx+2))
#define parents(step, y, x) parents[(step)*(ly+2)*(lx+2) + (y)*(lx+2) + (x)]
int dchr[4] = { 'D', 'R', 'U', 'L' }; // Down, Right, Up, Left
int dys[4] = { 1, 0, -1, 0 };
int dxs[4] = { 0, 1, 0, -1 };
int maze0[MAX_SIZE][MAX_SIZE], maze1[MAX_SIZE][MAX_SIZE];
int (*maze)[MAX_SIZE] = maze0, (*mazeb)[MAX_SIZE] = maze1;
int ly, lx;
void parent_file(uint8_t *parents, int step, const char *rw) {
if (step % DSTEP == DSTEP-1) {
char fn[64]; sprintf(fn, "parent%d.bin", step / DSTEP);
FILE *fp = fopen(fn, rw);
if (rw[0] == 'r')
fread(parents, PARENT_SIZE, 1, fp);
else
fwrite(parents, PARENT_SIZE, 1, fp);
fclose(fp);
}
}
void trace_path(int step, uint8_t *parents) {
char s_out[50016 * 2];
int y = ly, x = lx, nsteps = step;
memset(s_out, ' ', sizeof(s_out));
s_out[step * 2 - 1] = '\0';
while (step > 0) {
parent_file(parents, step, "rb");
int step_pos = (step / 4) % (DSTEP / 4);
int step_sht = (step % 4) * 2;
int d = (parents(step_pos, y, x) >> step_sht) & 0x03;
s_out[--step * 2] = dchr[d];
y -= dys[d]; x-= dxs[d];
}
printf("\r%d x %d \n%d steps \n%s\n", ly, lx, nsteps, s_out);
}
int count_green(int y, int x) {
int cnt = -(maze[y][x] == 1); // Removes central value
for(int y2=y-1; y2<y+2; y2++)
for(int x2=x-1; x2<x+2; x2++)
cnt += (maze[y2][x2] == 1);
return cnt;
}
void set_color(int y, int x) {
int g = count_green(y, x);
if ((maze[y][x] != 1 && g > 1 && g < 5) || (maze[y][x] == 1 && g > 3 && g < 6)) // B234/S45
mazeb[y][x] = 1;
else
mazeb[y][x] = 0;
}
void maze_chg_st() {
for(int y=1; y<=ly; y++)
for(int x=1; x<=lx; x++)
set_color(y, x);
mazeb[1][1] = 0; mazeb[ly][lx] = 0;
swap(maze, mazeb);
}
void bfs() {
int step = 0;
int *listN = (int *) malloc(MAX_SIZE*MAX_SIZE), listN_c = 1; listN[0] = 0x10001;
int *listO = (int *) malloc(MAX_SIZE*MAX_SIZE), listO_c;
uint8_t *parents = (uint8_t *) malloc(PARENT_SIZE);
while (listN_c > 0) {
maze_chg_st();
parent_file(parents, step++, "wb");
if(step%100 == 0)
printf("\r%d steps ", step);
int step_pos = (step / 4) % (DSTEP / 4);
int step_sht = (step % 4) * 2; // 2 bits for direction (0 - 3)
uint8_t step_msk = ~(0x03 << step_sht);
swap(listO, listN);
listO_c = listN_c; listN_c = 0;
for (int p=0; p<listO_c; p++) {
int y = listO[p] / 0x10000, x = listO[p] & 0xFFFF;
for(int d=0; d<4; d++) {
int yd = y + dys[d], xd = x + dxs[d];
if (!maze[yd][xd]) {
maze[yd][xd] = 9;
listN[listN_c++] = yd * 0x10000 + xd;
parents(step_pos, yd, xd) &= step_msk;
parents(step_pos, yd, xd) |= (d << step_sht);
}
}
}
if (maze[ly][lx]) break;
}
if (listN_c > 0)
trace_path(step, parents);
else
printf("\nFailed to find the Destination\n");
free(listN); free(listO); free(parents);
}
int main(int argc, char **argv)
{
memset(maze0, 9, sizeof(maze0)); memset(maze1, 9, sizeof(maze1));
FILE *fp = fopen(argv[1], "r");
ly = 0;
for(char line[8192]; fgets(line, sizeof(line), fp);) {
ly++; lx = 0;
for(int p=0, c=0; sscanf(&line[p], "%c", (char*)&c) == 1; p++)
if (c >= '0')
maze[ly][++lx] = c - '0';
}
fclose(fp);
bfs();
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment