[SPOILER] AoC 2020 Day 1, part 2

aoc_2020_day_1_2.c

/*

# AoC day1 part 2

## Idea

Instead of thinking to combinatorial problem, I were inspired from pattern matching algo like https://en.wikipedia.org/wiki/Rete_algorithm

I read the file as a sequence of events and I maintain a data structure with the values we need for answering the question.
When we ecounter it, the solution is returned.

## Benchmarks

The slowest part of the code is not calculating the result but reading the file.

### Calculate the result

$ bench "./main on ../day1_1.csv"
benchmarking ./main on ../day1_1.csv
time                 3.806 ms   (3.799 ms .. 3.814 ms)
                     1.000 R²   (1.000 R² .. 1.000 R²)
mean                 3.805 ms   (3.798 ms .. 3.812 ms)
std dev              22.41 μs   (17.81 μs .. 29.07 μs)

### Do not calculate nothing, but count only lines and print the total

$ bench "./main off ../day1_1.csv"
benchmarking ./main off ../day1_1.csv
time                 2.760 ms   (2.745 ms .. 2.779 ms)
                     1.000 R²   (1.000 R² .. 1.000 R²)
mean                 2.751 ms   (2.746 ms .. 2.760 ms)
std dev              21.07 μs   (14.10 μs .. 31.28 μs)

### cat to /dev/null

$ bench "cat ../day1_1.csv > /dev/null"
benchmarking cat ../day1_1.csv > /dev/null
time                 3.292 ms   (3.279 ms .. 3.304 ms)
                     1.000 R²   (1.000 R² .. 1.000 R²)
mean                 3.297 ms   (3.291 ms .. 3.308 ms)
std dev              25.96 μs   (17.51 μs .. 44.36 μs)

*/

#include <stdio.h>
#include <string.h>
#include <Judy.h>

int main(int argc, char** argv)
{
    if (argc < 3) {
      printf("Usage: <on|off> <file-name>");
      return 1;
    }

    FILE* ptr = fopen(argv[2], "r");
    if (ptr==NULL)
    {
        printf("no such file.");
        return 0;
    }

    int skip_processing = 0;
    if (strcmp(argv[1], "off") == 0) {
      skip_processing = 1;
    }

    // e0, e1, e2 are the 3 distinct entries to combine.
    // e0 + e1 + e2 == target_sum
    const Word_t target_sum = 2020;

    // The set with the e0 we have found right now.
    Pvoid_t set_of_found_e0 = (Pvoid_t) NULL;

    // The map with missing e2 we are waiting for reaching target_sum.
    Pvoid_t map_of_missing_e2 = (Pvoid_t) NULL;

    // Read all the entries.
    // NOTE: every read entry is managed from the point of view of e0, e1 and e2
    // because it can be used in all three ways countemporary.
    Word_t entry;
    int count_entries = 0;
    while (fscanf(ptr,"%lu",&entry) == 1) {
      count_entries++;

      if (!skip_processing) {
        // no hope to have something of useful
        if (entry >= target_sum) {
          continue;
        }

        // Test if we have found a missing e2 (i.e. we have found a solution of the problem)
        Word_t e2 = entry;
        PWord_t  ptr_product_e0_e1;
        JLG(ptr_product_e0_e1, map_of_missing_e2, e2);
        if (ptr_product_e0_e1 != NULL) {
          Word_t result = (*ptr_product_e0_e1) * e2;
          printf("%lu", result);
          return 0;
        }

        // Update the map_of_missing_e2 with the new found e1 and previously found e0
        Word_t e1 = entry;
        Word_t e0_limit = target_sum - e1;
        int found_e0;
        Word_t e0 = 0;
        J1F(found_e0, set_of_found_e0, e0);
        while(found_e0) {
          Word_t missing_e2 = e0_limit - e0;
          if (missing_e2 > 0) {
            JLI(ptr_product_e0_e1, map_of_missing_e2, missing_e2);
            // NOTE: there can be multiple results, but we are interested to only one, so overwrite in any case
            (*ptr_product_e0_e1) = e0 * e1;
          } else {
            // this e0 and next e0 in the map are too much big
            break;
          }

          // next found e0 in ascending order
          J1N(found_e0, set_of_found_e0, e0);
        }

        // Add the new found e0
        Word_t ignore;
        J1S(ignore, set_of_found_e0, entry);
      }
    }

    if (skip_processing) {
      printf("Entries %d", count_entries);
    }

    return 0;
}