Tag: programming
Blog Entry © Wednesday, December 24, 2025, by James Pate Williams, Jr. ID3 Decision Tree Metadata Parser
// ID3MetadataParser.cpp (c) December 2025
// by James Pate Williams, Jr.
#include "pch.h"
#define FILE_EOF 0
#define NO_ERROR 1
#define EMPTY_FILE 2
#define INVALID_LINE 3
#define MISSING_NAME 4
#define INVALID_NAME 5
#define INVALID_DESCRIPTION 6
#define MISSING_DESCRIPTION 7
#define INVALID_TYPE 8
#define MISSING_TYPE 9
#define INVALID_RANGE 10
#define INVALID_CATEGORICAL 11
#define INVALID_DOUBLE 12
#define INVALID_FLOAT 13
#define INVALID_INTEGER 14
#define INVALID_ROLE 15
#define MISSING_ROLE 16
enum AttributeType {
categorical, integer, doubleReal, FloatReal
};
typedef struct tagCategoricalAttribute {
std::string name = "";
std::string description = "";
std::vector<char> category;
} CategoricalAttribute, * PCategoricalAttribute;
typedef struct tagIntegerAttribute {
std::string name = "";
std::string description = "";
int loValue= -1, hiValue = -1;
} IntegerAttribute, * PIntegerAttribute;
typedef struct tagDoubleAttribute {
std::string name = "";
std::string description = "";
double loValue = -1.0, hiValue = -1.0;
} DoubleAttribute, * PDoubleAttribute;
typedef struct tagFloatAttribute {
std::string name = "";
std::string description = "";
float loValue = -1.0f, hiValue = -1.0f;
} FloatAttribute, * PFloatAttribute;
static bool parseName(
char line[],
int length,
int& errorCode,
int& index,
bool& feature,
std::string& name)
{
char* cptr1 = std::strstr(line, "#name: feature ");
char* cptr2 = std::strstr(line, "#name: target ");
if (cptr1 == nullptr && cptr2 == nullptr) {
errorCode = MISSING_NAME;
return false;
}
if (cptr1) {
feature = true;
index = static_cast<int>(strlen("#name: feature "));
}
else if (cptr2) {
feature = false;
index = static_cast<int>(strlen("#name: target "));
}
else {
errorCode = INVALID_NAME;
return false;
}
if (index >= static_cast<int>(strlen(line))) {
errorCode = INVALID_NAME;
return false;
}
if (line[index] >= L'A' && line[index] <= 'Z' ||
line[index] >= L'a' && line[index] <= 'z') {
bool first = true;
name = "";
while (index < strlen(line)) {
if (line[index] >= 'A' && line[index] <= 'Z' ||
line[index] >= 'a' && line[index] <= 'z' ||
line[index] == ' ') {
if (first)
name += line[index++];
else if (first &&
line[index] >= '0' &&
line[index] <= '9') {
first = false;
name += line[index++];
}
if (!first)
name += line[index++];
}
else if (!first) {
errorCode = INVALID_NAME;
return false;
}
}
}
errorCode = 0;
index = length;
return true;
}
static bool parseDescription(
char line[],
int length,
int& errorCode,
int& index,
std::string& description) {
char* cptr = std::strstr(line, "#description: ");
if (cptr == nullptr) {
errorCode = MISSING_DESCRIPTION;
return false;
}
int lengthDesc = static_cast<int>(
strlen("#description: "));
if (lengthDesc == length) {
errorCode = INVALID_DESCRIPTION;
return false;
}
index = lengthDesc;
while (index < length)
description += line[index++];
errorCode = 0;
return true;
}
static bool parseCategorical(
char line[],
int length,
int& errorCode,
int& index,
std::vector<char>& category) {
int delta = static_cast<int>(strlen("#type: categorical: {"));
char* cptr = line + delta - 1;
char ch = *cptr++;
while (ch != '}' && index < length) {
while (ch != ',' && index < length) {
if (ch == '}') {
if (index == length - 1)
break;
else {
errorCode = INVALID_TYPE;
return false;
}
}
category.push_back(ch);
index++;
break;
}
cptr++;
ch = *cptr;
}
if (category.size() != 0 && ch == '}') {
errorCode = 0;
return true;
}
else {
errorCode = INVALID_CATEGORICAL;
return false;
}
}
static bool parseDoubleRange(
char line[],
int length,
int& errorCode,
int& index,
double& hiDouble,
double& loDouble)
{
index = static_cast<int>(strlen("#type: doubleReal ["));
char ch = line[index++];
std::string doubleStr;
while (ch != ',' &&
index < static_cast<int>(strlen(line))) {
doubleStr.push_back(ch);
ch = line[index++];
}
if (doubleStr.size() == 0) {
errorCode = INVALID_DOUBLE;
return false;
}
try {
loDouble = std::stod(doubleStr);
doubleStr = "";
ch = line[index++];
while (ch != ']' && index < strlen(line)) {
doubleStr.push_back(ch);
ch = line[index++];
}
if (doubleStr.size() == 0) {
errorCode = INVALID_DOUBLE;
return false;
}
hiDouble = std::stod(doubleStr);
errorCode = 0;
return true;
}
catch (std::exception ex) {
errorCode = INVALID_DOUBLE;
return false;
}
errorCode = INVALID_RANGE;
return false;
}
static bool parseFloatRange(
char line[],
int length,
int& errorCode,
int& index,
float& hiFloat,
float& loFloat)
{
char ch = '\0';
std::string floatStr;
ch = line[index++];
while (ch != ',' && index < strlen(line)) {
floatStr.push_back(ch);
ch = line[index++];
}
if (floatStr.size() == 0) {
errorCode = INVALID_INTEGER;
return false;
}
else {
try {
loFloat = std::stof(floatStr);
floatStr = "";
ch = line[++index];
while (ch != ']' && index < strlen(line)) {
floatStr.push_back(ch);
ch = line[index++];
}
if (floatStr.size() == 0) {
errorCode = INVALID_FLOAT;
return false;
}
hiFloat = std::stof(floatStr);
errorCode = 0;
return true;
}
catch (std::exception ex) {
errorCode = INVALID_FLOAT;
return false;
}
}
errorCode = INVALID_RANGE;
return false;
}
static bool parseIntegerRange(
char line[],
int length,
int& errorCode,
int& index,
int& hiInteger,
int& loInteger) {
char ch = '\0';
int i = 0;
std::string integerStr;
ch = line[i++];
if (ch < '0' || ch > '9') {
errorCode = INVALID_INTEGER;
return false;
}
while (ch != ',' && index < length) {
integerStr.push_back(ch);
ch = line[i++];
index++;
}
if (integerStr.size() == 0) {
errorCode = INVALID_INTEGER;
return false;
}
else {
try {
loInteger = std::stoi(integerStr);
integerStr = "";
i = 0;
ch = line[i++];
ch = line[i++];
ch = line[i++];
index += 3;
while (
ch >= '0' && ch <= '9' &&
ch != ']' && index < length) {
integerStr.push_back(ch);
ch = line[i++];
index++;
}
if (integerStr.size() == 0) {
errorCode = INVALID_INTEGER;
return false;
}
hiInteger = std::stoi(integerStr);
errorCode = 0;
return true;
}
catch (std::exception ex) {
errorCode = INVALID_INTEGER;
return false;
}
}
errorCode = INVALID_RANGE;
return false;
}
static bool parseType(
char line[],
int length,
double& hiDouble,
double& loDouble,
float& hiFloat,
float& loFloat,
int& errorCode,
int& index,
int& hiInteger,
int& loInteger,
std::string& type,
std::vector<char>& alphabet) {
char* cptr = std::strstr(line, "#type: ");
if (cptr == nullptr) {
errorCode = MISSING_TYPE;
return false;
}
int lengthType = static_cast<int>(strlen("#type: "));
if (lengthType >= length) {
errorCode = INVALID_TYPE;
return false;
}
index = lengthType;
cptr = line + index;
if (std::strstr(cptr, "categorical {") != nullptr) {
if (parseCategorical(line, length, errorCode,
index, alphabet)) {
errorCode = 0;
type = "categorical";
return true;
}
else {
errorCode = INVALID_CATEGORICAL;
return false;
}
}
if (std::strstr(cptr, "integer [") != nullptr) {
bool pir = parseIntegerRange(
line + index + strlen("integer ["),
length,
errorCode,
index,
hiInteger,
loInteger);
if (pir) {
type = "integer";
return true;
}
else
return false;
}
if (std::strstr(cptr, "doubleReal [") != nullptr) {
bool pdr = parseDoubleRange(
line,
length,
errorCode,
index,
hiDouble,
loDouble);
if (pdr) {
type = "doubleReal";
return true;
}
else
return false;
}
if (std::strstr(cptr, "floatReal [") != nullptr) {
bool pfr = parseFloatRange(
line,
length,
errorCode,
index,
hiFloat,
loFloat);
if (pfr) {
type = "floatReal";
return true;
}
}
errorCode = INVALID_TYPE;
return false;
}
static bool readMetaDataLine(
std::ifstream& file1,
char line[],
int& errorCode,
int& index) {
file1.getline(line, 256);
if (strlen(line) == 0 && index == -1) {
errorCode = EMPTY_FILE;
return false;
}
if (file1.eof()) {
errorCode = 0;
index = FILE_EOF;
return false;
}
if (strlen(line) > 0 &&
std::strstr(line, "#endheader") != nullptr)
return false;
if (strlen(line) > 0)
return true;
else
return false;
}
double dbl_max[8] = { 0 };
double dbl_min[8] = { 0 };
int int_max = 0;
int int_min = 0;
static void readDatasetFile(
std::ifstream& file2) {
char line[256] = "";
for (int i = 0; i < 8; i++) {
dbl_min[i] = DBL_MAX;
dbl_max[i] = DBL_MIN;
}
int_min = INT_MAX;
int_max = INT_MIN;
while (!file2.eof()) {
file2.getline(line, 256);
int count = 0, index = 0;
while (
count <= 9 &&
index < static_cast<int>(strlen(line))) {
char ch = line[index++], subline[256] = "";
int cp = 0;
while (ch != ',' && cp < static_cast<int>(strlen(line))) {
subline[cp++] = ch;
ch = line[index++];
}
count++;
if (strlen(subline) >= 1)
subline[cp] = '\0';
if (count >= 1 && count <= 8 && cp > 1) {
std::string substr(subline);
double x = std::stod(subline);
if (x > dbl_max[count - 1])
dbl_max[count - 1] = x;
if (x < dbl_min[count - 1])
dbl_min[count - 1] = x;
}
else if (count == 9 && !(
strstr(subline, "F") ||
strstr(subline, "I") ||
strstr(subline, "M"))) {
std::string substr(subline);
int x = std::stoi(substr);
if (x > int_max)
int_max = x;
if (x < int_min)
int_min = x;
}
}
}
file2.close();
}
int main()
{
bool feature = false;
char filename1[256] = "C:\\Users\\James\\OneDrive\\Desktop\\ID3MetadataParser\\x64\\Debug\\ID3MetadataParserDataFile.txt";
char filename2[256] = "C:\\Users\\James\\OneDrive\\Desktop\\ID3MetadataParser\\x64\\Debug\\abalone.data.txt";
char line[256] = "";
int errorCode = -1, index = -1, role = -1;
std::ifstream file1(filename1);
std::ifstream file2(filename2);
// file1 format
std::string name, description, type;
std::vector<char> category;
// file2 format
std::string cat, length, diameter, height, whole;
std::string shucked, viscera, shell, rings;
std::vector<CategoricalAttribute> categoricalAttributes;
std::vector<IntegerAttribute> integerAttributes;
std::vector<DoubleAttribute> doubleAttributes;
std::vector<FloatAttribute> floatAttributes;
std::vector<std::string> names;
std::vector<std::string> descriptions;
std::vector<std::string> types;
while (!file1.eof()) {
index = -1;
bool result = readMetaDataLine(
file1,
line,
errorCode,
index);
if (!result)
break;
index = 0;
int length = static_cast<int>(strlen(line));
if (length == 0)
break;
name = "";
bool pn = parseName(
line,
length,
errorCode,
index,
feature,
name);
if (pn) {
bool result = readMetaDataLine(
file1,
line,
errorCode,
index);
if (!result)
break;
length = static_cast<int>(strlen(line));
index = 0;
description = "";
bool pd = parseDescription(
line,
length,
errorCode,
index,
description);
if (pd) {
bool result = readMetaDataLine(
file1,
line,
errorCode,
index);
if (!result)
break;
length = static_cast<int>(strlen(line));
index = 0;
type = "";
double hiDouble = DBL_MIN;
double loDouble = DBL_MAX;
float hiFloat = FLT_MIN;
float loFloat = FLT_MAX;
int hiInteger = INT_MIN;
int loInteger = INT_MAX;
bool pt = parseType(
line,
length,
hiDouble,
loDouble,
hiFloat,
loFloat,
errorCode,
index,
hiInteger,
loInteger,
type,
category);
length = static_cast<int>(strlen(line));
if (pt) {
if (type == "categorical") {
CategoricalAttribute ca;
ca.category = category;
ca.description = description;
ca.name = name;
categoricalAttributes.push_back(ca);
}
else if (type == "integer") {
IntegerAttribute ia;
ia.loValue = loInteger;
ia.hiValue = hiInteger;
ia.description = description;
ia.name = name;
integerAttributes.push_back(ia);
}
else if (type == "doubleReal") {
DoubleAttribute da;
da.loValue = loDouble;
da.hiValue = hiDouble;
da.description = description;
da.name = name;
doubleAttributes.push_back(da);
}
else if (type == "floatReal") {
FloatAttribute fa;
fa.loValue = loFloat;
fa.hiValue = hiFloat;
fa.description = description;
fa.name = name;
floatAttributes.push_back(fa);
}
else {
errorCode = INVALID_TYPE;
break;
}
}
else {
errorCode = MISSING_TYPE;
break;
}
}
else {
errorCode = INVALID_DESCRIPTION;
break;
}
}
else {
errorCode = INVALID_NAME;
return false;
}
}
readDatasetFile(file2);
for (int i = 1; i <= 7; i++) {
std::cout << i << '\t' << dbl_min[i];
std::cout << '\t' << dbl_max[i];
std::cout << std::endl;
}
std::cout << "8\t" << int_min << '\t' << int_max;
std::cout << std::endl;
std::cout << std::endl;
for (int i = 0; i < static_cast<int>(categoricalAttributes.size()); i++) {
std::cout << categoricalAttributes[i].name << ' ';
std::cout << categoricalAttributes[i].description << ' ';
std::cout << std::endl;
}
for (int i = 0; i < static_cast<int>(doubleAttributes.size()); i++) {
std::cout << doubleAttributes[i].name << ' ';
std::cout << doubleAttributes[i].description << ' ';
std::cout << doubleAttributes[i].loValue << ' ';
std::cout << doubleAttributes[i].hiValue;
std::cout << std::endl;
}
for (int i = 0; i < static_cast<int>(floatAttributes.size()); i++) {
std::cout << floatAttributes[i].name << ' ';
std::cout << floatAttributes[i].description << ' ';
std::cout << floatAttributes[i].loValue << ' ';
std::cout << floatAttributes[i].hiValue;
std::cout << std::endl;
}
for (int i = 0; i < static_cast<int>(integerAttributes.size()); i++) {
std::cout << integerAttributes[i].name << ' ';
std::cout << integerAttributes[i].description << ' ';
std::cout << integerAttributes[i].loValue << ' ';
std::cout << integerAttributes[i].hiValue;
std::cout << std::endl;
}
file1.close();
return 0;
}
Blog Entry © Tuesday, December 16, 2025, by James Pate Williams, Jr., Machine Learning the Abalone and Hill-Valley Datasets Using Learning Vector Quantization I and II, and the Radial Basis Function Neural Network
Blog Entry © Saturday, December 13, 2025, by James Pate Williams, Jr., Curve Fitting Georgia Statewide Temperature Averages from 1895 to 2001 Using a Polynomial Least Squares
Blog Entry © Wednesday, December 10, 2025, by James Pate Williams, Jr. Backpropagation Neural Network to Learn Three Continuous Functions
Blog Entry © Saturday, December 6, 2025, by James Pate Williams, Jr. Earley Parser
Blog Entry © Thursday, December 4, 2025, by James Pate Williams, Jr., Seven Methods to Solve the N-Queens Puzzle and Electron Scattering by a Hydrogen Atom
Blog Entry © Sunday, November 30, 2025, by James Pate Williams, Jr. and the Microsoft Artificially Intelligent Agent, the Copilot
Blog Entry © Saturday, November 28, 2025, by James Pate Williams, Jr. Fair Coin and Fair Dice Probabilities
Blog Entry © Tuesday 25, 2025, by James Pate Williams, Jr. Enumeration of the Tic-Tac-Toe Game Tree
/*
* Board.h
* Permutation
*
* Created by James Pate Williams, Jr. on 7/21/08.
* Modified on Monday 11/24/2025
* Copyright 2008 James Pate Williams, Jr. All rights reserved.
*
*/
#ifndef _Board_
#define _Board_
#include <fstream>
#include <vector>
class Board {
private:
char state[9];
std::vector<std::vector<char>> board;
public:
Board(void);
Board(const Board &board);
Board(const char b[3][3]);
Board(const std::vector<char> &v);
char GetState(int n) const;
void PrintBoard(int n) const;
void WriteBoard(std::ofstream &out) const;
friend bool operator == (const Board &b1, const Board &b2);
friend bool operator != (const Board &b1, const Board &b2);
friend bool Found(const Board &initial, const Board &board);
friend bool Win(const Board b, char winner[8]);
friend bool LegalBoard(
bool& legal, bool& won, char& whoWon, const Board b);
friend void PrintBoard(char board[3][3], int number);
static const char CharX, CharO, CharS;
};
#endif
/*
* Board.cpp
* Permutation
*
* Created by James Pate Williams, Jr. on 7/21/08.
* Copyright 2008 James Pate Williams, Jr. All rights reserved.
*
*/
#include <algorithm>
#include <fstream>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <vector>
#include "Board.h"
const char Board::CharO = 'o';
const char Board::CharX = 'x';
const char Board::CharS = '_';
Board::Board(void) {
board.resize(3, std::vector<char>(3));
for (int i = 0; i < 9; i++)
state[i] = '\0';
}
Board::Board(const Board &b) {
board.resize(3, std::vector<char>(3));
for (int i = 0; i < 3; i++)
for (int j = 0; j < 3; j++)
state[3 * i + j] = board[i][j] = b.state[3 * i + j];
}
Board::Board(const char b[3][3]) {
board.resize(3, std::vector<char>(3));
for (int i = 0; i < 3; i++)
for (int j = 0; j < 3; j++)
state[3 * i + j] = board[i][j] = b[i][j];
}
Board::Board(const std::vector<char> &v) {
board.resize(3, std::vector<char>(3));
for (int i = 0; i < 3; i++)
for (int j = 0; j < 3; j++)
state[3 * i + j] = board[i][j] = v[3LL * i + j];
}
char Board::GetState(int n) const {
return state[n];
}
void Board::PrintBoard(int n) const {
std::cout << n << std::endl;
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++)
std::cout << state[3 * i + j];
std::cout << std::endl;
}
std::cout << std::endl;
std::cout << std::endl;
}
void Board::WriteBoard(std::ofstream &out) const {
for (int i = 0; i < 9; i++)
out << state[i];
out << std::endl;
}
bool operator == (const Board &b1, const Board &b2) {
int i, equal = 0;
for (i = 0; i < 9; i++)
if (b1.state[i] == b2.state[i])
equal++;
return equal == 9;
}
bool operator != (const Board &b1, const Board &b2) {
for (int i = 0; i < 9; i++)
if (b1.state[i] == b2.state[i])
return false;
return true;
}
bool Found(const Board &initial, const Board &board) {
// reflections
if (initial.state[0] == board.state[6] && initial.state[1] == board.state[7] &&
initial.state[2] == board.state[8] && initial.state[3] == board.state[3] &&
initial.state[4] == board.state[4] && initial.state[5] == board.state[5] &&
initial.state[6] == board.state[0] && initial.state[7] == board.state[1] &&
initial.state[8] == board.state[2])
return true;
if (initial.state[0] == board.state[2] && initial.state[1] == board.state[1] &&
initial.state[2] == board.state[0] && initial.state[3] == board.state[5] &&
initial.state[4] == board.state[4] && initial.state[5] == board.state[3] &&
initial.state[6] == board.state[8] && initial.state[7] == board.state[7] &&
initial.state[8] == board.state[6])
return true;
if (initial.state[0] == board.state[0] && initial.state[1] == board.state[3] &&
initial.state[2] == board.state[6] && initial.state[3] == board.state[1] &&
initial.state[4] == board.state[4] && initial.state[5] == board.state[7] &&
initial.state[6] == board.state[2] && initial.state[7] == board.state[5] &&
initial.state[8] == board.state[8])
return true;
if (initial.state[0] == board.state[8] && initial.state[1] == board.state[5] &&
initial.state[2] == board.state[2] && initial.state[3] == board.state[7] &&
initial.state[4] == board.state[4] && initial.state[5] == board.state[1] &&
initial.state[6] == board.state[6] && initial.state[7] == board.state[3] &&
initial.state[8] == board.state[0])
return true;
// rotations
if (initial.state[0] == board.state[6] && initial.state[1] == board.state[3] &&
initial.state[2] == board.state[0] && initial.state[3] == board.state[7] &&
initial.state[4] == board.state[4] && initial.state[5] == board.state[1] &&
initial.state[6] == board.state[8] && initial.state[7] == board.state[5] &&
initial.state[8] == board.state[2])
return true;
if (initial.state[0] == board.state[8] && initial.state[1] == board.state[7] &&
initial.state[2] == board.state[6] && initial.state[3] == board.state[5] &&
initial.state[4] == board.state[4] && initial.state[5] == board.state[3] &&
initial.state[6] == board.state[2] && initial.state[7] == board.state[1] &&
initial.state[8] == board.state[0])
return true;
if (initial.state[0] == board.state[2] && initial.state[1] == board.state[5] &&
initial.state[2] == board.state[8] && initial.state[3] == board.state[1] &&
initial.state[4] == board.state[4] && initial.state[5] == board.state[7] &&
initial.state[6] == board.state[0] && initial.state[7] == board.state[3] &&
initial.state[8] == board.state[6])
return true;
// equal
return initial == board;
}
bool Win(const Board b, char winner[8]) {
bool win = false;
for (int i = 0; i < 8; i++)
winner[i] = Board::CharS;
if (b.board[0][0] == b.board[0][1] && b.board[0][0] ==
b.board[0][2] && b.board[0][0] != Board::CharS) {
winner[0] = b.board[0][0];
win = true;
}
if (b.board[1][0] == b.board[1][1] && b.board[1][0] ==
b.board[1][2] && b.board[1][0] != Board::CharS) {
winner[1] = b.board[1][0];
win = true;
}
if (b.board[2][0] == b.board[2][1] && b.board[2][0] ==
b.board[2][2] && b.board[2][0] != Board::CharS) {
winner[2] = b.board[2][0];
win = true;
}
if (b.board[0][0] == b.board[1][0] && b.board[0][0] ==
b.board[2][0] && b.board[0][0] != Board::CharS) {
winner[3] = b.board[0][0];
win = true;
}
if (b.board[0][1] == b.board[1][1] && b.board[0][1] ==
b.board[2][1] && b.board[0][1] != Board::CharS) {
winner[4] = b.board[0][1];
win = true;
}
if (b.board[0][2] == b.board[1][2] && b.board[0][2] ==
b.board[2][2] && b.board[0][2] != Board::CharS) {
winner[5] = b.board[0][2];
win = true;
}
if (b.board[0][0] == b.board[1][1] && b.board[0][0] ==
b.board[2][2] && b.board[0][0] != Board::CharS) {
winner[6] = b.board[0][0];
win = true;
}
if (b.board[0][2] == b.board[1][1] && b.board[0][2] ==
b.board[2][0] && b.board[0][2] != Board::CharS) {
winner[7] = b.board[0][2];
win = true;
}
return win;
}
void PrintBoard(char board[3][3], int number) {
std::cout << "number = " << number << std::endl;
std::cout << std::endl;
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++)
std::cout << board[i][j];
std:: cout << std::endl;
}
std::cout << std::endl;
}
bool LegalBoard(
bool &legal, bool &won, char &whoWon, const Board b) {
bool winO, winX;
char winner[8];
int countO = 0, countS = 0, countX = 0;
int i, j, oWins = 0, xWins = 0;
legal = won = false;
for (i = 0; i < 3; i++) {
for (j = 0; j < 3; j++) {
if (b.board[i][j] == Board::CharO)
countO++;
else if (b.board[i][j] == Board::CharX)
countX++;
else if (b.board[i][j] == Board::CharS)
countS++;
}
}
if ((countX >= 3 || countO >= 3) && Win(b, winner)) {
for (i = 0; i < 8; i++) {
if (winner[i] == Board::CharX)
xWins++;
else if (winner[i] == Board::CharO)
oWins++;
}
winX = (xWins >= 1 && oWins == 0) &&
(countX <= 5 && countO <= 4 && countX == countO + 1);
winO = (xWins == 0 && oWins >= 1) &&
(countO <= 5 && countX <= 4 && countO == countX + 1);
legal = won = winX || winO;
if (won && winX)
whoWon = Board::CharX;
else if (won && winO)
whoWon = Board::CharO;
}
else
legal = (countX <= 5 && countO <= 4 && countX == countO + 1) ||
(countO <= 5 && countX <= 4 && countO == countX + 1);
return legal;
}
#define _WriteBV_
#include <algorithm>
#ifdef _WriteBV_
#include <fstream>
#endif
#include <iomanip>
#include <iostream>
#include <vector>
#include "Board.h"
static int Compare(const void *vPtr1, const void *vPtr2) {
char *cPtr1 = (char *) vPtr1;
char *cPtr2 = (char *) vPtr2;
return strcmp(cPtr1, cPtr2);
}
static void EnumerateTicTacToe(void) {
bool legal, won;
char b[3][3], whoWon;
char tree[3][3][3][3][3][3][3][3][3];
int i0, i1, i2, i3, i4, i5, i6, i7, i8;
int legals = 0, number = 0, wCount = 0;
int xCount = 0, oCount = 0;
int bvSize, i, j;
std::vector<Board> boardVector;
for (i0 = 0; i0 < 3; i0++) {
for (i1 = 0; i1 < 3; i1++) {
for (i2 = 0; i2 < 3; i2++) {
for (i3 = 0; i3 < 3; i3++) {
for (i4 = 0; i4 < 3; i4++) {
for (i5 = 0; i5 < 3; i5++) {
for (i6 = 0; i6 < 3; i6++) {
for (i7 = 0; i7 < 3; i7++) {
for (i8 = 0; i8 < 3; i8++) {
if (i0 == 0)
b[0][0] = tree[i0][i1][i2][i3][i4][i5][i6][i7][i8] = Board::CharX;
else if (i0 == 1)
b[0][0] = tree[i0][i1][i2][i3][i4][i5][i6][i7][i8] = Board::CharO;
else if (i0 == 2)
b[0][0] = tree[i0][i1][i2][i3][i4][i5][i6][i7][i8] = Board::CharS;
if (i1 == 0)
b[0][1] = tree[i0][i1][i2][i3][i4][i5][i6][i7][i8] = Board::CharX;
else if (i1 == 1)
b[0][1] = tree[i0][i1][i2][i3][i4][i5][i6][i7][i8] = Board::CharO;
else if (i1 == 2)
b[0][1] = tree[i0][i1][i2][i3][i4][i5][i6][i7][i8] = Board::CharS;
if (i2 == 0)
b[0][2] = tree[i0][i1][i2][i3][i4][i5][i6][i7][i8] = Board::CharX;
else if (i2 == 1)
b[0][2] = tree[i0][i1][i2][i3][i4][i5][i6][i7][i8] = Board::CharO;
else if (i2 == 2)
b[0][2] = tree[i0][i1][i2][i3][i4][i5][i6][i7][i8] = Board::CharS;
if (i3 == 0)
b[1][0] = tree[i0][i1][i2][i3][i4][i5][i6][i7][i8] = Board::CharX;
else if (i3 == 1)
b[1][0] = tree[i0][i1][i2][i3][i4][i5][i6][i7][i8] = Board::CharO;
else if (i3 == 2)
b[1][0] = tree[i0][i1][i2][i3][i4][i5][i6][i7][i8] = Board::CharS;
if (i4 == 0)
b[1][1] = tree[i0][i1][i2][i3][i4][i5][i6][i7][i8] = Board::CharX;
else if (i4 == 1)
b[1][1] = tree[i0][i1][i2][i3][i4][i5][i6][i7][i8] = Board::CharO;
else if (i4 == 2)
b[1][1] = tree[i0][i1][i2][i3][i4][i5][i6][i7][i8] = Board::CharS;
if (i5 == 0)
b[1][2] = tree[i0][i1][i2][i3][i4][i5][i6][i7][i8] = Board::CharX;
else if (i5 == 1)
b[1][2] = tree[i0][i1][i2][i3][i4][i5][i6][i7][i8] = Board::CharO;
else if (i5 == 2)
b[1][2] = tree[i0][i1][i2][i3][i4][i5][i6][i7][i8] = Board::CharS;
if (i6 == 0)
b[2][0] = tree[i0][i1][i2][i3][i4][i5][i6][i7][i8] = Board::CharX;
else if (i6 == 1)
b[2][0] = tree[i0][i1][i2][i3][i4][i5][i6][i7][i8] = Board::CharO;
else if (i6 == 2)
b[2][0] = tree[i0][i1][i2][i3][i4][i5][i6][i7][i8] = Board::CharS;
if (i7 == 0)
b[2][1] = tree[i0][i1][i2][i3][i4][i5][i6][i7][i8] = Board::CharX;
else if (i7 == 1)
b[2][1] = tree[i0][i1][i2][i3][i4][i5][i6][i7][i8] = Board::CharO;
else if (i7 == 2)
b[2][1] = tree[i0][i1][i2][i3][i4][i5][i6][i7][i8] = Board::CharS;
if (i8 == 0)
b[2][2] = tree[i0][i1][i2][i3][i4][i5][i6][i7][i8] = Board::CharX;
else if (i8 == 1)
b[2][2] = tree[i0][i1][i2][i3][i4][i5][i6][i7][i8] = Board::CharO;
else if (i8 == 2)
b[2][2] = tree[i0][i1][i2][i3][i4][i5][i6][i7][i8] = Board::CharS;
Board bb(b);
if (LegalBoard(legal, won, whoWon, bb)) {
Board board(b);
legals++;
if (won) {
wCount++;
if (whoWon == Board::CharX)
xCount++;
else if (whoWon == Board::CharO)
oCount++;
}
boardVector.push_back(board);
}
number++;
}}}}}}}}}
for (i = 0; i < boardVector.size() - 1; i++)
for (j = i; j < boardVector.size(); j++)
if (Found(boardVector[i], boardVector[j]))
boardVector.erase(boardVector.begin() + j);
bvSize = (int)boardVector.size();
std::cout << std::setw(4) << "legal total = " << legals << std::endl;
std::cout << std::setw(4) << "xWins total = " << xCount << std::endl;
std::cout << std::setw(4) << "oWins total = " << xCount << std::endl;
std::cout << std::setw(4) << "oxWin total = " << xCount + oCount << std::endl;
std::cout << std::setw(4) << "unique size = " << boardVector.size();
std::cout << std::endl;
#ifdef _WriteBV_
std::cout << std::endl;
std::ofstream outFile("Tic TacToe Game Tree Enumeration.txt");
std::cout << std::endl;
for (i = 0; i < bvSize; i++) {
boardVector[i].PrintBoard(i + 1);
boardVector[i].WriteBoard(outFile);
}
#endif
}
int main (int argc, char * const argv[]) {
EnumerateTicTacToe();
return 0;
}