< up >
2020-12-01

AoC day 1

The puzzles of day one were easy to solve in the first place, but have more potential to optimize than I thought.

Problem

Find n addends which add up to 2020. Solution of the puzzle is the product of all addends where n=2 in puzzle one and n=3 in puzzle two.

Solution

The idea was to find all unique subsets with n elements, where n=2 in the algorithm below.

// ex: input array of integers
for i := 0; i < len(ex); i++ {
  for j := i + 1; j < len(ex); j++ {
    if ex[i]+ex[j] == 2020 {
      fmt.Printf("Found %d + %d = 2020\n", ex[i], ex[j])
      fmt.Printf("%d x %d = %d\n", ex[i], ex[j], ex[i] * ex[j])
    }
  }
}

The count of nested loops is equal to n which makes each subset accessible in the innermost loop. To ensure that the subset is unique, each inner loop starts with the index of the next outer loop plus one. By adding one all subsets are being skipped which share the same number.

Uniqueness is important to conquer both: Performance and wrong solutions. With unique subsets less than half the sums have to be calculated. Despite that, the puzzle says that all addends have to be different.

Visualization

On n=2, a simple brute force approach where the indices of all nested loops start at zero could be visualized with the following table. It shows the sum of all subsets with two elements made up from the input .

	1	2	3	4
1	2	3	4	5
2	3	4	5	6
3	4	5	6	7
4	5	6	7	8

The first observation one can make is the symmetry of the table. This is caused by the commutation property of addition which basically states that x+y = y+x. Good for us, we can get rid of almost one half and reduce the iteration count.

The next observation, is the diagonal. It is only made up of sums where the addends are equal. Better for us, we can get rid of them either.