Is the room open? | Hacker News Reader

Is the room open?

noudaldenhoven.nl

36 pointslizmat32 comments

This 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

Being pedantic, there is no room zero, so it should be 1 _ til 500.

You can try that, but it produces the wrong answer: "where" is still zero-based. You would also need 1+ i.e.

    q)1+where mod[;2] sum 0=(1_til 500) mod/: til 500
    1 4 9 16 25 36 49 64 81 100 121 144 169 196 225 256 289 324 361 400 441 484

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

I can read the C++ (not C), though, and improve it, whereas the two lines above are impenetrable.

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.

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

> Can you give an example of some improvements you see that are directly obvious from the C code?

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.

Well that was disappointing.

Anyway, good luck with things.

Disappointing? It's a simple, actionable comment.

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.

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.

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]

That's incorrect. Room 484 stays open.

Edit: I see you've updated your code susam.

484 is a perfect square. (22×22)

Edit: I see you've updated your comment geocar.

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

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

> 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

[2]: https://news.ycombinator.com/item?id=22288554

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,

  [k**2 for k in range(1, ceil(484**0.5))]

does not return 484.

Quite 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.

Behold 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");
            }
        }
    }

Simpler 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.

What 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.

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.

Aah you're right. Thanks.

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

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.

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.

This isn’t really a one-liner “programming” solution. The author solved it by hand and then made the computer write out the solution.

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.

The blog post is not about code. It’s about solving a puzzle, which they do!

PowerShell 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

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

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?

Seems like issue only on fedora even everything updated, debian test latest with chromium works fine: https://pastebin.com/URBBUgSU

https://rosettacode.org/wiki/100_doors

Reply on news.ycombinator.com