/* ======================================================================== */ /* CONTEST 9: Maze Solver (FAST version) */ /* Joseph Zbiciak, im14u2c@primenet.com. */ /* ======================================================================== */ /* ======================================================================== */ /* This program is free software; you can redistribute it and/or modify */ /* it under the terms of the GNU General Public License as published by */ /* the Free Software Foundation; either version 2 of the License, or */ /* (at your option) any later version. */ /* */ /* This program is distributed in the hope that it will be useful, */ /* but WITHOUT ANY WARRANTY; without even the implied warranty of */ /* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU */ /* General Public License for more details. */ /* */ /* You should have received a copy of the GNU General Public License */ /* along with this program; if not, write to the Free Software */ /* Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA. */ /* ======================================================================== */ /* Copyright (c) 2000, Joseph Zbiciak */ /* ======================================================================== */ /* ======================================================================== */ /* If your platform can safely perform non-aligned accesses, it may be a */ /* win to #define NONALIGN_OK here. */ /* ======================================================================== */ #define NONALIGN_OK #include #include #include #include #include #include #include #define MAX_X (256) #define MAX_Y (512) #define MAX_S (MAX_X * MAX_Y) char outbuf[1 << 24], *o = outbuf; /* 16 MB */ char *inbuf, *eof; char maze[MAX_Y * MAX_X]; char * start; /* D L R U */ const int dm[4] = { MAX_X, -1, 1, -MAX_X }; char * maze_loc_queue[MAX_S]; /* ======================================================================== */ /* SOLVE -- Breadth-first traversal of maze. */ /* ======================================================================== */ char *solve(void) { char **head; /* Head pointer in maze location queue. */ char **tail; /* Tail pointer in maze location queue. */ char *cur; /* Current location in maze. */ char *nbr; /* One of the neighbors to current location. */ /* -------------------------------------------------------------------- */ /* Seed our work-queue with a single node to the right of the 's' at */ /* the start. Our work-queue represents a "constant path-length */ /* contour" in the maze, and as soon as we touch 'f', we know we've */ /* found the shortest path from 's' to 'f'. We mark the cell to the */ /* right of 's' with a sentinel 'S', since we always move right into */ /* this cell. */ /* -------------------------------------------------------------------- */ head = tail = maze_loc_queue; *tail++ = start + 1; start[1] = 'S'; /* -------------------------------------------------------------------- */ /* While there are still active nodes in our work-queue, advance the */ /* contour. We advance down, left, right, and up in that order to */ /* meet the "alphabetical order" criteria in the contest rules. */ /* -------------------------------------------------------------------- */ while (head < tail) { cur = *head++; /* Get next position from queue */ /* ---------------------------------------------------------------- */ /* Very condensed: Try each of the four directions in turn, and */ /* enqueue that neighbor if that pathway is open. Also, mark that */ /* position with the direction we took to enter that position. */ /* We also test for 'f', but only when trying to move right. */ /* ---------------------------------------------------------------- */ nbr = cur + MAX_X; if(*nbr==' ') { *tail++ = nbr; *nbr=0; } /* Go D */ nbr = cur - 1; if(*nbr==' ') { *tail++ = nbr; *nbr=1; } /* Go L */ nbr = cur + 1; if(*nbr==' ') { *tail++ = nbr; *nbr=2; } /* Go R */ if (*nbr == 'f') { return cur; } /* Exit */ nbr = cur - MAX_X; if(*nbr==' ') { *tail++ = nbr; *nbr=3; } /* Go U */ } /* -------------------------------------------------------------------- */ /* If we get here, then we've covered all reachable parts of the maze */ /* and still have failed to find a solution. Return NULL -- failure. */ /* -------------------------------------------------------------------- */ return NULL; } char soln[MAX_S + 1]; /* temp buffer. */ /* ======================================================================== */ /* RETRACE -- Report solution by retracing solution path. */ /* ======================================================================== */ char *retrace(char *mp, int *len) { int m; char *s; /* -------------------------------------------------------------------- */ /* Start at the end of our solution string buffer and work backwards. */ /* Put the trailing newline there and indicate that we had moved */ /* right to get into that cell (always true in this contest). */ /* -------------------------------------------------------------------- */ s = &soln[MAX_S]; *s = '\n'; m = 2; /* -------------------------------------------------------------------- */ /* The last move is always 'R', so that's hard-coded. */ /* -------------------------------------------------------------------- */ *--s = 'R'; /* -------------------------------------------------------------------- */ /* Start at 'f' and step backwards towards 's', recording what our */ /* steps were. Write these into the solution buffer in reverse order */ /* since we're stepping backwards. The 'dm[]' array contains the */ /* pointer offsets that correspond to each of the four directions. */ /* The pointer 'mp' is our current position in the map, and 'm' is */ /* the move # that was made to move into that location. */ /* -------------------------------------------------------------------- */ do { *--s = "DLRU"[m]; mp -= dm[m]; } while ((m = *mp) != 'S'); /* -------------------------------------------------------------------- */ /* Finish off the string and report the final results' length. The */ /* first move is always 'R', so that's hard-coded. */ /* -------------------------------------------------------------------- */ *--s = 'R'; *len = &soln[MAX_S] - s + 1; return s; } /* ======================================================================== */ /* READ_MAZE -- Reads the next maze from the input to our work buffer. */ /* ======================================================================== */ int read_maze(void) { int x, len = 0; char *s, nc, *m; /* -------------------------------------------------------------------- */ /* Scan the input buffer and build up our maze array. */ /* -------------------------------------------------------------------- */ s = inbuf; m = maze; start = NULL; while (s < eof) { /* ---------------------------------------------------------------- */ /* Read a line from the maze. Do not grab the CR or LF at the */ /* ends of the lines. */ /* ---------------------------------------------------------------- */ x = 0; /* ---------------------------------------------------------------- */ /* If this isn't the last line of the maze, use an unrolled loop */ /* to copy the bulk of the maze contents over. */ /* ---------------------------------------------------------------- */ if (s[0] != '/') { #ifdef NONALIGN_OK unsigned *mm, *ss; int i; mm = (unsigned *)m; ss = (unsigned *)s; i = len >> 2; while (i-->0) *mm++ = *ss++; x += len & ~3; s += x; #else while (x < len) { m[x++] = *s++; m[x++] = *s++; m[x++] = *s++; m[x++] = *s++; } #endif } /* ---------------------------------------------------------------- */ /* Copy over the remaining bits. This is safely unrolled once, */ /* since end-of-line is two characters. */ /* ---------------------------------------------------------------- */ while (*s >= ' ') { m[x++] = *s++; m[x++] = *s++; } while (*s < ' ' && s < eof) s++; /* ---------------------------------------------------------------- */ /* If we see an 's', mark the start of the maze. If we see a */ /* '/', stop scanning and return. */ /* ---------------------------------------------------------------- */ if (m[0] == '/') { inbuf = s; return 0; } if (m[0] == 's') { start = m; } /* ---------------------------------------------------------------- */ /* Move to the next line of the maze buffer. */ /* ---------------------------------------------------------------- */ m += MAX_X; len = x - 4; } inbuf = s; return m > maze ? 0 : -1; } /* ======================================================================== */ /* MAIN -- Where the action is. */ /* ======================================================================== */ main() { int end_time, maze_num = 0; int fi, fo, ilen; FILE *fs; char *s, *f; int l; /* -------------------------------------------------------------------- */ /* Open our input and output files. mmap() the input file as a */ /* buffer in memory so that we can abuse the VM to do our disk reads. */ /* -------------------------------------------------------------------- */ fi = open("input2.txt", O_RDONLY, 0644); fo = open("output.txt", O_RDWR | O_CREAT | O_TRUNC, 0644); ilen = lseek(fi, 0, SEEK_END); inbuf = mmap(NULL, ilen, PROT_READ, MAP_PRIVATE, fi, 0); eof = inbuf + ilen; /* -------------------------------------------------------------------- */ /* Fault in the whole file. This speeds things up by avoiding faults */ /* during the middle of processing. Because we do all the faults */ /* in one place, the kernel fault-handling code stays hot in cache. */ /* -------------------------------------------------------------------- */ for (s = inbuf; s < eof; s += 4096) *(volatile char *)s; /* -------------------------------------------------------------------- */ /* Open the 'seconds.txt' file to get our time limit, or assume 30 */ /* seconds if the file does not exist. */ /* -------------------------------------------------------------------- */ fs = fopen("seconds.txt", "r"); if (fs) { fscanf(fs, "%d", &end_time); } else { end_time = 30; } end_time += time(0); /* -------------------------------------------------------------------- */ /* Solve mazes while we still have time! */ /* -------------------------------------------------------------------- */ while (time(0) < end_time && read_maze() >= 0) { maze_num++; /* ---------------------------------------------------------------- */ /* If the solver doesn't find 'f', report 'no answer', else */ /* retrace and report the solution. */ /* ---------------------------------------------------------------- */ if ((f = solve()) == NULL) { s = "no answer\n"; l = 10; } else { s = retrace(f, &l); } memcpy(o, s, l); o += l; } /* -------------------------------------------------------------------- */ /* Fire off our output buffer to output.txt. */ /* -------------------------------------------------------------------- */ write(fo, outbuf, o - outbuf); close(fo); /* -------------------------------------------------------------------- */ /* DONE! Return "SUCCESS." */ /* -------------------------------------------------------------------- */ return 0; }