summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorjonsykkel <jonrevold@gmail.com>2020-10-25 00:12:35 +0200
committerjonsykkel <jonrevold@gmail.com>2020-10-25 00:12:35 +0200
commitec2b6550fa7dea483acdfc932dab4edbaf0d2ece (patch)
treed35867b36af47663b5e416481cee168c70f19a44
parentd4c267b7a0296573b62992b7da5f90d587e1a205 (diff)
downloadmindustry_solver-ec2b6550fa7dea483acdfc932dab4edbaf0d2ece.tar.gz
oretek1
-rw-r--r--makefile3
-rw-r--r--src/main.c160
2 files changed, 110 insertions, 53 deletions
diff --git a/makefile b/makefile
index 1586589..4b6f738 100644
--- a/makefile
+++ b/makefile
@@ -38,6 +38,7 @@ ifeq ($(build),debug)
CFLAGS += -g
else ifeq ($(build),release)
CFLAGS += -O3
+ CFLAGS += -DFASTIK
#CFLAGS += -Wunused-variable -Wunused-function -Wunused-parameter -Wunused-label
LDFLAGS += $(RELFLAGS)
else ifeq ($(build),analyze)
@@ -56,7 +57,7 @@ ifneq ($(run),)
run_cmd := @echo "run $(bin)"
run_cmd += && cd bin
run_cmd += && echo "----------------------------------------------------------------"
- run_cmd += && ./$(out_file)
+ run_cmd += && time ./$(out_file)
run_cmd += ; echo "----------------------------------------------------------------"
run_cmd += && cd ..
endif
diff --git a/src/main.c b/src/main.c
index dfbe58f..7b6e77a 100644
--- a/src/main.c
+++ b/src/main.c
@@ -24,6 +24,8 @@
#define CELL_FLAG_FILL 0x01
+#define DRILL_FLAG_COUNTED 0x01
+
enum{
CELL_TYPE_GROUND,
CELL_TYPE_ORE,
@@ -39,7 +41,8 @@ typedef struct cell_t{
typedef struct drill_t{
uint16_t x;
uint16_t y;
- uint32_t dim;
+ uint8_t dim;
+ uint8_t flags;
}drill_t;
typedef struct map_t{
@@ -48,10 +51,13 @@ typedef struct map_t{
cell_t *cell;
size_t drill_cnt;
drill_t *drill;
+ size_t ore_cnt;
}map_t;
typedef struct backup_t{
cell_t cell[MAP_BACKUP_SIZE];
+ size_t drill_cnt;
+ size_t ore_cnt;
}backup_t;
static void fail(void){
@@ -88,6 +94,7 @@ static void map_alloc(map_t *map,size_t width,size_t height,char const *init){
drill_max = (width/DRILL_DIM_MIN)*(height/DRILL_DIM_MIN);
map->drill = malloc(sizeof(drill_t)*drill_max);
map->drill_cnt = 0;
+ map->ore_cnt = 0;
}
static void map_print(map_t *map){
@@ -106,37 +113,6 @@ static void map_print(map_t *map){
putc('\n',stdout);
}
-static void map_flood_clear(map_t *map){
- for(size_t x = 0;x < map->width*map->height;x++){
- map->cell[x].flags &= ~CELL_FLAG_FILL;
- }
-}
-
-static int map_flood_tmp(map_t *map,size_t x,size_t y){
- cell_t *c = MAP_CELL(map,x,y);
- if(c->type == CELL_TYPE_DRILL) return 3;
- if(MAP_CELL_IS_BORDER(map,x,y)) return 1;
-
- if(c->flags & CELL_FLAG_FILL) return 2;
- c->flags |= CELL_FLAG_FILL;
- int r;
- r = map_flood_tmp(map,x-1,y ); if(r <= 1) return r;
- r = map_flood_tmp(map,x+1,y ); if(r <= 1) return r;
- r = map_flood_tmp(map,x, y-1); if(r <= 1) return r;
- r = map_flood_tmp(map,x, y+1); if(r <= 1) return r;
- return 0;
-}
-
-//0 = floding done, no connection to border
-//1 = floding done, conection to border
-//2 = cell is filled
-//3 = cell is solid (dril)
-static int map_flood(map_t *map,size_t x,size_t y){
- int r = map_flood_tmp(map,x,y);
- map_flood_clear(map);
- return r;
-}
-
//pos = ore count
//neg = not possible build dril
static int map_drill_prospect(map_t *map,size_t x,size_t y,size_t dim){
@@ -159,7 +135,7 @@ static int map_drill_prospect(map_t *map,size_t x,size_t y,size_t dim){
return ore;
}
-static void map_drill_add(map_t *map,size_t x,size_t y,size_t dim){
+static void map_drill_add(map_t *map,size_t x,size_t y,size_t dim,size_t ore){
CHECK_DIM(dim);
for(size_t cy = 0;cy < dim;cy++){
for(size_t cx = 0;cx < dim;cx++){
@@ -171,14 +147,17 @@ static void map_drill_add(map_t *map,size_t x,size_t y,size_t dim){
if(c->type == CELL_TYPE_DRILL) fail();
#endif
c->type = CELL_TYPE_DRILL;
- c->drill_index = 1; //tmp
+ c->drill_index = map->drill_cnt; //tmp
}
}
drill_t *drill;
- drill = &map->drill[map->drill_cnt++];
+ drill = &map->drill[map->drill_cnt];
drill->x = x;
drill->y = y;
+
+ map->drill_cnt++;
+ map->ore_cnt += ore;
}
static void map_backup(map_t *map,size_t x,size_t y,size_t dim,backup_t *backup){
@@ -187,6 +166,8 @@ static void map_backup(map_t *map,size_t x,size_t y,size_t dim,backup_t *backup)
memcpy(cell,MAP_CELL(map,x,cy),sizeof(cell_t)*dim);
cell += dim;
}
+ backup->drill_cnt = map->drill_cnt;
+ backup->ore_cnt = map->ore_cnt;
}
static void map_restore(map_t *map,size_t x,size_t y,size_t dim,backup_t *backup){
@@ -195,7 +176,88 @@ static void map_restore(map_t *map,size_t x,size_t y,size_t dim,backup_t *backup
memcpy(MAP_CELL(map,x,cy),cell,sizeof(cell_t)*dim);
cell += dim;
}
- map->drill_cnt--;
+ map->drill_cnt = backup->drill_cnt;
+ map->ore_cnt = backup->ore_cnt;
+}
+
+static void map_flood_clear(map_t *map){
+ for(size_t x = 0;x < map->width*map->height;x++){
+ map->cell[x].flags &= ~CELL_FLAG_FILL;
+ }
+ for(size_t x = 0;x < map->drill_cnt;x++){
+ map->drill[x].flags &= ~DRILL_FLAG_COUNTED;
+ }
+}
+
+/*
+static int map_flood_tmp(map_t *map,size_t x,size_t y){
+ cell_t *c = MAP_CELL(map,x,y);
+ if(c->type == CELL_TYPE_DRILL) return 3;
+ if(MAP_CELL_IS_BORDER(map,x,y)) return 1;
+
+ if(c->flags & CELL_FLAG_FILL) return 2;
+ c->flags |= CELL_FLAG_FILL;
+ int r;
+ r = map_flood_tmp(map,x-1,y ); if(r <= 1) return r;
+ r = map_flood_tmp(map,x+1,y ); if(r <= 1) return r;
+ r = map_flood_tmp(map,x, y-1); if(r <= 1) return r;
+ r = map_flood_tmp(map,x, y+1); if(r <= 1) return r;
+ return 0;
+}
+
+//0 = floding done, no connection to border
+//1 = floding done, conection to border
+//2 = cell is filled
+//3 = cell is solid (dril)
+static int map_flood(map_t *map,size_t x,size_t y){
+ int r = map_flood_tmp(map,x,y);
+ map_flood_clear(map);
+ return r;
+}
+*/
+
+//returns number of new drills determined reachable
+static size_t map_flood(map_t *map,size_t x,size_t y){
+ cell_t *c = MAP_CELL(map,x,y);
+
+ if(c->flags & CELL_FLAG_FILL) return 0;
+ c->flags |= CELL_FLAG_FILL;
+
+ if(c->type == CELL_TYPE_DRILL){
+ drill_t *d = &map->drill[c->drill_index];
+ if(d->flags & DRILL_FLAG_COUNTED) return 0;
+ d->flags |= DRILL_FLAG_COUNTED;
+ return 1;
+ }
+
+ size_t r = 0;
+ if(x-1 < map->width) r += map_flood(map,x-1,y );
+ if(x+1 < map->width) r += map_flood(map,x+1,y );
+ if(y-1 < map->height) r += map_flood(map,x, y-1);
+ if(y+1 < map->height) r += map_flood(map,x, y+1);
+ return r;
+}
+
+static size_t map_reachable_drills(map_t *map){
+ size_t reachable = 0;
+ for(size_t x = 0;x < map->width;x++){
+ reachable += map_flood(map,x,0);
+ if(reachable >= map->drill_cnt) break;
+ }
+ for(size_t y = 1;y < map->height-2;y++){
+ reachable += map_flood(map,0,y);
+ if(reachable >= map->drill_cnt) break;
+ }
+ for(size_t y = 1;y < map->height-2;y++){
+ reachable += map_flood(map,map->width-1,y);
+ if(reachable >= map->drill_cnt) break;
+ }
+ for(size_t x = 0;x < map->width;x++){
+ reachable += map_flood(map,x,map->height-1);
+ if(reachable >= map->drill_cnt) break;
+ }
+ map_flood_clear(map);
+ return reachable;
}
//1 = placed drill
@@ -208,11 +270,14 @@ static int map_drill_auto(map_t *map,size_t dim){
int ore = map_drill_prospect(map,x,y,dim);
if(ore < target) continue;
- backup_t backup;
+ backup_t backup;
+ size_t reachable;
map_backup(map,x,y,dim,&backup);
- map_drill_add(map,x,y,dim);
- //map_restore(map,x,y,dim,&backup);
- return 1;
+ map_drill_add(map,x,y,dim,ore);
+ reachable = map_reachable_drills(map);
+ //printf("rech %zu dril total %zu\n",reachable,map->drill_cnt);
+ if(reachable >= map->drill_cnt) return 1;
+ map_restore(map,x,y,dim,&backup);
}
}
}
@@ -250,19 +315,10 @@ int main(int argc,char **argv){
//map_drill_add(&map,4,1,2);
- for(size_t x = 0;x < 18;x++)
- map_drill_auto(&map,2);
-
- /*
- map_drill_add(&map,4,1,2);
- map_drill_add(&map,6,1,2);
- map_drill_add(&map,4,3,2);
- map_drill_add(&map,8,3,2);
- map_drill_add(&map,6,3,2);
- map_drill_add(&map,6,5,2);
- printf("gonekted %d\n",map_drill_connected(&map,6,3));
- */
+ while(map_drill_auto(&map,2));
map_print(&map);
+ printf("drils total %zu\n",map.drill_cnt);
+ printf("ore total %zu\n",map.ore_cnt);
return 0;
}