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 /* Tuning this can reduce excess reallocs */
36 #define RRS_BRANCHING_FACTOR_ESTIMATE 10
38 #define RRS_STATE_SET_ROBOT(s, ri, x, y) ((s) |= (((y) << ((ri)<<3)) | ((x) << (((ri)<<3) + 4))))
39 #define RRS_STATE_GET_ROBOT(s, ri, x, y) { (y) = ((s) >> ((ri)<<3)) & 0xf; (x) = ((s) >> (((ri)<<3) + 4)) & 0xf; }
42 handle_events (rr_client_t *client);
45 rrs_state_get_from_board (rr_board_t *board);
48 rrs_solution_print (rrs_solution_t *solution);
51 solve_board (rr_board_t *board, rrs_solution_t *solution);
54 find_solution_states (rr_board_t *board,
55 rrs_state_buf_t ***solution_states,
57 rrs_state_t *final_state);
60 rrs_find_new_states (rr_board_t *board,
61 rrs_state_buf_t **previous,
64 rrs_state_t *solution_state);
67 trace_solution (rr_board_t *board,
68 rrs_state_buf_t **states, int moves,
69 rrs_state_t solution_state,
70 rrs_solution_t *solution);
73 main (int argc, char *argv[])
79 args_parse (&args, argc, argv);
84 rrs_solution_t solution;
86 for (i = 0; args.files[i]; i++) {
87 board = rr_board_create_from_file (args.files[i]);
89 fprintf (stderr, "Failed to parse board in %s\n", args.files[i]);
92 rrs_solution_init (&solution);
93 solve_board (board, &solution);
94 rrs_solution_print (&solution);
95 rrs_solution_fini (&solution);
96 rr_board_destroy (board);
99 client = rr_client_create (args.host, args.port, args.user);
100 if (client == NULL) {
101 fprintf (stderr, "Failed connecting to %s:%s as %s\n",
102 args.host, args.port, args.user);
106 status = rr_client_join (client, args.game);
107 if (status == RR_STATUS_NO_GAME)
108 status = rr_client_new (client, args.game);
110 fprintf (stderr, "Error joining or creating game: %s\n", rr_status_str (status));
114 handle_events (client);
116 rr_client_destroy (client);
123 handle_events (rr_client_t *client)
128 rrs_solution_t solution;
131 struct timespec move_delay = { 1, 200000000l };
133 /* XXX: This block of code can go away when add a NOTICE BOARD
134 for new users joining a game. */
136 status = rr_client_show (client, &diagram);
138 fprintf (stderr, "Error in rr_client_show: %s\n", rr_status_str (status));
141 board = rr_board_create_from_str (diagram);
145 /* XXX: This block of code can go away when we add a NOTICE TURN
146 for new users joining a game in progress. */
148 rrs_solution_init (&solution);
149 solve_board (board, &solution);
150 rr_client_bid (client, solution.num_moves);
151 rr_client_nobid (client);
155 status = rr_client_next_notice (client, ¬ice);
157 if (status == RR_STATUS_EOF)
158 fprintf (stderr, "Server has disconnected. Exiting.\n");
160 fprintf (stderr, "ERROR during rr_client_next_notice: %s\n",
161 rr_status_str (status));
165 fprintf (stderr, "No notice during rr_client_next_notice\n");
169 switch (notice->type) {
170 case RR_NOTICE_BOARD:
171 rr_board_parse (board, notice->u.string);
174 rr_board_set_goal_target (board, notice->u.target);
175 rrs_solution_init (&solution);
176 solve_board (board, &solution);
177 rr_client_bid (client, solution.num_moves);
178 rr_client_nobid (client);
180 case RR_NOTICE_ACTIVATE:
181 for (i = 0; i < solution.num_moves; i++) {
182 status = rr_client_move (client,
183 solution.move[i].robot,
184 solution.move[i].dir);
186 rr_client_message (client, "Drat, looks like I was wrong.");
187 rr_client_pass (client);
190 nanosleep (&move_delay, NULL);
192 rrs_solution_fini (&solution);
194 case RR_NOTICE_ABANDON:
195 rr_client_abandon (client);
197 case RR_NOTICE_NOBID:
198 rr_client_nobid (client);
200 case RR_NOTICE_POSITION:
201 rr_board_add_robot (board,
202 notice->u.position.robot,
203 notice->u.position.x,
204 notice->u.position.y);
206 case RR_NOTICE_GAMESTATE:
207 if (notice->u.gamestate == RR_GAMESTATE_DONE
208 || notice->u.gamestate == RR_GAMESTATE_SHOW) {
209 if (solution.num_moves) {
210 printf ("My solution (%d moves):", solution.num_moves);
211 rrs_solution_print (&solution);
215 case RR_NOTICE_GAMEOVER:
220 case RR_NOTICE_DISPOSE:
221 case RR_NOTICE_MESSAGE:
222 case RR_NOTICE_WATCH:
225 case RR_NOTICE_REVOKE:
226 case RR_NOTICE_TIMER:
227 case RR_NOTICE_ACTIVE:
230 case RR_NOTICE_RESET:
231 case RR_NOTICE_SCORE:
232 /* Ignore these notices */
242 rr_board_destroy (board);
246 rrs_solution_print (rrs_solution_t *solution)
249 rr_robot_t last_robot;
252 last_robot = RR_ROBOT_NONE;
253 for (i=0; i < solution->num_moves; i++) {
254 move = &solution->move[i];
255 if (move->robot == last_robot)
256 printf (", %s", rr_direction_str (move->dir));
258 printf ("\n Move #%d: %s %s",
259 i+1, rr_robot_str (move->robot), rr_direction_str (move->dir));
260 last_robot = move->robot;
266 rrs_state_get_from_board (rr_board_t *board)
274 for (i=0; i < RR_NUM_ROBOTS; i++) {
275 rr_board_find_robot (board, rr_robot_from_idx (i), &x, &y);
276 RRS_STATE_SET_ROBOT (state, i, x, y);
283 rrs_state_set_board (rrs_state_t state, rr_board_t *board)
288 for (i=0; i < RR_NUM_ROBOTS; i++)
289 rr_board_remove_robot (board, rr_robot_from_idx (i));
291 for (i=0; i < RR_NUM_ROBOTS; i++) {
292 RRS_STATE_GET_ROBOT (state, i, x, y);
293 rr_board_add_robot (board, rr_robot_from_idx (i), x, y);
298 solve_board (rr_board_t *board, rrs_solution_t *solution)
302 rrs_state_t solution_state;
303 rrs_state_buf_t **states;
304 struct timeval tv_start, tv_end;
306 if (rr_board_solved (board)) {
307 printf ("Board is solved to begin with.\n");
308 return RR_STATUS_SUCCESS;
311 printf ("Now trying to solve:");
312 puts (rr_board_to_str (board));
314 gettimeofday (&tv_start, NULL);
316 status = find_solution_states (board, &states, &moves, &solution_state);
320 gettimeofday (&tv_end, NULL);
323 printf ("It seems impossible.\n");
325 printf ("Found solution of %d moves in %g seconds.\n",
327 tv_end.tv_sec - tv_start.tv_sec
328 + (tv_end.tv_usec - tv_start.tv_usec) / 1e6);
330 gettimeofday (&tv_start, NULL);
332 trace_solution (board, states, moves, solution_state, solution);
334 gettimeofday (&tv_end, NULL);
336 printf ("Traced solution in %g seconds.\n",
337 tv_end.tv_sec - tv_start.tv_sec
338 + (tv_end.tv_usec - tv_start.tv_usec) / 1e6);
341 for (i=0; i <= moves; i++) {
342 rrs_state_buf_destroy (states[i]);
348 return RR_STATUS_SUCCESS;
352 rrs_state_connected (rrs_state_t a, rrs_state_t b,
353 rr_robot_t *robot, rr_direction_t *dir)
357 rrs_state_t diff, mask;
363 for (i=0; i < 8; i++) {
376 *robot = RR_ROBOT_BLUE;
380 *robot = RR_ROBOT_GREEN;
384 *robot = RR_ROBOT_RED;
388 *robot = RR_ROBOT_YELLOW;
394 delta = ((b & mask) >> shift) - ((a & mask) >> shift);
398 *dir = RR_DIRECTION_WEST;
400 *dir = RR_DIRECTION_EAST;
403 *dir = RR_DIRECTION_NORTH;
405 *dir = RR_DIRECTION_SOUTH;
411 trace_solution (rr_board_t *board,
412 rrs_state_buf_t **states, int moves,
413 rrs_state_t solution_state,
414 rrs_solution_t *solution)
418 rrs_state_buf_t *buf;
420 rr_robot_t robot, robot_found, last_robot_found = RR_ROBOT_NONE;
421 rr_direction_t dir, dir_found;
422 rrs_state_t state_found;
424 for (i = moves-1; i >= 0; i--) {
426 for (j = 0; j < buf->num_states; j++) {
427 if (rrs_state_connected (buf->state[j], solution_state,
429 rrs_state_set_board (buf->state[j], board);
430 status = rr_board_move (board, robot, dir);
431 if (status == RR_STATUS_SUCCESS) {
432 if (rrs_state_get_from_board (board) == solution_state) {
436 state_found = buf->state[j];
437 if (robot_found == last_robot_found)
440 last_robot_found = robot_found;
447 rrs_solution_prepend (solution, robot_found, dir_found);
448 solution_state = state_found;
450 fprintf (stderr, "ERROR: Failed to trace solution backwards to 0x%x at move %d\n",
451 solution_state, i+1);
458 find_solution_states (rr_board_t *board,
459 rrs_state_buf_t ***solution_states,
461 rrs_state_t *final_state)
465 rrs_state_buf_t **states, **new_states;
467 states = malloc (sizeof (rrs_state_buf_t *));
469 return RR_STATUS_NO_MEMORY;
471 initial = rrs_state_get_from_board (board);
473 states[0] = rrs_state_buf_create (1);
474 if (states[0] == NULL)
475 return RR_STATUS_NO_MEMORY;
476 rrs_state_buf_add (states[0], initial);
482 new_states = realloc (states, (moves + 1) * sizeof (rrs_state_buf_t *));
483 if (new_states == NULL)
484 return RR_STATUS_NO_MEMORY;
487 states[moves] = rrs_state_buf_create (RRS_BRANCHING_FACTOR_ESTIMATE
488 * states[moves-1]->num_states);
489 if (states[moves] == NULL)
490 return RR_STATUS_NO_MEMORY;
492 solved = rrs_find_new_states (board, states, moves-1, states[moves], final_state);
497 if (states[moves]->num_states == 0) {
498 printf ("Can't make any further progress after %d moves.\n", moves);
502 printf ("Move #%d generated %d new states.\n",
503 moves, states[moves]->num_states);
507 *num_state_buf = moves;
508 *solution_states = states;
510 return RR_STATUS_SUCCESS;
514 state_has_been_seen (rrs_state_buf_t **previous,
520 for (i=0; i <= moves; i++)
521 if (rrs_state_buf_contains (previous[i], state))
527 rrs_find_new_states (rr_board_t *board,
528 rrs_state_buf_t **previous,
530 rrs_state_buf_t *new,
531 rrs_state_t *solution_state)
535 rrs_state_t state, new_state;
536 rrs_state_buf_t *initial;
540 initial = previous[moves];
542 for (i = 0; i < initial->num_states; i++) {
543 state = initial->state[i];
545 rrs_state_set_board (state, board);
547 if (state == 0x611a4350)
548 printf ("I'm within one move now\n");
549 for (ri = 0; ri < RR_NUM_ROBOTS; ri++) {
550 robot = rr_robot_from_idx (ri);
551 for (dir = RR_DIRECTION_NORTH; dir <= RR_DIRECTION_EAST; dir++) {
552 status = rr_board_move (board, robot, dir);
553 if (status == RR_STATUS_SUCCESS) {
554 new_state = rrs_state_get_from_board (board);
555 if (! state_has_been_seen (previous, moves, new_state)) {
556 rrs_state_buf_add_sorted (new, new_state);
557 if (rr_board_solved (board)) {
558 *solution_state = new_state;
562 rr_board_undo (board);