News for hackers. Stuff that matters.
Re:Seven Puzzles You Think You Must Not Have Heard Correctly... by evanb on Monday August 29, 2016 @01:07PM (#12383307)
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.

Re:Seven Puzzles You Think You Must Not Have Heard Correctly... by rntz on Monday August 29, 2016 @01:47PM (#12383667)
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.)
Re:Seven Puzzles You Think You Must Not Have Heard Correctly... by jon_richards on Monday August 29, 2016 @02:37PM (#12384108)
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.

Re:Seven Puzzles You Think You Must Not Have Heard Correctly... by thomasahle on Tuesday August 30, 2016 @08:36AM (#12389407)
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.

Re:Seven Puzzles You Think You Must Not Have Heard Correctly... by jon_richards on Wednesday August 31, 2016 @10:04AM (#12398347)
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.

Re:Seven Puzzles You Think You Must Not Have Heard Correctly... by evanb on Monday August 29, 2016 @02:05PM (#12383807)
Ugh. This gives me a headache.
Re:Seven Puzzles You Think You Must Not Have Heard Correctly... by Tloewald on Monday August 29, 2016 @07:25PM (#12386235)
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.
Re:Seven Puzzles You Think You Must Not Have Heard Correctly... by aiiane on Monday August 29, 2016 @08:02PM (#12386407)
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.

Re:Seven Puzzles You Think You Must Not Have Heard Correctly... by Tloewald on Tuesday August 30, 2016 @02:02PM (#12392361)
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.
Re:Seven Puzzles You Think You Must Not Have Heard Correctly... by TylerE on Monday August 29, 2016 @01:15PM (#12383368)
That's way more than one bit of state!
Re:Seven Puzzles You Think You Must Not Have Heard Correctly... by kd0amg on Monday August 29, 2016 @01:29PM (#12383529)
Sure, but the extra is all local state. It still only uses one bit of shared state.
Re:Seven Puzzles You Think You Must Not Have Heard Correctly... by posterboy on Monday August 29, 2016 @03:38PM (#12384623)
> If the light is on when F gets to the room, they turn the light off, and they increment their counter.

Who is they???

Re:Seven Puzzles You Think You Must Not Have Heard Correctly... by andrepd on Monday August 29, 2016 @04:00PM (#12384823)
Re:Seven Puzzles You Think You Must Not Have Heard Correctly... by posterboy on Monday August 29, 2016 @04:37PM (#12385104)
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.

Re:Seven Puzzles You Think You Must Not Have Heard Correctly... by evanb on Monday August 29, 2016 @09:08PM (#12386678)
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.

Re:Seven Puzzles You Think You Must Not Have Heard Correctly... by posterboy on Tuesday August 30, 2016 @10:11AM (#12390285)
"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.

Re:Seven Puzzles You Think You Must Not Have Heard Correctly... by andrepd on Monday August 29, 2016 @06:03PM (#12385795)
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?

Re:Seven Puzzles You Think You Must Not Have Heard Correctly... by posterboy on Monday August 29, 2016 @08:11PM (#12386442)
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".

Re:Seven Puzzles You Think You Must Not Have Heard Correctly... by andrepd on Monday August 29, 2016 @09:49PM (#12386876)
>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.

Re:Seven Puzzles You Think You Must Not Have Heard Correctly... by posterboy on Tuesday August 30, 2016 @05:59AM (#12388625)
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.

Re:Seven Puzzles You Think You Must Not Have Heard Correctly... by andrepd on Tuesday August 30, 2016 @10:54AM (#12390680)
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.
Re:Seven Puzzles You Think You Must Not Have Heard Correctly... by posterboy on Tuesday August 30, 2016 @07:37PM (#12394826)
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.