- Introduction
- Getting the Needed Files
- Task 1: Deque Interface
- Task 2: wordToDeque
- Task 3: isPalindrome
- Task 4: Generalized Palindrome and OffByOne
- Task 5: OffByN
- Frequently Asked Questions
- I can’t get the provided LinkedListDeque solution to compile.
- My implementation of LinkedListDeque or ArrayDeque won’t compile.
- My code passes all my tests, but fails some autograder tests.
- The Autograder doesn’t like my tests.
- Only my tests are failing. What tests am I missing?
- I’m failing the TestPalindrome or TestOffByOne tests but I feel like my tests are good.
- What’s with the weird static Palindrome palindrome = new Palindrome(); stuff?
- Deliverables
Introduction
In most of your prior programming assignments, you’ve relied on some external source of truth to tell you that your code was correct.
In this project, you’ll use your one of your deques from project 1A to solve a real world problem. Along the way, you’ll also write tests of your application to convince yourself that everything works correctly.
Unlike Project 1A, this project will be more highly scaffolded to reduce the workload in anticipation of the midterm.
Warning: The autograder output for this project is going to be terse and unhelpful. This is because we want you to use your tests to build confidence in your code. You will not be able to rely on the autograder for correctness.
Getting the Needed Files
Skeleton Files
As before, pull the skeleton using the command git pull skeleton master
.
In the skeleton, we have provided the following files:
PalindromeFinder.java
: Class that helps identify generalized Palindromes in English.CharacterComparator.java
: An interface for comparing characters.TestPalindrome.java
: A class containing JUnit tests forPalindrome
.TestOffByOne.java
: A class containing JUnit tests forOffByOne
.
In addition you will create the following files:
Palindrome.java
: A class for palindrome operations.OffByOne.java
: A class for off-by-1 comparators.OffByN.java
: A class for off-by-N comparators.
You’ll also need to cd into your library-sp19
folder. Once you’re there, use git pull origin master
. If everything works as it should, you should see a file called words.txt
appear in the library-sp19/data
folder.
In summary, these should be the shell commands to use:
$ git pull skeleton master
$ cd library-sp19
$ git pull origin master
If that didn’t work, try git submodule update --recursive --remote
from your personal sp19-s???
folder.
Note: We’ve set up your git repository so that it will reject words.txt
by default.
For those of you who know that this means: Please don’t use the -f
command to force
this large file into your repo. It will slow down the autograder.
Additional Optional Manual Download
For this assignment, you’ll also need a correct deque implementation. You are
welcome to use your LinkedListDeque
or your ArrayDeque
from Part1A. If you’re not
sure if your solution to project 1a is correct, or you just didn’t finish,
you may download a correct implementation of LinkedListDeque
by left clicking on
this link, and manually copying and pasting
the displayed code.
Setting up via Intellij
You can import the proj1b
folder into Intellij as normal. However, we’ve seen a few issues with students’ Intellij not recognizing the code as Java because most of it is commented out. There are a few fixes to this issue:
- Mark the source directory (
proj1b
) as “Sources Root”. You can right click theproj1b
directory in Intellij -> Mark As -> Source Root. - Uncomment
TestPalindrome.java
andTestOffByOne.java
, and try reimporting again.
Task 1: Deque Interface
This first task is going to be a little tedious, but it won’t take long.
Create an interface in a new file named Deque.java
that contains all of the
methods that appear in both ArrayDeque
and LinkedListDeque
.
See the project 1a spec for a concise list.
In IntelliJ, use “New->Java Class”. IntelliJ will assume you want a class, so make
sure to replace the class
keyword with interface
.
Create this interface and add all the methods. For the isEmpty()
method,
give it a default
implementation, which returns true
if the size()
is 0
.
Notice that since both your LinkedListDeque
and ArrayDeque
probably use an
implementation like this, now that we have this default implementation, we could
delete the duplicate implementations inside of the two aforementioned concrete
classes (you can go ahead and delete them if you like).
Modify your LinkedListDeque
and/or ArrayDeque
so that they implement the Deque
interface by adding implements Deque<Item>
to the line declaring the existence of the
class. If you used something other than Item
for your generic type parameter, use
that instead. Add @Override
tags to each method that overrides a Deque
method.
Note: If you’re using the provided solution for LinkedListDeque
, which relies on
some inheritance black magic, your class definition should look like
public class LinkedListDeque<Item> extends LinkedList<Item> implements Deque<Item>
.
Task 2: wordToDeque
Create a new file called Palindrome.java
, and add a method with the signature
shown below:
public Deque<Character> wordToDeque(String word)
Don’t write any code yet for this method. For now, just have it return null
so that Palindrome.java
can compile.
Given a String
, wordToDeque
should return a Deque
where the characters appear
in the same order as in the String. For example, if the word is “persiflage”, then
the returned Deque
should have ‘p’ at the front, followed by ‘e’, and so forth.
Don’t implement wordToDeque yet!
Uncomment the code in TestPalindrome
and run the test contained in the file
(e.g. by right-clicking on it and picking Run TestPalindrome
). You should fail
the provided test. Your goal is to now pass this test by correctly implementing
wordToDeque
. Once you’ve passed the test, move on to the next part of this
assignment. Make sure that you don’t delete the weird line static Palindrome
palindrome = new Palindrome();
. It’s not useful for this task of the assignment,
but it’ll be necessary later.
Tip: Search the web to see how to get the i-th character in a String.
Tip: Inserting chars into a Deque<Character>
is just like inserting ints into
a LinkedListDeque<Integer>
.
Note: The careful reader of testWordToDeque
might wonder why we didn’t just
create a correct Deque
and then call assertEquals
. The reason is that our
Deque
class does not provide an equals
method and thus it won’t work the way
you expect. We’ll be talking about this in class soon.
Tip: If you’re failing your own test and can’t figure why, remember you have a debugger. Use it! Don’t just stare at your code looking for the bug. That’s too slow and tedious.
Task 3: isPalindrome
Task 3A: isPalindrome Testing
Now that you’re passing the test and getting to enjoy the nice green glow of the success bar, let’s break things again.
Modify your Palindrome.java
so that it now has a second method with the signature
below.
public boolean isPalindrome(String word)
For now, have it return a dummy value. A dummy value is just some arbitrary thing
you select, i.e. either true or false. Before we write the method itself, we’re
going to write a test. Let’s start by discussing what isPalindrome
is supposed to
do.
The isPalindrome
method should return true
if the given word is a palindrome,
and false
otherwise. A palindrome is defined as a word that is the same whether
it is read forwards or backwards. For example “a”, “racecar”, and “noon” are
all palindromes. “horse”, “rancor”, and “aaaaab” are not palindromes. Any word
of length 1 or 0 is a palindrome.
‘A’ and ‘a’ should not be considered equal; you don’t need to do anything special for capital letters to work properly. In fact, if you forget that capital letters exist, your code will work fine.
Add at least one test to TestPalindrome
that tests the isPalindrome
method.
You’ll probably find the assertTrue
and assertFalse
methods to be useful.
You’re also welcome to use any other methods in the
JUnit documentation.
Ideally, you should write several tests, and not just one, but it’s up to you. It’s
ok to have multiple asserts in one test, though don’t go too wild. Make sure to
annotate your tests with @Test
, otherwise JUnit won’t run your tests.
When you run TestPalindrome
again, your code should fail the (hopefully multiple)
tests.
Tip: As an example, assertFalse(palindrome.isPalindrome("cat"));
tests to ensure
that “cat” is not considered a palindrome.
Tip: If you’re looking for more interesting things to test, read this section carefully for any interesting corner cases, and ensure that your tests check those corner cases.
Task 3B: isPalindrome
Now that you have a failing test, implement the isPalindrome
method. Use your
wordToDeque
method to give yourself an easier time. While you can technically not
use a Deque
at all, we strongly encourage you to do so. It’s a good exercise in
understanding how your choice of data structures (in this case, Deque
) will have
a profound effect on how you write your code.
Once you’ve passed your own tests, you’re ready to move on. Keep in mind that our autograder is going to be very quiet, so you’ll want to make sure your tests are thorough so that you feel good about your code. At the very least, you should have at least one test that checks that some word is a palindrome, and one that checks that some word is not a palindrome, as well as two interesting corner cases.
Tip: Consider recursion. There’s a really beautiful solution that uses recursion. You’ll need to create a private helper method for this to work.
Tip: Don’t use the get
method of Deque. That will just make things unnecessarily
complicated.
Just for fun: Uncomment the code in the provided PalindromeFinder.java
class and you’ll get a list of all palindromes of length 4 or more in English
(assuming you also downloaded the provided words file).
Tip: If you’re failing your own test and can’t figure why, remember you have a debugger. Use it! Don’t just stare at your code looking for the bug. That’s too slow and tedious.
Task 4: Generalized Palindrome and OffByOne
For this task, you will do six things. Our suggested order is given below:
- Create a class called
OffByOne
that implementsCharacterComparator
. - Add tests to
TestOffByOne
for theequalChars
method in theOffByOne
class. - Complete the
equalChars
method and verify that it works. - Add a new method that overloads
isPalindrome
. - Add tests to
TestPalindrome
that tests your new method inisPalindrome
. It’s ok to usenew OffByOne()
for these tests. - Complete the new method in
isPalindrome
and verify that it works.
However, you’re welcome to do them in any order you choose. For this task, rather than carefully enumerating everything you’re supposed to do, as in the tasks above, we will simply give a general description of your goal.
In this task, your ultimate goal is to add a third public method to your Palindrome
class with the
following signature:
public boolean isPalindrome(String word, CharacterComparator cc)
The method will return true
if the word is a palindrome according to the
character comparison test provided by the CharacterComparator
passed in as
argument cc
. A character comparator is defined as shown below:
/** This interface defines a method for determining equality of characters. */
public interface CharacterComparator {
/** Returns true if characters are equal by the rules of the implementing class. */
public boolean equalChars(char x, char y);
}
For this task, you’ll also create a class called OffByOne.java
, which should implement
CharacterComparator
such that equalChars
returns true
for characters that are
different by exactly one. For example the following calls to obo
should
return true
. Note that characters are delineated in Java by single quotes, in
contrast to Strings, which use double quotes.
OffByOne obo = new OffByOne();
obo.equalChars('a', 'b'); // true
obo.equalChars('r', 'q'); // true
However, the three calls below should return false
:
obo.equalChars('a', 'e'); // false
obo.equalChars('z', 'a'); // false
obo.equalChars('a', 'a'); // false
Note: Characters in Java include non-alphabetical characters. For example ‘%’ and ‘&’ are off by one. This might seem strange (especially since they’re not even next to each other on the keyboard), but char values in Java are really just integers. For example ‘%’ is actually just another way of writing 37, and ‘&’ is another way of writing 38. That is, the code below is valid and the first print statement will print 38. The second two print statements are exactly equivalent, and they both simply print 1.
int x = '&';
System.out.println(x); // prints 38
System.out.println(38 - 37); // prints 1
System.out.println('&' - '%'); // prints 1
Thus the method call below should return true:
obo.equalChars('&', '%');
Similarly, ‘a’ and ‘B’ are NOT off by one, since ‘a’ - ‘B’ is 31. If you’re curious about the specific values for many familiar characters, see the table at the bottom of this wikipedia article.
To allow for odd length palindromes, we do not check the middle character for equality with itself. So “flake” is an off-by-1 palindrome, even though ‘a’ is not one character off from itself.
As with our earlier isPalindrome
method, any zero or 1 character word is considered a palindrome.
Tip: Make sure to include @Override
when implementing equalChars
. While it
has no effect on the function of your program, it’s a good habit for the
reasons detailed in lecture.
Tip: To calculate the difference between two chars, simply compute their
difference in java. For example int diff = 'd' - 'a';
would return diff
as -3
.
Tip: Even though a good solution for Palindrome and OffByOne should not explicitly worry about non-alphabetical characters or uppercase letters, your tests could hypothetically be run on a poor solution, and thus in that case should try to cause errors that only apply to non-alphabetical characters.
Just for fun: Try printing out all off-by-one palindromes of length 4 or more
in English (assuming you also downloaded the provided dictionary) by modifying
PalindromeFinder.java
. For example “flake” is an off-by-1 palindrome since “f”
and “e” are one letter apart, and “k” and “l” are one letter apart.
Tip: If you’re failing your own test and can’t figure why, remember you have a debugger. Use it! Don’t just stare at your code looking for the bug. That’s too slow and tedious.
Task 5: OffByN
In this last part, you will implement a class OffByN
, which
should implement the CharacterComparator
interface, as well as a single
argument constructor which takes an integer. In other words, the callable
methods and constructors will be:
OffByN(int N)
equalChars(char x, char y)
The OffByN
constructor should create objects whose equalChars
method
return true
for characters that are off by N
. For example the call to equal
chars below should return true
, since “a” and “f” are off by 5 letters, but the
second call would return false
since “f” and “h” are off by 4 letters.
OffByN offBy5 = new OffByN(5);
offBy5.equalChars('a', 'f'); // true
offBy5.equalChars('f', 'a'); // true
offBy5.equalChars('f', 'h'); // false
For this task, if you choose to write tests, you’ll need to make your own test file. Make
sure to include the appropriate import
statements, which you can copy and paste from
our two provided test files. Unlike the other test files, you’re welcome to use new
in your tests. Due to technical limitations we will not test your TestOffByN.java
file if you create one,
but you still might find it useful to create such tests.
Just-for-fun: Try modifying PalindromeFinder.java
so that it outputs a list of
offByN palindromes for the N
of your choosing.
Just-for-more-fun: For what N
are there the most palindromes in English? What
is the longest offByN palindrome for any N
?
Frequently Asked Questions
I can’t get the provided LinkedListDeque solution to compile.
Make sure your class definition is
public class LinkedListDeque<Item> extends LinkedList<Item> implements Deque<Item>
.
My implementation of LinkedListDeque or ArrayDeque won’t compile.
Make sure your class definition ends with implements Deque<Item>
, or if your code
doesn’t use Item
, replace this with whatever generic parameter type variable you used.
My code passes all my tests, but fails some autograder tests.
Try to think about corner cases that you may not be covering. Re-read the corresponding section of the spec carefully to identify them. Then write your own tests that test these corner cases, and ensure your code passes them.
The Autograder doesn’t like my tests.
Make sure that you’re not using words.txt
anywhere in your tests. The autograder does
not have access to this file.
Only my tests are failing. What tests am I missing?
Probably corner cases.
I’m failing the TestPalindrome or TestOffByOne tests but I feel like my tests are good.
Make sure your TestPalindrome
does not say new Palindrome
anywhere. Similarly, make
sure your TestOffByOne
does not say new OffByOne
anywhere.
What’s with the weird static Palindrome palindrome = new Palindrome(); stuff?
In order to create JUnit tests for your JUnit tests, we had to resort to some clever
hacks, and the easiest way involved this weird stuff. Sorry. Luckily in TestOffByN
you
don’t have to worry about it.
Deliverables
Deque.java
(created by you)Palindrome.java
(created by you)OffByOne.java
(created by you)OffByN.java
(created by you)TestPalindrome.java
TestOffByOne.java