Sunday, October 30, 2011

Program to Test if a Word is a Palindrome.

Problem: "A palindrome is a word that reads identically backward and forward, such as level or noon. Write a predicate method isPalindrome(str) that returns true if the string str is a palindrome. In addition, design and write a test program that calls isPalindrome to demonstrate that it works. In writing the program, concentrate on how to solve the problem simply rather than how to you make your solution more efficient." (Roberts ch 10, problem 6.)

What it looks like:
/* File: PalindromeTester
 * ----------------------------
 * This program lets a user enter in a string, and will respond with confirmation that the word is
 * or is not a palindrome. It uses a private boolean method isPalindrom(). This method goes 
 * halfway down each character of the word and compares to see whether that character and the
 * character at the mirror position on the string equal each other. If they don't, then break and 
 * returnn false, but if they do for all letters in the first half of the string, then return true.
 */

import acm.program.*;
 
public class PalindromeTester extends ConsoleProgram {
    public void run(){
        String str = readLine("Is it a palindrome? Enter string to test here:");
        if (isPalindrome(str)) {
            println("Yes it is!");
        }
        else println("No it isn't.");
    }
  

    private boolean isPalindrome(String str) {
        for (int i = 0; i < str.length()/2; i++) {          
            if (str.charAt(i) != str.charAt(str.length()-i-1)) {          
                return false;
            }                  
        }
        return true;
    }
}

What made it tough:

When I first wrote this, I had a bug. When checking to see if a word is a palindrome, the general approach is, for all charachters "i", to compare the "ith" character with its mirror character and see if they are equal, for all characters "i". So if your word is "kook", you'd compare the first last one to see if the characters are not the same (break if they're not), see if the two middle ones are the same, and so on.

In my buggy version, this is how I did the mirror check:
"if (str.charAt(i) != str.charAt(str.length()-i))"


This is the right version:
"if (str.charAt(i) != str.charAt(str.length()-i-1))"


Why do you have to subtract the extra 1 when you're trying inspect "i"'s mirror? In short because the "str.length" method counts starting at 1 when it returns how many characters a string contains, and meanwhile the charAt(i) method returns the "ith" character in a string, but counting as if the first letter of that string is 0. So because of this, the character at the second half of the word was actually always one after it should have been.

The funny thing is, when I wrote this and ran into the error, it didn't manifest itself via a warning in the Eclipse editor, or as red text showing up in my program's response. Instead the problem killed my program completely. I'd click to run the program, it would let me load up the interface for the user and enter in a word to test, and then instead of returning a result it would abort.

I'm sure there's a reason why my program reacted to the error in that particular way, but I'm not sure what that is. Thoughts?

19 comments:

  1. When your program compiles, it doesn't know how big the string its gonna be checking is. Therefore, accessing a character that is out of bounds of the string is referred to as a runtime error, because it can only occur during the run of your program. Runtime errors can often occur because of trying to manipulate data that is provided to you in a way that is illegal.

    Compile time errors are errors it can detect in your program that will occur regardless of any input provided. So, this method returns a String but, you're returning an int. The compiler can detect this and throw it's hands up at that point and go "NO GOOD!"

    ReplyDelete
  2. Josh is right: the big difference between runtime errors and compile errors is whether the compiler can detect them before running it. Compile errors usually have to do with the types of values being passed into and returned from methods, or whether a class or method exist. Runtime errors usually have to do with the values being passed around, generally not the types.

    In your case, it was a runtime error because you called the charAt method on the String class with an argument value that was out of range. While the compiler was able to reason that charAt only takes integer values, and you were passing str.length()-i, which will definitely be an integer, the compiler cannot reason about the value of that integer.

    For example, when you enter the word "noon", str.length() is equal to 4 and on the first iteration (i=0), you asked for str.charAt(str.length()-i) which is str.charAt(4) but the 4 characters in "noon" are at positions 0, 1, 2, 3 so charAt threw an exception because the position argument was out of range, but the compiler couldn't know the length of the string until you ran the program. Hence, it must be a runtime error.

    Haskell has something called "quick check" which will run your program with "random" (i.e., arbitrary, but carefully chosen) inputs and attempt to detect exactly these kind of errors. The carefully chosen values are usually boundary values, because they often cause these errors. In your case, the boundary values given to charAt would be -1, 0, 1 (to test the beginning of the string) plus str.length() and str.length()-1 (to test the end).

    ReplyDelete
  3. It's really a great and useful piece of information. I'm satisfied that you simply shared this helpful
    information with us. Please stay us informed like this.
    Thanks for sharing.

    my website online backup uk
    my web site: online backup

    ReplyDelete
  4. With havin so much content and articles do you ever
    run into any issues of plagorism or copyright infringement?
    My website has a lot of unique content I've either authored myself or outsourced but it looks like a lot of it is popping it up all over the web without my agreement. Do you know any ways to help prevent content from being ripped off? I'd definitely appreciate it.


    Here is my web-site ... insomnia video
    Stop by my web page :: insomnia funny quotes

    ReplyDelete
  5. Your style is unique in comparison to other people I've read stuff from. I appreciate you for posting when you have the opportunity, Guess I'll just book mark this
    web site.

    my weblog :: insomnia information
    Visit my site : insomnia questions

    ReplyDelete
  6. Yes! Finally someone writes about morristown.

    My homepage - online backup
    my website :: online backup solution

    ReplyDelete
  7. I all the time used to study piece of writing in news papers but
    now as I am a user of net so from now I am using net for
    articles or reviews, thanks to web.

    Feel free to surf to my site; online backup solutions
    Also visit my webpage :: online backup service reviews

    ReplyDelete
  8. Hi there are using Wordpress for your blog platform?
    I'm new to the blog world but I'm trying to get started and set up my own.
    Do you require any coding knowledge to make your own blog?

    Any help would be really appreciated!

    Here is my weblog ... insomnia 720p mkv
    Review my website - insomnia relief

    ReplyDelete
  9. Oh my goodness! Incredible article dude! Thank you so much, However I am having problems with your
    RSS. I don't know why I cannot join it. Is there anyone else getting identical RSS problems? Anybody who knows the solution will you kindly respond? Thanx!!

    my blog: insomnia youtube trailer
    My page: insomnia by elizabeth bishop

    ReplyDelete
  10. Hello, I enjoy reading through your post. I like to write
    a little comment to support you.

    Take a look at my homepage insomnia 563 bloor
    Feel free to visit my web page insomnia 3rd trimester

    ReplyDelete
  11. We are a group of volunteers and opening a new scheme in our
    community. Your website provided us with valuable
    info to work on. You have done an impressive
    job and our whole community will be thankful to you.


    Also visit my blog ... insomnia pictures
    My webpage > insomnia theater

    ReplyDelete
  12. It's appropriate time to make some plans for the longer term and it's time to be happy.
    I've learn this post and if I may I want to suggest you few fascinating issues or suggestions. Perhaps you could write next articles referring to this article. I want to learn more issues approximately it!

    My blog post; online backup storage
    Also see my website - online backup solutions

    ReplyDelete
  13. Hi, all the time i used to check blog posts here early in the morning, since i like to learn more and
    more.

    Here is my blog post; online backup software
    my website :: cheap online backup

    ReplyDelete
  14. I'm extremely inspired with your writing skills and also with the format in your weblog. Is that this a paid subject or did you modify it yourself? Anyway keep up the excellent high quality writing, it's rare
    to see a great blog like this one today..

    Take a look at my webpage ... online backup solution
    Also visit my website ; online backup solution

    ReplyDelete
  15. You have made some good points there. I checked
    on the web for additional information about the issue and found most people will go
    along with your views on this site.

    Also visit my web blog ... just click the up coming web site

    ReplyDelete
  16. Each algorithm may be 350W also cooking pot supports toward 27 oz.

    Set up, there are a few return to a little of the field of biology
    right. Some dips can be easily made in some sort of blender or maybe in a great blender.
    Just about the most couldn't match-up by using Breville's
    energy, it will do have a generation generator warranties!



    my web blog: best blenders

    ReplyDelete
  17. The particular stylish adornment means you can find more preparation suppleness or even space saving plus points.

    Pre-heat the particular convection part of short wave
    around 150 program Celsius. Choose apple sand wedges at info out there drop.

    I dislike for taking shedding weight be effective baking, point out bulgaria, mixed up.


    Here is my homepage; used convection oven for sale toronto []

    ReplyDelete
  18. Good article! We will be linking to this great content on our website.
    Keep up the good writing.

    Feel free to visit my blog More Signup bonuses

    ReplyDelete
  19. Please inform me it labored proper? I dont wish to sumit it again if i would not have to! Either the blog glitced out or im an idiot, the second option doesnt shock me lol. thanks for an ideal blog! Anyway, in my language, there are not much good source like this.
    Sarah Berger

    ReplyDelete