shanten_analysis.cc

#include <vector>
#include <iostream>
#include <climits>
#include <cassert>
#include <string>
#include <fstream>
#include <sstream>
using namespace std;

class ShantenAnalyzer {

  public:
    ShantenAnalyzer();
    int CalculateShantensu(const vector<int>& pids);

  private:
    void PidsToCountVector(const vector<int>& pids, vector<int>* count_vector);
    int CalculateShantensuInternal(
        const vector<int>& current_vector, vector<int>* target_vector,
        int left_mentsus, int min_mentsu_id, int found_min_shantensu);
    int CalculateShantensuLowerbound(const vector<int>& current_vector, const vector<int>& target_vector);
    bool IsValidTargetVector(const vector<int>& target_vector);
    void AddMentsu(vector<int>* target_vector, int mentsu_id);
    void RemoveMentsu(vector<int>* target_vector, int mentsu_id);

    static const int NUM_PIDS = 9 * 3 + 7;
    vector<vector<int> > mentsus_;

};

ShantenAnalyzer::ShantenAnalyzer() {
  for (int i = 0; i < NUM_PIDS; ++i) {
    mentsus_.push_back(vector<int>(3, i));
  }
  for (int t = 0; t < 3; ++t) {
    for (int n = 0; n < 7; ++n) {
      int pid = t * 9 + n;
      vector<int> mentsu;
      mentsu.push_back(pid);
      mentsu.push_back(pid + 1);
      mentsu.push_back(pid + 2);
      mentsus_.push_back(mentsu);
    }
  }
}

int ShantenAnalyzer::CalculateShantensu(const vector<int>& pids) {
  vector<int> count_vector;
  PidsToCountVector(pids, &count_vector);
  vector<int> target_vector(NUM_PIDS, 0);
  return CalculateShantensuInternal(count_vector, &target_vector, 4, 0, INT_MAX);
}

void ShantenAnalyzer::PidsToCountVector(const vector<int>& pids, vector<int>* count_vector) {
  assert(count_vector);
  count_vector->assign(NUM_PIDS, 0);
  for (int i = 0; i < int(pids.size()); ++i) {
    ++(*count_vector)[pids[i]];
  }
}

int ShantenAnalyzer::CalculateShantensuInternal(
    const vector<int>& current_vector, vector<int>* target_vector,
    int left_mentsus, int min_mentsu_id, int found_min_shantensu) {
  int min_shantensu = found_min_shantensu;
  if (left_mentsus == 0) {
    for (int pid = 0; pid < NUM_PIDS; ++pid) {
      (*target_vector)[pid] += 2;
      if (IsValidTargetVector(*target_vector)) {
        int shantensu = CalculateShantensuLowerbound(current_vector, *target_vector);
        min_shantensu = min(shantensu, min_shantensu);
      }
      (*target_vector)[pid] -= 2;
    }
  } else {
    for (int mentsu_id = min_mentsu_id; mentsu_id < int(mentsus_.size()); ++mentsu_id) {
      AddMentsu(target_vector, mentsu_id);
      int lowerbound = CalculateShantensuLowerbound(current_vector, *target_vector);
      if (IsValidTargetVector(*target_vector) && lowerbound < found_min_shantensu) {
        int shantensu = CalculateShantensuInternal(
            current_vector, target_vector, left_mentsus - 1, mentsu_id, min_shantensu);
        min_shantensu = min(shantensu, min_shantensu);
      }
      RemoveMentsu(target_vector, mentsu_id);
    }
  }
  return min_shantensu;
}

int ShantenAnalyzer::CalculateShantensuLowerbound(
    const vector<int>& current_vector, const vector<int>& target_vector) {
  int count = 0;
  for (int pid = 0; pid < NUM_PIDS; ++pid) {
    if (target_vector[pid] > current_vector[pid]) {
      count += target_vector[pid] - current_vector[pid];
    }
  }
  return count - 1;
}

bool ShantenAnalyzer::IsValidTargetVector(const vector<int>& target_vector) {
  for (int pid = 0; pid < NUM_PIDS; ++pid) {
    if (target_vector[pid] > 4) return false;
  }
  return true;
}

void ShantenAnalyzer::AddMentsu(vector<int>* target_vector, int mentsu_id) {
  assert(target_vector);
  for (int i = 0; i < int(mentsus_[mentsu_id].size()); ++i) {
    ++(*target_vector)[mentsus_[mentsu_id][i]];
  }
}

void ShantenAnalyzer::RemoveMentsu(vector<int>* target_vector, int mentsu_id) {
  assert(target_vector);
  for (int i = 0; i < int(mentsus_[mentsu_id].size()); ++i) {
    --(*target_vector)[mentsus_[mentsu_id][i]];
  }
}

int main(int argc, char** argv) {
  ShantenAnalyzer analyzer;
  ifstream fs("shanten_benchmark_data.num.txt");
  string line;
  while (getline(fs, line, '\n')) {
    istringstream ss(line);
    vector<int> pids;
    for (int j = 0; j < 14; ++j) {
      int pid;
      assert(ss >> pid);
      pids.push_back(pid);
    }
    int expected_shantensu;
    assert(ss >> expected_shantensu);
    int actual_shantensu = analyzer.CalculateShantensu(pids);
    assert(actual_shantensu == expected_shantensu);
  }
  return 0;
}

shanten_analysis.js

var fs = require("fs");

var NUM_PIDS = 9 * 3 + 7;
var MENTSUS = createMentsus();

function createMentsus() {
  var mentsus = [];
  for (var pid = 0; pid < NUM_PIDS; ++pid) {
    mentsus.push([pid, pid, pid]);
  }
  for (var t = 0; t < 3; ++t) {
    for (var n = 0; n < 7; ++n) {
      var pid = t * 9 + n;
      mentsus.push([pid, pid + 1, pid + 2]);
    }
  }
  return mentsus;
}

function calculateShantensu(pids) {
  var countVector = pidsToCountVector(pids);
  var targetVector = [];
  for (var i = 0; i < NUM_PIDS; ++i) {
    targetVector.push(0);
  }
  return calculateShantensuInternal(countVector, targetVector, 4, 0, 1 / 0);
}

function pidsToCountVector(pids) {
  var countVector = [];
  for (var i = 0; i < NUM_PIDS; ++i) {
    countVector.push(0);
  }
  for (var i = 0; i < pids.length; ++i) {
    ++countVector[pids[i]];
  }
  return countVector;
}

function calculateShantensuInternal(currentVector, targetVector, leftMentsu, minMentsuId, foundMinShantensu) {
  var minShantensu = foundMinShantensu;
  if (leftMentsu == 0) {
    for (var pid = 0; pid < NUM_PIDS; ++pid) {
      targetVector[pid] += 2;
      if (isValidTargetVector(targetVector)) {
        var shantensu = calculateShantensuLowerbound(currentVector, targetVector);
        if (shantensu < minShantensu) minShantensu = shantensu;
      }
      targetVector[pid] -= 2;
    }
  } else {
    for (var mentsuId = minMentsuId; mentsuId < MENTSUS.length; ++mentsuId) {
      addMentsu(targetVector, mentsuId);
      var lowerbound = calculateShantensuLowerbound(currentVector, targetVector);
      if (isValidTargetVector(targetVector) && lowerbound < foundMinShantensu) {
        var shantensu = calculateShantensuInternal(
            currentVector, targetVector, leftMentsu - 1, mentsuId, minShantensu);
        if (shantensu < minShantensu) minShantensu = shantensu;
      }
      removeMentsu(targetVector, mentsuId);
    }
  }
  return minShantensu;
}

function calculateShantensuLowerbound(currentVector, targetVector) {
  var count = 0;
  for (var pid = 0; pid < NUM_PIDS; ++pid) {
    if (targetVector[pid] > currentVector[pid]) {
      count += targetVector[pid] - currentVector[pid];
    }
  }
  return count - 1;
}

function isValidTargetVector(targetVector) {
  for (var pid = 0; pid < NUM_PIDS; ++pid) {
    if (targetVector[pid] > 4) return false;
  }
  return true;
}

function addMentsu(targetVector, mentsuId) {
  var mentsu = MENTSUS[mentsuId];
  for (var i = 0; i < mentsu.length; ++i) {
    ++targetVector[mentsu[i]];
  }
}

function removeMentsu(targetVector, mentsuId) {
  var mentsu = MENTSUS[mentsuId];
  for (var i = 0; i < mentsu.length; ++i) {
    --targetVector[mentsu[i]];
  }
}

fs.readFileSync("shanten_benchmark_data.num.txt").toString("utf-8").split(/\n/).forEach(function(line) {
  if (!line) return;
  var row = line.split(/ /);
  var pids = [];
  for (var i = 0; i < row.length - 1; ++i) {
    pids.push(parseInt(row[i]));
  }
  var expectedShantensu = parseInt(row[row.length - 1]);
  var actualShantensu = calculateShantensu(pids);
  if (actualShantensu != expectedShantensu) {
    throw "Shantensu mismatch: " + actualShantensu + " != " + expectedShantensu + ": " + line;
  }
});

shanten_benchmark_data.num.txt

3 4 9 10 15 15 16 20 24 27 28 29 31 33 5
1 4 10 18 18 21 22 25 26 26 28 29 31 32 5
1 2 2 3 4 5 6 11 14 14 21 24 25 32 2
5 6 7 10 12 13 14 14 20 21 22 24 25 33 1
1 2 5 5 6 7 8 10 13 14 21 25 29 29 2
7 8 11 11 12 14 15 19 23 24 25 26 28 32 3
1 2 12 13 13 17 20 21 24 25 25 25 30 33 3
0 0 1 3 5 5 14 15 21 22 24 25 25 32 3
2 4 4 5 6 7 14 14 15 19 20 24 25 26 1
1 2 5 6 11 12 13 16 16 17 26 27 31 33 3
2 2 3 6 6 9 11 12 16 20 21 23 24 25 2
1 3 5 5 9 10 13 14 15 18 19 21 23 25 2
1 1 4 7 10 11 16 17 20 20 20 22 22 22 1
3 3 4 5 6 7 12 13 18 18 19 19 20 20 0
0 2 3 3 11 13 15 20 20 22 29 29 31 31 3
0 2 4 6 6 10 11 21 21 22 22 24 27 27 3
2 2 4 8 8 8 14 21 22 22 24 25 25 26 2
0 1 2 6 8 9 10 14 18 20 20 21 24 25 2
0 3 5 6 10 10 19 21 23 23 28 30 30 32 3
0 3 5 7 8 8 16 17 22 22 27 30 32 33 4
0 1 3 3 7 11 12 22 23 23 24 27 27 31 2
1 5 5 6 6 9 13 15 17 23 27 31 31 33 4
2 3 9 10 11 12 15 17 22 23 24 31 32 33 2
4 6 7 11 11 19 20 21 24 25 25 27 28 29 3
6 8 9 9 10 11 11 13 16 19 21 24 25 25 2
5 5 10 11 12 16 17 18 20 21 22 23 23 23 0
2 3 6 6 9 9 10 11 12 21 23 23 24 28 2
0 1 2 4 7 8 10 12 21 23 26 29 32 33 3
0 0 6 11 12 14 15 16 20 21 27 27 27 29 1
5 6 7 9 10 11 14 15 16 17 17 22 23 30 0
2 4 11 12 13 14 15 16 16 18 19 20 27 27 0
5 7 9 10 10 12 12 13 13 20 22 25 25 29 3
1 2 3 5 12 13 14 15 18 19 20 20 21 22 0
1 1 3 6 7 8 14 18 19 20 20 22 33 33 1
3 3 5 8 8 10 13 15 17 18 23 25 27 33 4
3 4 4 6 6 10 13 16 17 19 20 22 22 31 3
3 6 8 12 15 15 16 18 19 20 22 26 29 29 3
1 2 3 12 12 14 16 19 19 20 21 21 23 29 1
2 4 4 5 6 10 11 15 22 22 23 24 24 24 1
11 13 14 15 15 16 16 17 23 23 23 24 25 26 0
0 1 6 8 8 9 11 17 17 18 20 20 21 23 3
2 3 3 3 4 5 6 13 14 15 16 23 24 25 0
5 5 7 10 11 11 12 15 23 23 24 25 33 33 2
2 3 5 12 13 14 16 17 17 21 22 23 27 33 2
6 7 9 10 11 15 21 22 23 27 27 29 29 33 1
1 2 4 5 5 6 11 13 19 20 21 24 25 30 2
0 4 5 8 10 10 11 14 14 20 20 20 33 33 2
0 1 5 5 9 11 14 14 15 16 16 20 21 22 1
2 4 8 10 11 13 15 19 21 22 24 26 30 32 4
0 5 7 10 11 12 14 16 17 19 22 24 27 33 3
2 3 7 8 12 15 16 17 24 27 28 29 29 30 3
0 0 8 8 12 12 13 13 17 17 22 22 27 32 3
1 3 10 10 11 12 12 13 13 14 16 16 24 30 1
1 2 5 6 7 9 10 12 12 14 15 16 27 29 1
0 4 5 6 6 10 12 12 13 14 19 21 23 23 1
2 3 5 7 9 10 13 16 19 22 24 24 24 25 3
1 2 2 4 5 5 7 12 13 14 19 21 24 31 2
0 2 3 5 6 7 10 10 13 13 14 15 19 25 2
3 3 6 6 8 8 11 11 17 17 18 23 23 33 3
2 3 4 7 8 8 10 13 14 14 18 18 22 23 2
2 4 6 7 11 11 11 14 18 18 20 24 25 26 1
0 2 5 6 6 8 11 11 12 18 21 23 23 31 3
4 5 6 6 10 12 12 13 14 15 18 21 23 30 2
6 7 18 20 22 23 24 26 27 28 29 31 33 33 3
0 2 2 5 9 11 11 13 14 15 16 16 17 17 2
3 5 5 5 6 7 13 13 17 17 22 31 33 33 2
0 1 2 3 4 5 6 7 10 12 12 21 22 24 1
1 1 2 2 3 4 10 10 14 14 16 22 24 27 2
4 5 6 9 10 11 13 15 22 22 24 25 25 26 0
1 2 2 2 3 5 6 6 8 10 16 21 23 31 2
0 1 2 3 9 10 11 14 16 17 17 20 21 24 1
3 5 10 11 12 14 15 16 18 18 21 22 23 33 0
1 2 3 4 4 5 5 14 15 15 16 21 21 21 0
3 4 5 12 12 13 13 14 15 16 16 21 23 26 1
0 1 1 3 3 4 12 13 19 21 21 23 25 33 3
10 12 13 14 16 16 16 17 22 23 26 30 30 32 2
3 4 4 11 14 16 16 20 21 22 23 24 26 27 3
0 2 5 5 6 7 8 9 9 10 12 18 19 28 2
3 4 5 12 13 14 15 16 16 21 21 22 24 25 1
4 4 7 10 11 14 18 18 21 22 24 25 26 30 2
2 4 5 5 7 18 18 19 22 22 23 24 27 29 3
3 3 7 8 12 13 18 19 21 24 25 25 31 31 3
1 2 3 9 11 11 13 14 15 16 17 29 33 33 1
2 6 8 9 12 15 16 19 20 20 21 22 25 26 3
5 6 7 7 7 8 8 11 12 13 24 25 30 30 1
5 7 11 11 14 15 15 16 17 21 21 21 22 24 1
0 1 2 4 6 7 8 21 22 25 25 31 31 32 1
4 11 15 19 20 20 25 25 27 28 30 30 31 32 5
11 12 13 18 19 20 21 21 22 22 23 28 30 30 0
1 2 6 12 13 14 15 17 20 23 24 25 27 31 2
1 1 2 2 3 4 4 4 5 7 7 17 22 28 2
1 2 2 9 10 17 17 18 19 20 23 24 24 32 2
0 3 10 10 13 16 20 21 23 24 25 30 31 32 4
4 7 9 9 10 11 19 22 22 24 26 31 32 33 4
0 1 3 3 5 8 12 15 21 25 27 28 28 31 5
2 2 4 5 9 12 13 14 15 18 20 25 25 25 1
2 3 5 10 10 11 13 21 21 25 25 31 32 32 3
0 2 7 9 12 13 15 15 17 22 23 23 26 30 4
0 4 5 6 11 12 15 18 20 21 22 26 27 28 3
3 11 12 13 14 15 16 18 18 19 21 22 22 28 1
2 2 2 5 7 10 12 13 14 15 15 20 20 22 1
0 0 1 2 8 8 14 22 24 24 26 27 29 33 3
3 4 6 6 7 14 14 14 22 23 25 25 26 31 2
1 1 5 6 10 13 15 16 20 22 22 24 30 30 3
3 3 6 7 8 10 12 15 16 22 23 24 24 30 1
5 7 7 11 12 13 14 15 20 25 25 26 29 29 2
0 12 12 15 17 18 22 27 28 28 29 29 31 33 4
3 3 5 6 10 12 13 15 19 21 21 23 25 28 3
3 3 4 6 7 17 20 21 23 23 26 28 30 30 3
0 1 2 2 10 11 14 14 16 16 18 19 21 25 2
0 3 5 10 14 16 17 18 19 19 25 29 31 33 5
3 8 11 12 12 17 21 22 22 24 25 26 29 33 4
10 11 13 14 15 18 19 19 20 29 29 29 33 33 0
0 4 8 12 14 15 15 15 18 18 19 19 21 25 3
3 5 9 12 13 14 16 17 17 19 21 22 23 27 2
2 7 8 14 15 16 21 22 23 23 24 25 25 32 1
1 5 6 10 11 11 12 13 13 21 21 25 31 31 2
2 2 3 5 18 20 20 21 22 23 24 25 25 26 1
0 1 2 5 9 10 11 13 16 17 18 20 22 24 2
0 1 3 4 5 12 13 16 18 20 23 31 32 32 2
8 10 12 15 16 16 18 21 22 25 26 28 29 33 4
0 0 1 1 3 11 12 12 13 19 19 20 23 28 3
2 6 6 9 11 14 15 20 22 23 25 26 28 32 3
4 7 9 10 10 12 12 13 20 22 23 25 25 33 3
0 0 0 4 5 11 13 15 16 17 20 21 31 31 1
6 6 10 10 10 14 14 23 24 25 25 28 28 28 0
0 7 9 9 11 12 13 19 20 22 23 23 31 33 3
3 4 6 7 8 10 12 18 18 20 22 24 28 31 2
0 6 6 10 10 11 15 16 17 19 21 25 26 31 2
2 3 4 8 8 10 11 12 14 14 19 25 25 33 1
2 6 9 12 14 17 17 23 25 26 26 29 32 33 4
4 6 6 9 10 12 14 14 15 16 17 18 23 27 3
1 2 3 9 9 21 22 24 25 26 31 31 33 33 1
1 2 3 4 5 7 12 15 22 24 27 32 33 33 3
5 7 14 15 16 19 20 24 26 28 30 31 32 33 3
2 2 6 8 11 12 15 16 19 20 20 21 23 28 2
3 4 10 11 11 13 14 14 16 16 24 25 25 26 2
5 6 13 14 15 18 19 19 20 22 24 24 29 29 1
3 3 5 7 8 10 15 23 23 29 29 31 32 33 4
1 5 6 7 15 15 18 19 20 21 21 23 25 26 1
0 0 2 4 18 19 19 20 20 23 24 24 25 27 1
6 6 9 9 12 12 13 13 14 14 16 16 17 17 1
2 6 6 7 9 11 13 16 17 17 20 22 24 33 4
0 3 3 5 11 12 13 14 14 16 19 22 25 25 3
0 2 6 7 7 11 15 16 19 21 26 27 28 32 4
3 4 13 15 16 18 18 18 22 23 24 25 26 31 2
1 2 2 5 5 13 14 14 20 20 26 26 27 33 3
4 5 12 13 14 18 18 18 22 23 24 26 26 29 0
3 5 5 6 7 11 12 19 22 23 24 26 27 27 1
1 5 5 12 15 15 15 16 18 21 23 23 29 29 3
1 2 3 6 7 9 10 10 13 21 23 27 29 29 2
2 4 4 6 8 11 11 12 13 14 15 18 19 23 2
2 3 4 17 18 19 19 21 21 24 24 26 33 33 2
0 1 2 5 7 11 12 12 14 16 16 20 23 29 2
5 6 18 19 20 21 22 23 23 25 25 25 30 30 0
0 1 3 4 5 13 16 16 17 20 21 23 23 25 2
0 1 2 6 7 8 10 12 14 16 20 21 24 25 2
0 1 2 5 5 6 10 15 17 19 22 22 29 31 3
1 5 5 7 8 8 10 11 15 19 23 23 32 33 4
4 6 6 6 10 15 16 17 21 22 24 29 29 30 2
2 4 6 7 11 15 16 17 18 20 26 26 26 27 2
0 3 3 4 12 12 14 15 23 23 25 27 27 31 3
1 2 7 8 10 10 13 13 14 16 18 22 27 32 3
1 1 1 5 5 5 7 7 8 11 12 14 14 31 1
0 2 3 4 6 6 7 10 16 17 21 23 24 32 3
3 10 10 11 12 13 14 19 21 23 24 25 31 32 2
4 4 5 7 7 9 12 12 13 13 15 15 20 23 3
0 2 3 4 6 7 7 10 12 19 22 23 23 32 3
1 3 5 6 9 10 11 13 13 14 16 29 29 29 1
2 10 11 11 13 14 16 18 20 20 21 22 23 23 2
4 5 6 7 7 12 14 14 15 16 20 21 22 23 0
1 2 3 12 18 19 19 21 22 24 24 25 27 33 3
0 4 8 14 15 15 17 19 20 21 25 26 28 28 2
3 5 6 8 9 16 17 19 21 25 26 28 31 32 4
1 5 7 10 11 14 14 16 16 21 24 28 29 30 4
3 3 4 4 5 5 7 7 9 14 16 24 25 26 0
1 3 3 11 11 12 12 13 18 19 20 22 24 26 1
1 3 4 4 7 9 9 18 19 19 20 22 31 31 2
0 3 7 8 10 16 20 25 26 26 28 29 32 33 6
0 1 1 2 3 5 7 7 8 13 14 18 32 32 2
0 1 4 7 8 11 11 15 18 20 21 27 29 29 3
1 2 2 3 7 8 12 13 15 20 21 23 32 32 2
1 2 3 6 7 9 14 19 19 20 20 20 23 26 2
1 3 5 6 6 7 8 12 16 28 31 32 32 33 3
3 5 6 6 6 13 15 17 18 21 29 30 31 33 4
0 1 3 4 5 11 11 13 24 25 27 27 29 29 2
0 0 0 1 3 3 9 10 13 13 15 15 16 33 2
0 1 2 5 7 11 12 12 14 16 16 23 28 29 2
0 0 1 6 7 8 11 14 15 16 18 18 20 33 2
1 2 3 6 7 9 21 22 22 24 24 30 31 32 3
1 3 4 14 14 15 15 16 18 19 20 23 23 28 1
14 15 16 20 21 23 24 25 28 29 29 29 32 32 0
5 6 7 10 11 15 15 16 21 22 23 25 25 31 1
2 3 5 6 6 7 7 9 10 15 17 23 25 26 3
5 6 8 9 11 18 18 19 21 21 21 23 24 31 2
2 3 8 11 11 13 14 16 17 18 22 23 27 31 3
6 6 7 8 8 12 12 13 13 16 16 22 23 26 2
2 2 8 8 9 9 14 14 16 16 16 19 19 20 2
19 20 20 21 22 23 23 24 27 31 31 32 33 33 2
2 2 3 3 3 4 4 5 20 26 26 29 29 29 0
2 3 3 6 7 8 12 14 15 15 16 23 24 30 2
2 4 5 6 7 11 13 15 16 19 19 20 20 22 2
0 1 3 9 17 20 23 23 24 25 28 31 32 33 5
0 3 4 9 11 15 16 22 23 26 28 29 29 31 3
0 1 2 5 11 12 12 21 22 23 23 23 28 28 1
0 1 2 7 7 10 14 15 18 19 20 21 22 23 0
0 1 2 6 8 8 16 21 21 23 25 25 30 31 3
1 5 6 7 7 10 10 12 14 20 20 23 30 30 2
2 3 5 5 5 12 17 19 20 21 25 25 33 33 1
2 3 10 10 10 11 15 16 20 20 21 21 22 23 1
4 5 5 11 11 12 12 13 20 22 22 25 25 25 1
2 2 5 6 7 15 16 18 19 20 22 25 25 26 1
5 8 14 17 18 20 22 25 27 28 28 29 31 32 6
2 3 4 10 11 12 20 21 22 23 23 29 29 30 0
2 3 4 5 6 8 8 12 13 21 25 26 26 31 2
1 2 5 5 6 13 13 13 15 15 20 21 29 29 2
0 3 3 7 9 12 14 19 21 22 22 24 29 33 4
0 4 5 6 9 11 12 15 18 20 21 22 22 28 3
1 1 2 3 5 6 6 8 11 12 12 20 24 25 2
2 2 4 6 6 7 8 10 12 12 20 23 25 27 2
8 9 11 12 14 16 19 21 21 21 24 25 25 26 2
1 1 6 6 12 12 13 13 15 21 24 29 32 32 3
7 12 14 18 20 21 21 23 24 27 28 28 30 33 3
2 3 4 11 13 14 14 14 19 20 21 22 23 24 0
1 2 3 4 5 13 15 16 17 18 19 20 20 23 1
0 2 2 9 9 11 12 13 14 14 17 24 27 27 2
1 2 3 6 7 8 12 13 13 14 15 21 21 23 0
1 1 3 4 6 7 10 12 14 23 23 24 25 27 2
0 2 2 6 14 16 17 18 18 22 24 27 31 33 4
0 1 2 6 7 8 13 13 14 14 16 18 19 19 1
3 3 4 5 6 7 11 12 14 14 16 21 22 33 2
2 3 4 6 8 19 20 21 21 24 25 26 26 26 0
2 3 6 8 9 10 12 13 15 16 17 23 25 25 2
2 7 9 11 12 13 15 16 20 23 24 25 27 33 3
3 6 9 10 10 11 11 18 19 22 23 25 28 29 3
1 3 3 11 12 12 15 16 18 20 20 21 25 25 3
0 1 2 6 9 10 11 12 14 16 18 19 25 25 1
1 7 8 11 12 15 17 19 22 25 29 29 31 33 4
0 1 2 6 11 11 13 13 18 19 20 25 25 26 1
5 6 6 9 11 19 19 20 20 21 22 24 26 32 2
1 2 3 12 12 14 16 18 19 19 20 21 21 23 1
2 3 5 6 12 12 13 13 14 19 21 23 25 29 3
0 1 3 9 11 12 16 17 17 18 23 30 31 32 5
1 2 3 6 7 12 13 14 19 20 20 21 21 22 0
2 3 5 6 7 11 12 15 20 20 23 23 29 31 2
1 2 4 7 7 13 13 14 14 16 18 18 19 19 3
1 8 9 10 10 11 15 15 17 17 20 20 23 30 3
1 1 3 4 4 6 7 8 10 11 14 15 16 20 1
0 4 18 19 21 23 26 26 28 31 31 31 32 32 2
1 3 6 6 13 16 16 24 25 25 26 28 30 30 2
4 6 9 10 12 14 14 14 17 22 22 24 24 29 2
1 1 1 3 6 14 16 19 21 22 23 24 24 33 2
0 2 3 6 7 9 11 15 16 27 28 30 31 33 4
0 4 6 7 8 12 12 13 17 20 25 26 26 32 4
0 0 4 7 7 11 11 13 16 18 18 19 23 24 3
4 5 5 9 10 11 13 20 20 22 23 23 24 24 1
12 13 14 15 19 19 20 20 20 21 22 23 25 26 0
4 4 5 6 6 9 11 12 17 21 21 24 25 26 1
0 1 2 5 10 10 10 14 15 18 19 26 26 31 1
3 3 3 5 6 6 12 13 14 23 24 24 25 26 0
0 2 6 7 8 8 17 18 18 19 19 26 31 32 3
1 2 4 7 7 12 14 14 15 21 22 22 23 24 2
0 1 2 9 10 10 15 17 18 19 22 26 31 31 2
3 4 9 14 14 16 18 19 20 21 22 24 25 33 2
2 2 6 8 10 10 11 11 12 12 16 19 21 23 1
1 2 10 12 15 17 17 18 22 23 28 31 31 33 3
1 3 5 6 6 8 9 10 19 22 27 27 28 33 3
1 3 5 9 9 11 13 13 13 18 24 25 28 28 2
3 3 4 5 6 7 7 9 12 15 20 24 32 32 3
1 2 3 5 6 8 8 20 21 22 22 23 24 25 0
4 5 6 8 10 14 16 20 22 25 25 32 32 33 2
0 0 1 1 2 5 13 13 15 15 16 16 28 28 2
0 2 2 5 6 6 12 14 16 24 26 26 30 33 4
0 5 7 11 12 14 14 18 18 20 23 31 32 33 4
1 2 3 9 12 12 14 16 19 19 20 21 21 23 1
0 2 3 5 5 6 10 14 15 20 23 23 23 29 3
3 8 8 9 12 12 13 15 18 19 20 24 29 29 2
2 3 6 7 8 11 12 13 20 21 24 26 27 27 1
0 0 1 2 3 3 4 9 10 15 15 16 18 20 2
0 1 3 9 9 13 15 19 21 21 22 23 27 28 2
2 3 5 5 6 7 8 10 11 12 13 14 15 33 0
5 7 11 12 13 15 16 17 17 22 23 27 30 30 1
0 2 4 5 7 7 9 10 11 17 21 22 24 25 2
1 9 10 15 16 22 23 24 24 25 30 30 32 33 2
3 9 11 11 12 13 18 19 19 19 22 22 23 24 1
7 11 13 15 15 16 18 19 20 21 21 21 22 29 2
1 3 3 5 6 7 9 11 13 13 23 23 24 24 2
0 1 2 3 11 12 14 15 16 19 19 20 21 22 0
2 2 9 10 10 11 11 14 14 20 20 21 23 23 2
2 5 11 12 12 13 14 16 20 21 22 26 28 28 2
5 7 7 9 10 10 15 18 20 22 23 23 23 24 2
1 2 3 12 13 14 15 17 17 20 20 21 24 25 1
6 6 12 14 15 16 19 19 24 24 26 27 27 27 1
3 3 3 5 7 11 12 13 13 14 15 20 20 22 0
1 3 5 5 9 10 11 13 14 15 19 21 23 25 1
2 4 9 9 11 11 12 16 20 21 22 24 25 28 2
1 2 2 3 6 7 7 10 13 21 21 23 23 23 2
0 1 1 1 3 4 5 10 12 14 15 19 19 19 1
0 0 4 5 15 16 17 18 19 20 29 33 33 33 0
0 2 4 9 10 15 15 17 19 22 22 23 26 29 4
1 2 2 2 3 11 12 21 22 22 23 23 24 26 0
1 3 5 6 7 7 10 10 12 12 13 20 20 32 2
5 6 10 10 12 12 13 15 15 19 20 25 30 30 3
5 6 7 9 15 15 18 19 20 21 21 23 25 26 1
2 5 12 14 14 15 16 16 21 22 22 25 30 30 3
1 2 2 3 3 5 5 16 19 20 21 23 24 25 0
5 12 12 13 14 14 19 21 22 24 30 30 30 32 2
2 3 6 7 10 13 16 16 17 17 21 21 23 25 3
2 3 4 5 7 8 12 19 21 22 24 27 28 28 2
2 2 2 9 10 11 13 13 19 20 21 23 24 24 0
2 6 8 11 14 16 17 18 20 25 27 28 31 32 5
2 3 4 5 6 7 10 11 12 14 19 24 25 26 0
1 1 3 10 11 12 12 14 16 21 22 24 24 25 2
0 1 6 7 13 13 14 14 25 25 26 33 33 33 2
0 1 2 5 5 6 7 8 21 22 23 24 25 26 -1
1 4 4 6 6 8 8 12 14 16 21 25 29 30 4
0 1 2 13 13 16 16 16 19 20 21 31 31 31 -1
1 3 6 7 8 11 13 20 23 24 24 26 32 32 2
1 3 3 4 7 8 10 14 20 22 24 25 26 32 3
1 2 2 3 5 6 8 8 20 21 22 23 24 25 0
4 6 8 11 14 16 20 20 21 22 23 24 26 27 2
0 5 5 9 10 14 16 18 19 25 27 29 31 33 4
3 4 6 7 7 9 22 23 23 25 25 26 27 33 3
2 2 4 11 12 14 15 15 15 23 25 30 30 33 2
1 2 2 7 12 13 14 14 15 18 18 20 22 31 2
1 2 4 6 6 13 21 22 29 31 31 33 33 33 2
0 1 2 5 8 11 12 12 21 22 23 23 23 28 2
1 4 5 5 7 10 11 12 14 19 21 22 24 29 3
1 1 2 12 13 14 22 22 24 24 24 25 30 30 1
1 2 2 4 6 9 11 13 15 16 19 22 25 29 4
1 1 4 8 15 17 21 23 25 25 27 29 30 32 4
3 4 9 10 11 12 13 15 16 17 19 22 22 26 1
2 3 4 7 8 9 10 14 16 16 19 21 23 26 2
1 4 5 9 10 10 12 18 19 20 27 28 28 32 2
2 4 4 6 7 12 13 14 15 18 19 21 22 33 2
1 2 3 7 9 21 22 24 25 26 31 31 33 33 1
2 3 4 8 12 12 13 14 24 25 26 30 30 30 0
2 3 4 9 11 13 14 14 15 18 19 20 32 32 0
1 5 12 13 13 14 15 18 23 24 27 28 30 30 3
1 2 7 8 12 12 16 17 19 20 22 24 26 30 3
20 21 22 22 23 23 23 25 26 26 28 28 31 31 1
0 1 2 5 6 12 16 18 20 20 22 23 24 24 2
1 3 3 4 4 6 8 14 19 22 23 24 28 30 3
2 4 4 7 8 9 13 14 14 16 16 16 32 33 3
1 1 6 11 12 13 15 15 18 18 24 25 33 33 2
1 1 6 7 8 13 13 15 16 17 18 19 25 27 1
6 7 9 12 20 22 23 26 27 28 29 31 33 33 5
0 7 8 8 8 9 10 12 12 15 18 21 22 23 2
2 3 10 15 17 21 22 27 27 27 28 29 29 29 2
0 4 4 5 6 6 8 10 12 14 19 19 31 31 2
2 3 4 12 13 14 15 18 18 18 20 21 30 30 0
0 7 8 8 8 12 12 13 13 14 14 19 21 25 1
3 6 7 7 10 10 13 14 15 15 16 25 27 31 3
0 5 9 14 14 15 16 19 20 23 26 26 27 33 4
1 2 2 3 4 13 14 15 15 19 22 22 28 28 1
0 0 0 1 4 11 11 13 19 23 27 27 27 30 3
0 2 2 7 8 12 13 13 17 21 23 24 29 31 4
1 3 4 4 8 10 11 13 16 16 23 23 24 32 3
0 2 7 8 11 15 16 22 24 25 27 31 33 33 3
1 4 8 8 12 18 18 19 20 21 22 23 24 33 2
3 9 11 12 13 16 17 19 20 22 22 23 30 30 2
3 4 5 5 12 13 13 14 15 15 15 20 22 22 1
1 2 3 11 12 13 13 14 15 21 21 21 22 22 -1
0 1 2 3 5 6 7 11 11 12 14 24 25 26 0
1 2 3 4 4 6 11 15 21 21 22 24 32 32 2
0 1 2 3 4 7 8 19 28 29 30 30 30 32 2
0 1 2 6 8 9 13 14 17 19 21 24 24 32 2
0 0 1 8 10 14 14 18 22 23 24 24 26 27 3
5 7 10 11 15 16 18 19 20 20 22 22 24 25 2
2 4 9 9 10 11 12 14 14 21 23 24 26 28 2
3 5 7 10 15 17 20 21 22 23 24 25 25 26 2
3 4 5 7 8 10 11 12 14 16 16 22 23 24 0
4 6 7 13 13 14 14 16 25 25 26 33 33 33 2
1 2 3 5 6 7 11 11 12 13 20 20 31 31 0
1 2 7 10 11 12 12 13 15 16 17 18 19 22 2
0 2 4 5 6 7 13 14 16 16 18 19 20 21 1
3 4 5 10 12 12 13 14 19 19 23 24 25 32 0
1 2 3 9 10 11 11 12 13 15 18 18 24 25 0
3 3 4 5 6 7 12 13 13 20 21 22 32 32 1
1 8 12 15 16 16 17 23 26 27 28 29 30 32 6
1 5 7 8 15 16 17 18 20 24 26 27 31 33 3
2 3 4 6 6 9 11 11 11 20 21 22 23 23 0
2 5 5 8 9 13 15 15 15 17 25 26 28 28 3
1 3 5 5 6 14 14 15 19 20 24 26 29 29 3
0 2 6 6 8 11 13 16 19 20 23 24 28 32 3
0 2 4 7 7 11 12 13 14 15 16 20 21 23 1
0 0 1 1 2 10 10 14 15 15 16 19 24 25 1
5 9 9 10 23 24 24 25 26 27 27 27 30 30 1
0 1 2 3 4 4 5 18 19 20 21 22 26 26 0
2 6 8 14 15 16 18 19 20 21 25 32 33 33 2
0 1 3 4 5 13 14 15 19 20 23 27 32 33 2
1 3 9 9 10 11 11 16 17 21 22 23 28 28 1
5 5 9 10 11 14 15 19 20 21 21 24 24 25 1
4 5 14 16 19 20 23 25 25 26 26 26 28 29 2
0 1 1 6 7 7 8 12 16 20 22 31 33 33 3
4 5 5 7 10 11 12 14 19 21 22 24 25 29 3
0 1 1 2 6 6 7 7 12 13 14 19 29 29 1
1 3 5 6 7 8 8 16 17 21 22 23 23 24 1
9 12 13 14 15 16 16 23 25 27 28 29 32 33 4
2 3 4 11 12 13 16 16 16 20 22 25 25 27 0
1 5 5 6 8 9 20 20 20 21 22 24 27 30 3
1 3 4 4 9 15 16 17 18 18 20 22 25 27 2
4 5 6 7 8 9 10 11 14 16 20 24 28 33 2
5 7 11 12 13 14 14 15 16 16 21 23 26 30 2
4 5 9 12 14 15 15 16 16 16 18 18 24 28 2
0 1 3 4 5 14 15 17 18 20 21 23 33 33 2
1 3 4 6 6 8 10 11 15 18 19 26 33 33 3
1 5 7 8 8 10 11 14 15 20 21 24 24 25 3
1 2 7 8 8 9 13 16 17 21 21 22 23 23 2
3 8 8 11 14 15 15 16 20 20 22 23 26 32 3
2 3 12 13 14 15 17 20 20 22 27 30 31 31 2
5 5 6 6 13 16 16 17 18 18 19 19 20 26 2
0 1 6 6 6 11 13 17 22 24 27 31 32 33 3
1 2 3 12 13 13 13 14 16 17 20 20 22 23 1
1 1 6 6 7 15 15 20 20 22 22 25 29 31 3
6 7 8 8 9 10 10 15 17 25 26 31 33 33 2
0 2 4 9 11 16 23 25 28 30 31 31 32 33 4
1 1 2 9 11 16 18 24 25 26 28 31 31 33 3
2 3 5 6 10 14 15 16 19 20 21 25 25 26 1
3 4 7 7 10 10 13 15 18 19 20 26 32 32 2
1 5 9 10 10 12 16 18 19 20 27 28 32 33 4
0 0 4 10 10 12 14 14 16 18 22 24 32 33 3
2 3 3 4 4 13 14 19 19 21 23 23 24 30 2
4 6 8 9 10 12 14 17 19 23 25 28 28 29 3
6 8 8 10 13 14 16 17 20 21 27 31 31 32 3
1 2 4 6 8 21 22 23 23 24 25 25 25 32 1
2 3 5 6 13 17 19 19 21 24 25 28 29 31 4
4 4 6 6 7 12 14 19 20 20 26 28 31 32 4
1 3 4 5 6 11 12 13 19 21 21 23 28 28 1
4 4 5 11 12 19 19 20 20 21 21 23 29 32 2
2 7 8 10 11 12 13 14 16 16 17 21 22 33 2
1 2 7 8 9 11 15 15 16 19 20 21 22 29 2
1 10 14 16 19 20 22 23 23 24 27 31 31 32 3
1 3 5 9 9 10 11 11 21 22 23 23 28 28 1
1 3 6 7 8 10 11 16 16 16 18 19 20 31 1
5 7 9 9 14 15 16 19 20 21 22 23 24 26 0
3 6 7 14 15 16 17 20 21 22 24 25 31 32 2
3 5 7 13 14 14 18 18 19 20 20 22 24 25 2
4 7 16 19 19 19 20 20 21 22 24 25 31 32 3
0 1 2 4 13 19 21 22 24 24 25 25 26 26 1
2 3 3 5 7 14 22 23 23 24 25 26 28 28 2
1 1 1 3 3 3 5 5 18 19 20 20 21 29 0
1 4 8 12 14 17 19 19 22 24 27 29 31 33 5
2 3 4 4 6 6 7 7 21 22 23 23 24 27 1
2 4 7 8 8 11 14 18 20 29 30 32 32 33 4
2 4 5 7 8 12 13 14 15 19 22 27 29 29 3
3 4 4 5 6 11 13 15 15 20 22 23 24 27 1
2 3 4 4 7 8 10 11 13 14 19 21 22 23 2
2 4 6 7 13 14 14 16 16 24 25 26 26 32 2
1 2 5 6 9 9 9 16 18 18 19 19 20 20 1
0 1 1 4 7 8 14 15 16 17 19 23 27 32 4
0 3 4 6 8 9 9 10 12 14 14 24 24 26 3
1 2 2 3 6 6 7 8 8 10 10 13 22 25 2
2 2 5 5 5 11 12 13 14 20 21 22 23 24 0
3 4 5 5 6 7 14 16 18 19 20 21 21 25 0
0 1 4 5 7 13 13 15 15 16 16 23 28 29 3
4 8 9 10 11 14 18 20 21 23 24 28 29 33 4
2 3 4 9 10 11 11 15 16 21 21 24 25 31 1
1 4 4 5 6 6 9 14 16 16 24 27 30 32 4
1 4 5 5 5 8 10 12 13 25 32 32 32 33 3
0 2 5 6 8 11 11 12 17 18 21 23 23 31 4
1 2 3 10 10 12 12 13 16 16 16 22 23 29 1
0 1 1 2 4 5 8 14 14 24 25 28 28 29 2
7 7 8 9 10 11 11 12 16 21 22 31 31 32 2
1 2 5 6 14 15 19 20 20 21 21 25 25 29 2
6 6 9 10 11 13 13 14 24 24 28 29 30 31 3
0 1 6 7 11 13 14 15 16 23 25 26 27 27 2
4 6 7 15 16 17 18 19 19 22 26 29 29 32 3
0 4 4 11 12 14 18 19 21 26 29 31 31 33 4
0 1 1 5 10 15 15 19 20 21 23 27 30 33 4
1 3 4 5 7 9 11 12 19 19 22 24 28 31 3
0 0 2 6 13 14 16 16 20 22 27 32 32 33 3
4 4 5 10 10 20 20 21 21 23 23 25 25 26 3
0 0 1 3 4 10 10 10 19 20 21 24 25 26 0
2 5 8 9 12 13 16 17 18 20 24 26 32 32 3
1 2 3 4 5 6 9 12 14 16 16 18 25 32 2
10 10 11 12 12 13 14 14 16 21 22 29 29 29 1
0 3 10 17 21 22 25 27 27 28 29 29 31 33 5
0 0 2 5 7 11 13 13 13 24 25 28 31 33 3
2 8 8 9 13 15 15 17 21 22 23 23 23 25 2
7 18 20 22 23 24 26 27 28 29 31 32 33 33 4
0 1 2 3 4 4 5 14 15 16 20 21 33 33 0
3 10 15 17 18 20 21 22 25 25 26 28 30 32 4
4 6 9 12 14 14 14 17 22 22 26 29 29 32 3
4 4 7 10 11 13 13 21 22 23 23 23 25 27 2
0 2 5 13 15 20 22 24 26 26 27 27 31 33 3
0 0 0 4 6 12 13 13 21 22 25 25 33 33 2
2 3 5 6 7 10 12 12 16 20 23 25 32 33 3
0 1 7 8 12 13 20 21 26 27 28 31 32 33 4
0 1 7 7 8 10 11 17 18 19 20 23 25 33 2
0 0 1 1 2 13 15 18 19 20 21 30 31 31 1
0 0 2 6 6 8 8 13 14 14 16 22 27 29 3
2 2 8 11 13 15 15 16 19 23 24 28 28 28 2
0 0 1 5 7 11 13 15 15 16 17 23 24 24 2
4 5 8 14 16 17 19 21 23 26 27 28 29 31 5
1 1 3 3 6 7 7 14 14 17 21 22 30 31 3
3 3 5 9 18 20 22 22 23 24 24 25 27 27 2
3 4 5 6 7 16 17 23 24 26 27 27 30 30 2
5 6 6 12 12 14 14 15 15 16 24 24 25 25 2
1 3 6 7 7 8 10 15 19 26 26 28 30 32 4
0 1 6 7 8 10 12 18 19 21 22 26 29 33 3
3 4 4 9 10 11 11 14 15 22 22 25 26 26 2
1 1 3 13 14 15 15 16 17 20 21 22 26 26 0
3 5 5 9 14 15 16 17 17 19 19 20 30 30 2
3 4 5 6 7 7 8 9 10 11 12 12 20 21 0
1 2 2 7 9 9 10 19 19 19 21 21 27 31 3
0 3 6 8 12 15 15 16 18 19 20 22 29 29 3
3 7 8 8 13 15 21 21 28 28 31 32 33 33 3
1 3 13 13 14 15 15 16 17 22 23 24 25 28 1
3 4 6 7 7 16 21 22 23 23 25 25 27 33 3
5 11 12 12 13 14 20 22 25 26 26 28 28 33 2
2 3 4 4 4 5 6 6 9 10 11 21 22 23 0
4 5 6 6 14 14 14 19 21 23 23 27 30 30 1
1 1 12 12 14 16 21 22 23 25 25 29 31 31 2
0 1 8 10 11 13 13 19 20 25 25 25 27 28 2
6 8 9 9 10 11 11 13 17 21 24 25 25 28 3
5 7 13 14 14 15 16 18 19 20 23 23 25 25 1
3 5 9 10 11 12 19 20 21 22 22 23 24 25 0
0 0 2 2 4 7 8 13 14 20 21 25 26 26 3
0 2 3 3 4 6 7 8 19 20 21 23 25 27 1
0 0 2 7 16 16 19 20 21 23 25 27 33 33 2
4 4 5 7 7 11 14 20 21 22 23 25 29 30 3
2 4 7 8 9 10 11 12 13 15 18 24 27 31 3
2 3 4 4 5 11 12 20 21 22 23 23 25 27 1
3 3 4 6 6 7 9 10 11 15 25 29 31 32 3
2 6 8 9 9 10 11 13 19 21 24 30 30 33 3
0 0 1 2 4 5 7 7 10 11 13 16 24 27 3
0 4 8 11 14 16 17 17 18 18 21 27 32 33 5
3 4 5 6 6 10 11 12 19 20 23 23 24 25 0
4 9 9 10 13 16 22 25 25 26 27 31 32 33 6
2 5 6 14 15 17 17 19 20 22 24 27 27 28 3
0 0 2 4 7 7 11 13 14 15 17 19 24 25 2
4 4 5 5 11 14 15 18 19 20 20 23 26 26 2
0 8 8 10 14 17 20 21 21 22 23 24 29 33 4
4 6 9 11 13 13 22 24 26 27 30 31 32 32 3
0 5 6 6 6 7 11 12 14 15 16 22 23 24 0
2 2 6 7 8 10 12 13 14 15 17 17 22 25 1
0 8 8 9 11 11 14 14 17 17 21 23 25 29 3
3 3 4 6 11 12 12 15 17 17 20 20 32 32 3
1 1 4 5 7 14 15 16 21 22 27 31 31 31 1
0 1 2 4 5 6 6 7 8 8 9 10 21 22 1
2 3 3 4 5 9 10 10 15 16 24 26 26 26 1
3 4 5 6 6 7 11 12 14 15 18 20 22 32 2
0 1 2 2 6 7 13 17 18 18 19 22 24 25 3
1 3 12 12 14 15 16 18 19 20 29 32 32 32 0
0 5 10 10 14 16 17 18 19 20 25 29 31 33 4
0 1 2 5 6 8 8 15 16 16 22 28 31 33 3
0 1 1 2 2 17 17 17 18 22 23 23 24 25 1
3 8 10 10 13 13 18 20 20 21 27 28 31 31 3
1 1 3 5 10 12 13 15 16 20 21 22 26 26 2
1 2 3 4 6 8 12 14 15 16 17 19 19 25 1
3 4 5 6 7 8 12 13 14 17 17 18 19 20 -1
0 3 4 4 7 8 12 12 13 16 21 22 24 28 4
4 4 6 7 7 11 12 14 14 21 22 22 30 30 3
1 3 3 11 11 13 13 14 15 16 18 19 20 27 1
4 7 12 14 16 17 17 22 23 25 25 26 30 30 3
2 3 3 8 8 14 17 18 18 19 20 22 23 28 3
3 4 9 10 10 13 14 18 19 19 20 21 22 24 2
4 4 6 7 8 10 11 14 18 21 22 24 25 26 1
2 2 3 5 5 7 7 7 19 19 20 24 25 26 1
0 1 2 6 8 10 12 18 21 22 23 23 24 25 1
1 4 5 5 5 8 10 12 13 25 27 32 32 32 3
0 1 2 7 8 8 8 12 13 18 20 20 21 22 1
10 11 14 15 16 18 19 20 22 22 23 24 25 27 0
2 3 4 8 12 13 13 15 17 19 23 24 25 32 2
1 3 5 13 14 15 15 16 17 20 21 22 26 26 0
2 8 9 9 11 11 13 15 22 25 26 26 26 32 3
1 2 5 6 9 10 13 14 15 17 20 21 24 27 3
10 11 13 13 13 16 16 16 18 19 21 23 25 32 2
3 3 7 10 10 11 12 14 15 16 21 23 24 25 1
4 5 6 8 8 9 13 13 13 14 15 21 22 23 0
3 3 3 5 5 5 10 12 19 21 22 24 25 26 1
6 6 11 12 13 16 16 18 20 22 22 24 25 28 2
0 0 1 2 3 3 5 7 11 13 15 18 19 21 2
6 6 7 8 9 11 14 15 16 18 20 24 26 31 2
0 0 1 3 4 5 9 9 16 21 23 24 25 32 2
2 4 9 9 11 12 15 16 20 21 22 24 25 30 2
4 5 5 13 14 15 16 16 22 23 24 24 24 25 1
5 5 10 11 18 18 18 20 21 22 23 32 32 32 0
0 2 4 5 7 7 9 10 11 21 22 24 25 29 2
1 3 4 8 13 14 14 15 21 26 27 30 30 33 4
1 2 2 3 6 6 11 12 13 19 20 24 25 26 0
2 4 9 9 10 12 17 18 22 25 30 32 32 33 4
3 6 8 13 20 20 21 23 24 24 26 26 26 32 2
0 0 1 2 7 8 10 14 14 17 18 19 19 32 3
1 1 2 6 7 8 8 12 12 21 25 26 27 33 3
7 9 9 10 15 16 22 22 23 24 24 24 30 30 2
7 9 12 12 13 14 16 17 19 20 22 24 31 32 3
1 4 5 10 12 14 16 16 16 21 23 24 26 32 3
1 4 7 9 9 11 13 15 16 18 21 26 31 32 5
3 7 9 11 12 15 21 22 22 27 28 30 31 33 6
4 12 14 15 18 19 22 23 25 27 30 30 31 32 4
0 0 2 5 6 7 12 14 15 21 22 23 29 32 2
1 2 2 4 5 6 12 13 20 20 20 25 29 29 1
4 6 7 8 10 13 15 16 22 24 25 26 29 29 2
1 2 10 12 12 13 14 20 21 23 23 23 33 33 1
1 4 5 9 10 12 12 19 20 25 26 28 30 32 3
6 11 11 12 12 13 22 22 22 23 24 24 25 26 0
0 1 1 4 6 7 8 8 8 11 13 21 23 27 2
2 3 5 6 7 8 11 12 13 14 14 15 19 24 2
4 4 6 7 11 12 16 21 22 24 24 25 29 29 3
3 6 7 8 8 9 11 11 12 12 13 16 27 29 3
2 3 4 4 5 10 12 20 21 23 24 28 28 30 2
5 8 8 12 13 15 15 18 19 20 20 21 29 31 2
7 7 11 11 14 14 15 16 16 19 19 24 28 30 2
1 2 3 4 4 5 9 9 11 21 22 23 33 33 1
0 1 3 3 3 5 10 15 16 17 22 25 26 32 2
10 11 12 13 13 13 18 18 23 24 25 31 33 33 0
1 2 2 4 4 5 6 7 20 20 21 21 22 32 1
2 3 4 4 9 15 16 18 21 21 22 23 28 30 3
1 2 3 4 7 10 11 12 16 19 19 21 30 30 2
1 9 9 10 15 16 22 23 24 24 25 30 30 33 2
1 2 3 5 6 8 9 22 23 24 24 28 31 33 3
1 3 5 11 11 11 12 12 14 15 15 15 15 16 0
2 2 3 9 13 13 14 15 20 24 25 27 30 31 4
1 1 2 3 4 5 10 10 13 13 25 26 31 33 2
0 7 8 9 11 12 13 13 15 21 25 26 28 32 3
5 7 7 10 10 12 13 14 14 16 20 20 25 30 2
0 0 2 5 7 13 15 16 22 23 24 30 30 30 1
1 2 4 6 6 7 7 8 13 14 15 26 29 29 1
3 4 4 6 7 10 14 20 21 22 24 25 26 32 2
1 5 12 13 16 17 21 21 22 23 23 24 26 31 3
2 3 4 12 13 15 15 20 22 23 23 27 30 32 2
4 4 6 6 7 8 11 18 20 21 22 23 24 25 1
1 1 3 6 7 8 14 18 19 20 22 27 33 33 2
3 5 8 9 13 15 16 17 19 21 26 27 28 30 4
12 13 14 18 18 18 19 19 21 22 23 23 24 25 -1
1 1 2 3 8 8 12 14 16 18 19 20 20 22 1
2 3 4 4 5 6 7 14 15 16 23 23 24 25 0
2 3 4 5 5 10 11 12 15 16 25 25 27 31 1
2 6 6 13 16 16 17 17 18 19 22 23 24 27 2
0 2 2 8 8 11 13 14 15 20 24 30 30 31 3
2 3 3 4 4 5 11 12 13 19 19 23 24 25 -1
0 1 2 7 7 7 12 13 14 15 16 16 16 27 0
0 4 4 4 5 10 11 16 17 17 22 22 24 24 2
0 2 2 5 6 7 9 10 11 21 21 22 23 24 0
4 6 6 9 10 22 22 24 24 25 26 28 31 32 3
2 9 10 11 15 16 17 18 22 26 31 31 32 33 3
0 4 5 7 12 15 15 17 18 19 24 27 29 33 5
1 2 2 3 8 8 10 15 16 20 20 24 26 28 2
5 6 7 9 10 11 11 14 14 16 23 25 32 32 1
3 4 6 6 7 11 11 12 16 18 18 19 30 30 3
4 4 5 5 8 11 12 15 18 19 19 20 27 31 3
4 6 7 8 12 14 15 18 24 25 25 26 28 28 2
1 1 3 11 12 13 15 15 17 18 19 24 25 26 1
0 0 1 7 8 10 12 19 21 21 21 24 25 26 1
1 3 4 6 8 11 12 13 13 14 14 15 21 21 1
10 13 14 14 15 15 16 17 18 18 19 29 30 32 3
6 6 10 13 13 15 15 21 21 23 26 27 27 32 3
0 2 3 6 8 9 10 13 16 17 23 25 27 31 4
0 1 3 5 5 11 15 18 19 20 21 25 26 29 3
0 2 2 3 4 4 5 15 16 20 21 21 22 23 1
1 5 10 12 12 14 17 19 20 22 26 27 30 32 5
1 2 2 5 7 9 11 16 22 23 25 26 28 33 3
0 1 2 5 17 17 18 19 19 19 22 23 33 33 1
4 7 7 10 11 11 12 16 17 17 21 25 25 25 2
1 3 3 7 9 10 19 20 24 24 25 26 31 32 3
1 3 7 11 15 16 17 23 23 24 25 28 33 33 2
0 4 4 6 6 12 13 15 16 18 18 19 21 22 3
3 4 15 15 16 17 20 21 22 24 24 26 32 32 1
1 1 2 4 5 9 10 11 12 15 15 20 22 24 2
3 3 6 16 16 21 22 25 26 26 28 28 29 32 3
2 2 5 6 7 12 13 15 16 17 18 23 23 24 1
1 2 2 4 5 5 13 14 15 15 18 19 19 21 2
8 9 10 11 13 14 15 16 17 19 19 27 27 27 0
1 2 6 17 18 19 20 23 24 25 26 26 32 32 1
4 4 4 6 9 9 11 13 13 20 23 24 30 31 3
8 10 13 13 14 18 20 22 25 26 27 27 31 33 4
12 13 18 18 20 21 21 22 23 24 25 26 29 29 1
6 6 7 7 10 12 12 14 15 16 19 21 23 29 2
1 2 2 5 7 9 9 11 13 14 14 23 31 31 3
6 8 12 13 14 16 17 17 20 25 25 26 26 26 1
0 4 7 7 12 18 20 20 20 21 28 28 30 31 4
1 3 3 5 13 14 14 15 18 19 20 23 29 29 1
5 8 10 11 12 12 14 14 15 21 27 31 33 33 3
1 2 3 4 5 6 6 10 11 12 15 16 17 21 0
3 4 5 6 8 12 16 16 17 21 23 28 29 32 3
0 2 3 6 7 9 10 10 13 21 23 28 29 33 4
7 8 12 14 17 17 20 21 21 22 22 23 24 26 1
5 5 7 7 7 13 15 17 19 21 27 28 32 33 3
3 5 10 10 12 14 18 19 21 23 25 27 30 32 3
2 2 2 5 6 6 7 16 16 21 23 24 25 30 1
1 1 3 3 6 7 8 11 12 12 14 15 18 20 2
3 4 7 10 10 10 12 13 16 19 19 22 24 24 2
0 0 1 1 2 2 4 21 21 22 23 23 31 31 0
2 3 3 6 7 10 14 16 28 28 29 30 32 33 4
0 0 1 2 3 4 4 5 20 20 22 23 23 24 1
1 2 2 2 14 16 17 21 21 22 22 23 27 28 2
1 2 3 10 12 13 14 15 18 19 20 20 21 22 0
3 11 12 13 16 17 19 20 22 22 23 30 30 32 2
5 6 7 12 13 14 15 15 17 17 22 25 25 26 1
3 3 3 3 5 7 13 15 20 21 25 28 29 30 3
1 1 3 6 7 8 14 18 19 20 22 27 33 33 2
2 3 4 5 6 6 7 7 7 8 15 17 19 19 0
0 3 10 10 11 14 15 16 17 19 21 27 29 33 4
1 2 4 6 7 14 15 15 16 20 22 32 32 32 2
5 5 7 11 12 14 14 14 19 21 22 24 29 31 2
3 4 6 7 8 9 11 12 14 16 17 17 18 20 2
2 6 9 10 11 12 16 17 17 20 22 28 29 30 4
2 4 5 6 6 7 7 10 10 13 13 19 22 23 2
3 4 5 6 6 7 18 19 20 23 24 24 30 30 1
0 3 7 7 10 13 15 16 16 19 20 23 23 25 3
3 4 4 6 7 10 14 21 22 24 25 26 31 32 3
4 5 7 8 10 20 21 21 22 22 26 31 32 32 2
0 4 6 9 9 11 15 15 17 21 22 23 26 29 3
5 6 12 13 15 18 20 21 21 22 22 23 25 25 1
0 2 3 4 4 5 6 9 10 11 21 21 22 23 0
0 5 7 9 11 13 14 21 22 25 25 27 30 31 3
4 4 5 6 6 7 11 13 15 20 20 20 23 25 1
2 3 6 8 10 10 11 12 12 12 14 22 22 25 2
2 3 4 6 10 12 13 15 17 18 19 23 24 28 3
2 6 8 10 12 15 16 19 20 20 21 22 25 26 3
2 8 8 8 9 9 10 18 18 24 25 26 30 30 1
4 4 6 7 10 10 12 15 16 17 21 25 27 27 2
2 3 6 9 11 14 15 20 21 24 25 27 27 28 3
4 5 8 11 12 13 16 16 19 21 21 22 24 26 2
1 3 5 11 12 12 15 16 17 20 22 23 30 33 3
0 1 2 3 4 13 13 14 15 16 22 23 24 24 0
1 3 9 9 13 15 15 21 21 22 22 23 27 28 2
2 11 12 14 14 15 19 23 23 25 30 30 32 32 3
2 5 6 7 8 9 11 12 13 14 15 19 25 33 3
2 3 4 6 6 8 8 9 9 12 13 19 20 21 1
3 3 4 4 9 10 11 13 22 26 31 31 32 32 2
1 3 3 3 10 11 12 12 13 20 23 24 25 26 1
2 3 5 5 9 11 12 12 18 19 23 24 25 32 2
0 0 2 7 10 11 11 14 18 24 29 29 32 32 4
9 9 10 13 13 14 15 16 17 24 25 26 31 31 1
1 2 3 3 11 12 14 20 21 22 25 29 29 33 2
0 3 4 6 7 8 11 11 11 13 13 15 24 24 1
2 2 4 4 12 13 14 18 19 20 21 21 22 26 1
1 2 5 5 7 7 10 11 12 14 14 16 28 28 2
4 10 11 13 14 17 17 19 20 21 23 24 24 25 1
2 3 4 5 6 6 7 7 8 15 17 18 19 19 0
1 2 3 4 5 6 6 10 11 15 16 17 19 20 1
3 6 8 9 9 10 13 18 19 20 21 21 22 33 3
8 8 9 9 10 12 17 18 18 18 25 26 29 30 2
0 0 2 4 5 9 11 15 24 25 26 32 33 33 2
7 10 10 13 13 14 16 16 16 21 22 29 29 32 2
2 2 3 5 5 6 11 11 14 16 19 21 24 25 3
0 1 2 3 3 6 7 7 7 8 13 22 27 31 2
0 0 3 4 11 11 18 19 20 20 21 23 32 32 2
2 3 5 6 7 13 14 15 16 16 18 18 25 27 1
1 1 1 2 2 3 4 4 5 7 10 11 22 32 2
0 1 4 5 6 8 12 13 22 23 24 26 26 27 1
1 2 5 6 7 10 12 15 19 20 20 20 24 24 1
0 0 0 3 4 13 15 17 17 19 23 25 26 31 2
1 12 13 17 18 18 19 20 21 25 26 31 31 32 2
1 2 3 4 4 4 9 10 10 17 17 17 30 30 0
3 5 6 10 10 12 15 16 19 19 20 22 23 29 3
3 4 6 6 11 13 14 15 16 18 20 24 26 33 2
0 1 1 4 5 7 13 14 17 17 19 20 22 31 3
1 4 5 6 11 12 23 24 28 29 29 31 33 33 2
1 2 2 3 3 4 6 7 24 25 26 30 33 33 0
0 2 10 10 12 12 13 14 14 16 16 22 23 26 2
8 8 10 13 14 20 22 23 24 24 25 25 28 28 2
2 4 5 7 11 12 16 16 20 22 25 25 28 28 3
1 1 3 4 4 6 7 11 11 13 14 15 18 19 2
2 2 2 5 11 11 12 13 14 14 18 23 23 23 1
5 6 10 12 14 15 15 23 23 23 24 25 26 30 1
2 3 4 10 11 13 14 19 20 23 23 25 27 27 2
3 4 5 8 12 13 14 19 19 20 22 24 24 30 1
4 5 15 16 17 19 19 22 27 29 29 29 30 32 2
2 11 13 13 14 14 17 17 18 18 21 23 25 27 3
3 12 13 14 14 15 16 16 18 18 18 22 23 32 1
1 1 6 7 7 15 15 17 22 23 24 26 28 32 3
0 1 2 6 6 12 16 20 20 22 23 24 27 27 1
2 7 8 10 11 12 13 14 16 16 17 21 22 31 2
0 1 2 4 7 9 11 14 14 15 18 19 31 32 3
3 5 6 6 7 13 14 17 17 19 20 21 29 31 2
1 2 2 5 6 7 8 11 12 13 21 23 30 30 1
6 6 9 10 13 13 15 15 19 21 21 27 27 32 3
1 1 5 6 6 8 10 13 14 14 18 21 32 33 4
3 8 9 13 15 15 19 20 21 23 25 26 28 29 4
1 2 3 4 4 4 10 10 17 17 17 28 30 30 0
2 3 3 6 7 8 8 16 20 23 25 28 29 30 4
1 5 7 9 11 15 19 19 22 23 23 24 31 31 2
1 3 4 4 5 8 11 14 14 17 22 23 24 25 3
6 10 15 18 20 21 21 22 23 24 25 26 26 28 3
3 10 10 10 11 13 14 17 20 21 22 22 23 23 2
1 2 3 4 5 12 12 15 17 20 23 24 33 33 2
2 3 4 5 6 7 8 10 11 16 16 22 24 24 1
1 2 3 4 5 6 12 13 14 15 16 17 18 18 -1
6 7 8 9 11 18 19 20 23 24 24 24 25 33 0
1 3 3 6 13 14 14 17 23 25 25 26 31 32 4
1 2 3 3 4 5 13 14 18 18 18 19 19 27 0
0 1 6 9 10 11 15 16 17 22 23 24 27 27 0
0 1 1 2 2 2 3 4 8 8 17 21 22 23 0
0 1 2 7 10 13 15 16 17 21 23 28 33 33 2
1 2 3 4 5 12 13 16 19 21 27 27 30 31 2
3 4 13 14 17 20 20 21 25 29 29 31 32 32 3
1 1 1 2 3 6 6 6 7 14 15 20 21 22 0
10 12 15 16 17 18 19 20 21 23 24 27 27 27 1
13 14 15 17 17 19 20 21 23 23 24 24 25 26 0
0 1 5 13 15 19 19 20 22 22 23 24 24 33 2
3 6 10 11 12 15 17 18 20 30 31 31 32 32 2
7 7 8 8 14 14 16 19 20 22 22 24 25 31 3
4 9 10 12 14 16 17 19 21 23 23 24 33 33 3
3 3 5 5 5 6 12 13 14 14 18 18 24 25 1
0 3 4 6 7 7 10 12 13 16 17 21 28 30 4
1 6 7 8 8 13 20 23 24 24 26 31 32 32 3
4 9 9 10 11 12 14 15 21 21 21 22 23 25 1
4 4 6 13 14 14 15 15 18 18 21 21 21 29 1
2 5 13 16 16 19 19 23 24 27 27 28 31 33 4
2 2 3 5 5 6 10 12 14 15 16 23 24 25 1
5 6 7 7 7 8 8 11 12 13 21 21 22 23 0
3 5 11 11 11 12 12 14 15 15 15 15 16 23 0
0 0 4 5 5 6 14 15 16 17 17 20 25 31 2
0 3 4 4 4 5 5 6 11 14 15 18 20 22 2
3 4 6 12 12 14 15 16 17 17 17 22 23 24 0
7 10 15 18 21 21 24 25 25 26 26 26 32 33 4
3 10 10 11 13 14 14 15 16 19 22 24 27 31 3
2 3 6 8 9 11 12 12 13 13 15 16 17 21 2
0 1 6 6 7 10 13 13 14 17 17 21 23 28 3
18 18 18 18 20 21 22 24 24 25 26 33 33 33 0
0 1 2 4 9 11 13 14 15 17 17 19 19 21 1
1 3 6 11 11 12 12 18 18 19 20 21 24 33 2
2 3 3 9 12 14 16 18 21 24 24 27 28 29 5
3 4 4 8 13 14 14 15 15 19 30 31 33 33 3
0 0 1 3 5 7 7 8 16 17 20 21 29 29 3
3 3 4 4 6 8 19 20 27 28 30 31 32 33 4
1 4 5 13 15 16 17 18 19 20 23 24 27 31 2
1 2 2 3 3 4 11 11 19 20 23 23 23 25 0
2 4 5 10 16 18 19 22 23 28 29 30 31 32 5
5 6 16 17 18 18 19 21 21 23 23 29 31 31 3
1 2 3 5 5 6 10 14 15 20 23 23 23 29 2
3 4 4 5 13 14 15 15 18 22 23 23 24 29 2
11 11 11 11 13 14 21 22 23 23 25 25 30 30 1
1 2 3 3 4 11 14 15 18 23 23 24 25 26 1
0 1 2 2 5 8 14 19 20 25 30 30 31 33 4
0 1 2 3 6 7 8 21 21 22 22 23 23 25 0
0 0 2 3 4 7 8 10 12 13 13 14 14 15 0
1 3 5 13 14 14 16 18 19 20 23 27 29 29 2
1 5 5 9 11 15 15 16 17 17 21 22 22 23 1
18 19 20 21 22 23 25 25 27 27 27 29 29 31 0
2 3 3 7 9 12 17 19 20 23 24 26 29 30 5
1 2 2 3 3 5 7 11 11 12 15 19 21 21 2
0 11 12 13 14 15 15 17 17 20 21 21 23 24 2
0 3 13 14 14 16 21 22 25 26 26 27 29 29 3
4 4 4 7 14 14 14 23 23 24 25 26 31 31 0
2 2 3 6 7 8 11 12 12 19 19 21 22 23 1
5 14 15 18 18 20 21 22 23 24 25 28 29 29 1
0 2 4 10 11 13 13 13 15 19 22 25 25 25 2
4 6 9 9 11 11 12 18 22 24 24 32 33 33 3
2 5 11 12 12 13 13 14 15 16 20 21 22 22 1
12 14 15 15 18 19 21 21 22 22 24 25 26 32 2
1 2 2 2 12 15 15 17 17 23 25 26 26 31 2
2 3 4 5 5 5 16 16 21 22 23 24 25 25 0
2 3 3 4 6 9 9 9 10 18 22 22 23 25 2
1 1 1 6 7 8 13 13 15 16 17 24 25 26 -1
2 3 3 4 6 11 12 13 13 14 15 22 23 24 0
0 2 9 10 12 12 13 13 20 20 22 29 30 30 3
4 6 6 6 13 16 16 20 23 24 24 26 27 28 3
1 1 2 3 6 6 10 12 13 14 19 23 29 29 2
0 3 4 7 11 11 14 14 16 16 24 25 25 26 2
3 4 4 4 5 8 11 19 25 28 30 31 32 33 5
6 7 7 9 9 16 16 17 20 20 22 23 23 24 2
2 3 3 12 13 15 15 17 21 21 21 23 23 24 2
0 1 2 3 4 13 13 14 15 16 22 23 24 27 0
0 1 4 8 12 14 17 19 19 22 24 27 31 33 4
2 5 10 12 13 14 15 15 24 25 30 31 33 33 3
1 3 4 5 11 11 12 13 21 22 22 23 25 25 1
2 2 3 6 6 16 16 20 20 20 22 23 24 33 1
0 1 2 5 9 10 11 18 19 23 24 26 26 26 1
2 2 3 6 11 12 13 14 18 23 24 28 32 33 4
2 4 12 12 13 15 17 18 23 23 25 32 32 33 3
2 3 5 9 10 16 21 21 21 22 23 25 26 26 2
1 3 10 11 12 14 15 16 19 21 26 26 26 30 1
3 9 12 14 15 17 18 22 24 28 31 32 33 33 4
4 9 16 18 18 19 19 20 20 21 23 27 28 32 3
4 10 11 11 12 19 21 22 22 25 26 27 30 32 3
4 5 15 16 17 19 19 20 22 23 29 29 29 30 1
1 1 2 3 3 5 7 12 12 13 21 21 25 26 2
0 1 1 1 5 6 8 10 13 13 21 22 24 24 2
1 3 13 14 15 15 15 17 19 20 22 27 31 33 3
1 4 5 8 12 13 19 20 20 21 21 30 31 33 3
1 1 1 8 16 16 17 17 18 24 24 30 31 31 2
1 2 2 3 15 18 18 21 21 27 28 30 32 33 4
1 6 8 9 12 14 14 15 16 19 20 23 30 32 3
2 3 4 5 6 6 11 11 15 16 16 17 17 25 1
1 7 8 9 10 11 11 12 15 17 22 24 26 32 3
0 2 9 10 10 12 18 21 22 22 24 25 32 33 3
3 4 5 5 11 11 12 15 21 21 22 25 30 32 4
3 4 4 6 6 13 16 17 19 20 20 22 22 31 3
0 2 4 5 5 8 8 10 16 21 22 27 28 29 4
4 5 5 11 11 11 21 23 23 23 25 25 33 33 1
2 2 2 4 5 10 11 15 16 17 21 22 23 31 1
2 5 12 18 19 21 22 22 26 30 30 31 31 31 3
0 2 2 6 11 14 16 17 18 18 18 22 24 25 3
1 2 3 6 7 10 10 13 21 21 23 23 23 24 1
0 1 2 14 15 15 18 19 19 20 21 24 25 30 1
5 5 10 12 16 16 19 19 21 21 22 22 23 23 1
4 4 5 6 6 7 7 8 20 21 22 23 24 25 -1
0 1 5 10 11 11 13 14 15 18 21 22 32 32 2
2 3 4 5 13 14 15 15 16 22 28 28 28 29 1
0 2 2 3 15 22 23 25 28 29 29 30 32 33 4
1 2 10 12 12 13 14 20 21 23 23 24 33 33 2
0 1 2 9 10 11 18 19 21 23 24 26 26 26 1
3 4 5 6 7 8 10 11 12 13 19 19 24 25 0
6 9 10 11 12 13 16 21 23 23 29 29 32 33 3
2 3 4 12 12 14 15 15 16 18 20 21 23 33 1
3 4 4 6 7 12 13 13 14 14 17 21 22 23 1
0 1 6 7 7 8 13 15 18 19 21 22 23 33 2
3 5 6 9 10 12 20 22 24 30 30 31 32 33 4
3 3 4 5 6 7 8 11 12 14 14 16 21 22 1
11 18 18 20 21 21 21 22 23 24 25 26 29 29 1
2 3 6 6 8 10 15 15 19 20 21 24 24 24 1
2 2 5 10 10 16 19 20 20 21 21 21 25 25 2
2 3 5 8 8 11 19 19 21 22 23 23 30 32 3
1 1 4 5 8 13 15 16 17 20 20 22 22 23 2
1 2 3 7 11 12 13 15 21 24 24 26 26 27 2
0 1 2 4 4 5 12 15 19 20 21 22 26 27 3
1 3 4 4 6 14 20 21 23 23 24 31 31 32 3
2 3 4 5 6 8 8 13 13 14 19 19 19 30 1
0 1 2 9 10 11 13 14 14 16 17 18 24 25 1
0 1 2 2 4 7 7 7 11 11 12 21 21 32 1
0 0 2 3 5 6 6 7 10 11 28 28 28 32 1
1 4 5 6 7 8 9 10 13 14 21 24 26 26 2
5 5 6 7 8 9 10 13 14 17 19 20 22 28 2
3 3 4 5 5 7 14 18 18 19 26 27 31 32 4
1 3 6 7 8 9 12 14 20 24 24 31 32 33 3
1 6 6 7 7 8 8 9 10 11 23 23 24 26 0
3 4 5 7 10 11 14 18 20 21 22 24 25 26 1
1 2 3 3 4 6 6 7 7 10 14 14 23 25 2
1 2 9 9 10 18 19 20 22 23 27 28 28 32 2
2 4 6 11 11 15 16 18 19 20 21 21 22 23 1
5 7 9 9 13 13 15 17 21 22 25 29 31 32 3
2 2 3 6 7 10 13 16 16 20 23 23 25 31 4
0 1 5 6 7 11 12 12 13 13 14 15 16 17 0
0 1 2 4 5 12 18 18 22 23 23 27 28 32 3
1 5 5 8 8 11 17 17 19 19 22 24 24 29 3
2 3 5 5 10 12 13 14 15 16 22 23 24 33 1
2 3 3 4 6 11 14 18 23 25 26 29 29 33 4
0 2 4 5 7 7 10 19 21 21 24 25 30 33 3
10 11 12 14 15 15 17 18 19 22 23 24 25 26 1
0 2 3 5 7 11 15 16 17 19 25 27 27 28 3
2 6 10 11 13 15 16 18 19 20 20 28 31 31 3
5 5 10 11 12 15 16 18 19 20 24 24 24 33 0
1 4 7 10 11 16 17 20 20 20 22 22 25 31 3
2 3 3 4 6 7 8 11 13 15 24 24 27 29 2
2 3 5 8 8 10 10 12 12 13 14 16 26 33 3
2 2 4 5 5 5 6 7 8 8 14 22 23 24 1
2 3 4 6 7 10 11 14 15 18 27 27 30 33 2
7 7 7 8 12 12 13 13 14 15 16 22 23 24 0
2 3 6 7 10 14 16 19 26 28 28 29 30 33 4
4 4 10 12 15 18 19 25 25 31 31 32 32 33 3
1 2 9 10 12 13 16 17 23 24 24 26 28 29 3
1 3 5 9 9 10 10 13 14 15 15 23 31 32 3
5 5 10 11 12 13 15 19 19 20 24 24 25 28 2
0 2 2 6 7 13 14 18 20 20 22 22 23 28 3
8 8 11 11 15 16 17 21 28 29 31 32 32 33 3
0 5 6 13 14 15 18 19 20 22 24 24 29 29 1
4 5 5 9 10 10 12 14 18 19 19 19 23 33 3
7 7 9 11 12 16 16 20 20 23 24 32 33 33 3
1 1 4 4 5 11 11 11 14 19 21 23 25 32 2
1 2 4 4 5 10 12 14 15 18 21 23 27 28 3
1 2 3 6 10 17 18 22 24 25 26 29 30 33 4
0 20 21 21 21 23 23 24 27 29 30 31 32 33 5
1 5 7 8 11 20 21 21 22 23 24 25 26 28 2
1 2 2 6 16 22 23 24 25 27 30 31 32 33 5
0 6 6 7 11 12 14 20 22 22 23 24 29 29 2
7 8 13 13 15 15 15 21 22 22 23 23 24 33 0
5 6 6 8 10 12 18 18 19 22 24 26 30 30 3
2 3 14 14 15 16 16 16 23 24 24 27 27 32 2
1 3 4 5 7 9 10 12 14 15 22 22 25 32 3
1 3 4 6 12 14 15 16 17 17 17 22 23 27 2
1 2 3 4 5 7 14 19 19 21 23 29 30 32 3
0 7 11 16 17 18 19 20 24 26 28 31 31 32 3
1 2 2 2 6 7 11 12 15 17 21 22 24 26 3
4 6 7 8 14 16 16 21 22 23 27 28 31 32 3
3 5 10 11 12 13 14 14 15 16 21 23 30 30 1
4 6 7 8 16 16 21 22 23 26 27 28 31 32 3
0 0 3 8 9 11 13 14 21 22 24 27 30 32 4
1 2 7 7 8 9 9 11 11 12 15 24 32 32 3
3 4 4 5 5 7 11 16 18 22 24 25 27 28 4
3 3 7 14 16 16 17 17 18 18 19 20 21 27 2
6 7 11 12 13 13 14 15 20 23 25 25 25 33 1
3 6 10 12 13 14 15 17 17 20 21 23 23 33 2
0 1 1 4 8 15 15 16 17 19 20 23 27 31 4
3 3 5 5 5 12 13 14 17 18 18 24 25 27 1
2 5 12 15 15 16 17 20 23 25 25 26 26 26 3
0 0 1 2 3 4 7 8 12 13 13 14 14 15 0
2 7 9 10 13 13 21 21 22 23 24 28 29 33 3
0 0 1 2 5 14 17 18 20 20 23 23 26 26 3
2 7 11 13 14 16 17 18 18 18 20 23 30 30 3
4 5 11 13 15 15 16 19 20 21 22 23 31 31 2
1 2 5 13 14 17 19 27 27 28 29 30 32 32 4
13 14 15 16 17 19 20 20 21 22 23 24 25 26 0
1 2 2 10 12 13 13 15 15 18 22 24 26 26 3
3 3 3 5 5 5 10 12 21 22 24 25 25 26 1
1 2 4 5 5 7 7 12 14 15 15 16 22 22 2
2 3 4 5 5 6 10 11 18 19 20 26 26 27 1
0 1 4 4 5 10 11 11 12 20 21 21 23 25 2
4 5 8 9 10 12 13 14 20 21 21 28 28 28 1
1 2 5 9 10 10 13 13 17 23 25 26 29 31 4
0 1 1 2 2 3 4 5 27 31 31 32 33 33 1
2 3 6 9 11 11 14 15 16 16 22 23 32 32 2
0 4 5 5 7 7 11 17 20 20 24 30 33 33 4
0 1 2 4 9 10 14 16 20 20 23 24 27 31 2
1 3 3 3 8 8 10 11 17 18 19 20 30 32 2
1 4 6 10 10 11 24 26 27 27 31 32 33 33 3

ShantenAnalysis.scala

import scala.collection.mutable.ArrayBuffer
import scala.io.Source

object ShantenAnalysis {

    val NUM_PIDS = 9 * 3 + 7
    var mentsus:ArrayBuffer[Array[Int]] = null

    def main(args: Array[String]) {
        mentsus = createMentsus()
        val src = Source.fromFile("shanten_benchmark_data.num.txt")
        for (line <- src.getLines) {
            val sline = line.stripLineEnd
            val row = sline split " "
            val pids = row.slice(0, row.length - 1).map(_.toInt)
            val expectedShantensu = row(row.length - 1).toInt
            val actualShantensu = calculateShantensu(pids)
            if(actualShantensu != expectedShantensu) {
                throw new RuntimeException(
                    "Shantensu mismatch: %d != %d: %s" format (actualShantensu, expectedShantensu, sline))
            }
        }
    }

    def createMentsus():ArrayBuffer[Array[Int]] = {
        var mentsus = new ArrayBuffer[Array[Int]]()
        var pid = 0
        while(pid < NUM_PIDS) {
            mentsus.append(Array(pid, pid, pid))
            pid += 1
        }
        var t = 0
        while(t < 3) {
            var n = 0
            while(n < 7) {
                val pid = t * 9 + n
                mentsus.append(Array(pid, pid + 1, pid + 2))
                n += 1
            }
            t += 1
        }
        return mentsus
    }

    def calculateShantensu(pids:Seq[Int]):Int = {
        val countVector = pidsToCountVector(pids)
        return calculateShantensuInternal(countVector, new Array[Int](NUM_PIDS), 4, 0, Int.MaxValue)
    }

    def pidsToCountVector(pids:Seq[Int]):Array[Int] = {
        var countVector = new Array[Int](NUM_PIDS)
        var i = 0
        while(i < pids.length) {
            countVector(pids(i)) += 1
            i += 1
        }
        return countVector
    }

    def calculateShantensuInternal(
            currentVector:Array[Int],
            targetVector:Array[Int],
            leftMentsu:Int,
            minMentsuId:Int,
            foundMinShantensu:Int):Int = {
        var minShantensu = foundMinShantensu
        if(leftMentsu == 0) {
            var pid = 0
            while(pid < NUM_PIDS) {
                targetVector(pid) += 2
                if(isValidTargetVector(targetVector)) {
                    val shantensu = calculateShantensuLowerbound(currentVector, targetVector)
                    minShantensu = minShantensu.min(shantensu)
                }
                targetVector(pid) -= 2
                pid += 1
            }
        } else {
            var mentsuId = minMentsuId
            while (mentsuId < mentsus.length) {
                addMentsu(targetVector, mentsuId)
                val lowerbound = calculateShantensuLowerbound(currentVector, targetVector)
                if(isValidTargetVector(targetVector) && lowerbound < foundMinShantensu) {
                    val shantensu = calculateShantensuInternal(
                        currentVector, targetVector, leftMentsu - 1, mentsuId, minShantensu)
                    minShantensu = minShantensu.min(shantensu)
                }
                removeMentsu(targetVector, mentsuId)
                mentsuId += 1
            }
        }
        return minShantensu
    }

    def calculateShantensuLowerbound(currentVector:Array[Int], targetVector:Array[Int]):Int = {
        var count = 0
        var pid = 0
        while (pid < NUM_PIDS) {
            if(targetVector(pid) > currentVector(pid)) {
                count += targetVector(pid) - currentVector(pid)
            }
            pid += 1
        }
        return count - 1
    }

    def isValidTargetVector(targetVector:Array[Int]):Boolean = {
        return targetVector.forall(_ <= 4)
    }

    def addMentsu(targetVector:Array[Int], mentsuId:Int) = {
        var mentsu = mentsus(mentsuId)
        var i = 0
        while(i < mentsu.length) {
            targetVector(mentsu(i)) += 1
            i += 1
        }
    }

    def removeMentsu(targetVector:Array[Int], mentsuId:Int) = {
        var mentsu = mentsus(mentsuId)
        var i = 0
        while(i < mentsu.length) {
            targetVector(mentsu(i)) -= 1
            i += 1
        }
    }

}

yuizumi_shanten_analysis.js

var fs = require("fs");

var NUM_PIDS = 9 * 3 + 7;
var CHOWS = [0, 1, 2, 3, 4, 5, 6, 9, 10, 11, 12, 13, 14, 15, 18, 19, 20, 21, 22, 23, 24];

function calculateShantensu(pids) {
  var countVector = pidsToCountVector(pids);
  var targetVector = [];
  for (var i = 0; i < NUM_PIDS; ++i) {
    targetVector.push(0);
  }
  return calculateShantensuInternal(countVector, targetVector, 0, 4, 0, 1 / 0) - 1;
}

function pidsToCountVector(pids) {
  var countVector = [];
  for (var i = 0; i < NUM_PIDS; ++i) {
    countVector.push(0);
  }
  for (var i = 0; i < pids.length; ++i) {
    ++countVector[pids[i]];
  }
  return countVector;
}

function calculateShantensuInternal(vector0, vector1, current, numMeldsLeft, minMeldId, upperbound) {
  if (numMeldsLeft == 0) {
    minDelta = 2;
    for (var i = 0; i < NUM_PIDS; ++i) {
      if (vector0[i] >= vector1[i] + 2) {
        minDelta = 0;
        break;
      } else if (vector0[i] == vector1[i] + 1) {
        minDelta = 1;
      }
    }
    current += minDelta;
    return current < upperbound ? current : upperbound;
  } else {
    for (var i = minMeldId; i < NUM_PIDS; ++i) {
      if (vector1[i] >= 2) continue;
      var current1;
      if (vector0[i] <= vector1[i]) {
        current1 = current + 3;
      } else if (vector0[i] < vector1[i] + 3) {
        current1 = current + (vector1[i] + 3) - vector0[i];
      } else {
        current1 = current;
      }
      if (current1 < upperbound) {
        vector1[i] += 3;
        upperbound = calculateShantensuInternal(vector0, vector1, current1, numMeldsLeft - 1, i, upperbound);
        vector1[i] -= 3;
      }
    }

    var startChowId = minMeldId < NUM_PIDS ? 0 : minMeldId - NUM_PIDS;
    for (var chowId = startChowId; chowId < CHOWS.length; ++chowId) {
      var i = CHOWS[chowId];
      if (vector1[i] == 4 || vector1[i + 1] == 4 || vector1[i + 2] == 4) {
        continue;
      }
      current1 = current;
      if (vector0[i] <= vector1[i]) ++current1;
      if (vector0[i + 1] <= vector1[i + 1]) ++current1;
      if (vector0[i + 2] <= vector1[i + 2]) ++current1;
      if (current1 < upperbound) {
        ++vector1[i]; ++vector1[i + 1]; ++vector1[i + 2];
        upperbound = calculateShantensuInternal(vector0, vector1, current1, numMeldsLeft - 1, chowId + NUM_PIDS, upperbound);
        --vector1[i]; --vector1[i + 1]; --vector1[i + 2];
      }
    }
    return upperbound;
  }
}

fs.readFileSync("shanten_benchmark_data.num.txt").toString("utf-8").split(/\n/).forEach(function(line) {
  if (!line) return;
  var row = line.split(/ /);
  var pids = [];
  for (var i = 0; i < row.length - 1; ++i) {
    pids.push(parseInt(row[i]));
  }
  var expectedShantensu = parseInt(row[row.length - 1]);
  var actualShantensu = calculateShantensu(pids);
  if (actualShantensu != expectedShantensu) {
    throw "Shantensu mismatch: " + actualShantensu + " != " + expectedShantensu + ": " + line;
  }
});