Assignment 3: Basic Types in Java

Programmers often find it convenient to store compound data in a text file with one line per entry. To separate the components of the entry, they use some designated symbol, such as a colon. For example, we might store movie ratings in a form like the following:

movietitle:rating:rater:date

Write and test a procedure, splitAt, that takes as input a string and a character to use in splitting the string and returns an array of the appropriate substrings. For example,

assertArrayEquals(new String[] { "a", "b", "c" },
                  StringUtils.splitAt("a:b:c", ':'));
assertArrayEquals(new String[] { "a", "b", "c" },
                  StringUtils.splitAt("a b c", ' '));
assertArrayEquals(new String[] { "a:b:c" },
                  StringUtils.splitAt("a:b:c", ' '));
assertArrayEquals("one field", new String[] { "a" },
                  StringUtils.splitAt("a", ':'));
assertArrayEquals("empty inner field", new String[] { "a", "", "c" },
                  StringUtils.splitAt("a::c", ':'));
assertArrayEquals("leading empty field", new String[] { "", "a" },
                  StringUtils.splitAt(":a", ':'));
assertArrayEquals("trailing empty field", new String[] { "a", "" },
                  StringUtils.splitAt("a:", ':'));

In implementing splitAt you may not use use the split method of java.util.String. (Yes, that's right, you have to implement a simpler version of that method by hand.)

One disadvantage of the “split at this character” strategy is that you cannot easily use the separator within one of the fields. Data designers have chosen a variety of approaches to handle the issue. One of the most common is to say “if the separator appears within text surrounded by double quotation marks, take it as part of the field, rather than as a separator”.

But even that approach has its own potential problems. For example, what if we want both the separator and a quote in a field. Once again, there is a common solution: “if two double quotation marks appear in sequence, treat them as a single character, rather than as the end of a string”.

Write and test a procedure, splitCSV, that splits a string using those policies, with a comma as the separator. For example,

assertArrayEquals(new String[] { "a", "b", "c" },
                  StringUtils.splitCSV("a,b,c"));
assertArrayEquals(new String[] { "a,b", "c" },
                  StringUtils.splitCSV("\"a,b\",c"));
assertArrayEquals(new String[] { "a", "b,b\"", "c" },
                  StringUtils.splitCSV("a,\"b,b\"\"\",c"));

You may be familiar with 133+ or leet, a form of writing in which alternate characters or sequences of characters are used in place of familiar alphabetics. For example, a plus sign (+) may be used in place of the letter t, a 3 in place of the letter e, the numeral 1 in place of the letter l, and the numeral 0 in place of the letter o. In some cases, multiple symbols are used in place of a single letter, such as a vertical bar and a 3 in place of b or B. or a vertical bar, a backslash, and a vertical bar in place of n.

Write a static method, deLeet, which takes as input a string of leet text and attempts to return the phrase in its more standard form. You should support at least the leet characters for a, b, e, l, n, and o For example,

assertEquals("e", StringUtils.deLeet("3"));
assertEquals("leet", StringUtils.deLeet("133+"));
assertEquals("eat banana", StringUtils.deLeet("3@+ |3@|\\|@|\\|@"));

You may be familiar with a classic algorithm by Shirley Ellis entitled The Name Game. Ms. Ellis describes this algorithms for developing phrases based on her colleague's names as follows:

She also gives us a number of examples:

Write a method, nameGame, that takes as input a string and returns a verse of the form Ms. Ellis suggests. Your method need not function correctly with names that begin with vowels, although you must handle situations in which the name begins with multiple consonants (as in the case of “Shirley”).

You need not write test cases for this procedure! A few simple experiments should suffice.

As you know, one of the primary uses of computers is to compute with numbers - that is, to calculate. A typical computer calculator needs to read and parse textual input, do the computation, and return a result. In this part of the assignment, we will simulate that behavior.

Write a method, eval0, that takes as input a string that represents an arithmetic expression over the integers and returns the result of evaluating that expression (as a BigInteger). You may assume that numbers and operators are separated by spaces. You should use the “naive” approach to calculation: Do operations in the order they appear, rather than paying attention to precedence. You should support the operations +, -, *, /, and ^ (exponentation). For example,

assertEquals(BigInteger.valueOf(0), Calculator.eval0("0"));
assertEquals(BigInteger.valueOf(2), Calculator.eval0("1 + 1"));
assertEquals(BigInteger.valueOf(4), Calculator.eval0("1 + 2 + 1"));
assertEquals(BigInteger.valueOf(9), Calculator.eval0("1 + 2 * 3"));

Your calculator must support arbitrarily large integers. For example, you should get the correct answer for Calculator.eval0("2 ^ 64"). You can achieve this result by using java.lang.BigInteger for your data values.

In the completely fictitious nation of Yksleber, the government has decided that using multiples of five for coin values is, well, kind of simplistic. Instead, they have chosen the “wot”, which has a value of two, the “eater”, which has a value of seven, the “stickpair”, which has a value of eleven, and the “deck”, which has a value of 54.

When making change, we like to use the fewest number of coins possible. Unfortunately, these denominations cause problems when used in conjunction with the traditional change-making algorithm of “use as many of the largest coin as possible” no longer works. For example, consider trying to make a value of 28. If you start with a stickpair (value 11), you are left with 17. If you then take another stickpair (value 11) you are left with 6. And then you take three wots. So that's five coins. But you can make 28 with four eaters.

The merchants of Yksleber have gotten very good at making change, but most of the populace find themselves challenged by this approach. And when citizens are challenged to compute, they look for smart phone apps.

Let's assume that you've been hired to implement the core of the Yksleber change app. Write a static method, fewestCoins, that takes as input a positive integer and returns an array that gives a smallest combination of coins that make up that value. (Rather than using the silly names, you should return an array of integers that represent the denominations of those coins. For example, fewestCoins(20) would return some permutation of the array { 2, 7, 11 }.)

You need not do exhaustive testing of this method. Pick a few interesting cases (like 20 and 28) and make sure that it works correctly for those.