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)
- 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)