// SmartPasswords.cpp
// John Buck, Greater NY Region
// For East Division Regional, 2024
// 
// Way overly complicated since this was a solution for a different problem.  Includes debug code
// to show all matches.
//

#include <stdio.h>
#include <stdlib.h>
#include <memory.h>
#include <string.h>
#include <ctype.h>

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

//#define	SHOW_REASON

using namespace std;

/* Keyboard layout */
#define	NUM_KB_ROWS		4
#define	NUM_MOD_KEYS	2

const string szRow1 = "`1234567890-=";
const string szRow1Shift = "~!@#$%^&*()_+";
#define	ROW1_LEFT_POS		6

const string szRow2 = "qwertyuiop[]\\";
const string szRow2Shift = "QWERTYUIOP{}|";
#define	ROW2_LEFT_POS		4

const string szRow3 = "asdfghjkl;'";
const string szRow3Shift = "ASDFGHJKL:\"";
#define	ROW3_LEFT_POS		4

const string szRow4 = "zxcvbnm,./";
const string szRow4Shift = "ZXCVBNM<>?";
#define	ROW4_LEFT_POS		4

struct SKeyboardRow {
	const string m_szChars[NUM_MOD_KEYS];
	int m_nLeftPos;
};

const SKeyboardRow szKeyboard[NUM_KB_ROWS] = {
	{ { szRow1, szRow1Shift}, ROW1_LEFT_POS },
	{ { szRow2, szRow2Shift}, ROW2_LEFT_POS },
	{ { szRow3, szRow3Shift}, ROW3_LEFT_POS },
	{ { szRow4, szRow4Shift}, ROW4_LEFT_POS }
};

#define	MAX_PASS_LENGTH		24
#define	MAX_GUESS_LENGTH	25

/*
 * Penalty's imposed
 */
#define		EPT_NONE	0x01
#define		EPT_LS		0x02
#define		EPT_RS		0x04
#define		EPT_EC		0x08
#define		EPT_MC		0x10
#define		EPT_SL		0x20
#define		NUM_PENALTIES	6
#define		EPT_ALL		0x3f

typedef	unsigned int	EPenaltyType;

const char *gszPenalties[NUM_PENALTIES] = {
	"EX","LS", "RS", "EC", "MC", "CL"
};

/* These are read in */
size_t ulPenalties[NUM_PENALTIES] = { 0 };

#define	ESD_LEFTHAND	0x01
#define	ESD_RIGHTHAND	0x02
typedef unsigned char	EShiftHand;

class SPasswordCandidate {
public:
	SPasswordCandidate(const string &p, EPenaltyType e) {
		m_szPassword = p;
		m_ePenalty = e;
	}
public:
	bool operator==(const SPasswordCandidate &c) const {
		// Dont care about penalty
		bool bRet = PasswordMatch(c);
#ifdef DEBUG
		if(bRet){
			if(m_ePenalty != c.m_ePenalty){
				fprintf(stderr, "penalty mismatch\n");
			}
		}
#endif
		return(bRet);
	}
	bool PasswordMatch(const SPasswordCandidate &c) const {
		return(m_szPassword.compare(c.m_szPassword) == 0);
	}
	EPenaltyType GetPenalty() {
		return(m_ePenalty);
	}
	const char *toString(EPenaltyType uiExtraChar){
		int n;
#ifdef _DEBUG
		n = ::snprintf(&(m_szStrBuf[0]), sizeof(m_szStrBuf), "%s: ", m_szPassword.c_str());
#else
		n = 0;
#endif
		EPenaltyType et = m_ePenalty | uiExtraChar;
		// Only show exact if it's the only one
		if((et & EPT_ALL) != EPT_NONE){
			et &= ~(EPT_NONE);
		}
		for(int i = 0; i < NUM_PENALTIES; i++){
			if(et & (1<<i)){
				n += ::snprintf(&(m_szStrBuf[n]), sizeof(m_szStrBuf)-n-1, " %s", gszPenalties[i]);
			}
		}
		return(&(m_szStrBuf[0]));
	}

private:
	char m_szStrBuf[256];
	string m_szPassword;
	EPenaltyType m_ePenalty;
};

vector<SPasswordCandidate> vPasswords;
vector<SPasswordCandidate> vPasswordMC;
vector<SPasswordCandidate> vGuess;

string Shift(string &szPassword, EShiftHand eshift)
{
	string szNew;
	int i, j;
	size_t idx;

	for(char &c : szPassword){
		for(i = 0; i < NUM_KB_ROWS; i++){
			for(j = 0; j < NUM_MOD_KEYS; j++){
				idx = szKeyboard[i].m_szChars[j].find(c);
				if(idx != string::npos){
					// Found it, check if it's on the left side of the keyboard
					if(idx <= szKeyboard[i].m_nLeftPos){
						if(eshift & ESD_LEFTHAND){
							szNew += szKeyboard[i].m_szChars[j].at(idx + 1);
						} else {
							szNew += c;
						}
					} else if(eshift & ESD_RIGHTHAND){
						szNew += szKeyboard[i].m_szChars[j].at(idx - 1);
					} else {
						szNew += c;
					}
					goto found;
				}
			}
		}
		// char not found
		fprintf(stderr, "Invalid character %c found in password %s\n", c, szPassword.c_str());
		exit(2);
	found:;
	}
#ifdef _DEBUG
	fprintf(stderr, "%hs: Original: \"%s\"  New: \"%s\"  Hand: 0x%02x\n", __FUNCTION__, szPassword.c_str(), szNew.c_str(), eshift);
#endif
	return(szNew);
}

string ShiftLock(const string &szPassword)
{
	string szNew;

	for(const char &c : szPassword){
		if(isupper(c)){
			szNew += tolower(c);
		} else if(islower(c)){
			szNew += toupper(c);
		} else {
			szNew += c;
		}
	}
	return(szNew);
}

void AddPassword(vector<SPasswordCandidate> &vec, const string &szPassword, EPenaltyType ept)
{
	SPasswordCandidate cand(szPassword, ept);
	if(std::find(vec.begin(), vec.end(), cand) != std::end(vec)){
		return;
	}
	vec.push_back(SPasswordCandidate(szPassword, ept));
#ifdef _DEBUG
	fprintf(stderr, "Added password: \"%s\" PenaltyType:%d\n", szPassword.c_str(), ept);
#endif
	SPasswordCandidate candsl(ShiftLock(szPassword), ept | EPT_SL);
	if(std::find(vec.begin(), vec.end(), candsl) != std::end(vec)){
		return;
	}

	/*
	 * Add shift-lock version
	 */
	vec.push_back(candsl);
}

/*
 * Makes up a list of valid passwords to match against
 */
void CreatePasswordList(string &szPassword)
{
	size_t i, n;
	string szTmpPassword;

	// The exact password
	AddPassword(vPasswords, szPassword, EPT_NONE);

	// Left hand shifted right
	AddPassword(vPasswords, Shift(szPassword, ESD_LEFTHAND), EPT_LS);
	// Right hand shifted left
	AddPassword(vPasswords, Shift(szPassword, ESD_RIGHTHAND), EPT_RS);

	// Now add a password for each char being missing
	n = szPassword.length();
	for(i = 0; i < n; i++){
		szTmpPassword = szPassword;
		szTmpPassword.erase(i, 1);
		AddPassword(vPasswordMC, szTmpPassword, EPT_MC);
	}
}

void AddGuess(const string &szGuess, EPenaltyType ept)
{
	SPasswordCandidate cand(szGuess, ept);
	if(std::find(vGuess.begin(), vGuess.end(), cand) != std::end(vGuess)){
		return;
	}
	vGuess.push_back(cand);
#ifdef _DEBUG
	fprintf(stderr, "Added guess: \"%s\" PenaltyType:%d\n", szGuess.c_str(), ept);
#endif
}

/*
 * Check each guess in vGuess against the password list vPass.
 * Return smallest penalty
 */
size_t CheckPassword(vector<SPasswordCandidate> &vPass, vector<SPasswordCandidate> &vGuess, vector<SPasswordCandidate *> &vMatches)
{
	vector<SPasswordCandidate>::iterator iterPass = vPass.begin();
	vector<SPasswordCandidate>::iterator iterGuess;
	bool bMatch = false;

	for(; iterPass < vPass.end(); iterPass++){
		for(iterGuess = vGuess.begin(); iterGuess < vGuess.end(); iterGuess++){
			if(iterPass->PasswordMatch(*iterGuess)){
				vMatches.push_back(&(*iterPass));
				bMatch = true;
			}
		}
	}
	return(bMatch);
}

int main()
{
	string szPassword;
	string szGuess, szTmpGuess;
	size_t i, pl, gl;
	int iProb, nProb;
	vector<SPasswordCandidate *>vMatches;
	bool bMatch;
	EPenaltyType uiExtraCharForGuess;

	getline(cin, szPassword);
	pl = szPassword.length();
	if(pl > MAX_PASS_LENGTH || pl < 2){
		perror("Password too long\n");
		return(1);
	}

	CreatePasswordList(szPassword);

	cin >> nProb;
	getline(cin, szTmpGuess);

	for(iProb = 0; iProb < nProb; iProb++){
		getline(cin, szGuess);
		gl = szGuess.length();
#ifdef _DEBUG
		// Skip comment lines
		if(gl > 0 && szGuess.at(0) == '#'){
			continue;
		}
#endif
		if(gl < pl - 1 || gl > pl + 1){
			fprintf(stderr, "Guess length %tu is bad (password length is %tu)\n", gl, pl);
			exit(2);
		}
		vGuess.clear();
		vMatches.clear();
		uiExtraCharForGuess = 0;
		/*
		 * If guess length is smaller, we use the MC (missing char) password list to compare against
		 */
		if(gl < pl){
			// The exact guess
			AddGuess(szGuess, EPT_NONE);
			bMatch = CheckPassword(vPasswordMC, vGuess, vMatches);
		} else if(gl == pl){
			// The exact guess
			AddGuess(szGuess, EPT_NONE);
			bMatch = CheckPassword(vPasswords, vGuess, vMatches);
		} else {
			// Guess is bigger so make up list of passwords with each char removed
			for(i = 0; i < gl; i++){
				szTmpGuess = szGuess;
				szTmpGuess.erase(i, 1);
				AddGuess(szTmpGuess, EPT_EC);
			}
			bMatch = CheckPassword(vPasswords, vGuess, vMatches);
			uiExtraCharForGuess = EPT_EC;
		}
#ifdef _DEBUG
		if(bMatch == false){
			printf("Guess: \"%s\" NO\n", szGuess.c_str());
		} else {
			vector<SPasswordCandidate *>::iterator iterPass = vMatches.begin();

			printf("Guess: \"%s\" YES\n", szGuess.c_str());
			for(; iterPass < vMatches.end(); iterPass++){
				printf(" %s\n", (*iterPass)->toString(uiExtraCharForGuess));
			}
		}
#else
		if(bMatch == true){
			const char *szReason = "NONE";
			vector<SPasswordCandidate *>::iterator iterPass = vMatches.begin();
			if(iterPass < vMatches.end()){
				szReason = (*iterPass)->toString(uiExtraCharForGuess);
			}
#ifdef SHOW_REASON
			printf("YES%s\n", szReason);
#else
			printf("YES\n");
#endif
		} else {
			printf("NO\n");
		}
#endif
	}
	return(0);
}