Here is my script:
local function firstLetter(str) return str:sub(1, 1) end local function lastLetter(str) return str:sub(-1) end local function middleLetters(str) return str:sub(2, -2) end local function isPalindrome(str) print(str) -- this prints rotor then oto then t local fLetter = firstLetter(str) local lLetter = lastLetter(str) local mLetters = middleLetters(str) if str:len() <= 1 then print(str) -- this prints t as it should return true -- this should end the function right? else if fLetter:lower() == lLetter:lower() then isPalindrome(mLetters) else return false end end end local str = "rotor" local pValue = isPalindrome(str) print(pValue) -- when I print this the output is nil
My main question is why is this returning nil when it should be returning true? In a previous question I asked @BlueTaslem said that the middleLetters function is not a good idea when working with large strings. Is there any way I can fix that? Thanks!
The culprit is line 37
. You write
isPalindrome(mLetters)
instead of
return isPalindrome(mLetters)
The first one returns it to nothing, and thus the function concludes by returning nil
(by default). If you replace it with the second version things should check out.
Ok, to address the second part of the question.
One thing you might be able to do to make it more efficient is by first converting the string to an array.
local stringArray = {} for i=1, #str:len() do stringArray[i] = str:sub(i, i) end
This should only be around O(n)
amortized, which is good. We're converting it to an array so that we can directly index letters and pass this around without too much overhead.
With this, we can rewrite the isPalindrome()
function
local function isPalindrome(str, startIndex, endIndex) local stringArray local length if type(str) == "string" then stringArray = {} length = str:len() for i=1, length do stringArray[i] = str:sub(i, i) end else stringArray = str end startIndex = startIndex or 1 endIndex = endIndex or length local fLetter = stringArray[startIndex] local lLetter = stringArray[endIndex] if endIndex - startIndex <= 1 then return true elseif fLetter:lower() == lLetter:lower() then return isPalindrome(stringArray, startIndex + 1, endIndex - 1) end return false end
As you can see, I've ditched the supporter functions and everything's contained within one more compact isPalindrome()
function. The idea behind the modifications is that everything's inplace and that we only have to communicate information about indices between function calls instead of feeding the string each time and then further modifying that during each iteration.
To see if our hard work actually made the code more efficient, let's test its speed!
-- Test efficiency local startTime = tick() local testString = "1234567890098765432112345678900987654321" for i=0, 100000 do -- run 100k times local palindrome = isPalindrome(testString) end local endTime = tick() print(endTime-startTime)
For your original function, it took around 3.48
seconds.
For the modified version, it only took 3.12
seconds.
This amounts to only about an 11% speed improvement, which is dismally small given how many modifications we made. However, 11% could also mean the difference between a player quitting your game due to lag and a player enjoying your game for what it is. Plus, this is recursive, so there's always going to be that added function call overhead slowing us down.
Still, I think we can do better. In fact, I'm sure we can. What I wrote was hastily scribbled and was treated with very limited foresight. It definitely can be optimized further.
But I think we're reinventing the wheel here...
It's returning nil because if you input a string with more than one character, your code doesn't return true.
On line 37, you say isPalindrome(mLetters)
but you should return that value, so if for every iteration it is a valid palindrome, then the whole word is a palindrome and you should return true. If one of the cases returns false, your entire word would return false.
So change line 37 to return isPalindrome(mLetters)