// SmartPasswords.cpp
// John Buck, Greater NY Region
// For East Division Regional, 2024
//

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

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

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_SL		0x08
#define		EPT_MC		0x10
#define		EPT_EC		0x20
#define		NUM_PENALTIES	6

typedef	unsigned int	EPenaltyType;

/* 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);
		if(bRet){
			if(m_ePenalty != c.m_ePenalty){
				fprintf(stderr, "penalty mismatch\n");
			}
		}
		return(bRet);
	}
	bool PasswordMatch(const SPasswordCandidate &c) const {
		return(m_szPassword.compare(c.m_szPassword) == 0);
	}
	EPenaltyType GetPenalty() {
		return(m_ePenalty);
	}
private:
	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);
	// Right & left hand shifted left
	AddPassword(vPasswords, Shift(szPassword, ESD_RIGHTHAND | ESD_LEFTHAND), EPT_RS|EPT_LS);

	// 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);
		// Left hand shift version
		AddPassword(vPasswordMC, Shift(szTmpPassword, ESD_LEFTHAND), EPT_LS | EPT_MC);
		// Right hand shift version
		AddPassword(vPasswordMC, Shift(szTmpPassword, ESD_RIGHTHAND), EPT_RS | EPT_MC);
		// Right & left hand shifted left
		AddPassword(vPasswordMC, Shift(szTmpPassword, ESD_RIGHTHAND | ESD_LEFTHAND), EPT_RS | EPT_LS | 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
}

size_t GetPenalty(EPenaltyType p)
{
	EPenaltyType pi;
	size_t penalty = 0;

	for(pi = 0; pi < NUM_PENALTIES; pi++){
		if(p & (1<<pi)){
			penalty += ulPenalties[pi];
		}
	}
	return(penalty);
}

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

	for(; iterPass < vPass.end(); iterPass++){
		for(iterGuess = vGuess.begin(); iterGuess < vGuess.end(); iterGuess++){
			if(iterPass->PasswordMatch(*iterGuess)){
				pTest = ::GetPenalty(iterPass->GetPenalty()) + ::GetPenalty(iterGuess->GetPenalty());
				if(pTest < penalty){
					penalty = pTest;
				}
			}
		}
	}
	return(penalty);
}

int main()
{
	string szPassword;
	string szGuess, szTmpGuess;
	size_t i, pl, gl;
	size_t penalty = 0;
	size_t maxPenalty = 0;
	int iProb, nProb;

	for(i = 1; i < NUM_PENALTIES; i++){
		cin >> ulPenalties[i];
	}
	cin >> maxPenalty;

	// suck up to end of line
	getline(cin, szTmpGuess);

	getline(cin, szPassword);
	pl = szPassword.length();
	if(pl > MAX_PASS_LENGTH || pl < 2){
		perror("Password too long\n");
		return(1);
	}
#ifdef _DEBUG
	fprintf(stderr, "Penalties: ");
	for(size_t &p : ulPenalties){
		fprintf(stderr, " %tu", p);
	}
	fprintf(stderr, "\nPassword: \"%s\"\n", szPassword.c_str());
#endif

	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;
		}
#else
		// 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();
		/*
		 * 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);
			penalty = CheckPassword(vPasswordMC, vGuess);
		} else if(gl == pl){
			// The exact guess
			AddGuess(szGuess, EPT_NONE);
			penalty = CheckPassword(vPasswords, vGuess);
		} 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);
			}
			penalty = CheckPassword(vPasswords, vGuess);
		}
#ifdef _DEBUG
		if(penalty == (size_t)-1){
			printf("Guess: \"%s\" No match\n", szGuess.c_str());
		} else {
			printf("Guess: \"%s\" %s Penalty:\"%tu\"\n", szGuess.c_str(), penalty <= maxPenalty ? "YES" : "NO", penalty);
		}
#else
		if(penalty == (size_t)-1){
			printf("NO MATCH\n");
		} else {
			printf("%s %tu\n", penalty <= maxPenalty ? "YES" : "NO", penalty);
		}
#endif
	}
}