Win a copy of Kotlin in Action this week in the Kotlin forum!
  • Post Reply Bookmark Topic Watch Topic
  • New Topic

Where is my palindrome checker failing?  RSS feed

 
Jose Castillo
Greenhorn
Posts: 13
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
First of all, here's my code with an explanation afterwards



I am supposed to essentially take a grouping of files in a folder, read them in, and determine if they are any sort of palindrome (Line means it's mirrored by line, panema means it starts with "A man, a plan, a "..., word means it reads the same back and forwards, and char palindrome is what most people think of when they think of palindromes)

Here's my return. Files starting with c should be character palindromes, starting with an l is a line palindrome, p a panama palindrome, etc. z files are supposed to fail all tests.




I am not quite sure where I am going wrong. I want to work through it, but I feel I've tried what I can. If someone could just point out which parts of my code are failing me, so I could try and fix them myself I would appreciate it. I will be on here, so if I'm unclear on anything let me know! I know my code isn't the cleanest, and I do plan to clean it up when I can.

Thanks
J
 
Winston Gutkowski
Bartender
Posts: 10573
65
Eclipse IDE Hibernate Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Jose Castillo wrote:I am not quite sure where I am going wrong. I want to work through it, but I feel I've tried what I can. If someone could just point out which parts of my code are failing me, so I could try and fix them myself I would appreciate it.

Well, I can't do that, but I can suggest a few things:
1. Write out in English what the word "palindrome" means - ie, a description that answers the question: What is a "palindrome"?

2. Now write out, more specifically, what it means for each of your three types: line, word and character (I'm still not sure what this "panama" thing is), including any specific rules that you've been given.

3. Save what you've written and start a new program that tackles ONE of your palindrome types only. And don't work on anything else until it passes all of your test files - and you might want to add some more of your own for any specific tests that you come up with.

4. When - and ONLY when - that program works, every time, save it and start a new program that deals with another palindrome type. And go through the same process.

5. When you're finished you should have three (or four) programs that work for each type of palindrome. Now you have two choices:
a. You can copy and paste the code that you now know works into a new program that handles all three cases.
b. You can write a new program that calls each of your three programs in turn for all the files in your list.
Personally, I prefer the latter; but it's up to you.

I will be on here, so if I'm unclear on anything let me know!

You may be, but it beddie-byes time here, so good luck!

HIH

Winston
 
Jose Castillo
Greenhorn
Posts: 13
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Winston Gutkowski wrote:1. Write out in English what the word "palindrome" means - ie, a description that answers the question: What is a "palindrome"?


A palindrome is a string of text that reads the same, forwards and backwards. There are a few types:



Winston Gutkowski wrote:2. Now write out, more specifically, what it means for each of your three types: line, word and character (I'm still not sure what this "panama" thing is), including any specific rules that you've been given.

1. A line Palindrome: It reads the same bottom-to-top, as top to bottom. As an example:

This is a line Palindrome
It's not very interesting
It's not very interesting
This is a line Palindrome

2. A word palindrome reads the same word by word backwards and forwards. As an example:

This is a word palindrome word a is This

3. Character palindromes are basically words/phrases that spell out the same backwards and forwards. For example:

racecar

4. A panema palindrome. Starts with the phrase "A man, a plan, a canal". I.e:

A man, a plan, a canal - Panama!


In all these cases, special characters are ignored. White space is removed in the case of the Character palindrome. We must have a singular method to check for palindromes, only read in each file once. Stacks and queues must be used.


Here is how I am approaching the issue, in pseudo code I am rewriting the code as we speak, so I made some tiny modifications:

In the main method:
1. Split the .txt file into lines, while removing all special characters
2. Push these lines into a queue, lineQueue
3. Send the queue to a method, named isPalindrome

isPalindrome:
1. Create a stack, stack1, and dequeue all items in lineQueue
2. Create a stack, stack2, and pop half of stack1 into it.
3. If stack 1 > stack 2 or stack 2 > stack 1, pop the bigger one so they are even
4. Pop stack 1 and stack 2 into temporary strings, and compare the items. If they are not the same, they must not be palindromes, so return false If they're the same, go on until the stacks are empty and return true.

main method:
4. Set a boolean, isLinePalindrome to true or false based on the isPalindrome method
5. Take the lineQueue, split it word-by-word, and enqueue each word into a queue named "wordQueue"
6. Use the isPalindrome method on wordQueue, and set it to isWordPalindrome

7. Take the wordQueue, split by character (spaces were removed w/ delimiter when splitting word by word), put those charectars into a queue, charQueue
8. Use the isPalindrome method on charQueue, set result to isCharPalindrome

9. If isCharPalindrome == true, run isPanemaPalindrome

isPanemaPalindrome:
1. Take the first 11 charecters out of charQueue. If they are equal to "amanaplanac", set isPanemaPalindrome to true.

10. Print all the results out nicely, which I have already solved.


I am going to try rewriting the whole class to see if I can see what mistake I made. I will update when I'm done.
 
Knute Snortum
Sheriff
Posts: 4073
112
Chrome Eclipse IDE Java Postgres Database VI Editor
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

isPalindrome:
1. Create a stack, stack1, and dequeue all items in lineQueue

An "item" can be a line, word, or character -- correct?

2. Create a stack, stack2, and pop half of stack1 into it.
3. If stack 1 > stack 2 or stack 2 > stack 1, pop the bigger one so they are even

What will happen with the example you gave for a char palindrome "racecar"?
 
Knute Snortum
Sheriff
Posts: 4073
112
Chrome Eclipse IDE Java Postgres Database VI Editor
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
When you rewrite this class, don't put more than a line or two in the main() method. About all main should do is launch your app. See Main is a Pain.
 
Jose Castillo
Greenhorn
Posts: 13
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Knute Snortum wrote:

isPalindrome:
1. Create a stack, stack1, and dequeue all items in lineQueue

An "item" can be a line, word, or character -- correct?

2. Create a stack, stack2, and pop half of stack1 into it.
3. If stack 1 > stack 2 or stack 2 > stack 1, pop the bigger one so they are even

What will happen with the example you gave for a char palindrome "racecar"?


1. In the case of isPalindrome, you've got it.

2. If the line racecar is fed in, here is what ought to happen, I believe:

First, it would test to see if it is a line palindrome. It is one line, so it is not. Then, check to see if it's a word palindrome, which, being one word it is not. Then, it would:
1. Push racecar into stack1
2. Pop half of it into stack2, so stack1 contains race, and stack2 contains car
3. It would detect stack1 is 1 char higher, and pop off the e


Then it would compare each letter (thinking about this now, stack2 may have to be a queue), and find it to be a char palindrome.
 
Knute Snortum
Sheriff
Posts: 4073
112
Chrome Eclipse IDE Java Postgres Database VI Editor
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I can't find anything in the standard Java libraries that is a LinkedStack or a LinkedQueue -- are these custom classes? And you can only use them? There is a way to check for palindromes with an ArrayList that doesn't require you to dequeue half of your queue -- and as you've seen, this method has its problems. I don't know if you can do it with LinkedStack or LinkedQueue but it would be worth your while to look into it. That, or solve the problem of an odd number of items.

Also, I think you say that you remove all your whitespaces when checking for a line palindromes, but what happens when you need to check for word palindromes?
 
Jose Castillo
Greenhorn
Posts: 13
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Knute Snortum wrote:I can't find anything in the standard Java libraries that is a LinkedStack or a LinkedQueue -- are these custom classes? And you can only use them? There is a way to check for palindromes with an ArrayList that doesn't require you to dequeue half of your queue -- and as you've seen, this method has its problems. I don't know if you can do it with LinkedStack or LinkedQueue but it would be worth your while to look into it. That, or solve the problem of an odd number of items.

Also, I think you say that you remove all your whitespaces when checking for a line palindromes, but what happens when you need to check for word palindromes?


In effect, linkedstack and linkedqueue and standard queues and stacks implemented using singly linked lists. You got it, I can only use this, no arraylists.

For white spaces, they are NOT removed for line palindromes, but when breaking the words up for a word palindrome, I use " " as a delimiter, which, to my knowledge, removes spaces around the words.
 
Knute Snortum
Sheriff
Posts: 4073
112
Chrome Eclipse IDE Java Postgres Database VI Editor
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
2. If the line racecar is fed in, here is what ought to happen, I believe:

First, it would test to see if it is a line palindrome. It is one line, so it is not. Then, check to see if it's a word palindrome, which, being one word it is not. Then, it would:
1. Push racecar into stack1
2. Pop half of it into stack2, so stack1 contains race, and stack2 contains car
3. It would detect stack1 is 1 char higher, and pop off the e

That sounds like it will work. Determining what is "half" in this situation will be critical.

BTW, use the Preview button (right next to the Submit button) to determine if your tags are correct.
 
Jose Castillo
Greenhorn
Posts: 13
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Doing some writing it out, I've determined I can write my isPalindrome method a bit more simply, with just one stack and the queue provided:



Walking through this, it appears to be correct. However, when I comment off my attempt to make degenerate cases false (i.e., one line, one word, one char), it changes the bulk of my responses to yes.

So that must mean I have to be going wrong in my processing of files into queues of lines, words, and characters.
 
Knute Snortum
Sheriff
Posts: 4073
112
Chrome Eclipse IDE Java Postgres Database VI Editor
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
For white spaces, they are NOT removed for line palindromes, but when breaking the words up for a word palindrome, I use " " as a delimiter, which, to my knowledge, removes spaces around the words.

You are correct, as in:

But there is a better way using a regex that I think you almost had in your first program:

But if you are doing this to the String first:

...you've already taken care of multiple spaces.

BTW, I would probably do the first replaceAll() like this:

I think it's a little more clear.
 
Knute Snortum
Sheriff
Posts: 4073
112
Chrome Eclipse IDE Java Postgres Database VI Editor
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Walking through this, it appears to be correct. However, when I comment off my attempt to make degenerate cases false (i.e., one line, one word, one char), it changes the bulk of my responses to yes.

So that must mean I have to be going wrong in my processing of files into queues of lines, words, and characters.

The method is looking better. Maybe put a System.out.println() at the top to print out what's being sent into the method.

Some other things:

This should probably be:

I understand the first if, but not the reason for the second if.
 
Jose Castillo
Greenhorn
Posts: 13
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Knute Snortum wrote:
Walking through this, it appears to be correct. . . .

The method is looking better. . . .


My thought with the 2 if statements was, I wasn't quite sure how the half would split it. After thinking about it, you're right.

I don't have a tostring method for my LinkedQueue class, so I am not able to print it out right off the bat in the method.
 
Winston Gutkowski
Bartender
Posts: 10573
65
Eclipse IDE Hibernate Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Jose Castillo wrote:Here is how I am approaching the issue, in pseudo code I am rewriting the code as we speak, so I made some tiny modifications:

No matter. However, I think you may have leapt to implementation a bit too soon. One of the most important (and interesting) requirements of your problem is that you must use the same method to check if your lines/words/characters are "palindromic".

That suggests two things to me:
1. You need to refine your first description of "palindrome" (which was fine as a 'first cut', BTW) to replace "string of text" with something more generic since, in at least one case, you are NOT comparing strings of text; you're comparing lines.
2. Since you have to use the same method for all palindrome checks, it also has to be generic, which suggests to me that it should use Java generics. I presume you've covered this on your course.

Let me give you an example of what I mean for #1:
Palindrome - A "palindrome" is a collection of 2 or more items, ordered in such a way that if you successively take 1 item from each end, moving towards the middle until either no items are left, or only one is, every pair of items extracted is equal.

Now your description doesn't have to be the same (in fact, it's probably better if it isn't), but it needs to be generic enough to cover all your cases, and specific enough to describe precisely what it means to be "palindromic".

As to your implementation: Knute seems to be helping you splendidly. The only thing I'd suggest is that, since your method logic has to change the contents of the queue you pass to it, either:
(a) make absolutely sure that you don't need it again;   or
(b) copy it before you use it.

HIH

Winston
 
Consider Paul's rocket mass heater.
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!