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:
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)
...but this is not a huge bother for me: 0 mod 0 is 0N which doesn't equal zero, and I think the extra 1_ or 1+ distracts somewhat from the point I'm trying to make.
Re:Is the room open?
by geocar on Monday February 10, 2020 @01:44PM
(#22291941)
> I can read the C++ (not C), though, and improve it,
Can you give an example of some improvements you see that are directly obvious from the C code?
I'm especially interested in a process that reveals the sqrt optimisation.
> whereas the two lines above are impenetrable.
It takes practice to learn a new language. For now, you will have to take my word that the former of the lines is almost a literal translation of the problem, and to an experienced q developer, directly suggests the second line. I hoped the illustration would suggest this, but communicating alien things is hard.
Languages that have that property are extremely valuable to me: There are a lot of languages that have a nice notation leading from problem to code (lisp, haskell, etc; at least some of the time) but it is much more rare that we have a notation that directly suggest further (better) notations, and myself having programmed in C, C++, Perl, Python, Java, Forth, Fortran, Cobol, Lisp, and so on for decades, I'm telling you that this seems to happen more with array languages than with any other language or language-family that I've had experience with.
If that intrigues you, I can try and give you a crash course:
- til x is the vector of integers from 0 to x. In C it's a little like: r=calloc(sizeof(int),x);for(i=0;i<x;++i)r[i]=x;
- x mod y is modulo. Similar to x%y in C, but it generalises to vectors.
- x mod/: y shows each-right (/:) which composes to the operator on the left. This builds a 2d array of each x argument (columns) mod each y argument (rows).
- til[x] mod/: til[x] is thus the 2d array of integers from 0 to x mod each right the same list.
- x=y is equals. Similar to x==y in C, but it generalises to vectors.
- 0=til[x] mod/: til[x] is thus a bitmap of locations where (columns:0..x) mod (rows:0..x) = 0
- sum adds up the values in a vector. applied to a 2d array (including a bitmap) returns the sum of each column.
- functions are written with curly braces. In a function, x is the first argument, y is the second.
- {x*x} is thus a function that squares its result.
- mod[;2] is a projection. It is actually the function {x mod 2}
- where returns the locations of 1's in a list.
- where mod[;2] ... is thus the locations of odd values.
- sqrt x returns the square-root of x, expressed as a float. this too generalises to vectors, but we do not take advantage of this.
- ceiling x is the same as ceil(x) except it too generalises to vectors (we aren't using this).
With that in hand, you should be able to carefully decode each line: They're read from left to right, and q composes easily.
> I can also lift the core of the C++ code into a function and reuse it, which doesn't appear possible in the other language.
That's generally true for Python or Java, but q programmers have an excellent C binding. It's as simple as:
k(0, "{where mod[;2] sum 0=til[x] mod/: til x}", kj(n), 0)
- k(f,s,x,[y,[z,...]],NULL) calls into k. f must be zero (in-process) in this case. s is the script. x, y, z, (etc) are arguments terminated by null.
- kj(n) returns a variant (type tagged) from a long long.
Re:Is the room open?
by susam on Monday February 10, 2020 @07:23AM
(#22288482)
Summary: 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.
Re:Is the room open?
by geocar on Monday February 10, 2020 @09:57AM
(#22289601)
> 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?
Re:Is the room open?
by akovaski on Monday February 10, 2020 @01:09PM
(#22291582)
The +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,
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");
}
}
}
Re:Is the room open?
by boyobo on Tuesday February 11, 2020 @04:03PM
(#22302810)
The 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.
Re:Is the room open?
by boyobo on Tuesday February 11, 2020 @04:04PM
(#22302830)
Not 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.
Re:Is the room open?
by jerome-jh on Wednesday February 12, 2020 @08:23AM
(#22308565)
Indeed I was talking about prime factors. I understood your point later last night and it is certainly valid. I quite do not understand the original paper though.
Re:Is the room open?
by whatshisface on Monday February 10, 2020 @10:46AM
(#22290058)
You 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.
Re:Is the room open?
by hrgiger on Monday February 10, 2020 @08:55AM
(#22289082)
I 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
[1]: https://news.ycombinator.com/item?id=16851862
I can also lift the core of the C++ code into a function and reuse it, which doesn't appear possible in the other language.
Can you give an example of some improvements you see that are directly obvious from the C code?
I'm especially interested in a process that reveals the sqrt optimisation.
> whereas the two lines above are impenetrable.
It takes practice to learn a new language. For now, you will have to take my word that the former of the lines is almost a literal translation of the problem, and to an experienced q developer, directly suggests the second line. I hoped the illustration would suggest this, but communicating alien things is hard.
Languages that have that property are extremely valuable to me: There are a lot of languages that have a nice notation leading from problem to code (lisp, haskell, etc; at least some of the time) but it is much more rare that we have a notation that directly suggest further (better) notations, and myself having programmed in C, C++, Perl, Python, Java, Forth, Fortran, Cobol, Lisp, and so on for decades, I'm telling you that this seems to happen more with array languages than with any other language or language-family that I've had experience with.
If that intrigues you, I can try and give you a crash course:
- til x is the vector of integers from 0 to x. In C it's a little like: r=calloc(sizeof(int),x);for(i=0;i<x;++i)r[i]=x;
- x mod y is modulo. Similar to x%y in C, but it generalises to vectors.
- x mod/: y shows each-right (/:) which composes to the operator on the left. This builds a 2d array of each x argument (columns) mod each y argument (rows).
- til[x] mod/: til[x] is thus the 2d array of integers from 0 to x mod each right the same list.
- x=y is equals. Similar to x==y in C, but it generalises to vectors.
- 0=til[x] mod/: til[x] is thus a bitmap of locations where (columns:0..x) mod (rows:0..x) = 0
- sum adds up the values in a vector. applied to a 2d array (including a bitmap) returns the sum of each column.
- functions are written with curly braces. In a function, x is the first argument, y is the second.
- {x*x} is thus a function that squares its result.
- mod[;2] is a projection. It is actually the function {x mod 2}
- where returns the locations of 1's in a list.
- where mod[;2] ... is thus the locations of odd values.
- sqrt x returns the square-root of x, expressed as a float. this too generalises to vectors, but we do not take advantage of this.
- ceiling x is the same as ceil(x) except it too generalises to vectors (we aren't using this).
With that in hand, you should be able to carefully decode each line: They're read from left to right, and q composes easily.
> I can also lift the core of the C++ code into a function and reuse it, which doesn't appear possible in the other language.
That's generally true for Python or Java, but q programmers have an excellent C binding. It's as simple as:
- k(f,s,x,[y,[z,...]],NULL) calls into k. f must be zero (in-process) in this case. s is the script. x, y, z, (etc) are arguments terminated by null.- kj(n) returns a variant (type tagged) from a long long.
Comments and good variable names, to begin with, which should be mandated by any style guide.
If you can't give your variables readable, understandable names you don't understand your code and nobody else is going to, either.
Anyway, good luck with things.
It's also the bare minimum required to have readable source code.
Most people don't like reading stuff that looks like it came out of a particularly aggressive obfuscator.
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:
Edit: I see you've updated your code susam.
Edit: I see you've updated your comment geocar.
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)
The summary description matches the current correct code. So it could not possibly match any incorrect code (if it really existed).
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):
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
[2]: https://news.ycombinator.com/item?id=22288554
I can't amend my comment to that point, but the original comment didn't have +1 in there anyway.
public static void main2(String[] args) {
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.
I think your reasoning fails for x^y where y is an odd number > 1.
Maybe you are talking about the number of prime factors. This quantity is irrelevant to door open/closing problem.
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 ;)
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.
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
I'm guessing that "Let's Encrypt Authority X3" isn't in your local keyring?