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