foo.cpp

//
//  main.cpp
//  jpm-code-dojo-2015-05-cpp
//
//  Created by David Wagner on 18/05/2015.
//  Copyright (c) 2015 David Wagner. All rights reserved.
//

#include <iostream>
#include <set>
#include <vector>
#include <stdio.h>

union Board {
    struct {
        uint8_t _0:4;
        uint8_t _1:4;
        uint8_t _2:4;
        uint8_t _3:4;
        uint8_t _4:4;
        uint8_t _5:4;
        uint8_t _6:4;
        uint8_t _7:4;
        uint8_t _8:4;
    } cells;
    uint64_t all;
};

typedef int Position;
typedef char Cell;
typedef Cell (*AddNeighbour)(Board, Position);
typedef Board (*SwapNeighbour)(Board, Position);

inline Cell cell(Board b, Position o) {
    return (b.all >> (o * 4)) & 0xf;
}

inline Board set_cell(Board b, Position o, Cell v) {
    const auto shift = (o * 4);
    const auto mask = 0xfull << shift;
    b.all = (b.all & ~mask) | (((typeof(mask))v << shift) & mask);
    return b;
}

inline bool prime(Cell n) {
    return 2 == n ||
    3 == n ||
    5 == n ||
    7 == n ||
    11 == n ||
    13 == n ||
    17 == n;
}

template <int offset>
Cell add(Board b, Position o) {
    return cell(b, o) + cell(b, o + offset);
}

template <int offset>
Board swap(Board b, Position o) {
    const auto tmp = cell(b, o);
    b = set_cell(b, o, cell(b, o + offset));
    b = set_cell(b, o + offset, tmp);
    return b;
}

struct Mutator {
    const AddNeighbour add;
    const SwapNeighbour swap;
};

static const Mutator right = {add<1>, swap<1>};
static const Mutator down = {add<3>, swap<3>};

struct Operation {
    const Mutator mutator;
    const Position origin;
};

static const Operation kValidOperations[] = {
    {right, 0},
    {right, 1},
    {right, 3},
    {right, 4},
    {right, 6},
    {right, 7},
    {down, 0},
    {down, 1},
    {down, 2},
    {down, 3},
    {down, 4},
    {down, 5},
};
static const auto kNumValidOperations = (sizeof(kValidOperations) / sizeof(Operation));

const Board Target = {
    1,2,3,
    4,5,6,
    7,8,9};
const Board Test1 = {
    7,3,2,
    4,1,5,
    6,8,9};
const Board Test2 = {
    9,8,5,
    2,4,1,
    3,7,6};

int solve(Board b) {
    auto step = 0;
    auto visited = std::set<uint64_t>();
    
    visited.insert(b.all);
    
    if (visited.count(Target.all) != 0) {
        return step;
    }
    
    auto unvisited_permutations = [&visited](Board b) -> std::vector<Board> {
        auto p = std::vector<Board>();
        for (size_t i = 0; i < kNumValidOperations; i++) {
            auto op = kValidOperations[i];
            if (prime(op.mutator.add(b, op.origin))) {
                auto bb = op.mutator.swap(b, op.origin);
                if (visited.count(bb.all) == 0) {
                    p.push_back(bb);
                }
            }
        }
        return p;
    };
    
    auto mark_visited = [&visited](std::vector<Board> barr) {
        for (auto b : barr) {
            visited.insert(b.all);
        }
    };
    
    auto boards = unvisited_permutations(b);
    while (boards.size() > 0) {
        step++;
        mark_visited(boards);
        if (visited.count(Target.all)) {
            return step;
        }
        
        auto next = std::vector<Board>();
        for (auto b : boards) {
            auto unvisited = unvisited_permutations(b);
            next.insert(next.end(), unvisited.begin(), unvisited.end());
        }
        boards = next;
    }
    
    return -1;
}

int main(int argc, const char * argv[]) {
    std::cout << solve(Target) << std::endl;
    std::cout << solve(Test1) << std::endl;
    std::cout << solve(Test2) << std::endl;

    return 0;
}