/* * Program to brute-force solutions to Ricochet Robots problems. * * Ricochet Robots is a commercial game which turns a puzzle into a * multiplayer game. This program is about the underlying puzzle, not * the game. * * The physical equipment of the game consists of a game board which * comes in four double-sided pieces, each of which can be placed * either side up and has one distinguished corner. The four * distinguished corners are placed together to form the centre of the * board. Considering rotations as identical, this can be done in 96 * ways: 4! (orderings of the pieces) times 2^4 (each piece either * side up) divided by 4 (the reduction factor for rotations being * considered identical - the resulting board is square). The * resulting 16x16 board has walls printed around the outside edge, * two unit walls projecting in from each side, and 17 interior * squares with two adjacent walls printed and a coloured goal symbol * on the square. The other squares are blank. There is also a * plastic piece which has no game function; all it does is to hold * the board together by the centre - the distinguished corners have * holes in them which the plastic piece fits into. There are five * plastic shapes (red, green, blue, yellow, and silver), representing * robots, and five small chips of matching colours, suitable for * placing in a square and placing a robot on. There are then * seventeen small circular chips, with one side identical and the * other bearing copies of the symbols on the 17 goal squares. 16 of * these symbols are coloured red, green, blue, and yellow, matching * four of the robots' colours; the 17th is a swirl made up of all the * colours - the documentation calls it the `vortex' and the graphic * is appropriate to the name. There is also a timer, which serves no * purpose when viewing the thing as a puzzle; it has function only in * the conversion of that puzzle to a multiplayer game. In order to * arrange that all 17 goal squares appear regardless of how the board * is built, each board piece has the same goal squares on each side, * just with them, and the walls, arranged differently. * * The puzzle consists of turning up a chip and finding a way to get * the robot of that colour to the goal square which matches the chip, * preferably in as few moves as possible. (The way this is converted * to a multiplayer game, while clever, is not relevant to the puzzle * point of view and I will thus ignore it here.) There are, of * course, constraints on robots' motions, or there would be no * puzzle. * * Robots move orthogonally only, somewhat like the chess rook. * However, they cannot move through walls or other robots, and, once * they start moving, they cannot stop until they run into a wall or * another robot - it is not possible for them to stop before that. * So, from a given position, each robot has at most four moves, one * in each of the four cardinal directions. (It may have fewer, if * it's immediately blocked by a wall or robot in some or all of those * directions.) There are two additional restrictions: the target * robot (the one of the colour turned) must make at least one * 90-degree turn before reaching the goal, and a robot may not make a * 180-degree turn without another robot moving in between. (The * former is apparently designed to deal with cases where a robot can * move directly to its goal; the latter, to deal with a possible * reaction to the former.) This program ignores the former; given * that, the latter is completely pointless and is ignored too. * * For example, as a much-smaller example, consider this mini-puzzle, * where * is the goal spot, R is the target robot, and a and b are * other robots: * * +---+---+---+---+---+ * | a | | * + + + + + + * | | * | * + +---+ +---+ + * | | | * +---+ + + + + * | R b | * + + + + +---+ * | | | * +---+---+---+---+---+ * * This particular puzzle has a fairly easy solution in 4 moves: b up, * R right, R up, R left. (It has other solutions; for example, it * can be solved in 7 moves without moving either a or b - move R * right, up, right, up, left, down, left - or 6 by moving a but not * b, with a right, R up, R left, R up, R right, R down.) * * We do simple breadth-first search. A board position is represented * as a 40-bit number, with four bits each representing X and Y * coordinates for each of the five robots. (There is a little * redundancy in this representation, in that it can represent * multiple robots on the same square, which is impossible, and that * it can represent robots on the inaccessible four centre cells. The * actual number of possible positions is 252*251*250*249*248, or * 976484376000, as compared to 2^40=1099511627776 possible * representations, for about 11% wastage - about 11% of the possible * representations represent impossible positions. We ignore this * waste, especially since it is much less than one bit, and allows us * to support the game's choice of not using the silver robot by * including the four walls interior to the centre and placing the * silver robot on one of those squares, so it is never able to move.) * The walls are represented separately, since they do not change when * working on any particular puzzle; only the robots' positions * change, so that is the only part we care about storing compactly. * * Breadth-first search like this requires that we know when we've * found a position again. We store a maximum of MAXPOSN positions, * keeping them in a hash table of HTSIZE entries; however, positions * are moderately large (13 bytes of persistent storage; in the queue * of nodes to search, either 20 or 24 bytes each (on amd64) depending * on whether the compiler decides to pad struct pq), so the hash * table just contains int indices into the posn[], pdepth[], and * pfrom[] arrays. (In a sense, these should be an array of structs, * but either it'd have to be packed and pay big performance penalties * or be non-packed and pay big padding wastage penalties.) * * Ideally MAXPOSN and HTSIZE would be dynamic, but then we have to * deal with rehashing and suchlike. * * The puzzle is read from stdin. Some aspects of it are hardwired, * perhaps most notably (a) the board is always 16x16 and (b) there * are always exactly five robots involved. (To run a problem with * fewer than five robots, such as the "not using the silver robot" * kind, place the unused robot(s) inside the board centre, so they * cannot move at all.) There are three input formats supported: * * - A text listing of walls and robot locations. * - An ascii-graphics rendition of the whole puzzle. * - A brief summary based on the physical game. * * The text format consists of zero or more wall lines followed by one * target line and then five robot lines. Wall lines look like * * X Y DIR * * where X and Y are decimal numbers and DIR is a single letter L, R, * U, or D. For the directions to make sense, the puzzle needs to be * considered to be in the fourth quadrant, ie, with (0,0) at upper * left: L is decreasing X, R is increasing X, U is decreasing Y, and * D is increasing Y. Walls are always bidirectional; for example, if * "5 2 R" is specified, "6 2 L" is implied and need not actually be * given. Robot lines look like * * ROBOT X Y * * where ROBOT is a single character r, g, b, y, or s, or for the * target robot R, G, B, Y, or S, and X and Y are as for wall lines. * The target line specifies where the target robot should go and * looks like a robot line with a * for the robot character. * * The ascii-graphics format consists of a framework * * +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+ * | | * + + + + + + + + + + + + + + + + + * | | * + + + + + + + + + + + + + + + + + * | | * + + + + + + + + + + + + + + + + + * | | * + + + + + + + + + + + + + + + + + * | | * + + + + + + + + + + + + + + + + + * | | * + + + + + + + + + + + + + + + + + * | | * + + + + + + + + + + + + + + + + + * | | * + + + + + + + + + + + + + + + + + * | | * + + + + + + + + + + + + + + + + + * | | * + + + + + + + + + + + + + + + + + * | | * + + + + + + + + + + + + + + + + + * | | * + + + + + + + + + + + + + + + + + * | | * + + + + + + + + + + + + + + + + + * | | * + + + + + + + + + + + + + + + + + * | | * + + + + + + + + + + + + + + + + + * | | * +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+ * * with some of the internal walls filled in with | (for vertical * walls) or --- (for horizontal walls) replacing spaces. Robot * locations are indicated with r, g, b, y, and s characters, with the * target robot's character uppercase (R, G, B, Y, or S); the goal * cell is marked with a *. The marking character for a cell can * replace any of the three spaces representing the cell's interior. * * The version based on the phiysical game describes the board by * giving the four quarters and which side up they are, as in * * 2A 1B * 3B 4A * * followed by a target spec (see below) and then robot locations as * described above for the text format. The board quarters are given * here as if for the upper-left corner of the ascii-graphics form; * they are automatically rotated as appropriate. The target is * either a target spec as described for the text format, above, or * one of the two-letter codes appearing the descriptions below. * * 1A +---+---+---+---+---+---+---+---+ * | | * + + +---+ + + + + + * | | Ya * + + + + + + + + + * | * + + + + + + + + + * | | Bb * + + + + + + +---+ + * | * +---+ + + +---+ + + + * | Rd | * + + + + + + + + + * | Gc | * + +---+ + + + + +---+ * | | | * + + + + + + + +---+ * * 1B +---+---+---+---+---+---+---+---+ * | | * + + + + + + + + + * | Gc | * + + + + + +---+ + + * | | Rd * + +---+ + + + + + + * | * +---+ + + + + +---+ + * | | Ya * + + + + + + + + + * | * + + +---+ + + + + + * | Bb | * + + + + + + + +---+ * | | | * + + + + + + + +---+ * * 2A +---+---+---+---+---+---+---+---+ * | | * + + + + +---+ + + + * | | Ra * + +---+ + + + + + + * | Gb | * + + + + + + + + + * | Yc | * + + + + + + +---+ + * | * + + + + + + + + + * | * +---+ + + + + + + + * | | Bd * + + + +---+ + + +---+ * | | | * + + + + + + + +---+ * * 2B +---+---+---+---+---+---+---+---+ * | | * + + + + + + + + + * | Yc | * + +---+ + + + +---+ + * | | Gb * + + + + + + + + + * | * + + + + + + + + + * | * + + + + + + +---+ + * | Bd | * +---+ + + + + + + + * | | Ra * + + + +---+ + + +---+ * | | | * + + + + + + + +---+ * * 3A +---+---+---+---+---+---+---+---+ * | | * + + + + + + + + + * | | Rb * + +---+ + + + +---+ + * | Ga | * + + + + + + + + + * | * + + + + + + + + + * | Bc | * + + +---+ + + + +---+ * | | Yd * +---+ + + + + + + + * | * + + + + + + + +---+ * | | | * + + + + + + + +---+ * * 3B +---+---+---+---+---+---+---+---+ * | | * + + + + + + + + + * | * + + + + + + + + + * | Bc | * + + + + + +---+ + + * | * + + +---+ + + + + + * | Ga | * +---+ + + + + + + + * | | Rb * + +---+ + + + + +---+ * | | Yd * + + + + + + + +---+ * | | | * + + + + + + + +---+ * * 4A +---+---+---+---+---+---+---+---+ * | | * + + + + + + + + + * | | Ba * + + + + + + +---+ + * | * + +---+ + + + + + + * | Yb | * + + + + + +---+ + + * | | Gd * + + + + + + + + + * | Rc | Vx | * + + +---+ + + + +---+ * | * +---+ + + + + + +---+ * | | | * + + + + + + + +---+ * * 4B +---+---+---+---+---+---+---+---+ * | | * + + + + + + + + + * | Rc | * + + +---+ + + + + + * | * + + + + + + + + + * | | Gd * + +---+ + + + +---+ + * | | Yb * +---+ + + + + + + + * | * + + + + + +---+ + + * | Ba | * + + + + + + + +---+ * | Vx | | | * + + + +---+ + + +---+ * * The two-letter codes merely specify the goal square; using, for * example, Gb as the goal square does not mean that the G robot is * the target robot (though the commercial game does impose that). * * Note that there cannot be more than one target robot; there is no * direct support for the "when the vortex is the target any robot can * go there" semantic. Such problems must be represented by doing * multiple runs, naming each of the robots in turn as the target * robot and seeing which one comes up with the shortest answer. */ #include #include #include #include #include extern const char *__progname; #define MAXPOSN 16777216 #define HTSIZE 33554467 typedef struct binit BINIT; typedef struct pq PQ; typedef struct rshift RSHIFT; typedef struct gp GP; typedef struct quarter QUARTER; typedef struct wallinit WALLINIT; typedef struct robot ROBOT; struct robot { char lc; char uc; unsigned char contents; int shift; } ; struct gp { char name[2]; int x; int y; } ; struct wallinit { int x; int y; unsigned char dir; } ; struct quarter { WALLINIT walls[13]; GP goals[6]; } ; struct rshift { int s; unsigned char fill; char c; } ; struct binit { unsigned char x; unsigned char y; unsigned char bit; } ; typedef unsigned long long int POSN; #define POSN_S_R_R 0 #define POSN_S_R_G 8 #define POSN_S_R_B 16 #define POSN_S_R_Y 24 #define POSN_S_R_S 32 #define POSN_S_L_X 0 #define POSN_S_L_Y 4 #define POSN_MASK ((POSN)0xf) struct pq { PQ *link; POSN p; int from; } ; static unsigned char board[16][16]; #define WALLS 0xf0 #define WALL_L 0x10 #define WALL_U 0x20 #define WALL_R 0x40 #define WALL_D 0x80 #define CONTENTS 0x0f #define C_EMPTY 0x00 #define C_R_R 0x01 #define C_R_G 0x02 #define C_R_B 0x03 #define C_R_Y 0x04 #define C_R_S 0x05 static unsigned char pdepth[MAXPOSN]; static int pfrom[MAXPOSN]; static POSN posn[MAXPOSN]; static int nposn; static int htbl[HTSIZE]; static PQ *freepq = 0; static POSN startpos; static POSN goalmask; static POSN goalval; static const ROBOT robots[5] = { { 'r', 'R', C_R_R, POSN_S_R_R }, { 'g', 'G', C_R_G, POSN_S_R_G }, { 'b', 'B', C_R_B, POSN_S_R_B }, { 'y', 'Y', C_R_Y, POSN_S_R_Y }, { 's', 'S', C_R_S, POSN_S_R_S } }; static const QUARTER quarters[4][2] = { { { /* [0][0] = 1A */ { { 4, 0, WALL_R }, { 0, 4, WALL_D }, { 2, 1, WALL_L }, { 2, 1, WALL_U }, { 6, 3, WALL_L }, { 6, 3, WALL_D }, { 4, 5, WALL_U }, { 4, 5, WALL_R }, { 1, 6, WALL_R }, { 1, 6, WALL_D }, { -1 } }, { { { 'Y', 'a' }, 2, 1 }, { { 'B', 'b' }, 6, 3 }, { { 'R', 'd' }, 4, 5 }, { { 'G', 'c' }, 1, 6 }, { { '\0' } } } }, { /* [0][1] = 1B */ { { 3, 0, WALL_R }, { 0, 3, WALL_D }, { 5, 1, WALL_R }, { 5, 1, WALL_D }, { 1, 2, WALL_L }, { 1, 2, WALL_D }, { 6, 4, WALL_U }, { 6, 4, WALL_L }, { 2, 6, WALL_U }, { 2, 6, WALL_R }, { -1 } }, { { { 'G', 'c' }, 5, 1 }, { { 'R', 'd' }, 1, 2 }, { { 'Y', 'a' }, 6, 4 }, { { 'B', 'b' }, 2, 6 }, { { '\0' } } } } }, { { /* [1][0] = 2A */ { { 1, 0, WALL_R }, { 0, 5, WALL_D }, { 4, 1, WALL_U }, { 4, 1, WALL_L }, { 1, 2, WALL_U }, { 1, 2, WALL_R }, { 6, 3, WALL_R }, { 6, 3, WALL_D }, { 3, 6, WALL_L }, { 3, 6, WALL_D }, { -1 } }, { { { 'R', 'a' }, 4, 1 }, { { 'G', 'b' }, 1, 2 }, { { 'Y', 'c' }, 6, 3 }, { { 'B', 'd' }, 3, 6 }, { { '\0' } } } }, { /* [1][1] = 2B */ { { 4, 0, WALL_R }, { 0, 5, WALL_D }, { 6, 1, WALL_R }, { 6, 1, WALL_D }, { 1, 2, WALL_U }, { 1, 2, WALL_L }, { 6, 5, WALL_U }, { 6, 5, WALL_R }, { 3, 6, WALL_L }, { 3, 6, WALL_D }, { -1 } }, { { { 'Y', 'c' }, 6, 1 }, { { 'G', 'b' }, 1, 2 }, { { 'B', 'd' }, 6, 5 }, { { 'R', 'a' }, 3, 6 }, { { '\0' } } } } }, { { /* [2][0] = 3A */ { { 3, 0, WALL_R }, { 0, 5, WALL_D }, { 1, 1, WALL_L }, { 1, 1, WALL_D }, { 6, 2, WALL_U }, { 6, 2, WALL_R }, { 2, 4, WALL_R }, { 2, 4, WALL_D }, { 7, 5, WALL_U }, { 7, 5, WALL_L }, { -1 } }, { { { 'R', 'b' }, 1, 1 }, { { 'G', 'a' }, 6, 2 }, { { 'B', 'c' }, 2, 4 }, { { 'Y', 'd' }, 7, 5 }, { { '\0' } } } }, { /* [2][1] = 3B */ { { 3, 0, WALL_R }, { 0, 4, WALL_D }, { 5, 2, WALL_R }, { 5, 2, WALL_D }, { 2, 4, WALL_U }, { 2, 4, WALL_R }, { 7, 5, WALL_L }, { 7, 5, WALL_D }, { 1, 6, WALL_U }, { 1, 6, WALL_L }, { -1 } }, { { { 'B', 'c' }, 5, 2 }, { { 'G', 'a' }, 2, 4 }, { { 'R', 'b' }, 7, 5 }, { { 'Y', 'd' }, 1, 6 }, { { '\0' } } } } }, { { /* [3][0] = 4A */ { { 3, 0, WALL_R }, { 0, 6, WALL_D }, { 6, 1, WALL_L }, { 6, 1, WALL_D }, { 1, 3, WALL_U }, { 1, 3, WALL_R }, { 5, 4, WALL_U }, { 5, 4, WALL_L }, { 2, 5, WALL_R }, { 2, 5, WALL_D }, { 7, 5, WALL_R }, { 7, 5, WALL_D }, { -1 } }, { { { 'B', 'a' }, 6, 1 }, { { 'Y', 'b' }, 1, 3 }, { { 'G', 'd' }, 5, 4 }, { { 'R', 'c' }, 2, 5 }, { { 'V', 'x' }, 7, 5 }, { { '\0' } } } }, { /* [3][1] = 4B */ { { 4, 0, WALL_R }, { 0, 4, WALL_D }, { 2, 1, WALL_R }, { 2, 1, WALL_D }, { 1, 3, WALL_L }, { 1, 3, WALL_D }, { 6, 4, WALL_U }, { 6, 4, WALL_L }, { 5, 6, WALL_U }, { 5, 6, WALL_R }, { 3, 7, WALL_R }, { 3, 7, WALL_D }, { -1 } }, { { { 'R', 'c' }, 2, 1 }, { { 'G', 'd' }, 1, 3 }, { { 'Y', 'b' }, 6, 4 }, { { 'B', 'a' }, 5, 6 }, { { 'V', 'x' }, 3, 7 }, { { '\0' } } } } } }; static RSHIFT rsv[] = { { POSN_S_R_R, C_R_R, 'R' }, { POSN_S_R_G, C_R_G, 'G' }, { POSN_S_R_B, C_R_B, 'B' }, { POSN_S_R_Y, C_R_Y, 'Y' }, { POSN_S_R_S, C_R_S, 'S' } }; static void setwall(int x, int y, unsigned char bit) { if ((x < 0) || (x > 15) || (y < 0) || (y > 15)) abort(); board[x][y] |= bit; switch (bit) { case WALL_L: if (x == 0) abort(); board[x-1][y] |= WALL_R; break; case WALL_R: if (x == 15) abort(); board[x+1][y] |= WALL_L; break; case WALL_U: if (y == 0) abort(); board[x][y-1] |= WALL_D; break; case WALL_D: if (y == 15) abort(); board[x][y+1] |= WALL_U; break; default: abort(); break; } } static void read_lines(FILE *f, void (*fn)(const char *)) { char *lb; int la; int ln; int c; void save(int ch) { if (ln >= la) lb = realloc(lb,la=ln+8); lb[ln++] = ch; } lb = 0; la = 0; ln = 0; while <"reading"> (1) { c = getc(f); switch (c) { case EOF: if (ln > 0) { case '\n': save('\0'); (*fn)(lb); ln = 0; break; } break <"reading">; default: save(c); break; } } free(lb); } static void init_board(void) { int i; int j; for (i=16-1;i>=0;i--) { for (j=16-1;j>=0;j--) { board[i][j] = C_EMPTY; } } for (i=16-1;i>=0;i--) { board[i][0] |= WALL_U; board[i][15] |= WALL_D; board[0][i] |= WALL_L; board[15][i] |= WALL_R; } } static void read_problem_asciigraphic(FILE *f) { int x; int y; int c[4]; unsigned int row[16]; #define ROW_GOAL 0x100 #define ROW_TARGET 0x200 int havegoal; POSN gv; int gs; POSN gotr; int gots; char rch; void flushtrailer(char expect) { int c; c = getc(f); if (c != expect) { fprintf(stderr,"%s: corrupted ascii-graphics problem (no trailing %c at %d)\n",__progname,expect,y); exit(1); } while (1) { c = getc(f); if (c == EOF) { fprintf(stderr,"%s: corrupted ascii-graphics problem (premature EOF flushing trailer for %d)\n",__progname,y); exit(1); } if (c == '\n') break; } } void get4(void) { c[0] = getc(f); c[1] = getc(f); c[2] = getc(f); c[3] = getc(f); } void read_plus_row(void) { int x; for (x=0;x<16;x++) { get4(); if ((c[0] == '+') && (c[1] == ' ') && (c[2] == ' ') && (c[3] == ' ')) { row[x] = 0; } else if ((c[0] == '+') && (c[1] == '-') && (c[2] == '-') && (c[3] == '-')) { row[x] = 1; } else { fprintf(stderr,"%s: corrupted ascii-graphics problem (incorrect H at (%d,%d))\n",__progname,x,y); exit(1); } } flushtrailer('+'); } void read_cell_row(void) { int x; int i; int n; unsigned int fill; for (x=0;x<16;x++) { get4(); switch (c[0]) { case ' ': fill = 0; break; case '|': fill = WALL_L; break; default: fprintf(stderr,"%s: corrupted ascii-graphics problem (bad V at (%d,%d))\n",__progname,x,y); exit(1); } n = 3; for (i=1;i<4;i++) { switch (c[i]) { case ' ': n --; break; case '*': fill |= ROW_GOAL; break; case 'r': fill |= C_R_R; break; case 'g': fill |= C_R_G; break; case 'b': fill |= C_R_B; break; case 'y': fill |= C_R_Y; break; case 's': fill |= C_R_S; break; case 'R': fill |= C_R_R | ROW_TARGET; break; case 'G': fill |= C_R_G | ROW_TARGET; break; case 'B': fill |= C_R_B | ROW_TARGET; break; case 'Y': fill |= C_R_Y | ROW_TARGET; break; case 'S': fill |= C_R_S | ROW_TARGET; break; } } if (n > 1) { fprintf(stderr,"%s: corrupted ascii-graphics problem (multiple contents at (%d,%d))\n",__progname,x,y); exit(1); } row[x] = fill; } flushtrailer('|'); } havegoal = 0; gv = 0; gs = -1; gotr = 0; read_plus_row(); for (x=0;x<16;x++) { if (! row[x]) { fprintf(stderr,"%s: corrupted ascii-graphics problem (missing H border wall at top %d)\n",__progname,x); exit(1); } } for (y=0;y<16;y++) { if (y) { read_plus_row(); for (x=0;x<16;x++) if (row[x]) setwall(x,y,WALL_U); } read_cell_row(); for (x=0;x<16;x++) { if (row[x] & WALL_L) { if (x) setwall(x,y,WALL_L); } else { if (! x) { fprintf(stderr,"%s: corrupted ascii-graphics problem (missing V border wall at left %d)\n",__progname,y); exit(1); } } if (row[x] & ROW_GOAL) { if (havegoal) { fprintf(stderr,"%s: corrupted ascii-graphics problem (goal specified multiple times)\n",__progname); exit(1); } havegoal = 1; gv = (((POSN)x) << POSN_S_L_X) | (((POSN)y) << POSN_S_L_Y); } if (row[x] & ROW_TARGET) { if (gs >= 0) { fprintf(stderr,"%s: corrupted ascii-graphics problem (target robot specified multiple times)\n",__progname); exit(1); } switch (row[x] & CONTENTS) { default: abort(); break; case C_R_R: gs = POSN_S_R_R; break; case C_R_G: gs = POSN_S_R_G; break; case C_R_B: gs = POSN_S_R_B; break; case C_R_Y: gs = POSN_S_R_Y; break; case C_R_S: gs = POSN_S_R_S; break; } } rch = '\0'; switch (row[x] & CONTENTS) { case 0: break; case C_R_R: gots = POSN_S_R_R; rch = 'R'; break; case C_R_G: gots = POSN_S_R_G; rch = 'G'; break; case C_R_B: gots = POSN_S_R_B; rch = 'B'; break; case C_R_Y: gots = POSN_S_R_Y; rch = 'Y'; break; case C_R_S: gots = POSN_S_R_S; rch = 'S'; break; } if (rch) { if (gotr & (((POSN)1) << gots)) { fprintf(stderr,"%s: corrupted ascii-graphics problem (%c robot position specified multiple times)\n",__progname,rch); exit(1); } startpos |= ((((POSN)x) << POSN_S_L_X) | (((POSN)y) << POSN_S_L_Y)) << gots; gotr |= ((POSN)1) << gots; } } } read_plus_row(); for (x=0;x<16;x++) { if (! row[x]) { fprintf(stderr,"%s: corrupted ascii-graphics problem (missing H border wall at bottom %d)\n",__progname,x); exit(1); } } if (! havegoal) { fprintf(stderr,"%s: corrupted ascii-graphics problem (goal position not specified)\n",__progname); exit(1); } if (gs < 0) { fprintf(stderr,"%s: corrupted ascii-graphics problem (no target robot specified)\n",__progname); exit(1); } goalmask = ((POSN_MASK << POSN_S_L_X) | (POSN_MASK << POSN_S_L_Y)) << gs; goalval = gv << gs; if ( gotr != ( (((POSN)1) << POSN_S_R_R) | (((POSN)1) << POSN_S_R_G) | (((POSN)1) << POSN_S_R_B) | (((POSN)1) << POSN_S_R_Y) | (((POSN)1) << POSN_S_R_S) ) ) { fprintf(stderr,"%s: corrupted ascii-graphics problem (robot positions not all specified)\n",__progname); exit(1); } } static void read_problem_game(FILE *f) { char nm[3]; int i; int j; int k; int x; int y; unsigned int gotq; const QUARTER *q; GP gps[17]; int ngps; int n; int ts; POSN gm; int rotate_xy_x(int x, int y, int r) { switch (r) { case 0: return(x); break; case 1: return(15-y); break; case 2: return(15-x); break; case 3: return(y); break; } abort(); } int rotate_xy_y(int x, int y, int r) { switch (r) { case 0: return(y); break; case 1: return(x); break; case 2: return(15-y); break; case 3: return(15-x); break; } abort(); } int rotate_dir(unsigned char d, int r) { switch (r) { case 0: return(d); break; case 1: switch (d) { case WALL_L: return(WALL_U); break; case WALL_U: return(WALL_R); break; case WALL_R: return(WALL_D); break; case WALL_D: return(WALL_L); break; } break; case 2: switch (d) { case WALL_L: return(WALL_R); break; case WALL_U: return(WALL_D); break; case WALL_R: return(WALL_L); break; case WALL_D: return(WALL_U); break; } break; case 3: switch (d) { case WALL_L: return(WALL_D); break; case WALL_U: return(WALL_L); break; case WALL_R: return(WALL_U); break; case WALL_D: return(WALL_R); break; } break; } abort(); } void line(const char *l) { int x; int y; char c; int s; int target; unsigned char v; const char *what; if (sscanf(l," %c%d%d",&c,&x,&y) == 3) { switch (c) { default: fprintf(stderr,"%s: corrupted game-format problem (bad key character %c)\n",__progname,c); exit(1); break; case 'r': v = C_R_R; s = POSN_S_R_R; target = 0; what = "R"; break; case 'g': v = C_R_G; s = POSN_S_R_G; target = 0; what = "G"; break; case 'b': v = C_R_B; s = POSN_S_R_B; target = 0; what = "B"; break; case 'y': v = C_R_Y; s = POSN_S_R_Y; target = 0; what = "Y"; break; case 's': v = C_R_S; s = POSN_S_R_S; target = 0; what = "S"; break; case 'R': v = C_R_R; s = POSN_S_R_R; target = 1; what = "R"; break; case 'G': v = C_R_G; s = POSN_S_R_G; target = 1; what = "G"; break; case 'B': v = C_R_B; s = POSN_S_R_B; target = 1; what = "B"; break; case 'Y': v = C_R_Y; s = POSN_S_R_Y; target = 1; what = "Y"; break; case 'S': v = C_R_S; s = POSN_S_R_S; target = 1; what = "S"; break; } if ((x < 0) || (x > 15) || (y < 0) || (y > 15)) { fprintf(stderr,"%s: corrupted game-format problem (%s location (%d,%d) out of range)\n",__progname,what,x,y); exit(1); } switch (target) { default: abort(); break; case 1: if (ts >= 0) { fprintf(stderr,"%s: corrupted game-format problem (target robot specified multiple times)\n",__progname); exit(1); } ts = s; /* fall through */ case 0: if (gm & (((POSN)1) << s)) { fprintf(stderr,"%s: corrupted game-format problem (%s robot position specified multiple times)\n",__progname,what); exit(1); } gm |= ((POSN)1) << s; startpos |= ((((POSN)x) << POSN_S_L_X) | (((POSN)y) << POSN_S_L_Y)) << s; break; } } else { fprintf(stderr,"%s: corrupted game-format problem (unparseable line `%s')\n",__progname,l); exit(1); } } gotq = 0; ngps = 0; for (n=0;n<4;n++) { static const int r[4] = { 0, 1, 3, 2 }; if (fscanf(f,"%2s",&nm[0]) != 1) { fprintf(stderr,"%s: corrupted game-format problem (can't scan quarter %d name)\n",__progname,n+1); exit(1); } for (i=4-1;i>=0;i--) for (j=2-1;j>=0;j--) { q = &quarters[i][j]; if ((nm[0] == "1234"[i]) && (nm[1] == "AB"[j])) { if (gotq & (1 << i)) { fprintf(stderr,"%s: corrupted game-format problem (quarter %c occurs multiple times)\n",__progname,nm[0]); exit(1); } for (k=0;q->walls[k].x>=0;k++) { setwall( rotate_xy_x(q->walls[k].x,q->walls[k].y,r[n]), rotate_xy_y(q->walls[k].x,q->walls[k].y,r[n]), rotate_dir(q->walls[k].dir,r[n]) ); } setwall(rotate_xy_x(7,7,r[n]),rotate_xy_y(7,7,r[n]),rotate_dir(WALL_L,r[n])); setwall(rotate_xy_x(7,7,r[n]),rotate_xy_y(7,7,r[n]),rotate_dir(WALL_R,r[n])); setwall(rotate_xy_x(7,7,r[n]),rotate_xy_y(7,7,r[n]),rotate_dir(WALL_U,r[n])); setwall(rotate_xy_x(7,7,r[n]),rotate_xy_y(7,7,r[n]),rotate_dir(WALL_D,r[n])); for (k=0;q->goals[k].name[0];k++) { if (ngps >= 17) abort(); gps[ngps++] = (GP) { .name = { q->goals[k].name[0], q->goals[k].name[1] }, .x = rotate_xy_x(q->goals[k].x,q->goals[k].y,r[n]), .y = rotate_xy_y(q->goals[k].x,q->goals[k].y,r[n]) }; } } } } if (ngps != 17) abort(); fscanf(f," "); i = getc(f); if (i == EOF) { fprintf(stderr,"%s: corrupted game-format problem (nothing after quarters)\n",__progname); exit(1); } switch (i) { case '*': if (fscanf(f,"%d%d",&x,&y) != 2) { fprintf(stderr,"%s: corrupted game-format problem (can't scan target location)\n",__progname); exit(1); } break; case 'R': case 'G': case 'B': case 'Y': case 'V': nm[0] = i; nm[1] = getc(f); do <"found"> { for (i=17-1;i>=0;i--) { if ((nm[0] == gps[i].name[0]) && (nm[1] == gps[i].name[1])) break <"found">; } fprintf(stderr,"%s: corrupted game-format problem (unrecognized target location %c%c)\n",__progname,nm[0],nm[1]); exit(1); } while (0); x = gps[i].x; y = gps[i].y; break; } do { i = getc(f); if (i == EOF) { fprintf(stderr,"%s: corrupted game-format problem (premature EOF)\n",__progname); exit(1); } } while (i != '\n'); ts = -1; gm = 0; read_lines(f,&line); if (ts < 0) { fprintf(stderr,"%s: corrupted game-format problem (no target robot specified)\n",__progname); exit(1); } if ( gm != ( (((POSN)1) << POSN_S_R_R) | (((POSN)1) << POSN_S_R_G) | (((POSN)1) << POSN_S_R_B) | (((POSN)1) << POSN_S_R_Y) | (((POSN)1) << POSN_S_R_S) ) ) { fprintf(stderr,"%s: corrupted game-format problem (robot positions not all specified)\n",__progname); exit(1); } goalmask = ((POSN_MASK << POSN_S_L_X) | (POSN_MASK << POSN_S_L_Y)) << ts; goalval = ((((POSN)x) << POSN_S_L_X) | (((POSN)y) << POSN_S_L_Y)) << ts; } static void read_problem_text(FILE *f) { int lno; int tx; int ty; int ts; POSN gm; void line(const char *l) { int x; int y; char c; int bad; int s; int target; unsigned char v; const char *what; lno ++; if (sscanf(l,"%d%d %c",&x,&y,&c) == 3) { switch (c) { case 'L': bad = (x == 0); v = WALL_L; break; case 'R': bad = (x == 15); v = WALL_R; break; case 'U': bad = (y == 0); v = WALL_U; break; case 'D': bad = (y == 15); v = WALL_D; break; default: fprintf(stderr,"%s: corrupted text-mode problem, line %d (bad direction character %c)\n",__progname,lno,c); exit(1); } if ((x < 0) || (x > 15) || (y < 0) || (y > 15)) { fprintf(stderr,"%s: corrupted text-mode problem, line %d (cell location (%d,%d) out of range)\n",__progname,lno,x,y); exit(1); } if (bad) { fprintf(stderr,"%s: corrupted text-mode problem, line %d (direction goes outside grid)\n",__progname,lno); exit(1); } setwall(x,y,v); } else if (sscanf(l," %c%d%d",&c,&x,&y) == 3) { switch (c) { default: fprintf(stderr,"%s: corrupted text-mode problem, line %d (bad key character %c)\n",__progname,lno,c); exit(1); break; case '*': target = 2; what = "goal"; break; case 'r': v = C_R_R; s = POSN_S_R_R; target = 0; what = "R"; break; case 'g': v = C_R_G; s = POSN_S_R_G; target = 0; what = "G"; break; case 'b': v = C_R_B; s = POSN_S_R_B; target = 0; what = "B"; break; case 'y': v = C_R_Y; s = POSN_S_R_Y; target = 0; what = "Y"; break; case 's': v = C_R_S; s = POSN_S_R_S; target = 0; what = "S"; break; case 'R': v = C_R_R; s = POSN_S_R_R; target = 1; what = "R"; break; case 'G': v = C_R_G; s = POSN_S_R_G; target = 1; what = "G"; break; case 'B': v = C_R_B; s = POSN_S_R_B; target = 1; what = "B"; break; case 'Y': v = C_R_Y; s = POSN_S_R_Y; target = 1; what = "Y"; break; case 'S': v = C_R_S; s = POSN_S_R_S; target = 1; what = "S"; break; } if ((x < 0) || (x > 15) || (y < 0) || (y > 15)) { fprintf(stderr,"%s: corrupted text-mode problem, line %d (%s location (%d,%d) out of range)\n",__progname,lno,what,x,y); exit(1); } switch (target) { default: abort(); break; case 2: if (tx >= 0) { fprintf(stderr,"%s: corrupted text-mode problem, line %d (goal specified multiple times)\n",__progname,lno); exit(1); } tx = x; ty = y; break; case 1: if (ts >= 0) { fprintf(stderr,"%s: corrupted text-mode problem, line %d (target robot specified multiple times)\n",__progname,lno); exit(1); } ts = s; /* fall through */ case 0: if (gm & (((POSN)1) << s)) { fprintf(stderr,"%s: corrupted text-mode problem, line %d (%s robot position specified multiple times)\n",__progname,lno,what); exit(1); } gm |= ((POSN)1) << s; startpos |= ((((POSN)x) << POSN_S_L_X) | (((POSN)y) << POSN_S_L_Y)) << s; break; } } else { fprintf(stderr,"%s: corrupted text-mode problem, line %d (unparseable line)\n",__progname,lno); exit(1); } } tx = -1; ts = -1; gm = 0; lno = 0; read_lines(f,&line); if (tx < 0) { fprintf(stderr,"%s: corrupted text-mode problem (no goal specified)\n",__progname); exit(1); } if (ts < 0) { fprintf(stderr,"%s: corrupted text-mode problem (no target robot specified)\n",__progname); exit(1); } if ( gm != ( (((POSN)1) << POSN_S_R_R) | (((POSN)1) << POSN_S_R_G) | (((POSN)1) << POSN_S_R_B) | (((POSN)1) << POSN_S_R_Y) | (((POSN)1) << POSN_S_R_S) ) ) { fprintf(stderr,"%s: corrupted text-mode problem (robot positions not all specified)\n",__progname); exit(1); } goalmask = ((POSN_MASK << POSN_S_L_X) | (POSN_MASK << POSN_S_L_Y)) << ts; goalval = ((((POSN)tx) << POSN_S_L_X) | (((POSN)ty) << POSN_S_L_Y)) << ts; } static void read_problem(FILE *f) { int c; int c2; startpos = 0; goalmask = 0; goalval = 0; c = getc(f); if (c == '+') { ungetc(c,f); read_problem_asciigraphic(f); return; } switch (c) { case '1': case '2': case '3': case '4': c2 = getc(f); ungetc(c2,f); switch (c2) { case 'A': case 'B': ungetc(c,f); read_problem_game(f); return; } break; } ungetc(c,f); read_problem_text(f); } static void check_problem(void) { int x; int y; char b[16][16]; int i; void setchar(int x, int y, char c) { if (b[x][y] != ' ') { fprintf(stderr,"%s: corrupted problem: cell (%d,%d) has multiple things in it\n",__progname,x,y); b[x][y] = c; } } for (y=0;y<16;y++) for (x=0;x<16;x++) b[x][y] = ' '; for (i=5-1;i>=0;i--) { if ( (goalmask >> robots[i].shift) & ((POSN_MASK << POSN_S_L_X) | (POSN_MASK << POSN_S_L_Y)) ) { setchar((goalval>>(robots[i].shift+POSN_S_L_X))&POSN_MASK,(goalval>>(robots[i].shift+POSN_S_L_Y))&POSN_MASK,'*'); } setchar((startpos>>(robots[i].shift+POSN_S_L_X))&POSN_MASK,(startpos>>(robots[i].shift+POSN_S_L_Y))&POSN_MASK,robots[i].lc); } } static void setup_search(void) { int i; for (i=HTSIZE-1;i>=0;i--) htbl[i] = -1; nposn = 0; } static void fill_from_posn(POSN p, int ps, unsigned char fill) { unsigned char *bp; if (fill & ~CONTENTS) abort(); bp = &board[(p>>(ps+POSN_S_L_X))&POSN_MASK][(p>>(ps+POSN_S_L_Y))&POSN_MASK]; *bp = (*bp & ~CONTENTS) | fill; } static PQ *new_pq(void) { static int npq = -1; PQ *p; if (! freepq) { void *mmrv; int i; if (npq < 0) npq = 16777216 / sizeof(PQ); mmrv = mmap(0,npq*sizeof(PQ),PROT_READ|PROT_WRITE,MAP_ANON|MAP_PRIVATE,-1,0); if (mmrv == MAP_FAILED) { fprintf(stderr,"%s: mmap anonymous memory: %s\n",__progname,strerror(errno)); exit(1); } p = mmrv; for (i=npq;i>0;i--) { p->link = freepq; freepq = p; p ++; } } p = freepq; freepq = p->link; return(p); } static void old_pq(PQ *p) { p->link = freepq; freepq = p; } static int htfind(POSN p) { unsigned int h; int x; h = p % HTSIZE; while (1) { x = htbl[h]; if (x < 0) return(-1); if (posn[x] == p) return(x); h ++; if (h >= HTSIZE) h = 0; } } static int htenter(POSN p, int depth, int from) { unsigned int h; int x; if (nposn >= MAXPOSN) { fprintf(stderr,"%s: out of position room\n",__progname); exit(1); } posn[nposn] = p; pfrom[nposn] = from; pdepth[nposn] = depth; h = p % HTSIZE; while (1) { x = htbl[h]; if (x < 0) break; h ++; if (h >= HTSIZE) h = 0; } htbl[h] = nposn; return(nposn++); } static void attempt_moves(POSN p, void (*each)(POSN)) { int csx; int x0; int y0; int x; int y; int dir; static struct { unsigned char wall; int dx; int dy; } dirs[4] = { { WALL_L, -1, 0 }, { WALL_R, 1, 0 }, { WALL_U, 0, -1 }, { WALL_D, 0, 1 } }; for (csx=5-1;csx>=0;csx--) { x0 = (p >> (rsv[csx].s+POSN_S_L_X)) & POSN_MASK; y0 = (p >> (rsv[csx].s+POSN_S_L_Y)) & POSN_MASK; for (dir=4-1;dir>=0;dir--) { x = x0; y = y0; while (1) { if (board[x][y] & dirs[dir].wall) break; x += dirs[dir].dx; y += dirs[dir].dy; if ( (x < 0) || (x >= 16) || (y < 0) || (y >= 16) || ((board[x][y] & CONTENTS) != C_EMPTY) ) { x -= dirs[dir].dx; y -= dirs[dir].dy; break; } } if ((x != x0) || (y != y0)) (*each)( ( p & ~( (POSN_MASK<<(rsv[csx].s+POSN_S_L_X)) | (POSN_MASK<<(rsv[csx].s+POSN_S_L_Y)) ) ) | (((POSN)x)<<(rsv[csx].s+POSN_S_L_X)) | (((POSN)y)<<(rsv[csx].s+POSN_S_L_Y)) ); } } } static void place_robots(POSN p) { fill_from_posn(p,POSN_S_R_R,C_R_R); fill_from_posn(p,POSN_S_R_G,C_R_G); fill_from_posn(p,POSN_S_R_B,C_R_B); fill_from_posn(p,POSN_S_R_Y,C_R_Y); fill_from_posn(p,POSN_S_R_S,C_R_S); } static void unplace_robots(POSN p) { fill_from_posn(p,POSN_S_R_R,0); fill_from_posn(p,POSN_S_R_G,0); fill_from_posn(p,POSN_S_R_B,0); fill_from_posn(p,POSN_S_R_Y,0); fill_from_posn(p,POSN_S_R_S,0); } static void done(int px, POSN last) { POSN prev; void stepto(POSN p, unsigned char depth) { if (prev) { int i; for (i=5-1;i>=0;i--) { if ((p ^ prev) & (((POSN_MASK << POSN_S_L_X) | (POSN_MASK << POSN_S_L_Y)) << rsv[i].s)) { if ( ((p >> (rsv[i].s+POSN_S_L_X)) & POSN_MASK) < ((prev >> (rsv[i].s+POSN_S_L_X)) & POSN_MASK) ) printf("%c < ",rsv[i].c); if ( ((p >> (rsv[i].s+POSN_S_L_X)) & POSN_MASK) > ((prev >> (rsv[i].s+POSN_S_L_X)) & POSN_MASK) ) printf("%c > ",rsv[i].c); if ( ((p >> (rsv[i].s+POSN_S_L_Y)) & POSN_MASK) < ((prev >> (rsv[i].s+POSN_S_L_Y)) & POSN_MASK) ) printf("%c ^ ",rsv[i].c); if ( ((p >> (rsv[i].s+POSN_S_L_Y)) & POSN_MASK) > ((prev >> (rsv[i].s+POSN_S_L_Y)) & POSN_MASK) ) printf("%c v ",rsv[i].c); } } } else { printf(" "); } printf("R(%d,%d) G(%d,%d) B(%d,%d) Y(%d,%d) S(%d,%d) %d\n", (int)((p >> (POSN_S_R_R+POSN_S_L_X)) & POSN_MASK), (int)((p >> (POSN_S_R_R+POSN_S_L_Y)) & POSN_MASK), (int)((p >> (POSN_S_R_G+POSN_S_L_X)) & POSN_MASK), (int)((p >> (POSN_S_R_G+POSN_S_L_Y)) & POSN_MASK), (int)((p >> (POSN_S_R_B+POSN_S_L_X)) & POSN_MASK), (int)((p >> (POSN_S_R_B+POSN_S_L_Y)) & POSN_MASK), (int)((p >> (POSN_S_R_Y+POSN_S_L_X)) & POSN_MASK), (int)((p >> (POSN_S_R_Y+POSN_S_L_Y)) & POSN_MASK), (int)((p >> (POSN_S_R_S+POSN_S_L_X)) & POSN_MASK), (int)((p >> (POSN_S_R_S+POSN_S_L_Y)) & POSN_MASK), depth ); prev = p; } void printdone(int x) { if (x < 0) abort(); if (pdepth[x]) printdone(pfrom[x]); stepto(posn[x],pdepth[x]); } prev = 0; printdone(px); stepto(last,pdepth[px]+1); } static void do_search(POSN root, POSN gmask, POSN gval) { PQ *q; PQ *nextq; PQ *qe; int qex; int qdepth; int qlen; int any; void mvto(POSN p) { PQ *e; if ((p & gmask) == gval) { if (any) printf("\n"); any = 1; done(qex,p); fflush(0); } if (any) return; e = new_pq(); e->link = nextq; nextq = e; e->p = p; e->from = qex; qlen ++; } nextq = new_pq(); nextq->link = 0; nextq->p = root; nextq->from = -1; qdepth = -1; qlen = 1; any = 0; while (nextq) { if (any) break; q = nextq; nextq = 0; qdepth ++; printf("depth %d qlen %d nposn %d\n",qdepth,qlen,nposn); fflush(0); qlen = 0; if (! q) { printf("failure\n"); exit(0); } while (q) { qe = q; q = q->link; if (htfind(qe->p) < 0) { qex = htenter(qe->p,qdepth,qe->from); place_robots(qe->p); attempt_moves(qe->p,&mvto); unplace_robots(qe->p); } old_pq(qe); } } } static void dump_problem(void) { int x; int y; int i; char b[16][16]; char bc; void set(int x, int y, char c) { if (b[x][y] != ' ') abort(); b[x][y] = c; } for (y=0;y<16;y++) for (x=0;x<16;x++) b[x][y] = ' '; for (i=5-1;i>=0;i--) { if ( (goalmask >> robots[i].shift) & ((POSN_MASK << POSN_S_L_X) | (POSN_MASK << POSN_S_L_Y)) ) { set((goalval>>(robots[i].shift+POSN_S_L_X))&POSN_MASK,(goalval>>(robots[i].shift+POSN_S_L_Y))&POSN_MASK,'*'); bc = robots[i].uc; } else { bc = robots[i].lc; } set((startpos>>(robots[i].shift+POSN_S_L_X))&POSN_MASK,(startpos>>(robots[i].shift+POSN_S_L_Y))&POSN_MASK,bc); } for (y=0;y<16;y++) { for (x=0;x<16;x++) printf("+%s",(board[x][y]&WALL_U)?"---":" "); printf("+\n"); for (x=0;x<16;x++) { printf("%c %c ",(board[x][y]&WALL_L)?'|':' ',b[x][y]); } printf("|\n"); } printf("+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+\n"); } int main(void); int main(void) { init_board(); read_problem(stdin); check_problem(); setup_search(); dump_problem(); do_search(startpos,goalmask,goalval); return(0); }