Как в игре «Жизнь» определить предыдущее состояние клеток по текущему? (Одномерное поле)?

Question

[Flaker]

Собственно, вопрос следующий: Как по текущему состоянию клеток в игре "Жизнь", определить состояние 1 ход назад?

Правила поведения клеток:
1) Если у клетки 2 живых соседа, то она умирает
2) Если нет живых соседей, то умирает
3) Если есть один живой сосед, то клетка становится живой
4) В иных ситуациях состояние клетки не изменяется

Ход проходит одновременно для всех клеток. То есть состояние всех клеток учитывается по текущему ходу.

Поле, на котором находятся клетки, это одномерный массив.

Допустим текущее состояние: 0 1 1 0, тогда предыдущее будет 1 0 0 1.

Выход за пределы массива, это мертвый сосед.

Подскажите, пожалуйста, алгоритм определения предыдущего состояния поля?

Comments

[lightcaster]

Уточните в вопросе, что вариант игры - одномерный, чтобы не вызывать дикое удивление у тех, кто не читает детали вопроса :).

Answer 1

[Rsa97]

Обозначим текущее состояние как C[1..N], предыдущее как P[1..N], С[0] = P[0] = C[N+1] = P[N+1] = 0 - клетки за пределами поля.
На текущем шаге клетка жива тогда и только тогда, когда на предыдущем шаге у неё был ровно один сосед, то есть C[i] = P[i-1] xor P[i+1] => P[i+1] = C[i] xor P[i-1].
1. P[0] = 0, C[1] известна => P[2] = P[0] xor C[1]. Теперь, зная P[2] можно найти P[4] = P[2] xor C[3] или в общем случае:

для i от 1 до N с шагом 2
    P[i+1] = P[i-1] xor C[i];

Получили все предыдущие значения чётных ячеек.

2a. Для чётных N обратным ходом можно восстановить нечётные ячейки:

для i от N до 1 с шагом -2
    P[i-1] = P[i+1] xor C[i];

2b. Для нечётных N однозначного решения нет. В зависимости от значения P[1] будет получен один из двух вариантов решения:

P[1] = 0; // или 1
для i от 2 до N с шагом 2
    P[i+1] = P[i-1] xor C[i];

Comments

[Opaspap]

скажем было состояние когда 200 клеток стояли на расстоянии более 1 друг от друга, следующий шаг - пустое поле. т.е. никак.

[Flaker]

@Opaspap, клетки рядом стоят.

[Flaker]

@Rsa97, Массивы P и C инициализуются с одинаковыми значениями элементов, получается?

[Rsa97]

@Opaspap Почему? Если у клетки в обе стороны по два пустых соседа, то есть (00100), то на следующем шаге получим: C[1] = 0, C[5] = 0, правило 4; С[2] = 1, C[4] = 1 - правило 3; C[3] = 0, правило 2; то есть (01010).
@Flaker C - из условия задачи, P изначально неопределён, ячейки P[0], С[0], P[N+1] и C[N+1] находятся за пределами поля и всегда равны 0.

[Flaker]

Реализовал в коде на PHP: pastebin.com/QFAfYRFs

Система проверки выдает ошибку на ответ из этих данных:

Выходные данные: 1 1 1 0 0 1 1 1 0 1
Выходные: 0 0 1 1 1 1 0 0 1 0

[Rsa97]

Реализация неверная.

[Flaker]

Понял ошибки, спасибо)

Answer 2

[Rsa97]

Верно так:

// Инициализируем C, надо заменить на ввод исходных данных
$C = array(1, 1, 1, 0, 0, 1, 1, 1, 0, 1);
$N = count($C);

// Добавляем в начало и конец нули
array_unshift($C, 0);
$C[] = 0;

// Создаём массив P, заполняем 0 и N+1 элементы нулями
$P[0] = 0;
$P[$N+1] = 0;

// Заполняем чётные ячейки
for ($i = 1; $i <= $N; $i += 2)
    $P[$i+1] = $P[$i-1] ^ $C[$i];

// Заполняем нечётные ячейки
if (($N&1) == 0) {
    // Вариант с чётным количеством ячеек
    for ($i = $N; $i >= 1; $i -= 2)
        $P[$i-1] = $P[$i+1] ^ $C[$i];
} else {
    // Вариант с нечётным количеством ячеек
    $P[1] = 0;
    for ($i = 1; $i <= $N; $i -= 2)
        $P[$i-1] = $P[$i+1] ^ $C[$i];
}

// Выводим результат
for ($i = 1; $i <= $N; $i++)
    print $P[$i];

Получаем 0110100111.
Проверяем, (0110100111) даёт по правилам (1110011101)

Comments

[Flaker]

Спасибо большое)

Answer 3

[GDApsy]

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

Answer 4

[Пума Тайланд]

никак нельзя определить
можно найти одно из состояний из которого можно перейти в текущее

Answer 5

[Beholder]

Нельзя. Более того, в игре с классическими правилами существуют конфигурации, которые никак нельзя получить ни из каких предыдущих конфигураций (так называемые "сады Эдема").