Skip to content

Instantly share code, notes, and snippets.

@maksverver

maksverver/planet-explore.c

Forked from skeeto/planet-explore.c
Last active August 21, 2016 00:22
Show Gist options
  • Save maksverver/d496598e7e7c24f737d48d8f381fd065 to your computer and use it in GitHub Desktop.
Save maksverver/d496598e7e7c24f737d48d8f381fd065 to your computer and use it in GitHub Desktop.
Download ZIP
Planet exploration solver
Raw
planet-explore.c
/* 1) Immediately prints the base puzzle SVG to stdout.
* 2) Creates a path-*.svg each * time it hits a longest path.
* 3) Creates a solution-*.svg for each solution.
*/
#include <stdio.h>
#include <stdint.h>
#include <stdbool.h>
#define WIDTH 8u
#define HEIGHT 8u
#define KEY_BLUE 0x00000001
#define KEY_RED 0x00000002
#define KEY_GREEN 0x00000004
#define KEY_CYAN 0x00000008
#define KEY_PURPLE 0x00000010
#define KEY_ORANGE 0x00000020
#define ZONE_BLUE 0x00000100
#define ZONE_RED 0x00000200
#define ZONE_GREEN 0x00000400
#define ZONE_CYAN 0x00000800
#define ZONE_PURPLE 0x00001000
#define ZONE_ORANGE 0x00002000
#define N 0x00010000
#define S 0x00020000
#define E 0x00040000
#define W 0x00080000
#define NE 0x00100000
#define NW 0x00200000
#define SE 0x00400000
#define SW 0x00800000
#define STEP_TWICE 0x01000000
#define KEY_MASK 0x0000003f
#define ZONE_MASK 0x00003f00
#define has_key(v) !!(v & KEY_MASK)
#define has_zone(v) !!(v & ZONE_MASK)
#define can_pass(v, keys) (!(v & ZONE_MASK) || (((v) >> 8) & (keys)))
static const uint32_t map[HEIGHT][WIDTH] = {
{ /* row 1 */
E | S | SE,
E | SE | S | SW | W,
E | S | SW | W,
E | SE | S | W,
E | SE | S | SW | W | KEY_ORANGE,
S | SW | W,
E | S | ZONE_CYAN,
S | SW | W | ZONE_CYAN,
},
{ /* row 2 */
N | NE | E | SE | S | ZONE_BLUE,
N | NE | E | SE | SW | W | NW,
N | S | SW | W | NW,
N | NE | E,
N | NE | E | W | NW,
N | SE | W | NW,
N | NE | E | SE | S,
N | S | SW | W,
},
{ /* row 3 */
N | SE | E | SE | S | ZONE_BLUE,
NE | E | SE | S | SW | W | NW,
N | E | S | SW | W | NW,
E | SE | S | W | KEY_GREEN,
N | E | SE | S | SW | W | STEP_TWICE,
S | SW | W,
N | NE | E | SE | S | NW | STEP_TWICE,
N | S | SW | W | NW | KEY_CYAN,
},
{ /* row 4 */
N | NE | E | S | ZONE_BLUE,
N | NE | E | W | NW | KEY_BLUE,
N | SE | W | NW,
N | NE | E | SE | S | SW,
N | NE | E | SE | SW | W | NW | ZONE_PURPLE,
N | S | SW | W | NW,
N | NE | S,
N | NW,
},
{ /* row 5 */
N | E | SE | S,
E | S | SW | W,
NE | E | SE | S | W,
N | NE | E | SE | SW | W | NW,
NE | E | SW | S | W | NW,
N | S | SW | W | NW,
N | E | SE | S,
S | SW | W,
},
{ /* row 6 */
N | NE | E | SE | S | ZONE_RED,
N | S | SW | W | NW,
N | NE | S | ZONE_GREEN,
E | SE | NW,
N | NE | E | SE | S | SW | W | NW,
N | S | SW | W | NW,
N | NE | SE,
N | S | SW | NW,
},
{ /* row 7 */
N | NE | E | SE | S,
N | S | SW | W | NW | ZONE_RED,
N | S | ZONE_GREEN,
NE | SE | S,
N | NE | E | SE | S | SW | NW,
N | S | SW | W | NW,
NE | E | SE | S,
N | S | SW | W | NW,
},
{
/* row 8 */
N | NE | E | ZONE_RED,
N | E | W | NW | KEY_RED,
N | E | W | ZONE_GREEN,
N | NE | E | W | ZONE_GREEN,
N | NW | E | W | NW | ZONE_GREEN,
N | W | NW | KEY_PURPLE,
N | NE,
N | NW| ZONE_ORANGE,
},
};
static const struct {
uint32_t flag;
int dx;
int dy;
} dir[] = {
{N, 0, -1},
{S, 0, 1},
{E, 1, 0},
{W, -1, 0},
{NE, 1, -1},
{NW, -1, -1},
{SE, 1, 1},
{SW, -1, 1},
};
static void
line(FILE *o, float x1, float y1, float x2, float y2, float width, const char *c)
{
fprintf(o, "<line x1='%.3g' y1='%.3g' x2='%.3g' y2='%.3g' "
"stroke='%s' stroke-width='%.3g' stroke-linecap='round'/>\n",
x1, y1, x2, y2, c, width);
}
static const char *
get_color(uint32_t v) {
static const char *colors[] = {
"blue", "red", "green", "#0af", "purple", "#d70", "black", "black"
};
unsigned count = 0;
for (; !(v & 1); v >>= 1, count++);
return colors[count % 8];
}
static void
render_start(FILE *o, float scale)
{
float stroke_width = 0.05f;
float main_radius = 0.3f;
float zone_radius = 0.23f;
float key_radius = 0.15f;
fprintf(o, "<?xml version='1.0' encoding='UTF-8'?>\n");
fprintf(o, "<svg xmlns='http://www.w3.org/2000/svg' version='1.1' "
"width='%.3g' height='%.3g'>\n", WIDTH * scale, HEIGHT * scale);
for (unsigned y = 0; y < HEIGHT; y++) {
for (unsigned x = 0; x < WIDTH; x++) {
uint32_t v = map[y][x];
float x1 = (x + 0.5f) * scale;
float y1 = (y + 0.5f) * scale;
const char *c = "black";
if (N & v) {
float x2 = (x + 0.5f) * scale;
float y2 = (y - 1 + 0.5f) * scale;
line(o, x1, y1, x2, y2, stroke_width * scale, c);
}
if (S & v) {
float x2 = (x + 0.5f) * scale;
float y2 = (y + 1 + 0.5f) * scale;
line(o, x1, y1, x2, y2, stroke_width * scale, c);
}
if (E & v) {
float x2 = (x + 1 + 0.5f) * scale;
float y2 = (y + 0.5f) * scale;
line(o, x1, y1, x2, y2, stroke_width * scale, c);
}
if (W & v) {
float x2 = (x - 1 + 0.5f) * scale;
float y2 = (y + 0.5f) * scale;
line(o, x1, y1, x2, y2, stroke_width * scale, c);
}
if (NE & v) {
float x2 = (x + 1 + 0.5f) * scale;
float y2 = (y - 1 + 0.5f) * scale;
line(o, x1, y1, x2, y2, stroke_width * scale, c);
}
if (SE & v) {
float x2 = (x + 1 + 0.5f) * scale;
float y2 = (y + 1 + 0.5f) * scale;
line(o, x1, y1, x2, y2, stroke_width * scale, c);
}
if (NW & v) {
float x2 = (x - 1 + 0.5f) * scale;
float y2 = (y - 1 + 0.5f) * scale;
line(o, x1, y1, x2, y2, stroke_width * scale, c);
}
if (SW & v) {
float x2 = (x - 1 + 0.5f) * scale;
float y2 = (y + 1 + 0.5f) * scale;
line(o, x1, y1, x2, y2, stroke_width * scale, c);
}
}
}
for (unsigned y = 0; y < HEIGHT; y++) {
for (unsigned x = 0; x < WIDTH; x++) {
float cx = (x + 0.5f) * scale;
float cy = (y + 0.5f) * scale;
fprintf(o, "<circle cx='%.3g' cy='%.3g' r='%.3g' "
"stroke='black' stroke-width='%.3g' fill='white'/>\n",
cx, cy, main_radius * scale, stroke_width * scale);
}
}
for (unsigned y = 0; y < HEIGHT; y++) {
for (unsigned x = 0; x < WIDTH; x++) {
uint32_t v = map[y][x];
float cx = (x + 0.5f) * scale;
float cy = (y + 0.5f) * scale;
if (has_zone(v)) {
const char *color = get_color(v & ZONE_MASK);
fprintf(o, "<circle cx='%.3g' cy='%.3g' r='%.3g' "
"stroke='%s' stroke-width='%.3g' fill='none'/>\n",
cx, cy, zone_radius * scale,
color, stroke_width * scale);
}
if (has_key(v)) {
const char *color = get_color(v & KEY_MASK);
fprintf(o, "<circle cx='%.3g' cy='%.3g' r='%.3g' "
"stroke='none' fill='%s'/>\n",
cx, cy, key_radius * scale, color);
}
if (v & STEP_TWICE) {
float size = main_radius * scale * 1.25f;
fprintf(o, "<text x='%.3g' y='%.3g' "
"text-anchor='middle' alignment-baseline='central' "
"font-size='%0.3g' font-family='sans serif'>"
"2</text>\n",
cx, cy + size * 2 / 5, size);
}
}
}
}
static void
render_end(FILE *o)
{
fprintf(o, "</svg>\n");
}
struct p {
short x;
short y;
};
static void
render_path(FILE *o, float scale, struct p *p, unsigned len)
{
float stroke_width = 0.035f;
for (unsigned i = 1; i < len; i++) {
float x1 = (p[i - 1].x + 0.5f) * scale;
float y1 = (p[i - 1].y + 0.5f) * scale;
float x2 = (p[i].x + 0.5f) * scale;
float y2 = (p[i].y + 0.5f) * scale;
line(o, x1, y1, x2, y2, stroke_width * scale, "red");
}
}
static const struct p goal = {WIDTH - 1, HEIGHT - 1};
static const unsigned goal_distance = WIDTH * HEIGHT + 2; // TODO: count it
#define is_open(s, x, y) ((map[y][x] & STEP_TWICE) ? s[y][x] < 2 : s[y][x] < 1)
static void
floodfill(const short steps[HEIGHT][WIDTH], bool reachable[HEIGHT][WIDTH],
int x, int y) {
reachable[y][x] = true;
for (int i = 0; i < 8; ++i) {
if (map[y][x] & dir[i].flag) {
int xx = x + dir[i].dx, yy = y + dir[i].dy;
if (!reachable[yy][xx] && is_open(steps, xx, yy)) {
floodfill(steps, reachable, xx, yy);
}
}
}
}
static bool connected(short steps[HEIGHT][WIDTH]) {
bool reachable[HEIGHT][WIDTH] = {{false}};
for (int y = 0; y < HEIGHT; ++y) {
for (int x = 0; x < WIDTH; ++x) {
if (is_open(steps, x, y)) {
floodfill(steps, reachable, x, y);
goto found;
}
}
}
found:
for (int y = 0; y < HEIGHT; ++y) {
for (int x = 0; x < WIDTH; ++x) {
if (is_open(steps, x, y) && !reachable[y][x]) {
return false;
}
}
}
return true;
}
static void
solve(short steps[HEIGHT][WIDTH], uint32_t keys, struct p *p, unsigned len)
{
float scale = 100.0f;
static unsigned best = 0;
static unsigned solution_counter = 0;
if (len > best) {
/* Draw progress. */
best = len;
char filename[32];
sprintf(filename, "path-%03u.svg", len);
/*
FILE *out = fopen(filename, "w");
render_start(out, scale);
render_path(out, scale, p, len);
render_end(out);
fclose(out);
*/
}
struct p c = p[len - 1];
if (c.x == goal.x && c.y == goal.y && len == goal_distance) {
/* Draw this solution. */
char filename[32];
sprintf(filename, "solution-%09u.svg", solution_counter++);
/*
FILE *out = fopen(filename, "w");
render_start(out, scale);
render_path(out, scale, p, len);
render_end(out);
fclose(out);
*/
printf("Solution %d found!\n", solution_counter);
} else if (connected(steps)) {
uint32_t v = map[c.y][c.x];
keys |= v & KEY_MASK;
for (int i = 7; i >= 0; i--) {
struct p next = {c.x + dir[i].dx, c.y + dir[i].dy};
if ((v & dir[i].flag) &&
is_open(steps, next.x, next.y) &&
can_pass(map[next.y][next.x], keys)) {
p[len] = next;
steps[next.y][next.x]++;
solve(steps, keys, p, len + 1);
steps[next.y][next.x]--;
}
}
}
}
int
main(void)
{
render_start(stdout, 100.0f);
render_end(stdout);
fflush(stdout);
short steps[HEIGHT][WIDTH] = {{1}};
struct p path[WIDTH * HEIGHT * 2] = {{0, 0}};
solve(steps, 0, path, 1);
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment