Module day01 

Report Repair

The straightforward approach is to compare every possible pair of elements for part one and every possible triple for part two. This would have O(n²) and O(n³) time complexity respectively.

We can do better with O(n) complexity for part one and O(n²) for part two.

For part one we use an implicit hash table in an array, since values are constrained to between 0 and 2020 and each value is already perfectly hashed. For each entry we check the index at its value. If this is marked then we have seen the reciprocal 2020 - value before so we have found the answer. Creating this array also performs a radix sort that will be used in part two.

Functions

parse

part1

part2

Type Aliases

Input 🔒