soln.cpp

#include <algorithm>
#include <functional>
#include <iostream>
#include <string>
#include <vector>

template <int N>
int plus(int i)
{
	return i + N;
}

template<int N>
int mul(int i)
{
	return i * N;
}

template<int N>
int div(int i)
{
	if (i % N != 0) { return INT32_MAX; }
	return i / N;
}

int shift(int i)
{
	return i / 10;
}

template<int N>
int insert(int i)
{
	return std::stoi(std::to_string(i) + std::to_string(N));
}

template<int F, int R>
int findrep(int i)
{
	const std::string f = std::to_string(F);
	const std::string r = std::to_string(R);

	std::string out = std::to_string(i);

    size_t pos = 0;
    while ((pos = out.find(f, pos)) != std::string::npos) {
         out.replace(pos, f.length(), r);
         pos += r.length();
    }
	return std::stoi(out);
}

int square(int i)
{
	return i * i;
}

int negate(int i)
{
	return -i;
}

int reverse(int i)
{
	std::string out = std::to_string(i);
	std::reverse(out.begin(), out.end());
	return (i < 0 ? -1 : 1) * std::stoi(out);
}

int sum(int i)
{
	int s = 0;
	while (i != 0) {
		s += i % 10;
		i /= 10;
	}
	return s;
}

int cube(int i)
{
	return i * i * i;
}

int rotr(int i)
{
	std::string out = std::to_string(i);
    std::rotate(out.rbegin(), out.rbegin() + 1, out.rend());
	return std::stoi(out);
}

int rotl(int i)
{
	std::string out = std::to_string(i);
    std::rotate(out.begin(), out.begin() + 1, out.end());
	return std::stoi(out);
}

int mirror(int i)
{
	std::string rev = std::to_string(std::abs(i));
	std::reverse(rev.begin(), rev.end());
	return std::stoi(std::to_string(i) + rev);
}

std::vector<int> find(int start, const std::vector<std::function<int(int)>> &funcs, int target)
{
	std::vector<std::vector<int>> to_visit = {{start}};
	while (!to_visit.empty()) {
		std::vector<int> list = to_visit.front();
		if (list.back() == target) {
			return list;
		}
		to_visit.erase(to_visit.begin());
//		for (const auto &e : list) { std::cout << e << ' '; }
//		std::cout << '\n';

		for (const auto &f : funcs) {
			int next;
			try {
				next = f(list.back());
			} catch (const std::out_of_range &) {
				continue;
			}
			if (next >= 10000000) { continue; } // 7 digit display
			if (std::find(list.begin(), list.end(), next) != list.end()) { continue; }
			std::vector<int> v = list;
			v.push_back(next);
			to_visit.push_back(v);
		}
	}
	return {};
}

struct question {
	int start;
	std::vector<std::function<int(int)>> funcs;
	int target;
};

int main()
{
	static const std::vector<question> questions = {
		{0,    {plus<1>}, 2},
		{0,    {plus<2>, plus<3>}, 8},
		{0,    {mul<4>, plus<1>, plus<2>}, 12},
		{1,    {plus<4>, plus<-2>}, 7},
		{3,    {plus<4>, mul<4>, div<4>}, 4},
		{0,    {plus<2>, mul<4>}, 64},
		{4,    {div<3>, plus<3>, mul<3>}, 5},
		{4321, {shift}, 4},
		{0,    {plus<8>, mul<5>, shift}, 4},
		{50,   {div<5>, mul<3>, shift}, 9}, // 10
		{99,   {plus<-8>, mul<11>, shift}, 100},
		{0,    {plus<8>, mul<10>, div<2>}, 404},
		{171,  {mul<2>, plus<-9>, shift}, 23},
		{0,    {plus<5>, mul<3>, mul<5>, shift}, 21},
		{10,   {mul<3>, mul<2>, plus<-5>}, 50},
		{0,    {plus<4>, mul<9>, shift}, 2},
		{0,    {insert<1>}, 11},
		{0,    {insert<1>, insert<0>}, 101},
		{0,    {insert<2>, mul<2>}, 44},
		{0,    {plus<3>, insert<5>}, 35}, // 20
		{0,    {insert<1>, plus<5>}, 56},
		{0,    {plus<2>, div<3>, insert<1>}, 9},
		{15,   {insert<0>, plus<2>, div<5>}, 10},
		{0,    {plus<-5>, plus<5>, insert<2>, insert<5>}, 210},
		{40,   {insert<0>, plus<4>, div<2>}, 2020},
		{0,    {insert<12>, shift}, 11},
		{0,    {insert<10>, plus<1>, shift}, 102},
		{0,    {insert<1>, findrep<1, 2>}, 222},
		{0,    {plus<6>, mul<7>, findrep<6, 9>}, 93},
		{0,    {insert<1>, insert<2>, findrep<1, 2>, findrep<2, 3>}, 2321}, // 30
		{0,    {plus<9>, mul<2>, findrep<8, 4>}, 24},
		{11,   {div<2>, plus<3>, findrep<1, 2>, findrep<2, 9>}, 29},
		{36,   {plus<3>, div<3>, findrep<1, 2>}, 20},
		{2,    {div<3>, insert<1>, findrep<4, 5>, mul<2>}, 15},
		{1234, {findrep<23, 41>, findrep<24, 14>, findrep<12, 24>, findrep<14, 2>}, 414},
		{0,    {plus<6>, insert<5>, plus<-7>}, -85},
		{0,    {plus<-1>, plus<-2>, square}, 9},
		{0,    {mul<5>, plus<-6>, insert<4>}, -120},
		{0,    {plus<-1>, insert<2>, square}, 144},
		{-5,   {negate}, 5}, // 40
		{0,    {plus<4>, plus<2>, negate}, -6},
		{0,    {plus<3>, plus<-7>, negate}, -13},
		{0,    {plus<5>, plus<-10>, negate, mul<4>}, 60},
		{44,   {plus<9>, div<2>, negate, mul<4>}, 52},
		{9,    {plus<5>, mul<5>, negate}, 10},
		{14,   {insert<6>, plus<5>, negate, div<8>}, 12},
		{55,   {plus<9>, negate, shift}, 13},
		{0,    {plus<-3>, insert<5>, negate, mul<4>}, 245},
		{39,   {mul<-3>, div<3>, negate, plus<9>}, 12},
		{111,  {mul<3>, plus<-9>, negate, shift}, 126}, // 50
		{34,   {plus<-5>, plus<8>, negate, div<7>}, 3},
		{25,   {plus<-4>, mul<-4>, negate, div<3>, div<8>}, 4},
		{12,   {reverse}, 21},
		{0,    {plus<6>, plus<9>, reverse}, 51},
		{100,  {insert<1>, plus<9>, reverse}, 101},
		{1101, {plus<-1>, reverse}, 100},
		{0,    {plus<4>, mul<4>, reverse, plus<-3>}, 58},
		{6,    {insert<1>, div<4>, reverse}, 4},
		{15,   {plus<9>, mul<5>, reverse}, 21},
		{100,  {div<2>, reverse}, 13}, // 60
		{10,   {insert<1>, reverse}, 11011},
		{0,    {insert<10>, mul<4>, reverse, plus<5>}, 102},
		{0,    {insert<2>, plus<1>, reverse, div<3>}, 7},
		{0,    {insert<5>, mul<4>, reverse, mul<2>}, 4},
		{121,  {insert<2>, plus<-1>, reverse}, 212},
		{8,    {mul<3>, insert<1>, reverse, div<5>}, 9},
		{0,    {plus<7>, plus<8>, reverse, plus<9>}, 13},
		{0,    {plus<3>, insert<1>, reverse, plus<-2>}, 123},
		{0,    {insert<6>, plus<8>, reverse}, 424},
		{7,    {plus<-9>, mul<3>, negate, plus<4>, reverse}, 81}, // 70
		{0,    {plus<-5>, plus<7>, reverse, plus<-9>}, -43},
		{0,    {plus<6>, plus<-3>, reverse, shift}, 28},
		{0,    {insert<1>, plus<2>, reverse, mul<3>}, 136},
		{0,    {plus<5>, reverse, negate}, -1},
		{0,    {plus<4>, mul<3>, reverse, negate}, -25},
		{0,    {plus<7>, mul<3>, reverse, negate}, -5},
		{88,   {div<4>, plus<-4>, reverse}, 41},
		{100,  {insert<0>, mul<2>, reverse, findrep<2, 10>, findrep<0, 1>}, 101},
		{0,    {div<2>, insert<5>, findrep<5, 4>, reverse}, 424},
		{99,   {insert<9>, div<9>, reverse, findrep<1, 0>}, 100}, // 80
		{8,    {insert<2>, plus<-4>, findrep<2, 3>, reverse}, 30},
		{101,  {plus<-1>, reverse, findrep<0, 2>}, 222},
		{36,   {mul<4>, div<3>, findrep<1, 5>, reverse}, 500},
		{0,    {insert<1>, plus<12>, reverse, mul<13>, shift}, 196},
		{50,   {findrep<1, 10>, plus<50>, reverse, findrep<5, 1>}, 101},
		{1,    {insert<2>, mul<4>, reverse, mul<10>}, 2048},
		{12,   {insert<12>, plus<1>, findrep<12, 2>, reverse}, 123},
		{86,   {plus<2>, plus<14>, reverse, findrep<0, 5>}, 55},
		{0,    {insert<1>, sum}, 3},
		{1231, {sum, findrep<3, 1>, findrep<2, 3>}, 4}, // 90
		{0,    {mul<9>, insert<4>, findrep<3, 5>, mul<3>, sum}, 45},
		{424,  {mul<4>, findrep<4, 6>, sum}, 28},
		{3,    {insert<3>, plus<33>, sum, findrep<3, 1>}, 8},
		{24,   {div<2>, insert<4>, findrep<1, 2>, sum}, 44},
		{142,  {mul<9>, plus<9>, findrep<44, 43>, sum}, 143},
		{24,   {div<3>, mul<4>, findrep<5, 10>, sum}, 1},
		{4,    {insert<3>, mul<3>, sum, plus<1>}, 100},
		{93,   {plus<4>, mul<3>, sum}, 8},
		{5,    {mul<5>, div<2>, sum, findrep<5, 2>}, 16},
		{128,  {mul<4>, div<4>, sum, findrep<5, 16>}, 64}, // 100
		{59,   {insert<1>, mul<5>, findrep<15, 51>, sum}, 121},
		{18,   {mul<2>, div<3>, findrep<12, 21>, sum}, 5},
		{9,    {plus<-5>, mul<-6>, negate, sum}, 30},
		{105,  {plus<-5>, div<5>, negate, mul<4>, sum}, -17},
		{36,   {plus<-6>, div<3>, negate, sum}, 11},
		{3,    {plus<3>, sum, cube, findrep<0, 1>}, 64},
		{2,    {mul<2>, insert<10>, cube, sum, findrep<10, 1>}, 11},
		{1123, {rotl}, 2311},
		{5432, {rotr}, 3254},
		{101,  {plus<2>, rotr, rotl}, 121}, // 110
		{98,   {insert<1>, insert<9>, findrep<89, 99>, rotr}, 1999},
		{70,   {mul<3>, insert<9>, rotr}, 129},
		{120,  {plus<1>, rotl, negate}, 210},
		{1001, {plus<2>, rotr, findrep<12, 0>}, 210},
		{100,  {plus<5>, insert<0>, rotl}, 501},
		{212,  {plus<11>, findrep<3, 1>, sum, rotl}, 3},
		{356,  {plus<-2>, div<3>, rotr}, 121},
		{2152, {findrep<25, 12>, findrep<21, 3>, rotr, findrep<12, 5>, reverse}, 13},
		{1025, {rotr, findrep<50, 0>, findrep<25, 525>, findrep<51, 5>}, 520},
		{23,   {mirror}, 2332}, // 120
		{0,    {insert<1>, insert<2>, mirror}, 1221},
		{91,   {plus<5>, mirror, sum}, 19},
		{22,   {plus<-3>, insert<6>, mirror, sum}, 116},
		{125,  {findrep<6, 2>, insert<0>, mirror, sum}, 20},
		{22,   {sum, div<2>, mirror, shift}, 3},
		{0,    {plus<2>, mul<6>, mirror, findrep<21, 11>}, 1111},
		{-1,   {mul<3>, plus<8>, reverse, plus<2>, mirror}, 2020},
	};
	int i = 1;
	for (const auto &q : questions) {
		std::cout << "Solution " << i << ": ";
		for (const auto &e : find(q.start, q.funcs, q.target)) { std::cout << e << ' '; }
		std::cout << '\n';
		i++;
	}
}

soln118.dot

digraph D {
	node [shape = doublecircle]; 2152 13;
	node [shape = circle];
	2152 -> 352;
	2152 -> 2215;
	2152 -> 2512;
	352 -> 235;
	352 -> 253;
	2215 -> 235;
	2215 -> 5221;
	2215 -> 5122;
	2512 -> 1212;
	2512 -> 255;
	2512 -> 2251;
	235 -> 523;
	235 -> 532;
	253 -> 123;
	5221 -> 523;
	5221 -> 1522;
	5221 -> 1225;
	5122 -> 552;
	5122 -> 2512;
	1212 -> 55;
	1212 -> 2121;
	255 -> 125;
	255 -> 525;
	255 -> 552;
	2251 -> 2121;
	2251 -> 1225;
	2251 -> 1522;
	1522 -> 1522;
	523 -> 325;
	532 -> 253;
	123 -> 53;
	53 -> 35;
	35 -> 35;
	123 -> 312;
	123 -> 321;
	325 -> 312;
	325 -> 532;
	1225 -> 1212;
	1225 -> 525;
	2121 -> 33;
	2121 -> 251; // !!!
	33 -> 33;
	125 -> 55;
	125 -> 112;
	55 -> 55;
	125 -> 521;
	525 -> 512;
	525 -> 552;
	321 -> 33;
	321 -> 132;
	132 -> 213;
	132 -> 231;
	213 -> 33;
	231 -> 231;
	312 -> 35;
	521 -> 53;
	521 -> 152;
	512 -> 55;
	512 -> 215;
	512 -> 251;
	152 -> 152;
	215 -> 35;
	251 -> 121;
	251 -> 125;
	251 -> 152;
	121 -> 13;
	121 -> 51;
	51 -> 15;
	15 -> 15;
	552 -> 552;
	112 -> 15;
	112 -> 211
	211 -> 31;
	211 -> 121;
	31 -> 13;
}
//25=>12,21=>3,12=>5,shift>,rev