Ijin puzzle solver

ijin_puzzle.cpp

#include <iostream>
#include <string>
#include <vector>
#include <set>
#include <deque>
#include <cassert>
#include <tuple>
#include <algorithm>

using namespace std;

const char START_S = '*';
const char END_S = '@';
const char INVALID_S = 'X';

const int SYMBOL_TOTAL = 8;

vector<string> puzzle;

struct Position {
	int x, y;
	bool isInvalid() const {
		return x < 0 || y < 0;
	}

	bool operator<(const Position &rhs) const {
		if ( x == rhs.x ) {
			return y < rhs.y;
		}
		return x < rhs.x;
	}

	bool operator==(const Position &rhs) const {
		return x == rhs.x && y == rhs.y;
	}
};

ostream& operator<<(ostream &oss, const Position &rhs) {
	oss << '(' << rhs.x << ',' << rhs.y << ')';
	return oss;
}

bool positionAccessible(const Position &p) {
	if (p.y < 0 || p.y >= puzzle.size())
		return false;
	if (p.x < 0 || p.x >= puzzle[p.y].size())
		return false;
	return true;
}

struct State {
	vector<Position> trail;
	set<char> visitedSymbols;

	bool visited(const Position &p) const {
		return find(trail.begin(), trail.end(), p) != trail.end();
	}
};

char getSymbol(const Position &pos) {
		assert(positionAccessible(pos));
		return puzzle[pos.y][pos.x];
}
bool atEnd(const Position &p) {
	return getSymbol(p) == END_S;
}

vector<Position> findStartingPositions(const vector<string> &m) {
	vector<Position> result;
	for (int y = 0; y < m.size(); ++y) {
		for (int x = 0; x < m[y].size(); ++x) {
			if (m[y][x] == START_S) {
				result.push_back(Position{x, y});
			}
		}
	}
	return result;
}

int main() {
	string buffer;

	while(getline(cin, buffer)) {
		puzzle.push_back(buffer);
	}

	cout << "parsed map:\n";
	for ( const auto &row : puzzle ) {
		cout << row << '\n';
	}
	cout << "===END===\n";

	deque<State> q;
	{
		const auto &startingPositions = findStartingPositions(puzzle);
		if (startingPositions.empty()) {
			cout << "No starting position (" << START_S << ") found\n";
			return 1;
		}
		for ( const auto &p : startingPositions) {
			State startState;
			startState.trail.push_back(p);
			cout << "starting position: " << p << endl;
			q.push_back(startState);
		}
	}

	while (!q.empty()) {
		const auto s = q.front();
		q.pop_front();

		if ( atEnd(s.trail.back()) && s.visitedSymbols.size() >= SYMBOL_TOTAL + 1 ) {
			//cout << "landed at end tile. visited symbols: ";
			// for ( const auto c : s.visitedSymbols ) {
			// 	cout << c;
			// }
			//cout << '\n';
			
			//found solution!
			cout << "Found solution!\n";
			vector<string> solution = puzzle;
			for ( int i = 0; i < s.trail.size(); ++i) {
				const auto &pos = s.trail[i];
				solution[pos.y][pos.x] = '0' + i;
			}
			for ( const auto &row : solution ) {
				cout << row << '\n';
			}
		} else {
			tuple<int, int> dir[] = {
				{1, 0},
				{-1, 0},
				{0, 1},
				{0, -1}
			};

			for ( int i = 0; i < 4; ++i ) {
				Position nextPos = s.trail.back();

				nextPos.x += get<0>(dir[i]);
				nextPos.y += get<1>(dir[i]);

				// cout << "checking " << nextPos << '\n';
				if ( !positionAccessible(nextPos) || s.visited(nextPos) ) {
					 // cout << "\tpos invalid\n";
					continue;
				}

				auto symb = getSymbol(nextPos);
				if ( symb == INVALID_S ) {
					continue;
				}
				if (symb != END_S && s.visitedSymbols.count(symb) != 0) {
					// cout << "\tsymbol already visited: " << symb << '\n';
					continue;
				}
				auto newState = s;
				newState.visitedSymbols.insert(symb);
				newState.trail.push_back(nextPos);
				q.push_back(newState);
			}
		}
	}
	return 0;
}