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, char *name);
  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, args.user);
 115
 116         rr_client_destroy (client);
 117     }
 118
 119     return 0;
 120 }
 121
 122 static void
 123 handle_events (rr_client_t *client, char *name)
 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 = { 0, 800000000l };
 132     rr_players_t *players;
 133
 134     rr_client_players (client, &players);
 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         rr_client_nobid (client);
 155     }
 156
 157     while (1) {
 158         status = rr_client_next_notice (client, &notice);
 159         if (status) {
 160             if (status == RR_STATUS_EOF)
 161                 fprintf (stderr, "Server has disconnected. Exiting.\n");
 162             else
 163                 fprintf (stderr, "ERROR during rr_client_next_notice: %s\n",
 164                          rr_status_str (status));
 165             return;
 166         }
 167         if (!notice) {
 168             fprintf (stderr, "No notice during rr_client_next_notice\n");
 169             continue;
 170         }
 171
 172         switch  (notice->type) {
 173         case RR_NOTICE_BOARD:
 174             rr_board_parse (board, notice->u.string);
 175             break;
 176         case RR_NOTICE_TURN:
 177             rr_board_set_goal_target (board, notice->u.target);
 178             rrs_solution_init (&solution);
 179             solve_board (board, &solution);
 180             rr_client_bid (client, solution.num_moves);
 181             rr_client_nobid (client);
 182             break;
 183         case RR_NOTICE_ACTIVATE:
 184             for (i = 0; i < solution.num_moves; i++) {
 185                 status = rr_client_move (client,
 186                                          solution.move[i].robot,
 187                                          solution.move[i].dir);
 188                 if (status) {
 189                     rr_client_message (client, "Drat, looks like I was wrong.");
 190                     rr_client_pass (client);
 191                     break;
 192                 }
 193                 nanosleep (&move_delay, NULL);
 194             }
 195             rrs_solution_fini (&solution);
 196             break;
 197         case RR_NOTICE_ABANDON:
 198             rr_client_abandon (client);
 199             break;
 200         case RR_NOTICE_NOBID:
 201             rr_client_nobid (client);
 202             break;
 203         case RR_NOTICE_POSITION:
 204             rr_board_add_robot (board,
 205                                 notice->u.position.robot,
 206                                 notice->u.position.x,
 207                                 notice->u.position.y);
 208             break;
 209         case RR_NOTICE_GAMESTATE:
 210             if (notice->u.gamestate == RR_GAMESTATE_DONE
 211                 || notice->u.gamestate == RR_GAMESTATE_SHOW) {
 212                 if (solution.num_moves) {
 213                     printf ("My solution (%d moves):", solution.num_moves);
 214                     rrs_solution_print (&solution);
 215                 }
 216             }
 217             break;
 218         case RR_NOTICE_BID:
 219             /* rrsolve is kind enought to offer pity points */
 220             if (notice->u.bid.number == solution.num_moves &&
 221                 strcmp (notice->u.bid.username, name) &&
 222                 rr_players_get_score (players, notice->u.bid.username) < rr_players_get_score (players, name))
 223             {
 224                 rr_client_revoke (client);
 225                 rr_client_bid (client, solution.num_moves);
 226             }
 227             break;
 228         case RR_NOTICE_JOIN:
 229             rr_players_add (players, notice->u.string);
 230             break;
 231         case RR_NOTICE_PART:
 232             rr_players_remove (players, notice->u.string);
 233             break;
 234         case RR_NOTICE_SCORE:
 235             rr_players_set_score (players, notice->u.bid.username, notice->u.bid.number);
 236             break;
 237         case RR_NOTICE_GAMEOVER:
 238         case RR_NOTICE_GAME:
 239         case RR_NOTICE_USER:
 240         case RR_NOTICE_QUIT:
 241         case RR_NOTICE_DISPOSE:
 242         case RR_NOTICE_MESSAGE:
 243         case RR_NOTICE_WATCH:
 244         case RR_NOTICE_REVOKE:
 245         case RR_NOTICE_TIMER:
 246         case RR_NOTICE_ACTIVE:
 247         case RR_NOTICE_MOVE:
 248         case RR_NOTICE_UNDO:
 249         case RR_NOTICE_RESET:
 250             /* Ignore these notices */
 251             break;
 252         }
 253         free (notice);
 254     }
 255
 256   DONE:
 257     if (notice)
 258         free (notice);
 259     if (board)
 260         rr_board_destroy (board);
 261 }
 262
 263 static void
 264 rrs_solution_print (rrs_solution_t *solution)
 265 {
 266     int i;
 267     rr_robot_t last_robot;
 268     rrs_move_t *move;
 269
 270     last_robot = RR_ROBOT_NONE;
 271     for (i=0; i < solution->num_moves; i++) {
 272         move = &solution->move[i];
 273         if (move->robot == last_robot)
 274             printf (", %s", rr_direction_str (move->dir));
 275         else
 276             printf ("\n Move #%d: %s %s",
 277                     i+1, rr_robot_str (move->robot), rr_direction_str (move->dir));
 278         last_robot = move->robot;
 279     }
 280     printf ("\n");
 281 }
 282
 283 static rrs_state_t
 284 rrs_state_get_from_board (rr_board_t *board)
 285 {
 286     int i;
 287     int x, y;
 288     rrs_state_t state;
 289
 290     state = 0;
 291
 292     for (i=0; i < RR_NUM_ROBOTS; i++) {
 293         rr_board_find_robot (board, rr_robot_from_idx (i), &x, &y);
 294         RRS_STATE_SET_ROBOT (state, i, x, y);
 295     }
 296
 297     return state;
 298 }
 299
 300 static void
 301 rrs_state_set_board (rrs_state_t state, rr_board_t *board)
 302 {
 303     int i;
 304     int x, y;
 305
 306     for (i=0; i < RR_NUM_ROBOTS; i++)
 307         rr_board_remove_robot (board, rr_robot_from_idx (i));
 308
 309     for (i=0; i < RR_NUM_ROBOTS; i++) {
 310         RRS_STATE_GET_ROBOT (state, i, x, y);
 311         rr_board_add_robot (board, rr_robot_from_idx (i), x, y);
 312     }
 313 }
 314
 315 static rr_status_t
 316 solve_board (rr_board_t *board, rrs_solution_t *solution)
 317 {
 318     rr_status_t status;
 319     int i, moves;
 320     rrs_state_t solution_state;
 321     rrs_state_buf_t **states;
 322     struct timeval tv_start, tv_end;
 323
 324     if (rr_board_solved (board)) {
 325         printf ("Board is solved to begin with.\n");
 326         return RR_STATUS_SUCCESS;
 327     }
 328
 329     printf ("Now trying to solve:");
 330     puts (rr_board_to_str (board));
 331
 332     gettimeofday (&tv_start, NULL);
 333
 334     status = find_solution_states (board, &states, &moves, &solution_state);
 335     if (status)
 336         return status;
 337
 338     gettimeofday (&tv_end, NULL);
 339
 340     if (moves < 0) {
 341         printf ("It seems impossible.\n");
 342     } else {
 343         printf ("Found solution of %d moves in %g seconds.\n",
 344                 moves,
 345                 tv_end.tv_sec - tv_start.tv_sec
 346                 + (tv_end.tv_usec - tv_start.tv_usec) / 1e6);
 347
 348         gettimeofday (&tv_start, NULL);
 349
 350         trace_solution (board, states, moves, solution_state, solution);
 351
 352         gettimeofday (&tv_end, NULL);
 353
 354         printf ("Traced solution in %g seconds.\n",
 355                 tv_end.tv_sec - tv_start.tv_sec
 356                 + (tv_end.tv_usec - tv_start.tv_usec) / 1e6);
 357     }
 358
 359     for (i=0; i <= moves; i++) {
 360         rrs_state_buf_destroy (states[i]);
 361         states[i] = NULL;
 362     }
 363
 364     free (states);
 365
 366     return RR_STATUS_SUCCESS;
 367 }
 368
 369 static int
 370 rrs_state_connected (rrs_state_t a, rrs_state_t b,
 371                      rr_robot_t *robot, rr_direction_t *dir)
 372 {
 373     int i;
 374     int nib;
 375     rrs_state_t diff, mask;
 376     int shift, delta;
 377
 378     diff = a ^ b;
 379
 380     nib = -1;
 381     for (i=0; i < 8; i++) {
 382         if (diff & 0xf) {
 383             if (nib > 0)
 384                 return 0;
 385             else
 386                 nib = i;
 387         }
 388         diff >>= 4;
 389     }
 390
 391     switch (nib) {
 392     case 0:
 393     case 1:
 394         *robot = RR_ROBOT_BLUE;
 395         break;
 396     case 2:
 397     case 3:
 398         *robot = RR_ROBOT_GREEN;
 399         break;
 400     case 4:
 401     case 5:
 402         *robot = RR_ROBOT_RED;
 403         break;
 404     case 6:
 405     case 7:
 406         *robot = RR_ROBOT_YELLOW;
 407         break;
 408     }
 409
 410     shift = 4 * nib;
 411     mask = 0xf << shift;
 412     delta = ((b & mask) >> shift) - ((a & mask) >> shift);
 413
 414     if (nib % 2)
 415         if (delta < 0)
 416             *dir = RR_DIRECTION_WEST;
 417         else
 418             *dir = RR_DIRECTION_EAST;
 419     else
 420         if (delta < 0)
 421             *dir = RR_DIRECTION_NORTH;
 422         else
 423             *dir = RR_DIRECTION_SOUTH;
 424
 425     return 1;
 426 }
 427
 428 static void
 429 trace_solution (rr_board_t *board,
 430                 rrs_state_buf_t **states, int moves,
 431                 rrs_state_t solution_state,
 432                 rrs_solution_t *solution)
 433 {
 434     rr_status_t status;
 435     int i, j;
 436     rrs_state_buf_t *buf;
 437     int found_move = 0;
 438     rr_robot_t robot, robot_found, last_robot_found = RR_ROBOT_NONE;
 439     rr_direction_t dir, dir_found;
 440     rrs_state_t state_found;
 441
 442     for (i = moves-1; i >= 0; i--) {
 443         buf = states[i];
 444         for (j = 0; j < buf->num_states; j++) {
 445             if (rrs_state_connected (buf->state[j], solution_state,
 446                                      &robot, &dir)) {
 447                 rrs_state_set_board (buf->state[j], board);
 448                 status = rr_board_move (board, robot, dir);
 449                 if (status == RR_STATUS_SUCCESS) {
 450                     if (rrs_state_get_from_board (board) == solution_state) {
 451                         found_move = 1;
 452                         robot_found = robot;
 453                         dir_found = dir;
 454                         state_found = buf->state[j];
 455                         if (robot_found == last_robot_found)
 456                             goto NEXT_MOVE;
 457                         else
 458                             last_robot_found = robot_found;
 459                     }
 460                 }
 461             }
 462         }
 463       NEXT_MOVE:
 464         if (found_move) {
 465             rrs_solution_prepend (solution, robot_found, dir_found);
 466             solution_state = state_found;
 467         } else {
 468             fprintf (stderr, "ERROR: Failed to trace solution backwards to 0x%x at move %d\n",
 469                      solution_state, i+1);
 470             break;
 471         }
 472     }
 473 }
 474
 475 static rr_status_t
 476 find_solution_states (rr_board_t *board,
 477                       rrs_state_buf_t ***solution_states,
 478                       int *num_state_buf,
 479                       rrs_state_t *final_state)
 480 {
 481     int solved, moves;
 482     rrs_state_t initial;
 483     rrs_state_buf_t **states, **new_states;
 484
 485     states = malloc (sizeof (rrs_state_buf_t *));
 486     if (states == NULL)
 487         return RR_STATUS_NO_MEMORY;
 488
 489     initial = rrs_state_get_from_board (board);
 490
 491     states[0] = rrs_state_buf_create (1);
 492     if (states[0] == NULL)
 493         return RR_STATUS_NO_MEMORY;
 494     rrs_state_buf_add (states[0], initial);
 495
 496     moves = 0;
 497     while (1) {
 498         moves++;
 499
 500         new_states = realloc (states, (moves + 1) * sizeof (rrs_state_buf_t *));
 501         if (new_states == NULL)
 502             return RR_STATUS_NO_MEMORY;
 503
 504         states = new_states;
 505         states[moves] = rrs_state_buf_create (RRS_BRANCHING_FACTOR_ESTIMATE
 506                                               * states[moves-1]->num_states);
 507         if (states[moves] == NULL)
 508             return RR_STATUS_NO_MEMORY;
 509
 510         solved = rrs_find_new_states (board, states, moves-1, states[moves], final_state);
 511
 512         if (solved)
 513             break;
 514
 515         if (states[moves]->num_states == 0) {
 516             printf ("Can't make any further progress after %d moves.\n", moves);
 517             moves = -1;
 518             break;
 519         } else {
 520             printf ("Move #%d generated %d new states.\n",
 521                     moves, states[moves]->num_states);
 522         }
 523     }
 524
 525     *num_state_buf = moves;
 526     *solution_states = states;
 527
 528     return RR_STATUS_SUCCESS;
 529 }
 530
 531 static int
 532 state_has_been_seen (rrs_state_buf_t **previous,
 533                      int moves,
 534                      rrs_state_t state)
 535 {
 536     int i;
 537
 538     for (i=0; i <= moves; i++)
 539         if (rrs_state_buf_contains (previous[i], state))
 540             return 1;
 541     return 0;
 542 }
 543
 544 static int
 545 rrs_find_new_states (rr_board_t *board,
 546                      rrs_state_buf_t **previous,
 547                      int moves,
 548                      rrs_state_buf_t *new,
 549                      rrs_state_t *solution_state)
 550 {
 551     int i, ri;
 552     rr_direction_t dir;
 553     rrs_state_t state, new_state;
 554     rrs_state_buf_t *initial;
 555     rr_status_t status;
 556     rr_robot_t robot;
 557
 558     initial = previous[moves];
 559
 560     for (i = 0; i < initial->num_states; i++) {
 561         state = initial->state[i];
 562
 563         rrs_state_set_board (state, board);
 564
 565         if (state == 0x611a4350)
 566             printf ("I'm within one move now\n");
 567         for (ri = 0; ri < RR_NUM_ROBOTS; ri++) {
 568             robot = rr_robot_from_idx (ri);
 569             for (dir = RR_DIRECTION_NORTH; dir <= RR_DIRECTION_EAST; dir++) {
 570                 status = rr_board_move (board, robot, dir);
 571                 if (status == RR_STATUS_SUCCESS) {
 572                     new_state = rrs_state_get_from_board (board);
 573                     if (! state_has_been_seen (previous, moves, new_state)) {
 574                         rrs_state_buf_add_sorted (new, new_state);
 575                         if (rr_board_solved (board)) {
 576                             *solution_state = new_state;
 577                             return 1;
 578                         }
 579                     }
 580                     rr_board_undo (board);
 581                 }
 582             }
 583         }
 584     }
 585
 586     return 0;
 587 }
 588