fork(6) download
copy 
  1. // #include <boost/functional/hash/hash.hpp>
  2.  
  3. #include <deque>
  4. #include <functional>
  5. #include <type_traits>
  6. #include <unordered_set>
  7. #include <vector>
  8.  
  9. #include <assert.h>
  10. #include <stddef.h>
  11. #include <stdio.h>
  12. #include <string.h>
  13. #include <strings.h>
  14.  
  15. int board[5][4] = {
  16. //  0  1  2  3
  17.   { 1, 2, 2, 3, },   // 0
  18.   { 1, 2, 2, 3, },   // 1
  19.   { 4, 5, 5, 6, },   // 2
  20.   { 4, 7, 8, 6, },   // 3
  21.   { 9, 0, 0, 10 } }; // 4
  22.  
  23. struct Mask;
  24.  
  25. const int kRows = 5;
  26. const int kColumns = 4;
  27. const int kBlocks = 10;
  28.  
  29. enum class Shape // : int8_t
  30. {
  31.   kInvalid,
  32.   kSingle,
  33.   kHorizon,
  34.   kVertical,
  35.   kSquare,
  36. };
  37.  
  38. struct Block
  39. {
  40.   Shape shape;
  41.   int left, top;  // int8_t
  42.  
  43.   Block()
  44.     : shape(Shape::kInvalid),
  45.       left(-1),
  46.       top(-1)
  47.   {
  48.   }
  49.  
  50.   Block(Shape s, int left, int top)
  51.     : shape(s),
  52.       left(left),
  53.       top(top)
  54.   {
  55.     assert(shape != Shape::kInvalid);
  56.     assert(left >= 0 && left < kColumns);
  57.     assert(top >= 0 && top < kRows);
  58.   }
  59.  
  60.   int bottom() const
  61.   {
  62.     const static int delta[] = { 0, 0, 0, 1, 1, };
  63.     assert(shape != Shape::kInvalid);
  64.     return top + delta[static_cast<int>(shape)];
  65.   }
  66.  
  67.   int right() const
  68.   {
  69.     const static int delta[] = { 0, 0, 1, 0, 1, };
  70.     assert(shape != Shape::kInvalid);
  71.     return left + delta[static_cast<int>(shape)];
  72.   }
  73.  
  74.   void mask(int8_t value, Mask* mask) const;
  75. };
  76.  
  77. struct Mask
  78. {
  79.   Mask()
  80.   {
  81.     bzero(board_, sizeof(board_));
  82.   }
  83.  
  84.   bool operator==(const Mask& rhs) const
  85.   {
  86.     return memcmp(board_, rhs.board_, sizeof board_) == 0;
  87.   }
  88.  
  89.   size_t hashValue() const
  90.   {
  91.     const int8_t* begin = board_[0];
  92.     // return boost::hash_range(begin, begin + sizeof(board_));
  93.     size_t ret = 0;
  94.     for (; begin != board_[0] + sizeof(board_); ++begin)
  95.       ret = 31*ret + *begin;
  96.     return ret;
  97.   }
  98.  
  99.   void print() const
  100.   {
  101.     for (int i = 0; i < kRows; ++i)
  102.     {
  103.       for (int j = 0; j < kColumns; ++j)
  104.       {
  105.         printf(" %c", board_[i][j] + '0');
  106.       }
  107.       printf("\n");
  108.     }
  109.   }
  110.  
  111.   void set(int8_t value, int y, int x)
  112.   {
  113.     assert(value > 0);
  114.     assert(x >= 0 && x < kColumns);
  115.     assert(y >= 0 && y < kRows);
  116.     assert(board_[y][x] == 0);
  117.     board_[y][x] = value;
  118.   }
  119.  
  120.   bool empty(int y, int x) const
  121.   {
  122.     assert(x >= 0 && x < kColumns);
  123.     assert(y >= 0 && y < kRows);
  124.     return board_[y][x] == 0;
  125.   }
  126.  
  127.  private:
  128.   int8_t board_[kRows][kColumns];
  129. };
  130.  
  131. namespace std
  132. {
  133.   template<> struct hash<Mask>
  134.   {
  135.     size_t operator()(const Mask& x) const
  136.     {
  137.       return x.hashValue();
  138.     }
  139.   };
  140. }
  141.  
  142. inline void Block::mask(int8_t value, Mask* mask) const
  143. {
  144.   mask->set(value, top, left);
  145.   switch (shape)
  146.   {
  147.     case Shape::kHorizon:
  148.       mask->set(value, top, left+1);
  149.       break;
  150.     case Shape::kVertical:
  151.       mask->set(value, top+1, left);
  152.       break;
  153.     case Shape::kSquare:
  154.       mask->set(value, top, left+1);
  155.       mask->set(value, top+1, left);
  156.       mask->set(value, top+1, left+1);
  157.       break;
  158.     default:
  159.       assert(shape == Shape::kSingle);
  160.       ;
  161.   }
  162. }
  163.  
  164. struct State
  165. {
  166.   Mask toMask() const
  167.   {
  168.     Mask m;
  169.     for (int i = 0; i < kBlocks; ++i)
  170.     {
  171.       Block b = blocks_[i];
  172.       b.mask(static_cast<int>(b.shape), &m);
  173.     }
  174.     return m;
  175.   }
  176.  
  177.   bool isSolved() const
  178.   {
  179.     // FIXME: magic number
  180.     Block square = blocks_[1];
  181.     assert(square.shape == Shape::kSquare);
  182.     return (square.left == 1 && square.top == 3);
  183.   }
  184.  
  185.   template<typename FUNC>
  186.   void move(const FUNC& func) const
  187.   {
  188.     static_assert(std::is_convertible<FUNC, std::function<void(const State&)>>::value,
  189.                   "func must be callable with a 'const State&' parameter.");
  190.     const Mask mask = toMask();
  191.  
  192.     for (int i = 0; i < kBlocks; ++i)
  193.     {
  194.       Block b = blocks_[i];
  195.       if (b.top > 0 && mask.empty(b.top-1, b.left))
  196.       {
  197.         bool moveUp = false;
  198.         if (b.shape == Shape::kHorizon || b.shape == Shape::kSquare)
  199.         {
  200.           if (mask.empty(b.top-1, b.left+1))
  201.             moveUp = true;
  202.         }
  203.         else
  204.           moveUp = true;
  205.         if (moveUp)
  206.         {
  207.           State next = *this;
  208.           next.step++;
  209.           next.blocks_[i].top--;
  210.           func(next);
  211.         }
  212.       }
  213.  
  214.       if (b.bottom() < kRows-1 && mask.empty(b.bottom()+1, b.left))
  215.       {
  216.         bool moveDown = false;
  217.         if (b.shape == Shape::kHorizon || b.shape == Shape::kSquare)
  218.         {
  219.           if (mask.empty(b.bottom()+1, b.left+1))
  220.             moveDown = true;
  221.         }
  222.         else
  223.           moveDown = true;
  224.         if (moveDown)
  225.         {
  226.           State next = *this;
  227.           next.step++;
  228.           next.blocks_[i].top++;
  229.           func(next);
  230.         }
  231.       }
  232.  
  233.       if (b.left > 0 && mask.empty(b.top, b.left-1))
  234.       {
  235.         bool moveLeft = false;
  236.         if (b.shape == Shape::kVertical || b.shape == Shape::kSquare)
  237.         {
  238.           if (mask.empty(b.top+1, b.left-1))
  239.             moveLeft = true;
  240.         }
  241.         else
  242.           moveLeft = true;
  243.         if (moveLeft)
  244.         {
  245.           State next = *this;
  246.           next.step++;
  247.           next.blocks_[i].left--;
  248.           func(next);
  249.         }
  250.       }
  251.  
  252.       if (b.right() < kColumns-1 && mask.empty(b.top, b.right()+1))
  253.       {
  254.         bool moveRight = false;
  255.         if (b.shape == Shape::kVertical || b.shape == Shape::kSquare)
  256.         {
  257.           if (mask.empty(b.top+1, b.right()+1))
  258.             moveRight = true;
  259.         }
  260.         else
  261.           moveRight = true;
  262.         if (moveRight)
  263.         {
  264.           State next = *this;
  265.           next.step++;
  266.           next.blocks_[i].left++;
  267.           func(next);
  268.         }
  269.       }
  270.     }
  271.   }
  272.  
  273.   // std::vector<State> moves() const;
  274.  
  275.   Block blocks_[kBlocks];
  276.   int step = 0;
  277. };
  278.  
  279. int main()
  280. {
  281.   printf("sizeof(Mask) = %zd, sizeof(State) = %zd\n", sizeof(Mask), sizeof(State));
  282.   std::unordered_set<Mask> seen;
  283.   std::deque<State> queue;
  284.  
  285.   State initial;
  286.   initial.blocks_[0] = Block(Shape::kVertical, 0, 0);
  287.   initial.blocks_[1] = Block(Shape::kSquare,   1, 0);
  288.   initial.blocks_[2] = Block(Shape::kVertical, 3, 0);
  289.   initial.blocks_[3] = Block(Shape::kVertical, 0, 2);
  290.   initial.blocks_[4] = Block(Shape::kHorizon,  1, 2);
  291.   initial.blocks_[5] = Block(Shape::kVertical, 3, 2);
  292.   initial.blocks_[6] = Block(Shape::kSingle, 1, 3);
  293.   initial.blocks_[7] = Block(Shape::kSingle, 2, 3);
  294.   initial.blocks_[8] = Block(Shape::kSingle, 0, 4);
  295.   initial.blocks_[9] = Block(Shape::kSingle, 3, 4);
  296.  
  297.   queue.push_back(initial);
  298.   seen.insert(initial.toMask());
  299.  
  300.   while (!queue.empty())
  301.   {
  302.     const State curr = queue.front();
  303.     queue.pop_front();
  304.  
  305.     if (curr.isSolved())
  306.     {
  307.       printf("found solution with %d steps\n", curr.step);
  308.       break;
  309.     }
  310.     else if (curr.step > 200)
  311.     {
  312.       printf("too many steps.\n");
  313.       break;
  314.     }
  315.  
  316.     curr.move([&seen, &queue](const State& next) {
  317.       auto result = seen.insert(next.toMask());
  318.       if (result.second)
  319.         queue.push_back(next);
  320.     });
  321.  
  322.     // for (const State& next : curr.moves())
  323.     // {
  324.     //   auto result = seen.insert(next.toMask());
  325.     //   if (result.second)
  326.     //     queue.push_back(next);
  327.     // }
  328.   }
  329. }
  330.  
Success #stdin #stdout 0.03s 3436KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
sizeof(Mask) = 20, sizeof(State) = 124
found solution with 116 steps
https://ideone.com/GoQAtw
language:
C++14 (gcc 8.3)
created:
10 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!