A bunch of smart YouTube viewers said my algorithm is horribly inefficient since it was O(n) and I could have used a hash reducing it to O(1). Well, it turns out they were right, except somehow they forgot to account for the data set size which is a big impact on how slow the algorithm *actually* is. Whoopsy!

How "slow" is brute force?.cpp

// System Specs
// ============
// These benchmarks were run on an Intel i7-9700k @ 3.6 GHz
//
// How it was run
// ===============
// The correct recipe is at the very end of the list of recipes. Which means this must run
// through the entire list, the worst case scenario. The rest of the recipes are randomized
// to offer some variation, but I don't set the slots where the correct recipe has the correct slots.
// to ensure we don't accidentally exit early.
// 
// The hash is computed for each recipe by summing and xoring values multiplied by a prime number.
// See the hashRecipe() function for more details
// 
// The test is run 10,000 times for the first 3 tests, 1,000 times for the outrageous test, and 10
// times for the incredibly outrageous test operating on 13 Gigabytes of binary recipe data.
// 
// 
// THE RESULTS
// ===========
// 
// (The amount of recipes in Vanilla Minecraft as of 1.16)
// Running the algorithm with 379 recipes 10,000 times
// ===================================================
// Original Algorithm Avg Time: 8.06959 [microseconds] ~8x slower
//     Hash Algorithm Avg Time: 1.38105 [microseconds] ~6 microsecond performance gain
// Hash Set Algorithm Avg Time: 1.17415 [nanoseconds]
// 
// Original Algorithm Max Time: 453.2   [microseconds]
//     Hash Algorithm Max Time: 69.3    [microseconds]
// Hash Set Algorithm Max Time: 78.9    [nanoseconds]
// 
// Original Algorithm Min Time: 7.2     [microseconds]
//     Hash Algorithm Min Time: 1.2     [microseconds]
// Hash Set Algorithm Min Time: 0.9     [nanoseconds]
//
//
// 
// (Crazy number I will most likely never reach)
// Running the algorithm with 1,000 recipes 10,000 times
// =====================================================
// Original Algorithm Avg Time: 18.6516 [microseconds] ~9x slower
//     Hash Algorithm Avg Time: 2.49611 [microseconds] ~16 microsecond performance gain
// Hash Set Algorithm Avg Time: 1.25757 [nanoseconds]
// 
// Original Algorithm Max Time: 1084.5  [microseconds]
//     Hash Algorithm Max Time: 63.8    [microseconds]
// Hash Set Algorithm Max Time: 74.9    [nanoseconds]
// 
// Original Algorithm Min Time: 17.1    [microseconds]
//     Hash Algorithm Min Time: 2.1     [microseconds]
// Hash Set Algorithm Min Time: 1       [nanoseconds]
//
// 
// 
// (Outrageous number I definitely will never reach)
// Running the algorithm with 10,000 recipes 10,000 times
// ======================================================
// Original Algorithm Avg Time: 174.283  [microseconds] ~9.6x slower
//     Hash Algorithm Avg Time: 18.5532  [microseconds] ~160 microsecond performance gain (uh oh, this might actually lag for 1/5th of a frame)
// Hash Set Algorithm Avg Time: 1.12915  [nanoseconds]
// 
// Original Algorithm Max Time: 3593.5   [microseconds]
//     Hash Algorithm Max Time: 112.4    [microseconds]
// Hash Set Algorithm Max Time: 10       [nanoseconds]
// 
// Original Algorithm Min Time: 165.9    [microseconds]
//     Hash Algorithm Min Time: 16.5     [microseconds]
// Hash Set Algorithm Min Time: 0.9      [nanoseconds]
//
// 
// 
// 
// Just for fun
// 
// Just remember, 1 frame at 60FPS gives us a grand total of (16ms to work with)
// 
// 
// (Absolutely insane number just to illustrate how ridiculous this is)
// 
// [The "slow" version just barely takes 1 whole frame to calculate, 
//  meaning 1 FRAME of a lag spike. Oh dear, the gamers are gonna kill me
//  for that 1 FRAME lag spike while they were crafting their recipe]
// 
// Running the algorithm with 1,000,000 recipes 1,000 times 
// ========================================================
// Original Algorithm Avg Time: 18350.1 [microseconds] (18.350 ms) 
//     Hash Algorithm Avg Time: 2434.4  [microseconds] (2.4344 ms) 
// Hash Set Algorithm Avg Time: 1.0678  [nanoseconds]             
// 
// Original Algorithm Max Time: 33763.6 [microseconds] (33.76 ms)
//     Hash Algorithm Max Time: 3990.7  [microseconds] (3.991 ms)
// Hash Set Algorithm Max Time: 17.7    [nanoseconds]
// 
// Original Algorithm Min Time: 16965.8 [microseconds] (16.97 ms)
//     Hash Algorithm Min Time: 2233.2  [microseconds] (2.233 ms)
// Hash Set Algorithm Min Time: 0.8     [nanoseconds]
// 
// 
// 
// 
// I only ran this next one 10 times because it's much slower,
// however please note: This is operating on 13 GIGABYTES OF DATA
// 
// 
// (13 GIGABYTES OF DATA... GIGABYTES!!!)
// Running the algorithm with 100,000,000 recipes 10 times
// =======================================================
// Original Algorithm Avg Time: 1.92073e+06 [microseconds] (1.92073  seconds) ~9.5x slower
//     Hash Algorithm Avg Time: 239569      [microseconds] (0.239569 seconds)
// Hash Set Algorithm Avg Time: 1.19        [nanoseconds]
// 
// Original Algorithm Max Time: 1.97881e+06 [microseconds] (1.97881  seconds)
//     Hash Algorithm Max Time: 245201      [microseconds] (0.245201 seconds)
// Hash Set Algorithm Max Time: 2.5         [nanoseconds]
// 
// Original Algorithm Min Time: 1.8519e+06  [microseconds] (1.8519   seconds)
//     Hash Algorithm Min Time: 236272      [microseconds] (0.236272 seconds)
// Hash Set Algorithm Min Time: 0.8         [nanoseconds]
// 



#include <cstdint>
#include <vector>
#include <chrono>
#include <iostream>
#include <assert.h>
#include <unordered_set>

struct CraftingRecipe
{
	int maxWidth;
	int maxHeight;
	// 9 is the max crafting size
	uint16_t blockIds[9];
	int16_t output;
	uint8_t outputCount;
};

struct InventorySlot
{
	uint16_t blockId;
	uint8_t count;
};

std::vector<CraftingRecipe> getAllCraftingRecipes()
{
	std::vector<CraftingRecipe> res;
	CraftingRecipe r{};

	// Change this to get the number of recipes to test with
	constexpr int numRecipes = 379;
	for (int i = 0; i < numRecipes - 1; i++)
	{
		r.blockIds[0] = (uint16_t)(((float)rand() / (float)RAND_MAX) * 80.0f);
		r.blockIds[2] = (uint16_t)(((float)rand() / (float)RAND_MAX) * 80.0f);
		r.blockIds[6] = (uint16_t)(((float)rand() / (float)RAND_MAX) * 80.0f);
		r.blockIds[8] = (uint16_t)(((float)rand() / (float)RAND_MAX) * 80.0f);
		res.push_back(r);
	}

	// Push the matching recipe on last so that we MUST iterate every single recipe to
	// thoroughly test the worst case scenario
	r = {};
	r.blockIds[1] = 39;
	r.blockIds[3] = 39;
	r.blockIds[5] = 10;
	r.maxWidth = 3;
	r.maxHeight = 3;
	r.output = 420;
	r.outputCount = 69;
	res.push_back(r);

	return res;
}

struct CraftingRecipeHash
{
	CraftingRecipe recipe;
	uint32_t hash;
};

// Helper function that returns negative modulus the same way a language like python would
int negativeMod(int value, int lowerBound, int upperBound)
{
	int rangeSize = upperBound - lowerBound + 1;

	if (value < lowerBound)
	{
		value += rangeSize * ((lowerBound - value) / rangeSize + 1);
	}

	return lowerBound + (value - lowerBound) % rangeSize;
}

uint32_t hashCraftingRecipe(const uint16_t* inventorySlots)
{
	uint32_t hashedValue = 17;
	for (int i = 0; i < 9; i++)
	{
		hashedValue = (uint32_t)((uint64_t)(hashedValue * 37 + std::hash<uint16_t>()(inventorySlots[i])) % (UINT32_MAX));
	}
	return hashedValue;
}

// NOTE: Same hash algorithm, just computed for two different types

uint32_t hashInventory(InventorySlot* craftingSlots)
{
	// We have to flip the Y-axis here to match the game
	uint32_t hashedValue = 17;
	for (int i = 0; i < 9; i++)
	{
		if (i >= 0 && i <= 2)
		{
			hashedValue = (uint32_t)((uint64_t)(hashedValue * 37 + std::hash<uint16_t>()(craftingSlots[i + 6].blockId)) % (UINT32_MAX));
		}
		else if (i >= 6 && i <= 8)
		{
			hashedValue = (uint32_t)((uint64_t)(hashedValue * 37 + std::hash<uint16_t>()(craftingSlots[i - 6].blockId)) % (UINT32_MAX));
		}
		else
		{
			hashedValue = (uint32_t)((uint64_t)(hashedValue * 37 + std::hash<uint16_t>()(craftingSlots[i].blockId)) % (UINT32_MAX));
		}
	}
	return hashedValue;
}

std::vector<CraftingRecipeHash> getRecipesWithHash(const std::vector<CraftingRecipe>& allRecipes)
{
	std::vector<CraftingRecipeHash> recipesWithHash = std::vector<CraftingRecipeHash>();
	for (auto& r : allRecipes)
	{
		CraftingRecipeHash hashRecipe;
		hashRecipe.recipe = r;
		hashRecipe.hash = hashCraftingRecipe(r.blockIds);
		recipesWithHash.emplace_back(hashRecipe);
	}

	return recipesWithHash;
}

class CraftingRecipeHasher
{
public:
	size_t operator()(const CraftingRecipe& recipe) const
	{
		size_t hashedValue = 17;
		for (int i = 0; i < 9; i++)
		{
			hashedValue = (uint32_t)((uint64_t)(hashedValue * 37 + std::hash<uint16_t>()(recipe.blockIds[i])) % (UINT32_MAX));
		}
		return hashedValue;
	}
};

class CraftingRecipeEquality
{
public:
	bool operator()(const CraftingRecipe& r1, const CraftingRecipe& r2) const
	{
		for (int row = 0; row < 3; row++)
		{
			for (int column = 0; column < 3; column++)
			{
				int blockId = r2.blockIds[column + (row * 3)];
				bool isMatch = true;
				for (int recipeRow = 0; recipeRow < 3 && isMatch; recipeRow++)
				{
					for (int recipeColumn = 0; recipeColumn < 3; recipeColumn++)
					{
						int recipeBlockId = recipeBlockId = r1.blockIds[recipeColumn + (recipeRow * 3)];
						int currentBlockId = r2.blockIds[((recipeColumn + column) % 3) + (((recipeRow + row) % 3) * 3)];
						if (recipeBlockId != currentBlockId)
						{
							isMatch = false;
							break;
						}
					}
				}

				if (isMatch)
				{
					return true;
				}
			}
		}

		return false;
	}
};

std::unordered_set<CraftingRecipe, CraftingRecipeHasher, CraftingRecipeEquality> getAllRecipesAsHashSet(const std::vector<CraftingRecipe>& allRecipes)
{
	auto res = std::unordered_set<CraftingRecipe, CraftingRecipeHasher, CraftingRecipeEquality>();
	for (auto& recipe : allRecipes)
	{
		res.insert(recipe);
	}

	return res;
}

// Exact same algorithm I'm using right now
bool ogAlgorithm(InventorySlot* craftingSlots, const std::vector<CraftingRecipe>& allRecipes)
{
	for (auto& recipe : allRecipes)
	{
		int firstBlockIdInRecipe = recipe.blockIds[0];
		for (int row = 0; row < 3; row++)
		{
			for (int column = 0; column < 3; column++)
			{
				// The crafting slots are stored bottom -> up in the array
				// so flip the y axis here
				int blockId = craftingSlots[column + ((2 - row) * 3)].blockId;
				if (blockId == firstBlockIdInRecipe)
				{
					bool isMatch = true;
					for (int recipeRow = 0; recipeRow < 3 && isMatch; recipeRow++)
					{
						for (int recipeColumn = 0; recipeColumn < 3; recipeColumn++)
						{
							int recipeBlockId = recipeBlockId = recipe.blockIds[recipeColumn + (recipeRow * 3)];
							int currentBlockId = craftingSlots[((recipeColumn + column) % 3) + (negativeMod((2 - (recipeRow + row)), 0, 2) * 3)].blockId;
							if (recipeBlockId != currentBlockId)
							{
								isMatch = false;
								break;
							}
						}
					}

					if (isMatch)
					{
						craftingSlots[9].blockId = recipe.output;
						craftingSlots[9].count = recipe.outputCount;
						return true;
					}
				}
			}
		}
	}

	return false;
}

// Exact same algorith, except using a hash to early out
bool ogAlgorithmWithHash(InventorySlot* craftingSlots, const std::vector<CraftingRecipeHash>& allRecipes)
{
	uint32_t hash = hashInventory(craftingSlots);

	for (auto& recipeWithHash : allRecipes)
	{
		if (recipeWithHash.hash != hash)
		{
			continue;
		}
		const CraftingRecipe& recipe = recipeWithHash.recipe;

		int firstBlockIdInRecipe = recipe.blockIds[0];
		for (int row = 0; row < 3; row++)
		{
			for (int column = 0; column < 3; column++)
			{
				// The crafting slots are stored bottom -> up in the array
				// so flip the y axis here
				int blockId = craftingSlots[column + ((2 - row) * 3)].blockId;
				if (blockId == firstBlockIdInRecipe)
				{
					bool isMatch = true;
					for (int recipeRow = 0; recipeRow < 3 && isMatch; recipeRow++)
					{
						for (int recipeColumn = 0; recipeColumn < 3; recipeColumn++)
						{
							int recipeBlockId = recipeBlockId = recipe.blockIds[recipeColumn + (recipeRow * 3)];
							int currentBlockId = craftingSlots[((recipeColumn + column) % 3) + (negativeMod((2 - (recipeRow + row)), 0, 2) * 3)].blockId;
							if (recipeBlockId != currentBlockId)
							{
								isMatch = false;
								break;
							}
						}
					}

					if (isMatch)
					{
						craftingSlots[9].blockId = recipe.output;
						craftingSlots[9].count = recipe.outputCount;
						return true;
					}
				}
			}
		}
	}

	return false;
}

// Let's test this
int main()
{
	std::vector<CraftingRecipe> allRecipes = getAllCraftingRecipes();
	std::vector<CraftingRecipeHash> allRecipesWithHash = getRecipesWithHash(allRecipes);
	auto allRecipesAsHashSet = getAllRecipesAsHashSet(allRecipes);

	// Y-Axis must be flipped to match the game
	InventorySlot inventorySlots[10] = {};
	inventorySlots[7].blockId = 39;
	inventorySlots[3].blockId = 39;
	inventorySlots[5].blockId = 10;

	constexpr int numRuns = 10'000;

	// Let's time it

	// Run it 10,000 times then print the results
	float ogAlgoAvgNanoseconds = 0;
	float ogMaxNanoSeconds = 0;
	float ogMinNanoSeconds = FLT_MAX;
	std::cout << "Test Og algorithm 1,000 times" << std::endl << std::endl;
	for (int i = 0; i < numRuns; i++)
	{
		// Time it
		std::chrono::steady_clock::time_point begin = std::chrono::steady_clock::now();
		inventorySlots[9].blockId = 0;
		inventorySlots[9].count = 0;
		bool res = ogAlgorithm(inventorySlots, allRecipes);
		std::chrono::steady_clock::time_point end = std::chrono::steady_clock::now();

		// Make sure it was valid
		assert(res, "Didn't find match the recipe for some reason.");
		assert(inventorySlots[9].blockId == 420, "Didn't get the right output id.");
		assert(inventorySlots[9].count == 69, "Didn't get the right output count.");

		std::cout << "Run (" << i << "): Time difference = " << std::chrono::duration_cast<std::chrono::microseconds>(end - begin).count() << "[µs]" << std::endl;
		std::cout << "Run (" << i << "): Time difference = " << std::chrono::duration_cast<std::chrono::nanoseconds> (end - begin).count() << "[ns]" << std::endl;
		float numNanoSeconds = std::chrono::duration_cast<std::chrono::nanoseconds> (end - begin).count();
		ogAlgoAvgNanoseconds += numNanoSeconds;
		ogMaxNanoSeconds = numNanoSeconds > ogMaxNanoSeconds ? numNanoSeconds : ogMaxNanoSeconds;
		ogMinNanoSeconds = numNanoSeconds < ogMinNanoSeconds ? numNanoSeconds : ogMinNanoSeconds;
	}
	ogAlgoAvgNanoseconds /= (float)numRuns;

	// Run it 10,000 times print the results and at the end the average
	float hashAlgoAvgNanoseconds = 0;
	float hashMaxNanoSeconds = 0;
	float hashMinNanoSeconds = FLT_MAX;
	std::cout << "Test Hash algorithm 1,000 times" << std::endl << std::endl;
	for (int i = 0; i < numRuns; i++)
	{
		// Time it
		std::chrono::steady_clock::time_point begin = std::chrono::steady_clock::now();
		inventorySlots[9].blockId = 0;
		inventorySlots[9].count = 0;
		bool res = ogAlgorithmWithHash(inventorySlots, allRecipesWithHash);
		std::chrono::steady_clock::time_point end = std::chrono::steady_clock::now();

		// Make sure it was valid
		assert(res, "Didn't match the recipe for some reason.");
		assert(inventorySlots[9].blockId == 420, "Didn't get the right output id.");
		assert(inventorySlots[9].count == 69, "Didn't get the right output count.");

		std::cout << "Run (" << i << "): Time difference = " << std::chrono::duration_cast<std::chrono::microseconds>(end - begin).count() << "[microseconds]" << std::endl;
		std::cout << "Run (" << i << "): Time difference = " << std::chrono::duration_cast<std::chrono::nanoseconds> (end - begin).count() << "[nanoseconds]" << std::endl;
		float numNanoSeconds = std::chrono::duration_cast<std::chrono::nanoseconds> (end - begin).count();
		hashAlgoAvgNanoseconds += numNanoSeconds;
		hashMaxNanoSeconds = numNanoSeconds > hashMaxNanoSeconds ? numNanoSeconds : hashMaxNanoSeconds;
		hashMinNanoSeconds = numNanoSeconds < hashMinNanoSeconds ? numNanoSeconds : hashMinNanoSeconds;
	}
	hashAlgoAvgNanoseconds /= (float)numRuns;

	// Run it 10,000 times print the results and at the end the average
	float hashSetAlgoAvgNanoseconds = 0;
	float hashSetMaxNanoSeconds = 0;
	float hashSetMinNanoSeconds = FLT_MAX;
	std::cout << "Test Hash algorithm 1,000 times" << std::endl << std::endl;
	for (int i = 0; i < numRuns; i++)
	{
		// I'm not timing this part since it's technically not part of the search algorithm
		inventorySlots[9].blockId = 0;
		inventorySlots[9].count = 0;
		CraftingRecipe inventorySlotsAsRecipe = {};
		for (int i = 0; i < 9; i++)
		{
			if (i >= 0 && i <= 2)
			{
				inventorySlotsAsRecipe.blockIds[i] = inventorySlots[(i + 6)].blockId;
			}
			else if (i >= 6 && i <= 8)
			{
				inventorySlotsAsRecipe.blockIds[i] = inventorySlots[(i - 6)].blockId;
			}
			else
			{
				inventorySlotsAsRecipe.blockIds[i] = inventorySlots[i].blockId;
			}
		}

		// Time it
		std::chrono::steady_clock::time_point begin = std::chrono::steady_clock::now();
		auto iter = allRecipesAsHashSet.find(inventorySlotsAsRecipe);
		std::chrono::steady_clock::time_point end = std::chrono::steady_clock::now();

		// This is a dumb way to do things, but I'd rather not change a bunch of code
		// so I'm just jury rigging this in like this
		inventorySlots[9].blockId = iter->output;
		inventorySlots[9].count = iter->outputCount;

		// Make sure it was valid
		assert(iter != allRecipesAsHashSet.end(), "Didn't match the recipe for some reason.");
		assert(inventorySlots[9].blockId == 420, "Didn't get the right output id.");
		assert(inventorySlots[9].count == 69, "Didn't get the right output count.");

		std::cout << "Run (" << i << "): Time difference = " << std::chrono::duration_cast<std::chrono::microseconds>(end - begin).count() << "[microseconds]" << std::endl;
		std::cout << "Run (" << i << "): Time difference = " << std::chrono::duration_cast<std::chrono::nanoseconds> (end - begin).count() << "[nanoseconds]" << std::endl;
		float numNanoSeconds = std::chrono::duration_cast<std::chrono::nanoseconds> (end - begin).count();
		hashSetAlgoAvgNanoseconds += numNanoSeconds;
		hashSetMaxNanoSeconds = numNanoSeconds > hashSetMaxNanoSeconds ? numNanoSeconds : hashSetMaxNanoSeconds;
		hashSetMinNanoSeconds = numNanoSeconds < hashSetMinNanoSeconds ? numNanoSeconds : hashSetMinNanoSeconds;
	}
	hashSetAlgoAvgNanoseconds /= (float)numRuns;

	// Print results
	std::cout << std::endl << std::endl;
	std::cout << "Original Algorithm Avg Time: " << (ogAlgoAvgNanoseconds / 1000.0f) << "[microseconds]" << std::endl;
	std::cout << "Hash     Algorithm Avg Time: " << (hashAlgoAvgNanoseconds / 1000.0f) << "[microseconds]" << std::endl;
	std::cout << "Hash Set Algorithm Avg Time: " << (hashSetAlgoAvgNanoseconds / 1000.0f) << "[nanoseconds]" << std::endl << std::endl;

	std::cout << "Original Algorithm Max Time: " << (ogMaxNanoSeconds / 1000.0f) << "[microseconds]" << std::endl;
	std::cout << "Hash     Algorithm Max Time: " << (hashMaxNanoSeconds / 1000.0f) << "[microseconds]" << std::endl;
	std::cout << "Hash Set Algorithm Max Time: " << (hashSetMaxNanoSeconds / 1000.0f) << "[nanoseconds]" << std::endl << std::endl;

	std::cout << "Original Algorithm Min Time: " << (ogMinNanoSeconds / 1000.0f) << "[microseconds]" << std::endl;
	std::cout << "Hash     Algorithm Min Time: " << (hashMinNanoSeconds / 1000.0f) << "[microseconds]" << std::endl;
	std::cout << "Hash Set Algorithm Min Time: " << (hashSetMinNanoSeconds / 1000.0f) << "[nanoseconds]" << std::endl << std::endl;

	return 0;
}