Scripting Helpers is winding down operations and is now read-only. More info→

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

Asked by

User#21908 42

6 years ago

Edited 6 years ago

Here is my script:

01local function firstLetter(str)
02 
03    return str:sub(1, 1)
04 
05end
06 
07local function lastLetter(str)
08 
09    return str:sub(-1)
10 
11end
12 
13local function middleLetters(str)
14 
15    return str:sub(2, -2)
16 
17end
18 
19local function isPalindrome(str)
20 
21    print(str) -- this prints rotor then oto then t
22 
23    local fLetter = firstLetter(str)
24    local lLetter = lastLetter(str)
25    local mLetters = middleLetters(str)
26 
27    if str:len() <= 1 then
28 
29        print(str) -- this prints t as it should
30 
31        return true -- this should end the function right?
32 
33    else
34 
35        if fLetter:lower() == lLetter:lower() then
36 
37            isPalindrome(mLetters)
38 
39        else
40 
41            return false
42 
43        end
44 
45    end
46 
47end
48 
49local str = "rotor"
50 
51local pValue = isPalindrome(str) 
52 
53print(pValue) -- when I print this the output is nil
 View all 53 lines...

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 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 — 6y

answered thebayou 441 — 6y

2 answers

Answered by

thebayou 441

6 years ago

Edited 6 years ago

The culprit is line 37. You write

`1`	`isPalindrome(mLetters)`

instead of

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

1local stringArray = {}
2for i=1, #str:len() do
3    stringArray[i] = str:sub(i, i)
4end

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

01local function isPalindrome(str, startIndex, endIndex)
02 
03    local stringArray
04    local length
05    if type(str) == "string" then
06        stringArray = {}
07        length = str:len()
08 
09        for i=1, length do
10            stringArray[i] = str:sub(i, i)
11        end
12 
13    else
14        stringArray = str
15    end
16 
17    startIndex = startIndex or 1
18    endIndex = endIndex or length
19 
20    local fLetter = stringArray[startIndex]
21    local lLetter = stringArray[endIndex]
22 
23    if endIndex - startIndex <= 1 then
24        return true
25 
26    elseif fLetter:lower() == lLetter:lower() then
27        return isPalindrome(stringArray, startIndex + 1, endIndex - 1)
28    end
29 
30    return false
31end
 View all 31 lines...

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!

01-- Test efficiency
02 
03local startTime = tick()
04 
05local testString = "1234567890098765432112345678900987654321"
06 
07for i=0, 100000 do  -- run 100k times
08    local palindrome = isPalindrome(testString)
09end
10 
11local endTime = tick()
12 
13print(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()

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 — 6y

Although with larger amounts af data I am sure it woull prove to create a more signifigant performance change. User#21908 42 — 6y

Thank you so much! User#21908 42 — 6y

Answered by

chomboghai 2044

6 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)

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

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

2 answers

EDIT:

Answer this question