solver of snake cube puzzle

.gitignore

cube.out
cube.out.dSYM/

cube.cpp

/*! if g++ -Wall -Wextra -g cube.cpp -o cube.out; then ./cube.out cube.txt; fi
 */




#include <string>
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <cstdlib>
#include <cassert>




using namespace std;




class vec3{
public:
  int val[3];
  vec3() {}
  vec3(int x, int y, int z){
    val[0] = x;
    val[1] = y;
    val[2] = z;
  }
  vec3(const vec3& v){
    val[0] = v.val[0];
    val[1] = v.val[1];
    val[2] = v.val[2];
  }
  bool operator==(const vec3& v) const {
    for(int i = 0; i < 3; i++) if(val[i] != v.val[i]) return false;
    return true;
  }
  vec3 operator-() const {
    vec3 ret(*this);
    for(int i = 0; i < 3; i++){
      ret.val[i] *= -1;
    }
    return ret;
  }
  vec3 operator+(const vec3 & v) const {
    return vec3(val[0] + v.val[0],
                val[1] + v.val[1],
                val[2] + v.val[2]);
  }
  vec3 abs() const {
    vec3 ret;
    for(int i = 0; i < 3; i++){
      ret.val[i] = std::abs(val[i]);
    }
    return ret;
  }
};




class block{
public:
  vec3 in, out;
  bool straight;
  block() {}
  block(vec3 in_, vec3 out_) : in(in_), out(out_), straight(in_ == out_) {}
};




class mat3{
public:
  int val[3][3];
  mat3() {}
  mat3(int x00, int x01, int x02,
       int x10, int x11, int x12,
       int x20, int x21, int x22){
    val[0][0] = x00; val[0][1] = x01; val[0][2] = x02;
    val[1][0] = x10; val[1][1] = x11; val[1][2] = x12;
    val[2][0] = x20; val[2][1] = x21; val[2][2] = x22;
  }
  mat3(const mat3& m){
    for(int i = 0; i < 3; i++){
      for(int j = 0; j < 3; j++){
        val[i][j] = m.val[i][j];
      }
    }
  }
  mat3 operator*(const mat3& m) const {
    mat3 ret;
    for(int i = 0; i < 3; i++){
      for(int j = 0; j < 3; j++){
        ret.val[i][j] = 0;
        for(int k = 0; k < 3; k++){
          ret.val[i][j] += val[i][k] * m.val[k][j];
        }
      }
    }
    return ret;
  }
  vec3 operator*(const vec3& v) const {
    vec3 ret;
    for(int i = 0; i < 3; i++){
      ret.val[i] = 0;
      for(int j = 0; j < 3; j++){
        ret.val[i] += val[i][j] * v.val[j];
      }
    }
    return ret;
  }
  mat3 inverse() const {
    return (*this) * (*this) * (*this);
  }
};




const vec3 ex(1, 0, 0);
const vec3 ey(0, 1, 0);
const vec3 ez(0, 0, 1);
const mat3 rotx(1, 0, 0,
                0, 0, -1,
                0, 1, 0);
const mat3 roty(0, 0, 1,
                0, 1, 0,
                -1, 0, 0);
const mat3 rotz(0, -1, 0,
                1, 0, 0,
                0, 0, 1);
const mat3 I(1, 0, 0,
             0, 1, 0,
             0, 0, 1);




vector<block> block_sequence(0);
const size_t buffer = 5;
vector<vector<vector<int> > > box(buffer*2 + 3, vector<vector<int> >(buffer*2 + 3, vector<int>(buffer*2 + 3, 0)));
#define LOOP(i) for(size_t i = buffer; i < buffer + 3; i++)



int& get(const vec3& pos){
  return box[buffer + pos.val[0]][buffer + pos.val[1]][buffer + pos.val[2]];
}


ostream& operator<<(ostream& ost, const vec3& v){
  return ost << "(" << v.val[0] << "," << v.val[1] << "," << v.val[2] << ")";
}
ostream& operator<<(ostream& ost, const block& b){
  return ost << "in=" << b.in << ", out=" << b.out << ", straight=" << b.straight;
}




mat3 get_rot(vec3 v){
  if(v.abs() == ex) return rotx;
  if(v.abs() == ey) return roty;
  if(v.abs() == ez) return rotz;
  assert(false);
}




bool read_puzzle(int x, int y, vec3 in, vector<string>& txt){
  if(x >= (int)txt.size() || x < 0) return false;
  if(y >= (int)txt[x].size() || y < 0) return false;
  if(txt[x][y] == '.') return false;
  txt[x][y] = '.';
  int dx[]  = {1, 0, -1, 0};
  int dy[]  = {0, -1, 0, 1};
  vec3 out;
  for(int i = 0; i < 4; i++){
    int xx = x + dx[i];
    int yy = y + dy[i];
    out = vec3(dx[i], dy[i], 0);
    if(read_puzzle(xx, yy, out, txt)){
      break;
    }
  }
  block_sequence.push_back(block(in, out));
  return true;
}




void read_puzzle(char* fpath){
  vector<string> txt;
  string buf;
  ifstream ifs(fpath);
  while(getline(ifs, buf)){
    txt.push_back(buf);
  }
  int x = 0;
  int y = txt[0].find_first_of("*");
  read_puzzle(x, y, vec3(1, 0, 0), txt);
  reverse(block_sequence.begin(), block_sequence.end());
}




void init(char* fpath){
  read_puzzle(fpath);
  LOOP(i){
    LOOP(j){
      LOOP(k){
        box[i][j][k] = -1;
      }
    }
  }
}




void print_ans(){
  cout << "answer:" << endl;
  LOOP(x){
    LOOP(z){
      LOOP(y){
        printf("%02d ", box[x][y][z]);
      }
      cout << "| ";
    }
    cout << endl;
  }
}




void dfs(size_t idx, const vec3& pos, const mat3& rot){
  if(idx == block_sequence.size()){
    print_ans();
    return;
  }
  if(get(pos) >= 0){
    return;
  }
  if((pos.val[0] + pos.val[1] + pos.val[2]) % 2 != idx % 2){
    return;
  }
  get(pos) = idx;
  const block& b = block_sequence[idx];
  vec3 in = rot * b.in;
  vec3 out = rot * b.out;
  if(b.straight){
    dfs(idx + 1, pos + out, rot);
  }
  else{
    mat3 new_rot = rot;
    mat3 in_rot = get_rot(in);
    for(int i = 0; i < 4; i++){
      new_rot = in_rot * new_rot;
      out = in_rot * out;
      dfs(idx + 1, pos + out, new_rot);
    }
  }
  get(pos) = -1;
}




int main(int argc, char *argv[]){
  init(argv[1]);
  for(int x = 0; x < 3; x++){
    for(int y = 0; y < 3; y++){
      for(int z = 0; z < 3; z++){
        dfs(0, vec3(x, y, z), I);
      }
    }
  }
  return 0;
}

cube.txt

*.............
*.............
**............
.***..........
...***........
.....**.......
......*.......
......***.....
........**....
.........***..
...........*..
...........***
.............*
.............*