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 rrs_state_t
  47 rrs_state_get_from_board (rr_board_t *board);
  48
  49 static void
  50 rrs_solution_print (rrs_solution_t *solution);
  51
  52 static rr_status_t
  53 solve_board (rr_board_t *board, rrs_solution_t *solution);
  54
  55 static rr_status_t
  56 find_solution_states (rr_board_t *board,
  57                       rrs_state_buf_t ***solution_states,
  58                       int *num_state_buf,
  59                       rrs_state_t *final_state);
  60
  61 static int
  62 rrs_find_new_states (rr_board_t *board,
  63                      rrs_state_buf_t **previous,
  64                      int moves,
  65                      rrs_state_buf_t *new,
  66                      rrs_state_t *solution_state);
  67
  68 static void
  69 trace_solution (rr_board_t *board,
  70                 rrs_state_buf_t **states, int moves,
  71                 rrs_state_t solution_state,
  72                 rrs_solution_t *solution);
  73
  74 int
  75 main (int argc, char *argv[])
  76 {
  77     args_t args;
  78     rr_status_t status;
  79     rr_client_t *client;
  80     rr_board_t *board;
  81     rrs_solution_t solution;
  82     char *diagram;
  83
  84     args_parse (&args, argc, argv);
  85
  86     client = rr_client_create (args.host, args.port, args.user);
  87     if (client == NULL) {
  88         fprintf (stderr, "Failed connecting to %s:%s as %s\n",
  89                  args.host, args.port, args.user);
  90         return 1;
  91     }
  92
  93     status = rr_client_join (client, GAME);
  94     if (status == RR_STATUS_NO_GAME)
  95         status = rr_client_new (client, GAME);
  96     if (status) {
  97         fprintf (stderr, "Error joining or creating game: %s\n", rr_status_str (status));
  98         return 1;
  99     }
 100
 101     status = rr_client_show (client, &diagram);
 102     if (status) {
 103         fprintf (stderr, "Error in rr_client_new: %s\n", rr_status_str (status));
 104         return 1;
 105     }
 106     board = rr_board_create_from_str (diagram);
 107
 108     puts (rr_board_to_str (board));
 109
 110     rrs_solution_init (&solution);
 111     solve_board (board, &solution);
 112     printf ("Solution (%d moves):", solution.num_moves);
 113     rrs_solution_print (&solution);
 114     rrs_solution_fini (&solution);
 115
 116     free (diagram);
 117
 118     rr_board_destroy (board);
 119
 120     rr_client_destroy (client);
 121
 122     return 0;
 123 }
 124
 125 static void
 126 rrs_solution_print (rrs_solution_t *solution)
 127 {
 128     int i;
 129     rr_robot_t last_robot;
 130     rrs_move_t *move;
 131
 132     last_robot = RR_ROBOT_NONE;
 133     for (i=0; i < solution->num_moves; i++) {
 134         move = &solution->move[i];
 135         if (move->robot == last_robot)
 136             printf (", %s", rr_direction_str (move->dir));
 137         else
 138             printf ("\n Move #%d: %s %s",
 139                     i, rr_robot_str (move->robot), rr_direction_str (move->dir));
 140         last_robot = move->robot;
 141     }
 142     printf ("\n");
 143 }
 144
 145 static rrs_state_t
 146 rrs_state_get_from_board (rr_board_t *board)
 147 {
 148     int i;
 149     int x, y;
 150     rrs_state_t state;
 151
 152     state = 0;
 153
 154     for (i=0; i < RR_NUM_ROBOTS; i++) {
 155         rr_board_find_robot (board, rr_robot_from_idx (i), &x, &y);
 156         RRS_STATE_SET_ROBOT (state, i, x, y);
 157     }
 158
 159     return state;
 160 }
 161
 162 static void
 163 rrs_state_set_board (rrs_state_t state, rr_board_t *board)
 164 {
 165     int i;
 166     int x, y;
 167
 168     for (i=0; i < RR_NUM_ROBOTS; i++) {
 169         RRS_STATE_GET_ROBOT (state, i, x, y);
 170         rr_board_position_robot (board, rr_robot_from_idx (i), x, y);
 171     }
 172
 173 }
 174
 175 static rr_status_t
 176 solve_board (rr_board_t *board, rrs_solution_t *solution)
 177 {
 178     rr_status_t status;
 179     int i, moves;
 180     rrs_state_t solution_state;
 181     rrs_state_buf_t **states;
 182     struct timeval tv_start, tv_end;
 183
 184     if (rr_board_solved (board)) {
 185         printf ("Board is solved to begin with.\n");
 186         return RR_STATUS_SUCCESS;
 187     }
 188
 189     gettimeofday (&tv_start, NULL);
 190
 191     status = find_solution_states (board, &states, &moves, &solution_state);
 192     if (status)
 193         return status;
 194
 195     gettimeofday (&tv_end, NULL);
 196
 197     if (moves < 0) {
 198         printf ("It seems impossible.\n");
 199     } else {
 200         printf ("Found solution of %d moves in %g seconds.\n",
 201                 moves,
 202                 tv_end.tv_sec - tv_start.tv_sec
 203                 + (tv_end.tv_usec - tv_start.tv_usec) / 1e6);
 204
 205         gettimeofday (&tv_start, NULL);
 206
 207         trace_solution (board, states, moves, solution_state, solution);
 208
 209         gettimeofday (&tv_end, NULL);
 210
 211         printf ("Traced solution in %g seconds.\n",
 212                 tv_end.tv_sec - tv_start.tv_sec
 213                 + (tv_end.tv_usec - tv_start.tv_usec) / 1e6);
 214     }
 215
 216     for (i=0; i <= moves; i++) {
 217         rrs_state_buf_destroy (states[i]);
 218         states[i] = NULL;
 219     }
 220
 221     free (states);
 222
 223     return RR_STATUS_SUCCESS;
 224 }
 225
 226 static int
 227 rrs_state_connected (rrs_state_t a, rrs_state_t b,
 228                      rr_robot_t *robot, rr_direction_t *dir)
 229 {
 230     int i;
 231     int nib;
 232     rrs_state_t diff, mask;
 233     int shift, delta;
 234
 235     diff = a ^ b;
 236
 237     nib = -1;
 238     for (i=0; i < 8; i++) {
 239         if (diff & 0xf) {
 240             if (nib > 0)
 241                 return 0;
 242             else
 243                 nib = i;
 244         }
 245         diff >>= 4;
 246     }
 247
 248     switch (nib) {
 249     case 0:
 250     case 1:
 251         *robot = RR_ROBOT_BLUE;
 252         break;
 253     case 2:
 254     case 3:
 255         *robot = RR_ROBOT_GREEN;
 256         break;
 257     case 4:
 258     case 5:
 259         *robot = RR_ROBOT_RED;
 260         break;
 261     case 6:
 262     case 7:
 263         *robot = RR_ROBOT_YELLOW;
 264         break;
 265     }
 266
 267     shift = 4 * nib;
 268     mask = 0xf << shift;
 269     delta = ((b & mask) >> shift) - ((a & mask) >> shift);
 270
 271     if (nib % 2)
 272         if (delta < 0)
 273             *dir = RR_DIRECTION_WEST;
 274         else
 275             *dir = RR_DIRECTION_EAST;
 276     else
 277         if (delta < 0)
 278             *dir = RR_DIRECTION_NORTH;
 279         else
 280             *dir = RR_DIRECTION_SOUTH;
 281
 282     return 1;
 283 }
 284
 285 static void
 286 trace_solution (rr_board_t *board,
 287                 rrs_state_buf_t **states, int moves,
 288                 rrs_state_t solution_state,
 289                 rrs_solution_t *solution)
 290 {
 291     rr_status_t status;
 292     int i, j;
 293     rrs_state_buf_t *buf;
 294     rr_robot_t robot;
 295     rr_direction_t dir;
 296
 297     for (i = moves-1; i >= 0; i--) {
 298         buf = states[i];
 299         for (j = 0; j < buf->num_states; j++) {
 300             if (rrs_state_connected (buf->state[j], solution_state,
 301                                      &robot, &dir)) {
 302                 rrs_state_set_board (buf->state[j], board);
 303                 status = rr_board_move (board, robot, dir);
 304                 if (status == RR_STATUS_SUCCESS) {
 305                     if (rrs_state_get_from_board (board) == solution_state) {
 306                         rrs_solution_prepend (solution, robot, dir);
 307                         solution_state = buf->state[j];
 308                         goto NEXT_MOVE;
 309                     }
 310                 }
 311             }
 312         }
 313         fprintf (stderr, "ERROR: Failed to trace solution backwards to 0x%x at move %d\n",
 314                  solution_state, i+1);
 315         break;
 316       NEXT_MOVE:
 317         ;
 318     }
 319 }
 320
 321 static rr_status_t
 322 find_solution_states (rr_board_t *board,
 323                       rrs_state_buf_t ***solution_states,
 324                       int *num_state_buf,
 325                       rrs_state_t *final_state)
 326 {
 327     int solved, moves;
 328     rrs_state_t initial;
 329     rrs_state_buf_t **states, **new_states;
 330
 331     states = malloc (sizeof (rrs_state_buf_t *));
 332     if (states == NULL)
 333         return RR_STATUS_NO_MEMORY;
 334
 335     initial = rrs_state_get_from_board (board);
 336
 337     states[0] = rrs_state_buf_create (1);
 338     if (states[0] == NULL)
 339         return RR_STATUS_NO_MEMORY;
 340     rrs_state_buf_add (states[0], initial);
 341
 342     moves = 0;
 343     while (1) {
 344         moves++;
 345
 346         new_states = realloc (states, (moves + 1) * sizeof (rrs_state_buf_t *));
 347         if (new_states == NULL)
 348             return RR_STATUS_NO_MEMORY;
 349
 350         states = new_states;
 351         states[moves] = rrs_state_buf_create (RRS_BRANCHING_FACTOR_ESTIMATE
 352                                               * states[moves-1]->num_states);
 353         if (states[moves] == NULL)
 354             return RR_STATUS_NO_MEMORY;
 355
 356         solved = rrs_find_new_states (board, states, moves-1, states[moves], final_state);
 357
 358         if (solved)
 359             break;
 360
 361         if (states[moves]->num_states == 0) {
 362             printf ("Can't make any further progress after %d moves.\n", moves);
 363             moves = -1;
 364             break;
 365         } else {
 366             printf ("Move #%d generated %d new states.\n",
 367                     moves, states[moves]->num_states);
 368         }
 369     }
 370
 371     *num_state_buf = moves;
 372     *solution_states = states;
 373
 374     return RR_STATUS_SUCCESS;
 375 }
 376
 377 static int
 378 state_has_been_seen (rrs_state_buf_t **previous,
 379                      int moves,
 380                      rrs_state_t state)
 381 {
 382     int i;
 383
 384     for (i=0; i <= moves; i++)
 385         if (rrs_state_buf_contains (previous[i], state))
 386             return 1;
 387     return 0;
 388 }
 389
 390 static int
 391 rrs_find_new_states (rr_board_t *board,
 392                      rrs_state_buf_t **previous,
 393                      int moves,
 394                      rrs_state_buf_t *new,
 395                      rrs_state_t *solution_state)
 396 {
 397     int i, ri;
 398     rr_direction_t dir;
 399     rrs_state_t state, new_state;
 400     rrs_state_buf_t *initial;
 401     rr_status_t status;
 402     rr_robot_t robot;
 403
 404     initial = previous[moves];
 405
 406     for (i = 0; i < initial->num_states; i++) {
 407         state = initial->state[i];
 408
 409         rrs_state_set_board (state, board);
 410         for (ri = 0; ri < RR_NUM_ROBOTS; ri++) {
 411             robot = rr_robot_from_idx (ri);
 412             for (dir = RR_DIRECTION_NORTH; dir <= RR_DIRECTION_EAST; dir++) {
 413                 status = rr_board_move (board, robot, dir);
 414                 if (status == RR_STATUS_SUCCESS) {
 415                     new_state = rrs_state_get_from_board (board);
 416                     if (! state_has_been_seen (previous, moves, new_state)) {
 417                         rrs_state_buf_add_sorted (new, new_state);
 418                         if (rr_board_solved (board)) {
 419                             *solution_state = new_state;
 420                             return 1;
 421                         }
 422                     }
 423                     rr_board_undo (board);
 424                 }
 425             }
 426         }
 427     }
 428
 429     return 0;
 430 }
 431