Hacker News Reader

Let F be the only person who is permitted to turn the light oFF. The N be every body else---they will be turning the lights oN.

F starts with a counter at 0. If the light is on when F gets to the room, they turn the light off, and they increment their counter. If the light is off when F gets to the room, do nothing.

Each N starts with a counter at 2. When any N enters the room, if the light is on, do nothing, but if their counter is more than 0 and the light is off, turn it on and decrement their counter.

If the light starts on, F will turn it off once, putting their counter at 1. Then, if their counter gets to 198 = 1 + 197, they will know all 99 N people has been in the room once, (and will be certain all but one have been twice).

If the light starts off, some N will turn it on. F's counter gets to 198 when everybody else has been in the room at least twice.

If any prisoner is queried, they should answer "I don't know" unless they are F and their counter is at 198.

That's way more than one bit of state!

Sure, but the extra is all local state. It still only uses one bit of shared state.

This is indeed the standard solution. There is also a more difficult version: Every prisoner is required to have the same strategy (so you cannot pick a unique person F). (Every thread runs the same program, and threads do not have access to a unique thread identifier.)

Ugh. This gives me a headache.

I'll just solve this assuming the light starts off, because otherwise I have a feeling it will get miserable to think through.

Every prisoner starts at c=1. If light is on, turn it off and decrement c. If the light is off, turn it on and increment c. It c hits 0, always do nothing. If c=101, everyone has been to the room.

Everyone wants to turn off 1 more light than they turn on, but that means one person has to turn on the light 99 more times than they turn it off (and then they have to see it off, indicating the 99th person has reached c=0, and turn it on for themself to reach c=101).

Edit: Thinking back through, I think just starting at c=2 and waiting for c=200 works for an uncertain initial state of the light.

Edit 2: One of the problems with this method is that you are essentially waiting for the nature of random distributions to select people unevenly to get people to hit c=0 and be "removed". At higher average c (excluding 0s), this may take a while. It can probably be made faster by having a chance to not turn on the light at low c and not turn off the light at high c, but I wouldn't be surprised if that doesn't actually end up being faster. At the very minimum a prisoner could stop lowering c once it got above the 50% mark.

Very nice solution.

I wonder if it can be made not rely on randomness at all. The 'standard' solution just required that every prisoner would be taken to the room infinitely many times. As long as this was the case, the warden could try any devious sequence they liked.

Interesting question. Haven't solved it yet, but it did give me an idea for an optimization.

If the prisoner stores c_max, they can decide to only ever turn off the light (until c=0) if c < c_max - 1.

This is because there is at least 1 other prisoner still turning on the light (they could turn off the light they turned on to reach c = c_max - 1, but only get lower if someone else turns on the light for them).

Unfortunately an adversarial sequence still hangs progress, as prisoners can be juggled between c_max and c_max-1.

> If the light is on when F gets to the room, they turn the light off, and they increment their counter.

Who is they???

https://en.wikipedia.org/wiki/Singular_they

Good grief. If you want to write objective, do so, and ommit personal pronouns all together, but don't employ this archaic, confusing grammatical quirk. I'd like to point out to you, ekke's comment was much better understandable and shorter.

Edit: Did you even read what you linked?

> One explanation given for some uses of they referring to a singular antecedent is notional agreement, when the antecedent is seen as semantically plural

F was definitely singular.

> Distributive constructions apply a single idea to multiple members of a group. They are typically marked in English by words like each, every and any.

That is indeed something I often wondered about, sadly that part is inconclusive.

> Referential and non-referential anaphors

I didn't even try to read. That looks like it should be it's own article.

> On the other hand, when the pronoun they was used to refer to known individuals ("referential antecedents, for which the gender was presumably known", e.g my nurse, that truck driver, a runner I knew), reading was slowed when compared with use of a gendered pronoun consistent with the "stereotypic gender" (e.g. he for a specific truck driver).

You might ommit personal pronouns, as I said, or use 'it' on the object of the sentence using passive verbs.

You seem to be very angry with a feature of English grammar. Using they/them/their is a perfectly reasonable, consistent and well-understood way to refer in the third person to someone of unknown gender.

How would you rewrite the sentence "If the light is on when F gets to the room, they turn the light off, and they increment their counter." without using they?

I am not angry with a feature of the language. I am angry with the people abusing a bug, for lack of a better word, that makes a simple language overly complicated. I am angry, because I didn't understand the whole comment. In my opinion that is not just my fault. It was, in many ways, terribly written. I think a little meta discussion is beneficial. Seeing that it is a question of logic and we are in a logic puzzle thread, I think, you should try to answer your question yourself.

> consistent

If that was a consistent feature, or better to say regular, there would be the -s inflexion on the verb, that the singular third person requires.

> well-understood

What does that even mean? In the referred article, were, as I said, at least two counts against the particular usage in the GP.

> How would you ...

What does it matter? Are you saying there is no other way? Why don't you give it a try yourself, it's not hard. For starters, just try replacing "they" with "F".

>What does it matter? Are you saying there is no other way? Why don't you give it a try yourself, it's not hard. For starters, just try replacing "they" with "F".

Lol. It does matter because you are bitching about using they when you don't even say what on earth are we supposed to say instead.

Replace they with the name? "If the light is on when Franklin gets to the room, Franklin turns the light off, and Franklin increments his or her counter." Yeah sounds perfectly natural. Pronouns are for losers.

So, my personal ability to rephrase the sentence is attacked, the pretense that there would be no alternatives is kept and my idea is dismissed as petty. That's just as expected.

Note that the above sentence is written in the objective way that I mentioned before. There is no way a third person singular gendered pronoun could creep in there, even if I was talking about you in the third person.

Unless Franklin was a transfinite gender fluid with multiple personalities, the use of they would be wrong there, according to the article you linked.

Yes, your alternative of simply repeating the noun several times instead of using a pronoun, which you avoid using because you feel its gender neutrality is a tool of the "transfinite gender fluid sjw brigade", despite being in use for 600 years now, is a petty solution indeed.

The first sentence of my last comment was what I had called objective. All the while, going by the repeated mentioning of me, ie. "you", the answer I got seemed much more focused on me. Well, I'm very egoistic, going by my mentioning myself so often here, so I'm flattered by your attention, but I suppose you are missing the point.

Nice talking to you, thanks for the link.

Although you allege ekke's comment was "much better understandable", it commits the same use of they as singular.

> Others follow a simple pattern - if the light is off, and they have never turned it on yet, turn it on. If it is already on, or they have already ever turned it on, do nothing.

"They" cannot possibly be referring to the group---"they" is referring to each person individually. If it's referring to the others as a group, it's not a solution to the puzzle.

And yet, you found it understandable.

"Others" is not singular. "they" is a reference to individuals out of a group. "they each" is a common disambiguation, but it doesn't actually matter who turns the light on. The generic he was also used, anyway. This "they" is commonly used to refer to groups of only males, too, and has nothing to do with gendering.

In contrast, F was really singular.

Why does each person need to enter the room twice? F is allowed to turn the light off, each other person can only turn the light on ONCE. Every time F enters and the light is ON he turns it off and increments his counter. When F's count gets to 100 they go free (99 turned it on ONCE and there was at most one false positive) and, obviously, F has entered at least 100 times.

If the initial state of the light is known to F then you only need once per person.

However if the initial state of the light is unknown to F then your proposal would deadlock at 99 wherever the light starts off, because it will only ever be turned on 99 times, so 100 will never be reached.

The twice entry solution avoids this issue because if the light starts on then the most that 98 people will turn it on is 196 times, for a total of 197 "on" count, with 198 guaranteeing 99 people involved, but if the light starts off the 99 people will turn it on 198 times as well.

The 198 solution has the same problem. F cannot tell if the light is on because it was originally on, or G preceded F and the light started off. You're always going to be susceptible to off-by-one errors.

Good one!

A naive strategy where they never die, and hopefully stay in prison for slightly less than a few billion years:

One prisoner is the light-counter (Mr C). Others follow a simple pattern - if the light is off, and they have never turned it on yet, turn it on. If it is already on, or they have already ever turned it on, do nothing.

Mr C enters the room, if the light is on, remembers it, and turns it off.

When Mr C has entered the room 99 times with light on, he can say 'Yes' and they are safe.

This can be optimized. How?

You have to be careful, because if the light starts out on, Mr C could be fooled when only 98 other people have entered the room.

This is essentially the same solution I came up with. I'm not sure it needs to be optimized assuming we can set the starting state and the strategy for every prisoner.

Here's a much harder variation. There are three changes:

(1) No prisoner is distinguishable from any other. In other words, they must all have the same strategy.

(2) The prisoners are all given coins, so that they can make random decisions.

(3) The goal is now to find a strategy that will eventually halt with probability 1 (in other words, how long it takes can depend on the coin flips, but any run that takes infinite time must happen only with probability 0). However, the prisoners are not allowed to take chances when answering "yes"; they can only say "yes" if they are certain that every prisoner has visited the room.

It has a very elegant solution.

>The "easiest" solution would simply be to wait a few billion years

Actually that is incorrect as there is no guarantee that every prisoner has been in the room at least once over any amount of time. Of course the probability will get higher and higher that everyone was in the room once if it was completely random but that probability will never be 100%.

I know of two legitimate answers to this problem, it took me awhile when I first heard it.

>Actually that is incorrect as there is no guarantee that every prisoner has been in the room at least once over any amount of time.

IIRC, in the original statement of the problem, there's also a stipulation that, for all prisoners, the king/chooser/whatever will visit them an infinite number of times (so at any time it must be true that each prisoner will be visited [again or for the first time] if the game doesn't terminate).

So? It doesn't have to be true that each prisoner will be visited within any particular time frame.

The solution only requires that they will eventually be visited; you can keep deferring until they are. There's no specific time frame in which you have to make a guess.

> There's no specific time frame in which you have to make a guess

This is correct.

> The solution only requires that they will eventually be visited; you can keep deferring until they are.

This is false; you can't "keep deferring until everyone is visited" because you have no way of assessing whether that's happened. As a strategy, it is impossible to implement.

Yes, you can: the designated prisoner waits until the signal has been fipped n+k times where n is the number of prisoners and k is the number of times the guard can intervene. All other prisoners flip it to that state if it isn't already. See the other replies.

That is a completely different strategy than "if we wait long enough, it's bound to work". Waiting is worthless, no matter how long you wait.

But under the corrected assumption about the problem, you can reliably know when it is safe to say that all prisoners have been in the room and when you should keep deferring. In the other version of the problem, I agree there's no such guarantee; hence why I bought up the difference.

I think dsugarman meant "at least once over any FINITE amount of time", in which case each prisoner might visit again an infinite number of times, but it can be arbitrarily many turns in the future.

So, if you wait a finite amount of time (in this case a "few" billion years") it's possible that the visiting condition might not yet be satisfied.

True. I alluded to that further down, as even with the perfect strategy this means that "it is theoretically possible that the goal state never happens", i.e. the probability that the algorithm will terminate will never be 100% (but it terminates with probability 1).