aoc-2019-c

main.c (4257B)

#include "aoc.h"
#include "icc.h"
#include "util.h"
#include "allocator.h"

#include <assert.h>
#include <string.h>
#include <stdlib.h>
#include <stdio.h>
#include <stdint.h>

void
run_amp(struct icc *icc, int phase, int input, int *out)
{
	int in_cnt, out_cnt;

	in_cnt = out_cnt = 0;
	while (icc->state != ICC_HALT) {
		icc_step_inst(icc);
		switch (icc->state) {
		case ICC_INPUT:
			assert(in_cnt <= 1);
			icc->in = (in_cnt == 0) ? phase : input;
			in_cnt++;
			break;
		case ICC_OUTPUT:
			assert(out_cnt == 0);
			*out = icc->out;
			out_cnt++;
			break;
		}
	}
}

void
bf_phase(struct icc *icc, struct dvec *inst, size_t *state,
	size_t max_depth, size_t depth, int in, int *max, size_t *maxstate)
{
	size_t i, k;
	int out;

	if (depth == max_depth) {
		aoc_debug("SETTING %i%i%i%i%i -> %i\n", state[0], state[1],
			state[2], state[3], state[4], in);
		if (*max == 0 || in > *max) {
			*max = in;
			memcpy(maxstate, state, sizeof(int) * max_depth);
		}
		return;
	}

	for (i = 0; i < max_depth; i++) {
		/* dont reuse phase setting */
		for (k = 0; k < depth; k++)
			if (state[k] == i) break;
		if (k != depth) continue;

		state[depth] = i;
		icc_reset(icc, inst);
		aoc_debug("START AMP %i (%i):\n", depth, i);
		run_amp(icc, (int) i, in, &out);
		aoc_debug("END AMP %i (%i): %i -> %i\n", depth, i, in, out);
		bf_phase(icc, inst, state, max_depth,
			depth + 1, out, max, maxstate);
	}
}

int
run_phase_loop(struct icc *iccs, struct dvec *inst, size_t *state, size_t n)
{
	size_t i;
	int passes, done;
	int *ins, out, in_cnt;

	ins = malloc(n * sizeof(int));
	assert(ins != NULL);

	for (i = 0; i < n; i++)
		icc_reset(&iccs[i], inst);

	ins[0] = 0;
	passes = done = 0;
	while (!done) {
		for (i = 0; i < n; i++) {
			in_cnt = 0;
			aoc_debug("START AMP %i (%i):\n", i, state[i]);
			while (iccs[i].state != ICC_HALT) {
				icc_step_inst(&iccs[i]);
				switch (iccs[i].state) {
				case ICC_INPUT:
					iccs[i].in =
						(!passes && !in_cnt
						? (int) state[i] : ins[i]);
					in_cnt++;
					break;
				case ICC_OUTPUT:
					ins[(i+1) % n] = iccs[i].out;
					break;
				}
				if (iccs[i].state == ICC_OUTPUT)
					break;
			}
			if (iccs[i].state == ICC_HALT)
				done = 1;
			aoc_debug("END AMP %i (%i): %i -> %i\n", i,
					state[i], ins[i], ins[(i+1) % n]);
		}
		passes += 1;
	}

	out = ins[0];
	free(ins);

	return out;
}

void
bf_phase_loop(size_t *state, size_t max_depth, size_t depth,
	struct icc *iccs, void *inst, int *max, size_t *maxstate)
{
	size_t i, k;
	int out;

	if (depth == max_depth) {
		out = run_phase_loop(iccs, inst, state, max_depth);
		aoc_debug("SETTING %i%i%i%i%i -> %i\n", state[0], state[1],
			state[2], state[3], state[4], out);
		if (*max == 0 || out > *max) {
			*max = out;
			memcpy(maxstate, state, sizeof(int) * max_depth);
		}
		return;
	}

	for (i = 0; i < max_depth; i++) {
		for (k = 0; k < depth; k++)
			if (state[k] - 5 == i) break;
		if (k != depth) continue;

		state[depth] = i + 5;
		bf_phase_loop(state, max_depth, depth + 1, iccs, inst, max, maxstate);
	}
}

void
part1(void)
{
	struct icc icc;
	struct dvec inst;
	size_t state[5], maxstate[5];
	int max;

	icc_init(&icc);
	icc_parse_inst(&icc, aoc.input, aoc.input_size);

	dvec_init(&inst, sizeof(int), 0, &stdlib_heap_allocator);
	dvec_copy(&inst, &icc.instructions);

	max = 0;
	bf_phase(&icc, &inst, state, 5, 0, 0, &max, maxstate);

	aoc_debug("\nMAX SETTING: %i%i%i%i%i\n", maxstate[0], maxstate[1],
		maxstate[2], maxstate[3], maxstate[4]);

	aoc.answer = aprintf("%i", max);
	aoc.solution = "24625";

	dvec_deinit(&inst);
	icc_deinit(&icc);
}

void
part2(void)
{
	size_t state[5], maxstate[5];
	struct icc iccs[5];
	struct dvec inst;
	int i, max;

	icc_init(&iccs[0]);
	icc_parse_inst(&iccs[0], aoc.input, aoc.input_size);

	dvec_init(&inst, sizeof(int), 0, &stdlib_heap_allocator);
	dvec_copy(&inst, &iccs[0].instructions);

	for (i = 1; i < 5; i++) {
		icc_init(&iccs[i]);
		icc_copy(&iccs[i], &iccs[0]);
	}

	max = 0;
	bf_phase_loop(state, 5, 0, iccs, &inst, &max, maxstate);

	aoc_debug("\nMAX SETTING: %i%i%i%i%i\n", maxstate[0], maxstate[1],
		maxstate[2], maxstate[3], maxstate[4]);

	aoc.answer = aprintf("%i", max);
	aoc.solution = "36497698";

	dvec_deinit(&inst);
	for (i = 0; i < 5; i++)
		icc_deinit(&iccs[i]);
}