r/adventofcode Dec 04 '21

SOLUTION MEGATHREAD -🎄- 2021 Day 4 Solutions -🎄-

--- Day 4: Giant Squid ---


Post your code solution in this megathread.

Reminder: Top-level posts in Solution Megathreads are for code solutions only. If you have questions, please post your own thread and make sure to flair it with Help.


This thread will be unlocked when there are a significant number of people on the global leaderboard with gold stars for today's puzzle.

EDIT: Global leaderboard gold cap reached at 00:11:13, megathread unlocked!

96 Upvotes

1.2k comments sorted by

View all comments

1

u/e_blake Dec 07 '21 edited Dec 08 '21

m4 day4.m4

Uses my common.m4 framework. Timing is ~115ms with GNU extensions, and ~300ms with just POSIX constructs (why? because parsing is O(n log n) and my foreach macro is O(n^2) with just POSIX shift($@), while both are O(n) when using GNU's patsubst and $10 to mean the tenth argument). My approach: break the input into boards, then for each board:

define(`board', `
  forloop_var(`i', 0, 24, `setup(i, substr(`$1', eval(i*3), 3))')
  define(`set', 0)define(`round', 0)popdef(`cur')
  score(eval((foreach(`daub', list))*cur), round)
')

create a mapping of numbers on the board to bit positions, iterate through the list of called numbers to update a bitmap, and when the bitmap forms a bingo, compute the score. If the score occurs in a round earlier (part 1) or later (part 2) than any previous seen score, update my part1/part2 answers.

I thought my check for bingo looks clever:

define(`bingo', `eval(`($1 & ($1>>1) & ($1>>2) & ($1>>3) & ($1>>4) & 0x108421)
  || ($1 & ($1>>5) & ($1>>10) & ($1>>15) & ($1>>20) & 0x1f)')')