Question

一道程序员面试题，设计，很难

设计一个状态控制机和消息，使得在一端输入这个消息，过一段时间后，所有盒子的灯同时打开。题目背景如下：

有2的N次方的盒子，排成一排，除了首尾外，所有盒子都有左右邻居。
每个盒子都有一盏灯在顶端。
盒子可以给他的左右邻居发消息，可以打开自己的灯（但是不能关闭灯）。
每个盒子拥有一个状态控制机来控制自己的行为（拥有有限个状态）。
每当接受到消息，盒子可以根据目前的状态和消息类型进入一个新状态。
每当进入一个新状态，盒子可以发送消息给左右邻居（可以同时发送），还可以同时打开自己的灯或者选择不开。
所有盒子拥有同样的状态控制器，并且在初始时拥有同样的状态，且灯全部是关着的。

请高手们帮忙。谢谢了。
假设有这个能力吧

Answer 1

状态0：初始状态
状态1：我是端点A
状态2：我可能是端点B
状态3：我是端点B
状态4：我是路人

消息0：初始化消息
消息1：这是来自端点A的消息，我正在寻找端点B
消息2：你的另一边还有我，你不是端点B
消息3：那么谁是端点B呢
消息4：这是来自端点B的消息
消息5：这是来自端点A的消息
消息6，路人请在下一次接到消息5时开灯，端点A请开灯

回馈，将消息发给触发当前消息的一端（谁给我的我就给谁）
转发：将消息发给触发当前消息的另一端（谁给我的我就不给谁）
广播：将消息发给两边（给两边都发送）

收到初始化消息的人将自己置为状态1，并转发消息1，
收到消息1的人将自己置为状态2，并转发消息1，回馈消息2，
收到消息2的人将分为两种：
状态1，不改变状态，并回馈消息3
状态2，将自己置为状态4，不发送消息
收到消息3的人将分为两种：
状态4，不改变状态，转发消息3
状态2，将自己置为状态3，回馈消息4
/*
至此为止，三种角色已经明确，两个端点分别是状态1和状态3，状态4是路人
*/
可能收到消息4的人分为三种：
端点A，回馈消息5
路人，转发消息4
端点B，回馈消息4
收到消息5的人分为两种：
路人，转发消息5
端点B，
/*
当端点B收到消息5的时候，端点B还正在无限发送消息4，端点A正在无限发送消息5，路人正在无限转发消息5和4
*/
此时所有路人都可能收到两种消息，4和5，端点A只会收到4端点B只会收到5
端点A收到消息5则回馈消息4
端点B收到消息4则回馈消息5
路人只负责转发

我已经尽力了，只能做到这个程序，这个是结合网络路由协议设计出来的一种通信机制，但是也只能做到目前的程度，经过我一周零散时间的考虑，想要实现同时开灯，必须在状态里边提供计数器，能给个整数就行，这样就可以通过对信号进行计数来约定时间，否则我真的想不到办法了，以上答案仅仅是一个思路，而且我认为这个题缺乏必要条件，希望对你有帮助。

Answer 2

是不是应该用线程和队列啊？对线程不太了解

Answer 3

先鄙视一下楼主