C, score 2.397x10^38
Man this took way too long to do, most likely due to my choice of language. I got the algorithm working fairly early, but ran into a lot of problems with memory allocation (couldn't recursively free stuff due to stack overflows, leak sizes were huge).
Still! It beats the other entry on every test case, and might even be optimal gets pretty close or exactly optimal solutions a lot of the time.
Anyway, here's the code:
#include <stdlib.h>
#include <stdio.h>
#include <stdbool.h>
#include <string.h>
#define WHITE 'W'
#define BLACK 'B'
#define RED 'R'
typedef struct image {
int w, h;
char* buf;
} image;
typedef struct point {
int x, y;
struct point *next;
struct point *parent;
} point;
typedef struct shape {
point* first_point;
point* last_point;
struct shape* next_shape;
} shape;
typedef struct storage {
point* points;
size_t points_size;
size_t points_index;
shape* shapes;
size_t shapes_size;
size_t shapes_index;
} storage;
char getpx(image* img, int x, int y) {
if (0>x || x>=img->w || 0>y || y>=img->h) {
return WHITE;
} else {
return img->buf[y*img->w+x];
}
}
storage* create_storage(int w, int h) {
storage* ps = (storage*)malloc(sizeof(storage));
ps->points_size = 8*w*h;
ps->points = (point*)calloc(ps->points_size, sizeof(point));
ps->points_index = 0;
ps->shapes_size = 2*w*h;
ps->shapes = (shape*)calloc(ps->shapes_size, sizeof(shape));
ps->shapes_index = 0;
return ps;
}
void free_storage(storage* ps) {
if (ps != NULL) {
if (ps->points != NULL) {
free(ps->points);
ps->points = NULL;
}
if (ps->shapes != NULL) {
free(ps->shapes);
ps->shapes = NULL;
}
free(ps);
}
}
point* alloc_point(storage* ps) {
if (ps->points_index == ps->points_size) {
printf("WHOAH THERE BUDDY SLOW DOWN\n");
/*// double the size of the buffer
point* new_buffer = (point*)malloc(ps->points_size*2*sizeof(point));
// need to change all existing pointers to point to new buffer
long long int pointer_offset = (long long int)new_buffer - (long long int)ps->points;
for (size_t i=0; i<ps->points_index; i++) {
new_buffer[i] = ps->points[i];
if (new_buffer[i].next != NULL) {
new_buffer[i].next += pointer_offset;
}
if (new_buffer[i].parent != NULL) {
new_buffer[i].parent += pointer_offset;
}
}
for(size_t i=0; i<ps->shapes_index; i++) {
if (ps->shapes[i].first_point != NULL) {
ps->shapes[i].first_point += pointer_offset;
}
if (ps->shapes[i].last_point != NULL) {
ps->shapes[i].last_point += pointer_offset;
}
}
free(ps->points);
ps->points = new_buffer;
ps->points_size = ps->points_size * 2;*/
}
point* out = &(ps->points[ps->points_index]);
ps->points_index += 1;
return out;
}
shape* alloc_shape(storage* ps) {
/*if (ps->shapes_index == ps->shapes_size) {
// double the size of the buffer
shape* new_buffer = (shape*)malloc(ps->shapes_size*2*sizeof(shape));
long long int pointer_offset = (long long int)new_buffer - (long long int)ps->shapes;
for (size_t i=0; i<ps->shapes_index; i++) {
new_buffer[i] = ps->shapes[i];
if (new_buffer[i].next_shape != NULL) {
new_buffer[i].next_shape += pointer_offset;
}
}
free(ps->shapes);
ps->shapes = new_buffer;
ps->shapes_size = ps->shapes_size * 2;
}*/
shape* out = &(ps->shapes[ps->shapes_index]);
ps->shapes_index += 1;
return out;
}
shape floodfill_shape(image* img, storage* ps, int x, int y, char* buf) {
// not using point allocator for exploration stack b/c that will overflow it
point* stack = (point*)malloc(sizeof(point));
stack->x = x;
stack->y = y;
stack->next = NULL;
stack->parent = NULL;
point* explored = NULL;
point* first_explored;
point* next_explored;
while (stack != NULL) {
int sx = stack->x;
int sy = stack->y;
point* prev_head = stack;
stack = stack->next;
free(prev_head);
buf[sx+sy*img->w] = 1; // mark as explored
// add point to shape
next_explored = alloc_point(ps);
next_explored->x = sx;
next_explored->y = sy;
next_explored->next = NULL;
next_explored->parent = NULL;
if (explored != NULL) {
explored->next = next_explored;
} else {
first_explored = next_explored;
}
explored = next_explored;
for (int dy=-1; dy<2; dy++) {
for (int dx=-1; dx<2; dx++) {
if (dy != 0 || dx != 0) {
int nx = sx+dx;
int ny = sy+dy;
if (getpx(img, nx, ny) == WHITE || buf[nx+ny*img->w]) {
// skip adding point to fringe
} else {
// push point to top of stack
point* new_point = (point*)malloc(sizeof(point));
new_point->x = nx;
new_point->y = ny;
new_point->next = stack;
new_point->parent = NULL;
stack = new_point;
}
}
}
}
}
/*if (getpx(img, x, y) == WHITE || buf[x+y*img->w]) {
return (shape){NULL, NULL, NULL};
} else {
buf[x+y*img->w] = 1;
shape e = floodfill_shape(img, ps, x+1, y, buf);
shape ne = floodfill_shape(img, ps, x+1, y+1, buf);
shape n = floodfill_shape(img, ps, x, y+1, buf);
shape nw = floodfill_shape(img, ps, x-1, y+1, buf);
shape w = floodfill_shape(img, ps, x-1, y, buf);
shape sw = floodfill_shape(img, ps, x-1, y-1, buf);
shape s = floodfill_shape(img, ps, x, y-1, buf);
shape se = floodfill_shape(img, ps, x+1, y-1, buf);
point *p = alloc_point(ps);
p->x = x;
p->y = y;
p->next = NULL;
p->parent = NULL;
shape o = (shape){p, p, NULL};
if (e.first_point != NULL) {
o.last_point->next = e.first_point;
o.last_point = e.last_point;
}
if (ne.first_point != NULL) {
o.last_point->next = ne.first_point;
o.last_point = ne.last_point;
}
if (n.first_point != NULL) {
o.last_point->next = n.first_point;
o.last_point = n.last_point;
}
if (nw.first_point != NULL) {
o.last_point->next = nw.first_point;
o.last_point = nw.last_point;
}
if (w.first_point != NULL) {
o.last_point->next = w.first_point;
o.last_point = w.last_point;
}
if (sw.first_point != NULL) {
o.last_point->next = sw.first_point;
o.last_point = sw.last_point;
}
if (s.first_point != NULL) {
o.last_point->next = s.first_point;
o.last_point = s.last_point;
}
if (se.first_point != NULL) {
o.last_point->next = se.first_point;
o.last_point = se.last_point;
}
return o;
}*/
shape out = {first_explored, explored, NULL};
return out;
}
shape* create_shapes(image* img, storage* ps) {
char* added_buffer = (char*)calloc(img->w*img->h, sizeof(char));
shape* first_shape = NULL;
shape* last_shape = NULL;
int num_shapes = 0;
for (int y=0; y<img->h; y++) {
for (int x=0; x<img->w; x++) {
if (getpx(img, x, y) != WHITE && !(added_buffer[x+y*img->w])) {
shape* alloced_shape = alloc_shape(ps);
*alloced_shape = floodfill_shape(img, ps, x, y, added_buffer);
if (first_shape == NULL) {
first_shape = alloced_shape;
last_shape = alloced_shape;
} else if (last_shape != NULL) {
last_shape->next_shape = alloced_shape;
last_shape = alloced_shape;
}
num_shapes++;
}
}
}
free(added_buffer);
return first_shape;
}
void populate_buf(image* img, shape* s, char* buf) {
point* p = s->first_point;
while (p != NULL) {
buf[p->x+p->y*img->w] = 1;
p = p->next;
}
}
bool expand_frontier(image* img, storage* ps, shape* prev_frontier, shape* next_frontier, char* buf) {
point* p = prev_frontier->first_point;
point* n = NULL;
bool found = false;
size_t starting_points_index = ps->points_index;
while (p != NULL) {
for (int dy=-1; dy<2; dy++) {
for (int dx=-1; dx<2; dx++) {
if (dy != 0 || dx != 0) {
int nx = p->x+dx;
int ny = p->y+dy;
if ((0<=nx && nx<img->w && 0<=ny && ny<img->h) // in bounds
&& !buf[nx+ny*img->w]) { // not searched yet
buf[nx+ny*img->w] = 1;
if (getpx(img, nx, ny) != WHITE) {
// found a new shape!
ps->points_index = starting_points_index;
n = alloc_point(ps);
n->x = nx;
n->y = ny;
n->next = NULL;
n->parent = p;
found = true;
goto __expand_frontier_fullbreak;
} else {
// need to search more
point* f = alloc_point(ps);
f->x = nx;
f->y = ny;
f->next = n;
f->parent = p;
n = f;
}
}
}
}}
p = p->next;
}
__expand_frontier_fullbreak:
p = NULL;
point* last_n = n;
while (last_n->next != NULL) {
last_n = last_n->next;
}
next_frontier->first_point = n;
next_frontier->last_point = last_n;
return found;
}
void color_from_frontier(image* img, point* frontier_point) {
point* p = frontier_point->parent;
while (p->parent != NULL) { // if everything else is right,
// a frontier point should come in a chain of at least 3
// (f point (B) -> point to color (W) -> point in shape (B) -> NULL)
img->buf[p->x+p->y*img->w] = RED;
p = p->parent;
}
}
int main(int argc, char** argv) {
if (argc < 3) {
printf("Error: first argument must be filename to load, second argument filename to save to.\n");
return 1;
}
char* fname = argv[1];
FILE* fp = fopen(fname, "r");
if (fp == NULL) {
printf("Error opening file \"%s\"\n", fname);
return 1;
}
int w, h;
w = 0;
h = 0;
fscanf(fp, "%d %d\n", &w, &h);
if (w==0 || h==0) {
printf("Error: invalid width/height specified\n");
return 1;
}
char* buf = (char*)malloc(sizeof(char)*w*h+1);
fgets(buf, w*h+1, fp);
fclose(fp);
image img = (image){w, h, buf};
int nshapes = 0;
storage* ps = create_storage(w, h);
while (nshapes != 1) {
// main loop, do processing step until one shape left
ps->points_index = 0;
ps->shapes_index = 0;
shape* head = create_shapes(&img, ps);
nshapes = 0;
shape* pt = head;
while (pt != NULL) {
pt = pt->next_shape;
nshapes++;
}
if (nshapes % 1024 == 0) {
printf("shapes left: %d\n", nshapes);
}
if (nshapes == 1) {
goto __main_task_complete;
}
shape* frontier = alloc_shape(ps);
// making a copy so we can safely free later
point* p = head->first_point;
point* ffp = NULL;
point* flp = NULL;
while (p != NULL) {
if (ffp == NULL) {
ffp = alloc_point(ps);
ffp->x = p->x;
ffp->y = p->y;
ffp->next = NULL;
ffp->parent = NULL;
flp = ffp;
} else {
point* fnp = alloc_point(ps);
fnp->x = p->x;
fnp->y = p->y;
fnp->next = NULL;
fnp->parent = NULL;
flp->next = fnp;
flp = fnp;
}
p = p->next;
}
frontier->first_point = ffp;
frontier->last_point = flp;
frontier->next_shape = NULL;
char* visited_buf = (char*)calloc(img.w*img.h+1, sizeof(char));
populate_buf(&img, frontier, visited_buf);
shape* new_frontier = alloc_shape(ps);
new_frontier->first_point = NULL;
new_frontier->last_point = NULL;
new_frontier->next_shape = NULL;
while (!expand_frontier(&img, ps, frontier, new_frontier, visited_buf)) {
frontier->first_point = new_frontier->first_point;
frontier->last_point = new_frontier->last_point;
new_frontier->next_shape = frontier;
}
free(visited_buf);
color_from_frontier(&img, new_frontier->first_point);
__main_task_complete:
img = img;
}
free_storage(ps);
char* outfname = argv[2];
fp = fopen(outfname, "w");
if (fp == NULL) {
printf("Error opening file \"%s\"\n", outfname);
return 1;
}
fprintf(fp, "%d %d\n", img.w, img.h);
fprintf(fp, "%s", img.buf);
free(img.buf);
fclose(fp);
return 0;
}
Tested on: Arch Linux, GCC 9.1.0, -O3
This code takes input/output in a custom file I call "cppm" (because it's like a condensed version of the classic PPM format). A python script to convert to/from it is below:
from PIL import Image
BLACK='B'
WHITE='W'
RED ='R'
def image_to_cppm(infname, outfname):
outfile = open(outfname, 'w')
im = Image.open(infname)
w, h = im.width, im.height
outfile.write(f"{w} {h}\n")
for y in range(h):
for x in range(w):
r, g, b, *_ = im.getpixel((x, y))
if r==0 and g==0 and b==0:
outfile.write(BLACK)
elif g==0 and b==0:
outfile.write(RED)
else:
outfile.write(WHITE)
outfile.write("\n")
outfile.close()
im.close()
def cppm_to_image(infname, outfname):
infile = open(infname, 'r')
w, h = infile.readline().split(" ")
w, h = int(w), int(h)
im = Image.new('RGB', (w, h), color=(255, 255, 255))
for y in range(h):
for x in range(w):
c = infile.read(1)
if c==BLACK:
im.putpixel((x,y), (0, 0, 0))
elif c==RED:
im.putpixel((x,y), (255, 0, 0))
infile.close()
im.save(outfname)
im.close()
if __name__ == "__main__":
import sys
if len(sys.argv) < 3:
print("Error: must provide 2 files to convert, first is from, second is to")
infname = sys.argv[1]
outfname = sys.argv[2]
if not infname.endswith("cppm") and outfname.endswith("cppm"):
image_to_cppm(infname, outfname)
elif infname.endswith("cppm") and not outfname.endswith("cppm"):
cppm_to_image(infname, outfname)
else:
print("didn't do anything, exactly one file must end with .cppm")
Algorithm explanation
How this algorithm works is that it starts by finding all the connected shapes in the image, including red pixels. It then takes the first one and expands its frontier one pixel at a time until it encounters another shape. It then colors all the pixels from the touching to the original shape (using the linkedlist it made along the way to keep track). Finally, it repeats the process, finding all the new shapes created, until there is only one shape left.
Image gallery
Testcase 1, 183 pixels
Testcase 2, 140 pixels
Testcase 3, 244 pixels
Testcase 4, 42 pixels
Testcase 5, 622 pixels
Testcase 6, 1 pixel
Testcase 7, 104 pixels
Testcase 8, 2286 pixels
Testcase 9, 22 pixels
Testcase 10, 31581 pixels
Testcase 11, 21421 pixels
Testcase 12, 5465 pixels
Testcase 13, 4679 pixels
Testcase 14, 7362 pixels
