“Start ‘em off hard! Clear out the riff-raff!”

I’m assuming that’s what was said when the Day 1 problem for the 2020 Advent of Code was being written. This problem is an NP-complete problem in disguise. Key characteristics of an NP-complete problem are:

  1. NP-complete problems cannot be solved efficiently in polynomial time. That is, the number of operations required to solve the problem, expressed as a function of the “size” of the inputs, grows too quickly to be solved efficiently as the problem size grows larger.
  2. NP-complete problems can be verified efficiently. Put another way, given a problem P and a proposed solution S, there are efficient algorithms to verify that S is or is not a solution to P.

So, what is the Day 1 problem, and why is it an NP-complete problem?

The problem consists of finding a pair of numbers in a list that sum to a particular value, in this case 2020, and computing the product of the two numbers. The general form of this problem is the SUBSET-SUM problem, and is known to be in NP-complete. Showing that this problem is NP-complete requires a proof, and rather than write one for you, I am taking the easy way out and linking to this proof from Cornell University.

To solve part 1, you can get away with a simple solution using sets. Assuming you have the numbers read into a set, you can iterate over the set, checking for each number n to see if 2020 - n is in the set. Sets give order O(1) lookup time, so the runtime of this algorithm will be fast, requiring at most n - 1 lookups:

for num in nums:
  if 2020 - num in nums:
    p1 = num * (2020 - num)
	break

For part 2, you have to find three numbers that sum to 2020. This is exactly the same problem as before, but now you will require a nested for loop to perform the same calculation:

for num1 in nums:
  for num2 in nums:
	n = num1 + num2
	if (2020 - n) in nums:
	  p2 = num1 * num2 * (2020 - n)
	  break

Alternatively:

for num1 in nums:
  for num2 in nums:
    for num3 in nums:
	  if num1 + num2 + num3 in nums:
	    p2 = num1 * num2 * num3
		break

A more efficient algorithm could be devised, since SUBSET-SUM is a known problem, but the cost-benefit ratio would be way out of balance to write, debug, and run the most efficient algorithm possible.

So, a hard computational problem, but one that was almost trivial to solve in terms of time to write a basic solution.