Skip to content

Instantly share code, notes, and snippets.

@massimo-zaniboni
Created December 3, 2020 00:43
Show Gist options
  • Save massimo-zaniboni/8011294996e6ca451a3579328b5d7f74 to your computer and use it in GitHub Desktop.
Save massimo-zaniboni/8011294996e6ca451a3579328b5d7f74 to your computer and use it in GitHub Desktop.
[SPOILER] AoC 2020 Day 1, part 2
/*
# 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;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment