#include <stddef.h>
#include <stdio.h>
#include <assert.h>
#include <vector>
#include "squares.h"
struct edge;
int seq[2048], iseq[1024], seqi = 0;
bool seq_init = false;
bool v[512][2] = {0};
void deBrujinSeq(int w) {
for(int i = 0; i < 2; i++) {
if(!v[w][i]) {
v[w][i] = true;
deBrujinSeq(((w << 1) | i) & 511);
seq[seqi++] = i;
}
}
}
std::vector<int> paint(int n) {
if(!seq_init) {
//Create a De Brujn sequence
deBrujinSeq(0);
//Create a reverse lookup table
std::fill(iseq+0, iseq+1023, -1);
for(int i = 0; i <= 1024-10; i++) {
int w = 0;
for(int j = 0; j < 10; j++) {
assert(seq[i+j] >= 0);
w = (w << 1) | seq[i+j];
}
iseq[w & 1023] = i;
}
seq_init = true;
}
//Init labels from sequence
std::vector<int> l(n+1);
for(int i = 0; i < n; i++) l[i] = seq[i];
l[n] = 10;
return l;
}
int find_location(int n, std::vector<int> c) {
assert(c.size() == 10);
//Is at edge?
if(c[9] < 0) {
int p = 0;
while(c[p] >= 0) p++;
return n - p;
}
//Calculate word
int w = 0;
for(int i = 0; i < 10; i++) {
assert(c[i] >= 0);
w = (w << 1) | c[i];
}
//Lookup in LUT
return iseq[w];
}
