"Charge changing" algorithm

Question

First of all I'm not sure how to name this problem. If anyone have better idea feel free to change it or tell that I do so.

Let's say I have two strings s1, s2 containing '+' and '-', which means positive and negative charge.

s1 is our begin input, s2 is pattern we want to get from s1. Our only operation is that we can change charge into opposite. But when we do so not only chosen charge is being changed but also charges next to one that we choose (left and right, besides first and last character since one of them do not have left and other right).

1. When it's not possible to get from s1 to s2.
2. How to find minimum amount of charge changes to transform from s1 to s2.

I believe the only one is when we have string length of 2 and in total amount '+'(or '-') is odd. For instance

in:"+-"

pattern:"++"

otherwise it's possible, but proof would be appreciated. As point 2 I have no idea, any hints are welcome.

Answer 1

Your intuition for when the problem is solvable isn't quite right. Half of all instances are insoluble whenever n = 2 (mod 3). One way to see this is by doing a few steps of reducing the appropriate system of equations (mod 2). Another way to see that there's some redundancy is to see that flipping the first, fourth, seventh, ... (n-1)st affects exactly the same set of characters as flipping the second, fifth, eight, ... nth.

As for an algorithm for solving these problems: There are two possible choices for the first flip. Once you've decided whether to flip around the first character, the value of the first character tells you whether you need to flip around the second character. Then the value of the second character tells you whether to flip around the third character. And so forth. So just try both possibilities. If neither one works, the problem's insoluble; if one works, report it; if both work, report the one that required fewer flips.