Ten users, three lights but it's a chatroom

Question

This is a variant of the classic problem of m prisoners n lights. (Example may be found here but note that the requirements are not exactly the same)

The goal for you, however, is different. You want to challenge the system and overcome the restriction on communication, and talk to your fellow users with the lights as a medium. It might even relieve some of your loneliness.

---

One day, 10 puzzling.SE users, including you, find yourselves in a horrible prison.

A supervisor shows up and tells you about a game that you have to follow. For now, you may communicate freely and devise a plan. After the game begins, however, you will each work in isolation.

There is a room with 3 lights with switches. In random, each of you will be taken into the room. When inside, you will be able to see the state of the 3 lights, and you will be able to turn on/off the lights at will.

The original goal of the game is not important for now. The thing is, you want to still be able to communicate freely during the game. So you want to set up a chatroom, in which arbitrary conversation can take place, just using the lights.

Can you devise a protocol for this?

---

Details:

A chatroom means anyone can broadcast an arbitrary message in a string of bits, and anyone may broadcast a reply to that first message, and anyone may reply to the second message, and so on. This means everyone's message is not pre-determined and may depend on what other people send.

You will only need to create a 'hardware-level' protocol; it just needs to be clear that the chatroom can be built on top of it. Master-slave architecture? decentralized architecture? You decide.

Each of you may follow a different plan.

The initial state of the lights is unknown. The 3 lights have no state other than on and off.

The 3 lights are your only medium of communication, and it's not possible to see them from outside. This basically means only one will be able to receive and send information at a time.

Each person will be taken inside multiple times. You will keep getting taken inside.

It is impossible to know, between two entries, whether anyone else has entered, or how many has entered.

'Random' means picking one uniformly randomly each time. However, a plan that fails sometimes, even with arbitrary low probability, is not acceptable. Your goal is to keep the chatroom, and allow each finitely long conversation to be done in finite time, with probability 1.

---

Extra credit:

• Does your plan work for arbitrarily many people? (It may be easier to work on this extra credit than the original; I'm not sure.)
• Can you make do with only 2 lights?

---

I already know the solution to the above, including the extra credits. So it's possible. Challenge for you.

---

It may be helpful to write a program to check for possible off-by-one errors and the like. Generators in, for example, Python and JavaScript are your friend.

Answer 1

This is my shot at a two light solution:

The prisoners can presumably agree ahead of time on some way of distinguishing the two lights. We thus have four possible states for the switches to be in, which we will note as follows:

• Off Off: null
• Off On: 0
• On Off: 1
• On On: _

We give the n prisoners an order $p_1, p_2 ... p_n$.

We know the solution for figuring out if everyone has seen a message with a single light switch, where one person, the counter, turns on the light every time they're in the room and increments the count every time they see it off, and everyone else turns it off the first time they see it on so as to increase the count by exactly one.

Using two switches, one person can then encode messages by setting the switches at different non-null states, keeping the same state until they know everyone has seen that state, then changing the state.

This leaves two problems unresolved:

1. How do people distinguish between e.g 0 and 00?
2. How do we let multiple people send messages?

The _ state is the key to this. The algorithm goes as follows:

To transmit a single character X the sender (Alice) takes the role of the counter in the single switch problem. She places the switches in state X, and everyone else sets it to null exactly the first time they see that the switches are in state X. Once Alice notices she has had to flip the state back from null to X exactly n-1 times, she can be sure that everyone has seen X.

Now, the next character she sends has to be different from X, so that everyone else knows that a new character is being sent, rather than the old one still being in the process of being sent. This can be achieved by alternating bits and _, so for instance if Alice wanted to send the information 0110, she would have to send _0_1_1_0.

After Alice has finished her message, she sends a predetermined signoff (say, 0_0_0_0), to indicate to the next prisoner (Bob) that it is their turn to transmit a message. After seeing that everyone has noticed the final 0, Alice sets the state to 1 to indicate to Bob that everyone has seen the signoff. Once Bob has seen the 1, he flips it to _ and takes control of transmitting and counting.

Everyone just passes the transmitter off in a predetermined order $p_i$ to $p_{i+1}$, with $p_n$ passing it back to $p_1$. Certainly now that everyone can send binary by just waiting their turn, a chatroom can be built off of that.

The very first character of the very first message is special, since the initial state is unknown. To account for this, everyone agrees that $p_1$ will begin their message with a _, and everyone will switch the state to null the first two times that they see a _. $p_1$ checks that the switch has been flipped $2(n-1)-1$ times, after which everyone must have seen the _ at least once. This number will still be reached even if the lights both started on.

I will admit that I had seen the original prisoner-lightbulb puzzle before and I think I read the solution to it, so I didn't come up with that part myself, but I thought of the rest on my own. This is also my first puzzle answer on this site so I apologize if I didn't follow the proper spoiler etiquette.

Answer 2

I'm going to say:

This is impossible

Because:

Even if you manage to come up with a messaging protocol that works with only 3 bits of info (3 lights). Since you have to "broadcast" each message (everyone must recieve all messages) there is no way to be (100%) sure that each person has recieved the message as they are taken in randomly.

Answer 3

In order to solve this, you need to do two things: transcode a message and check that everyone received this message.

Transcoding the message

We can use two bulbs for this and simply implement an I2C protocol over these bulbs where one bulb is the clock line and one is the data line. The first person to seize the bus by pulling the clock line is the master until they send the escape character that ends communication, freeing up the line. This brings about one extra problem: the two bulbs have to be in a known state for I2C to start (because signalling is started by pulling the clock line to the non-default position). This can be solved by checking that everyone has entered the room before the first master seizes the bus the first time.

Check that everyone received the message

This is the same as checking that everyone has entered the room during each state of the transcoding of the message (as well as at the start). In order to do this, have the current master be the counter in the solution to the standard lightbulb-prisoner problem. In order to do it at the start, decide on one starting master (during the initial coordination) and have them be the counter, when they know that everyone has entered the room, they can start communicating and announce that the chatroom is opened. The communication works because they're sure that everyone has seen the room's communication wires initial states, so they would see a change in that state.

Extra credit:

• The plan works for every group size, as long as the size is known during coordination
• I believe you can make it work using two wires by having something like a heavily adapted simplex UART lane, but I'm not sure how. If I ever think of a solution, I'll edit it in.

Answer 4

Now that someone already had the answer, I thought it could be appropriate to post my original solution code here. A brief explanation:

(Light states are described as 2 binary digits like 01 for light one off, light two on.)
This solution is not essentially different to the one given by a.g.g. The major differences, stated relative to that answer, are:
1. The initial 'syncing' round is different. Since we have three states at our disposal, we could let the others signal their first sight and second sight of the _ state with two different acknowledgement states. Specifically, the first time we put it into 00, and the second time, 11. Then we only need to count the 'second acknowledgements'
2. Everyone, in their turn, simply sends a _, sends the bit, and asks the next one take control. The signal for the next one to take control is the opposite bit. For example, if I send 1, then making that 0 means I'm ready for the next to take over.
3. State 00 is null, 01 is _, and 10 11 are states 0 1 respectively. Guess that's a bit easier on the code?

import random

num_actors = 5
max_steps = 2000
random.seed(12345)
logging = True

state = random.choice(['00', '01', '10', '11'])
step = 0

sent = ['' for i in range(num_actors)]
recv = [['' for j in range(num_actors)] for i in range(num_actors)]

def log_sent(src, bit):
    sent[src] += str(bit)

def log_recv(src, dest, bit):
    recv[dest][src] += str(bit)

def actor(me):
    global state, step

    def log(str):
        if logging:
            print('{:6} | {:3}: {}'.format(step, me, str))

    def next_actor(x):
        return (x + 1) % num_actors

    def wait_ack(msg, ack):
        global state
        state = msg
        count = 1
        while count < num_actors:
            yield
            if state == ack:
                count += 1
            state = msg

    def wait_until(target):
        if type(target) == str:
            target = [target]
        while state not in target:
            yield

    def sync_host():
        log('+ sync: begin counting')
        yield from wait_ack(msg = '10', ack = '11')
        log('+ sync: master done')

    def sync_guest():
        global state

        yield from wait_until(['10', '01'])
        state = '00'
        log('  sync: first ack')

        yield from wait_until('10')
        state = '11'
        log('  sync: second ack')

    def sender():
        global state

        state = '01'
        yield from wait_ack(msg = '01', ack = '00')

        log('+ takeover: done')

        bit = random.choice([0, 1])
        log('+ send: sending {}'.format(bit))

        msg = '1' + str(bit)
        yield from wait_ack(msg = msg, ack = '00')
        log('+ send: done')
        log_sent(src = me, bit = bit)

        state = '1' + str(1 - bit)

    def receiver():
        global state

        yield from wait_until('01')
        state = '00'
        log('  takeover: ack')

        yield from wait_until(['10', '11'])

        bit = int(state[1])

        log('  recv: ack, bit {} from {}'.format(bit, current))
        log_recv(src = current, dest = me, bit = bit)

        state = '00'
        yield

        if me == next_actor(current):
            neg_msg = '1' + str(1 - bit)
            yield from wait_until(neg_msg)

            log('+ taking over transmission')

    if me == 0:
        yield from sync_host()
    else:
        yield from sync_guest()

    current = 0

    while True:
        if me == current:
            yield from sender()
        else:
            yield from receiver()

        current = next_actor(current)


actors = [actor(i) for i in range(num_actors)]

for i in range(max_steps):
    step = i
    last_state = state
    actor_num = random.randrange(num_actors)
    next(actors[actor_num])

print('')
print('Transmission check')
print('')

for src in range(num_actors):
    src_sent = sent[src]
    print('{:3}|       {}'.format(src, src_sent))
    for dest in range(num_actors):
        if src != dest:
            dest_recv = recv[dest][src]

            ok = '(Ok!)' if dest_recv[:len(src_sent)] == src_sent else '(Not ok!)'
            print('    > {:3}: {} {}'.format(dest, dest_recv, ok))
    print('')

total_bits = sum(map(len, sent))

print('Transmission statistics:')
print('    {} actors, {} bits, {} steps'.format(num_actors, total_bits, max_steps))
print('    {} bits per 1k steps'.format(1000 * total_bits / max_steps))