Scripting Helpers is winding down operations and is now read-only. More info→
Ad
Log in to vote
1

Why is this function returning nil when it should be returning true?

Asked by 5 years ago
Edited 5 years ago

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!

0
The reason it's not a good idea is because of its efficiency, as BlueTaslem had previously pointed out. If you made references instead of duplicating the parts of the string, then the efficiency as well as memory utilization would be significantly improved thebayou 441 — 5y
0
answered thebayou 441 — 5y

2 answers

Log in to vote
1
Answered by
thebayou 441 Moderation Voter
5 years ago
Edited 5 years ago

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.

EDIT:

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...

string.reverse()

0
Thanks for your help. I now realize that the variable would equal the first incarnation(per se) of the function. Is there any way you could answer the second part of my question though? User#21908 42 — 5y
0
Although with larger amounts af data I am sure it woull prove to create a more signifigant performance change. User#21908 42 — 5y
0
Thank you so much! User#21908 42 — 5y
Ad
Log in to vote
0
Answered by
chomboghai 2044 Moderation Voter Community Moderator
5 years ago

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)

0
I already answered the question with the same solution you posted, but good extra explanation thebayou 441 — 5y

Answer this question