DevQuiz2011jp - slidepuzzle

#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <string.h>
#include <sys/types.h>
#include <sys/stat.h>
#include <fcntl.h>

struct _globals {
    int LX; /* max Ls */
    int RX; /* max Rs */
    int UX; /* max Us */
    int DX; /* max Ds */
    int N;  /* number of pannels */
} globals;

struct node {
    int x;
    int y;
    char c;
    int canl;
    int canr;
    int canu;
    int cand;
    int dist;
};

struct pannel {
    int x;
    int y;
    char *s;
    char *sorted;
    int md;
    int round;
    char move;
    struct node *world;
    int solved;
    struct pannel *prev;
};

struct taskque {
    struct pannel *pannel;
    struct taskque *prev;
    struct taskque *next;
    int depth;
};

int manhattandistance(struct pannel *p, struct node *n)
{
    int i, len;
    int posc = n->x + n->x*n->y;
    int poss;
    char *s = p->sorted;

    if (n->c == '=')
        return 0;

    for (i=0, len=strlen(s) ; i<len ; i++, s++) {
        if (n->c == *s) {
            poss = i;
            break;
        }
    }

    if (posc > poss) {
        i = posc;
        posc = poss;
        poss = i;
    }

    n->dist = poss - posc;
    return n->dist;
}

int md(struct pannel *pannel)
{
    int i, len = pannel->x * pannel->y;
    struct node *n = pannel->world;

    pannel->md = 0;
    for (i=0 ; i<len ; i++) {
        pannel->md += manhattandistance(pannel, n++);
    }

    return pannel->md;
}

struct node *buildworld(struct pannel *pannel)
{
    struct node *world = (struct node *)
        calloc(1, sizeof(struct node) * pannel->x * pannel->y);
    struct node *n;
    int x, y;
    char *cp = pannel->s;

    if (!world) {
        perror("buildworld");
        exit(0);
    }

    n = world;
    for (y=0 ; y<pannel->y ; y++) {
        for (x=0 ; x<pannel->x ; x++, n++) {
            n->x = x;
            n->y = y;
            n->c = *cp++;
            if (n->c != '=') {
                if (x != 0)
                    n->canl = 1;
                if (x != pannel->x - 1)
                    n->canr = 1;
                if (y != 0)
                    n->canu = 1;
                if (y != pannel->y - 1)
                    n->cand = 1;
            }
            n->dist = manhattandistance(pannel, n);
            pannel->md += n->dist;
        }
    }

    n = world;
    for (y=0 ; y<pannel->y ; y++) {
        for (x=0 ; x<pannel->x ; x++, n++) {
            if (n->c == '=') {
                if (x != pannel->x - 1)
                    (n + 1)->canl = 0;
                if (x != 0)
                    (n - 1)->canr = 0;
                if (y != pannel->y - 1)
                    (n + pannel->x)->canu = 0;
                if (y != 0)
                    (n - pannel->x)->cand = 0;
            }
        }
    }

    pannel->world = world;
    return world;
}

void bubblesort(char *p)
{
    char *pp = p;
    int len = strlen(p);
    int i;
    for (i=0 ; i<len-1 ; i++, p++) {
        if (*p > *(p+1)) {
            char c = *p;
            *p = *(p+1);
            *(p+1) = c;
            bubblesort(pp);
        }
    }
}

char *presort(char *src) {
    int len = strlen(src);
    int i;
    char *dst = (char *)calloc(1, len + 1);
    char *sorted = (char *)calloc(1, len + 1);
    char *p, *q, *r;

    if (!dst || !sorted) {
        perror("presort");
        exit(0);
    }

    for (i=0, p=dst, q=src ; i<len ; i++, q++) {
        if (*q != '=' && *q != '0')
            *p++ = *q;
    }
    bubblesort(dst);
    for (i=0, p=dst, q=src, r=sorted ; i<len ; i++, q++) {
        if (*q == '=')
            *r++ = *q;
        else if (*q != '0')
            *r++ = *p++;
    }
    *r = '0';
    free(dst);
    return sorted;
}

void freeapannel(struct pannel *p)
{
    if (p) {
        if (p->world)
            free(p->world);
        free(p->s);
        free(p->sorted);
        free(p);
    }
}

void cleanup(struct taskque *root)
{
    struct taskque *q = root;

    while (q) {
        struct taskque *next = q->next;
        freeapannel(q->pannel);
        free(q);
        q = next;
    }
}

FILE *readglobal(char *name)
{
    FILE *f;
    char buf[80];
    f = fopen(name, "r");
    fgets(buf, sizeof(buf), f);
    sscanf(buf, "%d %d %d %d",
           &globals.LX, &globals.RX, &globals.UX, &globals.DX);
    fgets(buf, sizeof(buf), f);
    sscanf(buf, "%d", &globals.N);
    return f;
}

struct pannel *readapannel(FILE *f)
{
    char buf[80]; /* max 6x6 -> 40 */
    int len;
    struct pannel *p;

    fgets(buf, sizeof(buf), f);
    len = strlen(buf) - 4;

    p = (struct pannel *)calloc(1, sizeof(struct pannel));
    if (!p) {
        perror("readapannel");
        exit(0);
    }

    p->s = (char *)calloc(1, len + 1);
    if (!p->s) {
        perror("readapannel");
        exit(0);
    }

    sscanf(buf, "%d,%d,%s", &p->x, &p->y, p->s);
    return p;
}

struct node *findzero(struct pannel *p, struct node *world)
{
    struct node *n = world;
    int i;
    for (i=0 ; i<p->x*p->y ; i++, n++) {
        if (n->c == '0')
            return n;
    }
    return NULL;
}

struct node *moveup(struct pannel *pannel)
{
    struct node *zero = findzero(pannel, pannel->world);
    if (zero->canu) {
        struct node *world = pannel->world;
        struct node *zero = findzero(pannel, world);
        struct node *u = zero - pannel->x;
        char c = u->c;
        zero->c = c;
        u->c = '0';
        *(pannel->s + zero->x + pannel->x*zero->y) = c;
        *(pannel->s + u->x + pannel->x*u->y) = '0';
        u->dist = 0;
        pannel->md = md(pannel);
        return u;
    }
    return NULL;
}

struct node *movedown(struct pannel *pannel)
{
    struct node *zero = findzero(pannel, pannel->world);
    if (zero->cand) {
        struct node *world = pannel->world;
        struct node *zero = findzero(pannel, world);
        struct node *d = zero + pannel->x;
        char c = d->c;
        zero->c = c;
        d->c = '0';
        *(pannel->s + zero->x + pannel->x*zero->y) = c;
        *(pannel->s + d->x + pannel->x*d->y) = '0';
        d->dist = 0;
        pannel->md = md(pannel);
        return d;
    }
    return NULL;
}

struct node *moveleft(struct pannel *pannel)
{
    struct node *zero = findzero(pannel, pannel->world);
    if (zero->canl) {
        struct node *world = pannel->world;
        struct node *zero = findzero(pannel, world);
        struct node *l = zero - 1;
        char c = l->c;
        zero->c = c;
        l->c = '0';
        *(pannel->s + zero->x + pannel->x*zero->y) = c;
        *(pannel->s + l->x + pannel->x*l->y) = '0';
        l->dist = 0;
        pannel->md = md(pannel);
        return l;
    }
    return NULL;
}

struct node *moveright(struct pannel *pannel)
{
    struct node *zero = findzero(pannel, pannel->world);
    if (zero->canr) {
        struct node *world = pannel->world;
        struct node *zero = findzero(pannel, world);
        struct node *r = zero + 1;
        char c = r->c;
        zero->c = c;
        r->c = '0';
        *(pannel->s + zero->x + pannel->x*zero->y) = c;
        *(pannel->s + r->x + pannel->x*r->y) = '0';
        pannel->md = md(pannel);
        return r;
    }
    return NULL;
}

struct taskque *inserttask(struct taskque *r, struct pannel *p)
{
    struct taskque *q = (struct taskque *)calloc(1, sizeof(struct taskque));
    if (!q) {
        perror("inserttask");
        exit(0);
    }

    q->pannel = p;
    if (r) {
        if (r->next) {
            r->next->prev = q;
            q->next = r->next;
        }
        r->next = q;
        q->prev = r;
    }
    return q;
}

struct taskque *addtask(struct taskque *r, struct pannel *p)
{
    struct taskque *q = (struct taskque *)calloc(1, sizeof(struct taskque));
    if (!q) {
        perror("inserttask");
        exit(0);
    }

    q->pannel = p;
    if (r) {
        while (r->next) {
            r = r->next;
        }
        if (r->next)
            r->next->prev = q;
        q->next = r->next;
        r->next = q;
        q->prev = r;
    }
    return q;
}

struct taskque *sorttask(struct taskque *r, struct pannel *p)
{
    struct taskque *q = (struct taskque *)calloc(1, sizeof(struct taskque));
    if (!q) {
        perror("inserttask");
        exit(0);
    }

    q->pannel = p;
    if (r) {
        while (r->next) {
            if (r->next->pannel->md + r->next->pannel->round \
                > q->pannel->md + q->pannel->round)
                break;
            r = r->next;
        }
        if (r->next)
            r->next->prev = q;
        q->next = r->next;
        r->next = q;
        q->prev = r;
    }
    return q;
}

struct pannel *copypannel(struct pannel *pannel)
{
    struct pannel *p = (struct pannel *)calloc(1, sizeof(struct pannel));
    struct node *w = (struct node *)calloc(pannel->x * pannel->y, sizeof(struct node));
    struct node *world = pannel->world;
    char *s;

    if (!p || !w) {
        perror("copypannel");
        exit(0);
    }

    memcpy(p, pannel, sizeof(struct pannel));
    memcpy(w, world, pannel->x * pannel->y * sizeof(struct node));
    p->world = w;
    s = (char *)calloc(1, strlen(pannel->s) + 1);
    if (!s) {
        perror("copypannel");
        exit(0);
    }
    strcpy(s, pannel->s);
    p->s = s;

    s = (char *)calloc(1, strlen(pannel->s) + 1);
    if (!s) {
        perror("copypannel");
        exit(0);
    }
    strcpy(s, pannel->sorted);
    p->sorted = s;
    p->round++;
    p->prev = pannel;
    return p;
}

int isvisited(struct taskque *r, char *s)
{
    struct taskque *q = r;

    while (q) {
        if (!strcmp(q->pannel->s, s))
            return 1;
        q = q->next;
    }
    return 0;
}

int ending(int qnum, struct taskque *root, struct pannel *last)
{
    char *buf = (char *)calloc(1, last->round + 1);
    int pos = last->round - 1;
    struct pannel *p = last;
    char fname[80];
    FILE *handle;

    if (!buf) {
        perror("copypannel");
        exit(0);
    }

    while (p->prev) {
        *(buf + pos) = p->move;
        pos--;
        p = p->prev;
    }

    sprintf(fname, "result/q.%d", qnum);
    handle = fopen(fname, "w");
    fprintf(handle, "%s", buf);
    fclose(handle);
    fprintf(stderr, "done: %d, %s\n", qnum, buf);
    free(buf);

    pos = last->round;
    root->pannel->solved = 1;
    freeapannel(last);
    return pos;
}

int engine(int qnum, struct taskque *root, struct taskque *taskque, struct pannel *pannel)
{
    struct node *world = pannel->world;
    struct node *zero = findzero(pannel, world);

/*
    if (pannel->round > 30)
        root->pannel->solved = 1;
*/

    /* fprintf(stderr, "%5.5d, %2.2d\r", root->depth, pannel->round); */

    if (root->pannel->solved)
        return 0;

    if (root->depth > 80000)
        return 0;

    if (pannel->round > 50)
        goto exit;

    if (zero->canu) {
        struct pannel *u = copypannel(pannel);
        moveup(u);
        u->move = 'U';
        if (!strcmp(u->s, u->sorted)) {
            return ending(qnum, root, u);
        }
        if (!isvisited(root, u->s)) {
            root->depth++;
#if 0
            sorttask(taskque, u);
#endif
            if (u->md + u->round <= pannel->md + pannel->round)
                inserttask(taskque, u);
            else
                addtask(taskque, u);
        }
        else {
            freeapannel(u);
        }
    }

    if (zero->cand) {
        struct pannel *d = copypannel(pannel);
        movedown(d);
        d->move = 'D';
        if (!strcmp(d->s, d->sorted)) {
            return ending(qnum, root, d);
        }
        if (!isvisited(root, d->s)) {
            root->depth++;
#if 0
            sorttask(taskque, d);
#endif
            if (d->md + d->round <= pannel->md + pannel->round)
                inserttask(taskque, d);
            else
                addtask(taskque, d);
        }
        else {
            freeapannel(d);
        }
    }

    if (zero->canr) {
        struct pannel *r = copypannel(pannel);
        moveright(r);
        r->move = 'R';
        if (!strcmp(r->s, r->sorted)) {
            return ending(qnum, root, r);
        }
        if (!isvisited(root, r->s)) {
            root->depth++;
#if 0
            sorttask(taskque, r);
#endif
            if (r->md + r->round <= pannel->md + pannel->round)
                inserttask(taskque, r);
            else
                addtask(taskque, r);
        }
        else {
            freeapannel(r);
        }
    }

    if (zero->canl) {
        struct pannel *l = copypannel(pannel);
        moveleft(l);
        l->move = 'L';
        if (!strcmp(l->s, l->sorted)) {
            return ending(qnum, root, l);
        }
        if (!isvisited(root, l->s)) {
            root->depth++;
#if 0
            sorttask(taskque, l);
#endif
            if (l->md + l->round <= pannel->md + pannel->round)
                inserttask(taskque, l);
            else
                addtask(taskque, l);
        }
        else {
            freeapannel(l);
        }
    }

exit:
    if (!taskque->next)
        return 0;
    return engine(qnum, root, taskque->next, taskque->next->pannel);
}

int main(int argc, char *argv[])
{
    FILE *fquiz;
    struct pannel *p;
    struct node   *world;
    struct taskque *root;
    int i, mod, assigned;

    if (argc > 1) {
        sscanf(argv[1], "%d", &mod);
        sscanf(argv[2], "%d", &assigned);
    }

    fquiz = readglobal("slidepannel.txt");
    for (i=0 ; i<globals.N ; i++) {
        FILE *resultf;
        char fname[80];
        p = readapannel(fquiz);
        sprintf(fname, "result/q.%d", i);
        resultf = fopen(fname, "r");
        if (resultf) {
            fclose(resultf);
            continue;
        }
        if (argc > 1 && i%mod != assigned) {
            freeapannel(p);
            continue;
        }
#if 0
        if (p->x > 4 && p->y > 4) {
            freeapannel(p);
            continue;
        }
#endif
        p->sorted = presort(p->s);
        world = buildworld(p);
        root = addtask(NULL, p);
        fprintf(stderr, "%d, %s\n", i, p->s);
        engine(i, root, root, p);
        cleanup(root);
    }
    fclose(fquiz);
    return 0;
}