jallah
Level: Roachling

Rank Points: 13
Registered: 01-03-2005
IP: Logged

File: Locker.java (1 KB)
Downloaded 61 times.
License: Other
From: Unspecified

Solution to the Locker puzzle posted by Schik 02-04-2003
This is a java code solution It's "one off" as it returns 32 instead of 31, and I've tried to fix it..

Please post corrections, comments, etc.
NOTE: the updated file is attached to the follow up below

jallah

This is( some of )the program output

1
100
10000
1000000
100000000
10000000000
1000000000000
100000000000000
10000000000000000
1000000000000000000
100000000000000000000
10000000000000000000000
1000000000000000000000000
100000000000000000000000000
10000000000000000000000000000
1000000000000000000000000000000

[Edited by jallah at Local Time:01-04-2005 at 03:10 PM: file change info]

____________________________
http://www.the-underdogs.org/index.php

stigant
Level: Smitemaster

Rank Points: 1182
Registered: 08-19-2004
IP: Logged

Its one off because you have a locker 0 instead of starting with locker 1. Since 0 is divisible by all numbers, its open after odd students and closed after even students.

The fix is pretty simple, just start your count (at the end) on item 1 instead of 0:

int temp = 0;
for( int i=1; i<skap.length; i++)
if( skap == 1 )
temp++;
System.out.println(temp);


____________________________
Progress Quest Progress

jallah
Level: Roachling

Rank Points: 13
Registered: 01-03-2005
IP: Logged

The last bit of the program (that you have corrected) is only the bit that writes to the console/gives output. The "math bit" that does the actual calculations/solves the puzzle, is the bit above.

Also, if i start the count at item 1 (index 1) ,then the first locker will not be accounted for. So it must start at index 0, as arrays range from 0 to the length of the array minus 1, and the rest of the program uses index 0 as the starting point (as the first locker).

So the problem lies elsewhere. Thanks though.

However it should be added that making your suggested change would force the program to produce a correct answer, 31.

[Edited by jallah at Local Time:01-04-2005 at 02:18 PM]

____________________________
http://www.the-underdogs.org/index.php

jallah
Level: Roachling

Rank Points: 13
Registered: 01-03-2005
IP: Logged

File: Locker.java (1.6 KB)
Downloaded 50 times.
License: Other
From: Unspecified

So... just updated the java file, now its all english and comments are better so should be easier to understand...

Still haven't found the error, so I'm starting to suspect that maybe its not wrong, but that its actually 32?

The new file is attached to this follow up post.

jallah

____________________________
http://www.the-underdogs.org/index.php

stigant
Level: Smitemaster

Rank Points: 1182
Registered: 08-19-2004
IP: Logged

Well, if locker 0 is representing locker 1, then you are starting all the students (other than the first one) in the wrong place. Student 2 starts at locker 2 (index 1), student 3 starts at locker 3 (index 2) etc.

By having index 0 represent "locker 0" you can have all students start at the same point (this is what I assumed that you did). However, since "locker 0" doesn't exist, you have to ignore it in your count at the end.

____________________________
Progress Quest Progress

jallah
Level: Roachling

Rank Points: 13
Registered: 01-03-2005
IP: Logged

Are you sure?

for ( int k = 0; k < locker.length; k += 2 )
{
locker[k] = 0; // locked
}

The code above shows what student 2 does.
If you're familiar with the for statement and arrays, you know that the first few runs of the loop will do this:

locker[0] = 0;

then

locker[2] = 0;

etc. as k is initialized to 0 and increases by 2 for every runthrough. Every index reached by this block will be set to 0.

Are you misunderstanding or am I missing something?
It's not my intention to be pig-headed.

btw. note that when you want to write arrays like [ i ]
you should replace "i" with "j" or "k" in order to avoid the italic when writing code in a forum using UBB code.

____________________________
http://www.the-underdogs.org/index.php

stigant
Level: Smitemaster

Rank Points: 1182
Registered: 08-19-2004
IP: Logged

Are you misunderstanding or am I missing something?

Ok, I went back and re-read the problem. Its not clear, but the intent of the problem is that the 2nd student starts with the 2nd locker (ie the 2nd student toggles all lockers which are multiples of 2), the 3rd student toggles all lockers which are multiples of 3 etc. Since 1 is not a multiple of any number other than 1, the only student who should affect locker 1 (index 0) is the first one.

[Edited by stigant at Local Time:01-04-2005 at 05:19 PM]

____________________________
Progress Quest Progress

stigant
Level: Smitemaster

Rank Points: 1182
Registered: 08-19-2004
IP: Logged

btw. note that when you want to write arrays like [ i ]
you should replace "i" with "j" or "k" in order to avoid the italic when writing code in a forum using UBB code.

or you can use [lb] to create a left bracket and [rb]

____________________________
Progress Quest Progress

Schik
Level: Legendary Smitemaster

Rank Points: 5381
Registered: 02-04-2003
IP: Logged

whether student N starts at locker 0 or locker N shouldn't matter - you should end up with 31 either way.

I took a glance at your code, and it looks like you're only iterating through 999 students. You do the first two as separate cases, then loop through from 3 to 999. That's 2 + 997 = 999 students. Make that outer loop in Students 3-1000 (i <= NUMBER_OF_STUDENTS) and that should fix it.



____________________________
The greatness of a nation and its moral progress can be judged by the way it treats its animals.
--Mahatma Gandhi

stigant
Level: Smitemaster

Rank Points: 1182
Registered: 08-19-2004
IP: Logged

whether student N starts at locker 0 or locker N shouldn't matter - you should end up with 31 either way.

Well, it doesn't matter if you aren't couting locker 0 (in the original problem, there is no locker 0). It does matter if you do count locker 0 since every student toggles locker 0. The point of the solution to the problem is that only those lockers with a square number will be open at the end because an odd number of students have toggled them (since they have an odd number of unique factors). Since 0 has neither an odd nor an even number of factors (it has an infinite number of factors), the final state of locker 0 diverges, unlike the other lockers. If you count locker 0, your answer will actually depend on whether the last student was odd or even. If even (and between floor(sqrt(1000)) and ceiling(sqrt(1000)) you will get 31, but if odd, you will get 32).

I took a glance at your code, and it looks like you're only iterating through 999 students. You do the first two as separate cases, then loop through from 3 to 999. That's 2 + 997 = 999 students. Make that outer loop in Students 3-1000 (i <= NUMBER_OF_STUDENTS) and that should fix it.

true, but if index 0 is locker 0, then there are only really 999 lockers, and you only need 999 students since student 1000 will not change any lockers.

If index 0 is locker 1, then there are actually 2 bugs: the number of students, but also the fact that every student is toggling locker 1 when only one student (student 1) should be.

____________________________
Progress Quest Progress

jallah
Level: Roachling

Rank Points: 13
Registered: 01-03-2005
IP: Logged

Schik wrote:
I took a glance at your code, and it looks like you're only iterating through 999 students. You do the first two as separate cases, then loop through from 3 to 999. That's 2 + 997 = 999 students. Make that outer loop in Students 3-1000 (i <= NUMBER_OF_STUDENTS) and that should fix it.

Yep, that was it. Thank you.

And stigant, thanks for your efforts too, but you're wrong... take a look at my replies to your earlier posts. If you read them well (and actually know programming) you should be able to see what I mean. Not to be rude, just that youre off the track


jallah

[Edited by jallah at Local Time:01-04-2005 at 09:12 PM]

____________________________
http://www.the-underdogs.org/index.php

jallah
Level: Roachling

Rank Points: 13
Registered: 01-03-2005
IP: Logged

File: Locker.java (1.6 KB)
Downloaded 55 times.
License: Other
From: Unspecified

And at last here's the final code, with the neccasary changes made

____________________________
http://www.the-underdogs.org/index.php

stigant
Level: Smitemaster

Rank Points: 1182
Registered: 08-19-2004
IP: Logged

And stigant, thanks for your efforts too, but you're wrong... take a look at my replies to your earlier posts. If you read them well (and actually know programming) you should be able to see what I mean. Not to be rude, just that youre off the track

ok, look, I was a software developer for 4 years, and I majored in CS. I know what I'm talking about. If you change the number of lockers and students to 1001 in your final program, you will get the wrong answer (the answer should still be 31 open lockers since 1001 is not a square number, but since the 1001st student toggles the 0 index locker, you have an additional open locker, and the program will tell you that there are 32 open lockers)

____________________________
Progress Quest Progress

Schik
Level: Legendary Smitemaster

Rank Points: 5381
Registered: 02-04-2003
IP: Logged

That is true, jallah. With 1000 students, you will get the same results either way, but your algorithm is slightly different than the scenario described in the puzzle post. It's trivial to fix your program to work as the puzzle is described: Change the inner loop for students 3-1000 to be for (int j = i; j < locker.length; j += i).

i.e. just init j to be i, not zero.

____________________________
The greatness of a nation and its moral progress can be judged by the way it treats its animals.
--Mahatma Gandhi

jallah
Level: Roachling

Rank Points: 13
Registered: 01-03-2005
IP: Logged

Ok I suppose theres a better way to solve it. However, my intention was only to solve the puzzle at hand, which was limited to 1000 students. I'm happy with that tbh. For now

Would be cool though if you were to complete the code by making the improvements that you see fit.

jallah

____________________________
http://www.the-underdogs.org/index.php

stigant
Level: Smitemaster

Rank Points: 1182
Registered: 08-19-2004
IP: Logged

However, my intention was only to solve the puzzle at hand, which was limited to 1000 students. I'm happy with that tbh. For now

don't you find getting the right answer for the wrong reason unsatisfying?

____________________________
Progress Quest Progress