フカシギの数え方_深さ優先探索

fukashigi_dfs.cpp

#include <iostream>
#include <sstream>
#include <memory>
#include <vector>
#include <chrono>
#include <emscripten/emscripten.h>

using namespace std;

struct Node {
  Node() :isPassed(false), isTerminal(false) {}

  vector<shared_ptr<Node>> neighbors;
  bool isPassed;
  bool isTerminal;
};

class Board {
public:
  Board(unsigned char n);
  void walk();
  unsigned long long getPaths() {return paths;};
private:
  void setUp();
  void walk(shared_ptr<Node> currentNode);
  unsigned char n;
  vector<shared_ptr<Node>> nodes;
  unsigned long long paths;
};

Board::Board(unsigned char n) :n(n), paths(0) {
  setUp();
};

void Board::setUp() {
  // nodesを準備
  for (auto i = 0; i < n * n; i++) {
    nodes.push_back(shared_ptr<Node>(new Node()));
  }
  nodes.back()->isTerminal = true;
  // 各nodeに対してneighborsを登録
  for (auto i = 0; i < n; i++) {
    for (auto j = 0; j < n; j++) {
      auto x = i * n + j;
      if (x - n >= 0) {
        nodes[x]->neighbors.push_back(nodes[x - n]);
      }
      if (x + n < n * n) {
        nodes[x]->neighbors.push_back(nodes[x + n]);
      }
      if (x % n != 0) {
        nodes[x]->neighbors.push_back(nodes[x - 1]);
      }
      if (x % n != n - 1) {
        nodes[x]->neighbors.push_back(nodes[x + 1]);
      }
    }
  }
}

void Board::walk() {
  walk(nodes.front());
};

void Board::walk(shared_ptr<Node> currentNode) {
  if (currentNode->isTerminal) {
    paths++;
    return;
  }
  currentNode->isPassed = true;
  vector<shared_ptr<Node>>::iterator it = currentNode->neighbors.begin();
  for (; it != currentNode->neighbors.end(); it++) {
    if (!(*it)->isPassed) {
      walk(*it);
    }
  }
  currentNode->isPassed = false;
};

unsigned long long EMSCRIPTEN_KEEPALIVE fukashigiDFS(unsigned char n) {
  Board board(n);
  board.walk();
  return board.getPaths();
}

int main() {
  auto n = 7; // wasm化後の引数の渡し方がわからなくて…
  auto start = chrono::system_clock::now();
  auto paths = fukashigiDFS(n);
  auto span = chrono::system_clock::now() - start;
  stringstream fixedSpan;
  if (span < chrono::duration<int, milli>(10000)) {
    fixedSpan << chrono::duration_cast<chrono::milliseconds>(span).count() << "ms";
  } else {
    fixedSpan << chrono::duration_cast<chrono::seconds>(span).count() << "s";
  }
  cout << paths << " paths are found on " << n << "*" << n << " nodes in " << fixedSpan.str() << " by WebAssembly(C++)." << endl;
}

fukashigi_dfs.js

// according to:
// http://handasse.blogspot.com/2012/09/blog-post.html

class Node {
  constructor() {
    this.neighbors = []
    this.isPassed = false
    this.isTerminal = false
  }
}

class Board {
  constructor(n) {
    this.n = n
    this.nodes = []
    this.paths = 0
    this.setUp()
  }
  setUp() {
    // nodesを準備
    const n = this.n
    for (let i = 0; i < n * n; i++) {
      this.nodes.push(new Node())
    }
    this.nodes[this.nodes.length - 1].isTerminal = true
    // 各nodeに対してneighborsを登録
    for (let i = 0; i < n; i++) {
      for (let j = 0; j < n; j++) {
        const x = i * n + j
        if (x - n >= 0) {
          this.nodes[x].neighbors.push(this.nodes[x - n])
        }
        if (x + n < n * n) {
          this.nodes[x].neighbors.push(this.nodes[x + n])
        }
        if (x % n !== 0) {
          this.nodes[x].neighbors.push(this.nodes[x - 1])
        }
        if (x % n !== n - 1) {
          this.nodes[x].neighbors.push(this.nodes[x + 1])
        }
      }
    }
  }
  walk(currentNode = this.nodes[0]) {
    if (currentNode.isTerminal) {
      this.paths++
      return
    }
    currentNode.isPassed = true
    currentNode.neighbors.forEach(neighbor => {
      if (!neighbor.isPassed) {
        this.walk(neighbor)
      }
    })
    currentNode.isPassed = false
  }
}

const fukashigiDFS = n => {
  const board = new Board(n)
  // カウント開始
  const start = Date.now()
  board.walk()
  const span = Date.now() - start
  const fixedSpan = span < 10000 ? `${span}ms` : `${(span / 1000).toFixed(1)}s`
  console.log(
    `${board.paths} paths are found on ${n}\*${n} nodes in ${
      fixedSpan
    } by JavaScript.`
  )
}

module.exports = fukashigiDFS