Pull to refresh
86.97
ISPsystem
IT infrastructure management platforms

Игра «Жизнь» в одном твите

Level of difficultyEasy
Reading time10 min
Views8.7K
Original author: Michal Koczkodon

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

В одно прекрасное воскресенье, потягивая пиво и размышляя о жизни, я вдруг подумал: а можно ли вместить JavaScript-реализацию игры «Жизнь» в один твит? И не смог устоять перед желанием попробовать свои силы. 

Это не настольная игра

Предположим, вы никогда не слышали об игре «Жизнь» и вдруг решаете зайти в Google и узнать, что это вообще такое. Скорее всего, первым, что попадется вам на глаза, будет вот такая настолка.

Настольная игра The Game of Life, издание 1991 года (источник: amazon.com)
Настольная игра The Game of Life, издание 1991 года (источник: amazon.com)

С большой долей вероятности она покажется вам довольно сложной, и вы подумаете — с какой стати я вообще пытаюсь втиснуть всю логику этой игры в 280 символов кода? Так вот. Это не та игра «Жизнь», что вы ищете. 

Игра «Жизнь» Джона Конвея (Game Of Life) — вот как раз о ней пойдёт речь в этой статье. Всё действие происходит на двумерном поле с клетками. Каждая клетка может быть либо мертвой, либо живой. Состояние клетки может измениться после каждого раунда в зависимости от состояния ее соседей (клеток, расположенных рядом по горизонтали, вертикали или диагонали):

  • живая клетка останется живой в следующем раунде, если у нее есть два или три живых соседа, в противном случае она умирает;

  • мертвая клетка становится живой в следующем раунде, если у нее есть ровно три живых соседа, в противном случае она остается мертвой.

Вот как это выглядит
Вот как это выглядит

Вот, собственно, и все. Для тех, кто хочет узнать про игру больше, есть статья в Википедии.

Отправная точка

Что я, собственно, имею в виду, когда говорю о JavaScript-реализации игры «Жизнь»? Конечно, я мог бы просто написать базовую функцию, которая принимает текущее состояние игры, творит некую магию и возвращает стейт для следующего раунда. Она без проблем уместится в одном твите. Но мне захотелось получить нечто более комплексное и самостоятельное. В моем представлении, код должен был генерировать начальное (случайное) состояние игры, запускать игру в бесконечном цикле и выдавать визуальное представление каждого раунда.

Я сел за ноутбук и принялся писать код. Буквально через пару минут у меня получилась работоспособная JavaScript-реализация, которая делала ровно то, что я хотел.

function gameOfLife(sizeX, sizeY) {
    let state = [];

    for (let y = 0; y < sizeY; y++) {
        state.push([])

        for (let x = 0; x < sizeX; x++) {
            const alive = !!(Math.random() < 0.5);
            state[y].push(alive)
        }
    }

    setInterval(() => {
        console.clear()
        
        const consoleOutput = state.map(row => {
            return row.map(cell => cell ? 'X' : ' ').join('')
        }).join('\n')

        console.log(consoleOutput)

        const newState = []

        for (let y = 0; y < sizeY; y++) {
            newState.push([])

            for (let x = 0; x < sizeX; x++) {
                let aliveNeighbours = 0

                for (let ny = y - 1; ny <= y + 1; ny++) {
                    if (state[ny]) {
                        for (let nx = x - 1; nx <= x + 1; nx++) {
                            if (!(nx === x && ny === y) && state[ny][nx]) {
                                aliveNeighbours++
                            }
                        }
                    }
                }

                if (state[y][x] && (aliveNeighbours < 2 || aliveNeighbours > 3)) {
                    newState[y].push(false)
                } else if (!state[y][x] && aliveNeighbours === 3) {
                    newState[y].push(true)
                } else {
                    newState[y].push(state[y][x])
                }
            }
        }

        state = newState
    }, 1000)
}

gameOfLife(20, 20)

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

Код запускается в Node.js и делает то, что ему говорят
Код запускается в Node.js и делает то, что ему говорят

Итак, давайте я вкратце объясню, что здесь вообще происходит. Я создал функцию gameOfLife, которая принимает два аргумента: sizeX и sizeY. Они используются для создания двумерного массива state, который заполняется случайными булевыми значениями (это делается во вложенных циклах for. True означает, что клетка жива, false — что мертва).

Затем с помощью setInterval каждую секунду выполняется анонимная функция. Она очищает текущий вывод консоли и формирует новый вывод, опираясь на данные о текущем состоянии. В этом выводе символом X обозначаются живые клетки, а символом пробела — мертвые.

Далее с помощью еще одного набора вложенных циклов for создается новое состояние (newState). Для каждой клетки (представленной в виде координат x, y) функция проверяет всех возможных соседей (от x-1 до x+1 и от y-1 до y+1) и подсчитывает количество живых (aliveNeighbours). Для страховки из цикла исключается текущая ячейка, а также несуществующие соседи (например, x=-1, y=-1). На основании информации о количестве живых соседей устанавливается новое состояние ячейки. Итоговое состояние перезаписывает newState.

Наконец, вызывается функция gameOfLife с параметрами 20 строк на 20 столбцов. Вот и все.

Цель

На всякий случай поясню. Под твитом я подразумеваю пост в Twitter (социальной сети с птичкой), размер которого ограничен 280 символами.

В него мне и нужно уместить свой код. Конечно, отступы и длинные имена переменных никак не облегчают задачу, поэтому я оставлю их в исходном коде для лучшей читабельности, а затем воспользуюсь uglify-js для удаления лишних пробелов/строк и сокращения имен переменных (с именами длиной в один символ решить поставленную задачу будет легче).

После прогона через uglifier я получил исходный код длиной 549 символов. Чтобы впихнуть его в один твит, мне придется сократить его почти вдвое.

function gameOfLife(t,f){let s=[];for(let o=0;o<f;o++){s.push([]);for(let e=0;e<t;e++){const l=!!(Math.random()<.5);s[o].push(l)}}setInterval(()=>{console.clear();const e=s.map(e=>{return e.map(e=>e?"X":" ").join("")}).join("\n");console.log(e);const o=[];for(let l=0;l<f;l++){o.push([]);for(let f=0;f<t;f++){let t=0;for(let o=l-1;o<=l+1;o++){if(s[o]){for(let e=f-1;e<=f+1;e++){if(!(e===f&&o===l)&&s[o][e]){t++}}}}if(s[l][f]&&(t<2||t>3)){o[l].push(false)}else if(!s[l][f]&&t===3){o[l].push(true)}else{o[l].push(s[l][f])}}}s=o},1e3)}gameOfLife(20,20);

Рефакторинг

Итак, требования сформулированы, время терять нельзя, — приступаем к сокращению кода!

Декларации

Прежде всего, совсем не обязательно сначала объявлять именованную функцию, а затем вызывать ее. Я могу преобразовать ее в самовызывающуюся функцию, например ((sizeX, sizeY) => {...})(20, 20) — этого вполне достаточно, и места она займет меньше.

Следующий момент — объявления переменных. В настоящее время я определяю переменные, когда они мне нужны, но это приводит к многократному появлению в коде let и const (слов длиной в целых 5 символов!). Давайте вместо этого один раз воспользуемся старым добрым 'var' и объявим все переменные в начале функции.

((sizeX, sizeY) => {
    var state = [],
    y, x, consoleOutput, ny, nx, aliveNeighbours, newState;
    ...
})(20, 20)

А теперь пусть uglify-js сделает свою работу, и... мы получим 499 символов! Это все еще далеко от лимита Twitter, но вполне подходит для Mastodon (другой социальной медиаплатформы, конкурента Twitter).

Скриншот поста на Mastodon с кодом игры
Скриншот поста на Mastodon с кодом игры

Сам пост вы можете посмотреть по этой ссылке.

((o,e)=>{var r=[],s,f,n,a,l,p,u;for(s=0;s<e;s++){r.push([]);for(f=0;f<o;f++){const h=!!(Math.random()<.5);r[s].push(h)}}setInterval(()=>{console.clear();n=r.map(o=>{return o.map(o=>o?"X":" ").join("")}).join("\n");console.log(n);u=[];for(s=0;s<e;s++){u.push([]);for(f=0;f<o;f++){p=0;for(a=s-1;a<=s+1;a++){if(r[a]){for(l=f-1;l<=f+1;l++){if(!(l===f&&a===s)&&r[a][l]){p++}}}}if(r[s][f]&&(p<2||p>3)){u[s].push(false)}else if(!r[s][f]&&p===3){u[s].push(true)}else{u[s].push(r[s][f])}}}r=u},1e3)})(20,20);

Причесываем генерацию начального состояния

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

var state = Array.from(Array(sizeY), () => Array.from(Array(sizeX), () => Math.random() < .5 ? 'X' : ' ' ))

Array.from принимает два аргумента. Первый является обязательным и представляет собой итерируемый объект, который будет преобразован в массив. Второй, необязательный, представляет собой callback. Значение, возвращаемое callback, помещается в выходной массив. Array(n) возвращает массив длины n, заполненный пустыми значениями, но callback может их переопределить.

Поскольку и Array.from, и Array используются дважды, я могу сэкономить место с помощью переменных.

var array = Array,
arrayFrom = array.from,
state = arrayFrom(array(sizeY), () => arrayFrom(array(sizeX), () => Math.random() < .5 ? 'X' : ' ' )),

Возможно, сейчас этого не видно, но после того, как имена переменных будут изуродованы uglifier’ом, код станет на несколько символов короче.

Вы, наверное, заметили, что я больше не использую булевы значения. Поскольку для консольного вывода мне нужны символы X и пробела, проще использовать их и в состоянии. Благодаря этому код для управления консолью можно сократить:

console.clear()
console.log(state.map(row => row.join('')).join('\n'))

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

...
conzole = console,
...
conzole.clear()
conzole.log(...)

Еще несколько небольших корректировок (из-за использования X и пробела вместо булевых значений), и минифицированный код содержит... 448 символов. Осталось убрать меньше 200.

((r,o)=>{var e=Array,f=e.from,s=console,a=f(e(o),()=>f(e(r),()=>Math.random()<.5?"X":" ")),i,l,n,h,p,m,t;setInterval(()=>{s.clear();s.log(a.map(r=>r.join("")).join("\n"));t=[];for(i=0;i<o;i++){t.push([]);for(l=0;l<r;l++){m=0;for(n=i-1;n<=i+1;n++){if(a[n]){for(h=l-1;h<=l+1;h++){if(!(h===l&&n===i)&&a[n][h]==="X"){m++}}}}p=a[i][l].trim();if(p&&(m<2||m>3)){t[i].push(" ")}else if(!p&&m===3){t[i].push("X")}else{t[i].push(a[i][l])}}}a=t},1e3)})(20,20);

Переход в новое состояние

С самого начала мне не очень нравилась моя реализация newState. Я сторонник использования методов массивов при работе с ними, поэтому решил применить reduce и сократить количество циклов for. Дополнительно я присвоил индикаторы состояния (символы X / пробел) новым переменным. Помимо этого, присвоение нового состояния клеток теперь обрабатывается эффективнее. Последнее улучшение в этой итерации — замена тройного знака равенства (===) на двойной (==) для сравнений.

...
alive = 'X',
dead = ' '
...
setInterval(() => {
  ...
  state = state.map((row, y) => row.reduce((newRow, cell, x) => {
    aliveNeighbours = 0

    for (ny = y - 1; ny <= y + 1; ny++) {
        for (nx = x - 1; nx <= x + 1; nx++) {
            if (!(nx == x && ny == y) && state[ny]?.[nx] == alive) aliveNeighbours++ 
        }
    }

    newRow.push(cell.trim()
        ? [2,3].includes(aliveNeighbours) ? alive : dead
        : aliveNeighbours == 3 ? alive : dead
    )

    return newRow
  }, []))
}, 1000)

После всех этих манипуляций у меня получилось 367 символов (естественно, в минифицированном виде). Неплохой результат, но все равно недостаточно емко для Twitter.

Ценить то, что уже есть

Как я уже говорил, я большой поклонник методов массивов (особенно reduce). Однако здесь я активно использую и map, и reduce, а названия этих методов занимают довольно много места. Выше я уже применил Array.from и поместил его в переменную, а после пары дополнительных минут изучения кода понял, что могу использовать его вместо map и reduce следующим образом:

state = arrayFrom(state, (row, y) => arrayFrom(row, (cell, x) => {
    aliveNeighbours = 0

    for (ny = y - 1; ny <= y + 1; ny++) {
        for (nx = x - 1; nx <= x + 1; nx++) {
            if (!(nx == x && ny == y) && state[ny]?.[nx] == alive) aliveNeighbours++ 
        }
    }

    return cell.trim()
        ? [2,3].includes(aliveNeighbours) ? alive : dead
        : aliveNeighbours == 3 ? alive : dead
    )
}))

К тому же код, определяющий новое состояние каждой клетки, все равно мне не нравился (хотя и работал правильно), поэтому через какое-то время я пришел к такому решению:

return aliveNeighbours == 3
  ? alive
  : aliveNeighbours == 2 ? cell : dead

После минификации я получил код длиной 321 символ.

((r,o)=>{var a=Array,n=a.from,e=console,f="X",l=" ",t=n(a(o),()=>n(a(r),()=>Math.random()<.5?f:l)),i,m,c;setInterval(()=>{e.clear();e.log(t.map(r=>r.join("")).join("\n"));t=n(t,(r,a)=>n(r,(r,o)=>{c=0;for(i=a-1;i<=a+1;i++){for(m=o-1;m<=o+1;m++){if(!(m==o&&i==a)&&t[i]?.[m]==f)c++}}return c===3?f:c===2?r:l}))},1e3)})(20,20);

Погружаемся ещё глубже 

Что ж, вот я дошел до того момента, когда 40 символов стали казаться мне целой книгой. Что еще можно сократить и упростить? Следуя практике переиспользования имеющихся инструментов (Array.from), я могу переписать вот этот фрагмент:

conzole.log(state.map(row => row.join('')).join('\n'))

следующим образом:

conzole.log(arrayFrom(state, (row) => row.join('')).join('\n'))

Конечно, в неминифицированном виде этот код длиннее оригинала. Однако после минификации он сократился до 319 символов, и я сэкономил целых 2 символа — это, мягко говоря, не так уж и много. Осталось еще 38.

Вообще-то не обязательно передавать size как два отдельных аргумента — это может быть один аргумент, используемый как для x, так и для y. И вообще вместо 20 я могу использовать 9, что сократит значение аргумента на один символ. Итак, сколько же мы выиграли? 311 символов минифицированного кода.

Что дальше? Допустим, я могу использовать числа — 0 для обозначения мертвой клетки и 1 для живой. Мы получим всего один символ вместо громоздкого трехсимвольного представления (0 вместо ' ' и 1 вместо 'X'). И поскольку это всего один символ, мне не нужно хранить его в отдельной переменной. 299 символов. Победа близка.

Теперь, используя числа в качестве индикаторов состояния, я могу немного подкорректировать логику, отвечающую за подсчет количества aliveNeightbours:

...
for (ny = y - 1; ny < y + 2; ny++) {
    for (nx = x - 1; nx < x + 2; nx++) {
        if (state[ny]?.[nx] == 1) aliveNeighbours++ 
    }
}

return aliveNeighbours - cell == 3
    ? 1
    : aliveNeighbours - cell == 2 ? cell : 0

Я больше не проверяю, имеет ли потенциальный сосед те же координаты, что и клетка, для которой я считаю живых соседей. Вместо этого я вычитаю значение этой ячейки из итоговой суммы. Дополнительно я заменил nx <= x + 1 на nx < x + 2 (то же самое для y) — результат тот же, но на один символ короче. 286 символов. Осталось всего 6!

Я посмотрел на код, который генерирует uglify-js, и понял, что он сохраняет фигурные скобки для циклов for - for (...){for(...){...}}. Но ведь их можно убрать и написать все одной строкой:

for (ny = y - 1; ny < y + 2; ny++) for (nx = x - 1; nx < x + 2; nx++) state[ny]?.[nx] == 1 && aliveNeighbours++

Прогоним это через uglify-js, и...

Наконец-то

Ровно 280 символов. Ну, технически 281 символ, но uglify-js добавляет точку с запятой в конце, а она мне не очень-то и нужна.

Вот окончательный вариант кода:

((size) => {
  var array = Array,
  arrayFrom = array.from,
  conzole = console,
  state = arrayFrom(array(size), () => arrayFrom(array(size), () => Math.random() < .5 ? 1 : 0 )),
  ny, nx, aliveNeighbours;

  setInterval(() => {
    conzole.clear()
  
    conzole.log(arrayFrom(state, (row) => row.join('')).join('\n'))
  
    state = arrayFrom(state, (row, y) => arrayFrom(row, (cell, x) => {
      aliveNeighbours = 0

      for (ny = y - 1; ny < y + 2; ny++) for (nx = x - 1; nx < x + 2; nx++) state[ny]?.[nx] == 1 && aliveNeighbours++

      return aliveNeighbours - cell == 3
        ? 1
        : aliveNeighbours - cell == 2 ? cell : 0
    }))
  }, 1000)
})(9)
В скрипте всего 280 символов, и он работает!
В скрипте всего 280 символов, и он работает!

Твит

А вот и сам твит
А вот и сам твит

Предвосхищая комментарии — уверен, вы найдете способ «срезать» еще парочку символов. Возможно, у вас получится даже лучше, чем у меня!

Tags:
Hubs:
Total votes 17: ↑16 and ↓1+18
Comments11

Articles

Information

Website
www.ispsystem.com
Registered
Founded
Employees
101–200 employees
Location
Россия