1 /* rrsolve - Simple RR solver and librr client.
3 * Copyright © 2003 Carl Worth
5 * Permission to use, copy, modify, distribute, and sell this software
6 * and its documentation for any purpose is hereby granted without
7 * fee, provided that the above copyright notice appear in all copies
8 * and that both that copyright notice and this permission notice
9 * appear in supporting documentation, and that the name of Carl Worth
10 * not be used in advertising or publicity pertaining to distribution
11 * of the software without specific, written prior permission.
12 * Carl Worth makes no representations about the suitability of this
13 * software for any purpose. It is provided "as is" without express
14 * or implied warranty.
16 * CARL WORTH DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE,
17 * INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS, IN
18 * NO EVENT SHALL CARL WORTH BE LIABLE FOR ANY SPECIAL, INDIRECT OR
19 * CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS
20 * OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT,
21 * NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN
22 * CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
24 * Author: Carl Worth <carl@theworths.org>
35 #define HOST "localhost"
37 #define USER "rrsolve"
40 /* Tuning this can reduce excess reallocs */
41 #define RRS_BRANCHING_FACTOR_ESTIMATE 10
43 #define RRS_STATE_SET_ROBOT(s, ri, x, y) ((s) |= (((y) << ((ri)<<3)) | ((x) << (((ri)<<3) + 4))))
44 #define RRS_STATE_GET_ROBOT(s, ri, x, y) { (y) = ((s) >> ((ri)<<3)) & 0xf; (x) = ((s) >> (((ri)<<3) + 4)) & 0xf; }
47 handle_events (rr_client_t *client);
50 rrs_state_get_from_board (rr_board_t *board);
53 rrs_solution_print (rrs_solution_t *solution);
56 solve_board (rr_board_t *board, rrs_solution_t *solution);
59 find_solution_states (rr_board_t *board,
60 rrs_state_buf_t ***solution_states,
62 rrs_state_t *final_state);
65 rrs_find_new_states (rr_board_t *board,
66 rrs_state_buf_t **previous,
69 rrs_state_t *solution_state);
72 trace_solution (rr_board_t *board,
73 rrs_state_buf_t **states, int moves,
74 rrs_state_t solution_state,
75 rrs_solution_t *solution);
78 " === === === === === === === === === === === === === === === === \n"
79 "|... ... ... ...|r.. ... ... ... ... ... ... ...|... ... ... ...|\n"
81 "|... ... ... ... ... ... ... ... ... ... ... ... ...|.rs Y.. ...|\n"
83 "|... ... ... ... ... .bo|... ... ... .bt|... ... ... ... ... ...|\n"
85 "|... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ...|\n"
87 "|... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ...|\n"
89 "|... ... .gc|... ... ... ...|.rt ... ... ... ... ... ...|.go ...|\n"
91 "|... ... ... ... ... ... ... ... ... ... ... .yc|... ... ... ...|\n"
93 "|...|.YS ... ... ... ... ...|... ...|... ... ... ... ... ... ...|\n"
95 "|... ... ... ... ... ... ...|... ...|... ... ...|.ww ... ... ...|\n"
97 "|... .yo|... ... ...|bbs ... ... ... ...|.bc ... ... ... ... ...|\n"
99 "|... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ...|\n"
101 "|... ... ... ... ... ... ... ... ... .yt|... ... ... ... ... ...|\n"
103 "|... ... ... ... ... ... .rc|... ... ... ... ... ... ... .gs|...|\n"
105 "|... ... ... ... ... ... ... ... ... ... ... ... ... ... ... g..|\n"
107 "|... ...|.gt ... ... ... ... ... ... ... ... ... ...|.ro ... ...|\n"
109 "|... ... ... ... ... ...|... ... ... ... ...|... ... ... ... ...|\n"
110 " === === === === === === === === === === === === === === === === ";
112 Move #1 generated 11 new states.
113 Move #2 generated 59 new states.
114 Move #3 generated 216 new states.
115 Move #4 generated 640 new states.
116 Move #5 generated 1701 new states.
117 Move #6 generated 4239 new states.
118 Move #7 generated 10041 new states.
119 Move #8 generated 22678 new states.
120 Move #9 generated 49103 new states.
121 Move #10 generated 102154 new states.
122 Move #11 generated 204086 new states.
123 Move #12 generated 391534 new states.
124 Move #13 generated 722808 new states.
125 Move #14 generated 1285932 new states.
126 Move #15 generated 2204971 new states.
127 Found solution of 16 moves in 3694.8 seconds.
128 Traced solution in 0.052438 seconds.
130 Move #0: yellow east, south, west
131 Move #3: green south, west, north
132 Move #6: blue east, north, west, south
133 Move #10: yellow south, east, south
135 Move #14: yellow north
139 main (int argc, char *argv[])
145 args_parse (&args, argc, argv);
147 client = rr_client_create (args.host, args.port, args.user);
148 if (client == NULL) {
149 fprintf (stderr, "Failed connecting to %s:%s as %s\n",
150 args.host, args.port, args.user);
154 status = rr_client_join (client, GAME);
155 if (status == RR_STATUS_NO_GAME)
156 status = rr_client_new (client, GAME);
158 fprintf (stderr, "Error joining or creating game: %s\n", rr_status_str (status));
162 handle_events (client);
164 rr_client_destroy (client);
170 handle_events (rr_client_t *client)
175 rrs_solution_t solution;
176 rr_board_t *board = NULL;
178 struct timespec move_delay = { 1, 200000000l };
181 status = rr_client_next_notice (client, ¬ice);
183 fprintf (stderr, "ERROR during rr_client_next_notice: %s\n",
184 rr_status_str (status));
188 fprintf (stderr, "No notice during rr_client_next_notice\n");
192 switch (notice->type) {
193 case RR_NOTICE_GAMEOVER:
195 status = rr_client_show (client, &diagram);
197 fprintf (stderr, "Error in rr_client_show: %s\n", rr_status_str (status));
201 board = rr_board_create_from_str (diagram);
203 rr_board_parse (board, diagram);
205 /* XXX: Fixing the server to send a NOTICE TURN here would let me drop this code */
206 rrs_solution_init (&solution);
207 solve_board (board, &solution);
208 rr_client_bid (client, solution.num_moves);
211 rr_board_set_goal_target (board, notice->u.target);
212 rrs_solution_init (&solution);
213 solve_board (board, &solution);
214 rr_client_bid (client, solution.num_moves);
216 case RR_NOTICE_ACTIVATE:
217 for (i = 0; i < solution.num_moves; i++) {
218 status = rr_client_move (client,
219 solution.move[i].robot,
220 solution.move[i].dir);
222 rr_client_message (client, "Drat, looks like I was wrong.");
223 rr_client_pass (client);
226 nanosleep (&move_delay, NULL);
228 rrs_solution_fini (&solution);
230 case RR_NOTICE_ABANDON:
231 rr_client_abandon (client);
233 case RR_NOTICE_NOBID:
234 rr_client_nobid (client);
236 case RR_NOTICE_POSITION:
237 rr_board_position_robot (board,
238 notice->u.position.robot,
239 notice->u.position.x,
240 notice->u.position.y);
242 case RR_NOTICE_GAMESTATE:
243 if (notice->u.gamestate == RR_GAMESTATE_SHOW) {
244 if (solution.num_moves) {
245 printf ("My solution (%d moves):", solution.num_moves);
246 rrs_solution_print (&solution);
253 case RR_NOTICE_DISPOSE:
254 case RR_NOTICE_MESSAGE:
255 case RR_NOTICE_WATCH:
258 case RR_NOTICE_REVOKE:
259 case RR_NOTICE_TIMER:
260 case RR_NOTICE_ACTIVE:
263 case RR_NOTICE_RESET:
264 case RR_NOTICE_SCORE:
265 /* Ignore these notices */
272 rr_board_destroy (board);
276 rrs_solution_print (rrs_solution_t *solution)
279 rr_robot_t last_robot;
282 last_robot = RR_ROBOT_NONE;
283 for (i=0; i < solution->num_moves; i++) {
284 move = &solution->move[i];
285 if (move->robot == last_robot)
286 printf (", %s", rr_direction_str (move->dir));
288 printf ("\n Move #%d: %s %s",
289 i, rr_robot_str (move->robot), rr_direction_str (move->dir));
290 last_robot = move->robot;
296 rrs_state_get_from_board (rr_board_t *board)
304 for (i=0; i < RR_NUM_ROBOTS; i++) {
305 rr_board_find_robot (board, rr_robot_from_idx (i), &x, &y);
306 RRS_STATE_SET_ROBOT (state, i, x, y);
313 rrs_state_set_board (rrs_state_t state, rr_board_t *board)
318 for (i=0; i < RR_NUM_ROBOTS; i++) {
319 RRS_STATE_GET_ROBOT (state, i, x, y);
320 rr_board_position_robot (board, rr_robot_from_idx (i), x, y);
326 solve_board (rr_board_t *board, rrs_solution_t *solution)
330 rrs_state_t solution_state;
331 rrs_state_buf_t **states;
332 struct timeval tv_start, tv_end;
334 if (rr_board_solved (board)) {
335 printf ("Board is solved to begin with.\n");
336 return RR_STATUS_SUCCESS;
339 printf ("Now trying to solve:");
340 puts (rr_board_to_str (board));
342 gettimeofday (&tv_start, NULL);
344 status = find_solution_states (board, &states, &moves, &solution_state);
348 gettimeofday (&tv_end, NULL);
351 printf ("It seems impossible.\n");
353 printf ("Found solution of %d moves in %g seconds.\n",
355 tv_end.tv_sec - tv_start.tv_sec
356 + (tv_end.tv_usec - tv_start.tv_usec) / 1e6);
358 gettimeofday (&tv_start, NULL);
360 trace_solution (board, states, moves, solution_state, solution);
362 gettimeofday (&tv_end, NULL);
364 printf ("Traced solution in %g seconds.\n",
365 tv_end.tv_sec - tv_start.tv_sec
366 + (tv_end.tv_usec - tv_start.tv_usec) / 1e6);
369 for (i=0; i <= moves; i++) {
370 rrs_state_buf_destroy (states[i]);
376 return RR_STATUS_SUCCESS;
380 rrs_state_connected (rrs_state_t a, rrs_state_t b,
381 rr_robot_t *robot, rr_direction_t *dir)
385 rrs_state_t diff, mask;
391 for (i=0; i < 8; i++) {
404 *robot = RR_ROBOT_BLUE;
408 *robot = RR_ROBOT_GREEN;
412 *robot = RR_ROBOT_RED;
416 *robot = RR_ROBOT_YELLOW;
422 delta = ((b & mask) >> shift) - ((a & mask) >> shift);
426 *dir = RR_DIRECTION_WEST;
428 *dir = RR_DIRECTION_EAST;
431 *dir = RR_DIRECTION_NORTH;
433 *dir = RR_DIRECTION_SOUTH;
439 trace_solution (rr_board_t *board,
440 rrs_state_buf_t **states, int moves,
441 rrs_state_t solution_state,
442 rrs_solution_t *solution)
446 rrs_state_buf_t *buf;
450 for (i = moves-1; i >= 0; i--) {
452 for (j = 0; j < buf->num_states; j++) {
453 if (rrs_state_connected (buf->state[j], solution_state,
455 rrs_state_set_board (buf->state[j], board);
456 status = rr_board_move (board, robot, dir);
457 if (status == RR_STATUS_SUCCESS) {
458 if (rrs_state_get_from_board (board) == solution_state) {
459 rrs_solution_prepend (solution, robot, dir);
460 solution_state = buf->state[j];
466 fprintf (stderr, "ERROR: Failed to trace solution backwards to 0x%x at move %d\n",
467 solution_state, i+1);
475 find_solution_states (rr_board_t *board,
476 rrs_state_buf_t ***solution_states,
478 rrs_state_t *final_state)
482 rrs_state_buf_t **states, **new_states;
484 states = malloc (sizeof (rrs_state_buf_t *));
486 return RR_STATUS_NO_MEMORY;
488 initial = rrs_state_get_from_board (board);
490 states[0] = rrs_state_buf_create (1);
491 if (states[0] == NULL)
492 return RR_STATUS_NO_MEMORY;
493 rrs_state_buf_add (states[0], initial);
499 new_states = realloc (states, (moves + 1) * sizeof (rrs_state_buf_t *));
500 if (new_states == NULL)
501 return RR_STATUS_NO_MEMORY;
504 states[moves] = rrs_state_buf_create (RRS_BRANCHING_FACTOR_ESTIMATE
505 * states[moves-1]->num_states);
506 if (states[moves] == NULL)
507 return RR_STATUS_NO_MEMORY;
509 solved = rrs_find_new_states (board, states, moves-1, states[moves], final_state);
514 if (states[moves]->num_states == 0) {
515 printf ("Can't make any further progress after %d moves.\n", moves);
519 printf ("Move #%d generated %d new states.\n",
520 moves, states[moves]->num_states);
524 *num_state_buf = moves;
525 *solution_states = states;
527 return RR_STATUS_SUCCESS;
531 state_has_been_seen (rrs_state_buf_t **previous,
537 for (i=0; i <= moves; i++)
538 if (rrs_state_buf_contains (previous[i], state))
544 rrs_find_new_states (rr_board_t *board,
545 rrs_state_buf_t **previous,
547 rrs_state_buf_t *new,
548 rrs_state_t *solution_state)
552 rrs_state_t state, new_state;
553 rrs_state_buf_t *initial;
557 initial = previous[moves];
559 for (i = 0; i < initial->num_states; i++) {
560 state = initial->state[i];
562 rrs_state_set_board (state, board);
563 for (ri = 0; ri < RR_NUM_ROBOTS; ri++) {
564 robot = rr_robot_from_idx (ri);
565 for (dir = RR_DIRECTION_NORTH; dir <= RR_DIRECTION_EAST; dir++) {
566 status = rr_board_move (board, robot, dir);
567 if (status == RR_STATUS_SUCCESS) {
568 new_state = rrs_state_get_from_board (board);
569 if (! state_has_been_seen (previous, moves, new_state)) {
570 rrs_state_buf_add_sorted (new, new_state);
571 if (rr_board_solved (board)) {
572 *solution_state = new_state;
576 rr_board_undo (board);