11
\$\begingroup\$

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 < 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?

\$\endgroup\$
  • 7
    \$\begingroup\$ Welcome to Code Review. I have rolled back your last edit. Please do not update the code in your question to incorporate feedback from answers, doing so goes against the Question + Answer style of Code Review. This is not a forum where you should keep the most updated version in your question. Please see what you may and may not do after receiving answers. \$\endgroup\$ – Heslacher Sep 17 at 4:35
13
\$\begingroup\$

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.

  1. 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)
  1. 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] & d\in[0, H) \\ 0 & d=H, 2H + 1\\ s_0[2H-d] & 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] & d = 0 \\ s_k'[d-1]\oplus s_k'[d+1] = s_k[d-1]\oplus s_k[d+1]=s_{k+1}[d] & d\in(0,H) \\ s_k'[H-1]\oplus s_k'[H+1] = s_k[H-1]\oplus s_k[H-1] = 0 & 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] & d\in(H,2H) \\ s_k'[2H-1]\oplus s_k'[2H+1] = s_k'[2H-1] = s_k[1] = s_{k+1}[0] & d = 2H \\ s_k'[2H]\oplus s_k'[0] = s_k[0]\oplus s_k[0] = 0 & d = 2H+1 \end{array}\right. $$

We can then verify the following property of \$s_k'\$ $$ \begin{eqnarray} s_{k+1}'[d] & = & s_k'[(d-1)\%H'] \oplus s_k'[(d+1)\%H'] & \\ s_{k+2}'[d] & = & s_{k+1}[(d-1)\%H'] \oplus s_{k+1}[(d+1)\%H'] \\ & = & s_k[(d-2)\%H'] \oplus s_k[d] \oplus s_k[d] \oplus s_k[(d+2)\%H'] \\ & = & s_k[(d-2)\%H'] \oplus s_k[(d+2)\%H'] \\ s_{k+4}'[d] & = & s_{k+2}'[(d-2)\%H'] \oplus s_{k+2}'[(d+2)\%H'] \\ & = & s_k'[(d-4)\%H'] \oplus s_k'[d] \oplus s_k'[d] \oplus s_k'[(d+4)\%H'] \\ & = & s_k'[(d-4)\%H'] \oplus s_k'[(d+4)\%H'] \\ \ldots & \\ s_{k+2^m}'[d] & = & 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' & = & (d-2^m)\%H' & \qquad d_2' & = & (d+2^m)\%H' \\ d_1 & = & \min(d_1',2H-d_1') & \qquad d_2 & = & \min(d_2', 2H-d_2') \\ a_1 & = & \left\{\begin{array}{ll} s_k[d_1] & d_1 \in [0, L) \\ 0 & \text{Otherwise} \\ \end{array}\right. & \qquad a_2 & = & \left\{\begin{array}{ll} s_k[d_2] & d_2 \in [0, L) \\ 0 & \text{Otherwise} \\ \end{array}\right. \\ & & & s_{k+2^m}[d] & = & 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>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>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>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)\$.

\$\endgroup\$
  • \$\begingroup\$ Thanks so much for the thorough analysis. What is the runtime of this and how does it compare to my original solution? \$\endgroup\$ – LuxuryMode Sep 17 at 3:13
  • \$\begingroup\$ Your shortcut formula fails on the second example. It appears from the examples that houses outside the 8 are supposed to be treated as 0 at every stage, whereas you are assuming an infinite board with all other houses initially 0. The actual update rule is a reversible permutation of the 256 states, and all cycles have lengths 1, 2, 7, or 14, so you can start with days %= 14 and have an O(1) algorithm (which then automatically supports days < 0 too). \$\endgroup\$ – benrg Sep 17 at 21:15
  • 1
    \$\begingroup\$ @benrg Thanks for pointing out the mistake. I've revised the algorithm and proved a conclusion of cycle lengths for arbitrary number of houses \$H\$. Note that your \$O(1)\$ time complexity is based on fixed \$H=8\$ and therefore cannot be directly generalized to arbitrary \$H\$. \$\endgroup\$ – GZ0 Sep 18 at 7:12
  • 1
    \$\begingroup\$ @LuxuryMode I made a mistake yesterday on the boundaries of the state sequence. I've revised the algorithm entirely and presented a complete algorithm as well as the time complexity analysis. \$\endgroup\$ – GZ0 Sep 18 at 7:13
  • \$\begingroup\$ @benrg The reversibility only holds when \$H\$ is even. If \$H\$ is odd, there exist states that cannot be a valid output of any other state (e.g., [1, 0, 0]). Therefore not all the states are in the cycles themselves. \$\endgroup\$ – GZ0 Sep 18 at 16:54
10
\$\begingroup\$

On the logic, you should notice that the next state of the i'th house becomes

state[i - 1] ^ state[i + 1]

(some care at the boundaries to be exercised). Upon the closer inspection you may also notice that if you represent the state of the entire block as an integer composed of bits from each house, then

state = (state << 1) ^ (state >> 1)

is all you need to do. Python would take care of boundaries (by shifting in zeroes into right places), and update all bits simultaneously.


I don't know the constraints, but I suspect that the number of days could be quite large. Since there are only that many states the block may be in (for 8 houses there are mere 256 of them), you are going to encounter the loop. An immediate optimization is to identify it, and use its length, rather than simulating each day in the entire time period.

\$\endgroup\$
  • 4
    \$\begingroup\$ While Python will take care of one of the boundaries automatically (since a >> b discards the lowest b bits of a), you do need an explicit bit mask to take care of the other. Something like state = ((state << 1) ^ (state >> 1)) & ((1 << cells) - 1), where cells = 8 is the number of "houses" in the system, should do it. \$\endgroup\$ – Ilmari Karonen Sep 17 at 10:41
5
\$\begingroup\$

Enumerate

Instead of writing range(len()), consider using enumerate. It provides the index and the value associated with that index. It's useful in your case because, instead of having to write in_states[i], you can write value instead. This will save you from having to index the list again with in_states[i].

Docstrings

You should provide a docstring at the beginning of every module, class, and method you write. This will allow people to see how your code functions, and what it's supposed to do. It also helps you remember what types of variables are supposed to be passed into the method. Take this for example.

def my_method(param_one, param_two):
    ... do code stuff here ...

By reading just the method header, you had no idea what data this method is supposed to accept (hopefully you never have parameter names this ambiguous, but I'm being extreme in this example). Now, take a look at this:

def my_method(param_one, param_two):
    """
    This method does ... and ... ...

    :param param_one: An Integer representing ...
    :param param_two: A String representing ...
    """
    ... do code stuff here ...

Now, you know clearly what is supposed to be passed to the method.

Consistency

I see this in your code:

new_state.append(0 if group[0] == group[2] else 1)

But then I see this:

if not state:
    state = new_state(states)
else:
    state = new_state(state)

You clearly know how to accomplish the former, and since that code looks cleaner, I'd say you stick with it and be consistent:

state = new_state(states if not state else state)

Looping

Your looping with the while loop and using j confuses me. It looks like a glorified for loop, only running days amount of times. So, this:

state = None
j = 0
while j < days:
    if not state:
        state = new_state(states)
    else:
        state = new_state(state)
    j += 1

Can be simplified to this:

state = None
for _ in range(days):
    state = new_state(states if not state else state)
return state

Updated Code

"""
Module Docstring (a description of this program goes here)
"""
def cell_compete(states, days):
    """
    Method Docstring (a description of this method goes here)
    """
    def new_state(in_states):
        """
        Method Docstring (a description of this method goes here)
        """
        new_state = []
        for index, value in enumerate(in_states):
            if index == 0:
                group = [0, in_states[0], in_states[1]]
            elif index == len(in_states) - 1:
                group = [in_states[index - 1], value, 0]
            else:
                group = [in_states[index - 1], value, in_states[index + 1]]
            new_state.append(0 if group[0] == group[2] else 1)
        return new_state

    state = None
    for _ in range(days):
        state = new_state(states if not state else state)
    return state
\$\endgroup\$
  • \$\begingroup\$ Thanks a lot, great feedback. I appreciate it. Any thoughts on the substance/logic of the algorithm itself? \$\endgroup\$ – LuxuryMode Sep 17 at 1:34
  • 4
    \$\begingroup\$ states if not state else state is somewhat awkward - first, it should be inverted as state if state else states. Then, take advantage of or semantics: state or states. \$\endgroup\$ – Reinderien Sep 17 at 6:13
  • 1
    \$\begingroup\$ Actually state can be initialized with states to avoid the unnecessary test of if state (moreover, the states variable can be used directly without the need of state). \$\endgroup\$ – GZ0 Sep 17 at 14:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.