Coding Challenge #11
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!
This one’s harder than usual!
Thanks for the epic, one and only, @LegitimatlyMe, for the challenge idea.
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 Luau has disabled
- You can’t use httpservice to cheat the challenge
A non-decreasing array is an array where any element at index i is less or equal to the element at index i+1 .
{4, 5, 2} is decreasing, because we decreased from 5 to 2. {4, 5, 8} on the other hand is non-decreasing, because each element is less than the element after it.
Given an array A of length n , write a function CanBeNonDecreasing that determines if you can make A non-decreasing by changing at most one element.
Like in the example above, we can make {4, 5, 2} by just changing the 2, so the function returns true for that. {2, 6, 4, 3} would return false, because you can’t make it non-decreasing by just changing one element.
If the function received an already non-decreasing array (like {0, 1, 5, 9} or {5, 6, 6}) return true straight away.
To check your code, get this link, copy the code, and pass your function to the check function, if it passes through all tests, you succeeded! link 
Goodluck! You can find a list of all the challenges here or a github version here.
Answer!
First, there a couple of general things that you should notice:
- If there is more than a single decreasing number, you can’t make the array non-decreasing (e.g.
{1, 2, 1, 0}can’t become non-decreasing) - Changing the decreasing number to the previous number would make the array non-decreasing (assuming the array has a singe decreasing number) (e.g. if you had an array
{4, 5, 2}you can make it non-decreasing just by doing{4, 5, 5}
Now, knowing these two things, it might seem obvious that your code would just look like something simple similar to
local function CanBeNonDecreasing(t)
local flaws = {}
for i = 1, #t-1 do
if t[i] > t[i+1] then --if current index is greater than the next
table.insert(flaws, i)
end
end
if #flaws > 1 then return false end --if there is more than a single decreasing number
return true --else return true
end
This would cover most simple test cases, but it won’t work for some. Something like {1, 1, 0, 0} would return true because we see that there is only 1 flaw, and that is second index 1 is bigger than third index 0. But when you change 0 to 1 (attempting to make array non-decreasing) you get {1, 1, 1, 0} which is still non-decreasing, so in reality it’s supposed to return true.
The way I wrote my code is, first checking if the array was non-decreasing, if so just return true straight away, if there was more than a single flaw obviously you can’t make it non-decreasing, so return false. Now, if there was a single flaw, what I do is, make two separate attempts to make the array non-decreasing, first attempt is by changing the decreasing number to the previous greater number, or vice versa, changing the previous great number to the decreasing number. Then I check if either one of the attempts was non-decreasing. Technically if the array was still non-decreasing after these attempts, which are the only possible attempts, it can’t become non-decreasing, and I return false, if either of them made it non-decreasing, I return true.
local function CanBeNonDecreasing(t)
if #t == 0 or #t == 1 then return true end
local function f(t_, index, change)
local flaws = {}
local t = {}
for i, v in pairs(t_) do
t[i] = v
end
t[index] = change
for i = 1, #t-1 do
if t[i] > t[i+1] then
table.insert(flaws, i)
end
end
if #flaws == 0 then return true end
return false, flaws[1]
end
local index = select(2, f(t,0,0))
if not(index) then
return true
end
if f(t,index,t[index+1]) or f(t,index+1,t[index]) then
return true
end
return false
end
Now my solution isn’t that epic. Your boy @LegitimatlyMe has this even epicer solution that’s too amazing for me to explain.
function getIdxOfLastElementOfNonDecreasingSubsequence(t, i, j)
for k = i, j - 1 do
if t[k] > t[k + 1] then
return k
end
end
return -1
end
local function test(t)
local n = getIdxOfLastElementOfNonDecreasingSubsequence(t, 1, #t)
if n == -1 or #t <= 2 then
return true
end
return getIdxOfLastElementOfNonDecreasingSubsequence(t, n + 1, #t) == -1
and ((t[n - 1] or -math.huge) <= (t[n + 1] or math.huge)
or (t[n] or -math.huge) <= (t[n + 2] or math.huge))
end