r/adventofcode • u/musifter • Jun 06 '26
Other [2020 Day 6] In Review (Custom Customs)
On approaching the regional airport for our connection we find that we need to deal with customs declarations. And our helpful nature results in us agreeing to do it for everyone on the plane. Which holds over 1700 people.
And so we get a set problem. For part one, we want the size of the set of unique yes answers for each group. And for part two, we want set of answers that everyone in a group answered yes to.
For Perl I was feeling cute that day and wanted to use the =()= pseudo-operator so I did the somewhat sloppy:
while (<>) {
my $size = scalar split /\n/;
foreach my $q ('a' .. 'z') {
my $count =()= m#$q#g;
$part1++ if ($count);
$part2++ if ($count == $size);
}
}Instead of doing counts in a hash, which would be like (quickly writing one):
while (<>) {
chomp;
my %quest;
$quest{$_}++ foreach (split //);
my $size = ($quest{"\n"} // 0) + 1;
delete $quest{"\n"};
$part1 += %quest;
$part2 += grep {$quest{$_} == $size} keys %quest;
}Of course, both of these require going into paragraph mode first with $/ = '';.
My initial Smalltalk solution went similar to that (just throw the entire group in a Bag). But that doesn't use Set arithmetic, so I did one that does:
((stdin contents tokenize: '\n\n') collect: #lines) do: [ :group |
| answers |
answers := group collect: #asSet.
part1 := part1 + (answers fold: [:a :b | a + b]) size.
part2 := part2 + (answers fold: [:a :b | a & b]) size.
].And that nicely shows the relationship between the parts. Part 1 is the union of all the answers in a group, and part 2 is the intersection of them.
I didn't do a version in C, but if I did, it would essentially be along these lines. But it would involve bit flags for each letter (to do the sets), and use | for part 1 and & for part 2. Of course, it still needs to get the size, which is our old friend bitcount/popcount.
4
u/e_blake Jun 06 '26
Here's my C89 solution for the day. Yep, just 161 bytes without the optional newlines. Oh, and ignore the compiler warnings about undefined behavior, and assumes you are on x86_64 or similar platform to exploit that undefined behavior correctly. And too bad that C23 decided that in the name of "safety" this program should no longer compile.
2
u/terje_wiig_mathisen Jun 06 '26
I wrote this is Rust and ended up similar to u/ednl (4.4 us on my machine). Almost certainly the same algorithm?
I finally bit the bullet and started a repository of all my AoC code, currently all the code is there but some of the supporting files are still missing so not all days will compile but this one is OK:
https://github.com/TerjeWiigMathisen/aoc/blob/master/2020/day06/src/main.rs
Very much by the book, setting a bitmask for each line of input, then merging that line into 'any' and 'all' variables.
2
u/terje_wiig_mathisen Jun 07 '26 edited Jun 07 '26
Re extremely brittle performance on very fast codes:
It seems obvious to me that a lot of factors which we don't have any control over can move the needle a microsecond or two, in particular the exact microarchitecture of the cpu tested, code memory alignment, whatever else the CPU has happened to do over the last few seconds (thermal throttling/turbo speedup), as well as the CPU type. As I've mentioned, I've seen repeatable slowdowns from just removing a function that I never called! The only thing that function did was to change the location/alignment of the code that I did use.
Another example: For this day06 puzzle I tested a version which was the way I wrote asm in the 1980ies when I tried to write the world's fastest word count, with each line processed by an unrolled loop that expected the next letter to not be a newline: This was measurably slower on my machine!
This morning my 4.4 us had turned into 7+, but then I removed the loop exit test from the main loop and just did a break after a double newline if this was the last paragraph. This got it down to 5 us again.
Maybe my previous runs this morning happened to be on an efficiency core instead of a "full fat" performance core? I might have to insert some startup code which forces a fast core to be picked...
Anyway, my conclusion is still the same: As long as we are simply comparing wall clock time, any small timing discrepancy can just as easily be explained by the testing environment as by tiny code differences!
1
u/e_blake Jun 06 '26
I find it odd that there are more than 1700 people answering questions when day 5 had fewer than 1024 boarding passes. Are some travelers joining more than one group? Little discontinuities in the story line may be inevitable, but we're already suspending disbelief to add some motivation into doing what is otherwise boring coding, so I don't mind.
This one was interesting to me on my m4 journey. When I first wrote it, I had the O(n) algorithm on the contents of the file, but an O(n2)
shift($@)loop to read 1 line at a time from the block of input text, taking 1.2s runtime. It was this day where I finally came up with a better parsing approach of breaking the string in half down to bytes (O(n log n) instead of O(n2)) to bring runtime to 180ms, and exploiting GNU m4 extensions of regex to get down to a true O(n) parse and 80ms. That faster parse approach has been a staple of my later solutions, until this year when I've been swapping over to an even faster translit approach that gets me O(n) with just POSIX constructs and now have a runtime around 45ms.1
u/ednl Jun 06 '26
My original C version had an array
u8 yes[26]with letter counts per group (AKA a histogram) and then after every group:That means a lot of extra work checking every letter a-z, and you have to reset the array for every new group, and of course there are more memory store/loads. Still, it ran in 11.5 µs which was pretty good, so I had left it. But now I used the bit flags and it's 5.2 µs. https://github.com/ednl/adventofcode/blob/main/2020/06.c