[Logic] Bar man (draft)

During the interview, this question is very interesting:

A bar man put 4 cups in front of you, up or down, then you close your eye, you tell the bar man to reverse one or some cups (left, up, right or down, you can reverse one, or more).

then the bar man will tell you if you have all the cups up or down (you win), if not win, he will route the four cups, left, right, one, or several or not :
ex :
1    2    ------>     41   or 34    or 23    or   12
4    3                   32        21        14           34
 Question : the best strategy to win ?

my think :
first: make a module : sign the up as 0 and down as 1(I did : + and - but I think 0&1 is better as we have only tow situations and -0+can give 3 situations.)

second:  simplify the problem : we do not rote, so just four cups fix.
now we can give all states :    2^4 = 16
10      01     00     00
00      00     10     01

01      10     11     11
11      11     01     10

00      10     11      01
11      10     00      01

01       10
10       01

00    11
00    11

now, try to simplify the states :  

a. you got all 0 or all 1 to win, so we have the half of the states :  (you change 1 to 0 and 0 to 1 you can get all)
10      01     00     00
00      00     10     01

00      10    
11      10    

01     
10   

00
00

b. you you can consider the rotation and we see some states can be the same :
10    
00   

00     
11    

01     
10   

00
00
so, now we have a very simple set of states, now try to think about the result of your option : reverse in every status.
How many transactions : 
a.reverse one cup (in the context of rotation, the absolute position is no more important) 
b. reverse 2 cups (in the context of rotation, the absolute position is no more important, but the relative position should be consider in : )
     ----> 2 cups one side : xx   x0   00   0x
                                           00   x0   xx   0x

     -----> 2 cups in cross :  0x  x0
                                            x0  0x

and then, when you what reverse 3 cups, it dose the same thing as revers one(in the context of all 0 can win and all 1 can win).

now it's very clear to construct an inite-state machine (FSM): 

 the red lines are the path sure, and the black ones are possible paths, now we can try to got the strategy from this graph :


1 the only on path sure to win is tow cross state + 2 cross transaction --> this state is the most simple state.


2 the state one and state two same side is less simple, but we can always try with them and try to know if we are in this state.



so the solution is : i got an unknown state :


try transaction 2 cross :

     ----> win

     ----> not win : I 'm in state "one" or state "tow same side"

             try trasaction "2 same side "

                    -----> win

                    ------> not win : I'm now in state "one" or state "two cross"

                               try transaction 2 cross :

                                      -----> win

                                      ------> not win : I'm in state "one"

                                                 try transaction "1" :

                                                         ------> win

                                                         ------> not win : I 'm in state "two same side" or "two cross"

                                                                    try "2 cross":

                                                                           -----> win

                                                                           ------>not win : I'm in state "two same side"

                                                                                     try "2 same side"

                                                                                            ------>win

                                                                                             ------> not win : I 'm in"two cross"

                                                                                                         try "2 cross":

                                                                                                          -----> win

so this is the strategy.


When I asked Botu this question, he gave another thought :

 state can be presented by :

0000 1000 1100 1010

then we can construct a tree to let this problem "inverse": from result :


0000

|            \                      \

1000        1100           1010

|        \       |         \          |      \

....

use this tree to cover all possible start states.


I still think the   inite-state machine       is more suitable for this problem, but the thought of tree is very interesting too, but I have non idea how he will use this tree,and I will finish this part when he tell me his solution.