David Finch's solution:
I did a lot of hand culling. I tried to organize the data to minimize hard disk thrashing, but the memory requirements were probably 2.5x my physical ram. Due to swapping, it took over half an hour.
//Written by David Finch, dtfinch@charter.net or david@mytsoftware.com
#include <stdio.h>
#include <stdlib.h>
#define Width 173
#define Height 173
#define PWidth (Width*10)
#define PHeight (Height*10)
#define NumPoints 346991 // # of reachable x,y positions, or the most we want to look at
//too lazy to write a loader, so here's the map
//The dashes are to exclude areas of the map that'll waste time and memory.
char map[Height][Width+1]={
"------------------------------------------------------------------------------------------ --------------------------------\000",
"-------------------------------------------------------------------------------------- -----------------------------\000",
"----------------------------------------------------------------------------------- -------------------------\000",
"------------------------------------------------------------------------------- ----------------------\000",
"--------------------------------------------------------------------------- -------------------\000",
"------------------------------------------------------------------------- -----------------\000",
"---------------------------------------------------------------------- ----------------\000",
"-------------------------------------------------------------------- ---------------\000",
"------------------------------------------------------------------ -------------\000",
"---------------------------------------------------------------- -----------\000",
"--------------------------------------------------------------- ----------\000",
"-------------------------------------------------------------- ---------\000",
"------------------------------------------------------------- --------\000",
"------------------------------------------------------------ ###### ##### -------\000",
"----------------------------------------------------------- -----------#################### ------\000",
"---------------------------------------------------------- -------------###################### -----\000",
"---------------------------------------------------------- O ---------------------####################### ----\000",
"--------------------------------------------------------########----------------------------------------------------------------########################## ---\000",
"---------------------------------------------------##############--------------------------------------------------------------########################### --\000",
"-------------------------------------------------##################------------------------------------------------------------########################### -\000",
"-----------------------------------------------#####################----------------------------------------------------------############################ \000",
"---------------------------------------------#######################----------------------------------------------------------##########################-- \000",
"-------------------------------------------##########################--------------------------------------------------------##########################--- \000",
"-----------------------------------------############################---------------------------------------------------------#########################--- \000",
"------------------------------------###################################----------------------------------------------------###########################---- \000",
"----------------------------------######################################--------------------------------------------------##########################------ \000",
"--------------------------------########################################--------------------------------------------------########################-------- \000",
"------------------------------############################################------------------------------------------##############################--------- \000",
"-------------------------###################################################--------------------------------------###################################------ \000",
"--------------------##########################################################----------------------------------#######################################---- \000",
"---------------################################################################-------------------------------##########################################--- \000",
"-----------####################################################################-----------------------------##############################################- \000",
"--------#########################################################################-------------------------################################################## \000",
"------############################################################################-----------------------################################################### \000",
"----##############################################################################-----------------------################################################## \000",
"--#################################################################################---------------------################################################### \000",
"###################################################################################---------------------################################################# \000",
"####################################################################################-------------------################################################ \000",
"####################################################################################-----------------################################################# \000",
"########################################### ###################################--------------################################################### \000",
"###################################### #################################---------####################################################### \000",
"#################################### ######################################################################################### -\000",
"################################### -------############################################################################### --\000",
"################################### -----########################################################################## ----\000",
"################# -----################################################################# ------\000",
"################ -----############################################################## --------\000",
"############## -----########################################################### ---------\000",
"############# ----######################################################### ###########\000",
"############# ----###################################################### #############\000",
"############ ##### --###################################################### ##############\000",
"############ ##########-- ##################################################### --##############\000",
"############ ############-------### ################################################ ##################\000",
"############ ######################### ########################################### --####################\000",
"########### ############################## ####################################### ###########################\000",
"########### ####################################### #################################### #############################\000",
"########### ####################################### ################################## #################################\000",
"########### ######################################- ########################## ##################################\000",
"########### ######################################- ################## ##################################\000",
"########### ######################################- ################# ##################################\000",
"########### #######################################- ############## ###################################\000",
"########### #######################################- ########### ##################################\000",
"########### #########---###########################- ########### ##################################\000",
"###########- -------#############----########### ######## #################################\000",
"###########-- ---###########--------######### ####### ####-----#### #################################\000",
"###########--- --##########----------######### ###### ########-######## ################################\000",
"###########---- -##########----------########## ##### #################### ################################\000",
"###########------ #########------------########## ##### ###################### ###############################\000",
"###########------------#### ########------------############ ### ######################## ###############################\000",
"###########------------###### ########------------############## ######################## ##############################\000",
"###########------------####### ########------------############### ######################### ##############################\000",
"###########-----------######## ########------------################ ############################# #############################\000",
"###########-----------######### ########-------------################ ############################### #############################\000",
"###########----------########## ########-------------################## ################################ ############################\000",
"###########--------############ #########-------------################### --################################ ############################\000",
"###########-----############### #########-------------####################-- ----################################# ############################\000",
"###########------############## ##########-------------#####################--- ------################################- #########################\000",
"###########------############## ##########-------------######################-------------------###############################-- ########################\000",
"###########-------############# ###########-------------#####################-------------------#############################---- #######################\000",
"###########-------############# ###########-------------####################---------------------#######################---------- #####################\000",
"###########-------############# ############---------------------###########---------------------#####################------------- ####################\000",
"###########--------############ ############-----------------------#########----------------------############---------------------- ##################\000",
"###########-------############# ############-----------------------#########------------------------########-------------------------- ################\000",
"###########--------############ ############-----------------------#########--------------------------####----------------------------------# ##############\000",
"###########-------############# ############-----------------------#########-------------------------------------------------------------##### ############\000",
"###########-------############# ############----------------------##########----------------------------------------------------------######### ###########\000",
"############################### #############----------###---------##########---------------------------------------------------------########### ###########\000",
"############################### ##############--------######-------###########--------------------------------------------------------############# ##########\000",
"############################## ################----########-------############---------------------------------------------------################### ##########\000",
"############################## ############################-------#############---------------------------------#--------------####################### ##########\000",
"############################# ############################------###############------------------------------####-------############################# ##########\000",
"############################# ############################--------####################################------########################################### #########\000",
"############################ ###########################-----------################################################################################### #########\000",
"########################## -##########################------------ ################################################################################# #########\000",
"######################## ---#######################------- --######################################################################### ########\000",
"####################### ----###################### ######################################################################## ########\000",
"#################### ----##################### ###################################################################### ########\000",
"################## ------################## ##################################################################### #######\000",
"##########------ ------########-------- ---------------------############------#### #######\000",
"##########----- ------########------- -------------------############------- #######\000",
"##########---- -------########----- ----------------#############----- #######\000",
"###########-- --------#########--- -------------#############---- #######\000",
"###########- --------#########- --#########################- #######\000",
"########### ----------######### #### --########################## ######## #######\000",
"########### ----------######### ######## -########################### ########## #######\000",
"########### -------------####### ##-------------------######### -########################## ########### #######\000",
"######### --------------##### ##########-------------######### ########################### ########### #######\000",
"######## ----------------#### ############-------------########## ########################### ############ ######\000",
"######## #####---------------#### #################-------------########## ########################### ############ ######\000",
"####### #####---------------### ################-------------########### ################ ############ ######\000",
"####### ######---------------### #################-------------###########- ############ ############ ######\000",
"###### #####----------------## ###################------------############-- ###### -############ ######\000",
"###### ######---------------### ###################------------############--- -############ #####\000",
"###### ######---------------### #####################----------#############----- --########### #####\000",
"###### #######--------------#### #######################----------#############------ --########### #####\000",
"###### #########-------------#### ##########----------####---------##############--------- ---########### #####\000",
"###### ########-------------#### ########------------------------##############------------ -----########## #####\000",
"###### #########------------#### #######-------------------------##############------------------ --------########## #####\000",
"####### #########------------#### #######-------------------------#############----------------------- --------############ #####\000",
"####### ##########-----------#### ########------------------------#############-----#####--------------- -----------############ #####\000",
"####### ##########----------##### #########------------------------#############- ##########-------------------------------------############# #####\000",
"####### ###########--------###### #########------------------------#################################-----------------------------############# #####\000",
"####### #############----######## ##########-#-#-#-#-#-#-#####-##-####################################--------------------------############# #####\000",
"####### ######################## #########################################################################---------------------############# #####\000",
"####### ######################## ###################################################################################----------############# #####\000",
"####### ######################## #####################################################################################---------############# #####\000",
"####### ######################## #####################################################################################---------############ #####\000",
"####### ######################## #####################################################################################---------############ ######\000",
"####### ####################### ####################################################################################----------############ ######\000",
"#######- ##################### ####################################################################################----------############ ######\000",
"#######-- ################### ####################################################################################----------############ ######\000",
"#######--- ################ ####################################################################################----------########### ######\000",
"########--- ############## #########################################------#####################################---------############ ######\000",
"########---- --- #########################------------------------###################################----------############ ######\000",
"#########---- #######################---------------------------##################################----------############ ######\000",
"#########------- ############----------------------------------------################################-----------############ ######\000",
"##########-----------### ############-----------------------------------------###############################-----------############ ######\000",
"###########---------###### #############------------------------------------------#################-############-----------############ ######\000",
"##############----########## ###############------------------------------------------######------------############-----------############ ######\000",
"############################# ################------------------------------------------------------------##############----------############ ######\000",
"############################# ##################--------------------##############---------------#########################---------############# ######\000",
"############################ #####################-----------------##################------------###########################--------############# ######\000",
"############################ ########################------------- #####################-----------##########################---------############ ######\000",
"########################### ##########################------------#######################-----------##########################---------############ ######\000",
"########################### ###########################----------#########################---------##########################-----------########### ######\000",
"######################### ############################----------#########################-------############################-----------########### ######\000",
"######################## ############################---------##########################-------############################-----------########### ######\000",
"######################## #############################--------######################----------------########################-----------########### ######\000",
"###################### ###########################--------###############------------------------------###################-----------########### ######\000",
"##################### ###########################----------###########-----------------------------------#################-----------########### ######\000",
"##################### ###########################----------##############-----------------------------------------------------------############ ######\000",
"#################### ############--------#######------------###############---------------------------------------------------------############ ######\000",
"#################### ############---------------------------####################---------------------------------------------------############# ######\000",
"##########--------- #############-----------------------################################--------------------------------------################## ######\000",
"########----------- ############------------------##########################################-------------------------------#################### #######\000",
"#######------------ ##########-----------------##############################################---############################################## #######\000",
"#######------------ ######################################################################################################################### #######\000",
"#######------------ ######################################################################################################################## ########\000",
"#######------------- ##################################################################################################################### ########\000",
"#######------------- #################################################################################################################### ########\000",
"########-------------- ################################################################################################################### #########\000",
"####################----- + ################################################################################################################# #########\000",
"################################# ################################################################################################################ #########\000",
"################################## ############################################################################################################# ##########\000",
"#################################### ##############################---------############################################################# ##########\000",
"##################################### ##################### ############################################ ###########\000",
"##################################### ############### ################################### ############\000",
"##################################### ########### ####### ##############\000",
"###################################### #################\000",
"######################################## ######################\000",
"############################################ ##### #########################\000",
"############################################################################################### ############ ################################\000",
"#############################################################################################################################################################################\000",
"#############################################################################################################################################################################\000"
};
/*
A node only needs to store the address of the best source and if it was visited.
Address format: 32 bit
visited:1 - When searching for shortest path by # of steps, we only need to track visited vs unvisited.
map:1 - Which map, to or from.
xy:20
dx:5
dy:5
*/
#define Visited ((unsigned int)1<<31)
#define pack(v,m,x,y,dx,dy) (((unsigned int)(v)<<31)|((m)<<30)|(indexes[x][y]<<10)|(((dx)+16)<<5)|((dy)+16))
#define unpackv(a) (((a)>>31)&1)
#define unpackm(a) (((a)>>30)&1)
#define unpackx(a) RevX[((a)>>10)&1048575]
#define unpacky(a) RevY[((a)>>10)&1048575]
#define unpackdx(a) ((((a)>>5)&31)-16)
#define unpackdy(a) (((a)&31)-16)
#define ListSize 5000000
typedef unsigned int Address;
typedef struct {
int x;
int y;
int dx;
int dy;
int map;
int visited;
} SAddress;
typedef struct {
Address points[ListSize];
unsigned short int fuel[ListSize];
int length;
} List;
Address world[2][NumPoints][21][21];
#define source(a) world[unpackm(a)][indexes[unpackx(a)][unpacky(a)]][unpackdx(a)+10][unpackdy(a)+10]
List lists[2];
List *srcL=&lists[0];
List *destL=&lists[1];
#define pop() (srcL->points[--srcL->length])
#define empty() (srcL->length==0)
void push(Address a, int fuel) {
destL->fuel[destL->length]=fuel;
destL->points[destL->length++]=a;
}
#define NoAddress ((Address)0xffffffff)
#define PBlocked 1
#define PStart 2
#define PEnd 4
typedef char PState;
int spaces=0;
int indexes[PWidth][PHeight];
PState PixMap[PWidth][PHeight];
int RevX[NumPoints];
int RevY[NumPoints];
Address spack(SAddress *a) {
return pack(a->visited,a->map,a->x,a->y,a->dx,a->dy);
}
void Blot(int x,int y) {
map[y/10][x/10]='*';
}
void PrintMap() {
int i;
printf("\n");
for(i=0;i<Height;i++) {
printf("%s\n",map[i]);
}
}
void sunpack(Address a, SAddress *r) {
r->x=unpackx(a);
r->y=unpacky(a);
r->dx=unpackdx(a);
r->dy=unpackdy(a);
r->map=unpackm(a);
r->visited=unpackv(a);
}
PState GetMapStatePoint(int x, int y) {
x=x/10;
y=y/10;
if(y>=35 && y<156 && x>=0 && x<128) return PBlocked; //some extra culling
if(y>=98 && y<121 && x>=128 && x<158) return PBlocked;
switch(map[y][x]) {
case ' ':
return 0;
case 'O':
return PStart;
case '+':
return PEnd;
}
return PBlocked;
}
PState GetMapStateSlow(int x, int y) {
return GetMapStatePoint(x,y)
| GetMapStatePoint(x+9,y)
| GetMapStatePoint(x,y+9)
| GetMapStatePoint(x+9,y+9);
}
PState GetMapStateFast(int x, int y) {
if(x<0 || y<0 || x>=PWidth || y>=PHeight) return PBlocked;
return PixMap[x][y];
}
#define isWin(a) (unpackm(a)==1&&(PixMap[unpackx(a)][unpacky(a)]&PStart))
Address CalcDest(Address src, int left, int up, int right) {
SAddress d;
char s;
sunpack(src,&d);
if(d.dx>10 && right) return NoAddress;
if(d.dx<-10 && left) return NoAddress;
if(left) d.dx-=2;
if(right) d.dx+=2;
if(up) d.dy-=1; else d.dy+=1;
if(d.dx>10) d.dx=10;
if(d.dx<-10) d.dx=-10;
if(d.dy>10) d.dy=10;
if(d.dy<-10) d.dy=-10;
while((s=GetMapStateFast(d.x+d.dx,d.y+d.dy))&PBlocked) {
d.dx/=2;
d.dy/=2;
}
d.x+=d.dx;
d.y+=d.dy;
if((s&PEnd)&&d.map==0) d.map=1;
// printf(" [%d %d %d %d %d]",d.map,d.x,d.y,d.dx,d.dy);
return spack(&d);
}
void TracePath(Address dest) {
Address src;
char buffer[2000];
char *s=buffer+1900;
*s=0;
do {
src=source(dest);
if((dest|Visited)==(CalcDest(src,0,0,0)|Visited)) *--s='0';
else if((dest|Visited)==(CalcDest(src,1,0,0)|Visited)) *--s='1';
else if((dest|Visited)==(CalcDest(src,0,1,0)|Visited)) *--s='2';
else if((dest|Visited)==(CalcDest(src,0,0,1)|Visited)) *--s='4';
else if((dest|Visited)==(CalcDest(src,1,1,0)|Visited)) *--s='3';
else if((dest|Visited)==(CalcDest(src,0,1,1)|Visited)) *--s='6';
else *--s='?';
if(s<=buffer) {
printf("Error");
return;
}
dest=src;
} while(unpackx(src)!=590||unpacky(src)!=160||unpackm(src)!=0);
printf("\n%s\n",s);
}
void MoveAbsolute(Address src, Address dest, int fuel) {
if(dest!=NoAddress && unpackv(source(dest))==0) { //if destination hasn't been visited yet
source(dest)=src|Visited;
push(dest,fuel);
if(isWin(dest)) {
printf("Done\n");
TracePath(dest);
exit(0);
}
//printf("+");
//Blot(unpackx(dest),unpacky(dest));
}// else printf("-");
}
void SwapLists() {
List *temp;
temp=srcL;
srcL=destL;
destL=temp;
}
//I know this is horribly inefficient. I'm too lazy to sort.
void ProcessList() {
SwapLists();
destL->length=0;
int i,f;
int mf=10000,xf=0;
for(i=0;i<srcL->length;i++) {
int fuel=srcL->fuel[i];
if(fuel<mf) mf=fuel;
if(fuel>xf) xf=fuel;
}
xf+=2;
for(f=mf;f<=xf;f++) {
for(i=0;i<srcL->length;i++) {
Address src=srcL->points[i];
int fuel=srcL->fuel[i];
if(fuel==f) {
MoveAbsolute(src,CalcDest(src,0,0,0),f);
}
if(fuel+1==f) {
MoveAbsolute(src,CalcDest(src,1,0,0),f);
MoveAbsolute(src,CalcDest(src,0,1,0),f);
MoveAbsolute(src,CalcDest(src,0,0,1),f);
}
if(fuel+2==f) {
MoveAbsolute(src,CalcDest(src,1,1,0),f);
MoveAbsolute(src,CalcDest(src,0,1,1),f);
}
}
}
}
void FillPixMap() {
int x,y,j,k;
char s;
for(j=0;j<2048;j++) {
for(k=0;k<2048;k++) {
x=(j&0xaaaaaaaa)|(k&0x55555555); //this mixing should improve locality, to increase cache hits and reduce swap activity. I hope.
y=(j&0x55555555)|(k&0xaaaaaaaa);
if(x<PWidth && y<PHeight) {
PixMap[x][y]=s=GetMapStateSlow(x,y);
if((s & PBlocked)==0) {
RevX[spaces]=x;
RevY[spaces]=y;
indexes[x][y]=spaces++;
}
}
}
}
}
void ClearNodes() {
int i,j,k;
for(i=0;i<NumPoints;i++) {
for(j=0;j<21;j++) {
for(k=0;k<21;k++) {
world[0][i][j][k]=0;
world[1][i][j][k]=0;
}
}
}
}
int main(void) {
printf("started\n");
int steps=0;
FillPixMap();
printf("Spaces: %d\n",spaces);
// return;
ClearNodes();
push(pack(0,0,590,160,0,0),0); //Starting position
while(destL->length) {
printf("\n%d %d",++steps,destL->length);
ProcessList();
}
printf("\n");
PrintMap();
return 0;
}