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 #define HOST "localhost"
  36 #define PORT "5252"
  37 #define USER "rrsolve"
  38 #define GAME "game"
  39
  40 /* Tuning this can reduce excess reallocs */
  41 #define RRS_BRANCHING_FACTOR_ESTIMATE 10
  42
  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; }
  45
  46 static void
  47 handle_events (rr_client_t *client);
  48
  49 static rrs_state_t
  50 rrs_state_get_from_board (rr_board_t *board);
  51
  52 static void
  53 rrs_solution_print (rrs_solution_t *solution);
  54
  55 static rr_status_t
  56 solve_board (rr_board_t *board, rrs_solution_t *solution);
  57
  58 static rr_status_t
  59 find_solution_states (rr_board_t *board,
  60                       rrs_state_buf_t ***solution_states,
  61                       int *num_state_buf,
  62                       rrs_state_t *final_state);
  63
  64 static int
  65 rrs_find_new_states (rr_board_t *board,
  66                      rrs_state_buf_t **previous,
  67                      int moves,
  68                      rrs_state_buf_t *new,
  69                      rrs_state_t *solution_state);
  70
  71 static void
  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);
  76
  77 int
  78 main (int argc, char *argv[])
  79 {
  80     args_t args;
  81     rr_status_t status;
  82     rr_client_t *client;
  83
  84     args_parse (&args, argc, argv);
  85
  86     if (args.files) {
  87         int i;
  88         rr_board_t *board;
  89         rrs_solution_t solution;
  90
  91         for (i = 0; args.files[i]; i++) {
  92             board = rr_board_create_from_file (args.files[i]);
  93             if (board == NULL)
  94                 continue;
  95             rrs_solution_init (&solution);
  96             solve_board (board, &solution);
  97             rrs_solution_print (&solution);
  98             rrs_solution_fini (&solution);
  99             rr_board_destroy (board);
 100         }
 101     } else {
 102         client = rr_client_create (args.host, args.port, args.user);
 103         if (client == NULL) {
 104             fprintf (stderr, "Failed connecting to %s:%s as %s\n",
 105                      args.host, args.port, args.user);
 106             return 1;
 107         }
 108
 109         status = rr_client_join (client, GAME);
 110         if (status == RR_STATUS_NO_GAME)
 111             status = rr_client_new (client, GAME);
 112         if (status) {
 113             fprintf (stderr, "Error joining or creating game: %s\n", rr_status_str (status));
 114             return 1;
 115         }
 116
 117         handle_events (client);
 118
 119         rr_client_destroy (client);
 120     }
 121
 122     return 0;
 123 }
 124
 125 static void
 126 handle_events (rr_client_t *client)
 127 {
 128     int i;
 129     rr_status_t status;
 130     rr_notice_t *notice;
 131     rrs_solution_t solution;
 132     rr_board_t *board;
 133     char *diagram;
 134     struct timespec move_delay = { 1, 200000000l };
 135
 136     /* XXX: This block of code can go away when add a NOTICE BOARD
 137        for new users joining a game. */
 138     {
 139         status = rr_client_show (client, &diagram);
 140         if (status) {
 141             fprintf (stderr, "Error in rr_client_show: %s\n", rr_status_str (status));
 142             goto DONE;
 143         }
 144         board = rr_board_create_from_str (diagram);
 145         free (diagram);
 146     }
 147
 148     /* XXX: This block of code can go away when we add a NOTICE TURN
 149        for new users joining a game in progress. */
 150     {
 151         rrs_solution_init (&solution);
 152         solve_board (board, &solution);
 153         rr_client_bid (client, solution.num_moves);
 154     }
 155
 156     while (1) {
 157         status = rr_client_next_notice (client, &notice);
 158         if (status) {
 159             if (status == RR_STATUS_EOF)
 160                 fprintf (stderr, "Server has disconnected. Exiting.\n");
 161             else
 162                 fprintf (stderr, "ERROR during rr_client_next_notice: %s\n",
 163                          rr_status_str (status));
 164             return;
 165         }
 166         if (!notice) {
 167             fprintf (stderr, "No notice during rr_client_next_notice\n");
 168             continue;
 169         }
 170
 171         switch  (notice->type) {
 172         /* XXX: The processing needed for GAMEOVER, JOIN, and TURN
 173            is a mess right now. There should be one NOTICE to say
 174            the board has changed and one to say a TURN has started,
 175            rather than the current mess. */
 176         case RR_NOTICE_GAMEOVER:
 177             status = rr_client_show (client, &diagram);
 178             if (status) {
 179                 fprintf (stderr, "Error in rr_client_show: %s\n", rr_status_str (status));
 180                 goto DONE;
 181             }
 182             rr_board_parse (board, diagram);
 183             free (diagram);
 184             break;
 185         case RR_NOTICE_TURN:
 186             rr_board_set_goal_target (board, notice->u.target);
 187             rrs_solution_init (&solution);
 188             solve_board (board, &solution);
 189             rr_client_bid (client, solution.num_moves);
 190             break;
 191         case RR_NOTICE_ACTIVATE:
 192             for (i = 0; i < solution.num_moves; i++) {
 193                 status = rr_client_move (client,
 194                                          solution.move[i].robot,
 195                                          solution.move[i].dir);
 196                 if (status) {
 197                     rr_client_message (client, "Drat, looks like I was wrong.");
 198                     rr_client_pass (client);
 199                     break;
 200                 }
 201                 nanosleep (&move_delay, NULL);
 202             }
 203             rrs_solution_fini (&solution);
 204             break;
 205         case RR_NOTICE_ABANDON:
 206             rr_client_abandon (client);
 207             break;
 208         case RR_NOTICE_NOBID:
 209             rr_client_nobid (client);
 210             break;
 211         case RR_NOTICE_POSITION:
 212             rr_board_position_robot (board,
 213                                      notice->u.position.robot,
 214                                      notice->u.position.x,
 215                                      notice->u.position.y);
 216             break;
 217         case RR_NOTICE_GAMESTATE:
 218             if (notice->u.gamestate == RR_GAMESTATE_SHOW) {
 219                 if (solution.num_moves) {
 220                     printf ("My solution (%d moves):", solution.num_moves);
 221                     rrs_solution_print (&solution);
 222                 }
 223             }
 224             break;
 225         case RR_NOTICE_GAME:
 226         case RR_NOTICE_USER:
 227         case RR_NOTICE_JOIN:
 228         case RR_NOTICE_QUIT:
 229         case RR_NOTICE_DISPOSE:
 230         case RR_NOTICE_MESSAGE:
 231         case RR_NOTICE_WATCH:
 232         case RR_NOTICE_PART:
 233         case RR_NOTICE_BID:
 234         case RR_NOTICE_REVOKE:
 235         case RR_NOTICE_TIMER:
 236         case RR_NOTICE_ACTIVE:
 237         case RR_NOTICE_MOVE:
 238         case RR_NOTICE_UNDO:
 239         case RR_NOTICE_RESET:
 240         case RR_NOTICE_SCORE:
 241             /* Ignore these notices */
 242             break;
 243         }
 244         free (notice);
 245     }
 246
 247   DONE:
 248     if (notice)
 249         free (notice);
 250     if (board)
 251         rr_board_destroy (board);
 252 }
 253
 254 static void
 255 rrs_solution_print (rrs_solution_t *solution)
 256 {
 257     int i;
 258     rr_robot_t last_robot;
 259     rrs_move_t *move;
 260
 261     last_robot = RR_ROBOT_NONE;
 262     for (i=0; i < solution->num_moves; i++) {
 263         move = &solution->move[i];
 264         if (move->robot == last_robot)
 265             printf (", %s", rr_direction_str (move->dir));
 266         else
 267             printf ("\n Move #%d: %s %s",
 268                     i+1, rr_robot_str (move->robot), rr_direction_str (move->dir));
 269         last_robot = move->robot;
 270     }
 271     printf ("\n");
 272 }
 273
 274 static rrs_state_t
 275 rrs_state_get_from_board (rr_board_t *board)
 276 {
 277     int i;
 278     int x, y;
 279     rrs_state_t state;
 280
 281     state = 0;
 282
 283     for (i=0; i < RR_NUM_ROBOTS; i++) {
 284         rr_board_find_robot (board, rr_robot_from_idx (i), &x, &y);
 285         RRS_STATE_SET_ROBOT (state, i, x, y);
 286     }
 287
 288     return state;
 289 }
 290
 291 static void
 292 rrs_state_set_board (rrs_state_t state, rr_board_t *board)
 293 {
 294     int i;
 295     int x, y;
 296
 297     for (i=0; i < RR_NUM_ROBOTS; i++) {
 298         RRS_STATE_GET_ROBOT (state, i, x, y);
 299         rr_board_position_robot (board, rr_robot_from_idx (i), x, y);
 300     }
 301
 302 }
 303
 304 static rr_status_t
 305 solve_board (rr_board_t *board, rrs_solution_t *solution)
 306 {
 307     rr_status_t status;
 308     int i, moves;
 309     rrs_state_t solution_state;
 310     rrs_state_buf_t **states;
 311     struct timeval tv_start, tv_end;
 312
 313     if (rr_board_solved (board)) {
 314         printf ("Board is solved to begin with.\n");
 315         return RR_STATUS_SUCCESS;
 316     }
 317
 318     printf ("Now trying to solve:");
 319     puts (rr_board_to_str (board));
 320
 321     gettimeofday (&tv_start, NULL);
 322
 323     status = find_solution_states (board, &states, &moves, &solution_state);
 324     if (status)
 325         return status;
 326
 327     gettimeofday (&tv_end, NULL);
 328
 329     if (moves < 0) {
 330         printf ("It seems impossible.\n");
 331     } else {
 332         printf ("Found solution of %d moves in %g seconds.\n",
 333                 moves,
 334                 tv_end.tv_sec - tv_start.tv_sec
 335                 + (tv_end.tv_usec - tv_start.tv_usec) / 1e6);
 336
 337         gettimeofday (&tv_start, NULL);
 338
 339         trace_solution (board, states, moves, solution_state, solution);
 340
 341         gettimeofday (&tv_end, NULL);
 342
 343         printf ("Traced solution in %g seconds.\n",
 344                 tv_end.tv_sec - tv_start.tv_sec
 345                 + (tv_end.tv_usec - tv_start.tv_usec) / 1e6);
 346     }
 347
 348     for (i=0; i <= moves; i++) {
 349         rrs_state_buf_destroy (states[i]);
 350         states[i] = NULL;
 351     }
 352
 353     free (states);
 354
 355     return RR_STATUS_SUCCESS;
 356 }
 357
 358 static int
 359 rrs_state_connected (rrs_state_t a, rrs_state_t b,
 360                      rr_robot_t *robot, rr_direction_t *dir)
 361 {
 362     int i;
 363     int nib;
 364     rrs_state_t diff, mask;
 365     int shift, delta;
 366
 367     diff = a ^ b;
 368
 369     nib = -1;
 370     for (i=0; i < 8; i++) {
 371         if (diff & 0xf) {
 372             if (nib > 0)
 373                 return 0;
 374             else
 375                 nib = i;
 376         }
 377         diff >>= 4;
 378     }
 379
 380     switch (nib) {
 381     case 0:
 382     case 1:
 383         *robot = RR_ROBOT_BLUE;
 384         break;
 385     case 2:
 386     case 3:
 387         *robot = RR_ROBOT_GREEN;
 388         break;
 389     case 4:
 390     case 5:
 391         *robot = RR_ROBOT_RED;
 392         break;
 393     case 6:
 394     case 7:
 395         *robot = RR_ROBOT_YELLOW;
 396         break;
 397     }
 398
 399     shift = 4 * nib;
 400     mask = 0xf << shift;
 401     delta = ((b & mask) >> shift) - ((a & mask) >> shift);
 402
 403     if (nib % 2)
 404         if (delta < 0)
 405             *dir = RR_DIRECTION_WEST;
 406         else
 407             *dir = RR_DIRECTION_EAST;
 408     else
 409         if (delta < 0)
 410             *dir = RR_DIRECTION_NORTH;
 411         else
 412             *dir = RR_DIRECTION_SOUTH;
 413
 414     return 1;
 415 }
 416
 417 static void
 418 trace_solution (rr_board_t *board,
 419                 rrs_state_buf_t **states, int moves,
 420                 rrs_state_t solution_state,
 421                 rrs_solution_t *solution)
 422 {
 423     rr_status_t status;
 424     int i, j;
 425     rrs_state_buf_t *buf;
 426     int found_move;
 427     rr_robot_t robot, robot_found, last_robot_found = RR_ROBOT_NONE;
 428     rr_direction_t dir, dir_found;
 429     rrs_state_t state_found;
 430
 431     for (i = moves-1; i >= 0; i--) {
 432         buf = states[i];
 433         for (j = 0; j < buf->num_states; j++) {
 434             if (rrs_state_connected (buf->state[j], solution_state,
 435                                      &robot, &dir)) {
 436                 rrs_state_set_board (buf->state[j], board);
 437                 status = rr_board_move (board, robot, dir);
 438                 if (status == RR_STATUS_SUCCESS) {
 439                     if (rrs_state_get_from_board (board) == solution_state) {
 440                         found_move = 1;
 441                         robot_found = robot;
 442                         dir_found = dir;
 443                         state_found = buf->state[j];
 444                         if (robot_found == last_robot_found)
 445                             goto NEXT_MOVE;
 446                         else
 447                             last_robot_found = robot_found;
 448                     }
 449                 }
 450             }
 451         }
 452       NEXT_MOVE:
 453         if (found_move) {
 454             rrs_solution_prepend (solution, robot_found, dir_found);
 455             solution_state = state_found;
 456         } else {
 457             fprintf (stderr, "ERROR: Failed to trace solution backwards to 0x%x at move %d\n",
 458                      solution_state, i+1);
 459             break;
 460         }
 461     }
 462 }
 463
 464 static rr_status_t
 465 find_solution_states (rr_board_t *board,
 466                       rrs_state_buf_t ***solution_states,
 467                       int *num_state_buf,
 468                       rrs_state_t *final_state)
 469 {
 470     int solved, moves;
 471     rrs_state_t initial;
 472     rrs_state_buf_t **states, **new_states;
 473
 474     states = malloc (sizeof (rrs_state_buf_t *));
 475     if (states == NULL)
 476         return RR_STATUS_NO_MEMORY;
 477
 478     initial = rrs_state_get_from_board (board);
 479
 480     states[0] = rrs_state_buf_create (1);
 481     if (states[0] == NULL)
 482         return RR_STATUS_NO_MEMORY;
 483     rrs_state_buf_add (states[0], initial);
 484
 485     moves = 0;
 486     while (1) {
 487         moves++;
 488
 489         new_states = realloc (states, (moves + 1) * sizeof (rrs_state_buf_t *));
 490         if (new_states == NULL)
 491             return RR_STATUS_NO_MEMORY;
 492
 493         states = new_states;
 494         states[moves] = rrs_state_buf_create (RRS_BRANCHING_FACTOR_ESTIMATE
 495                                               * states[moves-1]->num_states);
 496         if (states[moves] == NULL)
 497             return RR_STATUS_NO_MEMORY;
 498
 499         solved = rrs_find_new_states (board, states, moves-1, states[moves], final_state);
 500
 501         if (solved)
 502             break;
 503
 504         if (states[moves]->num_states == 0) {
 505             printf ("Can't make any further progress after %d moves.\n", moves);
 506             moves = -1;
 507             break;
 508         } else {
 509             printf ("Move #%d generated %d new states.\n",
 510                     moves, states[moves]->num_states);
 511         }
 512     }
 513
 514     *num_state_buf = moves;
 515     *solution_states = states;
 516
 517     return RR_STATUS_SUCCESS;
 518 }
 519
 520 static int
 521 state_has_been_seen (rrs_state_buf_t **previous,
 522                      int moves,
 523                      rrs_state_t state)
 524 {
 525     int i;
 526
 527     for (i=0; i <= moves; i++)
 528         if (rrs_state_buf_contains (previous[i], state))
 529             return 1;
 530     return 0;
 531 }
 532
 533 static int
 534 rrs_find_new_states (rr_board_t *board,
 535                      rrs_state_buf_t **previous,
 536                      int moves,
 537                      rrs_state_buf_t *new,
 538                      rrs_state_t *solution_state)
 539 {
 540     int i, ri;
 541     rr_direction_t dir;
 542     rrs_state_t state, new_state;
 543     rrs_state_buf_t *initial;
 544     rr_status_t status;
 545     rr_robot_t robot;
 546
 547     initial = previous[moves];
 548
 549     for (i = 0; i < initial->num_states; i++) {
 550         state = initial->state[i];
 551
 552         rrs_state_set_board (state, board);
 553         for (ri = 0; ri < RR_NUM_ROBOTS; ri++) {
 554             robot = rr_robot_from_idx (ri);
 555             for (dir = RR_DIRECTION_NORTH; dir <= RR_DIRECTION_EAST; dir++) {
 556                 status = rr_board_move (board, robot, dir);
 557                 if (status == RR_STATUS_SUCCESS) {
 558                     new_state = rrs_state_get_from_board (board);
 559                     if (! state_has_been_seen (previous, moves, new_state)) {
 560                         rrs_state_buf_add_sorted (new, new_state);
 561                         if (rr_board_solved (board)) {
 562                             *solution_state = new_state;
 563                             return 1;
 564                         }
 565                     }
 566                     rr_board_undo (board);
 567                 }
 568             }
 569         }
 570     }
 571
 572     return 0;
 573 }
 574