用3盏灯实现群聊 —— 一道趣味题和一个协议设计

这是题目:

10个人不能见面,只靠3盏灯来交换信息,如何协调配合呢?
不可思议的是,只要3盏灯,10个人就可以拉个群一起聊天了 —— 没错,互相发送文字,没有长度限制,只要把文字编码到这3盏灯的状态,再配合上一个正确的通信协议。

来看一段聊天记录吧:

这是Python实现:


#!/usr/bin/env python
import time
import random
import binascii

STEPS = 0

wire = [random.randint(0, 1), random.randint(0, 1), random.randint(0, 1)]
SLAVE_COUNT = 9

data = [None] * (SLAVE_COUNT + 1)
data[0] = dict()
data[0]["initialized"] = 0
data[0]["mode"] = 0
data[0]["last_read"] = 0
data[0]["direction"] = 0
data[0]["direction_initialized"] = 0
data[0]["send_buffer"] = ""
data[0]["recv_buffer"] = ""

for i in range(1, SLAVE_COUNT + 1):
    data[i] = dict()
    data[i]["initialized"] = 0
    data[i]["mode"] = 0
    data[i]["last_clock"] = 0
    data[i]["last_read"] = 0
    data[i]["direction"] = 0
    data[i]["direction_initialized"] = 0
    data[i]["send_buffer"] = ""
    data[i]["recv_buffer"] = ""

def str2bin(str):
    temp_str = bin(int(binascii.hexlify(str), 16))[2:]
    return temp_str

def bin2str(bin):
    return binascii.unhexlify('%x' % int(bin, 2))

def writeWire(id, value):
    wire[id] = value;

def readWire(id):
    return wire[id];

def flipWire(id):
    wire[id] = not wire[id]

def node(id):
    if id == 0:
        master()
    elif id > 0:
        slave(id)

def master():
    global STEPS
    if data[0]["mode"] == 0:
        if data[0]["initialized"] == 0:
            writeWire(2, 0)
            data[0]["initialized"] = 1
        else:
            if readWire(2) == 1:
                data[0]["mode"] = 1
                writeWire(0, 0)
                data[0]["send_buffer"] = str2bin("Hello, I'm master") + '00000000'
                # print("SEND: " + data[0]["send_buffer"])
                data[0]["recv_buffer"] = ""
                print("#" + str(STEPS) + " master connected")
        flipWire(0)
    elif data[0]["mode"] == 1:
        if data[0]["direction_initialized"] == 0:
            if readWire(1) == 0:
                writeWire(1, 1)
                data[0]["direction"] = 1
            else:
                data[0]["direction"] = 0
            data[0]["direction_initialized"] = 1
            writeWire(0, 1)
            print("#" + str(STEPS) + " master direction " + str(data[0]["direction"]))
        else:
            if data[0]["direction"] == 1:
                if readWire(0) == 0:
                    if len(data[0]["send_buffer"]):
                        send_data = int(data[0]["send_buffer"][0])
                        data[0]["send_buffer"] = data[0]["send_buffer"][1:]
                        writeWire(1, send_data)
                        writeWire(0, 1)
                        #print("#" + str(STEPS) + " master send " + str(send_data))
                    else:
                        data[0]["mode"] = 0
                        data[0]["direction_initialized"] = 0
                        writeWire(2, 0)
                        print("#" + str(STEPS) + " master disconnected")
            else:
                if readWire(0) == 1:
                    recv_data = readWire(1)
                    #print("#" + str(STEPS) + " master received " + str(recv_data))
                    data[0]["recv_buffer"] = data[0]["recv_buffer"] + str(recv_data)
                    writeWire(0, 0)
                    if len(data[0]["recv_buffer"]) % 8 == 0:
                        if data[0]["recv_buffer"][-1] == "0" and data[0]["recv_buffer"][-2] == "0" and\
                            data[0]["recv_buffer"][-3] == "0" and data[0]["recv_buffer"][-4] == "0" and\
                            data[0]["recv_buffer"][-5] == "0" and data[0]["recv_buffer"][-6] == "0" and\
                            data[0]["recv_buffer"][-7] == "0" and data[0]["recv_buffer"][-8] == "0":
                            # print("RECV: " + data[0]["recv_buffer"])
                            print("#" + str(STEPS) + " master received " + bin2str(data[0]["recv_buffer"][1:-8]))
                            print("#" + str(STEPS) + " master disconnected")
                            data[0]["mode"] = 0
                            data[0]["direction_initialized"] = 0
                            writeWire(2, 0)

def slave(id):
    global STEPS
    if data[id]["mode"] == 0:
        if data[id]["initialized"] == 0:
            data[id]["initialized"] = 1
            data[id]["last_clock"] = readWire(0)
        else:
            if readWire(0) != data[id]["last_clock"]:
                if readWire(2) == 0:
                    writeWire(2, 1)
                    data[id]["mode"] = 1
                    writeWire(1, 0)
                    writeWire(0, 0)
                    data[id]["send_buffer"] = str2bin("Hello, I'm slave " + str(id)) + '00000000'
                    # print("SEND: " + data[id]["send_buffer"])
                    data[id]["recv_buffer"] = ""
                    print("#" + str(STEPS) + " slave " + str(id) + " connected")
                data[id]["last_clock"] = readWire(0)
    elif data[id]["mode"] == 1:
        if data[id]["direction_initialized"] == 0:
            if readWire(1) == 0:
                writeWire(1, 1)
                data[id]["direction"] = 1
            else:
                data[id]["direction"] = 0
            data[id]["direction_initialized"] = 1
            writeWire(0, 1)
            print("#" + str(STEPS) + " slave " + str(id) + " direction " + str(data[id]["direction"]))
        else:
            if data[id]["direction"] == 1:
                if readWire(0) == 0:
                    if len(data[id]["send_buffer"]):
                        send_data = int(data[id]["send_buffer"][0])
                        data[id]["send_buffer"] = data[id]["send_buffer"][1:]
                        writeWire(1, send_data)
                        writeWire(0, 1)
                        #print("#" + str(STEPS) + " slave " + str(id) + " sent " + str(send_data))
                    else:
                        data[id]["mode"] = 0
                        data[id]["direction_initialized"] = 0
                        data[id]["initialized"] = 0
                        print("#" + str(STEPS) + " slave " + str(id) + " disconnected")
            else:
                if readWire(0) == 1:
                    recv_data = readWire(1)
                    data[id]["recv_buffer"] = data[id]["recv_buffer"] + str(recv_data)
                    #print("#" + str(STEPS) + " slave " + str(id) + " received " + str(recv_data))
                    writeWire(0, 0)
                    if len(data[id]["recv_buffer"]) % 8 == 0:
                        if data[id]["recv_buffer"][-1] == "0" and data[id]["recv_buffer"][-2] == "0" and\
                            data[id]["recv_buffer"][-3] == "0" and data[id]["recv_buffer"][-4] == "0" and\
                            data[id]["recv_buffer"][-5] == "0" and data[id]["recv_buffer"][-6] == "0" and\
                            data[id]["recv_buffer"][-7] == "0" and data[id]["recv_buffer"][-8] == "0":
                            # print("RECV: " + data[id]["recv_buffer"])
                            print("#" + str(STEPS) + " slave " + str(id) + " received " + bin2str(data[id]["recv_buffer"][1:-8]))
                            print("#" + str(STEPS) + " slave " + str(id) + " disconnected")
                            data[id]["mode"] = 0
                            data[id]["direction_initialized"] = 0
                            data[id]["initialized"] = 0

while True:
    node(random.randint(0, SLAVE_COUNT))
    STEPS += 1
    if STEPS == 100000:
        break
    #time.sleep(0.1)

 

对这个通信协议做一点简单说明:

这是一个区分服务器/客户端的协议,服务器为代码中的master,客户端为代码中的slave。

服务器的两个状态:监听状态和通信状态

客户端的两个状态:尝试连接状态和通信状态

三盏灯的定义:

在监听/尝试连接状态下,为(1) 时钟信号; (2) <未使用>;(3) 连接状态指示信号

在通信状态下,为(1) 同步(ACK)信号;(2) 数据信号;(3) 连接状态指示信号