git.cworth.org Git - rrsolve/blob - src/rrsolve.c

   1 /* rrsolve - Simple RR solver and librr client.
   2  *
   3  * Copyright © 2003 Carl Worth
   4  *
   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.
  15  *
  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.
  23  *
  24  * Author: Carl Worth <carl@theworths.org>
  25  */
  26
  27 #include <stdio.h>
  28 #include <stdlib.h>
  29 #include <string.h>
  30 #include <sys/time.h>
  31 #include <time.h>
  32
  33 #include "rrsolve.h"
  34
  35 /* Tuning this can reduce excess reallocs */
  36 #define RRS_BRANCHING_FACTOR_ESTIMATE 10
  37
  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; }
  40
  41 static void
  42 handle_events (rr_client_t *client);
  43
  44 static rrs_state_t
  45 rrs_state_get_from_board (rr_board_t *board);
  46
  47 static void
  48 rrs_solution_print (rrs_solution_t *solution);
  49
  50 static rr_status_t
  51 solve_board (rr_board_t *board, rrs_solution_t *solution);
  52
  53 static rr_status_t
  54 find_solution_states (rr_board_t *board,
  55                       rrs_state_buf_t ***solution_states,
  56                       int *num_state_buf,
  57                       rrs_state_t *final_state);
  58
  59 static int
  60 rrs_find_new_states (rr_board_t *board,
  61                      rrs_state_buf_t **previous,
  62                      int moves,
  63                      rrs_state_buf_t *new,
  64                      rrs_state_t *solution_state);
  65
  66 static void
  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);
  71
  72 int
  73 main (int argc, char *argv[])
  74 {
  75     args_t args;
  76     rr_status_t status;
  77     rr_client_t *client;
  78
  79     args_parse (&args, argc, argv);
  80
  81     if (args.files) {
  82         int i;
  83         rr_board_t *board;
  84         rrs_solution_t solution;
  85
  86         for (i = 0; args.files[i]; i++) {
  87             board = rr_board_create_from_file (args.files[i]);
  88             if (board == NULL) {
  89                 fprintf (stderr, "Failed to parse board in %s\n", args.files[i]);
  90                 continue;
  91             }
  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);
  97         }
  98     } else {
  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);
 103             return 1;
 104         }
 105
 106         status = rr_client_join (client, args.game);
 107         if (status == RR_STATUS_NO_GAME)
 108             status = rr_client_new (client, args.game);
 109         if (status) {
 110             fprintf (stderr, "Error joining or creating game: %s\n", rr_status_str (status));
 111             return 1;
 112         }
 113
 114         handle_events (client);
 115
 116         rr_client_destroy (client);
 117     }
 118
 119     return 0;
 120 }
 121
 122 static void
 123 handle_events (rr_client_t *client)
 124 {
 125     int i;
 126     rr_status_t status;
 127     rr_notice_t *notice;
 128     rrs_solution_t solution;
 129     rr_board_t *board;
 130     char *diagram;
 131     struct timespec move_delay = { 1, 200000000l };
 132
 133     /* XXX: This block of code can go away when add a NOTICE BOARD
 134        for new users joining a game. */
 135     {
 136         status = rr_client_show (client, &diagram);
 137         if (status) {
 138             fprintf (stderr, "Error in rr_client_show: %s\n", rr_status_str (status));
 139             goto DONE;
 140         }
 141         board = rr_board_create_from_str (diagram);
 142         free (diagram);
 143     }
 144
 145     /* XXX: This block of code can go away when we add a NOTICE TURN
 146        for new users joining a game in progress. */
 147     {
 148         rrs_solution_init (&solution);
 149         solve_board (board, &solution);
 150         rr_client_bid (client, solution.num_moves);
 151         rr_client_nobid (client);
 152     }
 153
 154     while (1) {
 155         status = rr_client_next_notice (client, &notice);
 156         if (status) {
 157             if (status == RR_STATUS_EOF)
 158                 fprintf (stderr, "Server has disconnected. Exiting.\n");
 159             else
 160                 fprintf (stderr, "ERROR during rr_client_next_notice: %s\n",
 161                          rr_status_str (status));
 162             return;
 163         }
 164         if (!notice) {
 165             fprintf (stderr, "No notice during rr_client_next_notice\n");
 166             continue;
 167         }
 168
 169         switch  (notice->type) {
 170         case RR_NOTICE_BOARD:
 171             rr_board_parse (board, notice->u.string);
 172             break;
 173         case RR_NOTICE_TURN:
 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);
 179             break;
 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);
 185                 if (status) {
 186                     rr_client_message (client, "Drat, looks like I was wrong.");
 187                     rr_client_pass (client);
 188                     break;
 189                 }
 190                 nanosleep (&move_delay, NULL);
 191             }
 192             rrs_solution_fini (&solution);
 193             break;
 194         case RR_NOTICE_ABANDON:
 195             rr_client_abandon (client);
 196             break;
 197         case RR_NOTICE_NOBID:
 198             rr_client_nobid (client);
 199             break;
 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);
 205             break;
 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);
 212                 }
 213             }
 214             break;
 215         case RR_NOTICE_GAMEOVER:
 216         case RR_NOTICE_GAME:
 217         case RR_NOTICE_USER:
 218         case RR_NOTICE_JOIN:
 219         case RR_NOTICE_QUIT:
 220         case RR_NOTICE_DISPOSE:
 221         case RR_NOTICE_MESSAGE:
 222         case RR_NOTICE_WATCH:
 223         case RR_NOTICE_PART:
 224         case RR_NOTICE_BID:
 225         case RR_NOTICE_REVOKE:
 226         case RR_NOTICE_TIMER:
 227         case RR_NOTICE_ACTIVE:
 228         case RR_NOTICE_MOVE:
 229         case RR_NOTICE_UNDO:
 230         case RR_NOTICE_RESET:
 231         case RR_NOTICE_SCORE:
 232             /* Ignore these notices */
 233             break;
 234         }
 235         free (notice);
 236     }
 237
 238   DONE:
 239     if (notice)
 240         free (notice);
 241     if (board)
 242         rr_board_destroy (board);
 243 }
 244
 245 static void
 246 rrs_solution_print (rrs_solution_t *solution)
 247 {
 248     int i;
 249     rr_robot_t last_robot;
 250     rrs_move_t *move;
 251
 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));
 257         else
 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;
 261     }
 262     printf ("\n");
 263 }
 264
 265 static rrs_state_t
 266 rrs_state_get_from_board (rr_board_t *board)
 267 {
 268     int i;
 269     int x, y;
 270     rrs_state_t state;
 271
 272     state = 0;
 273
 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);
 277     }
 278
 279     return state;
 280 }
 281
 282 static void
 283 rrs_state_set_board (rrs_state_t state, rr_board_t *board)
 284 {
 285     int i;
 286     int x, y;
 287
 288     for (i=0; i < RR_NUM_ROBOTS; i++)
 289         rr_board_remove_robot (board, rr_robot_from_idx (i));
 290
 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);
 294     }
 295 }
 296
 297 static rr_status_t
 298 solve_board (rr_board_t *board, rrs_solution_t *solution)
 299 {
 300     rr_status_t status;
 301     int i, moves;
 302     rrs_state_t solution_state;
 303     rrs_state_buf_t **states;
 304     struct timeval tv_start, tv_end;
 305
 306     if (rr_board_solved (board)) {
 307         printf ("Board is solved to begin with.\n");
 308         return RR_STATUS_SUCCESS;
 309     }
 310
 311     printf ("Now trying to solve:");
 312     puts (rr_board_to_str (board));
 313
 314     gettimeofday (&tv_start, NULL);
 315
 316     status = find_solution_states (board, &states, &moves, &solution_state);
 317     if (status)
 318         return status;
 319
 320     gettimeofday (&tv_end, NULL);
 321
 322     if (moves < 0) {
 323         printf ("It seems impossible.\n");
 324     } else {
 325         printf ("Found solution of %d moves in %g seconds.\n",
 326                 moves,
 327                 tv_end.tv_sec - tv_start.tv_sec
 328                 + (tv_end.tv_usec - tv_start.tv_usec) / 1e6);
 329
 330         gettimeofday (&tv_start, NULL);
 331
 332         trace_solution (board, states, moves, solution_state, solution);
 333
 334         gettimeofday (&tv_end, NULL);
 335
 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);
 339     }
 340
 341     for (i=0; i <= moves; i++) {
 342         rrs_state_buf_destroy (states[i]);
 343         states[i] = NULL;
 344     }
 345
 346     free (states);
 347
 348     return RR_STATUS_SUCCESS;
 349 }
 350
 351 static int
 352 rrs_state_connected (rrs_state_t a, rrs_state_t b,
 353                      rr_robot_t *robot, rr_direction_t *dir)
 354 {
 355     int i;
 356     int nib;
 357     rrs_state_t diff, mask;
 358     int shift, delta;
 359
 360     diff = a ^ b;
 361
 362     nib = -1;
 363     for (i=0; i < 8; i++) {
 364         if (diff & 0xf) {
 365             if (nib > 0)
 366                 return 0;
 367             else
 368                 nib = i;
 369         }
 370         diff >>= 4;
 371     }
 372
 373     switch (nib) {
 374     case 0:
 375     case 1:
 376         *robot = RR_ROBOT_BLUE;
 377         break;
 378     case 2:
 379     case 3:
 380         *robot = RR_ROBOT_GREEN;
 381         break;
 382     case 4:
 383     case 5:
 384         *robot = RR_ROBOT_RED;
 385         break;
 386     case 6:
 387     case 7:
 388         *robot = RR_ROBOT_YELLOW;
 389         break;
 390     }
 391
 392     shift = 4 * nib;
 393     mask = 0xf << shift;
 394     delta = ((b & mask) >> shift) - ((a & mask) >> shift);
 395
 396     if (nib % 2)
 397         if (delta < 0)
 398             *dir = RR_DIRECTION_WEST;
 399         else
 400             *dir = RR_DIRECTION_EAST;
 401     else
 402         if (delta < 0)
 403             *dir = RR_DIRECTION_NORTH;
 404         else
 405             *dir = RR_DIRECTION_SOUTH;
 406
 407     return 1;
 408 }
 409
 410 static void
 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)
 415 {
 416     rr_status_t status;
 417     int i, j;
 418     rrs_state_buf_t *buf;
 419     int found_move = 0;
 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;
 423
 424     for (i = moves-1; i >= 0; i--) {
 425         buf = states[i];
 426         for (j = 0; j < buf->num_states; j++) {
 427             if (rrs_state_connected (buf->state[j], solution_state,
 428                                      &robot, &dir)) {
 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) {
 433                         found_move = 1;
 434                         robot_found = robot;
 435                         dir_found = dir;
 436                         state_found = buf->state[j];
 437                         if (robot_found == last_robot_found)
 438                             goto NEXT_MOVE;
 439                         else
 440                             last_robot_found = robot_found;
 441                     }
 442                 }
 443             }
 444         }
 445       NEXT_MOVE:
 446         if (found_move) {
 447             rrs_solution_prepend (solution, robot_found, dir_found);
 448             solution_state = state_found;
 449         } else {
 450             fprintf (stderr, "ERROR: Failed to trace solution backwards to 0x%x at move %d\n",
 451                      solution_state, i+1);
 452             break;
 453         }
 454     }
 455 }
 456
 457 static rr_status_t
 458 find_solution_states (rr_board_t *board,
 459                       rrs_state_buf_t ***solution_states,
 460                       int *num_state_buf,
 461                       rrs_state_t *final_state)
 462 {
 463     int solved, moves;
 464     rrs_state_t initial;
 465     rrs_state_buf_t **states, **new_states;
 466
 467     states = malloc (sizeof (rrs_state_buf_t *));
 468     if (states == NULL)
 469         return RR_STATUS_NO_MEMORY;
 470
 471     initial = rrs_state_get_from_board (board);
 472
 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);
 477
 478     moves = 0;
 479     while (1) {
 480         moves++;
 481
 482         new_states = realloc (states, (moves + 1) * sizeof (rrs_state_buf_t *));
 483         if (new_states == NULL)
 484             return RR_STATUS_NO_MEMORY;
 485
 486         states = new_states;
 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;
 491
 492         solved = rrs_find_new_states (board, states, moves-1, states[moves], final_state);
 493
 494         if (solved)
 495             break;
 496
 497         if (states[moves]->num_states == 0) {
 498             printf ("Can't make any further progress after %d moves.\n", moves);
 499             moves = -1;
 500             break;
 501         } else {
 502             printf ("Move #%d generated %d new states.\n",
 503                     moves, states[moves]->num_states);
 504         }
 505     }
 506
 507     *num_state_buf = moves;
 508     *solution_states = states;
 509
 510     return RR_STATUS_SUCCESS;
 511 }
 512
 513 static int
 514 state_has_been_seen (rrs_state_buf_t **previous,
 515                      int moves,
 516                      rrs_state_t state)
 517 {
 518     int i;
 519
 520     for (i=0; i <= moves; i++)
 521         if (rrs_state_buf_contains (previous[i], state))
 522             return 1;
 523     return 0;
 524 }
 525
 526 static int
 527 rrs_find_new_states (rr_board_t *board,
 528                      rrs_state_buf_t **previous,
 529                      int moves,
 530                      rrs_state_buf_t *new,
 531                      rrs_state_t *solution_state)
 532 {
 533     int i, ri;
 534     rr_direction_t dir;
 535     rrs_state_t state, new_state;
 536     rrs_state_buf_t *initial;
 537     rr_status_t status;
 538     rr_robot_t robot;
 539
 540     initial = previous[moves];
 541
 542     for (i = 0; i < initial->num_states; i++) {
 543         state = initial->state[i];
 544
 545         rrs_state_set_board (state, board);
 546
 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;
 559                             return 1;
 560                         }
 561                     }
 562                     rr_board_undo (board);
 563                 }
 564             }
 565         }
 566     }
 567
 568     return 0;
 569 }
 570