Охота на лис 100

Игра Охота на лис (логическая игра).

Задача

Найти всех лис.

Общее описание

На поле 10 на 10 случайным образом расположены лисы, количество которых (Count) задаётся в начале игры. Count это число от 1 до 100. Все лисы в разных клетках! Вы задаёте положение, указав координаты клетки (координаты охотника). В ответ ПМК выдаёт количество лис, пеленгуемых из указанной клетки. Это число указывает, сколько лис расположено в одной вертикали, горизонтали и диагоналях с указанной клеткой.

Если координаты клетки совпадают с положением одной из лис, то она считается найденной, и исключается из дальнейшей пеленгации. В этом случае ПМК отображает общее количество оставшихся лис со знаком минус, чтобы не путать с обычным ответом. В регистре Y можно посмотреть исходные координаты.

Игровой процесс

Начало

Убедитесь, что переключатель Р-ГРД-Г расположен в положении ГРД (посередине). Для корректной работы программы это важно!

Если не используете образ из эмулятора, то перед первым запуском необходимо ввести значения в регистры памяти: R8 = 70, R9 = −75, Ra = 10, Rc = 43, Rd = 0.83048126. Для последующих игр это вводить уже не потребуется.

Введите случайное число от 0 до 1. Оно будет использовано для генерации положений лис. Затем В↑, количество лис, В/О, С/П.

ПМК расставит лис случайным образом и по окончании выдаст −Count, как бы сообщая, что осталось Count лис. Если количество лис большое, то это может занять время, потому что ПМК не ставит две лисы в одно поле, а датчик случайных чисел может выдавать одинаковые первые цифры, что заставляет ПМК пробовать другое число и т.д.

Игра

Вы задаёте координаты клетки, из которой хотите провести пеленгацию, числом в виде пары цифр, разделённых десятичной точкой. Обычно целая часть – вертикальная координата, а дробная – горизонтальная. Впрочем, можете считать наоборот, для игры это не важно – поле-то квадратное! После С/П ПМК выдаст результат на экран. Вот возможные результаты:

Окончание

Если вы нашли всех лис, то на экран будет выдано -99999975. , как признак окончания игры. В регистре Y указано количество ходов, которые вы сделали за игру. Соревновательный момент состоит в том, чтобы как можно быстрее обнаружить всех лис. Т. е. за меньшее число ходов. При одинаковом входном значении случайного числа лисы рассаживаются одинаково.

Для начала новой игры повторите действия, указанные в разделе Начало.

Дополнительная информация

Контроль со стороны ПМК

Число 100 в названии отражает максимальное количество лис, которые можно разместить. Если вы укажите больше, то просто не дождётесь расстановки, потому что невозможно разместить более 100 лис на поле 10 x 10. Число 100 указать можно, ПМК заполнит всё поле, хотя не зная этого будет стараться сделать это случайным образом, поэтому долго. Но играть будет уже не так интересно.

Над каждым ходом ПМК долго думает, поэтому если используете эмулятор с ускорением – ускорьте. Для примера, ход в обычном режиме занимает чуть меньше двух минут, если конечно не найдена лиса, в этом случае быстрее. Со включенным ускорением – 8 секунд.

Далее только для тех, кто не только играет…

Программа делится на две части. Первая – расстановка лис на основе случайного числа, ведённого игроком. Вторая – цикл поиска лис.

Распределение регистров

R0, R1, Rb, Re Битовые поля для хранения положения лис. Инициализируются нулём.
R2 Переменная цикла. В первой части, чтобы расставить всех лис, во второй - чтобы проверить все координаты игрового поля. Инициализируется значением, указанным в начале игры.
R3 Хранит число оставшихся лис. Инициализируется значением, указанным в начале игры.
R4 Введённые координаты охотника.
R5 Результат хода (ответ ПМК). Либо количество запеленгованных лис, либо дубль R3 с отрицательным значением.
R6 Количество ходов за игру. Инициализируется нулём.
R7 Номер регистра для битового поля (0,1,11,14).
R8 70. Адрес кода, где происходит приращение счётчика запеленгованных лис.
R9 Константа (−75). 75 – это адрес процедуры проверки лисы по заданным в RX координатам. После первого использования в регистре уже будет -99999975. , как признак окончания игры.
Ra 10. Константа, используемая для вычислений, а также адрес начала цикла расстановки.
Rc 43. Адрес начала цикла по проверке всех координат.
Rd Число 8.3048126^-01. Используется для вычисления 2x. А хвостик – это адрес начала общего цикла программы.

Текст программы

 # |  00 01 02 03 04 05 06 07 08 09
 00 |  К[x] x→П2 x→П3 FLg Cx x→П6 x→П0 x→П1 x→Пb x→Пe
 10 |  <-> 7 × Fπ + К{x} В↑ ВП 2 К[x]
 20 |  КПП9 Кx<0a FВx Кx→П7 − FL2 10 П→x3 /-/ x→П5
 30 |  П→x4 П→x5 С/П x→П4 Кx≥0d П→xa − Кx<0d 0 x→П5
 40 |  Fcos-1 x→П2 КП→x6 КП→x2 П→x2 Fx≥0 30 КПП9 Кx≥0c FВx
 50 |  П→x4 П→x2 П→xa ÷ − Fx≠0 98 FВx К{x} П→x4
 60 |  К{x} − Кx≠08 + Кx≠08 FВx ÷ Fx2 Fcos Кx=0c
 70 |  КП→x5 КБПc ÷ x→П7 F↻ 4 ÷ К[x] FВx К{x}
 80 |  П→xd /-/ x→Пd Fx≥0 72 ÷ F10x К[x] <-> 1
 90 |  + F10x + КП→x7 <-> К⊕ − В/О <-> Кx→П7
 A0 |  FL3 27 П→x6 П→x9 С/П

Алгоритм работы на словах

Для начала общая идея. Как ПМК хранит до 100 разных координат при 15 регистрах? Ответ: координаты лис хранятся в виде битов. ПМК умеет обрабатывать шестнадцатеричные значения в 7 разрядах числа. Каждая шестнадцатеричная цифра это 4 бита. Итого в одном числе (регистре) можно сохранить 7 × 4 = 28 бит. Четырёх регистров хватит на 4 × 28 = 112 бит. Для нас более чем достаточно. Т. е. всё поле представлено битами в диапазоне 0…99.

Поэтому общая структура программы состоит из двух частей.

  1. Расстановка лис.
    1. Ввести параметы игры с проверкой количества лис.
    2. Обнулить счётчик ходов и битовые планы.
    3. Цикл расстановки:
      1. Сгенерировать случайное число в диапазоне 0…99.
      2. Бит с таким номером уже установлен?
        1. Да. На начало цикла без изменения счётчика лис.
        2. Нет. Установить бит и уменьшить счётчик лис. Ещё остались лисы?
          1. Да. На начало цикла.
          2. Нет. Завершение инициализации.
  2. Основной цикл поиска лис.
    1. Вывести результат. Ожидать ввода.
    2. Проверить введённые координаты охотника. Правильные?
      1. Нет. На начало основного цикла.
      2. Да.
        1. Увеличить счётчик ходов.
        2. Обнулить счётчик пеленгуемых лис.
        3. Цикл от 0 до 99: в заданной индексом координате есть лиса?
          1. Нет. На начало цикла 0…99.
          2. Да. Совпадает с координатой охотника?
            1. Нет.
              1. Лиса пеленгуется с координаты охотника?
                1. Да. Увеличить счёчик запеленгованых лис.
              2. На начало цикла 0…99.
            2. Да. Прервать цикл 0…99. Удалить лису с поля. Уменьшить количество оставшихся лис. Есть ещё лисы?
              1. Да. На начало основного цикла.
              2. Нет. Завершить программу с выводом счетчика ходов.
        4. На начало основного цикла.

Теперь детали.

Процедура проверки, только интерфейс

Самая сложная и часто используемая часть – это процедуры проверки установленного бита. Адрес её в регистре R9. Опишем её контракт.

На входе в регистре X целое число в диапазоне 0…99. На выходе сразу несколько значений:

  1. Знак регистра X отражает факт наличия бита (ранее установленной лисы). Меньше нуля – нет. Больше нуля – есть. Само значение роли не играет.
  2. Регистр R7 содержит номер регистра, в котором живёт данный бит. Ссылка на один из регистров R0, R1, Rb, Re.
  3. Регистр X1 – новый битовый план регистра, на который ссылается R7, чтобы изменить значение бита: если он был, то удалит, если не было, то поставит.

Ещё у этой процедуры есть удобное свойство. Если на входе в регистре Y что-то было, то на выходе это что-то там же и останется.

Процедура достаточно сложная, поэтому её рассмотрение перенесём на конец, сейчас же просто задекларировали, как её нужно использовать.

Расстановка лис

Пойдём по порядку, с адреса 00. Напомним ввод игрока: RX – количество лис, RY - случайное число. По адресам 00…03 целая часть числа лис сохраняется, и проверяется, что больше нуля. Затем по адресу 04…09 обнуляются счётчик ходов и битовые поля. С адреса 10 уже идёт сам цикл расстановки.

Цикл расстановки использует генератор случайных чисел, который работает по формуле Ni+1 = {Ni × 7 + π}.

Адрес 10. Напомню, что случайное число сейчас в RY. Поэтому его подтягиваем из RY и передаём на вход генератору случайных чисел. Кстати, оно так и хранится в дальнейшем в регистре Y. Сохраняет его новое значение там команда по адресу 06, заодно обеспечивая валидность последующего возведения во вторую степень.

Адрес 20. Вызов процедуры проверки. Последнее случайное число всё еще в регистре Y. После проверки, если уже была лиса по таким координатам (>0), то возврат на адрес 10 (Ra=10). Если нет, то извлечение из X1 нового битового плана и сохранение его в нужном месте через R7. Затем по адресу 24 используется арифметическая операция, чтобы подтащить уехавшее в стек случайное число обратно в регистр Y. И стандартное завершение цикла по R2 (количеству лис). С адреса 27 уже начинается основной цикл поиска лис.

Основной цикл поиска лис

Вывод, ввод, проверка, подготовка

Начало (до С/П) простое – копирование в R5 счётчика оставшихся лис, только со знаком минус. Потом вывод R4 и R5. Дело в том, что при нормальном ходе в R5 будет число запеленгованных лис, но тогда вывод начинается с адреса 30. А при ошибках или после расстановки – с адреса 27. Конечно R4 у нас не инициализировано, но по условиям после расстановки про регистр RY ничего и не сказано, а в дальнейшем там будут координаты охотника (ввод игрока).

Адрес этого начала, для быстрого возврата, хранится в Rd, хотя это и не очевидно. Дело в том, что числа порядка −01 не меняются при косвенной адресации, и последние две цифры (7,8 разряды) Rd содержат адрес перехода. Тут он вообще-то равен 26, а не 27, как положено. Но в данном случае это не критично для выполнения, т. к. по адресу 26 идёт 10 – это код команды сложения, которая ничего не портит. А 27 в конце не походит для процедуры проверки. Ага, заинтриговал, как же сделана эта процедура, что для неё критично значение в восьмом разряде после запятой. Но это в конце, потерпите.

Адреса 33…37. Сохранение координат в R4 и проверка, что больше или равно нулю и меньше 10. Тут всё просто.

Адреса 38…39. Зануление счётчика запеленгованных лис.

Адреса 40…41. Подготовка цикла с нуля до 99. В регистр R2 заносится число 100. Вот тут нам и пригодилось, что Р-ГРД-Г в положении ГРД, при котором arccos(0) = 100.

Цикл по всему полю от 0 до 99

Начинается с адреса 43 (он же в Rc). Дело в том, что обычные циклы в ПМК идут от 1 до 100, и на это рассчитаны команды FLx. Но нам нужно от 0 до 99. Поэтому мы не пользуемся FLx, а самостоятельно уменьшаем счётчик цикла, причём сразу. Фактически получается цикл от 99 до 0. Если при уменьшении индекс стал отрицательным, то стоп циклу. Именно это выполняется по адресам 43…46.

Адреса 47…48. Вызов процедуры проверки. Если лисы нет в этой ячейке, то на начало цикла.

Адрес 49. Сохранение в стеке значение X1, которое содержит новый битовый план, чтобы при случае удалить лису. Случай, кстати, настанет только по адресу 99.

Адреса 50…56. Проверка на совпадение координат лисы и охотника. При удаче переход на адрес 98. Перед вычитанием координаты поля в битовом представлении 0…99 переводится в координаты игры 0.0…9.9 путём деления на 10.

Для объяснения дальнейших проверок удобнее ввести формулы. Обозначим координаты лисы как F.f (число), а координаты охотника (в R4) как H.h. Если перейти к дробям, то (F + f/10) и (H + h/10) соответственно. Тогда разность (которая сейчас в RX) будет (H + h/10) − (F + f/10).

Адреса 57…62. Находим разность дробных частей, которая получится (f/10 − h/10). Если нулевая, что означает, что лиса на одной горизонтали с охотником, то переходим на адрес 70 (R8=70), где увеличивается счётчик запеленгованных лис.

Адреса 63…64. Проверяем совпадение по вертикали. Для этого мы просто складываем ((H + h/10) − (F + f/10)) + (f/10 − h/10). В результате получим (H − F). Если успех (ноль), то снова на адрес 70.

Адреса 65…69. Проверяем совпадение по диагонали. Для этого делим (H − F) на (f/10 − h/10) из X1. Делитель точно не ноль, это уже проверили. Если клетки расположены на одной диагонали, то разница между вертикальными и горизонтальными координатами должна совпадать. С учётом того, что целая часть в 10 раз больше дробной, разница совпадает, если результат деления равен ровно 10 (или −10). Или квадрат числа равен 100. Это и делается, т. к. при положении ГРД (снова пригодился) cos(100) = 0. Если и тут нет (не ноль), то эта лиса не видна и просто переход на начало цикла (Rc=43).

Адреса 70…71. Увеличение счётчика запеленгованных лис и безусловный переход на начало цикла.

Завершение программы

Адреса 98…A4. Сюда попадаем, если координаты охотника совпали с координатой лисы. Если вспомнить, то по адресу 49 мы сохранили в стеке битовую карту без этой лисы. Сейчас она находится в RY. Поэтому мы её берём и сохраняем через R7. Затем проверяем, что ещё остались лисы через FL3. Если есть, то на начало цикла поиска, если уже всё, то вывод счётчика ходов, вывод специального значения для завершения и остановка. Игра закончена. Кстати, программа к концу забывает сколько исходно было лис. Первое значение в R2 тратится при расстановке. Второе в R3 уже здесь. Впрочем, и случайное число тоже теряется во время работы.

Следует пояснить, почему если не нажать В/О, то произойдёт ЕГГ0Г . Дело в том, что у ПМК две ветви исполнения после адреса A4. Одна короткая пойдёт на A5, который равен 00, затем дойдёт до адреса B1, который равен 06, но потом уйдёт на длинную ветвь и снова вернётся на 00 (B2), но теперь уже с RX=0, который был установлен при первом проходе. А FLg по адресу 03 и вызовет ошибку.

Процедура проверки, реализация

Ну вот и добрались до вкусного. В общих словах то, как процедура выполняет проверку, можно разбить на четыре части.

  1. Сначала исходное число делится на 4. Остаток, а точнее дробные числа 0, 0.25, 0.5, 0.75 преобразуются в номер регистра для хранения битового плана.
  2. Целая часть от деления 0…24 снова делится на 4. Но тут остаток или, если быть точным, снова дробная часть преобразуется в бит. И получаются числа 1, 2, 4, 8.
  3. Новая целая часть 0…6 используется как порядок для отодвигания бита в нужный разряд и складывается с этим битом. Просто 101…7 + бит будет то, что на нужно.
  4. Полученное число для бита, например число 100004, через К⊕ совмещается с исходным битовым планом. А затем из исходного битового плана вычитается полученное значение. Если бита не было, и он появился, то разность будет отрицательной и наоборот.

Часть 1

Как из дробной части деления на 4 получить ссылки на регистры R0, R1, Rb, Re? Тут пригодилось деление этого остатка на число Rd = 0.83048126. Лучше вывести результат в виде таблицы:

X X / Rd Хвостик Регистр
0 0 00 R0
0.25 0.30103027 27 R1
0.5 0.60206054 54 Re
0.75 0.90309081 81 Rb

Детально, почему это можно использовать для косвенной адресации и как получились такие номера регистров можно узнать здесь: Недокументированные возможности.

Тут можно раскрыть, почему нам не подходит Rd = 0.83048127. Дело в том, что в этом случае получаются другие числа и другие регистры. А для нормальной работы программы нужно, чтобы было свободно два регистра из серии автоуменьшения (R0…R3), два из серии автоувеличения (R4…R6), и не более двух из остальных, т. к. они нужны для косвенной адресации (уменьшения длины программы). А в данном случае вообще 0.25 / Rd = 0.30103026. Что соответствует R0, а он же получается и для нуля.

Часть 2

Тут мы остаток преобразуем по-другому. В общем, мы хотим получить N = 2(X mod 4). Для этого используется константа приблизительно равная 4 × Lg2. Тогда 10{X/4}×4×Lg2 и будет нужным значением. Функция 10x неточная, поэтому константа подобрана так, чтобы полученное число было немногим больше, чтобы целая часть была точно 1, 2, 4 или 8.

А значение Rd = 0.83048126 и есть эта константа, только в виде обратной величины: 1 / (4 × Lg2). Чтобы её можно было использовать и для косвенной адресации.

Детальный код всей процедуры

Теперь смотрим код. С адреса 75 по 79. Всё как положено по части 1: делим на 4, целую часть от деления задвигаем пока в стек, начинаем что-то делать с дробной частью. Но далее идёт некий трюк, который я сейчас опишу.

Дело в том, что нам нужно дважды повторить: разделить на 4, выделить целую часть, выделить дробную часть, разделить её на константу. Но для цикла от 1 до 2 уже нет свободных регистров. Тогда делаем так: некую константу, которая нам нужна, мы после извлечения пересохраняем, но со знаком минус. И проверяем, что она положительная. Если это не так, а первый раз это точно не так, повторяем код. При втором проходе она уже будет положительной и завершит цикл.

Что и делается по адресам 80…84. И переход идёт не на начало процедуры, а немного раньше – на адрес 72, где выполняется деление и сохранения полученного значение в R7, чтобы по нему ссылаться на битовый план. Обратите внимание, что тут в R7 число будет отрицательным, а не так, как в таблице части 1, но для косвенной адресации это не важно.

И после того, как мы уберём из стека по адресу 74 ненужное уже значение, мы перейдём на выполнение части 2. Убрать из стека нужно только так, а не через <->, потому что процедура должна сохранить то, что было на входе в регистре Y.

И вот при повторном проходе условие по адресу 83 уже будет выполнено. Поэтому мы выходим из замкнутого круга и выполняем то, что нужно в части 2 по адресам 85…87.

После чего, поменяв местами X и Y, выполняем часть 3 по адресам 89…92.

В оставшихся адресах 93…96 выполняем часть 4.

Тут следует заметить, что такой необычный цикл можно было бы избежать, просто оформив повторяющуюся часть кода в виде отдельной процедуры. В этом случае вместо странных значений в R7 можно было бы, как в части 2, сделать обычные 1, 2, 4, 8. И общая длина программы осталось бы такой же. Так почему так не сделано? Потому что изначально так и было, но ради скорости выполнения переделано по-другому. Благодаря отказу от ПП и одному F10x скорость программы возросла на 20% (!). Потому что процедура проверки вызывается 100 раз, и даже небольшая оптимизация в ней приводит к таким результатам.