Talk:100 doors: Difference between revisions
→Invalid JavaScript solution: typo
(→Invalid JavaScript solution: typo) |
|||
| (17 intermediate revisions by 8 users not shown) | |||
Line 1:
== Incorrect answers ==
Some of the "solutions" given are incorrect. This problem is also a great example of the "Fence Post" condition often missed by programmers. Look over the solutions and ask yourself if the 100th door is shown to be open or closed.▼
: Yes -- because the doors in the problem are described with counting numbers and not zero-indexed, there are multiple incorrect solutions with the classic [https://en.wikipedia.org/wiki/Off-by-one_error#Fencepost_error fencepost error], listing 1 (not 0) but omitting 100. There wrong answers include Raku, SuperCollider, and Ursala. [[User:Jeremydouglass|Jeremydouglass]] ([[User talk:Jeremydouglass|talk]]) 00:35, 18 April 2020 (UTC)
::The Processing answer is wrong too. Note that indexing from 0 does not necessarily mean the solution is wrong: this only means that the second door is at index 1, etc. The C solution is correct, for instance. [[User:Hooch|Hooch]] ([[User talk:Hooch|talk]]) 07:45, 18 April 2020 (UTC)
== An observation ==
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. --[[User:Short Circuit|Short Circuit]] 00:14, 7 October 2007 (MDT)
:Actually, ''Vedit macro language'' example does not need any passes to display the results. The results are visible in the edit buffer as soon as the macro has finished opening and closing the doors. --[[User:PauliKL|PauliKL]] 14:59, 29 April 2009 (UTC)
Line 6 ⟶ 12:
: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 [http://olimu.com/Notes/Monkeys&Doors.htm] explains it.[[User:Drea|Drea]] 16:20, 11 October 2007 (MDT)
::Actually, square numbers have an even number of factors, the odd count comes from the first iteration that opens all doors. --[[User:AlexLehm|AlexLehm]] 22:16, 19 October 2011 (UTC)
::: Integer factors of 5 -> [1, 5], Integer factors of 4 -> [1, 2, 4] (The integer square root gives the list an odd length - other factors are always paired with their matching quotients) [[User:Hout|Hout]] ([[User talk:Hout|talk]]) 07:59, 8 September 2016 (UTC)
It also seems that the number of doors left open is the same as the integer square root of the total number of doors. --[[User:Nig|Nig]] ([[User talk:Nig|talk]]) 14:30, 16 June 2023 (UTC)
----
▲Some of the "solutions" given are incorrect. This problem is also a great example of the "Fence Post" condition often missed by programmers. Look over the solutions and ask yourself if the 100th door is shown to be open or closed.
== 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). [[User:JimD|JimD]] 16:02, 15 October 2007 (MDT)
Line 23 ⟶ 30:
::: Specialization is useful for teasing out specific differences between languages, but generalization obviously offers more flexibility in choices and demonstrations of clever solutions. If a particular class of solutions must be forbidden, I'd prefer to see the task forked to allow that class to be demonstrated. (Otherwise, a task is very likely to get stuck in a particular idiomatic mindset) --[[User:Short Circuit|Michael Mol]] 17:16, 27 May 2011 (UTC)
I would prefer if all solutions had at least the unoptimized version, though the optimized is fine with me as well (as of this writing, Erlang is missing a unoptimized version for example) --[[User:AlexLehm|AlexLehm]] 22:19, 19 October 2011 (UTC)
::: The so-called "optimized" version solves a _very different_ problem: finding the code with lowest Kolomogorov Complexity that prints the output of the "nonoptimized" version. It's basically the same as printing the solution directly from a string. (And here, ladies and gentlemen, is my optimized version of proving Fermat's Last Theorem, and it fits in the margin, too: <pre>"print 'TRUE'"</pre>). IMHO, for the optimized version to be acceptable, the language should be a theorem prover that spits out the optimized version from a properly encoded problem statement and also provides the proof that this is indeed equivalent to the nonoptimized version. Maybe the problem should be changed to ''"start with a random open/closed door state and then proceed as follows..."'' [[User:Bear-Shaped Lampshade|Bear-Shaped Lampshade]] ([[User talk:Bear-Shaped Lampshade|talk]]) 14:19, 29 December 2018 (UTC)
:Optimized solutions are essentially bypassing (my opinioin) the task requirements in that they don't perform the task's description (which I interpreted as implying how to solve the task or at least, implying the method; namely: visit every door and toggle the door). Otherwise, why don't we just change the task's name to ''display the non-negative squares up to'' '''N'''? -- [[User:Gerard Schildberger|Gerard Schildberger]] 19:49, 23 June 2012 (UTC)
:: Perhaps it was inevitable that this task would split into two, given the character of its solution. Understandable to have decided, at some point, that 'optimisations' were OK, but maybe that can still be reversed, and
== Self-contradictory task description ==
Line 51 ⟶ 58:
The main page currently says: "Since people can only keep seven things (plus or minus two) in their minds at a time, this quickly becomes an intellectual burden." But there is some significant evidence that this issue is related to the native language of the speaker. I do not know keywords to search on to dig out references, but I am remembering that typical chinese speakers can hold ten independent concepts where english speakers can hold six. --[[User:Rdm|Rdm]] 15:58, 3 December 2010 (UTC)
::FWIW and with a lag of 5 years, the 7+/-1 trope goes back to the 1950s and is very much out of date. The particular issue with Mandarin was simply that that the Mandarin integer morphemes are phonetically simpler, and impose a lighter load on the 'acoustic loop' of internal rehearsal, which does seem to have a rather limited capacity. The word "seven" is just phonetically more expensive (3 consonants, two syllables) than Mandarin's monosyllabic first tone 'qi', for example. Mandarin number words simply pack a bit more densely than English in constrained acoustic space. (Cantonese, which has more final consonants in its number morphemes, is likely to be somewhere in between).
== Output consistency ==
Line 108 ⟶ 116:
I just edited in missing initializations and fixed an off-by one termination test. I also commented some assumptions and a few 6502 quirks. This example has no output code -- the referenced emulator displays the memory directly. If I've counted the pixels(!) correctly, the output is numerically correct. It probably was anyway, but if so, only because of unstated initial conditions in the emulator. I don't know if I need to do anything to log the user (Gary Tippery) and time (11-Feb-2014 03:14 PDT).
== the
Well, the optimized version for the C, and C++ codes are just this for loop
Line 117 ⟶ 125:
</pre>
But in the examples it goes to 100, and not to 10, that means it's calculating 1000 doors, and not 100 doors? [[User:Rainb|Rainb]] ([[User talk:Rainb|talk]]) 07:03, 21 July 2014 (UTC)
== Invalid JavaScript solution ==
ES6:
// Array comprehension style
[ for (i of Array.apply(null, { length: 100 })) i ].forEach((_, i) => {
var door = i + 1
var sqrt = Math.sqrt(door);
if (sqrt === (sqrt | 0)) {
console.log("Door %d is open", door);
}
});
JavaScript does not have array comprehension, this results in a syntax error... [[User:MattDESTROYER|MattDESTROYER]] ([[User talk:MattDESTROYER|talk]]) 00:29, 3 December 2023 (UTC)
:Interesting. I tried it on TIO.RUN. they have 4 Javascript options, only SpiderMonkey accepts the syntax but gives incorrect output.
:Changing <code>console.log("Door %d is open", door);</code> to <code>console.log("Door " + door + " is open");</code> gives correct output.
:--[[User:Tigerofdarkness|Tigerofdarkness]] ([[User talk:Tigerofdarkness|talk]]) 14:01, 3 December 2023 (UTC)
| |||