6 ms·
Is the room open?
- susam 7y agoSummary: There are 500 doors numbered 1, 2, ..., 500. All doors are closed initially. In iteration k, we toggle the states of doors k, 2k, ..., floor(500/k) * k where k runs from 1 to 500, inclusive. What doors are open in the end? Only perfect squares have odd number of factors. All other natural numbers have even number of factors. Therefore, only the doors with perfect square numbers on them get toggled odd number of times and end up in states that are opposite of their initial states. Python solution: >>> [k**2 for k in range(1, int(500**0.5) + 1)] [1, 4, 9, 16, 25, 36, 49, 64, 81, 100, 121, 144, 169, 196, 225, 256, 289, 324, 361, 400, 441, 484]
- deleted 7y ago[deleted]
- geocar 7y agoThat's incorrect. Room 484 stays open. Edit: I see you've updated your code susam.
- nmyk 7y ago484 is a perfect square. (22×22) Edit: I see you've updated your comment geocar.
- geocar 7y ago484 wasn't returned by the code susam originally posted. Isn’t it funny how a python one liner required two edits to produce the correct result? (The summary description still matches the old incorrect code)
- deliciousreader 7y ago> The summary description still matches the old incorrect code The summary description matches the current correct code. So it could not possibly match any incorrect code (if it really existed).
- geocar 7y ago> The summary description matches the current correct code. So it could not possibly match any incorrect code. Incorrect. Here's the summary reproduced (in case susam edits again): >>> There are 500 doors numbered 1, 2, ..., 500. All doors are closed initially. In iteration k, we toggle the states of doors k, 2k, ..., floor(500/k) * k where k runs from 1 to 500 Note the "floor(500/k)" statement. That matched the original code fragment (and what is still sitting in a terminal on my laptop): >>> [k**2 for k in range(1, int(500**0.5))] but not the new one which includes a +1. int(…) is floor. int(…)+1 isn't, and it's wrong: It works for 500, but not for other values. math.ceil would have been more correct, but it might've been more obvious that it doesn't match the "summary". > (if it really existed). Let me make sure I understand what you mean here: You actually think it more likely that my two implementations, written in a comment [1] with a lower timestamp than [2], and the perl6 implementation on the linked article all include 484 as part of the valid result, and yet my comment [2] that calls on this value specifically, was somehow meant to indicate that 484 is not part of the valid result? Ha. [1]: https://news.ycombinator.com/item?id=22288534 https://news.ycombinator.com/item?id=22288534 [2]: https://news.ycombinator.com/item?id=22288554 https://news.ycombinator.com/item?id=22288554
- akovaski 7y agoThe +1 makes the range inclusive rather than exclusive. This matches the summary, which is inclusive of floor(500/k). Ceil wouldn't correctly handle the case where the number of rooms equals a perfect square. That is, [k**2 for k in range(1, ceil(484**0.5))] does not return 484.
- geocar 7y agoQuite right! So a 1+ is needed. I can't amend my comment to that point, but the original comment didn't have +1 in there anyway.
- geocar 7y agoThis problem has a nice array solution: q)where mod[;2] sum 0=til[500] mod/: til[500] 0 1 4 9 16 25 36 49 64 81 100 121 144 169 196 225 256 289 324 361 400 441 484 q){x*x} til ceiling sqrt 500 0 1 4 9 16 25 36 49 64 81 100 121 144 169 196 225 256 289 324 361 400 441 484 but I think it's very interesting to look at them side by side: Do you see the "triangle" in the above that suggests the sqrt-solution? q)0=til[500] mod/: til[500] 00000000000000000000000000000000000000000000000000000000000000000000000000000.. 11111111111111111111111111111111111111111111111111111111111111111111111111111.. 10101010101010101010101010101010101010101010101010101010101010101010101010101.. 10010010010010010010010010010010010010010010010010010010010010010010010010010.. 10001000100010001000100010001000100010001000100010001000100010001000100010001.. 10000100001000010000100001000010000100001000010000100001000010000100001000010.. 10000010000010000010000010000010000010000010000010000010000010000010000010000.. 10000001000000100000010000001000000100000010000001000000100000010000001000000.. 10000000100000001000000010000000100000001000000010000000100000001000000010000.. 10000000010000000010000000010000000010000000010000000010000000010000000010000.. 10000000001000000000100000000010000000001000000000100000000010000000001000000.. 10000000000100000000001000000000010000000000100000000001000000000010000000000.. 10000000000010000000000010000000000010000000000010000000000010000000000010000.. 10000000000001000000000000100000000000010000000000001000000000000100000000000.. 10000000000000100000000000001000000000000010000000000000100000000000001000000.. 10000000000000010000000000000010000000000000010000000000000010000000000000010.. 10000000000000001000000000000000100000000000000010000000000000001000000000000.. 10000000000000000100000000000000001000000000000000010000000000000000100000000.. 10000000000000000010000000000000000010000000000000000010000000000000000010000.. 10000000000000000001000000000000000000100000000000000000010000000000000000001.. 10000000000000000000100000000000000000001000000000000000000010000000000000000.. 10000000000000000000010000000000000000000010000000000000000000010000000000000.. .. Isn't that beautiful? This is really illustrative of what I think is valuable in learning array programming, and whilst I've noted it previously on HN[1], this might be an even better example. Try writing the algorithm in C or Python: void main(){ int i,j,k; for(i=0;i<500;++i) { for(j=k=0;j<499;++j)if(!(i%(1+j)))++k; if(k%2)printf("%d ",i); } puts(""); } Now because I can't see the shape of the data so easily anymore, I might not so quickly recognise the optimisation waiting for me in that code, especially if this spanned more than a screenful (because e.g. we were doing something else besides printing the results) [1]: https://news.ycombinator.com/item?id=16851862 https://news.ycombinator.com/item?id=16851862
- useerup 7y agoPowerShell solution: 1..[Math]::Sqrt(500) | %{$_*$_} 1 4 9 16 25 36 49 64 81 100 121 144 169 196 225 256 289 324 361 400 441 484
- hrgiger 7y agoI am getting: Attackers might be trying to steal your information from www.noudaldenhoven.nl (for example, passwords, messages, or credit cards). Learn more NET::ERR_CERT_AUTHORITY_INVALID from:digicert: TLS Certificate is not trusted The certificate is not signed by a trusted authority (checking against Mozilla's root store). If you bought the certificate from a trusted authority, you probably just need to install one or more Intermediate certificates. Contact your certificate provider for assistance doing this for your server platform. Beside of that http works and isnt room 3 only closed once and never opened or am I missing something
- michaelt 7y agohttps://www.ssllabs.com/ssltest/analyze.html?d=www.noudaldenhoven.nl https://www.ssllabs.com/ssltest/analyze.html?d=www.noudalden... says the site has an incomplete certificate chain. I'm guessing that "Let's Encrypt Authority X3" isn't in your local keyring?
- hrgiger 7y agoSeems like issue only on fedora even everything updated, debian test latest with chromium works fine: https://pastebin.com/URBBUgSU https://pastebin.com/URBBUgSU
- lxe 7y agoThis isn’t really a one-liner “programming” solution. The author solved it by hand and then made the computer write out the solution.
- whatshisface 7y agoYou wouldn't want a brute force solution to a problem that could be solved by hand. It's really the fault of the problem that no programming was needed to solve it.
- Jaxan 7y agoThe blog post is not about code. It’s about solving a puzzle, which they do!
- kazinator 7y agohttps://rosettacode.org/wiki/100_doors https://rosettacode.org/wiki/100_doors
- mothsonasloth 7y agoBehold my enterprisey Java solution public static void main2(String[] args) { final List<String> rooms = new ArrayList<>(Collections.nCopies(MAX_ROOM, "CLOSED")); int employee = 1; do { int roomIndex = employee - 1; do { final String roomState = rooms.get(roomIndex); if (roomState.equals(OPEN)) { rooms.set(roomIndex, CLOSED); } else if (roomState.equals(CLOSED)) { rooms.set(roomIndex, OPEN); } roomIndex = roomIndex + employee; } while (roomIndex < MAX_ROOM); employee++; } while (employee <= MAX_ROOM); for (int i = 0; i < rooms.size(); i++) { if (rooms.get(i).equals(OPEN)) { System.out.println("Room " + (i + 1) + " is OPEN"); } } }
- boyobo 7y agoSimpler explanation for why perfect square <=> odd number of factors Proof: For every divisor d of n, n/d is another, different, divisor. This gives a pairing of all the divisors. The only exception is if n/d = d. The exceptional case n/d=d only happens when n=d^2, i.e. when n is a perfect square. Thus, when n is not a perfect square, there is a pairing of all its divisors, hence the number of divisors is even. If n is a perfect square, the pairing pairs up all the divisors except for sqrt(n). Thus the number of divisors is odd.
- seanhunter 7y agoWhat about 27? It has an odd number of factors but isn't a perfect square. I think your reasoning fails for x^y where y is an odd number > 1.
- boyobo 7y agoThe factors of 27 are 1,3,9 and 27. That’s four factors. That's why door 27 is closed at the end of the open/closing process - employees 1,3,9 and 27 touch the door and so the final state of the door is the same as the initial state of the door. Maybe you are talking about the number of prime factors. This quantity is irrelevant to door open/closing problem.
- seanhunter 7y agoAah you're right. Thanks.
- jerome-jh 7y agoperfect square => even number of factors n = r^2 n = (p1^k1 * p2^k2 * ... * pi^ki)^2 n = p1^(2 * k1) * p2^(2 * k2) * ... * pi^(2 * ki) hence n has 2 * (k1+k2+...+ki) factors. Or am I wrong? Reciprocal left as an exercise ;)
- boyobo 7y agoNot really sure what your argument is. But it’s wrong, because n=4 is a counterexample. The factors are 1,2 and 4. This is an odd number of factors. Edit: it seems you are talking about 'The number of factors in the prime factorization of n'. This is not really relevant to the question posed in the submission.