From 9661a03e8bc2204cf23e00bb98578fd2dd09fc56 Mon Sep 17 00:00:00 2001 From: Carl Worth Date: Wed, 25 Jun 2003 10:45:07 +0000 Subject: [PATCH] Initial revision --- .cvsignore | 20 ++ AUTHORS | 2 + COPYING | 20 ++ ChangeLog | 0 INSTALL | 11 ++ Makefile.am | 3 + NEWS | 0 README | 1 + autogen.sh | 28 +++ configure.in | 30 +++ src/.cvsignore | 6 + src/Makefile.am | 11 ++ src/args.c | 103 +++++++++++ src/args.h | 52 ++++++ src/rrs_solution.c | 120 ++++++++++++ src/rrs_state_buf.c | 248 +++++++++++++++++++++++++ src/rrsolve.c | 431 ++++++++++++++++++++++++++++++++++++++++++++ src/rrsolve.h | 99 ++++++++++ 18 files changed, 1185 insertions(+) create mode 100644 .cvsignore create mode 100644 AUTHORS create mode 100644 COPYING create mode 100644 ChangeLog create mode 100644 INSTALL create mode 100644 Makefile.am create mode 100644 NEWS create mode 100644 README create mode 100755 autogen.sh create mode 100644 configure.in create mode 100644 src/.cvsignore create mode 100644 src/Makefile.am create mode 100644 src/args.c create mode 100644 src/args.h create mode 100644 src/rrs_solution.c create mode 100644 src/rrs_state_buf.c create mode 100644 src/rrsolve.c create mode 100644 src/rrsolve.h diff --git a/.cvsignore b/.cvsignore new file mode 100644 index 0000000..43b89a7 --- /dev/null +++ b/.cvsignore @@ -0,0 +1,20 @@ +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 + + + + diff --git a/AUTHORS b/AUTHORS new file mode 100644 index 0000000..8ac74b5 --- /dev/null +++ b/AUTHORS @@ -0,0 +1,2 @@ +Carl Worth + diff --git a/COPYING b/COPYING new file mode 100644 index 0000000..d456b8e --- /dev/null +++ b/COPYING @@ -0,0 +1,20 @@ +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. + diff --git a/ChangeLog b/ChangeLog new file mode 100644 index 0000000..e69de29 diff --git a/INSTALL b/INSTALL new file mode 100644 index 0000000..051defa --- /dev/null +++ b/INSTALL @@ -0,0 +1,11 @@ +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 + diff --git a/Makefile.am b/Makefile.am new file mode 100644 index 0000000..bd02e6c --- /dev/null +++ b/Makefile.am @@ -0,0 +1,3 @@ +SUBDIRS = . src + + diff --git a/NEWS b/NEWS new file mode 100644 index 0000000..e69de29 diff --git a/README b/README new file mode 100644 index 0000000..2277566 --- /dev/null +++ b/README @@ -0,0 +1 @@ +rrsolve - Ricochet Robot solver diff --git a/autogen.sh b/autogen.sh new file mode 100755 index 0000000..3c416dd --- /dev/null +++ b/autogen.sh @@ -0,0 +1,28 @@ +#!/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 diff --git a/configure.in b/configure.in new file mode 100644 index 0000000..99bb91b --- /dev/null +++ b/configure.in @@ -0,0 +1,30 @@ +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 +]) diff --git a/src/.cvsignore b/src/.cvsignore new file mode 100644 index 0000000..8e57cc1 --- /dev/null +++ b/src/.cvsignore @@ -0,0 +1,6 @@ +.deps +Makefile +Makefile.in +rrsolve + + diff --git a/src/Makefile.am b/src/Makefile.am new file mode 100644 index 0000000..46a5363 --- /dev/null +++ b/src/Makefile.am @@ -0,0 +1,11 @@ +bin_PROGRAMS = rrsolve + +rrsolve_SOURCES = \ + args.c \ + args.h \ + rrsolve.c \ + rrs_state_buf.c \ + rrs_solution.c + +INCLUDES = $(rrsolve_CFLAGS) +LDFLAGS = $(rrsolve_LIBS) diff --git a/src/args.c b/src/args.c new file mode 100644 index 0000000..67d9703 --- /dev/null +++ b/src/args.c @@ -0,0 +1,103 @@ +/* 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 + */ + +#include +#include + +#include "args.h" + +const char *argp_program_version = "grrobot " VERSION; + +const char *argp_program_bug_address = ""; + +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); +} diff --git a/src/args.h b/src/args.h new file mode 100644 index 0000000..a0a3c42 --- /dev/null +++ b/src/args.h @@ -0,0 +1,52 @@ +/* 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 + */ + +#ifndef ARGS_H +#define ARGS_H + +#ifdef HAVE_CONFIG_H +#include "config.h" +#endif + +#include + +#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 diff --git a/src/rrs_solution.c b/src/rrs_solution.c new file mode 100644 index 0000000..140159c --- /dev/null +++ b/src/rrs_solution.c @@ -0,0 +1,120 @@ +/* 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 + */ + +#include +#include + +#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; +} diff --git a/src/rrs_state_buf.c b/src/rrs_state_buf.c new file mode 100644 index 0000000..3cba10f --- /dev/null +++ b/src/rrs_state_buf.c @@ -0,0 +1,248 @@ +/* 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 + */ + +#include +#include + +#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; +} diff --git a/src/rrsolve.c b/src/rrsolve.c new file mode 100644 index 0000000..80f17b1 --- /dev/null +++ b/src/rrsolve.c @@ -0,0 +1,431 @@ +/* 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 + */ + +#include +#include +#include +#include +#include + +#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; +} + diff --git a/src/rrsolve.h b/src/rrsolve.h new file mode 100644 index 0000000..b6fef4e --- /dev/null +++ b/src/rrsolve.h @@ -0,0 +1,99 @@ +/* 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 + */ + +#ifndef RRSOLVE_H +#define RRSOLVE_H + +#include + +#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 -- 2.43.0