// This program demonstrates three methods, each faster
// than the last, for computing which scores are impossible
// to get by throwing D darts at a dart board with W wedges.
// The dart board is assumed to include rings for doubling
// and tripling each throw.  Depending on the values of the
// macros below, the program will also allow throws of 0,
// 25 and 50.
//
// You are free to use this code in any way you like.
//
// Ben Jackson, March 2010

#include <stdio.h>
#include <stdlib.h>

// Set this to true to consider cases where darts
// miss the board completely
#define ALLOW_ZERO true

// Set this to true to include the values 25 and 50,
// like a regular dart board.
#define USE_SPECIAL_VALUES true


// Global Variables.
// 'a' contains the valid throws up to the current number of darts.
// 'b' is a scratch buffer swapped back and forth with 'a'
bool* a;
bool* b;

// Functions. Defined and commented below.
bool isValidThrow(int i, int w);
void method1(int d, int w, int s=0);
void method2(int d, int w, int s=0);
void method3(int d, int w);

int main(int argc, char** argv) {
    if (argc < 3) {
        printf("Specify two integers, d & w\n");
        return 1;
    }
    int d = atoi(argv[1]);
    int w = atoi(argv[2]);

    int size = d*3*w + 1;
    a = new bool[size];
    b = new bool[size];

    // Erase a and b
    for (int x=0; x<size; x++) a[x] = b[x] = false;

    //method1(d, w);
    //method2(d, w);
    method3(d, w);

    // Print the invalid throws
    printf("%3d darts, %2d wedges: ", d, w);
    for (int x=0; x<size; x++) if (!a[x]) printf("%d, ", x);
    printf("\n");

    delete [] a;
    delete [] b;

    return 0;
}


// Determine whether a single throw of i is valid for a given
// number of wedges, w.
bool isValidThrow(int i, int w) {
    if (i < 1) return ALLOW_ZERO;

    if (USE_SPECIAL_VALUES && (i==25 || i==50)) return true;

    if (i <= w) return true;

    if (i <= 2*w && i%2 == 0) return true;

    if (i <= 3*w && i%3 == 0) return true;

    return false;
}

// The recursive brute force way: O(w^d), where d is
// the number of darts and w is the.
void method1(int d, int w, int s) {
    for (int i=0; i<=3*w; i++) {
        if (!isValidThrow(i, w)) continue;
        int si = s+i;

        if (d == 1) {
            a[si] = true;
        } else {
            method1(d-1, w, si);
        }
    }
}

// An alternate recursive method that is
//
// O(w + 2*w^2 + 3*w^2 + ... + d*w^2)
//
// which I believe reduces to
//
// O((w^2)(d^2))
void method2(int d, int w, int s) {
    if (s==d) return;

    // erase b
    for (int i=0; i<=(s+1)*3*w; i++) b[i] = false;

    if (s==0) {
        for (int j=0; j<=3*w; j++) {
            if (isValidThrow(j, w)) {
                b[j] = true;
            }
        }
    } else {
        int limit = s*3*w;

        for (int i=0; i<=limit; i++) {
            if (!a[i]) continue;

            for (int j=0; j<=3*w; j++) {
                if (isValidThrow(j, w)) {
                    b[i+j] = true;
                }
            }
        }
    }

    // swap a&b
    bool* t = a;
    a = b;
    b = t;

    // recurse
    method2(d, w, s+1);
}

// A third method that takes advantage of the simple repeating
// patterns you get when d increases but w is held constant.
// For example, with w=20, you get:
//
// 1 darts: 23, 29, 31, 35, 37, 41, 43, 44, 46, 47, 49, 52, 53, 55, 56, 58, 59,
// 2 darts: 103, 106, 109, 112, 113, 115, 116, 118, 119,
// 3 darts: 163, 166, 169, 172, 173, 175, 176, 178, 179,
// 4 darts: 223, 226, 229, 232, 233, 235, 236, 238, 239,
// 5 darts: 283, 286, 289, 292, 293, 295, 296, 298, 299,
//
// This method is O(w^2), which means that for a regular dart
// board, where only d can vary, the method is O(1)
void method3(int d, int w) {

    //  Handle the trivial cases
    if (d <= 2) return method2(d, w);

    // Populate 'a' for 2 darts.
    method2(2, w);

    // set 'b' to all true
    for (int i=0; i<=d*3*w; i++) b[i] = true;

    // Exploit the repeating pattern for d > 2
    for (int i=0; i<2*3*w; i++) {
        if (!a[i]) b[i+((d-2)*3*w)]=false;
    }

    // swap a&b
    bool* t = a;
    a = b;
    b = t;
}