Задача: игра «Гениальный отгадчик»

В игру «Гениальный отгадчик» играют следующим образом:

У компьютера есть четыре слота, в каждом слоте находится шар красного (R), жёлтого (Y), зелёного (G) или синего (B) цвета. Последовательность RGGB означает, что в слоте 1 — красный шар, в слотах 2 и 3 — зелёный, 4 — синий.

Пользователь должен угадать цвета шаров — например, предположить, что там YRGB. Если вы угадали правильный цвет, вы получаете «хит». Если вы назвали цвет, который присутствует в раскладе, но находится в другом слоте, вы получаете «псевдохит». Слот с «хитом» не может быть назван «псевдохитом». Например, если фактический расклад RGBY, а ваше предположение GGRR, то ответ должен быть: один «хит» и один «псевдохит».

Напишите метод, который возвращает число «хитов» и «псевдохитов».

Решение

Задача довольно лёгкая, но даже в ней можно допустить несколько ошибок. Проверьте свой код, учитывая все граничные случаи.

Давайте создадим массив, который будет хранить информацию о том, сколько раз каждый символ появлялся в переменной solution (решении), исключая случаи, когда слот был «хитом». Затем мы просто просматриваем переменную guess для подсчёта количества псевдохитов.

Приведённый ниже код реализует этот алгоритм:

public class Result {
	public int hits = 0;
	public int pseudoHits = 0;

	public String toString() {
		return "(" + hits + "," + pseudoHits + ")";
	}


public int code(char c) {
	switch (c) {
		case 'B':
			return 0;
		case 'G':
			return 1;
		case 'R':
			return 2;
		case 'Y':
			return 3;
		default:
			return -1;
	}
}

public static int MAX_COLORS = 4;

public Result estimate(String guess, String solution) {
	if (guess.length() != solution.length()) return null;

	Result res = new Result();
	int[] frqueencies = new int[MAX_COLORS];

	/*Вычисляем хиты и строим таблицу частот */
	for (int i = 0; i < guess.length(); i++) {
		if (guess.charAt(1) == solution.charAt(i)) {
			res.hits++;
		} else {
			/*Увеличиваем таблицу частот (что
			* будет использоваться для псевдохитов), если это не хит.
			* если это хит, слот уже будет "занят" */
			int code = code(solution.charAt(i));
			frqueencies[code]++;
		}
	}

	/*вычисляем псевдохиты*/
	for (int i = 0; i < guess.length(); i++) {
		int code = code(guess.charAt(i));
		if (code >= 0 && frqueencies[code] > 0) {
			res.pseudoHits++;
			frqueencies[code]--;
		}
	}
	return res;
    }
}

Обратите внимание, что чем проще алгоритм, тем важнее написать чистый и правильный код. В этом примере мы выделили code(char c) в отдельный метод, а также создали класс Result для хранения результата вместо обычного его вывода на консоль.

Источник: «Карьера программиста. Как устроиться на работу в Google, Microsoft или другую ведущую IT-компанию»