Programming Praxis: Feb 15, 2011

Below is my solution to the Programming Praxis problem from Feb. 15, 2011. The problem came from Google Code Jam Qualification Round Africa 2010. For more info, check this link.

// Author: William Clausen
// Date: Aug. 11, 2014
// Descpription: This file solves the programming praxis problem from
// Feb. 15, 2011

#include <vector>
#include <iostream>
#include <unordered_map>

using namespace std;

// Problem 1: Given a target number, C, determine if a set of +integers contains
// two integers that sum to the target.

// This function returns two positive integers representing the indices of the
// integers in the set whose sum is the target
vector<int> storeCredit(int credit, vector<int> itemPrices) {
	// Create result array to return. Populate it with -1's to represent
	// failed state
	vector<int> result (2, -1);

	// Loop through the items to determine if a solution exists.
	for (int i = 0; i < itemPrices.size(); ++i) {
		for (int j = i+1; j < itemPrices.size(); ++j) {
			if (itemPrices[i] + itemPrices[j] == credit) {
				result[0] = i+1;
				result[1] = j+1;
				break;
			}
		}
	}

	return result;
}

// Problem 2: Given a list of separated words, reverse the order of the words.

string reverseWordList(string message) {
	// It will be helpful to split the message into strings representing
	// words
	string result;
	string copy(message);
	int wordEnd = message.length() - 1;

	// Loop through the list looking for spaces denoting breaks between words.
	while (copy.find_last_of(' ') != string::npos) {
		int wordStart = copy.find_last_of(' ') + 1;
		result.append(copy.substr(wordStart, wordEnd));
		result.push_back(' ');
		wordEnd = wordStart - 1;
		copy = copy.substr(0, wordEnd);
		--wordEnd;
	}

	// We left the first word because there are no spaces after it, so
	// add the first word to the end of the result string.
	result.append(copy);

	return result;
}

// Problem 3: Write a function that takes in a string message and outputs the
// appropriate T9 keypresses for that message

// For simplicity, typedef the map type
typedef unordered_map<char, int> letterMap;

bool sameButton(int first, int second) {
	// Break down the numbers to a single digit, then compare the digits
	while (first > 10) {
		first /= 10;
	}

	while (second > 10) {
		second /= 10;
	}

	return first == second;
}

vector<int> t9Converter(string message) {
	vector<int> result;

	// Just some input checking to start
	if (message.length() == 0) {
		return result;
	}
	// First, we need an unordered map for the mapping of numbers to letters
	// according to T9 standards.
	letterMap map ( {{'a', 2}, {'b', 22}, {'c', 222},
		            {'d', 3}, {'e', 33}, {'f', 333},
		            {'g', 4}, {'h', 44}, {'i', 444},
		            {'j', 5}, {'k', 55}, {'l', 555},
		            {'m', 6}, {'n', 66}, {'o', 666},
		            {'p', 7}, {'q', 77}, {'r', 777}, {'s', 7777},
		            {'t', 8}, {'u', 88}, {'v', 888},
		            {'w', 9}, {'x', 99}, {'y', 999}, {'z', 9999},
		            {' ', 0}} );

	// So that we don't have to call empty all the time...
	result.push_back(map[message[0]]);

	for (int i = 1; i < message.length(); ++i) {
		int nextNum = map[message[i]];

		if (sameButton(result[i-1], nextNum) && nextNum != 0) {
			// Add a space, denoted by a -1
			result.push_back(-1);
		}

		result.push_back(nextNum);
	}

	return result;
}

And here are some tests I did to make sure everything worked properly.

// Test the solutions

// Test problem 1
void testProblem1() {
	// First example
	int credit = 100;
	vector<int> itemPrices = {5, 75, 25};

	vector<int> answer = storeCredit(credit, itemPrices);

	cerr << "Answer for first test case for store credit problem: ";
	cout << answer[0] << "," << answer[1];
	cout << "\n";

	// Second example
	credit = 200;
	itemPrices = {150, 24, 79, 50, 88, 345, 3};

	answer = storeCredit(credit, itemPrices);

	cout << "Answer for second test case for store credit problem: ";
	cout << answer[0] << "," << answer[1];
	cout << "\n";

	// Third example
	credit = 8;
	itemPrices = {2, 1, 9, 4, 4, 56, 90, 3};

	answer = storeCredit(credit, itemPrices);

	cout << "Answer for third test case for store credit problem: ";
	cout << answer[0] << "," << answer[1];
	cout << "\n";
}

// Test problem 2
void testProblem2() {
	string input = "this is a test";
	string output = reverseWordList(input);

	cout << "input: " << input << "\n";
	cout << "output: " << output << "\n";
	cout << "\n";

	input = "foobar";
	output = reverseWordList(input);

	cout << "input: " << input << "\n";
	cout << "output: " << output << "\n";
	cout << "\n";

	input = "all your base";
	output = reverseWordList(input);

	cout << "input: " << input << "\n";
	cout << "output: " << output << "\n";
	cout << "\n";
}

// Helper function for printing vectors for problem 3
void printT9(vector<int> t9Message) {
	for (int i = 0; i < t9Message.size(); ++i) {
		if (t9Message[i] == -1) {
			cout << " ";
		}
		else {
			cout << t9Message[i];			
		}
	}
	cout << "\n";
}

// Test problem 3
void testProblem3() {
	string input = "hi";
	vector<int> t9Message = t9Converter(input);

	cout << "input: " << input << "\n";
	cout << "output: ";
	printT9(t9Message);

	input = "yes";
	t9Message = t9Converter(input);

	cout << "input: " << input << "\n";
	cout << "output: ";
	printT9(t9Message);

	input = "foo  bar";
	t9Message = t9Converter(input);

	cout << "input: " << input << "\n";
	cout << "output: ";
	printT9(t9Message);

	input = "hello world";
	t9Message = t9Converter(input);

	cout << "input: " << input << "\n";
	cout << "output: ";
	printT9(t9Message);
}

// For testing purposes
int main() {
	testProblem1();
	testProblem2();
	testProblem3();
}