Day 22: Monkey Market

Megathread guidelines

  • Keep top level comments as only solutions, if you want to say something other than a solution put it in a new post. (replies to comments can be whatever)
  • You can send code in code blocks by using three backticks, the code, and then three backticks or use something such as https://topaz.github.io/paste/ if you prefer sending it through a URL

FAQ

  • @[email protected]
    1•6 months ago

    C

    Really proud of this one! Started with with an O(n^atoms in the universe) scan which took 44s even after adding a dedup check.

    But iterating on a trick to encode the deltas for the dedup check, using it to build a mapping table here, a lookup there etc brought it down to a very fast, fairly low memory, linear complexity solution!

    Code 
    #include "common.h"

#define STEPS	2000
#define NCODES	(19*19*19*19)

int
main(int argc, char **argv)
{
	static int8_t prices[STEPS];
	static int8_t by_deltas[NCODES];
	static int sums[NCODES];

	uint64_t p1=0, secret;
	int p2=0, i;

	if (argc > 1)
		DISCARD(freopen(argv[1], "r", stdin));
	
	while (scanf(" %"SCNu64, &secret) == 1) {
		memset(by_deltas, 0, sizeof(by_deltas));

		for (i=0; i<STEPS; i++) {
			secret = (secret ^ secret << 6)  & 0xFFFFFF;
			secret = (secret ^ secret >> 5);
			secret = (secret ^ secret << 11) & 0xFFFFFF;

			prices[i] = secret % 10;
		}

		/*
		 * Build a deltas->price map for the buyer. Deltas are
		 * encoded as an integer for easy indexing. Iterating
		 * backwards ensures the stored price is the _earliest_
		 * occurence of that sequence.
		 */
		for (i=STEPS-1; i>=4; i--)
			by_deltas[
			    (prices[i-3] - prices[i-4] +9) *19*19*19 +
			    (prices[i-2] - prices[i-3] +9) *19*19 +
			    (prices[i-1] - prices[i-2] +9) *19 +
			    (prices[i]   - prices[i-1] +9)
			] = prices[i];

		for (i=0; i<NCODES; i++)
			sums[i] += by_deltas[i];

		p1 += secret;
	}

	for (i=0; i<NCODES; i++)
		p2 = MAX(p2, sums[i]);

	printf("22: %"PRIu64" %d\n", p1, p2);
	return 0;
}

    day22 0m00.04s real

    https://codeberg.org/sjmulder/aoc/src/branch/master/2024/c/day22.c