[recovery mode] С LINQом по «Жизни»26.07.2015 23:34

Знаменитая игра Джона Конвея«Жизнь», благодаря своей простоте, занимательности и поучительность, реализовывалась программистами так много раз, что уступает вероятно только пресловутой сортировке «пузырьком».

Приведу, тем не менее, еще один вариант исполнения этой замечательной игры, целиком основанный на технологии LINQ в среде .NET — простой, компактный, без циклов и многомерных массивов.

Сразу оговорюсь, что задача достижения максимальной эффективности не ставилась.

using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;

namespace LinqLife
{
    public struct Cell
    {
        public readonly int X, Y;

        public Cell(int x, int y) { X = x; Y = y; }
    }

    public class Life : IEnumerable
    {
        private List _cells = new List();

        private static readonly int[] Liveables = { 2, 3 };

        public bool Next()
        {
            var died = _cells
                .Where(cell => !Liveables.Contains(Count(cell)))    // Условие смерти
                .ToArray();

            var born = _cells
                .SelectMany(Ambit)                                  // Все окружающие ячейки
                .Distinct()                                         // ...без дубликатов
                .Except(_cells)                                     // ...пустые
                .Where(cell => Count(cell) == 3)                    // Условие рождения
                .ToArray();

            if (died.Length == 0 && born.Length == 0)
                return false; // Нет изменений

            _cells = _cells
                .Except(died)
                .Concat(born)
                .ToList();

            return _cells.Any(); // Не все еще умерли?
        }

        private int Count(Cell cell)
        {
            return Ambit(cell)
                .Intersect(_cells)
                .Count();
        }

        private static IEnumerable Ambit(Cell cell)
        {
            return Enumerable.Range(-1, 3)
                .SelectMany(x => Enumerable.Range(-1, 3)
                    .Where(y => x != 0 || y != 0)                                    // Кроме центральной клетки
                    .Select(y => new Cell(cell.X + x, cell.Y + y)));
        }

        public override string ToString()
        {
            if (_cells.Count == 0)
                return string.Empty;

            var xmin = _cells.Min(cell => cell.X);
            var xmax = _cells.Max(cell => cell.X);
            var ymin = _cells.Min(cell => cell.Y);
            var ymax = _cells.Max(cell => cell.Y);

            var matrix = Enumerable.Range(xmin, xmax - xmin + 1)
                .Select(x => Enumerable.Range(ymin, ymax - ymin + 1)
                    .Select(y => _cells.Contains(new Cell(x, y))));

            return string.Join(Environment.NewLine,
                matrix.Select(row =>
                    string.Join("",
                        row.Select(b => b ? "X" : "."))));
        }

        public IEnumerator GetEnumerator()
        {
            return _cells.GetEnumerator();
        }

        IEnumerator IEnumerable.GetEnumerator()
        {
            return GetEnumerator();
        }

        public void Add(int x, int y)
        {
            _cells.Add(new Cell(x, y));
        }
    }

    class Program
    {
        static void Main(string[] args)
        {
            var life = new Life { { 1, 1 }, { 2, 2 }, { 3, 3 }, { 1, 2 }, { 1, 3 } };
            
            var i = 0;
            do
            {
                Console.WriteLine("#{0}\r\n{1}", i++, life);

                Console.ReadLine();

            } while (life.Next());

            Console.WriteLine(life.Any() ? "* Stagnation!" : "* Extinction!");
        }
    }
}

Замечания к коду:

1. Текущее состояние игры — список координат живых клеток, обновляемый на каждом шаге. В других реализациях обычно используется представление игрового поля в виде двумерного массива.
2. Использование операций над множествами: объединение, пересечение, вычитание.
3. Ни единого явного цикла (в классе Life).
4. Использование struct для Cell позволяет не заботиться о сравнении ячеек и обеспечивает эффективное управление памятью (.NET нативно поддерживает ValueType в типизированных коллекциях).
5. Практически неограниченный размер игрового поля. Причем «бесплатно».
6. Возможна простая оптимизация: замена тип _cell с List на HashSet и вызовы Except ()/Concat () в Next () на циклы с Remove ()/Add () даст значительный прирост скорости (правда, в ущерб элегантности кода).
7. Возможна простая многопоточная оптимизация: AsParallel ().
8. Наследование от IEnumerable и метод Add () добавлены исключительно ради изящества инициализации.

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

© Habrahabr.ru