Advent of Code 2017 Day 7 Part 2, Dynamic Programming solution

advent2017d7p2.cpp

#include <cstdio>
#include <cstdlib>
#include <vector>

using vec = std::vector<int>;

/* Bare bones implementation of the intcode vm for Day 7 Part 2
 * When run with a phase setting of 5, 6, 7, 8, or 9, returns
 * an array of numbers that represents the effect of each
 * amplification stage (i.e., iteration of the feedback loop):
 *     0: multiply by two
 *     1: add one
 *     2: add two
 * These are the only effects possible with the Part 2 phase settings.
 */
struct cpu {
	vec M = { };
	cpu(FILE *fp) {
		for (int k; fscanf(fp, "%d,", &k) == 1; M.push_back(k));
	}
	auto run(int phase) {
		vec A, M = this->M;
		for (int ip = 0; ; ) switch (M[ip]) {
		    default: printf("unimplemented opcode %d\n", M[ip]); abort();
		    case   99: return A;
		    case  105: ip = M[ip+1] ? M[M[ip+2]] : ip + 3;            break;
		    case  101: M[M[ip+3]] =   M[ip+1]  + M[M[ip+2]]; ip += 4; break;
		    case 1001: M[M[ip+3]] = M[M[ip+1]] +   M[ip+2] ; ip += 4; break;
		    case  102: M[M[ip+3]] =   M[ip+1]  * M[M[ip+2]]; ip += 4; break;
		    case 1002: M[M[ip+3]] = M[M[ip+1]] *   M[ip+2] ; ip += 4; break;
		    case    3: M[M[ip+1]] = phase; phase = 0;        ip += 2; break;
		    case    4: A.push_back(M[M[ip+1]]);              ip += 2; break;
		}
	}
};

int main(int argc, char **argv) {
	if (argc < 2) {
		printf("usage: %s INPUT\n", *argv);
		return 1;
	}

	FILE *fp = fopen(argv[1], "r");
	if (!fp) {
		printf("Error opening file\n");
		return 1;
	}

	cpu C(fp);

	/* Figure out the sequence of operations for each phase setting
	 * by running the program once for each setting.
	 *    Amp[phase][stage]: Amplification effects (*2, +1, +2)
	 *    Weight[stage]:     Product of all x2 in stages _after_ this one
	 *    MulMask[stage]:    Bitmask of which phases multiply in this stage
	 */
	std::vector<vec> Amp;
	vec Weight, MulMask;
	for (int i = 0; i < 5; i++) {
		auto a = C.run(i + 5);
		Amp.push_back(a);

		// Update Weight and MulMask with the new phase setting
		Weight.resize(a.size(), 1);
		MulMask.resize(a.size());
		for (int j = 0; j < a.size(); j++) {
			MulMask[j] |= !a[j] << i;
			if (j && !a[j]) Weight[j-1] *= 2;
		}
	}

	// Make each Weight[] value the product of all later stages
	for (int i = Weight.size() - 1; i >= 1; i--) {
		Weight[i-1] *= Weight[i];
	}

	/* Dynamic programming:
	 * Find the best results attainable for each subset of phases.
	 * Phases NOT in a subset happen EARLIER in the amplification chain.
	 */
	vec best(32);
	for (int m = 1; m < 32; m++) {
		/* For each phase in the subset, try putting that
		 * phase first in the amplification chain.
		 */
		for (int bi = 0, b = 1; bi < 5; bi++, b *= 2) {
			// Skip if this phase is not in the subset
			if (~m & b) continue;

			/* Start with the best value attainable after
			 * removing this phase from the subset
			 */
			int value = best[m ^ b];

			/* Then add the per-stage contributions for this phase,
			 * only counting additive (+1 or +2) stages.
			 * The +1 or +2 is multiplied by:
			 *   - The product of all later-stage multipliers
			 *   - All multipliers in the current subset
			 */
			for (int i = 0; i < Amp[bi].size(); i++) {
				int s = __builtin_popcount(MulMask[i] & m);
				value += Amp[bi][i] * (Weight[i] << s);
			}
			best[m] = std::max(best[m], value);
		}
	}

	int part2 = best.back();
	printf("Part 2: %d\n", part2);

	return 0;
}