[Hacker Rank] Gena Playing Hanoi

Gena Playing Hanoi

  • Time : O(n * 2^n)
  • Space : O(2^n)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
int hashOf(vector<int>& A) {
int hash = 0;
for(int i = 0; i < A.size(); i++) {
hash += A[i] << (2 * i);
}
return hash;
}

int hanoi(vector<int> posts) {
int res = 0;
while(!posts.empty() and posts.back() == 1) posts.pop_back();
if(posts.empty()) return 0;
unordered_set<long long> us;
queue<vector<int>> q;
q.push(posts);
us.insert(hashOf(posts));
while(!q.empty()) {
int sz = q.size();
while(sz--) {
auto A = q.front(); q.pop();
int mask = 0, n = A.size();
for(int i = 0; i < n and __builtin_popcount(mask) < 3; i++) {
if(mask & (1<< A[i])) continue;
mask |= (1 << A[i]);
for(int j = 1; j <= 4; j++) {
if(mask & (1<<j)) continue;
if(i == n - 1 and j == 1) {
A.pop_back();
if(A.empty()) return res + 1;
int hash = hashOf(A);
if(!us.count(hash)) {
us.insert(hash);
q.push(A);
}
break;
}
int o = A[i];
A[i] = j;
int hash = hashOf(A);
if(!us.count(hash)) {
us.insert(hash);
q.push(A);
}

A[i] = o;
}
}
}
res++;
}
return -1;
}
Author: Song Hayoung
Link: https://songhayoung.github.io/2022/06/07/PS/HackerRank/gena/
Copyright Notice: All articles in this blog are licensed under CC BY-NC-SA 4.0 unless stating additionally.