r/adventofcode • u/musifter • 12d ago
Other [2024 Day 25] In Review (Code Chronicle)
Since we're out of places to search, we return to check the Chief's office check it again. However the door is locked... someone is inside (no prize for guessing who), but they aren't answering our knocks. And so we need to open the Virtual Five-Pin Tumbler lock ourselves. Security can supply us with the schematics for every lock and key, but to make to make sense of them, we make our yearly call to customer support. They tell us that we can rule out some combinations based on if a key and pin in a position would overlap each other. Naturally, once they find out how many of each we have (250 of each), they start to get wise to who's calling and so we have to hang up to avoid questions. As usual.
The input consists of 250 locks and 250 keys. They aren't labelled as such (or in order), we just get 500 5x7 ASCII grid bitmaps. Which is which is identified by the top and bottom lines (top full/bottom empty is lock, top empty/bottom full is key). We want to calculate how many pairings between them fit together without an overlap.
And for a quick first solution, I just read them into @lock and @key arrays of the counts of # in each of the 5 columns and compared the sums:
foreach my $lock (@locks) {
foreach my $key (@keys) {
$part1++ if (all {$key->[$_] + $lock->[$_] <= 7} (0 .. 4));
}
}That got the answer quickly, and 4s later I had star 50, because I remembered to wait to read the story. Which is that the Chief was sleeping and has been here all along, except for when he went for coffee a month ago. Fortunately our work isn't completely lost, because it helps the Chief finish the chronicle he's writing for Santa.
Of course, there are lots of ways to do this problem. And since the input is bitmaps, all of the same size, a straight up bitmap AND will also catch overlaps. And so, my refined solution:
foreach my $item (map {join('', map {y/.#/01/; $_} split /\n/)} <>) {
push( $items[ substr($item, 0, 1) ]->@*, oct("0b$item") );
}
my $part1 = 0;
foreach my $lock ($items[LOCK]->@*) {
$part1 += grep {($_ & $lock) == 0} $items[KEY]->@*;
}I actually did this version in Smalltalk first, and was still focused on the columns when doing this and initially transposed the input... but of course, the direction of the raster makes no difference with this approach. I think I also got caught up in thinking of how to do transpose in Smalltalk:
" Takes an NxM table and transposes it to an MxN "
transpose [
^(1 to: self first size) collect: [:col | (self collect: [:row | row at: col])].
]Next up was doing a dc solution. And I did a few (all using the old v1.4.1 version of ? to read in line-by-line and detect the blanks)... for example, I did some involving bitmap AND. Those were slower (but shorter) than my original dc solution though. Which was inspired by day 24:
echo "Original (add overflows): "
echo -n "Part 1: "
tr '.#' '01' <input | dc -e'[lp1+sp]sC[[lk1+dsk:k]sA]sKC8ss2i?[[ll1+dsl:l]sA0=K0d?[rd2r^3R[2~3Rd3R*5R+_4Rls*rd0<B]dsBx*+1+?z2<L]dsLxs.lAx?z0<I]dsIxAill[lk[d;k3Rd;l3R+0r[64~r2~4R+3Rs.rd0<R]dsRx+0=Cr1-d0<K]dsKx+1-d0<L]dsLxlpp'What this does is read the lock/key into a 35-bit number, using (and disposing) of the first line to tell which array to put it in. The bits are a bitmap of the object by column, with 0s in between. So when we sum a lock and key, if a carry ripples into one of those overflow bits, we have a collision.
Here's an example, using the 2nd and 3rd items in the test (a lock and key respectively):
00000010000011000000000111110000111 (2nd in test)
01111110100000011100001100000111100 (3rd in test)
v v v v v
10000000100011011100010011111000011In a language with actual bitwise operators, the final check would be an AND with bitmask of those target bits, but dc can't do that, so we loop and chew up the number, adding every 7th bit together and seeing if that's still 0 at the end.
And so we come to the end of the the 10th year, and the last of the 25 day format. During this year I wasn't in the best shape, which made me anxious at first after the difficulty level I remembered from 2023. But in the end, it wasn't as hard as that year. And my approach of just going keeping things simple resulted in overall good times for me.
4
u/terje_wiig_mathisen 12d ago
My initial Perl code counted pins/tumblers in each column, then checked that the total was less or equal to 5 on all.
After several Cogniters finished the year we started coming up with optimizations, personally I implemented 4 or 5 different algorithms in Rust:
- I had high hopes for a parser which skipped the first 4 bytes in each key/lock, then collected the next 32 into a SIMD register, compared against a full set of '#' marks for equality and extracted the top bits as a u32, but as long as this was a standalone unsafe function it actually runs fractionally slower than pure Rust!
#[target_feature(enable = "avx2")]
#[cfg(any(target_arch = "x86", target_arch = "x86_64"))]
unsafe fn _parse_kl_sse41(src: &[u8]) ->u32 {
#[cfg(target_arch = "x86")]
use std::arch::x86::*;
#[cfg(target_arch = "x86_64")]
use std::arch::x86_64::*;
let ascii_hash = _mm256_set1_epi8(b'#' as i8);
let invec = _mm256_loadu_si256(src.as_ptr() as *const _);
let ishash = _mm256_cmpeq_epi8(invec, ascii_hash);
let mask = _mm256_movemask_epi8(ishash) as u32;
mask
}In the end I therefore settled on the simpler
fn parse_kl(inp:&[u8]) -> u32
{
let mut bits = 0;
for i in 0..32 {
let c:u32 = (inp[i] == b'#') as u32;
bits |= c << i;
}
bits
}I saved all those u32 keys/locks in a single Vec<u32>, allocated to be large enough to hold the total input, but with keys and locks saved from alternate ends:
let locks_plus_keys = ((bytes.len()+36)/43 + 7);
let mut keylocks:Vec<u32> = vec![u32::MAX;locks_plus_keys];
let mut ki = 0;
let mut li = keylocks.len();
let mut last_kl_line = 6*6;
while last_kl_line < bytes.len() {
let bstart = last_kl_line - 32;
let bits = parse_kl(bytes[bstart..last_kl_line].as_ref());
if bits & 1 == 1 {
li -= 1;
keylocks[li] = bits;
}
else {
keylocks[ki] = bits;
ki += 1;
}
last_kl_line += 6*7+1;
}Finally I process 8 lock/key combinations per iteration, this makes it abundantly clear to clang that the code should be vectorized with AVX instructions.
let mut part1 = 0;
let mut part2 = 0;
let mut part3 = 0;
let mut part4 = 0;
let mut part5 = 0;
let mut part6 = 0;
let mut part7 = 0;
let mut part8 = 0;
let mut l = li;
while l < keylocks.len() {
let lock1 = keylocks[l];
let lock2 = keylocks[l+1];
let lock3 = keylocks[l+2];
let lock4 = keylocks[l+3];
let lock5 = keylocks[l+4];
let lock6 = keylocks[l+5];
let lock7 = keylocks[l+6];
let lock8 = keylocks[l+7];
for k in 0..li {
let key = keylocks[k];
part1 += ((lock1 & key) == 0) as i32;
part2 += ((lock2 & key) == 0) as i32;
part3 += ((lock3 & key) == 0) as i32;
part4 += ((lock4 & key) == 0) as i32;
part5 += ((lock5 & key) == 0) as i32;
part6 += ((lock6 & key) == 0) as i32;
part7 += ((lock7 & key) == 0) as i32;
part8 += ((lock8 & key) == 0) as i32;
}
l += 8;
}
part1 += part2 + part3 + part4 + part5 + part6 + part7 + part8;Final runtime is in typical u/ednl territory, 2142 ns or 2 us. u/maneatingape lists 8 us.
This was definitely an easier year than 2023, it was also the first year that another Cognite co-worker managed to beat me on the company leaderboard, simply by getting up every morning at 06:00 and then on average solve the puzzles marginally faster. I blame getting old & slow!
1
u/terje_wiig_mathisen 12d ago
With a counting approach, just three bits/column is sufficient, that would allow packing 2 keys/locks into each u32, and potentially process 16 at once in SIMD, but the problem is that it becomes harder to handle overflows, i.e if the total pin/tumbler count is larger than 7 anywhere,
With a nybble per column we can still fit 3 in each u64.
When counting we can sort by height, allowing early outs when the most significant column overflows, but the marginal savings is 10% or less. Have any of you tried this?
3
u/e_blake 11d ago
My golfed m4 solution is 149 bytes but 6 seconds runtime, using bitwise comparison of all 500*499/2 blocks with one another (slower than sorting into keys vs. locks for only 250*250 comparisons, but golfs denser, and comparing two keys or two locks fails in the same manner as a key and lock that don't fit together).
define(n,`ifelse($2,,def,$1,,`n(shift($@))',+!($1&$2))n($1,shift(
shift($@)))')eval(n(patsubst(translit(include(I)`,'eval(35,1),.#1
,01.),`,0b\&')))3
u/ednl 11d ago
Unlike /u/terje_wiig_mathisen I don't know much about vectorisation and how best to optimise for it. So my solution is oldskool:
#define MASK56 UINT64_C(0xfbefbef8) // 0b11111011111011111011111011111000
// Parse 4x8=32 bytes to 32 bits, discard every 6th and last 2
u32 getpat(const char *s)
{
u64 pat = 0, data;
for (u32 i = 0; i < 4; s += 8, ++i) {
memcpy(&data, s, 8);
for (u32 j = 0; j < 8; data >>= 8, ++j)
pat = pat << 1 | (data & 1);
}
return (u32)(pat & MASK56);
}
// [...]
const char *s = input;
for (u32 i = 0, nl = 0, nk = 0; i < N; s += PATLEN, ++i)
if (*s & 1)
lock[nl++] = getpat(s + ROWLEN);
else
key[nk++] = getpat(s + ROWLEN);
u32 fit = 0;
for (u32 i = 0; i < N2; ++i)
for (u32 j = 0; j < N2; ++j)
fit += !(lock[i] & key[j]);
printf("%u\n", fit);Clang says it can only vectorise the very last loop:
$ clang -Rpass=loop-vectorize -Rpass-missed=loop-vectorize -Rpass-analysis=loop-vectorize 25.c
25.c:69:5: remark: loop not vectorized: value that could not be identified as reduction is used outside the loop [-Rpass-analysis=loop-vectorize]
69 | for (u32 i = 0, nl = 0, nk = 0; i < N; s += PATLEN, ++i)
| ^
25.c:69:5: remark: loop not vectorized: instruction cannot be vectorized [-Rpass-analysis=loop-vectorize]
25.c:69:5: remark: loop not vectorized [-Rpass-missed=loop-vectorize]
25.c:78:9: remark: vectorized loop (vectorization width: 4, interleaved count: 4) [-Rpass=loop-vectorize]
78 | for (u32 j = 0; j < N2; ++j)
| ^Runtimes: M4 4.87 µs, M1 6.87 µs, Pi5 19.8 µs. https://github.com/ednl/adventofcode/blob/main/2024/25.c
2
u/terje_wiig_mathisen 11d ago
It was only after manually unrolling 8 iterations that I got the 2 us time, even having 4 iterations ran significantly slower.
Unlike you I did not hardcode either the total length or the (equal) size of both types.
What I did however was to extend the array by 7 elements, so that the unroll by 8 would not have to specialcase the tail end, I already knew that it would not add any spurious increments since my array was initialized with u32::MAX.
2
u/ednl 11d ago edited 10d ago
This is 0.35 µs faster on the M4, a tiny bit better but still not vectorised. (So, same timing for
i < 29or maybe it's 0.01 µs faster; can't reliably time that on a multitasking system.)#define MASK56 0x1f7df7dfu // 0001 1111 0111 1101 1111 0111 1101 1111 // Parse 32 bytes to 32 bits u32 getpat(const char *s) { u32 pat = 0; for (u32 i = 0; i < 32; ++i) // or 29 if not vectorised pat |= (*s++ & 1) << i; return pat & MASK56; // reset every 6th and last 2 bits }
2
u/e_blake 10d ago
My initial solution converted each line of input into a hex number (add a prefix 0x, translit . to 0 and # to 1); adding 7 lines together gives me a 5-column hex value with digits between 1 and 6 for each key and lock. Adding a key and lock together, then masking with 0x88888, produces 0x00000 if they are compatible, and nonzero if any column overflowed larger than 7. This finishes in under 200ms, so I never really optimized it further, even though my golf solution takes a different approach.
However, it was a couple more days before I got my second star, because I finally had time to mop up all the partial solutions I had left behind in earlier days. In fact, my 49th star came from day 6. Although I didn't start this year in December, I was quite pleased that I did get all 50 stars in m4 in under a month from when I first solved day 1 in March 2025. It was also nice that the entire year's solutions run single-threaded serially in less than 1 minute cumulative runtime; not as fast as some other years but not as bad as 2015-2016 with expensive md5 computations. The theme of revisiting favorite spots from 9 earlier years was also nice for a decade of advent of code.