#define RRS_STATE_SET_ROBOT(s, ri, x, y) ((s) |= (((y) << ((ri)<<3)) | ((x) << (((ri)<<3) + 4))))
#define RRS_STATE_GET_ROBOT(s, ri, x, y) { (y) = ((s) >> ((ri)<<3)) & 0xf; (x) = ((s) >> (((ri)<<3) + 4)) & 0xf; }
+static void
+handle_events (rr_client_t *client);
+
static rrs_state_t
rrs_state_get_from_board (rr_board_t *board);
rrs_state_t solution_state,
rrs_solution_t *solution);
+char TOUGH[] = "\n"
+" === === === === === === === === === === === === === === === === \n"
+"|... ... ... ...|r.. ... ... ... ... ... ... ...|... ... ... ...|\n"
+" === \n"
+"|... ... ... ... ... ... ... ... ... ... ... ... ...|.rs Y.. ...|\n"
+" \n"
+"|... ... ... ... ... .bo|... ... ... .bt|... ... ... ... ... ...|\n"
+" === === \n"
+"|... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ...|\n"
+" === \n"
+"|... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ...|\n"
+" === \n"
+"|... ... .gc|... ... ... ...|.rt ... ... ... ... ... ...|.go ...|\n"
+" === === === === \n"
+"|... ... ... ... ... ... ... ... ... ... ... .yc|... ... ... ...|\n"
+" === === === \n"
+"|...|.YS ... ... ... ... ...|... ...|... ... ... ... ... ... ...|\n"
+" === \n"
+"|... ... ... ... ... ... ...|... ...|... ... ...|.ww ... ... ...|\n"
+" === === === === \n"
+"|... .yo|... ... ...|bbs ... ... ... ...|.bc ... ... ... ... ...|\n"
+" === \n"
+"|... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ...|\n"
+" === === \n"
+"|... ... ... ... ... ... ... ... ... .yt|... ... ... ... ... ...|\n"
+" === === \n"
+"|... ... ... ... ... ... .rc|... ... ... ... ... ... ... .gs|...|\n"
+" === \n"
+"|... ... ... ... ... ... ... ... ... ... ... ... ... ... ... g..|\n"
+" === \n"
+"|... ...|.gt ... ... ... ... ... ... ... ... ... ...|.ro ... ...|\n"
+" === \n"
+"|... ... ... ... ... ...|... ... ... ... ...|... ... ... ... ...|\n"
+" === === === === === === === === === === === === === === === === ";
+/*
+Move #1 generated 11 new states.
+Move #2 generated 59 new states.
+Move #3 generated 216 new states.
+Move #4 generated 640 new states.
+Move #5 generated 1701 new states.
+Move #6 generated 4239 new states.
+Move #7 generated 10041 new states.
+Move #8 generated 22678 new states.
+Move #9 generated 49103 new states.
+Move #10 generated 102154 new states.
+Move #11 generated 204086 new states.
+Move #12 generated 391534 new states.
+Move #13 generated 722808 new states.
+Move #14 generated 1285932 new states.
+Move #15 generated 2204971 new states.
+Found solution of 16 moves in 3694.8 seconds.
+Traced solution in 0.052438 seconds.
+Solution (16 moves):
+ Move #0: yellow east, south, west
+Move #3: green south, west, north
+Move #6: blue east, north, west, south
+Move #10: yellow south, east, south
+Move #13: green west
+Move #14: yellow north
+*/
+
int
main (int argc, char *argv[])
{
args_t args;
rr_status_t status;
rr_client_t *client;
- rr_board_t *board;
- rrs_solution_t solution;
- char *diagram;
args_parse (&args, argc, argv);
return 1;
}
- status = rr_client_show (client, &diagram);
- if (status) {
- fprintf (stderr, "Error in rr_client_new: %s\n", rr_status_str (status));
- return 1;
- }
- board = rr_board_create_from_str (diagram);
+ handle_events (client);
- puts (rr_board_to_str (board));
+ rr_client_destroy (client);
- rrs_solution_init (&solution);
- solve_board (board, &solution);
- printf ("Solution (%d moves):", solution.num_moves);
- rrs_solution_print (&solution);
- rrs_solution_fini (&solution);
+ return 0;
+}
- free (diagram);
+static void
+handle_events (rr_client_t *client)
+{
+ int i;
+ rr_status_t status;
+ rr_notice_t *notice;
+ rrs_solution_t solution;
+ rr_board_t *board;
+ char *diagram;
+ struct timespec move_delay = { 1, 200000000l };
+
+ /* XXX: This block of code can go away when add a NOTICE BOARD
+ for new users joining a game. */
+ {
+ status = rr_client_show (client, &diagram);
+ if (status) {
+ fprintf (stderr, "Error in rr_client_show: %s\n", rr_status_str (status));
+ goto DONE;
+ }
+ board = rr_board_create_from_str (diagram);
+ free (diagram);
+ }
- rr_board_destroy (board);
+ /* XXX: This block of code can go away when we add a NOTICE TURN
+ for new users joining a game in progress. */
+ {
+ rrs_solution_init (&solution);
+ solve_board (board, &solution);
+ rr_client_bid (client, solution.num_moves);
+ }
- rr_client_destroy (client);
+ while (1) {
+ status = rr_client_next_notice (client, ¬ice);
+ if (status) {
+ if (status == RR_STATUS_EOF)
+ fprintf (stderr, "Server has disconnected. Exiting.\n");
+ else
+ fprintf (stderr, "ERROR during rr_client_next_notice: %s\n",
+ rr_status_str (status));
+ return;
+ }
+ if (!notice) {
+ fprintf (stderr, "No notice during rr_client_next_notice\n");
+ continue;
+ }
- return 0;
+ switch (notice->type) {
+ /* XXX: The processing needed for GAMEOVER, JOIN, and TURN
+ is a mess right now. There should be one NOTICE to say
+ the board has changed and one to say a TURN has started,
+ rather than the current mess. */
+ case RR_NOTICE_GAMEOVER:
+ status = rr_client_show (client, &diagram);
+ if (status) {
+ fprintf (stderr, "Error in rr_client_show: %s\n", rr_status_str (status));
+ goto DONE;
+ }
+ rr_board_parse (board, diagram);
+ free (diagram);
+ break;
+ case RR_NOTICE_TURN:
+ rr_board_set_goal_target (board, notice->u.target);
+ rrs_solution_init (&solution);
+ solve_board (board, &solution);
+ rr_client_bid (client, solution.num_moves);
+ break;
+ case RR_NOTICE_ACTIVATE:
+ for (i = 0; i < solution.num_moves; i++) {
+ status = rr_client_move (client,
+ solution.move[i].robot,
+ solution.move[i].dir);
+ if (status) {
+ rr_client_message (client, "Drat, looks like I was wrong.");
+ rr_client_pass (client);
+ break;
+ }
+ nanosleep (&move_delay, NULL);
+ }
+ rrs_solution_fini (&solution);
+ break;
+ case RR_NOTICE_ABANDON:
+ rr_client_abandon (client);
+ break;
+ case RR_NOTICE_NOBID:
+ rr_client_nobid (client);
+ break;
+ case RR_NOTICE_POSITION:
+ rr_board_position_robot (board,
+ notice->u.position.robot,
+ notice->u.position.x,
+ notice->u.position.y);
+ break;
+ case RR_NOTICE_GAMESTATE:
+ if (notice->u.gamestate == RR_GAMESTATE_SHOW) {
+ if (solution.num_moves) {
+ printf ("My solution (%d moves):", solution.num_moves);
+ rrs_solution_print (&solution);
+ }
+ }
+ break;
+ case RR_NOTICE_GAME:
+ case RR_NOTICE_USER:
+ case RR_NOTICE_JOIN:
+ case RR_NOTICE_QUIT:
+ case RR_NOTICE_DISPOSE:
+ case RR_NOTICE_MESSAGE:
+ case RR_NOTICE_WATCH:
+ case RR_NOTICE_PART:
+ case RR_NOTICE_BID:
+ case RR_NOTICE_REVOKE:
+ case RR_NOTICE_TIMER:
+ case RR_NOTICE_ACTIVE:
+ case RR_NOTICE_MOVE:
+ case RR_NOTICE_UNDO:
+ case RR_NOTICE_RESET:
+ case RR_NOTICE_SCORE:
+ /* Ignore these notices */
+ break;
+ }
+ free (notice);
+ }
+
+ DONE:
+ if (notice)
+ free (notice);
+ if (board)
+ rr_board_destroy (board);
}
static void
printf (", %s", rr_direction_str (move->dir));
else
printf ("\n Move #%d: %s %s",
- i, rr_robot_str (move->robot), rr_direction_str (move->dir));
+ i+1, rr_robot_str (move->robot), rr_direction_str (move->dir));
last_robot = move->robot;
}
printf ("\n");
printf ("Board is solved to begin with.\n");
return RR_STATUS_SUCCESS;
}
+
+ printf ("Now trying to solve:");
+ puts (rr_board_to_str (board));
gettimeofday (&tv_start, NULL);
rr_status_t status;
int i, j;
rrs_state_buf_t *buf;
- rr_robot_t robot;
- rr_direction_t dir;
+ int found_move;
+ rr_robot_t robot, robot_found, last_robot_found = RR_ROBOT_NONE;
+ rr_direction_t dir, dir_found;
+ rrs_state_t state_found;
for (i = moves-1; i >= 0; i--) {
buf = states[i];
status = rr_board_move (board, robot, dir);
if (status == RR_STATUS_SUCCESS) {
if (rrs_state_get_from_board (board) == solution_state) {
- rrs_solution_prepend (solution, robot, dir);
- solution_state = buf->state[j];
- goto NEXT_MOVE;
+ found_move = 1;
+ robot_found = robot;
+ dir_found = dir;
+ state_found = buf->state[j];
+ if (robot_found == last_robot_found)
+ goto NEXT_MOVE;
+ else
+ last_robot_found = robot_found;
}
}
}
}
- fprintf (stderr, "ERROR: Failed to trace solution backwards to 0x%x at move %d\n",
- solution_state, i+1);
- break;
NEXT_MOVE:
- ;
+ if (found_move) {
+ rrs_solution_prepend (solution, robot_found, dir_found);
+ solution_state = state_found;
+ } else {
+ fprintf (stderr, "ERROR: Failed to trace solution backwards to 0x%x at move %d\n",
+ solution_state, i+1);
+ break;
+ }
}
}
projects / rrsolve / blobdiff