ca_critters_reversible_example.cc

Go to the documentation of this file.

/*
                          Aleph_w
 
  Data structures & Algorithms
  version 2.0.0b
  https://github.com/lrleon/Aleph-w
 
  This file is part of Aleph-w library
 
  Copyright (c) 2002-2026 Leandro Rabindranath Leon
*/
 
#include <cstddef>
#include <cstdint>
#include <cstdlib>
#include <iostream>
#include <limits>
#include <random>
#include <stdexcept>
#include <string>
 
#include <ca-traits.H>
#include <tpl_ca_async_engine.H>
#include <tpl_ca_block_rule.H>
#include <tpl_ca_lattice.H>
#include <tpl_ca_storage.H>
#include <tpl_ca_update_scheme.H>
 
using namespace Aleph;
using namespace Aleph::CA;
 
namespace
{
 
using Grid = Lattice<Dense_Cell_Storage<int, 2>, ToroidalBoundary>;
 
void seed(Grid &g, std::uint32_t seed_value, double p_alive)
{
  std::mt19937 rng(seed_value);
  std::uniform_real_distribution<double> u(0.0, 1.0);
  for (ca_size_t i = 0; i < g.size(0); ++i)
    for (ca_size_t j = 0; j < g.size(1); ++j)
      g.set({static_cast<ca_index_t>(i), static_cast<ca_index_t>(j)},
            u(rng) < p_alive ? 1 : 0);
}
 
void render(const Grid &g, std::ostream &os)
{
  for (ca_size_t i = 0; i < g.size(0); ++i)
    {
      for (ca_size_t j = 0; j < g.size(1); ++j)
        os << (g.at({static_cast<ca_index_t>(i), static_cast<ca_index_t>(j)})
                 ? "##"
                 : " .");
      os << '\n';
    }
}
 
bool grids_equal(const Grid &a, const Grid &b)
{
  for (ca_size_t i = 0; i < a.size(0); ++i)
    for (ca_size_t j = 0; j < a.size(1); ++j)
      if (a.at({static_cast<ca_index_t>(i), static_cast<ca_index_t>(j)})
          != b.at({static_cast<ca_index_t>(i), static_cast<ca_index_t>(j)}))
        return false;
  return true;
}
 
std::size_t alive(const Grid &g)
{
  std::size_t n = 0;
  for (ca_size_t i = 0; i < g.size(0); ++i)
    for (ca_size_t j = 0; j < g.size(1); ++j)
      if (g.at({static_cast<ca_index_t>(i), static_cast<ca_index_t>(j)}) != 0)
        ++n;
  return n;
}
 
}  // namespace
 
int main(int argc, char **argv)
{
  std::size_t steps = 1000;
  ca_size_t side = 32;
  std::uint32_t seed_value = 0xC0DEFEEDu;
  try
    {
      if (argc >= 2)
        steps = static_cast<std::size_t>(std::stoul(argv[1]));
      if (argc >= 3)
        side = static_cast<ca_size_t>(std::stoul(argv[2]));
      if (argc >= 4)
        {
          // Accept hex (0x...) or decimal so the seed survives a
          // round-trip through the printed banner.
          const unsigned long long s = std::stoull(argv[3], nullptr, 0);
          if (s > std::numeric_limits<std::uint32_t>::max())
            throw std::out_of_range("seed");
          seed_value = static_cast<std::uint32_t>(s);
        }
    }
  catch (const std::invalid_argument &)
    {
      std::cerr << "Invalid argument: expected non-negative integers for "
                   "[steps] [side] [seed]\n";
      return 1;
    }
  catch (const std::out_of_range &)
    {
      std::cerr << "Argument out of range for [steps] [side] [seed]\n";
      return 1;
    }
 
  // Margolus reversibility requires a 2D grid whose extents are
  // both ≥ 2 and even: odd extents leave a one-cell strip that the
  // alternating partition cannot reach without breaking the
  // forward(N) ∘ backward(N) = identity property.
  if (side < 2 or side % 2 != 0)
    {
      std::cerr << "Invalid side: " << side
                << " (must be a positive even integer ≥ 2 for Margolus reversibility)\n";
      return 1;
    }
 
  Grid initial({side, side}, 0);
  seed(initial, seed_value, 0.45);
  Grid baseline = initial;
 
  std::cout << "Critters reversible CA — " << side << "×" << side
            << ", " << steps << " steps, seed 0x" << std::hex << seed_value
            << std::dec << "\n\n";
  std::cout << "Initial frame (" << alive(initial) << " alive):\n";
  render(initial, std::cout);
 
  using Engine = Async_Engine<Grid, Critters_Rule, Null_Neighborhood<2>,
                              Margolus_Update>;
  Engine engine(std::move(initial), Critters_Rule{}, Null_Neighborhood<2>{});
  engine.run(steps);
 
  std::cout << "\nAfter forward(" << steps << ") steps ("
            << alive(engine.frame()) << " alive):\n";
  render(engine.frame(), std::cout);
 
  engine.run_back(steps);
 
  std::cout << "\nAfter backward(" << steps << ") steps ("
            << alive(engine.frame()) << " alive):\n";
  render(engine.frame(), std::cout);
 
  const bool ok = grids_equal(engine.frame(), baseline);
  std::cout << "\nReversibility check: "
            << (ok ? "PASS — bit-exact identity recovered"
                   : "FAIL — recovered frame differs from initial")
            << "\n";
  return ok ? 0 : 1;
}