Простая игра в числа выражается следующими интерфейсами:
public interface User {
int getUpperBound();
boolean theNumberIs(int guess);
}
public interface Game {
int play(User user);
}
Вначале пользователь — User
— задумывает число от 0
до upperBound
; суть
игры — Game.play()
— отгадать задуманное число, спрашивая пользователя
theNumberIs
?, и вернуть угаданное значение. Для проверки написан следующий тест:
public class GameTest {
@Test
public void game() {
final SimpleUser user = new SimpleUser(1_000_000);
final Game game = new GameImpl();
final int answer = game.play(user);
Assert.assertEquals(user.getTheNumber(), answer);
}
}
в котором используется простой эмулятор пользователя:
public class SimpleUser implements User {
private final int theNumber;
private final int upperBound;
public SimpleUser(int upperBound) {
this.upperBound = upperBound;
this.theNumber = (int) (Math.random() * upperBound);
}
public int getTheNumber() {
return theNumber;
}
@Override
public int getUpperBound() {
return upperBound;
}
@Override
public boolean theNumberIs(int guess) {
return (theNumber == guess);
}
}
Напишите реализацию Game
без использования циклов (for
, while
, do..while
)
и инструкции goto
, чтобы эта реализация стабильно проходила заданный GameTest
(Java 7, параметры JVM — по-умолчанию).
Проанализируем задачу. При помощи цикла она решалась бы тривиальным перебором
от 0
до upperBound
, пока число не будет отгадано. Но по условию циклы использовать нельзя,
тогда вспомним, что любой цикл можно развернуть в рекурсию. Однако прямолинейная рекурсия в данном случае
даст переполнение стека (в языке без обязательной оптимизации концевой рекурсии (tail call optimization),
которым является Java). Теперь ключевой момент — догадаться разложить прямую рекурсию в бинарное дерево.
При этом глубина стека растет не линейно, а как логарифм upperBound
, что вполне достаточно для любого
обозримого числа. Остается оптимальным и корректным способом реализовать такую рекурсию
(что совсем не тривиально с учетом всех возможных подводных камней).
В итоге «эталонное» решение выглядит следующим образом (см. DichotomyGame
):
public class DichotomyGame implements Game {
private static final int UNDEFINED = -1;
@Override
public int play(User user) {
return playDichotomy(user, 0, user.getUpperBound());
}
public int playDichotomy(User user, int left, int right) {
assert (left <= right) : "left > right";
if (left == right) {
return user.theNumberIs(left) ? left : UNDEFINED;
} else {
final int middle = (left + right) >>> 1;
final int leftBranchTry = playDichotomy(user, left, middle);
return (leftBranchTry != UNDEFINED) ? leftBranchTry : playDichotomy(user, middle + 1, right);
}
}
}
Было прислано пять вариантов решений, каждое из которых успешно проходило заданный тест. Поэтому, дабы выделить одного победителя, не прибегая к слепому жребию, мы сформулировали дополнительные критерии.
Итак, решение должно (в порядке убывания важности):
- корректно обрабатывать граничный случай
0
; - корректно обрабатывать граничный случай
Integer.MAX_VALUE
; - быть устойчивым к «недобросовестности пользователя», когда он забывает загаданное число;
- «не раздражать» пользователя лишними вопросами, то есть не спрашивать про одно и тоже число несколько раз и не спрашивать после того, как число точно отгадано;
- (желательно) быть повторно используемым (а еще лучше — потокобезопасным).
Эти критерии формализованы в откорректированном GameTest
. «Эталонное» решение удовлетворяет им.
Присланные решения добавлены в проект (GameImpl1...5
), без указания авторства.
По каждому в комментариях дается краткий разбор.
Надо отметить, что каждое решение по-своему интересно и заставляет задуматься.
Но победитель может быть только один, и им становится участник, приславший нам решение GameImpl5
, которое удовлетворяет
всем дополнительным критериям, кроме пятого, наименее важного.
Всем спасибо за участие!
Сергей Кошель, ведущий разработчик CUSTIS.