Given a set of N=4 numbers, determine if combining the 4 numbers via mathematical operations == 24

find24.cpp

#include <iostream>
#include <vector>
#include <map>

/*
 * find24 example
 *
 * Given 4 numbers as input,
 *
 * determine if the four numbers can combine to make 24
 * can use any operator to do calculation
 */

typedef enum {
	mul = 0,
	divi,
	add,
	sub
} OpType;

typedef std::vector< std::vector< std::vector<int> > > Mat3d;

std::string printVector(std::vector<int> arr){
	std::string result;
	for(int i = 0; i < (int)arr.size(); i++){
		result += std::to_string(arr[i]) + " ";
	}
	return result;
}

std::vector<int> find24Helper(std::vector<int> subArr, OpType optype, int i, int j){
	int val1 = subArr[i], val2 = subArr[j];
	int newVal = 0;
	switch(optype){
		case add:
			newVal = val1 + val2;
			break;
		case sub:
			newVal = val1 - val2;
			break;
		case divi:
			newVal = val1 / val2;
			break;
		case mul:
			newVal = val1 * val2;
			break;

	};
	subArr.erase(subArr.begin() + i);
	subArr.erase(subArr.begin() + j - 1);
	std::vector<int> newArr = {newVal};
	newArr.insert(newArr.end(), subArr.begin(), subArr.end());
	
	return newArr;
}

std::map<std::vector<int>, Mat3d> dp;

bool find24(std::vector<int> nums){
	if((int)nums.size() == 1 && nums[0] == 24){
		return true;
	}

	// calculate division
	for(int i = 0; i < (int)nums.size(); i++){
		for(int j = 0; j < (int)nums.size(); j++){
			if(i != j && nums[i] && nums[j]){
				bool result = find24(find24Helper(nums, mul, i, j)) || find24(find24Helper(nums, divi, i, j)) || find24(find24Helper(nums, add, i, j)) || find24(find24Helper(nums, sub, i, j));
				if(result){
					return true;	
				}
			}
		}
	}
	return false;
	
}

void test(std::vector<int> arr){
	bool result = find24(arr);
	std::string resultString = (result) ? "Success" : "Failure";
	std::cout << "For array: " << printVector(arr) << std::endl;;
	std::cout << resultString << std::endl;
}

int main(){
	test({6, 2, 3, 4});
	test({9, 9, 9, 9});
	test({0, 0, 0, 0});
	test({5, 2, 1, 3});
	return 0;
}

find24Memoize.cpp

#include <iostream>
#include <vector>
#include <map>

/*
 * find24 example
 *
 * Given 4 numbers as input,
 *
 * determine if the four numbers can combine to make 24
 * can use any operator to do calculation
 */

typedef enum {
	mul = 0,
	divi,
	add,
	sub
} OpType;

typedef std::vector< std::vector< std::vector<std::vector<int> > > > Mat4d;
typedef std::map<std::vector<int>, Mat4d> Mat4dMap;

std::string printVector(const std::vector<int> &arr){
	std::string result;
	for(int i = 0; i < (int)arr.size(); i++){
		result += std::to_string(arr[i]) + " ";
	}
	return result;
}



/**
 * Returns true if the index position exists in the array
 */
template <class T>
bool positionExists(const std::vector<T> &arr, int position){
	if(position < (int)arr.size()){
		return true;
	}
	return false;
}

/**
 *
 * Returns true if this the result array has been calculated already 
 *
 * @param dp The memoization table to store results, a 3d array where indices are the OpType [operation type (*, +, -, /)] 
 * @param arr The array of numbers we are going to do calculations on
 * @param optype The operation type. Based on enum defined called OpType. Can be mul, divi, add or sub
 * @param i The index of the first value in the array 'arr'.
 * @param j The index of the second value in the array 'arr'
 *
 * @return True if the newly calculated array can be inserted
 */
bool canInsert(Mat4dMap &dp, std::vector<int> arr, OpType optype, int i, int j){
	if(dp.count(arr) == 0){
		Mat4d a;
		for(int i = 0; i < 4; i++){
			a.push_back({});
			for(int j = 0; j <= (int)arr.size(); j++){
				a[i].push_back({});
				for(int k = 0; k <= (int)arr.size(); k++){
					a[i][j].push_back({});
				}
			}
		}
		dp[arr] = a;
		return false;
	}
	bool vectorExists = positionExists(dp[arr], optype) && positionExists(dp[arr][optype], i) && positionExists(dp[arr][optype][i], j);
	//std::cout << "vector exists: " << printVector(arr) << std::endl;
	return vectorExists && dp[arr][optype][i][j].size() > 0;
}

/**
 * Returns a new array of size n-1, where n is size of the initial array
 * Combines two of the initial array values at indices i, j using an operation (*, +, /, -)
 */
std::vector<int> find24Helper(std::vector<int> subArr, OpType optype, int i, int j){
	int val1 = subArr[i], val2 = subArr[j];
	int newVal = 0;
	switch(optype){
		case add:
			newVal = val1 + val2;
			break;
		case sub:
			newVal = val1 - val2;
			break;
		case divi:
			newVal = val1 / val2;
			break;
		case mul:
			newVal = val1 * val2;
			break;

	};
	subArr.erase(subArr.begin() + i);
	subArr.erase(subArr.begin() + j - 1);
	std::vector<int> newArr = {newVal};
	newArr.insert(newArr.end(), subArr.begin(), subArr.end());
	
	return newArr;
}
/**
 * Determines if the new sub array has been previously calculated. If not, it memoizes
 * the new result
 * 
 * Returns the calculated array
 */
std::vector<int> memoizeVector(Mat4dMap &dp, std::vector<int> nums, OpType optype, int i, int j){
	// Calculate the new array (size N-1) using the old array, if it hasn't been calculated
	// already
	bool arrExists = canInsert(dp, nums, optype, i, j);
	std::vector<int> resultArr = (arrExists) ? dp[nums][optype][i][j] : find24Helper(nums, optype, i, j);
	if(!arrExists){
		// Memoize the resultant array of size N-1
		dp[nums][optype][i][j] = resultArr;
	}
	return resultArr; 
}

/**
 * Returns true if a set of N numbers can be combined to equal a value (default is 24) 
 */
bool find24(std::vector<int> nums, Mat4dMap &dp){
	if((int)nums.size() == 1 && nums[0] == 24){
		return true;
	}

	// calculate division
	for(int i = 0; i < (int)nums.size(); i++){
		for(int j = 0; j < (int)nums.size(); j++){
			if(i == j || !nums[i] || !nums[j]){
				continue;
			}
			
			std::vector<int> mulVec = memoizeVector(dp, nums, mul, i, j);
			std::vector<int> addVec = memoizeVector(dp, nums, add, i, j);
			std::vector<int> subVec = memoizeVector(dp, nums, sub, i, j);
			std::vector<int> diviVec = memoizeVector(dp, nums, divi, i, j);
			bool result = find24(mulVec, dp) || find24(addVec, dp) || 
				find24(subVec, dp) || find24(diviVec, dp);
			if(result){
				return true;	
			}
		}
	}
	return false;
}

void test(std::vector<int> arr){
	Mat4dMap dp;
	bool result = find24(arr, dp);
	std::string resultString = (result) ? "Success" : "Failure";
	std::cout << "For array: " << printVector(arr) << std::endl;;
	std::cout << resultString << std::endl;
}

int main(){
	test({6, 2, 3, 4});
	test({9, 9, 9, 9});
	test({0, 0, 0, 0});
	test({5, 2, 1, 3});
	test({4, 4, 4, 4});
	return 0;
}

Makefile

CC=g++
CFLAGS=-g -std=c++11
EXE=find24
EXE2=find24Memoize

all: $(EXE) $(EXE2) 
	
$(EXE): find24.cpp 
	$(CC) $(CFLAGS) find24.cpp -o $(EXE)

$(EXE2): find24Memoize.cpp
	$(CC) $(CFLAGS) find24Memoize.cpp -o $(EXE2)

run:
	./$(EXE)

run2:
	./$(EXE2)
clean:
	rm -rf $(EXE) $(EXE2)

Given a set of 4 numbers, determine if those 4 numbers can be combined to equal 24. The numbers can be combined via multiplication, addition, subtraction or division. The numbers can be ordered in anyway (they don't have to be sorted). Return true if you can do it with those four numbers, false if you can't.

The numbers must be in the range from 1-9.

Example

[6, 2, 3, 4] -> true
[9, 9, 9, 9] -> false