Consider the following "game".
There is an ant on a strip of length N. The ant can perform the following actions: move left, move right, and paint the cell he is on with white or black. The ant is also given a target coloring and must paint the strip according to such coloring in the most efficient way possible. The ant has two brushes, one for each color, and swapping the brushes has a cost.
More formally, we can define the game as follows: Let $S_N$ be the set of permutations of $\{1,..., N\}$ and $f:\{1,...N\} \to \{\text{white}, \text{black}\}$ be the target coloring for the strip. We want to find the permutation $\sigma \in S_N$ that minimizes this function: $$ \text{cost}(\sigma) = \sum_{i=1}^{N-1} M \cdot |\sigma_i - \sigma_{i+1}| + C \cdot \Bbb 1_{f(\sigma_i) \ne f(\sigma_{i+1})} $$ Where $M, C \in \mathbb N_{>0}$ are the costs of moving and swapping the color brushes respectively.
Can this problem be solved efficiently? Has this problem, or some variant similar to this been studied in the literature somewhere?
Edit: Not sure if this helps but we can formulate the task as a quadratic minimization program like this:
$$ \text{cost} = \sum_{i=1}^N\sum_{i' = 1}^N\sum_{j=1}^{N-1} x_{i,j} \cdot x_{i', j+1} \big(M \cdot |i - i'|+ C \cdot 1_{f(i) \ne f(i')}\big) $$ subject to $$ \sum_{j=1}^N x_{i,j} = 1, \; \; i = 1, \ldots, N $$ $$ x_{i,j} \in \{0, 1\}, \; \; i,j = 1,\ldots, N $$ This can be simplified to $$ \text{cost} = \|Q\vec w\|_1 $$ where $$ \phi:\{1,...,N^2\} \to \{1,...,N\} \times \{1,...,N\}$$ $$ i \mapsto \big( \phi_1(i), \phi_2(i) \big) $$ is some bijective function and $$ Q \in \Bbb \{0,1\}^{(N - 1) \times N^2} $$ $$ Q_{i,j} = x_{\phi_1(j), i} \cdot x_{\phi_2(j), i+1} $$ $$ \vec w \in \Bbb N^{N^2} $$ $$ \vec w_i = M \cdot |\phi_1(i) - \phi_2(i)| + C \cdot 1_{f\big(\phi_1(i)\big) \ne f\big(\phi_2(i)\big)} $$
Second edit: We can also frame this as a problem in Graph Theory. For an instance $I$ of the ant problem we define an edge weighted undirected graph $G = (V, E, W)$ where $V$ contains two copies of $1, ... ,N$ (one for black colored cells and one for white colored) cells. Further, for all $i$ there is an edge with weight $M$ to $i+1$, and an edge from each $v$ to its copy with weight $C$. I.e. $$ V = \{1_{\text{white}}, ..., N_{\text{white}}\} \cup \{1_{\text{black}}, ..., N_{\text{black}}\} $$
$$E = E_1 \cup E_2 \cup E_3$$ where $$ E_1 = \{ \{i_{\text{white}}, j_{\text{white}} \}: j = i+1, 1 \le j \le N\} $$ $$ E_2 = \{ \{i_{\text{black}}, j_{\text{black}} \}: j = i+1, 1 \le j \le N\} $$ $$ E_3 = \{\{i_{\text{white}}, i_{\text{black}}\}: 1 \le i \le N \} $$ $$ W(e) = \begin{cases} M & e \in E_1 \cup E_2 \\ C & e \in E_3 \end{cases} $$ We now define $\text{goal}(I) = \{ i_c : 1 \le i \le N, c = f(i) \}$ as the cells in the strip that must be visited. The minimum of $\text{cost}(\sigma)$ corresponds to a path $\pi$ in $G$ of minimal cost that visits each $v \in \text{goal}(I)$.
