Algorithm for competing cells of 0s and 1s I'm working on a practice algorithm problem, stated as follows:


  There are eight houses represented as cells. Each day, the houses compete with adjacent ones. 1 represents an "active" house and 0 represents an "inactive" house. If the neighbors on both sides of a given house are either both active or both inactive, then that house becomes inactive on the next day. Otherwise it becomes active. For example, if we had a group of neighbors [0, 1, 0] then the house at [1] would become 0 since both the house to its left and right are both inactive. The cells at both ends only have one adjacent cell so assume that the unoccupied space on the other side is an inactive cell. 
  
  Even after updating the cell, you have to consider its prior state when updating the others so that the state information of each cell is updated simultaneously. 
  
  The function takes the array of states and a number of days and should output the state of the houses after the given number of days. 
  
  Examples:
  
  
  input: states = [1, 0, 0, 0, 0, 1, 0, 0], days = 1
  output should be [0, 1, 0, 0, 1, 0, 1, 0]
  input: states = [1, 1, 1, 0, 1, 1, 1, 1], days = 2
  output should be [0, 0, 0, 0, 0, 1, 1, 0]
  


Here's my solution:

def cell_compete(states, days):
    def new_state(in_states):
        new_state = []
        for i in range(len(in_states)):
            if i == 0:
                group = [0, in_states[0], in_states[1]]
            elif i == len(in_states) - 1:
                group = [in_states[i - 1], in_states[i], 0]
            else:
                group = [in_states[i - 1], in_states[i], in_states[i + 1]]
            new_state.append(0 if group[0] == group[2] else 1)
        return new_state

    state = None
    j = 0
    while j &lt; days:
        if not state:
            state = new_state(states)
        else:
            state = new_state(state)
        j += 1
    return state


I originally thought to take advantage of the fact they are 0s and 1s only and to use bitwise operators, but couldn't quite get that to work. 

How can I improve the efficiency of this algorithm or the readability of the code itself?
EDIT: Thanks to @benrg pointing out a bug of the previous algorithm. I have revised the algorithm and moved it to the second part since the explanation is long.

While the other answer focuses more on coding style, this answer will focus more on performance.

Implementation Improvements

I will show some ways to improve the performance of the code in the original post.


The use of group is unnecessary in the for-loop. Also note that if a house has a missing adjacent neighbour, its next state will be the same as the existing neighbour. So the loop can be improved as follows.




for i in range(len(in_states)):
    if i == 0:
        out_state = in_states[1]
    elif i == len(in_states) - 1:
        out_state = in_states[i - 1]
    else:
        out_state = in_states[i - 1] == in_states[i + 1]
    new_state.append(out_state)



It is usually more efficient to use list comprehensions rather than explicit for-loops to construct lists in Python. Here, you need to construct a list where: (1) the first element is in_states[1]; (2) the last element is in_states[-2]; (3) all other elements are in_states[i - 1] == in_states[i + 1]. In this case, it is possible to use a list comprehension to construct a list for (3) and then add the first and last elements.




new_states = [in_states[i-1] == in_states[i+1] for i in range(1, len(in_states) - 1)]
new_states.insert(in_states[1], 0)
new_states.append(in_states[-2])


However, insertion at the beginning of a list requires to update the entire list. A better way to construct the list is to use extend with a generator expression:



new_states = [in_states[1]]
new_states.extend(in_states[i-1] == in_states[i+1] for i in range(1, len(in_states) - 1))
new_states.append(in_states[-2])


An even better approach is to use the unpack operator * with a generator expression. This approach is more concise and also has the best performance.



# state_gen is a generator expression for computing new_states[1:-1]
state_gen = (in_states[i-1] == in_states[i+1] for i in range(1, len(in_states) - 1))
new_states = [in_states[1], *state_gen, in_states[-2]]


Note that it is possible to unpack multiple iterators / generator expressions into the same list like this:

new_states = [*it1, *it2, *it3]




Note that if it1 and it3 are already lists, unpacking will make another copy so it could be less efficient than extending it1 with it2 and it3, if the size of it1 is large.

Algorithmic Improvement

Here I show how to improve the algorithm for more general inputs (i.e. a varying number of houses). The naive solution updates the house states for each day. In order to improve it, one needs to find a connection between the input states \$s_0\$ and the states \$s_n\$ after some days \$n\$ for a direct computation.

Let \$s_k[d]\$ be the state of the house at index \$d\$ on day \$k\$ and \$H\$ be the total number of houses. We first extend the initial state sequence \$s_0\$ into an auxiliary sequence \$s_0'\$ of length \$H'=2H+2\$ based on the following:

$$
s_0'[d]=\left\{\begin{array}{ll}
s_0[d] &amp; d\in[0, H) \\
0      &amp; d=H, 2H + 1\\
s_0[2H-d] &amp; d\in(H,2H] \\
\end{array}\right.\label{df1}\tag{1}
$$

The sequence \$s_k'\$ is updated based on the following recurrence, where \$\oplus\$ and \$\%\$ are the exclusive-or and modulo operations, respectively:
$$
s_{k+1}'[d] = s_k'[(d-1)\%H']\oplus s_k'[(d+1)\%H']\label{df2}\tag{2}
$$

Using two basic properties of \$\oplus\$: \$a\oplus a = 0\$ and \$a\oplus 0 = a\$, the relationship (\ref{df1}) can be proved to hold on any day \$k\$ by induction:

$$s_{k+1}'[d] = \left\{
\begin{array}{ll}
s_k'[1]\oplus s_k'[H'-1] = s_k'[1] = s_k[1] = s_{k+1}[0] &amp; d = 0 \\
s_k'[d-1]\oplus s_k'[d+1] = s_k[d-1]\oplus s_k[d+1]=s_{k+1}[d] &amp; d\in(0,H) \\
s_k'[H-1]\oplus s_k'[H+1] = s_k[H-1]\oplus s_k[H-1] = 0 &amp; d = H \\
s_k'[2H-(d-1)]\oplus s_k'[2H-(d+1)] \\
\quad = s_k[2H-(d-1)]\oplus s_k[2H-(d+1)] = s_{k+1}[2H-d] &amp; d\in(H,2H) \\
s_k'[2H-1]\oplus s_k'[2H+1] = s_k'[2H-1] = s_k[1] = s_{k+1}[0] &amp; d = 2H \\
s_k'[2H]\oplus s_k'[0] = s_k[0]\oplus s_k[0] = 0 &amp; d = 2H+1
\end{array}\right.
$$

We can then verify the following property of \$s_k'\$
$$
\begin{eqnarray}
s_{k+1}'[d] &amp; = &amp; s_k'[(d-1)\%H'] \oplus s_k'[(d+1)\%H'] &amp; \\
s_{k+2}'[d] &amp; = &amp; s_{k+1}[(d-1)\%H'] \oplus s_{k+1}[(d+1)\%H'] \\
       &amp; = &amp; s_k[(d-2)\%H'] \oplus s_k[d] \oplus s_k[d] \oplus s_k[(d+2)\%H'] \\
       &amp; = &amp; s_k[(d-2)\%H'] \oplus s_k[(d+2)\%H'] \\
s_{k+4}'[d] &amp; = &amp; s_{k+2}'[(d-2)\%H'] \oplus s_{k+2}'[(d+2)\%H'] \\
       &amp; = &amp; s_k'[(d-4)\%H'] \oplus s_k'[d] \oplus s_k'[d] \oplus s_k'[(d+4)\%H'] \\
       &amp; = &amp; s_k'[(d-4)\%H'] \oplus s_k'[(d+4)\%H'] \\
\ldots &amp; \\
s_{k+2^m}'[d] &amp; = &amp; s_k'[(d-2^m)\%H'] \oplus s_k'[(d+2^m)\%H']  \label{f1} \tag{3}
\end{eqnarray}
$$

Based on the recurrence (\ref{f1}), one can directly compute \$s_{k+2^m}'\$ from \$s_k'\$ and skip all the intermediate computations. We can also substitute \$s_k'\$ with \$s_k\$ in (\ref{f1}), leading to the following computations:

$$
\begin{eqnarray}
d_1' &amp; = &amp; (d-2^m)\%H' &amp; \qquad d_2' &amp; = &amp; (d+2^m)\%H' \\
d_1 &amp; = &amp; \min(d_1',2H-d_1') &amp; \qquad d_2 &amp; = &amp; \min(d_2', 2H-d_2') \\
a_1 &amp; = &amp; \left\{\begin{array}{ll}
s_k[d_1] &amp; d_1 \in [0, L) \\
0 &amp; \text{Otherwise} \\
\end{array}\right. &amp;
\qquad a_2 &amp; = &amp; \left\{\begin{array}{ll}
s_k[d_2] &amp; d_2 \in [0, L) \\
0 &amp; \text{Otherwise} \\
\end{array}\right. \\
&amp; &amp; &amp; s_{k+2^m}[d] &amp; = &amp; a_1 \oplus a_2 \label{f2}\tag{4}
\end{eqnarray}
$$

Note that since the sequence \$\{2^i\%H'\}_{i=0}^{+\infty}\$ has no more than \$H'\$ states, it is guaranteed that \$\{s_{k+2^i}\}_{i=0}^{+\infty}\$ has a cycle. More formally, there exists some \$c&gt;0\$ such that \$s_{k+2^{a+c}}=s_{k+2^a}\$ holds for every \$a\$ that is greater than certain threshold. Based on (\ref{f1}) and (\ref{f2}), this entails either \$H'|2^{a+c}-2^a\$ or \$H'|2^{a+c}+2^a\$ holds. If \$H'\$ is factorized into \$2^r\cdot m\$ where \$m\$ is odd, we can see that \$a\geq r\$ must hold for either of the divisibilty. That is to say, if we start from day \$2^r\$ and find the next \$t\$ such that \$H'|2^t-2^r\$ or \$H'|2^t+2^r\$, then \$s_{k+2^t}=s_{k+2^r}\$ holds for every \$k\$. This leads to the following algorithm:




Input: \$H\$ houses with initial states \$s_0\$, number of days \$n\$
Output: House states \$s_n\$ after \$n\$ days
Step 1: Let \$H'\leftarrow 2H+2\$, find the maximal \$r\$ such that \$2^r\mid H'\$ 
Step 2: If \$n\leq 2^r\$, go to Step 5. 
Step 3: Find the minimal \$t, t&gt;r\$ such that either \$H'|2^t-2^r\$ or \$H'|2^t+2^r\$ holds.
Step 4: \$n\leftarrow (n-2^r)\%(2^t-2^r)+2^r\$
Step 5: Divide \$n\$ into a power-2 sum \$2^{b_0}+2^{b_1}+\ldots+2^{b_u}\$ and calculate \$s_n\$ based on (\ref{f2})




As an example, if there are \$H=8\$ houses, \$H'=18=2^1\cdot 9\$. So \$r=1\$. We can find \$t=4\$ is the minimal number such that \$18\mid 2^4+2=18\$. Therefore \$s_{k+2}=s_{k+2^4}\$ holds for every \$k\geq 0\$. So we reduce any \$n&gt;2\$ to \$(n-2)\%14 + 2\$, and then apply Step 5 of the algorithm to get \$s_n\$.

Based on the above analysis, every \$n\$ can be reduced to a number between \$[0, 2^t)\$ and \$s_n\$ can be computed within \$\min(t, \log n)\$ steps using the recurrence (\ref{f2}). So the ultimate time complexity of the algorithm is \$\Theta(H'\cdot \min(t, \log n))=\Theta(H\cdot\min(m,\log n))=\Theta(\min(H^2,H\log n))\$. This is much better than the naive algorithm which has a time complexity of \$\Theta(H\cdot n)\$.