Как это посчитать?

Question

[ffff567]

есть список
[4, 2, 2 0]
1. Надо все нули сместить влево [0,4,2,2]
2. если 2 цифры в списке стоят подряд и они одинаковые то сложить их вместе [0,0,4,4]
В списке все ще есть 2 одинаковые цифры сложить их снова [0,0,0,8]

Пишу игру 2048 в оригнальной версии заметил баг поэтому пишу собственную игру.
Баг заключается в том что.
если 2 цифры в списке стоят подряд и они одинаковые то сложить их вместе
получается [0,0,4,4]. и все ход сделан на поле добавляется еще одна цифра. хотя в списке стоят 2 одинаковые их то же нужно сложить. В оригигнальной версии такого нет а по закону физики они тоже должны объдинится. так что оригинальная версия фигня

Comments

[Wispik]

Это не баг, а правила игры. За один ход цифры складываются один раз. И причём тут законы физики вообще не понятно

[ffff567]

Wispik, Законы физики при чем? Когда поворачиваеш доску закон притяжения одинаковые вещества соединияет

[Сергей delphinpro]

Оригинальная игра имеет фатальный недостаток =))

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

Answer 1

[Сергей Соколов]

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

+ сделать предохранитель от бесконечных повторов. Мало ли..

Answer 2

[Wataru]

Проще всего двигать элементы по одному, справа-налево. Элемент можно сдвинуть, если справа стоит 0 или такой же элемент. Поддерживаем инвариант, что все элементы правее current уже сдвинуты и уплотнены до предела. Двигаем текущий пока можем. Чтобы не было циклов не двигаем нули.

int n = a.size();
int current = n-1;
while (current >= 0) {
    while (a[current] > 0 && current < n-1 && 
          ((a[current+1] == a[current]) || (a[current+1] == 0))) {
      a[current+1] += a[current];
      a[current] = 0;
      ++current;
    }
    --current;
}

Comments

[ffff567]

ниче не понял почему нули нельзя трогать? и зачем сдвигать остальные числа?

[Wataru]

ffff567,

ниче не понял почему нули нельзя трогать?

Что значит, "двигать ноль"? Там же нет ничего. Но просто в этом алгоритме мы считаем, что можно значение сдвинуть, если дальше пустота (0) или такое же значение. Но для двух 0 подряд это условие выполняется. Однако двигать-то нечего, после выполнения сложения, у вас остается такой же массив в двумя нулями подряд.

Мы двигаем все числа по одному, справа-налево, пока можем. Если не можем текущее число двигать, переходим к более левому.

[ffff567]

Wataru, а зачем мне их в лево двигать? Я же сказал нули разместить влево а все остальные вправо