Talk:100 doors

An observation: You're actually making 101 passes. 100 mutative, and one for reading the final state. I'm wondering if the wording of the task should be changed, as no way of reporting the final state within the first 100 passes immediately comes to mind. --Short Circuit 00:14, 7 October 2007 (MDT)

---

Oddly enough it seems that the only doors left open after all the passes are complete are those which are perfect squares of integers: 1, 4, 9, 16, 25, 36, 49, 64, 81, and 100 Trivially trying the same code for 1000 doors and 1000 mutative passes seems to suggest that this is true for larger numbers (though it's far from proven). I should, undoubtely, do a proper analysis to see if I can prove that it generalizes and explain why.JimD 16:03, 11 October 2007 (MDT)

The number of times a door is visited is the same as the number of factors of the door's index. Open doors have been visited an odd number of times and only perfect squares have an odd number of factors. This [1] explains it.Drea 16:20, 11 October 2007 (MDT)

---

Optimized Examples

Somone just added a Python example which exploits the observation (noted in the preceding discussion here) that perfect squares are the only "open" doors after following this algorithm. That's fair enough, I guess. However, it suggests that similarly optimized implementations should be shown for all languages in which they are relevant (to offer a fair comparison). JimD 16:02, 15 October 2007 (MDT)

That was me, and you're absolutely right. I was just about to post a MAXScript version. I'll have to leave the Perl and Ada versions to someone else though. Drea 16:16, 15 October 2007 (MDT)

Unless we think that this kind of optimisation is beyond the scope of Rosetta Code? I'm not sure, but I thought I'd throw it out there. Drea 16:23, 15 October 2007 (MDT)

Or is the problem itself beyond the scope of Rosetta Code? What does the 100 Doors task show off about a langauge that is not covered in one of the other tasks? --IanOsgood 12:04, 16 October 2007 (MDT)

Strangely enough, the unoptimised MAXScript and Python examples demonstrate increasing the loop index by other than one. I haven't seen that in other tasks for languages where (<start>, <stop>, <step>) isn't always explicit in loop constructs. Drea 15:11, 16 October 2007 (MDT)

And looking back at the loop structures task, only a couple of language examples show that it's possible. For example, the C snippet only has "for (i=0; i<10; ++i)" (it also had one round and one curly bracket, but that's fixed now). Drea 15:27, 16 October 2007 (MDT)

Good point. This seems to be an argument not to have the optimized examples. Another classic task for loop increment >1 is the Sieve of Eratosthenes. --IanOsgood 15:55, 16 October 2007 (MDT)

As long as the code examples serve to illustrate factors that relate or separate languages, they're within the scope of Rosetta Code. (At least, as how I originally envisioned it. But I would like to see RC expand some by including more encyclopedic, documentary and historical information.) However, for clarity's sake, I described the optimized algorithm in the task description, and added additional organization to the code examples. --Short Circuit 21:25, 16 October 2007 (MDT)

I would not call that "optimized" example. It is entirely different algorithm. In fact, it just displays the known results. --PauliKL 14:11, 9 April 2009 (UTC)

Self-contradictory task description

The expression "... starting with the first door every time...." is in direct contradiction with statements like "...visit every 2nd door (door #2, #4, #6, ...)...". On the second round am I supposed to start with #1 or with #2?

I fixed the task description. It should start with door 1 on pass 1, door 2 on pass 2, etc. --Mwn3d 22:07, 11 July 2008 (UTC)

Sub-headings

Do we need the sub-headings for unoptimized and optimized implementations? They just make the Contents list very long and more difficult to find a language. I think it would be better just to use normal text with bold. --PauliKL 11:22, 8 April 2009 (UTC)