gofish.cpp

//sandbox file
#include <stdio.h>
#include <string.h>
#include <stddef.h>
#include <string>
#include <vector>
#include <map>
#include <unordered_map>
#include <iostream>
#include <sstream>
#include <algorithm>

using std::string;
using std::vector;
using std::unordered_map;
using std::ostringstream;

typedef unordered_map<string, double> dictType;
#define DEFAULT_NUM_SCHOOLS 2
#define SCHOOL_SIZE 4

string toString(vector<int>& currentData) {
    ostringstream oss;
    for (int i = 0; i < currentData.size(); i++) {
        oss << currentData[i];
    }
    return oss.str();
}

bool isSet(vector<int>& currentData, int i) {
    if (currentData[i / SCHOOL_SIZE] > (i % SCHOOL_SIZE)) {
        return true;
    }
    return false;
}

void setValue(vector<int>& currentData, int i) {
    currentData[i / SCHOOL_SIZE]++;
    if (currentData[i / SCHOOL_SIZE] > SCHOOL_SIZE) {
        std::cout << "ERROR: SCHOOL CHOSEN TOO OFTEN" << std::endl;
        string temp;
        std::cin >> temp;
    }
}

double recursiveCall(vector<int>& currentData, dictType& savedValues) {
    //sort in descending order for canonical version of currentData
    std::sort(currentData.begin(), currentData.end(), std::greater<int>());
    //see if we've encountered it before
    string hash = toString(currentData);
    if (savedValues.count(hash)) {
        return savedValues[hash];
    }

    double result = 0;

    int firstUnsetNode = -1;
    for (int i = 0; i < currentData.size() * SCHOOL_SIZE; i++) {
        if (!isSet(currentData, i)) {
            firstUnsetNode = i;
            break;
        }
    }

    if (firstUnsetNode == -1) {
        //all nodes chosen, so result is 1
        result = 1;
    } else {
        setValue(currentData, firstUnsetNode);

        int i = firstUnsetNode + 1;
        while (i % SCHOOL_SIZE != 0) i++; //can't match w/i school
        for ( ; i < currentData.size() * SCHOOL_SIZE; i++) {
            if (!isSet(currentData, i)) {
                vector<int> workingData = currentData;
                setValue(workingData, i);
                result += recursiveCall(workingData, savedValues);
            }
        }
        //assert: if no legal assignments, result is 0
    }

  //  std::cout << "Assigning value for " << hash << " of " << result << std::endl;
    savedValues[hash] = result;
    return result;
}

int main(int argc, char** argv) {
    dictType savedValues;
    int numSchools;
    if (argc == 2) {
        numSchools = atoi(argv[1]);
    } else {
        numSchools = DEFAULT_NUM_SCHOOLS;
    }

    vector<int> currentData(numSchools, 0);
    double solutionCount = recursiveCall(currentData, savedValues);

    std::cout << "Numerator: " << solutionCount << std::endl;
    double divisor = 1;
    for (int i = SCHOOL_SIZE * numSchools - 1; i > 0; i-=2) {
        divisor *= i;
    }
    double probability = solutionCount / divisor;
    std::cout << "Probability: " << 1 - probability << std::endl;
}