David Finch's solution:
I wrote a 5 dimensional shortest path finder.
Dimensions: trip (to vs from) x X x Y x dX x dY
I almost didn't have enough ram.
Compiled using gcc on Ubuntu Linux.
//Written by David Finch, dtfinch@charter.net or david@mytsoftware.com
#include <stdio.h>
#include <stdlib.h>
#define Width 75
#define Height 39
#define PWidth (Width*10)
#define PHeight (Height*10)
#define NumPoints 104409 //# of reachable x,y positions
//for some reason, NumPoints changed without any effort on my part
//I can't explain it.
/*
This is a job for a 4 dimensional shortest path algorithm
Actually a 5 dimensions if you include the target box as a gateway to the return path.
Storage needed: Positions x velocities x universes x storage per node
So 75*39*10*10 * 21*21 * 2 * 8bytes=2063880000 bytes to store, or about 2gb
Since I only have 512 mb:
Compress to remove unreachable or useless nodes.
Many parts of map blotted out.
Will need x,y lookup to calculate indexes now.
There are only 104409 points after blotting.
Now 736709904 bytes. Almost there.
Pack data structure to 32 bits and go without tracking score (possible).
Down to 368354952, within our limit. Leaves room for other stuff.
*/
//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",
" 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",
"Mars-Rescue-Mission----######## ####\000",
"Challenge-Map----------########## ######\000",
"Design-by-Frank-Buss---############## ########\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.
x:10
y:10
dx:5
dy:5
*/
#define Visited ((unsigned int)1<<31)
#define pack(v,m,x,y,dx,dy) (((unsigned int)(v)<<31)|((m)<<30)|((x)<<20)|((y)<<10)|(((dx)+16)<<5)|((dy)+16))
#define unpackv(a) (((a)>>31)&1)
#define unpackm(a) (((a)>>30)&1)
#define unpackx(a) (((a)>>20)&1023)
#define unpacky(a) (((a)>>10)&1023)
#define unpackdx(a) ((((a)>>5)&31)-16)
#define unpackdy(a) (((a)&31)-16)
#define ListSize 1000000
typedef unsigned int Address;
typedef struct {
int x;
int y;
int dx;
int dy;
int map;
int visited;
} SAddress;
typedef struct {
Address points[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)
#define push(a) (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];
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;
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[500];
char *s=buffer+400;
*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)!=10||unpacky(src)!=60||unpackm(src)!=0);
printf("\n%s\n",s);
}
void MoveAbsolute(Address src, Address dest) {
if(dest!=NoAddress && unpackv(source(dest))==0) { //if destination hasn't been visited yet
source(dest)=src|Visited;
push(dest);
if(isWin(dest)) {
printf("Done\n");
TracePath(dest);
exit(0);
}
//printf("+");
Blot(unpackx(dest),unpacky(dest));
}// else printf("-");
}
void TryMoves(int left, int down, int right) {
int i;
for(i=0;i<srcL->length;i++) {
Address src=srcL->points[i];
MoveAbsolute(src,CalcDest(src,left,down,right));
}
}
void SwapLists() {
List *temp;
temp=srcL;
srcL=destL;
destL=temp;
}
void ProcessList() {
SwapLists();
destL->length=0;
TryMoves(0,0,0); //ordered to favor lower fuel usage
TryMoves(1,0,0);
TryMoves(0,1,0);
TryMoves(0,0,1);
TryMoves(1,1,0);
TryMoves(0,1,1);
}
void FillPixMap() {
int x,y;
char s;
for(x=0;x<PWidth;x++) {
for(y=0;y<PHeight;y++) {
PixMap[x][y]=s=GetMapStateSlow(x,y);
if((s & PBlocked)==0) {
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) {
int steps=0;
FillPixMap();
ClearNodes();
printf("Spaces: %d\n",spaces);
push(pack(0,0,10,60,0,0)); //Starting position
while(destL->length) {
printf("\n%d %d",++steps,destL->length);
ProcessList();
}
printf("\n");
PrintMap();
return 0;
}