2048: сколько ходов я сделал?

2048 раньше был довольно популярен. Все играли в нее, и многие люди размещали хорошие скриншоты с их достижениями (я сам среди них). Затем в какой-то момент я начал задаваться вопросом, можно ли сказать, как долго кто-то играл, чтобы добраться до этого балла. Я тестировал и выясняет, что (по крайней мере, на приложении андроида я имею) не более одного хода можно сделать за одну секунду. Таким образом, если вы играете достаточно долго (и достаточно быстро), количество сделанных вами ходов неплохо приближается к количеству секунд, в которые вы играли. Теперь возникает вопрос: возможно ли иметь скриншот игры 2048, чтобы вычислить, сколько ходов было сделано.

Вот пример скриншота (на самом деле все мои усилия по игре до сих пор):

На скриншоте вы можете увидеть макет поля в текущий момент и количество очков, заработанных игроком. Итак: эта информация достаточно, чтобы вычислить, сколько ходов я сделал, и если да, каков алгоритм для этого?

ПРИМЕЧАНИЕ. Я хотел бы напомнить вам, что очки забиваются только тогда, когда две плитки "объединяются", а количество очков - это значение новой плитки (т.е. сумма значений комбинированных фрагментов).

Ответ 1

Короткий ответ - можно вычислить количество ходов, используя только эту информацию. Я объясню алгоритм, чтобы сделать это, и я попытаюсь опубликовать свой ответ пошагово. Каждый шаг будет наблюдением, направленным на то, чтобы помочь вам решить проблему. Я рекомендую читателю попытаться решить проблему самостоятельно после каждого совета.

Наблюдение номер один: после каждого движения появляется ровно одна плитка. Эта плитка - это 4 или 2. Таким образом, нам нужно подсчитать количество плиток, которые появились. По крайней мере, в версии игры, в которую я играл, игра всегда начиналась с 2 плиток с 2 на них, помещенных в случайном порядке.
Мы не заботимся о фактическом расположении поля. Мы только заботимся о числах, которые присутствуют на нем. Это станет более очевидным, если я объясню свой алгоритм.
Увидев значения в ячейках в поле, мы можем вычислить, какой будет счет, если 2 появился после каждого. Вызовите это значение twos_score.
Число четырех, которые появились, равно разнице в twos_score и actual_score, деленной на 4. Это верно, потому что для формирования 4 из двух двух секунд мы бы набрали 4 очков, а если 4 появится сразу, мы получим 0. Вызовите число четырех fours.
Мы можем вычислить количество двоичных чисел, необходимых для формирования всех чисел в поле. После этого нам нужно вычесть 2 * fours из этого значения, так как один 4 заменяет необходимость двух двух. Назовите это twos.

Используя эти наблюдения, мы можем решить эту проблему. Теперь я расскажу подробнее о том, как выполнить отдельные шаги.

Как вычислить счет, если появились только два?

Я докажу, что, чтобы сформировать число 2 ⁿ игрок набрал бы очки 2 ⁿ*(n - 1) (используя индукцию).

Заявления очевидны для 2, поскольку они появляются непосредственно, и поэтому за это не начисляются очки.
Предположим, что при фиксированном k для числа 2 ^k пользователь забьет 2 ^k*(k - 1)
Для k + 1: 2 ^{k + 1} может быть сформировано только объединение двух чисел значения 2 ^k. Таким образом, пользователь забьет 2 ^k*(k - 1) + 2 ^k*(k - 1) + 2 ^k+1 (оценка для двух числа вместе плюс оценка для нового номера).
Это равно: 2 ^{k + 1}*(k - 1) + 2 ^k+1= 2 ^k+1* (k - 1 + 1) = 2 ^k+1* k. Это завершает индукцию.

Для того чтобы вычислить счет, если появились только два, нам нужно перебрать все числа на доске и скопировать счет, который мы получаем для них, используя приведенную выше формулу.

Как вычислить количество двоичных чисел, необходимых для формирования чисел в поле?

Намного легче заметить, что число двое, необходимое для формирования 2 ⁿ составляет 2 ^{n - 1}. Строгое доказательство снова можно сделать с использованием индукции, но я оставлю это читателю.

Код

Я дам код для решения проблемы в c++. Однако я не использую ничего слишком специфичного для языка (appart из vector, который является просто динамически расширяющимся массивом), поэтому его очень легко переносить на многие другие языки.

/**
 * @param a - a vector containing the values currently in the field. 
 *   A value of zero means "empty cell".
 * @param score - the score the player currently has.
 * @return a pair where the first number is the number of twos that appeared
 *    and the second number is the number of fours that appeared.
 */
pair<int,int> solve(const vector<vector<int> >& a, int score) {
  vector<int> counts(20, 0);
  for (int i = 0; i < (int)a.size(); ++i) {
    for (int j = 0; j < (int)a[0].size(); ++j) {
      if (a[i][j] == 0) {
        continue;
      }
      int num;
      for (int l = 1; l < 20; ++l) {
        if (a[i][j] == 1 << l) {
          num = l;
          break;
        }
      }
      counts[num]++;
    }
  }
  // What the score would be if only twos appeared every time
  int twos_score = 0;
  for (int i = 1; i < 20; ++i) {
    twos_score += counts[i] * (1 << i) * (i - 1);
  }

  // For each 4 that appears instead of a two the overall score decreases by 4
  int fours = (twos_score - score) / 4;

  // How many twos are needed for all the numbers on the field(ignoring score)
  int twos = 0;
  for (int i = 1; i < 20; ++i) {
    twos += counts[i] * (1 << (i - 1));
  }
  // Each four replaces two 2-s
  twos -= fours * 2;

  return make_pair(twos, fours);
}

Теперь, чтобы ответить на сколько ходов мы сделали, мы должны добавить два значения пары, возвращенные этой функцией, и вычесть два, потому что сразу появляются две плитки с двумя.