Skip to content

Instantly share code, notes, and snippets.

@vhqtvn
Created September 28, 2015 02:48
Show Gist options
  • Save vhqtvn/288acbdf1ceebeceacf9 to your computer and use it in GitHub Desktop.
Save vhqtvn/288acbdf1ceebeceacf9 to your computer and use it in GitHub Desktop.
#include<iostream>
#include<algorithm>
#include<string>
#include<set>
#include<map>
#include<queue>
using namespace std;
typedef __uint128_t uint128_t;
typedef pair<uint128_t, int > state_t;
template<typename T>
inline T sw(T x, int a, int b){
T _a = ((x>>(4*a))&0xF);
T _b = ((x>>(4*b))&0xF);
return x-((_a)<<(4*a))-((_b)<<(4*b))+((_a)<<(4*b))+((_b)<<(4*a));
}
string solve(int len){
char ms[100]="", mse[100]="";
map<state_t, pair<int,int> > prev;
map<state_t, pair<int,int> > next;
queue<state_t> Q, QBack;
vector<vector<int> > adj;
for(int i=0;i<len;i++){
adj.push_back(vector<int>());
if(i>0) adj[i].push_back(len+i-1);
adj[i].push_back(len+i);
if(i<len-1) adj[i].push_back(len+i+1);
}
for(int i=0;i<len;i++){
adj.push_back(vector<int>());
if(i>0) adj[len+i].push_back(i-1);
adj[len+i].push_back(i);
if(i<len-1) adj[len+i].push_back(i+1);
}
uint128_t initial = 0;
for(uint128_t i=0;i<len*2;i++) initial |= i<<(i*4);
uint128_t target = sw(initial,0,len*2-1);
prev[make_pair(initial,len*2-1)]=make_pair(-1,0);
next[make_pair(target, 0)]=make_pair(-1,0);
Q.push(make_pair(initial,2*len-1));
QBack.push(make_pair(target, 0));
bool found=false;
state_t x_state;
int lastQ = -1;
int lastQBack = -1;
//first stage: find minimum move
while((Q.size()>0 || QBack.size()>0) && !found){
while(Q.size()>0 && !found){
state_t sn = Q.front();
int qlen = prev[sn].second;
if(qlen>lastQ) {lastQ++;break;}
Q.pop();
uint128_t s = sn.first;
int c = sn.second;
for(int j=0, je=adj[c].size();j<je;j++){
int c2 = adj[c][j];
uint128_t s2 = sw(s,c,c2);
state_t new_state = make_pair(s2, c2);
if(prev.find(new_state)==prev.end()){
prev[new_state]=make_pair(c,qlen+1);
Q.push(new_state);
if(next.find(new_state)!=next.end()){
if(!found) x_state = new_state;found=true;
}
}
}
lastQ = qlen;
}
while(!found && QBack.size()>0){
state_t sn = QBack.front();
int qlen = next[sn].second;
if(qlen>lastQBack) {lastQBack++;break;}
QBack.pop();
uint128_t s = sn.first;
int c = sn.second;
for(int j=0, je=adj[c].size();j<je;j++){
int c2 = adj[c][j];
uint128_t s2 = sw(s,c,c2);
state_t new_state = make_pair(s2, c2);
if(next.find(new_state)==next.end()){
next[new_state]=make_pair(c,qlen+1);
QBack.push(new_state);
}
}
lastQBack = qlen;
}
}
string sol = "";
//second, find the rest moves
if(found){
found = false;
Q=queue<state_t>();
Q.push(x_state);
while(Q.size()>0 && !found){
state_t sn = Q.front();
int qlen = prev[sn].second;
Q.pop();
uint128_t s = sn.first;
int c = sn.second;
for(int j=0, je=adj[c].size();j<je;j++){
int c2 = adj[c][j];
uint128_t s2 = sw(s,c,c2);
state_t new_state = make_pair(s2, c2);
if(prev.find(new_state)==prev.end()){
prev[new_state]=make_pair(c,qlen+1);
Q.push(new_state);
if(s2 == target){
x_state = new_state;found=true;break;
}
}
}
}
if(found){
int mov = x_state.second;
uint128_t state = x_state.first;
while(mov>=0){
sol.push_back('A'+mov);
int new_mov = prev[make_pair(state, mov)].first;
state = sw(state,mov,new_mov);
mov=new_mov;
}
reverse(sol.begin(),sol.end());
sol = sol.substr(1);
} else sol="Uknown2";
} else sol="Unknow1";
return sol;
}
int main(int argc, char *argv[]) {
for(int i=3;i<=8;i++)
cout<<i<<" : TMCTF{"<<solve(i)<<"}"<<endl;
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment