Advent of Code 2019 Day 16 Vanity Input Generator

day16vanity.cpp

#include <cstdio>
#include <cstdint>
#include <vector>
#include <array>
#include <random>

using int_t = long long;
using vec = std::vector<int_t>;
using arr8 = std::array<int8_t, 8>;

// Outputs are eight digits long
constexpr int_t MOD = 100000000;

// Extract a number from a list of digits
int_t get_number(const vec &V, int_t offset, int_t len) {
	int_t n = 0;
	for (int_t i = 0; i < len; i++) {
		n = 10 * n + V[offset + i];
	}
	return n;
}

// Split a number into 8 digits
auto split(int_t n) {
	arr8 A;
	for (int i = A.size() - 1; i >= 0; i--) {
		A[i] = n % 10;
		n /= 10;
	}
	return A;
}

// Combine 8 digits into a number
auto combine(const arr8 &A) {
	int_t n = 0;
	for (auto d : A) {
		n = 10 * n + d;
	}
	return n;
}

arr8 operator + (const arr8 &a, const arr8 &b) {
	arr8 sum;
	for (int i = 0; i < a.size(); i++) {
		(sum[i] = a[i] + b[i]) %= 10;
	}
	return sum;
}

arr8 operator - (const arr8 &a, const arr8 &b) {
	arr8 diff;
	for (int i = 0; i < a.size(); i++) {
		(diff[i] = 10 + a[i] - b[i]) %= 10;
	}
	return diff;
}

arr8 operator * (const arr8 &a, int_t n) {
	arr8 prod;
	for (int i = 0; i < a.size(); i++) {
		(prod[i] = a[i] * n) %= 10;
	}
	return prod;
}

// Binomial coefficient mod p using Lucas's theorem
int_t lucas_ncr(int_t n, int_t r, int_t p) {
	static const int_t pascal[5][5] = {
		    {1}, // mod 2, 5...
		   {1,1},
		  {1,2,1}, // mod 5...
		 {1,3,3,1},
		{1,4,1,4,1},
	};

	int_t c = 1;
	while (r) {
		c *= pascal[n % p][r % p];
		n /= p, r /= p;
	}
	return c;
}

// Binomial coefficient mod 10
int_t ncr_mod_10(int_t n, int_t r) {
	// Chinese remainder theorem
	return (5 * lucas_ncr(n, r, 2) + 6 * lucas_ncr(n, r, 5)) % 10;
};

int main(int argc, char **argv) {
	constexpr int_t INPUT_LEN = 649;
	constexpr int_t REPEAT = 10000;

	int_t DESIRED_OUTPUT = 31415926;
	int_t PHASES = 100;

	if (argc >= 2) {
		DESIRED_OUTPUT = atol(argv[1]) % MOD;
		printf("Searching for output %08lld\n", DESIRED_OUTPUT);
	} else {
		printf("Searching for default output %08lld\n", DESIRED_OUTPUT);
	}

	if (argc >= 3) {
		PHASES = atol(argv[2]);
		printf("Using phase count %lld\n", PHASES);
	} else {
		printf("Using default phase count %lld\n", PHASES);
	}

	std::random_device rd;
	std::mt19937 gen(rd());

	// Randomize input, and put the offset in the range 5940000-5949999
	std::vector<int_t> V(INPUT_LEN);
	for (auto &d : V) d = std::uniform_int_distribution<>{0,9}(gen);
	V[0] = 5; V[1] = 9; V[2] = 4;

	int offset = get_number(V, 0, 7);
	int tail = REPEAT * INPUT_LEN - offset;

	/* Compute weights for how each input digit affects each of the
	 * eight output digits.
	 */
	std::vector<arr8> Weight(V.size());
	for (int d = 0; d < 8; d++) {
		int idx = (offset + d) % INPUT_LEN;
		for (int i = 0; i < tail - d; i++) {
			auto s = ncr_mod_10(PHASES + i - 1, i);
			(Weight[idx][d] += s) %= 10;
			if (++idx == INPUT_LEN) idx = 0;
		}
	}

	/* Find the starting value, which is the Part 2 solution
	 * we would get by using the input as-is.
	 */
	arr8 A_start = { };
	for (int idx = 0; idx < INPUT_LEN; idx++) {
		A_start = A_start + Weight[idx] * V[idx];
	}
	int_t start = combine(A_start);

	printf("Initial solution for random string: %lld\n", start);

	/* DP array.  For each 8-digit output value, remembers which
	 * input digit we needed to increment in order to reach it.
	 * By following the chain of values back to the starting
	 * value, we can reconstruct the set of digits later on.
	 */
	std::vector<int16_t> DP(MOD);
	DP[start] = -1;

	/* Try to make the solution match by incrementing each input
	 * digit at most once.  One possible enhancement would be to
	 * consider all ways to modifiy a digit, but it's not really
	 * necessary.
	 */
	int_t reachable = 1;
	for (int idx = 7; idx < INPUT_LEN && !DP[DESIRED_OUTPUT]; idx++) {
		if (V[idx] == 9) {
			// Can't increment this one
			continue;
		}
		for (int r = 0; r < DP.size(); r++) {
			if (!DP[r] || DP[r] == idx) {
				// Not reachable yet using previous digits
				continue;
			}

			auto n = combine(split(r) + Weight[idx]);
			if (!DP[n]) {
				DP[n] = idx;
				reachable++;
			}
		}
		printf("idx=%d (%08lld), reachable=%lld\n",
				idx, combine(Weight[idx]), reachable);
	}

	if (!DP[DESIRED_OUTPUT]) {
		printf("Not found\n");
		return 1;
	}

	// Increment the input digits necessary to solve for DESIRED_OUTPUT
	int num_changes = 0;
	for (int_t n = DESIRED_OUTPUT; n != start; ) {
		int idx = DP[n];
		V[idx]++;
		num_changes++;
		n = combine(split(n) - Weight[idx]);
	}
	printf("Changed %d digits in the random string\n", num_changes);

	printf("Input: ");
	for (auto d : V) printf("%lld", d);
	putchar('\n');

	return 0;
}