Skip to content

Instantly share code, notes, and snippets.

@PanagiotisPtr
Created April 19, 2019 21:27
Show Gist options
  • Save PanagiotisPtr/9f150a7d1b0eab636ab8367092c1bdb4 to your computer and use it in GitHub Desktop.
Save PanagiotisPtr/9f150a7d1b0eab636ab8367092c1bdb4 to your computer and use it in GitHub Desktop.
Tic Tac Toe Board Encoding and Comparing (TTTBEC for short)
#include <iostream>
#include <vector>
#include <array>
using namespace std;
template<typename T>
using board = vector<vector<T> >;
typedef array<char, 3> encoding;
const char X = 1; // cross
const char O = 3; // circle
const char U = 0; // Undefined / empty
encoding encode(const board<int> &b) {
encoding rv;
// encode center
rv[0] = b[1][1];
// encode corners
rv[1] = (b[0][0]) | (b[0][2] << 2) | (b[2][0] << 6) | (b[2][2] << 4);
// encode cross
rv[2] = (b[0][1]) | (b[1][0] << 6) | (b[1][2] << 2) | (b[2][1] << 4);
return rv;
}
constexpr char rol(char c, unsigned n) {
return (c << n) | (c >> (8 - n));
}
bool match(const encoding& a, const encoding& b) {
if(a[0] != b[0])
return false;
if(a[1] == b[1])
return a[2] == b[2];
if(a[1] < b[1])
return match(b, a);
int i = 0;
while(i < 6)
if(rol(a[1], i) == b[1])
return rol(a[2], i) == b[2];
else
i += 2;
return false;
}
void print_bits(const char& c) {
for(int i = 7; i >= 0; i--) {
if((1 << i) & c)
cout << "1";
else
cout << "0";
if(i%2==0)
cout << " ";
}
cout << endl;
}
void print_encoding(const encoding& e) {
print_bits(e[0]);
print_bits(e[1]);
print_bits(e[2]);
}
int main() {
board<int> a = {{X,U,U},
{O,O,U},
{U,U,U}};
board<int> b = {{U,U,U},
{U,O,U},
{X,O,U}};
encoding e1 = encode(a);
encoding e2 = encode(b);
print_encoding(e1);
cout << endl;
print_encoding(e2);
cout << endl << boolalpha << match(e1, e2) << endl;
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment