#include "robot.h"
#include <bits/stdc++.h>
using namespace std;
/*
boundary: state = -2
obstacle: state = -1
otherwise: state = colour
n = up, s = down, w = left, e = right
S[0] is the state of cell (r, c).
S[1] is the state of the cell to the west.
S[2] is the state of the cell to the south.
S[3] is the state of the cell to the east.
S[4] is the state of the cell to the north.
*/
set<string> instr;
void instruction(vector<int> S, int Z, char A, bool ignore_duplicate = false) {
string val = "";
for (auto &el : S) val += to_string(el);
if (instr.count(val) && !ignore_duplicate) {
// cout << "Duplicate with: \n";
// cout << val << "\n";
} else {
if (!instr.count(val)) set_instruction(S, Z, A);
instr.insert(val);
}
}
void solve_empty() {
// if its entirely empty: go right while not a border on the right, then go up
// if
instruction({0, -2, 0, 0, -2}, 1, 'E'); // at (0, 0): go right
instruction({0, 1, 0, 0, -2}, 1, 'E'); // travelling along bottom: go right
instruction({0, 1, 0, -2, -2}, 1, 'S'); // at (W, 0): go down
instruction({0, 0, 0, -2, 1}, 1, 'S'); // travelling along side: go down
instruction({0, 0, -2, -2, 1}, 1, 'T'); // at (W, H): terminate
}
void solve_h2() {
// while possible, walk right
// if not possible, go down/up
// if at (W, H-1), go up
// go right while possible
for (auto &west_state : {-2, -1, 0, 1}) {
for (auto &south_state : {-2, -1, 0, 1}) {
for (auto &north_state : {-2, -1, 0, 1}) {
instruction({0, west_state, south_state, 0, north_state}, 1, 'E');
}
}
}
// go down when needed
for (auto &east_state : {-2, -1}) {
for (auto &west_state : {-2, 1}) {
instruction({0, west_state, 0, east_state, -2}, 1, 'S');
}
}
// go up when needed
for (auto &east_state : {-1}) {
for (auto &west_state : {-2, 1}) {
instruction({0, west_state, -2, east_state, 0}, 1, 'N');
}
}
// at end
for (auto &west_state : {-2, -1, 0, 1}) {
for (auto &north_state : {-1, 0, 1}) {
instruction({0, west_state, -2, -2, north_state}, 1, 'T');
}
}
}
const char DIR[5] = {'H', 'W', 'S', 'E', 'N'};
const int PERM[24][4] = {
{1, 2, 3, 4}, {1, 2, 4, 3}, {1, 3, 2, 4}, {1, 3, 4, 2}, {1, 4, 2, 3}, {1, 4, 3, 2},
{2, 1, 3, 4}, {2, 1, 4, 3}, {2, 3, 1, 4}, {2, 3, 4, 1}, {2, 4, 1, 3}, {2, 4, 3, 1},
{3, 1, 2, 4}, {3, 1, 4, 2}, {3, 2, 1, 4}, {3, 2, 4, 1}, {3, 4, 1, 2}, {3, 4, 2, 1},
{4, 1, 2, 3}, {4, 1, 3, 2}, {4, 2, 1, 3}, {4, 2, 3, 1}, {4, 3, 1, 2}, {4, 3, 2, 1}
};
#define wall(x) for (auto &x : {-2, -1})
#define wall_or_empty(x) for (auto &x : {-1, 0, 4})
#define wempty(x) for (auto &x : {-1, 0})
#define EBX(x) for (auto &x : {0, -1, -2, 4})
#define any(x) for (auto &x : {-2, -1, 0, 1, 2, 3, 4, 5})
#define empty_blue(x) for (auto &x : {0, 1})
#define bygo(x) for (auto &x : {1, 2, 3, 4, 5})
#define yg(x) for (auto &x : {1, 2})
#define ygo(x) for (auto &x : {2,3,4, 5})
#define RE(x) for (auto &x : {0, 4})
#define rwall(x) for (auto &x : {-1, -2, 4})
#define ewall(x) for (auto &x : {-1, -2, 0})
void rotate(vector<int> S, int Z, int C) {
set<string> seen;
for (auto &perm : PERM) {
vector<int> ins(5);
ins[0] = S[0];
ins[perm[0]] = S[1];
ins[perm[1]] = S[2];
ins[perm[2]] = S[3];
ins[perm[3]] = S[4];
char dir;
if (C == 0) dir = 'T';
else if (C == 5) dir = 'H';
else dir = DIR[perm[C-1]];
string v = ""; for (auto &el : ins) v+=to_string(el);
if (seen.count(v)) continue;
seen.insert(v);
instruction(ins, Z, dir);
}
}
void corners() {
// (1) special cases for the corners
// (a) 0, 0
instruction({0, -2, -1, 0, -2}, 1, 'E'); // only right
instruction({0, -2, 0, -1, -2}, 1, 'S'); // only down
instruction({0, -2, 0, 0, -2}, 2, 'E'); // both options, go right
instruction({2, -2, 0, 0, -2}, 1, 'S'); // option 1 bad, go down
instruction({2, -2, 0, 1, -2}, 1, 'T'); // option 1 good, make blue and terminate
instruction({2, -2, 1, 0, -2}, 1, 'T'); // option 2 good, make blue and terminate
// (b) (W, 0) or (0, W)
bygo(col) {
// keep the colour, going down or right
instruction({0, col, 0, -2, -2}, col, DIR[2]);
instruction({0, 0, col, -2, -2}, col, DIR[1]);
instruction({0, -2, -2, col, 0}, col, DIR[4]);
instruction({0, -2, -2, 0, col}, col, DIR[3]);
// reverse a yellow
// if (col == 1) continue;
// go in opposite direction if we have a blue
// instruction({3, col, 1, -2, -2}, 1, DIR[1]);
// instruction({3, 1, col, -2, -2}, 1, DIR[2]);
// instruction({3, -2, -2, col, 1}, 1, DIR[3]);
// instruction({3, -2, -2, 1, col}, 1, DIR[4]);
wall_or_empty(a) {
instruction({0, col, a, -2, -2}, 0, DIR[1]);
instruction({0, a, col, -2, -2}, 0, DIR[2]);
instruction({3, col, a, -2, -2}, 0, DIR[1]);
instruction({3, a, col, -2, -2}, 0, DIR[2]);
instruction({0, -2, -2, col, a}, 0, DIR[3]);
instruction({0, -2, -2, a, col}, 0, DIR[4]);
instruction({3, -2, -2, col, a}, 0, DIR[3]);
instruction({3, -2, -2, a, col}, 0, DIR[4]);
}
}
// (c) (W, H)
wall_or_empty(c) { // we can end
instruction({0, c, -2, -2, 1}, 1, 'T');
instruction({0, 1, -2, -2, c}, 1, 'T');
ygo(c2) { // need to go back
instruction({0, c, -2, -2, c2}, 1, DIR[4]);
instruction({0, c2, -2, -2, c}, 1, DIR[1]);
}
}
}
void forced_movements() {
// (2) we are carrying the previous colour with us to the only empty square we have
wall(a) {
rotate({0, a, -1, 0, 1}, 1, 3);
ygo(b) rotate({0, a, -1, 0, b}, 3, 3);
}
}
void clean_to_green() { // or orange
// (3) undoing a forward movement with yellow colour to clean it
wall(a) ygo(b) rotate({3, a, -1, b, 0}, 0, 3); // case 1: cleaning the yellow colour
wall(a) ygo(b) rotate({3, a, -1, b, 1}, 1, 3); // case 2: found the answer we're setting everything blue until we reach green/orange
}
void dead_ends() {
// (4) we hit a dead end in our search down a branch
wall(a) {
ygo(b) rotate({0, a, -1, -1, b}, 0, 4);
}
}
void blue2branch() {
// (5) our parent is blue, but we have 2 children
wall(a) rotate({0, a, 1, 0, 0}, 2, 4); // case 1: we just arrived, so set to green and go down child 1
wall(a) rotate({2, a, 1, 1, 0}, 1, 0); // case 2: we've come back from child 1 and child 1 is blue (we found the shortest path)
wall(a) rotate({2, a, 1, 0, 0}, 1, 3); // case 3: come back from child 1, and it doesnt lead to the answer
}
void blue3branch() {
// (6) our parent is blue, but we have 3 children
rotate({0, 1, 0, 0, 0}, 2, 4); // case 1: just arrived, go down first preference
rotate({2, 1, 1, 0, 0}, 1, 0); // case 2: first preference good, set to blue and terminate
rotate({2, 1, 0, 0, 0}, 4, 3); // case 3: first path was bad, going down second path
rotate({4, 1, 1, 0, 0}, 1, 0); // case 4: second path good, terminating
rotate({4, 1, 0, 0, 0}, 1, 2); // case 5: second path bad, going down third path
}
void yellow2branch() {
// (7) our parent is yellow/orange/green, but we have 2 children
ygo(p) {
wall(a) rotate({0, a, p, 0, 0}, 2, 4); // case 1: we just arrived, so set to green and go down child 1
wall(a) rotate({2, a, p, 1, 0}, 1, 2); // case 2: we've come back from child 1 and child 1 is blue (we found the shortest path)
wall(a) rotate({2, a, p, 0, 0}, 4, 3); // case 3: come back from child 1, and it doesnt lead to the answer, so set to orange and go down 2
wall(a) rotate({4, a, p, 1, 0}, 1, 2); // case 4: come back from child 2, and it is the answer
wall(a) rotate({4, a, p, 0, 0}, 0, 2); // case 5: come back from child 2, and it isnt the answer
}
}
void yellow3branch() {
// (8) our parent is yellow/green/orange, but we have 3 children
ygo(p) {
rotate({0, p, 0, 0, 0}, 2, 4); // case 1: just arrived, go down first preference
rotate({2, p, 1, 0, 0}, 1, 1); // case 2: first preference good, set to blue and go to parent
rotate({2, p, 0, 0, 0}, 4, 3); // case 3: first path was bad, going down second path
rotate({4, p, 1, 0, 0}, 1, 1); // case 4: second path good, terminating
rotate({4, p, 0, 0, 0}, 5, 2); // case 5: second path bad, going down third path
rotate({5, p, 1, 0, 0}, 1, 1); // case 6: third path good: set to blue and go to parent
rotate({5, p, 0, 0, 0}, 0, 1); // case 7: third path bad: set to empty and go to parent
}
}
void solve_one_path() {
// goal: simple cleaning routine (from root)
corners();
forced_movements();
clean_to_green();
dead_ends();
blue2branch();
blue3branch();
yellow2branch();
yellow3branch();
}
void rotate_half(vector<int> S, int Z, int C) {
set<string> seen;
for (auto &perm : PERM) {
if ((perm[2] != 3 && perm[2] != 4) || (perm[3] != 3 && perm[3] != 4)) continue;
vector<int> ins(5);
ins[0] = S[0];
ins[perm[0]] = S[1];
ins[perm[1]] = S[2];
ins[perm[2]] = S[3];
ins[perm[3]] = S[4];
char dir;
if (C == 0) dir = 'T';
else if (C == 5) dir = 'H';
else dir = DIR[perm[C-1]];
string v = ""; for (auto &el : ins) v+=to_string(el);
if (seen.count(v)) continue;
seen.insert(v);
instruction(ins, Z, dir);
}
}
// void lattice_dead() {
// // dead end in a lattice means south and east are both walls
// wall(a) rotate_half({})
// }
void solve_lattice() {
// predicated on knowing that if we find the end, and we only went right or down, we got a shortest path
// every cell is a potential branchpoint
/*
in essence:
(1) if cell empty, set to yellow and go right.
(2) if cell yellow,
(a) if right is blue, keep bringing the blue to the start
(b) if right is empty, set to green and go down
(3) if cell green,
(a) if down is blue, keep bringing blue to the start
(b) if down is empty, set to empty and go to parent
*/
// at start nicely
wall_or_empty(south) instruction({3, -2, south, 1, -2}, 1, 'H');
wall_or_empty(east) instruction({2, -2, 1, east, -2}, 1, 'H');
// dead ends
any(west) rwall(east) rwall(south) if (!(east == south && east == -2)) instruction({0, west, south, east, 2}, 4, 'N');
any(north) rwall(east) rwall(south) if (!(east == south && east == -2)) instruction({0, 3, south, east, north}, 4, 'W');
// at (W,H)
any(west) instruction({0, west, -2, -2, 2}, 1, 'N');
any(north) instruction({0, 3, -2, -2, north}, 1, 'W');
// empty cell(s)
any(west) any(north) RE(c) instruction({0, west, 0, c, north}, 2, 'S');
any(west) any(north) RE(c) instruction({0, west, 4, 0, north}, 3, 'E');
any(west) any(north) RE(c) instruction({2, west, c, 0, north}, 3, 'E'); // go down
any(west) EBX(c) instruction({2, west, 1, c, 2}, 1, 'H');
any(west) EBX(c) instruction({3, west, c, 1, 2}, 1, 'H'); // bring the blue north
any(west) ewall(c) instruction({1, west, 1, c, 2}, 1, 'N');
any(west) ewall(c) instruction({1, west, c, 1, 2}, 1, 'N'); // bring the blue north
any(west) instruction({3, west, 4, 4, 2}, 4, 'N'); // bring the empty north
any(north) EBX(c) instruction({2, 3, 1, c, north}, 1, 'H');
any(north) EBX(c) instruction({3, 3, c, 1, north}, 1, 'H'); // bring the blue west
any(north) ewall(c) instruction({1, 3, 1, c, north}, 1, 'W');
any(north) ewall(c) instruction({1, 3, c, 1, north}, 1, 'W'); // bring the blue west
any(north) instruction({3, 3, 4, 4, north}, 4, 'W'); // bring the empty west
// walls
any(west) any(north) wall(east) instruction({0, west, 0, east, north}, 2, 'S');
any(west) any(north) wall(south) instruction({0, west, south, 0, north}, 3, 'E');
any(west) wall(east) instruction({2, west, 4, east, 2}, 4, 'N');
any(north) wall(east) instruction({2, 3, 4, east, north}, 4, 'W');
any(west) wall(south) instruction({3, west, south, 4, 2}, 4, 'N');
any(north) wall(south) instruction({3, 3, south, 4, north}, 4, 'W');
// cleanup
wempty(south) instruction({1, -2, south, 1, -2}, 1, 'T'); // final terminate
wempty(east) instruction({1, -2, 1, east, -2}, 1, 'T');
any(west) ewall(east) ewall(south) if (!(east == south && east == -2)) instruction({4, west, south, east, 4}, 0, 'N');
any(north) ewall(east) ewall(south) if (!(east == south && east == -2) && !(north == 1)) instruction({4, 4, south, east, north}, 0, 'W');
// go down from blue
any(west) any(north) instruction({1, west, 4, 1, north}, 1, 'S'); // east is blue: go down
any(west) any(north) instruction({1, west, 1, 4, north}, 1, 'E'); // south is blue: go east
// go up to blue
ewall(south) ewall(east) any(north) instruction({4, 1, south, east, north}, 0, 'W'); // west is blue: go left
ewall(south) ewall(east) any(west) instruction({4, west, south, east, 1}, 0, 'N'); // north is blue: go up
// go down/right from red
any(north) any(west) instruction({4, west, 4, 4, north}, 4, 'S');
any(north) any(west) ewall(east) instruction({4, west, 4, east, north}, 4, 'S');
any(north) any(west) ewall(south) instruction({4, west, south, 4, north}, 4, 'E');
}
void program_pulibot() {
// solve_empty();
// solve_h2();
// solve_one_path();
solve_lattice();
// solve_bfs();
}
