Suppose you have an unknown cyclic binary sequence of length 4 (1111 or 0000 or 1000 or
Question:
Suppose you have an unknown cyclic binary sequence of length 4 (1111 or 0000 or 1000 or 1110 or 1010 or 1100). It is read cyclically, so the first entry follows the last one in a circle, so for example 1110 = 0111. You have no idea what the sequence is. Your mission is to get to either 0000 or 1111 with as few moves as possible. As soon as one of those is reached, you win (fanfare). If you start with 0000 or 1111, you already won without doing anything. A move is one of: a) flip all bits. b) flip one random bit. c) flip 3 random bits. d) flip two random consecutive bits. e) flip two random non-consecutive bits. So each move is of Hamming distance 1,2,3 or 4 (in one simultaneous step... no flips of the same move are allowed to be performed one by one). After every move, the sequence is rotated cyclically by a random amount, so you don\'t know which bits you modified before (hence the word \'random\'). Obviously, you are never allowed to see what the sequence is, either. Give us the shortest sequence of moves that guarantees that you succeed, no matter what you started with? Hint: Think about what Hamming distances are the most useful for making progress.
Data Structures and Algorithm Analysis in Java
ISBN: 978-0132576277
3rd edition
Authors: Mark A. Weiss