#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <string.h>
#include <stdint.h>

typedef uint32_t uint;


#define ROWS 4
#define COLUMNS ROWS
#define SIZE (ROWS * COLUMNS)
#define BLANK_VALUE (SIZE - 1)

typedef uint Cost;
typedef uint64_t Board;

typedef struct {
    Board tiles;
    int blank;
} State;

typedef struct {
    State *ptr;
    uint length;
} StateArray;

typedef struct {
    State *ptr;
    uint length, capacity;
} StateVector;

typedef struct {
    State state;
    Cost cost;
} Move;

typedef struct {
    StateVector solution;
    bool solved;
    Cost f_limit;
} Solver;


Cost manhattan[SIZE][SIZE];


int abs(const int x) {
    return x >= 0 ? x : -x;
}


void StateVector_append(StateVector *self, const State *x) {
    if (self->length >= self->capacity) {
        if (self->capacity > 0)
            self->capacity *= 2;
        else
            self->capacity = 4;
        self->ptr = realloc(self->ptr, self->capacity * sizeof(State));
        if (self->ptr == NULL)
            exit(1);
    }
    self->ptr[self->length++] = *x;
}

StateArray StateVector_slice(StateVector *self) {
    return (StateArray){self->ptr, self->length};
}


int Board_get(const Board data, const size_t i) {
    return (data >> (i * 4)) & 0xFU;
}

void Board_set(Board *data, const size_t i, const size_t value) {
    (*data) &= ~(0xFULL << (i * 4));
    (*data) |= ((Board)value) << (i * 4);
}


Cost State_h(const State *self) {
    Cost cost = 0;
    for (int i = 0; i < SIZE; i++)
        if (i != self->blank)
            cost += manhattan[i][Board_get(self->tiles, i)];
    return cost;
}


bool State_is_goal(const State *self) {
    return self->tiles == 18364758544493064720ULL;
}


bool contains(const StateArray solution, const State *state) {
    for (int i = solution.length - 1; i >= 0; i--)
        if (solution.ptr[i].tiles == state->tiles)
            return true;
    return false;
}


uint State_successors(const State *self, const StateArray solution, Move moves[4]) {
    uint moves_len = 0;

   if ((self->blank + 1) % COLUMNS != 0) {
        State s = {self->tiles, self->blank + 1};
        Board_set(&s.tiles, self->blank, Board_get(self->tiles, self->blank + 1));
        Board_set(&s.tiles, self->blank + 1, BLANK_VALUE);
        if (!contains(solution, &s))
            moves[moves_len++] = (Move){s, 1U};
    }

    if ((self->blank - COLUMNS) >= 0) {
        State s = {self->tiles, self->blank - COLUMNS};
        Board_set(&s.tiles, self->blank, Board_get(self->tiles, self->blank - COLUMNS));
        Board_set(&s.tiles, self->blank - COLUMNS, BLANK_VALUE);
        if (!contains(solution, &s))
            moves[moves_len++] = (Move){s, 1U};
    }

    if (self->blank % COLUMNS != 0) {
        State s = {self->tiles, self->blank - 1};
        Board_set(&s.tiles, self->blank, Board_get(self->tiles, self->blank - 1));
        Board_set(&s.tiles, self->blank - 1, BLANK_VALUE);
        if (!contains(solution, &s))
            moves[moves_len++] = (Move){s, 1U};
    }

    if ((self->blank + COLUMNS) < SIZE) {
        State s = {self->tiles, self->blank + COLUMNS};
        Board_set(&s.tiles, self->blank, Board_get(self->tiles, self->blank + COLUMNS));
        Board_set(&s.tiles, self->blank + COLUMNS, BLANK_VALUE);
        if (!contains(solution, &s))
            moves[moves_len++] = (Move){s, 1U};
    }

    return moves_len;
}


void State_show(const State *self) {
    const char *horiz = "+----+----+----+----+";
    for (int r = 0; r < ROWS; r++) {
        puts(horiz);
        for (int c = 0; c < COLUMNS; c++) {
            const int t = Board_get(self->tiles, r * COLUMNS + c);
            if (t == BLANK_VALUE)
                printf("|    ");
            else
                printf("| %2d ", t);
        }
        printf("|\n");
    }
    puts(horiz);
    puts("");
}


#define Solver_inf UINT32_MAX

Cost Solver_dfs(Solver *self, const State *s, const Cost g) {
    const Cost f1 = g + State_h(s);
    if (f1 > self->f_limit)
        return f1;
    StateVector_append(&self->solution, s);
    if (State_is_goal(s)) {
        self->solved = true;
        return f1;
    }
    Cost f_min = Solver_inf;

    Move moves[4];
    const uint moves_len = State_successors(s, StateVector_slice(&self->solution), moves);

    for (int i = 0; i < moves_len; i++) {
        const Cost f2 = Solver_dfs(self, &moves[i].state, g + moves[i].cost);
        if (self->solved)
            return f2;
        if (f2 < f_min)
            f_min = f2;
    }
    self->solution.length--;
    return f_min;
}

StateArray IDA_star_solve(const State s) {
    Solver solver;
    solver.solution.ptr = NULL;
    solver.solution.length = 0;
    solver.solution.capacity = 0;
    solver.solved = false;
    solver.f_limit = State_h(&s);

    while (!solver.solved && solver.f_limit < Solver_inf)
        solver.f_limit = Solver_dfs(&solver, &s, 0);
    return StateVector_slice(&solver.solution);
}


int main(int argc, char** argv) {
    for (int r = 0; r < SIZE; r++)
        for (int c = 0; c < SIZE; c++)
            manhattan[r][c] = abs(r / COLUMNS - c / COLUMNS) +
                              abs(r % COLUMNS - c % COLUMNS);

    const char *input = (argc == 2) ? argv[1] : "0FD1C3B648952A7E";
    Board tiles = 0;
    for (int i = 0; i < strlen(input); i++) {
        const char c = input[i];
        if (c >= '0' && c <= '9')
            Board_set(&tiles, i, c - '0');
        else if (c >= 'A' && c <= 'F')
            Board_set(&tiles, i, c - 'A' + 10);
        else if (c >= 'a' && c <= 'f')
            Board_set(&tiles, i, c - 'a' + 10);
        else
            exit(1);
    }

    int blank = 0;
    for (int i = 0; i < SIZE; i++)
        if (Board_get(tiles, i) == BLANK_VALUE) {
            blank = i;
            break;
        }

    const StateArray path = IDA_star_solve((State){tiles, blank});

    if (path.length == 0) {
        puts("No solutions found.");
    } else {
        printf("Solution in %u moves.\n\n", path.length - 1);
        for (int i = 0; i < path.length; i++)
            State_show(&path.ptr[i]);
    }

    return 0;
}