Coding Challenge #9
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
Recamán’s sequence is a sequence where the first term is 0 (meaning R(0) = 0), and each next term in the sequence is either the previous term minus the current index, if the result is negative, then the next term is the previous term plus the current index.
The first few terms of the sequence are: 0, 1, 3, 6, 2, 7, 13, 20, 12…
Write a function R(n), that returns the n-th term in the sequence.
R(0) -- 0
R(1) -- 1
R(2) -- 3
R(3) -- 6
R(12) -- 18
R(20) -- 22
R(100) -- 152
Goodluck! You can find a list of all the challenges here or a github version here.
Answer!
More formally,
If you ever made an algorithm for a fabonacci sequence for example, making an algorithm for another sequence would become a piece of cake! What’s the answer? Recursion.
Technically, in order to calculate the value each time we would need to do this
local previous = R(n-1)
if previous - i > 0 then
return previous - i
else
return previous + i
end
and with ternary magic we can do
local previous = R(n-1)
return previous - n > 0 and previous - n or previous + n
Now, let’s say we called R(3), the function will need to get the previous term, which is the 2nd term first in order to perform the calculations later. The 2nd term will need the 1st term, because any term requires the previous one. The 1st would require the starting term, the 0-th if you’d call it that, which is 0. We know the starting term so we can simply return it straight away (if n == 0 then return 0). Now we go up the ladder again, we hand off the 1st term 0, it finishes its calculation, we hand off the result of that to the 2nd term, and we hand off the result of that to the 3rd term, and we get out final result (which is 6). The poor computer has to go through this whole process! Imagine if we wanted to get the 100th term. This our function, very simple.
local function R(n)
if n == 0 then return 0 end
local r = R(n-1)
return r - n > 0 and r - n or r + n
end
You can even do this with iteration, but in cases like these, recursion seems to be superior, because it’s easier to understand and read. But performance wise, iteration is better.
local function R(n)
if n == 0 then return 0 end
local r = R(n-1)
return r - n > 0 and r - n or r + n
end
local function R2(n)
local previous = 0
for i = 1, n do
previous = previous-i>0 and previous-i or previous+i
end
return previous
end
local start = tick()
for i = 1, 10000 do
R(i)
end
print(tick()-start) --8.298012
local start = tick()
for i = 1, 10000 do
R2(i)
end
print(tick()-start) --3.761421
The Slightly Spooky Recamán Sequence - Numberphile - YouTube