0
$\begingroup$

This is a puzzle offered by HireVue as a challenge to would be programmers and algorithm designers. To my knowledge there is no reward, it's just for fun. And I take great interest in such puzzles.

Suppose we have a matrix with $N$ rows and $M$ columns. The matrix has the entries $0$ and $1$.

We can change the value of an entry from $0$ to $1$ or $1$ to $0$, but when we do, we also change the value of all adjacent entries in a $+$ sign (meaning we change entry to the right, left, above and below). Our goal is that the entire matrix will be zero.

The challenge is to design an algorithm that will change the entire matrix to zero in the minimum amount of steps.

For example:

Suppose we were given $\begin{pmatrix} 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 \end{pmatrix}$. The optimal solution would be:

1) switch state of row $1$ column $4$ to get $\begin{pmatrix} 0 & 0 & 1 & 1 \\ 0 & 1 & 0 & 1\\ 0 & 0 & 0 & 0 \end{pmatrix}$

2) switch state of row $2$ column $3$ to get $\begin{pmatrix} 0 & 0 & 0 & 1 \\ 0 & 0& 1 & 0\\ 0 & 0 & 1 & 0 \end{pmatrix}$

3) switch state of row $2$ column $4$ to get $\begin{pmatrix} 0 & 0 & 0 & 0 \\ 0 & 0& 0 & 1\\ 0 & 0 & 1 & 1 \end{pmatrix}$

4) switch state of row $3$ column $4$ to get $\begin{pmatrix} 0 & 0 & 0 & 0 \\ 0 & 0& 0 & 0\\ 0 & 0 & 0 & 0\end{pmatrix}$

We are done. We solved the puzzle optimally in four steps. That however was just a solved example. I am interested in an algorithm that will yield the optimal solution (meaning least number of state switches) regardless of input.

note: We can have more than one $1$ in the matrix we were given. For example the identity matrix or just a matrix full of ones are also valid inputs. If there is no way to make all the entries $0$, the algorithm needs to recognize that as well.

Source: https://www.codeeval.com/public_sc/191/

$\endgroup$
1
  • 3
    $\begingroup$ This is similar to this game. $\endgroup$
    – pjs36
    Sep 29, 2015 at 22:56

1 Answer 1

0
$\begingroup$

Puzzles like this have been studied extensively in AI. See, for example, this treatment of the 8-puzzle. In the case of the problem you present, breadth-first search will assure us that the solution, if it exists, will be optimal as you define it. You'll define whole matrices as the states in your search, and your "+" operation as the sole operation from states to states.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .