Привет ! Меня зовут Ксавье Жувено, и вот восемнадцатая часть длинной серии статей о Пришествии кода. Предыдущую часть можно найти здесь

В этом новом посте мы собираемся решить проблему от 18 декабря 2015 года под названием «Как GIF для вашего двора». Решение я предложу на C++, но рассуждения можно применить и к другим языкам.

Часть 1

Проблема

Полную версию этой проблемы можно найти непосредственно на сайте Пришествие кода, здесь я опишу лишь суть проблемы:

У нас снова есть сетка источников света (100×100), и на этот раз мы хотим сделать на ней красивую анимацию. Но есть некоторые правила, которые позволяют нам перейти к следующему состоянию сетки и создать при этом красивую анимацию:

  • Свет, который включен, остается включенным, когда включены 2 или 3 соседей, и выключается в противном случае.
  • Свет, который выключен, включается, если включены ровно 3 соседей, и остается выключенным в противном случае.

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

Цель состоит в том, чтобы узнать, сколько ламп включено после 100 шагов?

Решение

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

Поскольку это очень известная игра, в Интернете есть множество реализаций, возможно, намного лучше, чем та, которую я вам предложу, но, тем не менее, всегда полезно найти решение самостоятельно, прежде чем проверять другие решения.

Просто прочитав текст задачи, вы можете себе представить, что нам понадобятся некоторые Light, Grid объекты и выяснить их поведение. Итак, давайте посмотрим на решение, которое я вам предлагаю, начиная с Light 😉

using LightState = bool;
class Light {
public:
  Light(LightState initialState);
  ~Light();
  bool isOn() const;
  bool isOff() const;
  void prepareNextState(const std::vector<std::reference_wrapper<Light>> &neighbors);
  void nextState();
private:
  LightState currentState = false;
  LightState willChangeState = false;
};

Итак, вот интерфейс этого класса. Каждый свет будет иметь начальное состояние (в зависимости от начальной конфигурации). Мы можем проверить, включен он или нет. Мы также можем подготовиться к следующему состоянию этого источника света в зависимости от его соседей, чтобы выяснить, изменится ли состояние источника света в следующем состоянии. И, наконец, мы можем действовать в соответствии с решением, принятым во время подготовки.

Методы, дающие состояние источника света, тривиальны, поэтому мы подробно остановимся только на двух других методах:

void Light::prepareNextState(const std::vector<std::reference_wrapper<Light>> &neighbors) {
  const auto numberOfNeighborsOn = std::count_if(
    std::begin(neighbors), std::end(neighbors),
    [](const auto &light) { return light.get().isOn(); });
  if (isOff() && numberOfNeighborsOn == 3) {
    willChangeState = true;
  }
  else if (isOn() && (numberOfNeighborsOn != 2 && numberOfNeighborsOn != 3)) {
    willChangeState = true;
  }
}
void Light::nextState() {
  if (willChangeState) {
    currentState = !currentState;
    willChangeState = false;
  }
}

В процессе подготовки считаем количество включенных соседей по алгоритму std::count_if. Затем мы применяем правила, чтобы определить, когда изменится состояние источника света. Если свет выключен, он будет меняться, только если у него включены три соседа. И если свет горит, то он останется включенным, если у него есть 2 или 3 соседа, но, поскольку мы хотим знать, когда свет изменит свое состояние, мы принимаем отрицание этого условия. 😉

И вот у нас есть хорошо работающий свет. Теперь давайте посмотрим на файл Grid.

class Grid {
public:
  Grid();
  ~Grid();
  size_t numberOfLightsOn() const;
  // Builds the grid
  void emplaceLight(LightState lightState);
  void nextLine();
  // Run the animation
  void nextStep();
private:
std::vector<std::vector<Light>> lights;
};

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

// Grid methods
void Grid::emplaceLight(LightState lightState) {
  lights.back().emplace_back(lightState);
}
void Grid::nextLine() {
  lights.emplace_back();
}
// In the main
foreachLineIn(fileContent, [&lights](const std::string &line) {
  lights.nextLine();
  for (const auto &character : line) {
    lights.emplaceLight(character == '#');
  }
});

Вот как вы создаете свою первоначальную конфигурацию ваших Grid источников света с помощью этого интерфейса: для каждой строки файла конфигурации инициализации каждый включенный свет представлен #, поэтому мы создаем новую строку и добавляем каждый свет с состоянием дается условием character == '#'. Реализация Grid тоже довольно проста, используя метод std::vector.

Теперь давайте посмотрим на реализацию двух других методов:

void Grid::nextStep() {
  // Preparation
  for (size_t i{0}; i < lights.size(); ++i) {
    for (size_t j{0}; j < lights[i].size(); ++j) {
      std::vector<std::reference_wrapper<Light>> neighbors;
      if (i > 0) { neighbors.push_back(lights[i - 1][j]); }
      if (j > 0) { neighbors.push_back(lights[i][j - 1]); }
      if (i < (lights.size() - 1)) { neighbors.push_back(lights[i + 1][j]); }
      if (j < (lights[i].size() - 1)) { neighbors.push_back(lights[i][j + 1]); }
      if (i > 0 && j > 0) { neighbors.push_back(lights[i - 1][j - 1]); }
      if (i < (lights.size() - 1) && j < (lights[i].size() - 1)) { neighbors.push_back(lights[i + 1][j + 1]); }
      if (i > 0 && j < (lights[i].size() - 1)) { neighbors.push_back(lights[i - 1][j + 1]); }
      if (i < (lights.size() - 1) && j > 0) { neighbors.push_back(lights[i + 1][j - 1]); }
      lights[i][j]->prepareNextState(neighbors);
    }
  }
  // Next State
  for (size_t i{0}; i < lights.size(); ++i) {
    for (size_t j{0}; j < lights[i].size(); ++j) {
      lights[i][j].nextState();
    }
  }
}
size_t Grid::numberOfLightsOn() const {
  auto sum = 0;
  for (size_t i{0}; i < lights.size(); ++i) {
    sum += std::count_if(
      std::begin(lights[i]), std::end(lights[i]),
      [](const auto &light) { return light.isOn(); });
  }
  return sum;
}

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

Теперь давайте взглянем на гораздо более крупный метод, который позволяет нам перейти к следующему состоянию Grid. 🤔 Этот метод можно было бы разделить на две части, так как первая часть посвящена подготовке каждого источника света, а вторая часть запускает метод nextState для каждого источника света. Сложность этого метода заключается в том, чтобы создать соседей каждого источника света на этапе подготовки. В зависимости от того, где находится свет на сетке (на краю или нет), количество и положение соседей будут меняться, поэтому мы должны приспосабливаться к этому.

Все эти условия довольно дороги, и есть решения, чтобы улучшить это. Мы могли бы, например, интегрировать соседей в класс Light, так что нам нужно было бы вычислять соседей только один раз для каждого источника света. Еще одно решение, часто используемое в реализации Игры жизни Конвея, состоит в том, чтобы добавить слой источников света вокруг сетки и сделать эти источники света всегда включенными, чтобы интересующий нас источник света всегда имел восемь соседей. 😃

И чтобы завершить эту часть дня, все, что нам нужно, это запустить функцию Grid::nextStep 100 раз, чтобы найти решение:

for (auto i = 0; i < 100; ++i) {
  grid.nextStep();
}
const auto numberOfLightsOn = grid.numberOfLightsOn();

И вуаля, красивая анимация для нашей сетки 😉

Часть 2

Проблема

После настройки сетки мы замечаем, что свет в каждом углу сетки застрял и не может быть выключен. Это полностью поведение анимации, поэтому нам нужно выяснить, сколько источников света включено после 100 шагов, когда свет всегда включен.

Решение

Итак, теперь есть свет с особым поведением, которое звучит так, будто нам нужно какое-то наследование. На самом деле, используя наследование, поведение света в углу реализовать довольно просто:

class CornerLight : public Light {
public:
  CornerLight() : Light(true) {}
  ~CornerLight() = default;
  bool isOn() const override { return true; }
  bool isOff() const override { return false; }
};

И здесь у нас есть CornerLight, который всегда остается включенным (не забудьте установить метод как virtual в классе Light).

Так что создать класс было легко, но интегрировать его немного дольше. 🤔 Действительно, мы не сделали класс Grid способным иметь дело с наследованием на Light, поэтому нам нужно модифицировать его, добавив какой-то метод:

class Grid {
public:
// ... (other methods)
  void pushBackLight(std::unique_ptr<Light> light); 
  std::vector<std::vector<std::unique_ptr<Light>>> &getLights(); 
private:
  std::vector<std::vector<std::unique_ptr<Light>>> lights;

Таким образом, мы изменили Light на std::unique_ptr<Light>, чтобы иметь возможность использовать некоторое наследование, и добавили метод для добавления Light и его унаследованных классов в сетку. Реализация этого метода проста:

void Grid::emplaceLight(LightState lightState) {
  lights.back().emplace_back(std::make_unique<Light>(lightState));
}
void Grid::pushBackLight(std::unique_ptr<Light> light) {
  lights.back().emplace_back(std::move(light));
}

Нам также пришлось адаптировать Grid::emplaceLight(LightState lightState), так как теперь у нас есть std::unique_ptr 🙂

Итак, теперь у нас есть новый король света, мы адаптировали Grid, чтобы иметь возможность работать с ним, все, что нам осталось сделать, это добавить специальный свет в нужном месте.

auto &grid = lights.getLights();
const auto &lastLightIndex = grid[0].size() - 1;
grid[0][0] = std::make_unique<CornerLight>();
grid[0][grid[0].size() - 1] = std::make_unique<CornerLight>();
grid[grid.size() - 1][0] = std::make_unique<CornerLight>();
grid[grid.size() - 1][grid[grid.size() - 1].size() - 1] = std::make_unique<CornerLight>();

Это один из способов сделать это. После создания всей сетки с помощью простого Light вы изменяете 4 угла, чтобы в них было CornerLight, прежде чем выполнять 100 шагов 😉

И вуаля, у вас есть все интересные элементы во второй части 🙂

Вывод

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

Вот список элементов, которые мы использовали, я не могу убедить вас взглянуть на их определения:

- стандартный::вектор

- стд::начало

- стд::конец

- std::count_if

- std::unique_ptr

- std::make_unique

- стд::переместить

- std::reference_wrapper

Спасибо, что читаете, надеюсь, вам понравилось 😃

И до следующей части, получайте удовольствие, учась и развиваясь.

Первоначально опубликовано на http://10xlearner.com 9 декабря 2019 г.