Пользователь будет прятаться, а компьютер попытается их найти.
Во-первых, программа примет вход для размера сетки. Как 5x5, 10x10, 15x15 и т. Д. Сетка не всегда будет идеальным квадратом.
Сетка вроде шахматной доски:
_______________________________
| | | | | |
| A1 | | | | | A
|_____|_____|_____|_____|_____|
| | | | | |
| | B2 | | | | B
|_____|_____|_____|_____|_____|
| | | | | |
| | | C3 | | | C
|_____|_____|_____|_____|_____|
| | | | | |
| | | | D4 | | D
|_____|_____|_____|_____|_____|
| | | | | |
| | | | | E5 | E
|_____|_____|_____|_____|_____|
1 2 3 4 5
Теперь пользователь выберет квадрат, например B2
(не сообщая компьютеру)
Компьютер начнет угадывать квадраты. Если он выберет правильный квадрат, пользователь ответит y
. Если нет, они будут вводить направление, в котором их плитка выбрана (N, NE, E, SE, S, SW, W).
Так что, если пользователь выбрал B2
, и компьютер угадал C3
, пользователь будет вводить NW
.
Вот пример выходов и входов:
Grid?
5x5
C3?
NW
C2?
N
B2?
y
Подсчет очков:
Это будет забито немного иначе, чем обычный вызов.
Победителем становится программа, которая принимает наименьшее количество догадок (в среднем), необходимое для угадывания правильного квадрата. Усредненные тестовые случаи будут представлять собой все возможные квадраты в 5x5, а затем в 10x10.
Однако он также должен работать с каждым шаблоном сетки до 26 строк (т. Е. 5x8, 6x2, 20x5 и т. Д.).
Пожалуйста, укажите способ его тестирования, такой как JSFiddle.
И, наконец, в случае ничьей побеждает самая короткая программа.
источник
A1
и компьютер догадываетсяB9
, правильный ответNW
илиW
?Ответы:
Python 3,6 ,
466398392 байта, минимаксВход и выход должны быть в форме, показанной в примере. Это находит квадрат с минимальным «фактором разделения» - который является наибольшей оставшейся областью, которая может быть получена в результате ответа игрока (то есть NW, E, y и т. Д.) - и предполагает это. Да, это всегда центр оставшейся области в этой игре, но этот метод минимизации наихудшего случая будет работать более широко в подобных играх с другими правилами.
Нечитаемая версия:
источник
Mathematica, оптимальное поведение в тестовых случаях, 260 байт
Эта программа может быть протестирована путем вырезания и вставки вышеуказанного кода в Wolfram Cloud . (Протестируйте быстро, хотя: я думаю, что для каждого запуска программы существует ограничение по времени.) Предположения программы выглядят
2 c
вместоC2
, но в остальном она выполняется в соответствии со спецификацией выше. Сетка должна быть введена как упорядоченная пара целых чисел, как{26,100}
, и ответы на догадки программы должны быть введены как строки, как"NE"
или"y"
.Программа отслеживает наименьший и наибольший номер строки и номера столбца, который соответствует входным данным, и всегда угадывает центральную точку подсетки возможностей (округление NW). Программа является детерминированной, поэтому легко вычислить количество угадываний, которое требуется в среднем по фиксированной сетке. В сетке 10x10 программа требует 1 предположение для одного квадрата, 2 догадки для восьми квадратов, 3 догадки для 64 квадратов и 4 догадки для оставшихся 27 квадратов, в среднем 3,17; и это теоретический минимум, учитывая, сколько последовательностей 1-угадывание, 2-угадывание и т. д. может привести к правильным предположениям. Действительно, программа должна достичь теоретического минимума на сетке любого размера по аналогичным причинам. (На сетке 5x5 среднее количество догадок составляет 2,6.)
Небольшое объяснение кода, хотя это довольно просто, кроме игры в гольф. (Я изменил порядок некоторых инициализирующих операторов для пояснительных целей - не влияет на количество байтов.)
Строки 1-3 инициализируют
For
цикл, который на самом деле является простоWhile
замаскированным циклом, так что, эй, на два байта меньше. Возможные диапазоны номеров строк и номеров столбцов в любой момент сохраняются{{a, c}, {f, h}}
, и центрированное предположение в этой подсетке вычисляется функциями,{b, g}
определенными в строке 2. Строка 3 инициализируетc
столбец max-row и max-столбецh
из пользовательского ввода, и также инициализирует,r
которая является проверенной петлей переменной, а также последующие пользовательские вводы.В то время как тест в строке 4 выполнен, строка 5 получает ввод от пользователя, где подсказка приходит из текущего предположения
{b, g}
(Alphabet[][[b]]]
преобразует номер строки в букву). Затем строки 6-8 обновляют подсеть возможностей (и, следовательно, неявно следующее предположение). Например,t["NSu", {{a, b - 1}, {b + 1, c}, {b, b}}]
(учитывая определение вt
строке 1) расширяется догде вы можете видеть, как номера мин и рядов обновляются в соответствии с последним вводом пользователя. Строка 8 преобразует любой возможный ввод в упорядоченную пару символов в форме
{ "N" | "S" | "u", "u" | "W" | "X"}
; здесь"u"
обозначает правильный ряд или столбец и"X"
обозначает восток (просто,Sort
чтобы работать хорошо). Когда пользователь, наконец, вводит данные"y"
, эти строки выдают ошибку, но затем проверка цикла завершается неудачей, и ошибка никогда не распространяется (программа все равно просто останавливается).источник
Пакетно, разделяй и властвуй
Работает, создавая ограничивающую рамку области, которую еще предстоит найти. Следующее предположение - всегда центр коробки. Для тех точек компаса, которые не включены в ответ, поле уменьшается в этом направлении. Например, для ответа
N
слева, справа и снизу поля установлены угаданные квадраты.На 369 байтах я не собираюсь никого побеждать, поэтому оставил пробелы для удобства чтения.
источник