Steven Elliott's Website

/*************************************************************************/
/*                             JrCube 0.9.5                              */
/*                                  by                                   */
/*                           Steven L. Elliott                           */
/*                                                                       */
/* This program will form a complete database of all possible            */
/* permutations of the 2x2x2 Rubik's cube, known as Rubik's Jr, and then */
/* uses that database to solve a provided cube in a minimum number of    */
/* twists.  The 3.6 MiB database is generated using the '-g' option.     */
/*                                                                       */
/* Indent : indent -gnu -nut -i4 -bli0 -npcs -nbad jrcube.c              */
/*************************************************************************/
 
#define _GNU_SOURCE             /* Needed for asprintf() */
 
#include <errno.h>
#include <getopt.h>
#include <libgen.h>
#include <stdarg.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <sys/stat.h>
#include <sys/types.h>
#include <time.h>
#include <unistd.h>
 
/* TODO: Come up with a better system to detect what features are available. */
 
#ifdef __linux__
#define HAVE_MMAP 1
#endif
 
#ifdef HAVE_MMAP
#include <fcntl.h>
#include <sys/mman.h>
#endif
 
/* Types */
 
/* For each of the eight locations that make up the larger cube the number of
 * the smaller cube that is there and it's rotation.
 */
typedef struct
{
    int piece;                  /* Piece number 0-7 */
    int rot;                    /* 0-not rotated  1-to the left  2-to the right */
} mini_cube_t;
 
/* Item in the sides table.  See that table for details. */
typedef struct
{
    int poss[4];
    int rots[4];
} side_t;
 
/* Item in the orienting_turns table.  See that table for details. */
typedef struct
{
    int turns[4];
} orienting_turns_t;
 
/* The state of a particular cube as well as previous and next pointers. */
typedef struct cube_s
{
    struct cube_s *prev;
    struct cube_s *next;
    mini_cube_t pos[8];
    int index;
} cube_t;
 
/* An item in a linked list of items to be freed. */
typedef struct freeitem_s
{
    struct freeitem_s *next;
    void *ptr;
    int is_mmap;
    size_t size;
} freeitem_t;
 
/* Enumerations */
 
/* Log level argument passed in. */
typedef enum level_e
{
    level_debug,
    level_message,
    level_warning,
    level_fatal
} level_t;
 
/* Constants */
 
#define LOG_LEVEL level_message
 
#define NOOP     0
#define GENERATE 1
#define SOLVE    2
#define TEST     4
 
#define DB_SIZE  3674160
#define MAX_CF_NAMES 200
#define MAX_TWISTS 0x7f
#define LOWER ('a' - 'A')       /* Add this in ASCII to convert to lower case. */
 
#ifndef JC_LIB_DIR
#define JC_LIB_DIR "/usr/local/lib/jrcube"
#endif
 
/* Globals */
 
/* Linked list to be freed later. */
static freeitem_t *freeitem;
 
/* Calculated at runtime based on other values.  This is used to calculate the
 * index for a cube.
 */
static int digit_value[13];
 
/* Global tables */
 
/* When translating to and from an index the cube can be thought of as a
 * mixed base number.  Each entry indicates the base of that digit.  The
 * first row is for the rotations and the second row is for pieces.
 * The angle of the last corner is deduced.
 */
static const int digit_base[13] = { 3, 3, 3, 3, 3, 3, 1, 2, 3, 4, 5, 6, 7 };
 
/* Each side of the cube consists of four smaller cubes.  When a twist is
 * applied to a side the four smaller cubes that make up that side are
 * rearranged in a way that can be described as an item being removed from
 * a sequence and pushed onto the other end of the sequence:
 *   ABCD -> DABC
 * What the following table does is for each twist that can be done to a side
 * the index in the sequence (ABCD in the example above) is mapped onto the
 * position in the cube.
 */
static const side_t sides[] = {
    {{4, 0, 2, 6}, {2, 1, 2, 1}},       /* x+ */
    {{1, 5, 7, 3}, {2, 1, 2, 1}},       /* X+ */
    {{1, 0, 4, 5}, {0, 0, 0, 0}},       /* y+ */
    {{2, 3, 7, 6}, {0, 0, 0, 0}},       /* Y+ */
    {{0, 1, 3, 2}, {2, 1, 2, 1}},       /* z+ */
    {{5, 4, 6, 7}, {2, 1, 2, 1}}        /* Z+ */
};
 
/* A series of indexes into sides that indicates the turns required to
 * orient piece zero to positions zero.  Terminated by -1.
 */
/* *INDENT-OFF* */
static const orienting_turns_t orienting_turns[] = {
    {{-1, -1, -1, -1}},         /* piece 0 at 0 */
    {{ 3, -1, -1, -1}},         /* piece 0 at 1 */
    {{ 5, -1, -1, -1}},         /* piece 0 at 2 */
    {{ 5,  5, -1, -1}},         /* piece 0 at 3 */
    {{ 1, -1, -1, -1}},         /* piece 0 at 4 */
    {{ 3,  3, -1, -1}},         /* piece 0 at 5 */
    {{ 1,  1, -1, -1}},         /* piece 0 at 6 */
    {{ 1,  1,  3, -1}}          /* piece 0 at 7 */
};
/* *INDENT-ON* */
 
/* Utility functions */
 
/* Add memory to a list of items that are to be freed later. */
static void
freeitem_add(void *ptr, int is_mmap, size_t size)
{
    freeitem_t *fi = malloc(sizeof(*fi));
 
    if (!fi)
    {
        /* If memory has been exhausted then just leak this item. */
        return;
    }
 
    fi->next = freeitem;
    fi->ptr = ptr;
    fi->is_mmap = is_mmap;
    fi->size = size;
 
    freeitem = fi;
}
 
/* Iterate through the freeitem linked list of items and either free or unmap
 * them.
 */
static void
freeitem_free()
{
    freeitem_t *fi;
    freeitem_t *fi_next;
 
    for (fi = freeitem; fi; fi = fi_next)
    {
        if (fi->is_mmap)
        {
#ifdef HAVE_MMAP
            /* Don't bother with error handling since we are shutting down. */
            munmap(fi->ptr, fi->size);
#endif
        }
        else
        {
            free(fi->ptr);
        }
 
        fi_next = fi->next;
        free(fi);
    }
}
 
/* Error handling functions */
 
/* Logs a message to stderr.  If the level is high enough then the errno
 * may be decoded.  For fatal errors this program is aborted.
 */
static void
log_msg(level_t level, const char *fmt, ...)
{
    va_list ap;
 
    if (level < LOG_LEVEL)
    {
        return;
    }
 
    va_start(ap, fmt);
 
    vfprintf(stderr, fmt, ap);
    if ((level >= level_warning) && errno)
    {
        fprintf(stderr, "errno=%d - %s\n", errno, strerror(errno));
    }
 
    if (level >= level_fatal)
    {
        fprintf(stderr, "FATAL ERROR.  Exiting.\n");
        exit(1);
    }
 
    va_end(ap);
}
 
/* Conversion functions */
 
/* Convert a list of unique items ("perms") to a mixed based number ("digits")
 * that is equal to the unique items' index if the list of all possible
 * unique items were put in reverse order.  For example consider the various
 * permutations of 'A', 'B' and 'C' if they were arranged in reverse order and
 * what their "digits" would be:
 *
 *   Perms   Digits   Index
 *     CBA      000       0
 *     CAB      010       1
 *     BCA      100       2
 *     BAC      110       3
 *     ACB      200       4
 *     ABC      210       5
 *
 * In the above the index is determined as a function of the digits where
 * each digit has some weighted value.  The first (most significant) digit is
 * worth 2, the second is worth 1 and the last zero.  So, BAC, for example,
 * is worth 2 * 1 + 1 * 1 + 0 * 1 = 3
 *
 * Each digit is equal to the number of less significant items that follow the
 * item that corresponds to the digit that are greater in value.  For example
 * For BAC the digit that corresponds to the 'B' is 1 because there  is one
 * less significant item that follows that is greater in value (the 'C'
 * but not the 'A').
 *
 * The above definition, particularly the part about it being in reverse order,
 * was chosen so that the solved position is at index zero.  The solved position
 * involves placing the lowest numbered pieces in the least significant
 * locations
 */
static void
digits_from_perms(int *digits, int *perms, int num)
{
    int digit_val;
    int item_index;
    int item_scan;
 
    memset(digits, 0, num * sizeof(int));
 
    for (item_index = num - 1; item_index >= 0; item_index--)
    {
        digit_val = 0;
 
        for (item_scan = item_index - 1; item_scan >= 0; item_scan--)
        {
            if (perms[item_scan] > perms[item_index])
            {
                digit_val++;
            }
        }
 
        digits[item_index] = digit_val;
    }
}
 
/* This does the reverse of digits_from_perms().  See that functions comments
 * for details.
 */
static void
perms_from_digits(int *perms, int *digits, int num)
{
    int item_index;
    int perm_buff;
    int perm_sort;
 
    for (item_index = 0; item_index < num; item_index++)
    {
        perms[item_index] = num - item_index;
    }
 
    for (item_index = num - 1; item_index >= 0; item_index--)
    {
        /* Place the number indicated by the mixed case number first. */
        perm_buff = perms[item_index];
        perms[item_index] = perms[digits[item_index]];
        perms[digits[item_index]] = perm_buff;
 
        if (digits[item_index] < (item_index - 1))
        {
            /* Make sure that the remaining perms are in descending order. */
            for (perm_sort = digits[item_index]; perm_sort < (item_index - 1);
                 perm_sort++)
            {
                perms[perm_sort] = perms[perm_sort + 1];
            }
            perms[item_index - 1] = perm_buff;
        }
    }
}
 
/* Converts a numeric rotation to something descriptive. */
static char
rot_to_char(int rot)
{
    switch (rot)
    {
    case 0:
        return '-';
    case 1:
        return 'L';
    case 2:
        return 'R';
    default:
        return '?';             /* This should not happen. */
    }
}
 
/* Converts a descriptive rotation to something numeric. */
static int
char_to_rot(char rot)
{
    switch (rot)
    {
    case '-':
        return 0;
    case 'L':
        return 1;
    case 'R':
        return 2;
    default:
        return 999;             /* This should not happen. */
    }
}
 
/* Converts a numeric position to something descriptive.  The 8 small cubes
 * are numbered 0 through 7.  They are enumerated by looping through the cubes
 * X, Y and Z axis with the X axis in the inner most loop.
 * */
static char *
pos_to_str(int pos, char *str)
{
    int x_front = 1 & pos;
    int y_front = 2 & pos;
    int z_front = 4 & pos;
 
    sprintf(str, "%c%c%c", 'X' + (x_front ? 0 : LOWER),
            'Y' + (y_front ? 0 : LOWER), 'Z' + (z_front ? 0 : LOWER));
    return str;
}
 
/* Convert a numeric piece to something descriptive (the colors that appears
 * on that piece / small cube).
 */
static char *
piece_to_str(int piece, char *str)
{
    int x_front = 1 & piece;
    int y_front = 2 & piece;
    int z_front = 4 & piece;
 
    sprintf(str, "%c%c%c", (x_front ? 'R' : 'O'), (y_front ? 'B' : 'G'),
            (z_front ? 'W' : 'Y'));
    return str;
}
 
/* Output functions */
 
/* Output the state of the cube.  Each small cube / piece is displayed as
 * well as the rotation.  Note that the numeric columns demonstrate the format
 * of input files.
 */
static void
cube_print(cube_t * cube)
{
    char piece_str[4];
    char pos_str[4];
    int pos_index;
 
    printf("Pos #\tPos\tPiece #\tPiece\tRotation\n");
    for (pos_index = 0; pos_index <= 7; pos_index++)
    {
        printf("%d\t%s\t%d\t%s\t%c\n", pos_index,
               pos_to_str(pos_index, pos_str), cube->pos[pos_index].piece,
               piece_to_str(cube->pos[pos_index].piece, piece_str),
               rot_to_char(cube->pos[pos_index].rot));
    }
}
 
static void
print_twist(int front, char axis, int sign)
{
    printf("%c%c ", axis + (front ? 0 : ('a' - 'A')), (sign > 0) ? '+' : '-');
}
 
/* Cube functions */
 
/* Make sure that the rotations of the pieces are such that the cube is
 * solvable.  Rotating one of the eight pieces without making any other changes
 * results in a cube that can not be solved.
 */
static int
cube_rot_check(cube_t * cube)
{
    int pos_index;
    int rot_total = 0;
 
    for (pos_index = 0; pos_index <= 7; pos_index++)
    {
        rot_total += cube->pos[pos_index].rot;
    }
 
    return rot_total % 3;
}
 
/* A lower level version of cube_twist().  It applies a twist by taking a
 * mapping for the sides and rotations (which small cube gets mapped to which
 * position, etc.).  See cube_twist() for details.
 */
static void
cube_rot_circulate(cube_t * cube, const int rots[], const int poss[], int num,
                   int sign)
{
    int item_index;
    mini_cube_t mc_buf;
 
    for (item_index = 0; item_index < num; item_index++)
    {
        cube->pos[poss[item_index]].rot = (cube->pos[poss[item_index]].rot
                                           + rots[item_index]) % 3;
    }
 
    if (sign == 1)
    {
        mc_buf = cube->pos[poss[0]];
 
        for (item_index = 0; item_index < (num - 1); item_index++)
        {
            cube->pos[poss[item_index]] = cube->pos[poss[item_index + 1]];
        }
 
        cube->pos[poss[num - 1]] = mc_buf;
    }
    else
    {
        mc_buf = cube->pos[poss[num - 1]];
 
        for (item_index = num - 1; item_index > 0; item_index--)
        {
            cube->pos[poss[item_index]] = cube->pos[poss[item_index - 1]];
        }
 
        cube->pos[poss[0]] = mc_buf;
    }
}
 
/* Reduce the size required for the database by taking advantage of symmetry.
 * Before attempting to find the index for a given cube it is first oriented
 * into a standard position such that the zero cube (piece 0) is in
 * position 0.  Also, the cube is rotated so that the zero cube has no rotation.
 * This results in the zero cube always being it it's solved location and
 * rotation, so it can be ignored for the index calculation.
 */
static void
cube_orient(cube_t * cube)
{
    int pos_zero;               /* Position of the zero cube. */
    int side;
    int turn;
    int xside;                  /* The opposing parallel side. */
 
    /* Find the location of the zero cube. */
    for (pos_zero = 0; (pos_zero <= 7) && cube->pos[pos_zero].piece;
         pos_zero++);
 
    /* Rotate the entire cube so that the zero cube ends up in the zero
     * position.
     */
    for (turn = 0; (side = orienting_turns[pos_zero].turns[turn])
         != -1; turn++)
    {
        /* Turn the cube along the specified side. */
        cube_rot_circulate(cube, sides[side].rots, sides[side].poss, 4, 1);
 
        /* Determine the opposite side and sign (ex., X+ becomes x-) and
         * perform that turn.  The result is the entire cube is turned.
         */
        xside = 1 ^ side;
        cube_rot_circulate(cube, sides[xside].rots, sides[xside].poss, 4, -1);
    }
 
    /* Rotate the entire cube along the diagonal axis that passes through
     * position 0 and position 7 so that the zero cube no longer has any
     * rotation.  It turns out that rotating the entire cube along this
     * diagonal axis circulates smaller cubes around paths that are three cubes
     * long.
     */
    switch ((3 - cube->pos[0].rot) % 3)
    {
    case 1:
        /* Zero cube at position 0 is rotated to the right. */
        cube->pos[0].rot = (cube->pos[0].rot + 1) % 3;
 
        {
            const int rots[] = { 2, 2, 2 };
            const int poss[] = { 4, 1, 2 };
            cube_rot_circulate(cube, rots, poss, 3, 1);
        }
 
        {
            const int rots[] = { 1, 1, 1 };
            const int poss[] = { 5, 3, 6 };
            cube_rot_circulate(cube, rots, poss, 3, 1);
        }
 
        cube->pos[7].rot = (cube->pos[7].rot + 2) % 3;
        break;
 
    case 2:
        /* Zero cube at position 0 is rotated to the left. */
        cube->pos[0].rot = (cube->pos[0].rot + 2) % 3;
 
        {
            const int rots[] = { 1, 1, 1 };
            const int poss[] = { 2, 1, 4 };
            cube_rot_circulate(cube, rots, poss, 3, 1);
        }
 
        {
            const int rots[] = { 2, 2, 2 };
            const int poss[] = { 6, 3, 5 };
            cube_rot_circulate(cube, rots, poss, 3, 1);
        }
 
        cube->pos[7].rot = (cube->pos[7].rot + 1) % 3;
        break;
    }
}
 
/* Get and index for a cube by first converting the positions and the rotations
 * to a mixed base number.  See digits_from_perms() for details.
 */
static void
cube_set_index(cube_t * cube)
{
    cube_t cube_loc = *cube;
    int digit;
    int digits[13];
    int pieces[7];
    int pos_index;
 
    cube_orient(&cube_loc);
 
    for (pos_index = 1; pos_index <= 7; pos_index++)
    {
        pieces[pos_index - 1] = cube_loc.pos[pos_index].piece;
 
        if (pos_index != 7)
        {
            digits[pos_index - 1] = cube_loc.pos[pos_index].rot;
        }
    }
 
    digits_from_perms(digits + 6, pieces, 7);
 
    cube->index = 0;
    for (digit = 12; digit >= 0; digit--)
    {
        cube->index += digit_value[digit] * digits[digit];
    }
}
 
/* A constructor that returns a new cube based on a specified cube. */
cube_t *
cube_new_cube(cube_t * cube)
{
    cube_t *cube_new;
 
    if (!(cube_new = malloc(sizeof(*cube_new))))
    {
        log_msg(level_fatal, "Unable to allocate %d bytes for a cube_new\n",
                DB_SIZE);
    }
 
    *cube_new = *cube;
    /* Assume the caller will keep a reference to the cube_new returned. */
    return cube_new;
}
 
/* A constructor that creates a new cube by loading it from a file. The cube
 * file has three columns:
 *   Position Number   Piece Number   Rotation
 * Errors reading the specified file causes this program to abort.
 */
static cube_t *
cube_new_fname(char *cf_name)
{
    FILE *cf_fp;
    char rot[2];                /* Character and null terminator. */
    cube_t *cube;
    int piece;
    int pos;
    int total_rot;
 
    if (!(cf_fp = fopen(cf_name, "r")))
    {
        log_msg(level_fatal, "Could not open cube file for read: %s\n",
                cf_name);
    }
 
    printf("Loading %s:\n\n", cf_name);
 
    cube = calloc(1, sizeof(*cube));
 
    while (3 == fscanf(cf_fp, "%d%d%1s\n", &pos, &piece, rot))
    {
        if ((pos < 0) || (pos > 7))
        {
            log_msg(level_fatal,
                    "Position with value %d is outside the allowed "
                    "[0, 7] range.\n", pos, pos);
        }
 
        if ((piece < 0) || (piece > 7))
        {
            log_msg(level_fatal, "Piece with value %d is outside the allowed "
                    "[0, 7] range.\n", piece, piece);
        }
 
        cube->pos[pos].piece = piece;
        cube->pos[pos].rot = char_to_rot(*rot);
 
        if (cube->pos[pos].rot == 999)
        {
            log_msg(level_fatal, "Invalid rotation of '%s' specified.   Only "
                    "'L', '-' and 'R' are allowed.\n", rot);
        }
    }
    fclose(cf_fp);
 
    cube_print(cube);
 
    if ((total_rot = cube_rot_check(cube)))
    {
        log_msg(level_fatal, "The pieces have an additional rotation of %d "
                "(the sum of the rotations mod 3 is not zero).  Can not "
                "solve.\n", total_rot);
    }
 
    cube_set_index(cube);
 
    return cube;
}
 
/* A constructor that creates a new cube from a specified index.  */
static cube_t *
cube_new_index(int index)
{
    cube_t *cube;
    int digit;
    int digits[13];
    int pieces[7];
    int pos_index;
    int remaining = index;
 
    cube = calloc(1, sizeof(*cube));
    memset(cube, 0, sizeof(cube));
 
    for (digit = 12; digit >= 0; digit--)
    {
        digits[digit] = remaining / digit_value[digit];
        remaining -= digits[digit] * digit_value[digit];
    }
 
    perms_from_digits(pieces, digits + 6, 7);
 
    for (pos_index = 1; pos_index <= 7; pos_index++)
    {
        cube->pos[pos_index].piece = pieces[pos_index - 1];
 
        if (pos_index != 7)
        {
            cube->pos[pos_index].rot = digits[pos_index - 1];
        }
        else
        {
            /* The rotation of the last cube can be deduced. */
            cube->pos[pos_index].rot = (3 - cube_rot_check(cube)) % 3;
        }
    }
 
    cube->index = index;
    return cube;
}
 
/* Shallow free of the specified cube. */
static void
cube_free(cube_t * cube)
{
    if (cube)
    {
        free(cube);
    }
}
 
/* Deep free of the specified cube.  The term "history" is used since the
 * linked list is traversed backwards to free the older cubes.
 */
static void
cube_free_history(cube_t * cube)
{
    cube_t *cube_prev;
 
    while (cube)
    {
        cube_prev = cube->prev;
        cube_free(cube);
        cube = cube_prev;
    }
}
 
/* Perform a given twist by causing the pieces to switch places.  The rotations
 * are updated for pieces that cross the X-Z plane.
 */
static cube_t *
cube_twist(cube_t * cube, int front, char axis, int sign)
{
    cube_t *next_cube;
    int side;
 
    next_cube = cube_new_cube(cube);
    next_cube->prev = cube;
    cube->next = next_cube;
 
    side = 2 * (axis - 'X') + front;
    cube_rot_circulate(next_cube, sides[side].rots, sides[side].poss, 4,
                       sign);
 
    cube_set_index(next_cube);
 
    return next_cube;
}
 
/* Undoes a twist by reverting to the saved cube and index.
 */
static cube_t *
cube_untwist(cube_t * cube, int do_free)
{
    cube_t *prev_cube;
 
    /* This assumes that when a twist is undone it is not redone again later. */
    prev_cube = cube->prev;
    if (do_free)
    {
        cube_free(cube);
    }
    prev_cube->next = NULL;
 
    return prev_cube;
}
 
/* Try each possible twist and find the twist / twist that works best (that
 * gets the cube closer to being solved).
 */
cube_t *
cube_best_twist(cube_t * cube, char *db, int mode, int *num_good_twists)
{
    char axis;
    char axis_best;
    cube_t *cube_best = NULL;
    int num_twists;
    int score;
    int score_best;
    int sign;
    int sign_best;
 
    if (num_good_twists)
    {
        *num_good_twists = 0;
    }
 
    if ((cube->index < 0) || (cube->index >= DB_SIZE))
    {
        log_msg(level_fatal, "Invalid position.  index=%d\n", cube->index);
    }
 
    num_twists = db[cube->index];
    log_msg(level_debug, "num_twists=%d\n", num_twists);
 
    if (SOLVE & mode)
    {
        if (!num_twists)
        {
            /* The cube is already solved. */
            return NULL;
        }
 
        /* Start with the current score so that only twists that get closer to
         * solved are considered.
         */
        score_best = num_twists << 16;
    }
 
    for (axis = 'X'; axis <= 'Z'; axis++)
    {
        for (sign = -1; sign <= 1; sign += 2)
        {
            cube = cube_twist(cube, 1, axis, sign);
            if (GENERATE & mode)
            {
                if (db[cube->index] > (num_twists + 1))
                {
                    db[cube->index] = num_twists + 1;
                    if (num_good_twists)
                    {
                        (*num_good_twists)++;
                    }
                }
            }
            if (SOLVE & mode)
            {
#ifdef RND_SOLUTIONS
                /* Pick a twist at random that gets it closer to solved . */
                score = (db[cube->index] << 16) + (rand() % 0x10000);
#else
                /* Construct the score so that following is considered in
                 * order of importance:
                 *   1) Twists that reduce the number of twists from solved.
                 *   2) Twists that are in a positive direction.
                 *   3) First 'X", then 'Y' and finally 'Z'.
                 */
                score = (db[cube->index] << 16) + ((1 - sign) << 8) + axis;
#endif
                log_msg(level_debug, "score=%06x axis=%c sign=%2d\n", score,
                        axis, sign);
                if (score < score_best)
                {
                    score_best = score;
                    log_msg(level_debug, "score_best=%06x\n", score_best);
                    if (cube_best)
                    {
                        cube_free(cube_best);
                    }
                    cube_best = cube;
                    axis_best = axis;
                    sign_best = sign;
 
                    if (num_good_twists)
                    {
                        (*num_good_twists)++;
                    }
                }
            }
            cube = cube_untwist(cube, cube != cube_best);
        }
    }
 
    if ((SOLVE & mode) && cube_best)
    {
        print_twist(1, axis_best, sign_best);
    }
 
    return cube_best;
}
 
/* Solve the cube by starting with init_cube and seeing which twists, according
 * to the database, brings the cube closer to being solved.
 */
static cube_t *
cube_solve(cube_t * cube, char *db)
{
    cube_t *cube_last = NULL;
 
    while ((cube = cube_best_twist(cube, db, SOLVE, NULL)))
    {
        cube_last = cube;       /* The last non-null cube found. */
    }
 
    if (!cube_last)
    {
        /* Due to previous input checking the following should never happen. */
        log_msg(level_fatal, " Unable to find any twist that improves the "
                "specified cube.\n");
    }
 
    if (cube_last->index)
    {
        log_msg(level_warning,
                " Index %d instead of 0.  Solution not valid.\n",
                cube_last->index);
    }
 
    putchar('\n');
    return cube_last;
}
 
/* Database functions */
 
/* For a given index set the number of twists from solved.  Although currently
 * the database is just an array this allows for some abstraction.
 */
static int
dbase_set_twists(char *db, int num_twists)
{
    cube_t *cube;
    int index;
    int num_changes;
    int num_total = 0;
 
    for (index = 0; index < DB_SIZE; index++)
    {
        if (db[index] == num_twists)
        {
            cube = cube_new_index(index);
            cube_best_twist(cube, db, GENERATE, &num_changes);
            cube_free(cube);
            num_total += num_changes;
        }
    }
 
    printf("%d positions found %d twists from solved.\n", num_total,
           num_twists + 1);
    return num_total;
}
 
/* A constructor that creates a new database by allocating an array, marking the
 * solved position as zero twists from being solved and then working backwards
 * (one positions one twist from solved are marked as one twist from solved,
 * etc.).
 */
static char *
dbase_new_fname_gen(char *fname, int *do_mmap)
{
#ifdef HAVE_MMAP
    int db_fd;
#else
    FILE *db_fp;
#endif
    char *db;
    int num_twists;
    struct stat db_stat;
 
    /* Delete the db, if it exists. */
    if (stat(fname, &db_stat) != -1)
    {
        if (remove(fname) == -1)
        {
            log_msg(level_fatal, "Unable to remove existing database at %s\n",
                    fname);
        }
    }
 
#ifdef HAVE_MMAP
    *do_mmap = 1;
 
    /* Although 0666 is used for the following the umask will limit the
     * permissions on the resulting file.
     */
    if ((db_fd = open(fname, O_CREAT | O_RDWR, 0666)) == -1)
    {
        log_msg(level_fatal, "Unable to open the database at %s\n", fname);
    }
 
    /* Make sure a sparse file exists by seeking forward and writing a single
     * zero at the end.
     */
    lseek(db_fd, DB_SIZE - 1, SEEK_SET);
    write(db_fd, "", 1);
 
    if ((db =
         mmap(NULL, DB_SIZE, PROT_READ | PROT_WRITE, MAP_SHARED, db_fd,
              0)) == MAP_FAILED)
    {
        log_msg(level_fatal, "Unable to mmap the database at %s\n", fname);
    }
 
    close(db_fd);
#else
    *do_mmap = 0;
 
    if (!(db = malloc(DB_SIZE)))
    {
        log_msg(level_fatal, "Unable to allocate %d bytes for db\n", DB_SIZE);
    }
#endif
    memset(db, MAX_TWISTS, DB_SIZE);
    db[0] = 0;                  /* Mark the first position as solved. */
 
    for (num_twists = 0; num_twists < MAX_TWISTS; num_twists++)
    {
        if (!dbase_set_twists(db, num_twists))
        {
            /* No changes to the database were made. */
            break;
        }
    }
 
#ifndef HAVE_MMAP
    if (!(db_fp = fopen(fname, "wb")))
    {
        log_msg(level_fatal, "Could not open database for write: %s\n",
                fname);
    }
 
    fwrite(db, DB_SIZE, 1, db_fp);
    fclose(db_fp);
#endif
 
    return db;
}
 
/* A constructor that creates a new database by loading it from a specified file.
 */
static char *
dbase_new_fname_load(const char *fname, int *do_mmap)
{
#ifdef HAVE_MMAP
    int db_fd;
#else
    FILE *db_fp;
#endif
    char *db;
    struct stat db_stat;
 
    if (stat(fname, &db_stat) == -1)
    {
        log_msg(level_fatal, "Unable to stat the database at %s\n", fname);
    }
    if (db_stat.st_size != DB_SIZE)
    {
        log_msg(level_fatal, "Database at %s is %d bytes instead of %d\n",
                fname, db_stat.st_size, DB_SIZE);
    }
 
#ifdef HAVE_MMAP
    *do_mmap = 1;
 
    if ((db_fd = open(fname, O_RDONLY)) == -1)
    {
        log_msg(level_fatal, "Unable to open the database at %s\n", fname);
    }
 
    if ((db = mmap(NULL, DB_SIZE, PROT_READ, MAP_PRIVATE, db_fd, 0)) ==
        MAP_FAILED)
    {
        log_msg(level_fatal, "Unable to mmap the database at %s\n", fname);
    }
 
    close(db_fd);
#else
    *do_mmap = 0;
 
    if (!(db = malloc(DB_SIZE)))
    {
        log_msg(level_fatal, "Unable to allocate %d bytes to load the "
                "db\n", DB_SIZE);
    }
 
    if (!(db_fp = fopen(fname, "rb")))
    {
        log_msg(level_fatal, "Could not open database for read: %s\n", fname);
    }
 
    /* TODO: Add other validation.  Maybe the database should have a magic
     * header.  Maybe it should be stat'd to make sure it is the right size.
     */
 
    if (fread(db, DB_SIZE, 1, db_fp) < 1)
    {
        fclose(db_fp);
        log_msg(level_fatal, "Short read for the db: %s\n", fname);
    }
 
    fclose(db_fp);
#endif
 
    return db;
}
 
/* Misc functions */
 
/* Do whatever has to be done for shutdown. */
static void
deinit()
{
    freeitem_free();
}
 
/* Initialize global arrays that are redundant to other data (arrays where it
 * would be inefficient for them to have their own initializers).
 */
static void
init()
{
    int digit;
    int digit_val = 1;
 
    for (digit = 0; digit <= 12; digit++)
    {
        digit_value[digit] = digit_val;
        digit_val *= digit_base[digit];
    }
 
    atexit(deinit);
}
 
/* Test the code by applying various twists and then the corresponding
 * anti-twist.  After each anti-twist the cube should return to it's original
 * solved state with an index of 0 where dbase[0] = 0 (the solved cube,
 * stored at index 0, is 0 twists from being solved).
 */
static void
test(const char *db)
{
    cube_t *cube;
 
    printf("The database is %sloaded.\n\n", db ? "" : "NOT ");
 
    cube = cube_new_index(0);
 
    cube = cube_twist(cube, 1, 'X', 1);
    printf("X+ index=%d from_solved=%d\n", cube->index,
           db ? db[cube->index] : 0);
    cube_print(cube);
 
    cube = cube_twist(cube, 1, 'X', -1);
    printf("\nX- index=%d from_solved=%d\n", cube->index,
           db ? db[cube->index] : 0);
    cube_print(cube);
 
    cube = cube_twist(cube, 0, 'Y', 1);
    printf("\nY+ index=%d from_solved=%d\n", cube->index,
           db ? db[cube->index] : 0);
    cube_print(cube);
 
    cube = cube_twist(cube, 0, 'Y', -1);
    printf("\nY- index=%d from_solved=%d\n", cube->index,
           db ? db[cube->index] : 0);
    cube_print(cube);
 
    cube = cube_twist(cube, 0, 'Z', 1);
    printf("\nZ+ index=%d from_solved=%d\n", cube->index,
           db ? db[cube->index] : 0);
    cube_print(cube);
 
    cube = cube_twist(cube, 0, 'Z', -1);
    printf("\nZ- index=%d from_solved=%d\n", cube->index,
           db ? db[cube->index] : 0);
    cube_print(cube);
 
    cube_free_history(cube);
}
 
/* Simple usage statement. */
static void
usage(const char *name)
{
    fprintf(stderr, "Usage: %s -g dbase\n", name);
    fprintf(stderr, "Usage: %s [-l dbase] [-n solutions] -s cube file "
            "[-s cube file ...]\n", name);
    fprintf(stderr, "Usage: %s -t\n", name);
 
    exit(1);
}
 
/* Main entry point.  This parses command line options and calls everything
 * else.
 */
int
main(int argc, char *argv[], char *envp[])
{
    char *cf_name[MAX_CF_NAMES];
    char *db;
    char *dbase_fname = NULL;
    char opt_char;
    char opt_err = 0;
    cube_t *cube_init;
    cube_t *cube_solved;
    int cube_file_index;
    int cube_files = 0;
    int do_mmap;
    int mode = NOOP;
    int sol_count;
    int solutions = 1;
    int solve_args = 0;
 
    init();
 
    while (EOF != (opt_char = getopt(argc, argv, "g:l:n:s:t")))
    {
        switch (opt_char)
        {
        case 'g':
            mode |= GENERATE;
            dbase_fname = strdup(optarg);
            break;
        case 'l':
            mode |= SOLVE;
            solve_args++;
            dbase_fname = strdup(optarg);
            break;
        case 'n':
            mode |= SOLVE;
            solve_args++;
            solutions = atoi(optarg);
            break;
        case 's':
            mode |= SOLVE;
            solve_args++;
            if (cube_files == 200)
            {
                log_msg(level_fatal, "Too many cube files specified.");
                break;
            }
 
            cf_name[cube_files++] = optarg;
            break;
        case 't':
            mode |= TEST;
            break;
        default:
            opt_err = 1;
        }
    }
 
    if (!dbase_fname)
    {
        asprintf(&dbase_fname, "%s/%s.db", JC_LIB_DIR, basename(argv[0]));
    }
    if (!dbase_fname)
    {
        log_msg(level_fatal,
                "Unable to allocate memory for the database name.");
    }
    freeitem_add(dbase_fname, 0, 0);
 
    if (!mode || (mode > TEST) || opt_err ||
        ((mode == GENERATE) && (argc != 3)) ||
        ((mode == SOLVE) && !cube_files) ||
        ((mode == SOLVE) && (argc != (1 + 2 * solve_args))))
    {
        usage(basename(argv[0]));
    }
 
    if (GENERATE & mode)
    {
        db = dbase_new_fname_gen(dbase_fname, &do_mmap);
    }
    else
    {
        db = dbase_new_fname_load(dbase_fname, &do_mmap);
    }
    freeitem_add(db, do_mmap, DB_SIZE);
 
    if (TEST & mode)
    {
        test(db);
    }
    else if (SOLVE & mode)
    {
        for (cube_file_index = 0; cube_file_index < cube_files;
             cube_file_index++)
        {
            cube_init = cube_new_fname(cf_name[cube_file_index]);
 
            printf("\nSolutions:\n");
            for (sol_count = 1; sol_count <= solutions; sol_count++)
            {
                printf("  #%d: ", sol_count);
                cube_solved = cube_solve(cube_init, db);
                if (cube_solved)
                {
                    cube_free_history(cube_solved);
                }
            }
 
            if (cube_file_index != (cube_files - 1))
            {
                /* Newline if not the last cube. */
                putchar('\n');
            }
        }
    }
 
    return 0;
}