--- /dev/null
+aclocal.m4
+config.cache
+config.guess
+config.h
+config.h.in
+config.log
+config.status
+config.sub
+configure
+install-sh
+Makefile
+Makefile.in
+missing
+mkinstalldirs
+stamp-h
+stamp-h.in
+
+
+
+
--- /dev/null
+Carl Worth <carl@theworths.org>
+
--- /dev/null
+rrsolve is Copyright © 2003 Carl Worth
+
+Permission to use, copy, modify, distribute, and sell this software
+and its documentation for any purpose is hereby granted without fee,
+provided that the above copyright notice appear in all copies and that
+both that copyright notice and this permission notice appear in
+supporting documentation, and that the name of Carl Worth not be used
+in advertising or publicity pertaining to distribution of the software
+without specific, written prior permission. Carl Worth %makes no
+representations about the suitability of this software for any
+purpose. It is provided "as is" without express or implied warranty.
+
+CARL WORTH DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE,
+INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS, IN NO
+EVENT SHALL CARL WORTH BE LIABLE FOR ANY SPECIAL, INDIRECT OR
+CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF
+USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR
+OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR
+PERFORMANCE OF THIS SOFTWARE.
+
--- /dev/null
+This package uses automake, in order to generate the Makefiles use:
+
+ $ autogen.sh
+
+See the README for information on obtaining any missing libraries.
+
+After that, standard build procedures apply:
+
+ $ make
+ # make install
+
--- /dev/null
+SUBDIRS = . src
+
+
--- /dev/null
+rrsolve - Ricochet Robot solver
--- /dev/null
+#!/bin/sh
+# Run this to generate all the initial makefiles, etc.
+
+set -e
+
+if test -z "$*"; then
+ echo "$0: Note: \`./configure' will be run with no arguments."
+ echo " If you wish to pass any to it, please specify them on the"
+ echo " \`$0' command line."
+ echo
+fi
+
+do_cmd() {
+ echo "$0: running \`$@'"
+ $@
+}
+
+do_cmd libtoolize --force --copy
+
+do_cmd aclocal
+
+do_cmd autoheader
+
+do_cmd automake --add-missing
+
+do_cmd autoconf
+
+do_cmd ./configure ${1+"$@"} && echo "Now type \`make' to compile" || exit 1
--- /dev/null
+AC_INIT(src/rrsolve.c)
+
+dnl ===========================================================================
+
+rrsolve_VERSION=0.1.0
+AC_SUBST(rrsolve_VERSION)
+
+dnl ===========================================================================
+
+AM_INIT_AUTOMAKE(xsvg, $rrsolve_VERSION)
+AM_CONFIG_HEADER(config.h)
+
+AM_MAINTAINER_MODE
+
+AC_ISC_POSIX
+AC_PROG_CC
+AC_STDC_HEADERS
+
+dnl ===========================================================================
+
+PKG_CHECK_MODULES(rrsolve, librr)
+AC_SUBST(rrsolve_CFLAGS)
+AC_SUBST(rrsolve_LIBS)
+
+dnl ===========================================================================
+
+AC_OUTPUT([
+Makefile
+src/Makefile
+])
--- /dev/null
+.deps
+Makefile
+Makefile.in
+rrsolve
+
+
--- /dev/null
+bin_PROGRAMS = rrsolve
+
+rrsolve_SOURCES = \
+ args.c \
+ args.h \
+ rrsolve.c \
+ rrs_state_buf.c \
+ rrs_solution.c
+
+INCLUDES = $(rrsolve_CFLAGS)
+LDFLAGS = $(rrsolve_LIBS)
--- /dev/null
+/* args.c - Parse command-line arguments for grrobot using argp
+ *
+ * Copyright © 2003 Carl Worth
+ *
+ * Permission to use, copy, modify, distribute, and sell this software
+ * and its documentation for any purpose is hereby granted without
+ * fee, provided that the above copyright notice appear in all copies
+ * and that both that copyright notice and this permission notice
+ * appear in supporting documentation, and that the name of Carl Worth
+ * not be used in advertising or publicity pertaining to distribution
+ * of the software without specific, written prior permission.
+ * Carl Worth makes no representations about the suitability of this
+ * software for any purpose. It is provided "as is" without express
+ * or implied warranty.
+ *
+ * CARL WORTH DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE,
+ * INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS, IN
+ * NO EVENT SHALL CARL WORTH BE LIABLE FOR ANY SPECIAL, INDIRECT OR
+ * CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS
+ * OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT,
+ * NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN
+ * CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
+ *
+ * Author: Carl Worth <carl@theworths.org>
+ */
+
+#include <stdlib.h>
+#include <argp.h>
+
+#include "args.h"
+
+const char *argp_program_version = "grrobot " VERSION;
+
+const char *argp_program_bug_address = "<carl@theworths.org>";
+
+static char doc[] = "rrsolve - Ricochet Robot solver";
+
+static char args_doc[] = "";
+
+static struct argp_option options[] = {
+ /* name, key, arg, flags, doc */
+ {"host", 'h', "HOST", 0, "Host running RR server"},
+ {"port", 'p', "PORT", 0, "Port of server"},
+ {"user", 'u', "USERNAME", 0, "Username for conection"},
+ {"game", 'g', "GAME", 0, "Game to join"},
+ { 0 }
+};
+
+static error_t
+parse_opt (int key, char *arg, struct argp_state *state)
+{
+ struct args *args = state->input;
+
+ switch (key) {
+ case 'h':
+ args->host = arg;
+ break;
+ case 'p':
+ args->port = arg;
+ break;
+ case 'u':
+ args->user = arg;
+ break;
+ case 'g':
+ args->game = arg;
+ break;
+
+ case ARGP_KEY_ARG:
+ argp_usage (state);
+ break;
+
+/*
+ case ARGP_KEY_END:
+ if (state->arg_num < 1)
+ argp_usage (state);
+ break;
+*/
+
+ default:
+ return ARGP_ERR_UNKNOWN;
+ }
+
+ return 0;
+}
+
+static struct argp argp = { options, parse_opt, args_doc, doc };
+
+error_t
+args_parse(args_t *args, int argc, char *argv[])
+{
+ args->host = getenv ("RR_HOST");
+ if (args->host == NULL)
+ args->host = ARGS_HOST_DEFAULT;
+ args->port = getenv ("RR_PORT");
+ if (args->port == NULL)
+ args->port = ARGS_PORT_DEFAULT;
+ args->user = ARGS_USER_DEFAULT;
+ args->game = getenv ("RR_GAME");
+ if (args->game == NULL)
+ args->game = ARGS_GAME_DEFAULT;
+
+ return argp_parse (&argp, argc, argv, 0, 0, args);
+}
--- /dev/null
+/* args.h - Parse command-line arguments for grrobot using argp
+ *
+ * Copyright © 2003 Carl Worth
+ *
+ * Permission to use, copy, modify, distribute, and sell this software
+ * and its documentation for any purpose is hereby granted without
+ * fee, provided that the above copyright notice appear in all copies
+ * and that both that copyright notice and this permission notice
+ * appear in supporting documentation, and that the name of Carl Worth
+ * not be used in advertising or publicity pertaining to distribution
+ * of the software without specific, written prior permission.
+ * Carl Worth makes no representations about the suitability of this
+ * software for any purpose. It is provided "as is" without express
+ * or implied warranty.
+ *
+ * CARL WORTH DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE,
+ * INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS, IN
+ * NO EVENT SHALL CARL WORTH BE LIABLE FOR ANY SPECIAL, INDIRECT OR
+ * CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS
+ * OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT,
+ * NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN
+ * CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
+ *
+ * Author: Carl Worth <carl@theworths.org>
+ */
+
+#ifndef ARGS_H
+#define ARGS_H
+
+#ifdef HAVE_CONFIG_H
+#include "config.h"
+#endif
+
+#include <argp.h>
+
+#define ARGS_HOST_DEFAULT "rr.nickle.org"
+#define ARGS_PORT_DEFAULT "5252"
+#define ARGS_USER_DEFAULT "rrsolve"
+#define ARGS_GAME_DEFAULT "game"
+
+typedef struct args
+{
+ char *host;
+ char *port;
+ char *user;
+ char *game;
+} args_t;
+
+error_t
+args_parse(args_t *args, int argc, char *argv[]);
+
+#endif
--- /dev/null
+/* rrsolve - Simple RR solver and librr client.
+ *
+ * Copyright © 2003 Carl Worth
+ *
+ * Permission to use, copy, modify, distribute, and sell this software
+ * and its documentation for any purpose is hereby granted without
+ * fee, provided that the above copyright notice appear in all copies
+ * and that both that copyright notice and this permission notice
+ * appear in supporting documentation, and that the name of Carl Worth
+ * not be used in advertising or publicity pertaining to distribution
+ * of the software without specific, written prior permission.
+ * Carl Worth makes no representations about the suitability of this
+ * software for any purpose. It is provided "as is" without express
+ * or implied warranty.
+ *
+ * CARL WORTH DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE,
+ * INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS, IN
+ * NO EVENT SHALL CARL WORTH BE LIABLE FOR ANY SPECIAL, INDIRECT OR
+ * CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS
+ * OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT,
+ * NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN
+ * CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
+ *
+ * Author: Carl Worth <carl@theworths.org>
+ */
+
+#include <stdlib.h>
+#include <string.h>
+
+#include "rrsolve.h"
+
+rr_status_t
+rrs_solution_init (rrs_solution_t *solution)
+{
+ solution->move = NULL;
+ solution->size = 0;
+ solution->num_moves = 0;
+
+ return RR_STATUS_SUCCESS;
+}
+
+void
+rrs_solution_fini (rrs_solution_t *solution)
+{
+ free (solution->move);
+ solution->move = NULL;
+ solution->size = 0;
+ solution->num_moves = 0;
+}
+
+#define RRS_SOLUTION_GROWTH 5
+static rr_status_t
+_rrs_solution_grow (rrs_solution_t *solution)
+{
+ rrs_move_t *new_move;
+
+ if (solution->num_moves >= solution->size) {
+ solution->size += RRS_SOLUTION_GROWTH;
+ new_move = realloc (solution->move, solution->size * sizeof (rrs_move_t));
+ if (new_move == NULL) {
+ solution->size -= RRS_SOLUTION_GROWTH;
+ return RR_STATUS_NO_MEMORY;
+ }
+ solution->move = new_move;
+ }
+
+ return RR_STATUS_SUCCESS;
+}
+
+rr_status_t
+rrs_solution_push (rrs_solution_t *solution,
+ rr_robot_t robot, rr_direction_t dir)
+{
+ rrs_move_t *move;
+
+ _rrs_solution_grow (solution);
+
+ move = &solution->move[solution->num_moves++];
+ move->robot = robot;
+ move->dir = dir;
+
+ return RR_STATUS_SUCCESS;
+}
+
+rr_status_t
+rrs_solution_pop (rrs_solution_t *solution,
+ rr_robot_t *robot, rr_direction_t *dir)
+{
+ rrs_move_t *move;
+
+ if (solution->num_moves < 1)
+ return RR_STATUS_HISTORY_EMPTY;
+
+ move = &solution->move[--solution->num_moves];
+
+ if (robot)
+ *robot = move->robot;
+ if (dir)
+ *dir = move->dir;
+
+ return RR_STATUS_SUCCESS;
+}
+
+rr_status_t
+rrs_solution_prepend (rrs_solution_t *solution,
+ rr_robot_t robot, rr_direction_t dir)
+{
+ rrs_move_t *move;
+
+ _rrs_solution_grow (solution);
+
+ memmove (&solution->move[1], &solution->move[0],
+ solution->num_moves * sizeof (rrs_move_t));
+ move = &solution->move[0];
+ move->robot = robot;
+ move->dir = dir;
+ solution->num_moves++;
+
+ return RR_STATUS_SUCCESS;
+}
--- /dev/null
+/* rrsolve - Simple RR solver and librr client.
+ *
+ * Copyright © 2003 Carl Worth
+ *
+ * Permission to use, copy, modify, distribute, and sell this software
+ * and its documentation for any purpose is hereby granted without
+ * fee, provided that the above copyright notice appear in all copies
+ * and that both that copyright notice and this permission notice
+ * appear in supporting documentation, and that the name of Carl Worth
+ * not be used in advertising or publicity pertaining to distribution
+ * of the software without specific, written prior permission.
+ * Carl Worth makes no representations about the suitability of this
+ * software for any purpose. It is provided "as is" without express
+ * or implied warranty.
+ *
+ * CARL WORTH DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE,
+ * INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS, IN
+ * NO EVENT SHALL CARL WORTH BE LIABLE FOR ANY SPECIAL, INDIRECT OR
+ * CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS
+ * OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT,
+ * NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN
+ * CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
+ *
+ * Author: Carl Worth <carl@theworths.org>
+ */
+
+#include <stdlib.h>
+#include <string.h>
+
+#include "rrsolve.h"
+
+static int
+_rrs_state_buf_search (rrs_state_buf_t *buf, rrs_state_t state);
+
+static void
+_rrs_state_buf_sort (rrs_state_buf_t *buf);
+
+static rr_status_t
+_rrs_state_buf_grow_by (rrs_state_buf_t *buf, int growth);
+
+static rr_status_t
+_rrs_state_buf_grow_to (rrs_state_buf_t *buf, int new_size);
+
+rrs_state_buf_t *
+rrs_state_buf_create (int initial_size)
+{
+ rrs_state_buf_t *buf;
+
+ buf = malloc (sizeof (rrs_state_buf_t));
+ if (buf == NULL)
+ return NULL;
+
+ buf->state = NULL;
+ buf->num_states = 0;
+ buf->size = 0;
+
+ buf->sorted = 0;
+
+ _rrs_state_buf_grow_by (buf, initial_size);
+
+ return buf;
+}
+
+void
+rrs_state_buf_destroy (rrs_state_buf_t *buf)
+{
+ free (buf->state);
+
+ free (buf);
+}
+
+static rr_status_t
+_rrs_state_buf_grow_by (rrs_state_buf_t *buf, int growth)
+{
+ rrs_state_t *new_state;
+
+ buf->size += growth;
+
+ new_state = realloc (buf->state, buf->size * sizeof (rrs_state_t));
+ if (new_state == NULL) {
+ buf->size -= growth;
+ return RR_STATUS_NO_MEMORY;
+ }
+
+ buf->state = new_state;
+
+ return RR_STATUS_SUCCESS;
+}
+
+static rr_status_t
+_rrs_state_buf_grow_to (rrs_state_buf_t *buf, int new_size)
+{
+ if (new_size > buf->size)
+ return _rrs_state_buf_grow_by (buf, new_size - buf->size);
+
+ return RR_STATUS_SUCCESS;
+}
+
+#define RRS_STATE_BUF_MIN_GROWTH 10
+
+#define MAX(a,b) ((a) > (b) ? (a) : (b))
+
+rr_status_t
+rrs_state_buf_add (rrs_state_buf_t *buf, rrs_state_t state)
+{
+ rr_status_t status;
+
+ if (buf->num_states >= buf->size) {
+ status = _rrs_state_buf_grow_by (buf, MAX (RRS_STATE_BUF_MIN_GROWTH, buf->size));
+ if (status)
+ return status;
+ }
+
+ buf->state[buf->num_states++] = state;
+
+ buf->sorted = 0;
+
+ return RR_STATUS_SUCCESS;
+}
+
+rr_status_t
+rrs_state_buf_add_sorted (rrs_state_buf_t *buf, rrs_state_t state)
+{
+ int i;
+ rr_status_t status;
+
+ i = _rrs_state_buf_search (buf, state);
+
+ if (i < buf->num_states && buf->state[i] == state)
+ return RR_STATUS_OCCUPIED;
+
+ if (buf->num_states >= buf->size) {
+ status = _rrs_state_buf_grow_by (buf, MAX (RRS_STATE_BUF_MIN_GROWTH, buf->size));
+ if (status)
+ return status;
+ }
+
+ memmove (&buf->state[i+1], &buf->state[i],
+ (buf->num_states - i) * sizeof (rrs_state_t));
+ buf->state[i] = state;
+ buf->num_states++;
+
+ return RR_STATUS_SUCCESS;
+}
+
+rr_status_t
+rrs_state_buf_remove (rrs_state_buf_t *buf, rrs_state_t state)
+{
+ int i;
+
+ i = _rrs_state_buf_search (buf, state);
+
+ if (buf->state[i] != state)
+ return RR_STATUS_OCCUPIED;
+
+ buf->num_states--;
+ memmove (&buf->state[i], &buf->state[i+1],
+ (buf->num_states - i) * sizeof (rrs_state_t));
+
+ return RR_STATUS_SUCCESS;
+}
+
+rr_status_t
+rrs_state_buf_append (rrs_state_buf_t *buf, rrs_state_buf_t *other)
+{
+ rr_status_t status;
+ int new_size;
+
+ if (other == NULL)
+ return RR_STATUS_SUCCESS;
+
+ new_size = buf->num_states + other->num_states;
+ status = _rrs_state_buf_grow_to (buf, new_size);
+ if (status)
+ return status;
+
+ memcpy (&buf->state[buf->num_states], other->state, other->num_states * sizeof (rrs_state_t));
+ buf->num_states += other->num_states;
+
+ buf->sorted = 0;
+
+ return RR_STATUS_SUCCESS;
+}
+
+static int
+_rrs_state_compare (const void *a, const void *b)
+{
+ rrs_state_t a_state = *((rrs_state_t *) a);
+ rrs_state_t b_state = *((rrs_state_t *) b);
+
+ if (a_state > b_state)
+ return 1;
+ else if (a_state < b_state)
+ return -1;
+ else
+ return 0;
+}
+
+static int
+_rrs_state_buf_search (rrs_state_buf_t *buf, rrs_state_t state)
+{
+ int min, mid, max;
+
+ if (buf->sorted == 0)
+ _rrs_state_buf_sort (buf);
+
+ if (buf->num_states == 0)
+ return 0;
+
+ min = 0;
+ max = buf->num_states - 1;
+
+ do {
+ mid = min + (max - min) / 2;
+
+ if (state == buf->state[mid])
+ return mid;
+ else if (state > buf->state[mid])
+ min = mid + 1;
+ else
+ max = mid;
+ } while (min < max);
+
+ if (state > buf->state[max])
+ return max + 1;
+ else
+ return min;
+}
+
+static void
+_rrs_state_buf_sort (rrs_state_buf_t *buf)
+{
+ qsort (buf->state, buf->num_states, sizeof (rrs_state_t), _rrs_state_compare);
+ buf->sorted = 1;
+}
+
+int
+rrs_state_buf_contains (rrs_state_buf_t *buf, rrs_state_t state)
+{
+ int i;
+
+ i = _rrs_state_buf_search (buf, state);
+
+ if (i > buf->num_states - 1)
+ return 0;
+ else
+ return buf->state[i] == state;
+}
--- /dev/null
+/* rrsolve - Simple RR solver and librr client.
+ *
+ * Copyright © 2003 Carl Worth
+ *
+ * Permission to use, copy, modify, distribute, and sell this software
+ * and its documentation for any purpose is hereby granted without
+ * fee, provided that the above copyright notice appear in all copies
+ * and that both that copyright notice and this permission notice
+ * appear in supporting documentation, and that the name of Carl Worth
+ * not be used in advertising or publicity pertaining to distribution
+ * of the software without specific, written prior permission.
+ * Carl Worth makes no representations about the suitability of this
+ * software for any purpose. It is provided "as is" without express
+ * or implied warranty.
+ *
+ * CARL WORTH DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE,
+ * INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS, IN
+ * NO EVENT SHALL CARL WORTH BE LIABLE FOR ANY SPECIAL, INDIRECT OR
+ * CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS
+ * OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT,
+ * NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN
+ * CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
+ *
+ * Author: Carl Worth <carl@theworths.org>
+ */
+
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+#include <sys/time.h>
+#include <time.h>
+
+#include "rrsolve.h"
+
+#define HOST "localhost"
+#define PORT "5252"
+#define USER "rrsolve"
+#define GAME "game"
+
+/* Tuning this can reduce excess reallocs */
+#define RRS_BRANCHING_FACTOR_ESTIMATE 10
+
+#define RRS_STATE_SET_ROBOT(s, ri, x, y) ((s) |= (((y) << ((ri)<<3)) | ((x) << (((ri)<<3) + 4))))
+#define RRS_STATE_GET_ROBOT(s, ri, x, y) { (y) = ((s) >> ((ri)<<3)) & 0xf; (x) = ((s) >> (((ri)<<3) + 4)) & 0xf; }
+
+static rrs_state_t
+rrs_state_get_from_board (rr_board_t *board);
+
+static void
+rrs_solution_print (rrs_solution_t *solution);
+
+static rr_status_t
+solve_board (rr_board_t *board, rrs_solution_t *solution);
+
+static rr_status_t
+find_solution_states (rr_board_t *board,
+ rrs_state_buf_t ***solution_states,
+ int *num_state_buf,
+ rrs_state_t *final_state);
+
+static int
+rrs_find_new_states (rr_board_t *board,
+ rrs_state_buf_t **previous,
+ int moves,
+ rrs_state_buf_t *new,
+ rrs_state_t *solution_state);
+
+static void
+trace_solution (rr_board_t *board,
+ rrs_state_buf_t **states, int moves,
+ rrs_state_t solution_state,
+ rrs_solution_t *solution);
+
+int
+main (int argc, char *argv[])
+{
+ args_t args;
+ rr_status_t status;
+ rr_client_t *client;
+ rr_board_t *board;
+ rrs_solution_t solution;
+ char *diagram;
+
+ args_parse (&args, argc, argv);
+
+ client = rr_client_create (args.host, args.port, args.user);
+ if (client == NULL) {
+ fprintf (stderr, "Failed connecting to %s:%s as %s\n",
+ args.host, args.port, args.user);
+ return 1;
+ }
+
+ status = rr_client_join (client, GAME);
+ if (status == RR_STATUS_NO_GAME)
+ status = rr_client_new (client, GAME);
+ if (status) {
+ fprintf (stderr, "Error joining or creating game: %s\n", rr_status_str (status));
+ return 1;
+ }
+
+ status = rr_client_show (client, &diagram);
+ if (status) {
+ fprintf (stderr, "Error in rr_client_new: %s\n", rr_status_str (status));
+ return 1;
+ }
+ board = rr_board_create_from_str (diagram);
+
+ puts (rr_board_to_str (board));
+
+ rrs_solution_init (&solution);
+ solve_board (board, &solution);
+ printf ("Solution (%d moves):", solution.num_moves);
+ rrs_solution_print (&solution);
+ rrs_solution_fini (&solution);
+
+ free (diagram);
+
+ rr_board_destroy (board);
+
+ rr_client_destroy (client);
+
+ return 0;
+}
+
+static void
+rrs_solution_print (rrs_solution_t *solution)
+{
+ int i;
+ rr_robot_t last_robot;
+ rrs_move_t *move;
+
+ last_robot = RR_ROBOT_NONE;
+ for (i=0; i < solution->num_moves; i++) {
+ move = &solution->move[i];
+ if (move->robot == last_robot)
+ printf (", %s", rr_direction_str (move->dir));
+ else
+ printf ("\n Move #%d: %s %s",
+ i, rr_robot_str (move->robot), rr_direction_str (move->dir));
+ last_robot = move->robot;
+ }
+ printf ("\n");
+}
+
+static rrs_state_t
+rrs_state_get_from_board (rr_board_t *board)
+{
+ int i;
+ int x, y;
+ rrs_state_t state;
+
+ state = 0;
+
+ for (i=0; i < RR_NUM_ROBOTS; i++) {
+ rr_board_find_robot (board, rr_robot_from_idx (i), &x, &y);
+ RRS_STATE_SET_ROBOT (state, i, x, y);
+ }
+
+ return state;
+}
+
+static void
+rrs_state_set_board (rrs_state_t state, rr_board_t *board)
+{
+ int i;
+ int x, y;
+
+ for (i=0; i < RR_NUM_ROBOTS; i++) {
+ RRS_STATE_GET_ROBOT (state, i, x, y);
+ rr_board_position_robot (board, rr_robot_from_idx (i), x, y);
+ }
+
+}
+
+static rr_status_t
+solve_board (rr_board_t *board, rrs_solution_t *solution)
+{
+ rr_status_t status;
+ int i, moves;
+ rrs_state_t solution_state;
+ rrs_state_buf_t **states;
+ struct timeval tv_start, tv_end;
+
+ if (rr_board_solved (board)) {
+ printf ("Board is solved to begin with.\n");
+ return RR_STATUS_SUCCESS;
+ }
+
+ gettimeofday (&tv_start, NULL);
+
+ status = find_solution_states (board, &states, &moves, &solution_state);
+ if (status)
+ return status;
+
+ gettimeofday (&tv_end, NULL);
+
+ if (moves < 0) {
+ printf ("It seems impossible.\n");
+ } else {
+ printf ("Found solution of %d moves in %g seconds.\n",
+ moves,
+ tv_end.tv_sec - tv_start.tv_sec
+ + (tv_end.tv_usec - tv_start.tv_usec) / 1e6);
+
+ gettimeofday (&tv_start, NULL);
+
+ trace_solution (board, states, moves, solution_state, solution);
+
+ gettimeofday (&tv_end, NULL);
+
+ printf ("Traced solution in %g seconds.\n",
+ tv_end.tv_sec - tv_start.tv_sec
+ + (tv_end.tv_usec - tv_start.tv_usec) / 1e6);
+ }
+
+ for (i=0; i <= moves; i++) {
+ rrs_state_buf_destroy (states[i]);
+ states[i] = NULL;
+ }
+
+ free (states);
+
+ return RR_STATUS_SUCCESS;
+}
+
+static int
+rrs_state_connected (rrs_state_t a, rrs_state_t b,
+ rr_robot_t *robot, rr_direction_t *dir)
+{
+ int i;
+ int nib;
+ rrs_state_t diff, mask;
+ int shift, delta;
+
+ diff = a ^ b;
+
+ nib = -1;
+ for (i=0; i < 8; i++) {
+ if (diff & 0xf) {
+ if (nib > 0)
+ return 0;
+ else
+ nib = i;
+ }
+ diff >>= 4;
+ }
+
+ switch (nib) {
+ case 0:
+ case 1:
+ *robot = RR_ROBOT_BLUE;
+ break;
+ case 2:
+ case 3:
+ *robot = RR_ROBOT_GREEN;
+ break;
+ case 4:
+ case 5:
+ *robot = RR_ROBOT_RED;
+ break;
+ case 6:
+ case 7:
+ *robot = RR_ROBOT_YELLOW;
+ break;
+ }
+
+ shift = 4 * nib;
+ mask = 0xf << shift;
+ delta = ((b & mask) >> shift) - ((a & mask) >> shift);
+
+ if (nib % 2)
+ if (delta < 0)
+ *dir = RR_DIRECTION_WEST;
+ else
+ *dir = RR_DIRECTION_EAST;
+ else
+ if (delta < 0)
+ *dir = RR_DIRECTION_NORTH;
+ else
+ *dir = RR_DIRECTION_SOUTH;
+
+ return 1;
+}
+
+static void
+trace_solution (rr_board_t *board,
+ rrs_state_buf_t **states, int moves,
+ rrs_state_t solution_state,
+ rrs_solution_t *solution)
+{
+ rr_status_t status;
+ int i, j;
+ rrs_state_buf_t *buf;
+ rr_robot_t robot;
+ rr_direction_t dir;
+
+ for (i = moves-1; i >= 0; i--) {
+ buf = states[i];
+ for (j = 0; j < buf->num_states; j++) {
+ if (rrs_state_connected (buf->state[j], solution_state,
+ &robot, &dir)) {
+ rrs_state_set_board (buf->state[j], board);
+ status = rr_board_move (board, robot, dir);
+ if (status == RR_STATUS_SUCCESS) {
+ if (rrs_state_get_from_board (board) == solution_state) {
+ rrs_solution_prepend (solution, robot, dir);
+ solution_state = buf->state[j];
+ goto NEXT_MOVE;
+ }
+ }
+ }
+ }
+ fprintf (stderr, "ERROR: Failed to trace solution backwards to 0x%x at move %d\n",
+ solution_state, i+1);
+ break;
+ NEXT_MOVE:
+ ;
+ }
+}
+
+static rr_status_t
+find_solution_states (rr_board_t *board,
+ rrs_state_buf_t ***solution_states,
+ int *num_state_buf,
+ rrs_state_t *final_state)
+{
+ int solved, moves;
+ rrs_state_t initial;
+ rrs_state_buf_t **states, **new_states;
+
+ states = malloc (sizeof (rrs_state_buf_t *));
+ if (states == NULL)
+ return RR_STATUS_NO_MEMORY;
+
+ initial = rrs_state_get_from_board (board);
+
+ states[0] = rrs_state_buf_create (1);
+ if (states[0] == NULL)
+ return RR_STATUS_NO_MEMORY;
+ rrs_state_buf_add (states[0], initial);
+
+ moves = 0;
+ while (1) {
+ moves++;
+
+ new_states = realloc (states, (moves + 1) * sizeof (rrs_state_buf_t *));
+ if (new_states == NULL)
+ return RR_STATUS_NO_MEMORY;
+
+ states = new_states;
+ states[moves] = rrs_state_buf_create (RRS_BRANCHING_FACTOR_ESTIMATE
+ * states[moves-1]->num_states);
+ if (states[moves] == NULL)
+ return RR_STATUS_NO_MEMORY;
+
+ solved = rrs_find_new_states (board, states, moves-1, states[moves], final_state);
+
+ if (solved)
+ break;
+
+ if (states[moves]->num_states == 0) {
+ printf ("Can't make any further progress after %d moves.\n", moves);
+ moves = -1;
+ break;
+ } else {
+ printf ("Move #%d generated %d new states.\n",
+ moves, states[moves]->num_states);
+ }
+ }
+
+ *num_state_buf = moves;
+ *solution_states = states;
+
+ return RR_STATUS_SUCCESS;
+}
+
+static int
+state_has_been_seen (rrs_state_buf_t **previous,
+ int moves,
+ rrs_state_t state)
+{
+ int i;
+
+ for (i=0; i <= moves; i++)
+ if (rrs_state_buf_contains (previous[i], state))
+ return 1;
+ return 0;
+}
+
+static int
+rrs_find_new_states (rr_board_t *board,
+ rrs_state_buf_t **previous,
+ int moves,
+ rrs_state_buf_t *new,
+ rrs_state_t *solution_state)
+{
+ int i, ri;
+ rr_direction_t dir;
+ rrs_state_t state, new_state;
+ rrs_state_buf_t *initial;
+ rr_status_t status;
+ rr_robot_t robot;
+
+ initial = previous[moves];
+
+ for (i = 0; i < initial->num_states; i++) {
+ state = initial->state[i];
+
+ rrs_state_set_board (state, board);
+ for (ri = 0; ri < RR_NUM_ROBOTS; ri++) {
+ robot = rr_robot_from_idx (ri);
+ for (dir = RR_DIRECTION_NORTH; dir <= RR_DIRECTION_EAST; dir++) {
+ status = rr_board_move (board, robot, dir);
+ if (status == RR_STATUS_SUCCESS) {
+ new_state = rrs_state_get_from_board (board);
+ if (! state_has_been_seen (previous, moves, new_state)) {
+ rrs_state_buf_add_sorted (new, new_state);
+ if (rr_board_solved (board)) {
+ *solution_state = new_state;
+ return 1;
+ }
+ }
+ rr_board_undo (board);
+ }
+ }
+ }
+ }
+
+ return 0;
+}
+
--- /dev/null
+/* rrsolve - Simple RR solver and librr client.
+ *
+ * Copyright © 2003 Carl Worth
+ *
+ * Permission to use, copy, modify, distribute, and sell this software
+ * and its documentation for any purpose is hereby granted without
+ * fee, provided that the above copyright notice appear in all copies
+ * and that both that copyright notice and this permission notice
+ * appear in supporting documentation, and that the name of Carl Worth
+ * not be used in advertising or publicity pertaining to distribution
+ * of the software without specific, written prior permission.
+ * Carl Worth makes no representations about the suitability of this
+ * software for any purpose. It is provided "as is" without express
+ * or implied warranty.
+ *
+ * CARL WORTH DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE,
+ * INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS, IN
+ * NO EVENT SHALL CARL WORTH BE LIABLE FOR ANY SPECIAL, INDIRECT OR
+ * CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS
+ * OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT,
+ * NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN
+ * CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
+ *
+ * Author: Carl Worth <carl@theworths.org>
+ */
+
+#ifndef RRSOLVE_H
+#define RRSOLVE_H
+
+#include <rr.h>
+
+#include "args.h"
+
+typedef unsigned int rrs_state_t;
+
+typedef struct {
+ rrs_state_t *state;
+ int num_states;
+
+ int size;
+
+ int sorted;
+} rrs_state_buf_t;
+
+typedef struct {
+ rr_robot_t robot;
+ rr_direction_t dir;
+} rrs_move_t;
+
+typedef struct {
+ rrs_move_t *move;
+ int num_moves;
+ int size;
+} rrs_solution_t;
+
+/* rrs_solution.c */
+
+rr_status_t
+rrs_solution_init (rrs_solution_t *solution);
+
+void
+rrs_solution_fini (rrs_solution_t *solution);
+
+rr_status_t
+rrs_solution_push (rrs_solution_t *solution,
+ rr_robot_t robot, rr_direction_t dir);
+
+rr_status_t
+rrs_solution_pop (rrs_solution_t *solution,
+ rr_robot_t *robot, rr_direction_t *dir);
+
+rr_status_t
+rrs_solution_prepend (rrs_solution_t *solution,
+ rr_robot_t robot, rr_direction_t dir);
+
+/* rrs_state_buf.c */
+
+rrs_state_buf_t *
+rrs_state_buf_create (int initial_size);
+
+void
+rrs_state_buf_destroy (rrs_state_buf_t *buf);
+
+rr_status_t
+rrs_state_buf_add (rrs_state_buf_t *buf, rrs_state_t state);
+
+rr_status_t
+rrs_state_buf_add_sorted (rrs_state_buf_t *buf, rrs_state_t state);
+
+rr_status_t
+rrs_state_buf_append (rrs_state_buf_t *buf, rrs_state_buf_t *other);
+
+rr_status_t
+rrs_state_buf_remove (rrs_state_buf_t *buf, rrs_state_t state);
+
+int
+rrs_state_buf_contains (rrs_state_buf_t *buf, rrs_state_t state);
+
+#endif
projects / rrsolve / commitdiff