Algorithm on hexagonal grid

Question

Hexagonal grid is represented by a two-dimensional array with R rows and C columns. First row always comes "before" second in hexagonal grid construction (see image below). Let k be the number of turns. Each turn, an element of the grid is 1 if and only if the number of neighbours of that element that were 1 the turn before is an odd number. Write C++ code that outputs the grid after k turns.

Limitations:

1 <= R <= 10, 1 <= C <= 10, 1 <= k <= 2^(63) - 1

An example with input (in the first row are R, C and k, then comes the starting grid):

4 4 3
0 0 0 0
0 0 0 0
0 0 1 0
0 0 0 0

Simulation: image, yellow elements represent '1' and blank represent '0'.

This problem is easy to solve if I simulate and produce a grid each turn, but with big enough k it becomes too slow. What is the faster solution?

EDIT: code (n and m are used instead R and C) :

#include <cstdio>
#include <cstring>

using namespace std;

int old[11][11];
int _new[11][11];

int n, m;
long long int k;

int main() {

  scanf ("%d %d %lld", &n, &m, &k);

  for (int i = 0; i < n; i++) {
    for (int j = 0; j < m; j++) scanf ("%d", &old[i][j]);
  }

  printf ("\n");

  while (k) {

    for (int i = 0; i < n; i++) {
      for (int j = 0; j < m; j++) {
        int count = 0;
        if (i % 2 == 0) {
          if (i) {
            if (j) count += old[i-1][j-1];
            count += old[i-1][j];
          }
          if (j) count += (old[i][j-1]);
          if (j < m-1) count += (old[i][j+1]);
          if (i < n-1) {
            if (j) count += old[i+1][j-1];
            count += old[i+1][j];
          }
        }
        else {
          if (i) {
            if (j < m-1) count += old[i-1][j+1];
            count += old[i-1][j];
          }
          if (j) count += old[i][j-1];
          if (j < m-1) count += old[i][j+1];
          if (i < n-1) {
            if (j < m-1) count += old[i+1][j+1];
            count += old[i+1][j];
          }
        }
        if (count % 2) _new[i][j] = 1;
        else _new[i][j] = 0;
      }
    }

    for (int i = 0; i < n; i++) {
      for (int j = 0; j < m; j++) old[i][j] = _new[i][j];
    }

    k--;
  }

  for (int i = 0; i < n; i++) {
    for (int j = 0; j < m; j++) {
      printf ("%d", old[i][j]);
    }
    printf ("\n");
  }

  return 0;
}

Answer 1

There are several ways to speed up your algorithm.

You do the neighbour-calculation with the out-of bounds checking in every turn. Do some preprocessing and calculate the neighbours of each cell once at the beginning. (Aziuth has already proposed that.)

Then you don't need to count the neighbours of all cells. Each cell is on if an odd number of neighbouring cells were on in the last turn and it is off otherwise.

You can think of this differently: Start with a clean board. For each active cell of the previous move, toggle the state of all surrounding cells. When an even number of neighbours cause a toggle, the cell is on, otherwise the toggles cancel each other out. Look at the first step of your example. It's like playing Lights Out, really.

This method is faster than counting the neighbours if the board has only few active cells and its worst case is a board whose cells are all on, in which case it is as good as neighbour-counting, because you have to touch each neighbours for each cell.

The next logical step is to represent the board as a sequence of bits, because bits already have a natural way of toggling, the exclusive or or xor oerator, ^. If you keep the list of neigbours for each cell as a bit mask m, you can then toggle the board b via b ^= m.

These are the improvements that can be made to the algorithm. The big improvement is to notice that the patterns will eventually repeat. (The toggling bears resemblance with Conway's Game of Life, where there are also repeating patterns.) Also, the given maximum number of possible iterations, 2⁶³ is suspiciously large.

The playing board is small. The example in your question will repeat at least after 2¹⁶ turns, because the 4×4 board can have at most 2¹⁶ layouts. In practice, turn 127 reaches the ring pattern of the first move after the original and it loops with a period of 126 from then.

The bigger boards may have up to 2¹⁰⁰ layouts, so they may not repeat within 2⁶³ turns. A 10×10 board with a single active cell near the middle has ar period of 2,162,622. This may indeed be a topic for a maths study, as Aziuth suggests, but we'll tacke it with profane means: Keep a hash map of all previous states and the turns where they occurred, then check whether the pattern has occurred before in each turn.

We now have:

• a simple algorithm for toggling the cells' state and
• a compact bitwise representation of the board, which allows us to create a hash map of the previous states.

Here's my attempt:

#include <iostream>
#include <map>

/*
 *  Bit representation of a playing board, at most 10 x 10
 */
struct Grid {
    unsigned char data[16];

    Grid() : data() {
    }

    void add(size_t i, size_t j) {
        size_t k = 10 * i + j;

        data[k / 8] |= 1u << (k % 8);
    }

    void flip(const Grid &mask) {
        size_t n = 13;

        while (n--) data[n] ^= mask.data[n];
    }

    bool ison(size_t i, size_t j) const {
        size_t k = 10 * i + j;

        return ((data[k / 8] & (1u << (k % 8))) != 0);
    }

    bool operator<(const Grid &other) const {
        size_t n = 13;

        while (n--) {
            if (data[n] > other.data[n]) return true;
            if (data[n] < other.data[n]) return false;
        }

        return false;
    }

    void dump(size_t n, size_t m) const {
        for (size_t i = 0; i < n; i++) {
            for (size_t j = 0; j < m; j++) {
                std::cout << (ison(i, j) ? 1 : 0);
            }
            std::cout << '\n';
        }
        std::cout << '\n';
    }
};

int main()
{
    size_t n, m, k;

    std::cin >> n >> m >> k;

    Grid grid;
    Grid mask[10][10];

    for (size_t i = 0; i < n; i++) {
        for (size_t j = 0; j < m; j++) {
            int x;

            std::cin >> x;
            if (x) grid.add(i, j);
        }
    }

    for (size_t i = 0; i < n; i++) {
        for (size_t j = 0; j < m; j++) {
            Grid &mm = mask[i][j];

            if (i % 2 == 0) {
                if (i) {
                    if (j) mm.add(i - 1, j - 1);
                    mm.add(i - 1, j);
                }
                if (j) mm.add(i, j - 1);
                if (j < m - 1) mm.add(i, j + 1);
                if (i < n - 1) {
                    if (j) mm.add(i + 1, j - 1);
                    mm.add(i + 1, j);
                }
            } else {
                if (i) {
                    if (j < m - 1) mm.add(i - 1, j + 1);
                    mm.add(i - 1, j);
                }
                if (j) mm.add(i, j - 1);
                if (j < m - 1) mm.add(i, j + 1);
                if (i < n - 1) {
                    if (j < m - 1) mm.add(i + 1, j + 1);
                    mm.add(i + 1, j);
                }
            }
        }
    }

    std::map<Grid, size_t> prev;
    std::map<size_t, Grid> pattern;

    for (size_t turn = 0; turn < k; turn++) {    
        Grid next;
        std::map<Grid, size_t>::const_iterator it = prev.find(grid);

        if (1 && it != prev.end()) {
            size_t start = it->second;
            size_t period = turn - start;
            size_t index = (k - turn) % period;

            grid = pattern[start + index];
            break;
        }

        prev[grid] = turn;
        pattern[turn] = grid;

        for (size_t i = 0; i < n; i++) {
            for (size_t j = 0; j < m; j++) {
                if (grid.ison(i, j)) next.flip(mask[i][j]);
            }
        }

        grid = next;        
    }

    for (size_t i = 0; i < n; i++) {
        for (size_t j = 0; j < m; j++) {
            std::cout << (grid.ison(i, j) ? 1 : 0);
        }
        std::cout << '\n';
    }

    return 0;
}

There is probably room for improvement. Especially, I'm not so sure how it fares for big boards. (The code above uses an ordered map. We don't need the order, so using an unordered map will yield faster code. The example above with a single active cell on a 10×10 board took significantly longer than a second with an ordered map.)

Answer 2

For a given R and C, you have N=R*C cells.

If you represent those cells as a vector of elements in GF(2), i.e, 0s and 1s where arithmetic is performed mod 2 (addition is XOR and multiplication is AND), then the transformation from one turn to the next can be represented by an N*N matrix M, so that:

turn[i+1] = M*turn[i]

You can exponentiate the matrix to determine how the cells transform over k turns:

turn[i+k] = (M^k)*turn[i]

Even if k is very large, like 2^63-1, you can calculate M^k quickly using exponentiation by squaring: https://en.wikipedia.org/wiki/Exponentiation_by_squaring This only takes O(log(k)) matrix multiplications.

Then you can multiply your initial state by the matrix to get the output state.

From the limits on R, C, k, and time given in your question, it's clear that this is the solution you're supposed to come up with.

Answer 3

This started off as a comment, but I think it could be helpful as an answer in addition to what has already been stated.

You stated the following limitations:

1 <= R <= 10, 1 <= C <= 10

Given these restrictions, I'll take the liberty to can represent the grid/matrix M of R rows and C columns in constant space (i.e. O(1)), and also check its elements in O(1) instead of O(R*C) time, thus removing this part from our time-complexity analysis.

That is, the grid can simply be declared as bool grid[10][10];.

The key input is the large number of turns k, stated to be in the range:

1 <= k <= 2^(63) - 1

The problem is that, AFAIK, you're required to perform k turns. This makes the algorithm be in O(k). Thus, no proposed solution can do better than O(k)[1].

To improve the speed in a meaningful way, this upper-bound must be lowered in some way[1], but it looks like this cannot be done without altering the problem constraints.

Thus, no proposed solution can do better than O(k)[1].

The fact that k can be so large is the main issue. The most anyone can do is improve the rest of the implementation, but this will only improve by a constant factor; you'll have to go through k turns regardless of how you look at it.

Therefore, unless some clever fact and/or detail is found that allows this bound to be lowered, there's no other choice.

---

[1] For example, it's not like trying to determine if some number n is prime, where you can check all numbers in the range(2, n) to see if they divide n, making it a O(n) process, or notice that some improvements include only looking at odd numbers after checking n is not even (constant factor; still O(n)), and then checking odd numbers only up to √n, i.e., in the range(3, √n, 2), which meaningfully lowers the upper-bound down to O(√n).

Answer 4

Not sure about how you did it - and you should really always post code here - but let's try to optimize things here.

First of all, there is not really a difference between that and a quadratic grid. Different neighbor relationships, but I mean, that is just a small translation function. If you have a problem there, we should treat this separately, maybe on CodeReview.

Now, the naive solution is:

for all fields
    count neighbors
    if odd: add a marker to update to one, else to zero
for all fields
    update all fields by marker of former step

this is obviously in O(N). Iterating twice is somewhat twice the actual run time, but should not be that bad. Try not to allocate space every time that you do that but reuse existing structures.

I'd propose this solution:

at the start:
    create a std::vector or std::list "activated" of pointers to all fields that are activated

each iteration:
    create a vector "new_activated"
    for all items in activated
        count neighbors, if odd add to new_activated
    for all items in activated
        set to inactive
    replace activated by new_activated*
    for all items in activated
        set to active

*this can be done efficiently by putting them in a smart pointer and use move semantics

This code only works on the activated fields. As long as they stay within some smaller area, this is far more efficient. However, I have no idea when this changes - if there are activated fields all over the place, this might be less efficient. In that case, the naive solution might be the best one.

EDIT: after you now posted your code... your code is quite procedural. This is C++, use classes and use representation of things. Probably you do the search for neighbors right, but you can easily make mistakes there and therefore should isolate that part in a function, or better method. Raw arrays are bad and variables like n or k are bad. But before I start tearing your code apart, I instead repeat my recommendation, put the code on CodeReview, having people tear it apart until it is perfect.