The first important observation is that the order of bowl flipping is irrelevent, and as a corollary there is no point in doing the same flip twice (since the effect cancels out). Thus, since there are 20 flips, only 220 possibilities exist.
From here there are a number of possible approaches.
One approach is to try to solve directly for whether each triplet is flipped or not. At first this seems problematic, since there is no place to start. However, if you take a "guess" for the left-most pair, then everything else follows (since the left-most bowl can only be flipped again in one way, then the bowl next to it can only be flipped in one way and so on). Rather than guessing, you can solve the problem for both possibilities, then take the lower of the two values. You also have to consider that in one of the cases there may be no solution (although it is possible to prove that for 20 bowls it is either possible in both cases or possible in neither). See Kolstad's approach below.
A lazier approach is to consider every possible combination of flips, of which there are 220. This will be fast enough provided that the inner loop is quite efficient. The best method is to use the bits of an integer to represent flips. You can then loop that integer from 0 to 2^20-1, which will loop over all possible sets of flips. It is also possible to convert a set of flips to a set of flipped bowls using some binary operators:
flipped = ((flips << 1) ^ (flips) ^ (flips >> 1)) & 0xfffffThis makes the each iteration constant-time, which is more than fast enough, with only a million loop counts. For each set of flipped bowls that matches the set of initially inverted bowls, count the number of bits and take the lowest (the bitcounting is non-constant time, but from the previous algorithm we can see that it only occurs twice in total).
Initially, I implemented a full breadth first search with collision detection. This is way too complex for this problem, as Bruce's analysis suggests. A different approach can lead to an unbelievably fast solution that is only a bit more difficult to code.
Ignoring the upper 'two bowl' flip at the left end of the bowl list for a moment, one can easily believe that whatever highest bit is turned on must be flipped in order for the entire list to end up 0. Obviously, if you don't flip it, you won't get to a solution!
So, find that bit, and flip it along with the two bowls to its right. Now the highest bit is further to the right. Iterate this process until either all bowls are flipped to '0' (success!) or only the bottom bit is '1' (failure). The small number of bowls makes this run very quickly. It's not clear to me how to prove that this is guaranteed to get the proper final answer, by the way.
To see if the high-end two-bowl flip is better, just flip those top two bits and iterate as before, but starting the flip count at 1 instead of 0. This solution (inspired somewhat by Russ Cox and Mathijs Vogelzang) is shown below.
/* Quick find-the-top-bit-and-flip solution */
#include <stdio.h>
#define MASK (0xFFFFF << 1)
count (bowl, n, nflips) {
if ( (bowl&MASK) == 0) return nflips;
if (n == 1) return 99999;
if (bowl & (1 << n)) /* then flip and recursively count */
return count (bowl ^ (7 << (n-2)), n-1, nflips+1);
return count (bowl, n-1, nflips);
}
int main() {
int i, bit, bowl = 0, a, b;
FILE *fin = fopen ("bowls.in", "r");
FILE *fout = fopen ("bowls.out", "w");
for (i = 0; i < 20; i++) {
fscanf (fin, "%d", &bit);
bowl = (bowl << 1) | bit;
}
bowl = bowl << 1;
a = count (bowl ^ (3<<19), 20, 1);
b = count (bowl , 20, 0);
fprintf (fout, "%d\n", a < b ? a : b);
exit (0);
}