Coding Challenge #10
Hello! Welcome back to another challenge. I am still looking for people to help me out and make challenges as well! So if you’re interested, help me out!
As usual, same requirements:
- Has to be written in Lua 5.1 (the version roblox uses)
- The program has to be compatible with Roblox Studio, meaning you can’t use features vanilla Lua has but rbxlua disabled
- You can’t use httpservice to cheat the challenge
You study at a school where there are as many doors as students.
Each day, n students come, and each student changes states of certain doors. To change the state of a door means to open it if it was closed, or close it if it was open.
At the start of the day, all doors are closed. The first student comes, and changes state of all doors labeled with multiples of 1 (meaning {1, 2, 3, 4, 5, 6...}, remember that there are as many doors as students). The second student comes, and changes the state of all doors labeled with multiples of 2 (meaning {2, 4, 6, 8, 10...}, he’ll be changing states depending on the previous student’s changed states of course). Third student comes, all doors labeled with multiples of 3 are switched. Yada yada, you get the idea.
Write a function OpenDoors(n), where n is how many students came that day, that calculates how many doors are open at the end of the day (meaning after all students did the state changing).
OpenDoors(4) -- 2
OpenDoors(10) -- 3
OpenDoors(100) -- 10
Goodluck! You can find a list of all the challenges here or a github version here.
Answer!
This picture visualises what happens if you called OpenDoors(4), should give you an idea
Now, you can make a naive implementation, that loops n times, and each time goes through all the multiples of the current student (meaning the multiples of the current i) that are between 1 and n, because we have n doors. What we will do is, for each multiple, we inverse (the t[j] = not(t[j]) part) whatever the index inside of t was, this is where the state inversion/changing happens. At the end, we will have a table of falses and trues, where trues are open doors. We just need to calculate how many trues there are.
local function OpenDoors(n)
local t = {}
for i = 1, n do
for j = 0, n, i do
t[j] = not(t[j])
end
end
local sum = 0
for i, v in ipairs(t) do
if v == true then
sum = sum + 1
end
end
return sum
end
Now, for a more interesting solution, you can use xor bitwise operation, which is bit32.bxor. Doors have two states, open or closed, which means they’re kinda like binary, either a 1 or 0. We will represent doors with an n-long string that’s holding a binary number. An open door is a 1, a closed one is 0. If you were to look at xor's behavior.
It basically toggles bits. If you choose a 1, you’re gonna flip the current bit (turn it to 1 if it’s a 0, turn it to 0 if it’s 1), if you choose a 0, you’re leaving it as it is. We can use this, by creating a binary string for each student, where each one will have bits corresponding to multiples of the current student as 1s, that way if we do xor that with the starting string (which is all 0s because all doors are closed at the start of the day) we’ll flip the doors corresponding to the multiples of the current student. The starting string will be set again after each student so the next student flipes the doors depending on what the previous student flipped. Not gonna explain my implementation, but you understand the approach I took.
(BROKEN PIECE OF CODE, MIGHT FIX)
local function OpenDoors(n)
local b = string.rep("0", n)
for i = 1, n do
local a = b:gsub(string.rep(".", i), string.rep("0", i-1).."1")
local j = 0
b = b:gsub(".", function(bit)
j = j + 1
return bit32.bxor(bit, string.sub(a,j,j))
end)
end
return select(2, b:gsub("1", ""))
end
