#include "robot.h"
#include <algorithm>
#include <iostream>
#include <numeric>
#include <cassert>
#include <vector>
#include <set>
typedef long long llong;
const int MAXN = 20;
const int Z_MAX = 7;
struct State
{
bool isDone;
bool haventPassed;
bool traversedThrough;
bool isOutside;
bool isCross;
int dep;
State()
{
isDone = traversedThrough = haventPassed = dep = isOutside = isCross = 0;
}
int getNUM()
{
if (isDone) return 1;
if (isOutside) return -2;
if (isCross) return -1;
if (haventPassed) return 0;
return 3 * (int)(traversedThrough) + dep + 2; // zMAX == 7
}
void setState(int num)
{
isDone = traversedThrough = haventPassed = dep = isOutside = isCross = 0;
if (num == -2)
{
isOutside = 1;
return;
}
if (num == -1)
{
isCross = 1;
return;
}
if (num == 0)
{
haventPassed = 1;
return;
}
if (num == 1)
{
isDone = 1;
return;
}
assert(num <= 7);
if (num > 4)
{
traversedThrough = 1;
dep = num - 5;
return;
}
dep = num - 2;
}
};
State state[5];
std::vector <int> nums;
bool isNeighboor[5];
char getDirection[4] = {'W', 'S', 'E', 'N'};
char getOpposite[4] = {'E', 'N', 'W', 'S'};
void rec(int idx)
{
if (idx == 5)
{
if (state[0].isCross || state[0].isOutside || state[0].isDone)
{
return;
}
bool amIdone = false;
for (int i = 1 ; i <= 4 ; ++i)
{
if (state[i].isDone)
{
amIdone = true;
break;
}
}
if (amIdone)
{
char parent = 'T';
for (int i = 1 ; i <= 4 ; ++i)
{
if (state[i].isCross || state[i].isOutside || state[i].traversedThrough || state[i].haventPassed || state[i].isDone)
{
continue;
}
if (state[i].dep != (state[0].dep + 1) % 3)
{
parent = getDirection[i - 1];
break;
}
}
if (parent == 'T' && !(state[1].isOutside && state[4].isOutside))
{
return;
}
State newState = state[0];
newState.isDone = 1;
set_instruction(nums, newState.getNUM(), parent);
return;
}
if (state[0].haventPassed)
{
if (state[1].isOutside && state[4].isOutside)
{
State newState = state[0];
newState.haventPassed = 0;
newState.dep = 0;
set_instruction(nums, newState.getNUM(), 'H');
return;
}
bool is[3] = {0, 0, 0};
for (int i = 1 ; i <= 4 ; ++i)
{
if (!state[i].haventPassed && !state[i].isCross && !state[i].isOutside)
{
is[state[i].dep] = 1;
}
}
int cntAre = 0;
cntAre += is[0];
cntAre += is[1];
cntAre += is[2];
if (cntAre == 0 || cntAre == 3)
{
return;
}
int parDep = -1;
int myDep = -1;
if (cntAre == 1)
{
if (is[0])
{
parDep = 0;
myDep = 1;
} else if (is[1])
{
parDep = 1;
myDep = 2;
} else
{
parDep = 2;
myDep = 0;
}
} else
{
if (is[0] && is[1])
{
parDep = 0;
myDep = 1;
} else if (is[0] && is[2])
{
parDep = 2;
myDep = 0;
} else if (is[1] && is[2])
{
parDep = 1;
myDep = 2;
}
}
int countCandidates = 0;
for (int i = 1 ; i <= 4 ; ++i)
{
if (!state[i].haventPassed && !state[i].isCross && !state[i].isOutside && state[i].dep == parDep)
{
countCandidates++;
}
}
assert(countCandidates);
if (countCandidates == 1)
{
for (int i = 1 ; i <= 4 ; ++i)
{
if (!state[i].haventPassed && !state[i].isCross && !state[i].isOutside && state[i].dep == parDep)
{
State newState;
newState.traversedThrough = 1;
newState.dep = myDep;
if (state[2].isOutside && state[3].isOutside)
{
newState.isDone = 1;
}
set_instruction(nums, newState.getNUM(), getDirection[i - 1]);
return;
}
}
assert(false);
} else
{
for (int i = 1 ; i <= 4 ; ++i)
{
if (!state[i].haventPassed && !state[i].isCross && !state[i].isOutside && state[i].dep == parDep && state[i].traversedThrough)
{
State newState;
newState.traversedThrough = 1;
newState.dep = myDep;
if (state[2].isOutside && state[3].isOutside)
{
newState.isDone = 1;
}
set_instruction(nums, newState.getNUM(), getDirection[i - 1]);
return;
}
}
return;
assert(false);
}
}
if (!state[0].traversedThrough)
{
char parent = 'H';
for (int i = 1 ; i <= 4 ; ++i)
{
if (state[i].isCross || state[i].isOutside || state[i].traversedThrough)
{
continue;
}
if (state[i].haventPassed)
{
State newState = state[0];
if (!(state[1].isOutside && state[4].isOutside))
{
newState.traversedThrough = 1;
}
set_instruction(nums, newState.getNUM(), getDirection[i - 1]);
return;
}
if (state[i].dep != (state[0].dep + 1) % 3)
{
parent = getDirection[i - 1];
} else
{
set_instruction(nums, state[0].getNUM(), getDirection[i - 1]);
return;
}
}
if (parent == 'H' && !(state[1].isOutside && state[4].isOutside))
{
return;
}
State newState = state[0];
newState.traversedThrough = 1;
set_instruction(nums, newState.getNUM(), parent);
return;
}
if (!(state[1].isOutside && state[4].isOutside))
{
bool isParentTraversed = false;
for (int i = 1 ; i <= 4 ; ++i)
{
if (state[i].isCross || state[i].isOutside || state[i].haventPassed)
{
continue;
}
if (state[i].dep != (state[0].dep + 1) % 3)
{
isParentTraversed = state[i].traversedThrough;
break;
}
}
if (!isParentTraversed)
{
State newState = state[0];
newState.traversedThrough = 0;
set_instruction(nums, newState.getNUM(), 'H');
return;
}
}
char parent = 'H';
for (int i = 1 ; i <= 4 ; ++i)
{
if (state[i].isCross || state[i].isOutside || !state[i].traversedThrough)
{
continue;
}
if (state[i].haventPassed)
{
return;
}
if (state[i].dep != (state[0].dep + 1) % 3)
{
parent = getDirection[i - 1];
} else
{
set_instruction(nums, state[0].getNUM(), getDirection[i - 1]);
return;
}
}
if (parent == 'H' && !(state[1].isOutside && state[4].isOutside))
{
return;
}
State newState = state[0];
newState.traversedThrough = 0;
set_instruction(nums, newState.getNUM(), parent);
return;
}
for (int curr = -2 ; curr <= Z_MAX ; ++curr)
{
state[idx].setState(curr);
nums[idx] = curr;
rec(idx + 1);
}
}
void program_pulibot()
{
nums.resize(5);
rec(0);
}
