Code Jam 2013 qualification round files

fair-and-square.ts

///<reference path='app.d.ts' />

import fs = module("fs")
import _ = module("underscore")
import winston = module("winston")
import async = module("async")

var s = require('string');

// Usage: node appname input-file [output-file] [test] 
//  all files stored in ./files/fileFolderName/*
//  if test load output-file and do a diff, else if output-file output to file

var fileFolderName = 'fair-and-square';

/*
Given 2 numbers, find all numbers between the two that are both palindromes and squares of palindromes

for each n = 1 .. sqrt(max(B))
    if palindrome(n)
        if palindrome(n*n)
            fairSquares.push(n)

for each test case, go through list and count values between test case limit

Could do this asynchronously, storing in {} then converting to [], which would be faster but it's still not going to work for the 2nd large data set
*/


winston.remove(winston.transports.Console);
winston.add(winston.transports.Console, { timestamp: true });

var fairSquares = [];

//var maxB = 1000;
var maxB = 100000000000000; //10^14
var sqrtMaxB = Math.floor(Math.sqrt(maxB));

winston.info("Finding fairSquares, 1 -> " + sqrtMaxB);

for (var i = 1; i <= sqrtMaxB; i++) {
    if (isPalindrome(i.toString())) {
        var iSquared = i * i;
        if (isPalindrome(iSquared.toString())) {
            fairSquares.push(iSquared);
            // obvious pattern here, can be used for large data set
            winston.info(i + " & " + iSquared);
            //process.stdout.write('.');
        }
    }
}
//process.stdout.write('\n');

winston.info("Found " + fairSquares.length + " fairSquares");
//winston.info("fairSquares", fairSquares);

// Pause to check memory usage
//var prompt = require('prompt');
//prompt.get(['x'], () => {});

function isPalindrome(input: string) {
    var head = 0;
    var tail = input.length - 1;

    while (head < tail) {
        if (input[head++] != input[tail--]) {
            return false;
        }
    }
    return true;
}

function processTestCase(testCase: string): string {
    //winston.info("testCase", testCase);
    //return "TODO";

    var limits = testCase.split(" ");
    var lowerLimit = parseInt(limits[0]);
    var upperLimit = parseInt(limits[1]);

    var num = 0;
    _.each(fairSquares, (n) => { if (n >= lowerLimit && n <= upperLimit) { num++; } });

    return num.toString();
}

function fileToTestCases(input) {
    var testCases = [];
    
    while (input.length > 0) {
        var testCase = s(input.shift()).trim().s;
        if (testCase != '') {
            testCases.push(testCase);
        }
    }

    return testCases;

    //return input;
}


if (process.argv.length < 3) {
    throw "Invalid parameters";
}

var fileFolder = './files/' + fileFolderName + '/';

var inputFileName = fileFolder + process.argv[2];

if (process.argv.length > 3) {
    var outputFileName = fileFolder + process.argv[3];
}

var testExpectedFile = false;
if (process.argv.length > 4) {
    testExpectedFile = true;
}

var input = fs.readFileSync(inputFileName, 'utf8').split('\n');
var numTestCases = parseInt(input.shift());
var testCases = fileToTestCases(input);

if (testCases.length != numTestCases) {
    throw 'Wrong number of test cases - ' + testCases.length + ' vs ' + numTestCases;
}

var done = 0;

function asyncTestCase(testCase, callback) {
    var result = processTestCase(testCase);

    process.stdout.write('.');
    done++;
    if (done % 1000 == 0) {
        console.log('\n' + done);
    }

    callback(null, result);
}

function formatResult(result: string, i: number) {
    return "Case #" + (i+1) + ": " + result;
}

async.map(testCases, asyncTestCase, (err, results) => {
    if (err) {
        throw "Error processing test cases: " + err;
    }

    console.log("\nFinished processing test cases, outputting results");
    
    if (!outputFileName) {
        // Just write to stdout
        _.each(results, (result, index) => {
            console.log(formatResult(result, index));
        });
    }
    else {
        var output = '';
        _.each(results, (result, index) => {
            if (index > 0) {
                output += '\n';
            }
            output += formatResult(result, index);
        });
        
        if (testExpectedFile) {
            // Read in file and check against generated result
            console.log("\nChecking results against expected");

            var expected = fs.readFileSync(outputFileName, 'utf8');

            if (output == expected) {
                console.log("IT WORKS!!");
            }
            else {
                console.log("IT DIDN'T WORK!!");
                console.log("Expected:");
                console.log(expected);
                console.log("Got:");
                console.log(output);
            }
        }
        else {
            fs.writeFileSync(outputFileName, output, 'utf8');
        }
    }
});

lawnmower.ts

///<reference path='app.d.ts' />

import fs = module("fs")
import _ = module("underscore")
import winston = module("winston")
import async = module("async")

var s = require('string');

// Usage: node appname input-file [output-file] [test] 
//  all files stored in ./files/fileFolderName/*
//  if test load output-file and do a diff, else if output-file output to file

var fileFolderName = 'lawnmower';

/*
Height can be 1-100mm in 1mm increments
Height must be modified in a whole row or column

For each cell, all cells in the same row must have a height that is equal or lower OR all cells in the same col must have a height that is equal or lower

9 9 9 8 9 9 9 9 9 6 9 9
9 9 9 8 9 9 9 9 9 6 9 9
7 7 7 7 7 7 7 7 7 6 7 7
9 9 9 8 9 9 9 9 9 6 9 9
1 1 1 1 1 1 1 1 1 1 1 1
9 9 9 8 9 9 9 9 9 6 9 9

1 3 3 3
1 5 4 5
1 5 4 5

Translate string into array of rows and array of cols, with minimums and checked bool:
Rows:
0: [ 1,3,3,3 ] checked=false->true
1: [ 1,5,4,5 ] checked=false
2: [ 1,5,4,5 ] checked=false
Cols:
0: [ 1,1,1 ] checked=false->true
1: [ 3,5,5 ] checked=false->true
2: [ 3,4,4 ] checked=false->true
3: [ 3,5,5 ] checked=false

Store map of height -> set of x/y coords
1 -> 0/0 1/0 2/0
2 -> 
3 -> 0/1 0/2 0/3
4 -> 1/2 2/2
5 -> 1/1 1/3 2/1 2/3

for each height
  for each coord
    if (check(row,null,val))
      set row=checked
    if (checkRowCol(null,col,val))
      set col=checked

checkRowCol(row,col,val):
  if row
    return row is checked or all values in row either = val or are checked
  else if col
    return col is checked or all values in col either = val or are checked

2 1 2
1 1 1
2 1 2
Rows:
0: [ 2,1,2 ] checked=false
1: [ 1,1,1 ] checked=false
2: [ 2,1,2 ] checked=false
Cols:
0: [ 2,1,2 ] checked=false
1: [ 1,1,1 ] checked=false
2: [ 2,1,2 ] checked=false

1 -> 0/1 1/0 1/1 1/2 2/1
2 -> 0/0 0/2 2/0 2/2

*/


function processTestCase(testCase: any): string {
    //winston.info("testCase", testCase);
    
    // Translate string into array of rows and array of cols, with checked bool

    var numRows = testCase.numRows;
    //winston.info("numRows", numRows);
    var rows = [];
    while (numRows--) rows.push({checked: false});
    //winston.info("rows", rows);

    var numCols = testCase.numCols;
    //winston.info("numCols", numCols);
    var cols = [];
    while (numCols--) cols.push({checked: false});
    //winston.info("cols", cols);
    
    // Store map of height -> set of x/y coords (add entry for height=0 for clarity even though it can't exist)
    var heightCoords = [];
    for (var curHeight = 0; curHeight <= 100; curHeight++) heightCoords.push([]);
    
    var rowStrings = testCase.str.split('\n');
    _.each(rowStrings, (rowString, rowIndex) => {
        var chars = rowString.split(' ');

        var row = _.map(chars, (char) => { return parseInt(char); });
        rows[rowIndex]['numbers'] = row;
        
        _.each(row, (num, colIndex) => {
            if (!('numbers' in cols[colIndex])) {
                cols[colIndex]['numbers'] = [];
            }
            cols[colIndex]['numbers'].push(num);
            
            var coord = { row: rowIndex, col: colIndex };
            heightCoords[num].push(coord);
        });

    });

    //winston.info("rows", rows);
    //winston.info("cols", cols);
    //winston.info("heightCoords", heightCoords);
    
    // ewwwwwww
    var check = (rowIndex, colIndex, height) => {
        //winston.info("checking rowIndex=" + rowIndex + " colIndex=" + colIndex + " height=" + height);
        if (rowIndex != null) {
            if (rows[rowIndex].checked) {
                //winston.info("row checked, return true");
                return true;
            }
            for (var i = 0; i < rows[rowIndex]['numbers'].length; i++) {
                if (!cols[i].checked && rows[rowIndex]['numbers'][i] != height) {
                    //winston.info("bad col found (" + i + "), return false");
                    return false;
                }
            }
            //winston.info("no bad cols found, check and return true");
            rows[rowIndex]['checked'] = true;
            return true;
        }
        else if (colIndex != null) {
            if (cols[colIndex].checked) {
                //winston.info("col checked, return true");
                return true;
            }
            for (var i = 0; i < cols[colIndex]['numbers'].length; i++) {
                if (!rows[i].checked && cols[colIndex]['numbers'][i] != height) {
                    //winston.info("bad row found (" + i + "), return false");
                    return false;
                }
            }
            //winston.info("no bad rows found, check and return true");
            cols[colIndex]['checked'] = true;
            return true;
        }
    };

    var ok = true;
    _.each(heightCoords, (coords, height) => {
        _.each(coords, (coord) => {
            var rowOk = check(coord.row, null, height);
            var colOk = check(null, coord.col, height);

            if (!rowOk && !colOk) {
                ok = false;
                return;
            }
        });

        if (!ok) {
            return;
        }
    });

    return ok ? "YES" : "NO";
}

function fileToTestCases(input) {
    var testCases = [];

    while (input.length > 0) {
        var sizes = input.shift().split(' ');
        var numRows = parseInt(sizes[0]);
        var numCols = parseInt(sizes[1]);

        var curTestCase = {numRows: numRows, numCols: numCols};
        
        var curTestCaseString = '';
        while (numRows-- > 0) {
            curTestCaseString += input.shift() + '\n';
        }

        curTestCase['str'] = s(curTestCaseString).trim().s;
        
        if (curTestCase['str'] != '') {
            testCases.push(curTestCase);
        }
    }

    return testCases;
}


if (process.argv.length < 3) {
    throw "Invalid parameters";
}

var fileFolder = './files/' + fileFolderName + '/';

var inputFileName = fileFolder + process.argv[2];

if (process.argv.length > 3) {
    var outputFileName = fileFolder + process.argv[3];
}

var testExpectedFile = false;
if (process.argv.length > 4) {
    testExpectedFile = true;
}

var input = fs.readFileSync(inputFileName, 'utf8').split('\n');
var numTestCases = parseInt(input.shift());
var testCases = fileToTestCases(input);

if (testCases.length != numTestCases) {
    throw 'Wrong number of test cases - ' + testCases.length + ' vs ' + numTestCases;
}

var done = 0;

function asyncTestCase(testCase, callback) {
    var result = processTestCase(testCase);

    process.stdout.write('.');
    done++;
    if (done % 10 == 0) {
        console.log('\n' + done);
    }

    callback(null, result);
}

function formatResult(result: string, i: number) {
    return "Case #" + (i+1) + ": " + result;
}

async.map(testCases, asyncTestCase, (err, results) => {
    if (err) {
        throw "Error processing test cases: " + err;
    }

    console.log("\nFinished processing test cases, outputting results");
    
    if (!outputFileName) {
        // Just write to stdout
        _.each(results, (result, index) => {
            console.log('[' + formatResult(result, index) + ']');
        });
    }
    else {
        var output = '';
        _.each(results, (result, index) => {
            if (index > 0) {
                output += '\n';
            }
            output += formatResult(result, index);
        });
        
        if (testExpectedFile) {
            // Read in file and check against generated result
            console.log("\nChecking results against expected");

            var expected = fs.readFileSync(outputFileName, 'utf8');

            if (output == expected) {
                console.log("IT WORKS!!");
            }
            else {
                console.log("IT DIDN'T WORK!!");
                console.log("Expected:");
                console.log('[' + expected + ']');
                console.log("Got:");
                console.log('[' + output + ']');
            }
        }
        else {
            fs.writeFileSync(outputFileName, output, 'utf8');
        }
    }
});

template.ts

///<reference path='app.d.ts' />

import fs = module("fs")
import _ = module("underscore")
import winston = module("winston")
import async = module("async")

var s = require('string');

// Usage: node appname input-file [output-file] [test] 
//  all files stored in ./files/fileFolderName/*
//  if test load output-file and do a diff, else if output-file output to file

var fileFolderName = 'x';
var progressIncrement = 1000; // Display progress after this number of test cases complete

function processTestCase(testCase: any): string {
    winston.info("testCase", testCase);
    return "TODO";
}

function fileToTestCases(input) {
    var testCases = [];

    var curTestCase = '';
    var line;
    while (input.length > 0) {
        line = s(input.shift()).trim().s;
        if (line != '') {
            curTestCase += line + '\n';
        }
        else {
            if (curTestCase != '') {
                testCases.push(s(curTestCase).trim().s);
                curTestCase = '';
            }
        }
    }

    if (curTestCase != '') {
        testCases.push(curTestCase);
    }

    return testCases;
}


if (process.argv.length < 3) {
    throw "Invalid parameters";
}

var fileFolder = './files/' + fileFolderName + '/';

var inputFileName = fileFolder + process.argv[2];

if (process.argv.length > 3) {
    var outputFileName = fileFolder + process.argv[3];
}

var testExpectedFile = false;
if (process.argv.length > 4) {
    testExpectedFile = true;
}

var input = fs.readFileSync(inputFileName, 'utf8').split('\n');
var numTestCases = parseInt(input.shift());
var testCases = fileToTestCases(input);

if (testCases.length != numTestCases) {
    throw 'Wrong number of test cases - ' + testCases.length + ' vs ' + numTestCases;
}

var done = 0;

function asyncTestCase(testCase, callback) {
    var result = processTestCase(testCase);

    process.stdout.write('.');
    done++;
    if (done % progressIncrement == 0) {
        console.log('\n' + done);
    }

    callback(null, result);
}

function formatResult(result: string, i: number) {
    return "Case #" + (i+1) + ": " + result;
}

async.map(testCases, asyncTestCase, (err, results) => {
    if (err) {
        throw "Error processing test cases: " + err;
    }

    console.log("\nFinished processing test cases, outputting results");
    
    if (!outputFileName) {
        // Just write to stdout
        _.each(results, (result, index) => {
            console.log(formatResult(result, index));
        });
    }
    else {
        var output = '';
        _.each(results, (result, index) => {
            if (index > 0) {
                output += '\n';
            }
            output += formatResult(result, index);
        });
        
        if (testExpectedFile) {
            // Read in file and check against generated result
            console.log("\nChecking results against expected");

            var expected = fs.readFileSync(outputFileName, 'utf8');

            if (output == expected) {
                console.log("IT WORKS!!");
            }
            else {
                console.log("IT DIDN'T WORK!!");
                console.log("Expected:");
                console.log(expected);
                console.log("Got:");
                console.log(output);
            }
        }
        else {
            fs.writeFileSync(outputFileName, output, 'utf8');
        }
    }
});

tic-tac-toe-tomek.ts

///<reference path='app.d.ts' />

import fs = module("fs")
import child_process = module("child_process")
import _ = module("underscore")
import winston = module("winston")
import async = module("async")

var s = require('string');

// Usage: node appname input-file [output-file] [test] 
//  all files stored in ./files/fileFolderName/*
//  if test load output-file and do a diff, else if output-file output to file

var fileFolderName = 'tic-tac-toe-tomek';

function findWinner(str) {    
    // Dot means no-one won, otherwise check for existence of X and O
    var foundDot = false;
    var foundX = false;
    var foundO = false;

    _.each(str, (ch) => {
        if (ch == '.') {
            foundDot = true;
            return;
        }
        else if (ch == 'X') {
            foundX = true;
        }
        else if (ch == 'O') {
            foundO = true;
        }
    });

    if (foundDot) {
        return null;
    }
    else if (foundX && !foundO) {
        return 'X';
    }
    else if (foundO && !foundX) {
        return 'O';
    }
}

function processTestCase(testCase: string): string {

    // Check each row/col/diagonal for a winner
    var lines = testCase.split('\n');
    var chars = [];
    _.each(lines, (line) => {
        chars.push(line.split(''));
    });

    // Yay brute force
    var toCheck = lines; // Rows

    // Cols
    _.each([0, 1, 2, 3], (i) => {
        toCheck.push(chars[0][i] + chars[1][i] + chars[2][i] + chars[3][i]);
    });

    // Diagonals
    toCheck.push(chars[0][0] + chars[1][1] + chars[2][2] + chars[3][3]);
    toCheck.push(chars[3][0] + chars[2][1] + chars[1][2] + chars[0][3]);

    for (var i = 0; i < toCheck.length; i++) {
        var winner = findWinner(toCheck[i]);
        //winston.info("Winner for " + toCheck[i] + " is " + winner);
        if (winner) {
            return winner + " won";
        }
    }

    // Otherwise, check to see if the game is finished or not
    if (s(testCase).contains('.')) {
        return "Game has not completed";
    }
    else {
        return "Draw";
    }
}

function fileToTestCases(input) {
    var testCases = [];

    var curTestCase = '';
    var line;
    while (input.length > 0) {
        line = s(input.shift()).trim().s;
        if (line != '') {
            curTestCase += line + '\n';
        }
        else {
            if (curTestCase != '') {
                testCases.push(s(curTestCase).trim().s);
                curTestCase = '';
            }
        }
    }

    if (curTestCase != '') {
        testCases.push(curTestCase);
    }

    return testCases;
}


if (process.argv.length < 3) {
    throw "Invalid parameters";
}

var fileFolder = './files/' + fileFolderName + '/';

var inputFileName = fileFolder + process.argv[2];

if (process.argv.length > 3) {
    var outputFileName = fileFolder + process.argv[3];
}

var testExpectedFile = false;
if (process.argv.length > 4) {
    testExpectedFile = true;
}

var input = fs.readFileSync(inputFileName, 'utf8').split('\n');
var numTestCases = parseInt(input.shift());
var testCases = fileToTestCases(input);

if (testCases.length != numTestCases) {
    throw 'Wrong number of test cases - ' + testCases.length + ' vs ' + numTestCases;
}

var done = 0;

function asyncTestCase(testCase, callback) {
    var result = processTestCase(testCase);

    process.stdout.write('.');
    done++;
    if (done % 10 == 0) {
        console.log('\n' + done);
    }

    callback(null, result);
}

function formatResult(result: string, i: number) {
    return "Case #" + (i+1) + ": " + result;
}

async.map(testCases, asyncTestCase, (err, results) => {
    if (err) {
        throw "Error processing test cases: " + err;
    }

    console.log("\nFinished processing test cases, outputting results");
    
    if (!outputFileName) {
        // Just write to stdout
        _.each(results, (result, index) => {
            console.log(formatResult(result, index));
        });
    }
    else {
        var output = '';
        _.each(results, (result, index) => {
            if (index > 0) {
                output += '\n';
            }
            output += formatResult(result, index);
        });
        
        if (testExpectedFile) {
            // Read in file and check against generated result
            console.log("\nChecking results against expected");

            var expected = fs.readFileSync(outputFileName, 'utf8');

            if (output == expected) {
                console.log("IT WORKS!!");
            }
            else {
                console.log("IT DIDN'T WORK!!");
                console.log("Expected:");
                console.log(expected);
                console.log("Got:");
                console.log(output);
            }
        }
        else {
            fs.writeFileSync(outputFileName, output, 'utf8');
        }
    }
});

treasure.ts

///<reference path='app.d.ts' />

import fs = module("fs")
import _ = module("underscore")
import winston = module("winston")
import async = module("async")

var s = require('string');
var extend = require('extend');

// Usage: node appname input-file [output-file] [test] 
//  all files stored in ./files/fileFolderName/*
//  if test load output-file and do a diff, else if output-file output to file

var fileFolderName = 'treasure';
var progressIncrement = 1; // Display progress after this number of test cases complete

function addOrIncrement(map, index) {
    if (index in map) {
        map[index]++;
    }
    else {
        map[index] = 1;
    }
}

function processTestCase(testCase: any, callback) {
    //winston.info("testCase", testCase);

    if (!sanityCheck(testCase)) {
        return callback("IMPOSSIBLE");
    }

    // Initialize state
    var state = { keysInHand: {}, chestsOpened: [], numChestsUnopened: 0, currentSequence: [] };
    _.each(testCase.startingKeys, (keyType) => { addOrIncrement(state.keysInHand, keyType); });
    _.each(testCase.chestSpecs, () => { state.chestsOpened.push(false); state.numChestsUnopened++;  });
    //winston.info('state', state);

    var completedSequences = [];
    tryOpeningChests(testCase, state, completedSequences, () => {
        //winston.info("completedSequences", completedSequences);
        if (completedSequences.length == 0) {
            return callback("IMPOSSIBLE");
        }
        else {
            // Find lexicographically smallest by converting all results to a string and sorting
            var possibleResults = [];
            _.each(completedSequences, (sequence) => {  
                var result = "";
                _.each(sequence, (num) => { result += num + " "; });
                possibleResults.push(s(result).trim().s);
            });
            possibleResults.sort();
            //winston.info("possibleResults", possibleResults);

            return callback(possibleResults[0]);
        }
    });
}

function findLexicographicallySmallest(sequences) {
    return sequences[0];
}

// Try to open each chest, update the state, and keep going until they are all open or we can't open any more
function tryOpeningChests(testCase, state, completedSequences, callback) {
    //winston.info("tryOpeningChests", state);
    var newStates = [];

    _.each(state.chestsOpened, (isChestOpen, chestIndex) => {
        if (!isChestOpen) {
            var newState = getStateAfterOpeningChest(testCase, state, chestIndex);

            if (!newState) {
                // Chest can't be opened, do nothing
            }
            else if (newState.numChestsUnopened == 0) {
                // We've opened all the chests so we're done!
                completedSequences.push(newState.currentSequence);
            }
            else {
                // Otherwise, keep trying to open chests
                newStates.push(newState);
            }
        }
    });
    
    //winston.info("newStates", newStates);
    if (newStates.length == 0) {
        // Opened all the chests we can, return
        return callback();
    }
    else if (completedSequences.length > 0) {
        // short-circuit
        return callback();
    }
    else {
        // Otherwise there are still chests to open, open all of them
        // ewwww again
        async.map(newStates, (newState, callback2) => { tryOpeningChests(testCase, newState, completedSequences, callback2); }, function (err, results) {
            return callback();
        });
    }
}

// Get the state after opening chest with number chestIndex+1
function getStateAfterOpeningChest(testCase, oldState, chestIndex): any {
    /* State consists of:
        - keysInHand: map of key type -> number of keys, if the number is 0 the record should be deleted
        - chestsOpened: array of all chests (chest #1 is at index 0), with a bool indicating whether it is open or not
        - numChestsUnopened: the count of "false" values in chestsOpened
        - currentSequence: The sequence of opened chests so far
    */
    
    var chestSpec = testCase.chestSpecs[chestIndex+1];
    var keyToOpen = chestSpec.keyToOpen;
    if (!(keyToOpen in oldState.keysInHand)) {
        return null; // Can't open
    }
    
    //winston.info('Opening chest ' + (chestIndex+1), oldState);

    // Clone existing state
    var newState = {}; 
    extend(true, newState, oldState); // keysInHand: {}, chestsOpened: [], numChestsUnopened: 0, currentSequence: [] };
    
    // Remove key from hand
    newState['keysInHand'][keyToOpen]--;
    if (newState['keysInHand'][keyToOpen] == 0) {
        delete newState['keysInHand'][keyToOpen];
        //winston.info('Removed keyToOpen ' + keyToOpen + " from hand", newState);
    }

    // Add keys from chest to hand
    _.each(chestSpec.keysInside, (keyType) => { addOrIncrement(newState['keysInHand'], keyType); });

    // Set chest as opened
    newState['chestsOpened'][chestIndex] = true;
    newState['numChestsUnopened']--;

    // Add opened chest to sequence
    newState['currentSequence'].push(chestIndex+1);
    
    //winston.info('Done opening chest ' + (chestIndex+1), newState);

    return newState;
}

// make sure that we have enough keys in total to open all chests
function sanityCheck(testCase) {
    var haveRequiredKeys = true;

    var totalKeys = {};
    var requiredKeys = {};
    _.each(testCase.startingKeys, (keyType) => { addOrIncrement(totalKeys, keyType); });
    _.each(testCase.chestSpecs, (chest) => {
        addOrIncrement(requiredKeys, chest.keyToOpen);
        _.each(chest.keysInside, (keyType) => { addOrIncrement(totalKeys, keyType); });
    });

    //winston.info('totalKeys', totalKeys);
    //winston.info('requiredKeys', requiredKeys);

    _.each(requiredKeys, (numKeysRequired, requiredKeyType) => {
        if (!(requiredKeyType in totalKeys) || numKeysRequired > totalKeys[requiredKeyType]) {
            winston.info("Sanity check failed, don't have enough of key type " + requiredKeyType +
                ", have " + totalKeys[requiredKeyType] + " but need " + numKeysRequired);
            haveRequiredKeys = false;
            return; //break
        }
    });

    return haveRequiredKeys;
}

function fileToTestCases(input) {
    var testCases = [];

    while (input.length > 0) {
        var line = s(input.shift()).trim().s;
        if (line == '') {
            continue;
        }

        // 1st line - number of keys you start with and the number of chests you need to open
        var numKeysAndChests = line.split(' ');
        var numKeys = parseInt(numKeysAndChests[0]);
        var numChests = parseInt(numKeysAndChests[1]);

        // 2nd line - the types of the keys that you start with
        var startingKeys = _.map(input.shift().split(' '), (num) => { return parseInt(num); });
        if (numKeys != startingKeys.length) throw "Invalid number of keys " + numKeys + " vs " + startingKeys.length;

        // N lines - Each line will begin with integers Ti and Ki, indicating the key type needed to open the chest and the number of keys inside the chest. 
        // These two integers will be followed by Ki more integers, indicating the types of the keys contained within the chest.
        var chests = {};
        for (var curChest = 1; curChest <= numChests; curChest++) {
            var chestRawData = _.map(input.shift().split(' '), (num) => { return parseInt(num); });
            var keyToOpen = chestRawData.shift();
            var numKeysInside = chestRawData.shift();
            if (numKeysInside != chestRawData.length) throw "Invalid number of keys inside chest " + numKeysInside + " vs " + chestRawData.length;

            chests[curChest] = { keyToOpen: keyToOpen, keysInside: chestRawData };
        }

        testCases.push({ startingKeys: startingKeys, chestSpecs: chests });
    }

    return testCases;
}


if (process.argv.length < 3) {
    throw "Invalid parameters";
}

var fileFolder = './files/' + fileFolderName + '/';

var inputFileName = fileFolder + process.argv[2];

if (process.argv.length > 3) {
    var outputFileName = fileFolder + process.argv[3];
}

var testExpectedFile = false;
if (process.argv.length > 4) {
    testExpectedFile = true;
}

var input = fs.readFileSync(inputFileName, 'utf8').split('\n');
var numTestCases = parseInt(input.shift());
var testCases = fileToTestCases(input);

if (testCases.length != numTestCases) {
    throw 'Wrong number of test cases - ' + testCases.length + ' vs ' + numTestCases;
}

var done = 0;

function asyncTestCase(testCase, callback) {
    //winston.info('asyncTestCase', testCase);
    /*
    var result = processTestCase(testCase);

    process.stdout.write('.');
    done++;
    if (done % progressIncrement == 0) {
        console.log('\n' + done);
    }

    callback(null, result);
    */

    processTestCase(testCase, (result) => { 
        console.log(".");
        callback(null, result);
    });
}

function formatResult(result: string, i: number) {
    return "Case #" + (i+1) + ": " + result;
}

async.map(testCases, asyncTestCase, (err, results) => {
    if (err) {
        throw "Error processing test cases: " + err;
    }

    console.log("\nFinished processing test cases, outputting results");
    
    if (!outputFileName) {
        // Just write to stdout
        _.each(results, (result, index) => {
            console.log(formatResult(result, index));
        });
    }
    else {
        var output = '';
        _.each(results, (result, index) => {
            if (index > 0) {
                output += '\n';
            }
            output += formatResult(result, index);
        });
        
        if (testExpectedFile) {
            // Read in file and check against generated result
            console.log("\nChecking results against expected");

            var expected = fs.readFileSync(outputFileName, 'utf8');

            if (output == expected) {
                console.log("IT WORKS!!");
            }
            else {
                console.log("IT DIDN'T WORK!!");
                console.log("Expected:");
                console.log(expected);
                console.log("Got:");
                console.log(output);
            }
        }
        else {
            fs.writeFileSync(outputFileName, output, 'utf8');
        }
    }
});