Last active
August 29, 2015 14:21
-
-
Save mnem/a977e3d430b23e4380bd to your computer and use it in GitHub Desktop.
Revisions
-
mnem revised this gist
May 19, 2015 . 1 changed file with 82 additions and 47 deletions.There are no files selected for viewing
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode charactersOriginal file line number Diff line number Diff line change @@ -7,7 +7,8 @@ // #include <iostream> #include <set> #include <vector> #include <stdio.h> union Board { @@ -25,21 +26,23 @@ union Board { 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 || @@ -50,15 +53,15 @@ inline bool prime(uint64_t 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; } @@ -72,7 +75,7 @@ static const Mutator down = {add<3>, swap<3>}; struct Operation { const Mutator mutator; const Position origin; }; static const Operation kValidOperations[] = { @@ -89,42 +92,74 @@ static const Operation kValidOperations[] = { {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; } -
May 18, 2015 .There are no files selected for viewing
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode charactersOriginal file line number Diff line number Diff line change @@ -0,0 +1,130 @@ // // 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 <tuple> #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 uint64_t (*AddNeighbour)(Board, uint64_t); typedef Board (*SwapNeighbour)(Board, uint64_t); inline uint64_t cell(Board b, uint64_t o) { return (b.all >> (o * 4)) & 0xf; } inline Board set_cell(Board b, uint64_t o, uint64_t v) { const int shift = (o * 4); const uint64_t mask = 0xf << shift; b.all = (b.all & ~mask) | ((v << shift) & mask); return b; } inline bool prime(uint64_t n) { return 2 == n || 3 == n || 5 == n || 7 == n || 11 == n || 13 == n || 17 == n; } template <int offset> uint64_t add(Board b, uint64_t o) { return cell(b, o) + cell(b, o + offset); } template <int offset> Board swap(Board b, uint64_t o) { const uint64_t tmp = cell(b, o); set_cell(b, o, cell(b, 0 + offset)); 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 uint64_t 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}, }; int main(int argc, const char * argv[]) { // insert code here... 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}; // printf("0x%llx\n", cell(target, 0)); // printf("0x%llx\n", cell(target, 1)); // printf("0x%llx\n", cell(target, 8)); printf("0x%llx\n", set_cell(target, 0, 10).all); printf("0x%llx\n", set_cell(target, 1, 10).all); printf("0x%llx\n", set_cell(target, 2, 10).all); printf("0x%llx\n", set_cell(target, 3, 10).all); printf("0x%llx\n", set_cell(target, 4, 10).all); printf("0x%llx\n", set_cell(target, 5, 10).all); printf("0x%llx\n", set_cell(target, 6, 10).all); printf("0x%llx\n", set_cell(target, 7, 10).all); printf("0x%llx\n", set_cell(target, 8, 10).all); Board foo = set_cell(target, 8, 10); // printf("0x%llx\n", target.all); // printf("0x%llx\n", test1.all); // printf("0x%llx\n", test2.all); // std::cout << sizeof(Board); return 0; }