Solver for the problem posed in Another Roof's video about the game show Countdown

countdown.cpp

#include <array>
#include <bitset>
#include <unordered_map>
#include <iostream>
#include <vector>

// from https://github.com/martinus/unordered_dense
// direct link: https://github.com/martinus/unordered_dense/raw/v3.0.2/include/ankerl/unordered_dense.h
#include "unordered_dense.h"

using VAL = unsigned int;
using SET = std::array<VAL, 6>;
using RES = std::bitset<900>;

struct myhash {
	using is_avalanching = void;
	// required to be able to use unordered_map<array>.
	// this is basically just FNV except operating on integers instead of bytes.
	std::size_t operator()(SET const& s) const noexcept {
		std::size_t res = 0xcbf29ce484222325;
		for(int i=0;i<6;i++) {
			res ^= s[i];
			res *= 0x00000100000001B3;
		}
		return res;
	}
};

struct myeq {
	// not sure if this actually helps but i saw 4-function deep stacktraces during array compares
	bool operator()(SET const& a, SET const& b) const noexcept {
		return !__builtin_memcmp(a.data(),b.data(),6*sizeof(VAL));
	}
};

//using CACHE = std::unordered_map<SET, RES, myhash>;
using CACHE = ankerl::unordered_dense::map<SET, RES, myhash, myeq>;
CACHE caches[2];
CACHE& localcache = caches[0];
CACHE& oldcache = caches[1];

// input format: array of 6 numbers, in nonincreasing order. padded with zeros
// at the end if some numbers are used already. output: a bitset where the
// lowest bit means "100 is reachable", and so on up to 999 (900 bits total)
RES reach_set(SET inp) {
	RES res{};

	// if we only have 2 numbers left, find all possible numbers directly
	if(inp[2] == 0) {
		VAL x = inp[0], y = inp[1];
		for(VAL r : std::array<VAL,4> {x+y,x-y,x*y, (y && (x%y==0)) ? x/y : 0})
			if(r > 99 && r < 1000) res.set(r-100);
		return res;
	}
	
	// if we have seen this exact set of numbers already, return the same answer
	if(localcache.count(inp)) return localcache[inp];
	// if it was seen in the previous iteration, return it and save it to this
	// iteration's cache
	if(oldcache.count(inp)) { return localcache[inp] = oldcache[inp]; }

	// otherwise, find new possible sets of numbers and call reach_set recursively
	for(int i=0;i<6;i++) {
		if(inp[i] == 0) break;
		VAL x = inp[i];
		for(int j=i+1;j<6;j++) {
			if(inp[j] == 0) break;
			VAL y = inp[j];
			for(VAL r : std::array<VAL,4> {x+y,x-y,x*y, (y && (x%y==0)) ? x/y : 0}) {
				// negative numbers aren't possible because x>=y. we can still
				// get 0 from subtraction though
				if(r == 0) continue;
				if(r == x || r == y) continue; // mul or div by 1
				if(r > 99 && r < 1000) res.set(r-100);
				// this is basically a messy way to do the equivalent of
				// remaining = sorted(inp - {x} - {y} + {r})
				// but hopefully it's faster
				SET remaining{};
				int k=0;
				bool r_added = false;
				for(int l=0;l<6;l++) {
					if(inp[l] < r && !r_added) remaining[k++] = r, r_added = true;
					if(l!=i && l!=j) remaining[k++] = inp[l];
				}
				if(!r_added) remaining[k++] = r;
				res |= reach_set(remaining);
			}
			
		}
	}
	return localcache[inp] = res;
};
// wrapper to handle edge cases which only need to be handled for initial conditions
RES reach_set_wrap(VAL a, VAL b, VAL c, VAL d, VAL e, VAL f) {
	RES r = reach_set(SET{a,b,c,d,e,f});
	// the only number that needs to be manually checked like this: all other
	// inputs are less than 100 and thus every other target must be obtained by
	// an operation, so it'll be handled in reach_set's main recursion
	if(a == 100) r.set(0);
	return r;
};

void doset(std::array<VAL, 4> bigs, bool swapcache) {
	if(swapcache) {
		std::swap(localcache, oldcache);
		localcache.clear();
	}

	int tot = 0;
	for(int a=1;a<11;a++) {
		for(int b=a;b<11;b++) {
			size_t res = reach_set_wrap(bigs[0],bigs[1],bigs[2],bigs[3],b,a).count();
			tot += res;
			//printf("%d,%d,%d,%d,%d,%d = %zu\n", bigs[0],bigs[1],bigs[2],bigs[3],b,a, res);
		}
	}
	std::cout << "4L:" << bigs[0] << ',' << bigs[1] << ',' << bigs[2] << ',' << bigs[3] << ": " << tot << '\n';


	tot = 0;
	for(int exc = 0; exc < 4; exc++) {
		std::array<VAL, 3> thisbigs;
		for(int i=0,j=0;i<4;i++) if(i != exc) thisbigs[j++] = bigs[i];
		for(int a=1;a<11;a++) {
			for(int b=a;b<11;b++) {
				for(int c=b;c<11;c++) {
					if(a==b && a==c) continue;
					size_t res = reach_set_wrap(thisbigs[0], thisbigs[1], thisbigs[2], c,b,a).count();
					//printf("%d,%d,%d,%d,%d,%d = %zu\n", thisbigs[0], thisbigs[1], thisbigs[2], c,b,a, res);
					tot += res;
				}
			}
		}
	}
	std::cout << "3L:" << bigs[0] << ',' << bigs[1] << ',' << bigs[2] << ',' << bigs[3] << ": " << tot << '\n';


	tot = 0;
	for(int big1 = 0; big1 < 4; big1++) {
		for(int big2 = big1+1; big2 < 4; big2++) {
			for(int a=1;a<11;a++) {
				for(int b=a;b<11;b++) {
					for(int c=b;c<11;c++) {
						for(int d=c;d<11;d++) {
							// increasing or equal order right now
							// make sure there isn't 3 of any?
							if(a == b && a == c) continue;
							if(b == c && b == d) continue;
							size_t res = reach_set_wrap(bigs[big1], bigs[big2],d,c,b,a).count();
							tot += res;
							//printf("%d,%d,%d,%d,%d,%d = %zu\n", bigs[big1],bigs[big2],d,c,b,a, res);
						}
					}
				}
			}
		}
	}
	std::cout << "2L:" << bigs[0] << ',' << bigs[1] << ',' << bigs[2] << ',' << bigs[3] << ": " << tot << '\n';


	tot = 0;
	for(int big1 = 0; big1 < 4; big1++) {
		for(int a=1;a<11;a++) {
			for(int b=a;b<11;b++) {
				for(int c=b;c<11;c++) {
					for(int d=c;d<11;d++) {
						for(int e=d;e<11;e++) {
							// increasing or equal order right now
							// make sure there isn't 3 of any?
							if(a == b && a == c) continue;
							if(b == c && b == d) continue;
							if(c == d && d == e) continue;
							size_t res = reach_set_wrap(bigs[big1],e,d,c,b,a).count();
							tot += res;
							//printf("%d,%d,%d,%d,%d,%d = %zu\n", bigs[big1],e,d,c,b,a, res);
						}
					}
				}
			}
		}
	}
	std::cout << "1L:" << bigs[0] << ',' << bigs[1] << ',' << bigs[2] << ',' << bigs[3] << ": " << tot << '\n';
}

int main(int argc, char** argv) {
	if(argc != 4) {
		std::cout << "usage: ./a.out [large1] [large2] [large3]\n";
		std::cout << "large1,2,3 must be in descending order\n";
		return 1;
	}
	VAL l1 = std::stoi(argv[1]);
	VAL l2 = std::stoi(argv[2]);
	VAL l3 = std::stoi(argv[3]);
	if(l2 > l1 || l3 > l2 || l1 > 100 || l3 < 11) {
		std::cout << "invalid numbers\n";
		return 1;
	}
	for(int i=l3-1; i>10; i--) {
		std::array<VAL, 4> bigs{l1,l2,l3,(VAL)i};
		doset(bigs, i%2 == 0);
	}
}