Information Mathematics Introduction Report 2

LightsOut.cpp

#include <iostream>
#include <vector>

const int SIZE = 5;
const int NUMBER_OF_PATTERN = 1 << (SIZE * SIZE);
const int TABLE_MASK = ~(-1 << (SIZE * SIZE));
int RIGHT_MASK = 0;
int LEFT_MASK = 0;
int TOP_MASK = 0;
int BOTTOM_MASK = 0;

std::vector<int> results;

bool validate(int p) {
  int table = TABLE_MASK;
  for (int q = 1; (q & TABLE_MASK) != 0; q <<= 1) {
    if ((p & q) == 0)
      continue;
    table ^= q;
    if ((q & RIGHT_MASK) == 0)
      table ^= q >> 1;
    if ((q & LEFT_MASK) == 0)
      table ^= q << 1;
    if ((q & TOP_MASK) == 0)
      table ^= q << SIZE;
    if ((q & BOTTOM_MASK) == 0)
      table ^= q >> SIZE;
  }
  if (table == 0)
    return true;
  else
    return false;
}

int main() {
  for (int i = 0; i < SIZE; i++) {
    RIGHT_MASK |= 1 << (i * SIZE);
    LEFT_MASK |= (1 << (SIZE - 1)) << (i * SIZE);
    TOP_MASK |= (1 << i) << (SIZE * (SIZE - 1));
    BOTTOM_MASK |= 1 << i;
  }
#pragma omp parallel for
  for (int i = 0; i < NUMBER_OF_PATTERN; i++) {
    if (validate(i)) {
      results.push_back(i);
    }
  }
  for each (auto r in results)
  {
    for (int i = SIZE - 1; i >= 0; i--) {
      for (int j = SIZE - 1; j >= 0; j--) {
        if ((r & (1 << (i * SIZE + j))) == 0)
          std::cout << "0";
        else
          std::cout << "1";
      }
      std::cout << std::endl;
    }
    std::cout << std::endl;
  }
  return 0;
}

レポート課題とは関係なくvalidate関数のアルゴリズムを改善し、さらにAVX2のSIMD命令を使って高速化を行ったバージョンも作りました。
https://gist.github.com/Mine02C4/c2a58fbf4dc1270166cb