Palindrome

Hello,
I want to write a program that determines whether a sentence is a palindrome or not. I wrote the following program and it works, but I want to know if this piece of code is flawed from a programming science perspective:

function palindrome(str)
    ch = ""
    temp = ""
    str = lowercase(str)
    for i = 1 : length(str)
        if isletter(str[i])
            ch *= str[i]
        end
    end
    for i = length(ch) : -1 : 1
        temp *= ch[i]
    end
    if ch == temp
        return true
    else
        return false
    end
end

function main()
    print("Please enter a string: ")
    str = readline()
    if palindrome(str)
        println(str," is a palindrome.")
    else
        println(str," is not a palindrome.")
    end
end

main()

Thank you.

1 Like

You seem to like to do character-by-character parsing, but you don’t have to do those kinds of things as much anymore.

palindrome2(s) = s == reverse(lowercase(s))

It’s not exactly the same, because I didn’t do the isletter part, but it could be added without too much more effort.

palindrome3(s) = lowercase(filter(isletter, s)) == reverse(lowercase(filter(isletter, s)))

You’re treating Julia like it’s C, but it’s got a lot more to offer.

UPDATE: I added a missing lowercase call to palindrome3.

2 Likes

Incrementally building a string in this way is not recommended. A pre-allocated character array will perform better. But unless there’s a good reason not to, just use @g-gundam’s one-liner solutions.

1 Like

Well, the original specification is slightly different in that lowercase is applied to both sides as well. A short translation would be

palindrome(str) = let ch = filter(isletter, lowercase.(str))
                      reverse(ch) == ch
                  end

Imho, this should be two functions as deciding what to consider and checking for a palindrome are two orthogonal concerns, i.e.,

normalize(str) = filter(isletter, lowercase.(str))
ispalindrome(seq) = reverse(seq) == seq

const mypalindrome = ispalindrome 
2 Likes

Or don’t create a new String at all, and instead just compare (valid) characters in the input str by moving from front to back and back to front simultaneously :slight_smile:

1 Like

This depends on what your goals are. It is neither the most efficient implementation (as you create multiple extra Strings (in a suboptimal way, cf. @greatpet 's reply)), nor the shortest implementation (cf. @g-gundam, and even if you like to iterate explicitly, you could also just use return ch == temp, for example). I would also argue that “a12a” is not a palindrome.

But most often you don’t really need the fastest or shortest implementation. In this example, the IO time will likely dwarf the execution time for palindrome. In any case, the user will not notice the difference between 1 ns and 1 ms.

Hello,
Thank you so much for your reply.
I’m a newbie and learning Julia. I haven’t learned arrays yet. I have currently learned numbers, for and while loops, functions, and characters and strings in Julia.
With my current knowledge, is this program well written?

Is there a specific reason why you think your code might be “flawed”? It seems fine enough to me.

If you don’t want to use functions like (Iterators.)filter or reverse, I’m personally a bit more partial to something like

function is_palindrome(str)
    i = 1            # moves front to back
    j = length(str)  # moves back to front

    while i <= length(str) && j >= 1 
        # Move i forward to the first valid next character
        if !isletter(str[i])
            i += 1
            continue
        end

        # Move j backward to the first valid previous character
        if !isletter(str[j])
            j -= 1
            continue
        end

        lowercase(str[i]) == lowercase(str[j]) || return false
        i += 1
        j -= 1
    end
    return true
end

the interpretation of which might also be a good exercise in control flow (you could make it a bit easier by using nested while loops, potentially moved to a different function). I would also just leave out the isletter checks and lowercase conversion, but that depends on your definition of palindrome.

2 Likes

String indexing has quadratic time complexity due to the UTF-8 encoding. Using the built-in filter and reverse will be faster.

1 Like

String indexing seems pretty constant time to me?

Relevant code in string.jl
@assume_effects :foldable @inline function codeunit(s::String, i::Int)
    @boundscheck checkbounds(s, i)
    b = GC.@preserve s unsafe_load(pointer(s, i))
    return b
end

@propagate_inbounds function getindex(s::String, i::Int)
    b = codeunit(s, i)
    u = UInt32(b) << 24
    between(b, 0x80, 0xf7) || return reinterpret(Char, u)
    return getindex_continued(s, i, u)
end

function getindex_continued(s::String, i::Int, u::UInt32)
    if u < 0xc0000000
        # called from `getindex` which checks bounds
        @inbounds isvalid(s, i) && @goto ret
        string_index_err(s, i)
    end
    n = ncodeunits(s)

    (i += 1) > n && @goto ret
    @inbounds b = codeunit(s, i) # cont byte 1
    b & 0xc0 == 0x80 || @goto ret
    u |= UInt32(b) << 16

    ((i += 1) > n) | (u < 0xe0000000) && @goto ret
    @inbounds b = codeunit(s, i) # cont byte 2
    b & 0xc0 == 0x80 || @goto ret
    u |= UInt32(b) << 8

    ((i += 1) > n) | (u < 0xf0000000) && @goto ret
    @inbounds b = codeunit(s, i) # cont byte 3
    b & 0xc0 == 0x80 || @goto ret
    u |= UInt32(b)
@label ret
    return reinterpret(Char, u)
end

In particular, for ASCII characters getindex_continued will never be called.

Also note that

julia> s = "abÎłd"
"abÎłd"

julia> s[2]
'b': ASCII/Unicode U+0062 (category Ll: Letter, lowercase)

julia> s[3]
'Îł': Unicode U+03B3 (category Ll: Letter, lowercase)

julia> s[4]
ERROR: StringIndexError: invalid index [4], valid nearby indices [3]=>'Îł', [5]=>'d'
Stacktrace:
 [1] string_index_err(s::String, i::Int64)
   @ Base .\strings\string.jl:12
 [2] getindex_continued(s::String, i::Int64, u::UInt32)
   @ Base .\strings\string.jl:472
 [3] getindex(s::String, i::Int64)
   @ Base .\strings\string.jl:464
 [4] top-level scope
   @ REPL[12]:1

julia> s[5]
'd': ASCII/Unicode U+0064 (category Ll: Letter, lowercase)

For non-ASCII strings the above is_palindrome and original palindrome implementations would then fail (and are hence indeed flawed to some extent), while reverse would work. As a compromise you could change the indices i and j into Chars obtained from iterating over str and Iterators.reverse(str) via iterate.

2 Likes

You’re conpletely right, I totally forgot that Julia guaranteed constant time string indexing. It’s just that the getindex result may not be an actual character.

1 Like

You just need to use nextind and prevind to increment and decrement the index, rather than += 1 and -= 1.

1 Like

Thanks for cleaning it up.

Hello,
Thanks again.
That’s why I asked because I’m a novice and I want to know if I’m on the right track or not?
How can I calculate the execution time of the program?

I’d say you’re on the right track if you don’t want to use too many of the built-in features of the language. But as highlighted by @greatpet and @stevengj, Unicode strings (using characters from outside the Latin alphabet, requiring potentially more than 1 byte for a given Char) will lead to complications and we cannot just use simple incremental indexing (for i = 1:length(str) or i += 1), though for i = eachindex(str) is fine. As long as you intend the user to only supply simple ASCII strings (which is mostly sufficient for the English language), you don’t have to worry too much about that though, but it’s still good to keep in mind (and document).

You could look into theoretical computational complexity (the constant time and quadratic time complexity mentioned above). But you could also just measure the execution time, e.g. via BenchmarkTools.jl’s @btime and @benchmark:

using BenchmarkTools
using Random  # for randstring to generate a random String

function palindrome1(str)  # Made Unicode-proof
    ch = ""
    temp = ""
    str = lowercase(str)

    i = 1  # Will be a byte-level index
    while i <= sizeof(str)  # sizeof returns the byte-length
        if isletter(str[i])
            ch *= str[i]
        end
        i = nextind(str, i)
    end
    
    i = sizeof(ch) + 1  # Beyond the last byte (which might or might not already correspond to a full Char)
    i = prevind(ch, i)  # Now the start of the last Char in ch
    while i >= 1
        temp *= ch[i]
        i = prevind(ch, i)
    end

    return ch == temp
end

palindrome2(str) = let ch = filter(isletter, lowercase.(str))  # (Already worked fine)
    reverse(ch) == ch
end

function palindrome3(str)  # Also made Unicode-proof
    i = 1                                     # moves front to back
    j = sizeof(str) + 1; j = prevind(str, j)  # moves back to front

    while i <= j  # (Note: Changed to exploit symmetry)
        # Move i forward to the first valid next character
        if !isletter(str[i])
            i = nextind(str, i)
            continue
        end

        # Move j backward to the first valid previous character
        if !isletter(str[j])
            j = prevind(str, j)
            continue
        end

        lowercase(str[i]) == lowercase(str[j]) || return false
        i = nextind(str, i)
        j = prevind(str, j)
    end
    return true
end

# Below we return the minimal (best) execution time over a number of runs (determined automatically)
# for checking that a random string (not the same one each time) of length 1000 is a palindrome.
# We do not include the creation of the string to test in the timing.
# (By default randstring only uses standard Latin letters and digits, hence only ASCII character)

# Very likely non-palindromes:
@btime palindrome1(s) setup=(s = randstr(1000));  #  97.800 ÎĽs (1590 allocations: 673.77 KiB)
@btime palindrome2(s) setup=(s = randstr(1000));  #  11.800 ÎĽs (7 allocations: 6.30 KiB)
@btime palindrome2(s) setup=(s = randstr(1000));  #  19.358 ns (0 allocations: 0 bytes)
# (We immediately return False after comparing the first and last character.)

# Palindromes:
@btime palindrome1(s) setup=(s = randstr(500); s *= reverse(s));  #  96.200 ÎĽs (1556 allocations: 646.67 KiB)
@btime palindrome2(s) setup=(s = randstr(500); s *= reverse(s));  #  11.700 ÎĽs (7 allocations: 6.30 KiB)
@btime palindrome2(s) setup=(s = randstr(500); s *= reverse(s));  #  10.900 ÎĽs (0 allocations: 0 bytes)

For interactive usage 100 µs is negligible, so we really don’t have to worry much about computational efficiency here.

1 Like

Is this different from simply using j = lastindex(str)?

2 Likes

No, that should be the same. For some reason (I guess confusion between byte- and Char-indexing) I just didn’t think of lastindex, which would be better in every way.

help?> prevind
search: prevind

  prevind(str::AbstractString, i::Integer, n::Integer=1) -> Int

    •  Case n == 1
       (...) If i is equal to ncodeunits(str)+1 return lastindex(str). Otherwise throw BoundsError.
(...)