leetcode

commit d16a95b5a7fcc0f39540c993a3b89728d97919be
parent 4faa838ae100c53005b7e71f98cd7157e2d458b0
Author: Dimitrije Dobrota <mail@dimitrijedobrota.com>
Date:   Mon, 25 Nov 2024 21:13:52 +0100

Daily Problem

Diffstat:
A
Problems/0773.cpp
 | 
51
+++++++++++++++++++++++++++++++++++++++++++++++++++
M
README.md
 | 
1
+

2 files changed, 52 insertions(+), 0 deletions(-)
diff --git a/Problems/0773.cpp b/Problems/0773.cpp
@@ -0,0 +1,51 @@
+class Solution {
+    using type_t = pair<uint32_t, uint32_t>;
+
+    static type_t encode(const vector<vector<int>> &board) {
+        uint32_t n2p = 0; // number to position
+        uint32_t p2n = 0; // position to number
+
+        for (int i = 0; i < 2; i++) {
+            for (int j = 0; j < 3; j++) {
+                const int idx = i * 3 + j;
+                n2p |= idx << (board[i][j] * 3);
+                p2n |= board[i][j] << (idx * 3);
+            }
+        }
+
+        return {n2p, p2n};
+    }
+
+  public:
+    int slidingPuzzle(const vector<vector<int>> &board) const {
+        static const vector<vector<int>> adj = {{1, 3}, {0, 2, 4}, {1, 5}, {0, 4}, {1, 3, 5}, {2, 4}};
+
+        unordered_set<uint32_t> seen;
+        queue<type_t> q;
+
+        q.push(encode(board));
+        for (int lvl = 0; !q.empty(); lvl++) {
+            for (int k = size(q); k > 0; k--) {
+                const auto [n2p, p2n] = q.front();
+                q.pop();
+
+                if (n2p == 0x23445) return lvl;
+
+                const auto p = n2p & 0x7;                    // position of zero
+                for (const auto sp : adj[p]) {               // position to swap
+                    const auto sn = (p2n >> (sp * 3)) & 0x7; // number to swap
+
+                    const auto sn2p = (n2p & ~((0x7 << (sn * 3)) | (0x7 << (0 * 0)))) | (p << (sn * 3)) | sp;
+                    const auto sp2n = (p2n & ~((0x7 << (sp * 3)) | (0x7 << (p * 3)))) | (sn << (p * 3));
+
+                    if (!seen.count(sn2p)) {
+                        q.emplace(sn2p, sp2n);
+                        seen.insert(sn2p);
+                    }
+                }
+            }
+        }
+
+        return -1;
+    }
+};
diff --git a/README.md b/README.md
@@ -569,6 +569,7 @@ reference and a base for solving problems.
 |  0763  |   Medium   | [Partition Labels](Problems/0763.cpp)                                                              |
 |  0767  |   Medium   | [Reorganize String](Problems/0767.cpp)                                                             |
 |  0769  |   Medium   | [Max Chunks To Make Sorted](Problems/0769.cpp)                                                     |
+|  0773  |    Hard    | [Sliding Puzzle](Problems/0773.cpp)                                                                |
 |  0779  |   Medium   | [K-th Symbol in Grammar](Problems/0779.cpp)                                                        |
 |  0781  |   Medium   | [Rabbits in Forest](Problems/0781.cpp)                                                             |
 |  0783  |    Easy    | [Minimum Distance Between BST Nodes](Problems/0783.cpp)                                            |