Update: I've removed the Java 8 stuff, and I can't remember if Generics were in Java 5 or not, so they went as well. Hopefully this will work with that compiler.
The logic for this solution relies on two concepts, bitwise conditionals, and lazy evaluation. Additionally we'll throw in some nice abstractions to help make things a bit nicer.
Lazy Evaluation
A big part of recursion in functional languages is lazy evaluation. Basically we give code that we don't want to execute just yet (or possibly never). Java doesn't have this built in, but we can fake it.
We'll have to declare some interfaces to accomplish this, but they are pretty straightforward.
Assuming we have this interface:
private interface LazyOperation {
String apply ();
}
We can do this:
LazyOperation op = new LazyOperation() {
public String apply() {
return "lazy result";
}
};
op.apply(); // Nothing actually happens until this step.
Bitwise Conditionals
Now that we have a way to create chunks of code that can be executed in a delayed manner, we need a way to choose between them. Java's type safety is normally a good thing, but it gets in the way here. So first, some tools to do comparisons that yield an int instead of a boolean (this will be important in a moment).
First we define #isNegative by extracting the sign bit. We can do this because we know that Java stores ints in 2's complement, so the highest bit contains 1 if the int is negative and 0 if the int is positive.
Note that this returns 0 when passed 0.
private static int isNegative(int n) {
return n >> (Integer.SIZE - 1) & 1;
}
Once we have that, #isPositive is trivial, but we want it because it makes the logic easier to understand later on.
Note that this also returns 0 when passed 0.
private static int isPositive(int n) {
return isNegative(-n);
}
Lastly, we need a check for zero, which involves checking if the int is positive or negative, then flipping all of the bits (the ~ operation) and extracting the lowest to get 1 or 0.
private static int isZero(int n) {
return ~(isPositive(n) | isNegative(n)) & 1;
}
This allows us to create the function we really need, but which would be really, really hard to follow if we in-lined the above logic.
This function acts as a filter, passing 0 unless the following rules hold:
- n is positive
- the difference between max and n is non-negative
Basically, we're looking for valid input for the recursion to continue.
private static int shouldRecurse(int n, int max) {
int difference = max - n;
return isPositive(n) & (isPositive(difference) | isZero(difference));
}
Abstractions
Now it's time to start putting things together. There are two helpers we are going to create that are conceptually similar to common helpers in functional programming: #foldRight and #foldLeft.
We'll also need one new interface.
private interface IntToString {
String apply(int n);
}
public static String foldRight(int times, IntToString function) {
return (new LazyStringOperation[]{
new LazyStringOperation() {
public String apply() {
return "";
}
},
new LazyStringOperation() {
public String apply() {
return foldRight(times - 1, function) + function.apply(times - 1);
}
}
})[shouldRecurse(times, DAYS_OF_CHRISTMAS)].apply();
}
public static String foldLeft(int times, IntToString function) {
return (new LazyStringOperation[]{
new LazyStringOperation() {
public String apply() {
return "";
}
},
new LazyStringOperation() {
public String apply() {
return function.apply(times - 1) + foldLeft(times - 1, function);
}
}
})[shouldRecurse(times, DAYS_OF_CHRISTMAS)].apply();
}
You've probably noticed they are very close to identical. Actually, the only difference between them is that the combination is done either before or after the recursive call. This is more important than you'd think (deals with avoiding StackOverflow by using tail-recursion), but is a bit out of scope here.
The actual recursive operation is achieved by creating an array of lazy operations, with the base case at index 0, and the recursive case at index 1. It's a common convention to make the base case return an identity value, in the case of strings that is "". As you can see, this simplifies the logic nicely.
After creating the array, we immediately index into it using our decision function, which we know only yields 0 or 1. We then call LazyOperation#apply to execute the operation. This is nice because our decision function will avoid out of bounds input by jumping directly to the base case (which does not access the array).
Putting it all together
There are other minor improvements, mostly consolidating logic, and some minor modification of the way indexes are passed to account for having a base case that doesn't access the array.
public class TwelveDaysOfChristmas {
private static final int DAYS_OF_CHRISTMAS = 12;
private static final String[] presents = new String[] {
"A partridge in a pear tree",
"Two turtle doves and",
"Three French Hens,",
"Four calling birds",
"Five golden rings.",
"Six geese a-laying,",
"Seven swans a-swimming,",
"Eight maids a-milking,",
"Nine ladies dancing,",
"Ten lords a-leaping,",
"Eleven Pipers piping,",
"Twelve drummers drumming,"
};
private static final String[] ordinalNumbers = new String[] {
"first",
"second",
"third",
"fourth",
"fifth",
"sixth",
"seventh",
"eighth",
"ninth",
"tenth",
"eleventh",
"twelfth"
};
public static void main(String[] args) {
System.out.print(foldRight(
DAYS_OF_CHRISTMAS,
new IntToString() {
public String apply(int n) {
return verse(n);
}
}));
}
private interface IntToString {
String apply(int n);
}
private interface LazyStringOperation {
String apply ();
}
private static int isNegative(int n) {
return n >> (Integer.SIZE - 1) & 1;
}
private static int isPositive(int n) {
return isNegative(-n);
}
private static int isZero(int n) {
return ~(isPositive(n) | isNegative(n)) & 1;
}
private static int shouldRecurse(int n, int max) {
int difference = max - n;
return isPositive(n) & (isPositive(difference) | isZero(difference));
}
private static String foldRight(int times, IntToString function) {
return (new LazyStringOperation[]{
new LazyStringOperation() {
public String apply() {
return "";
}
},
new LazyStringOperation() {
public String apply() {
return foldRight(times - 1, function) + function.apply(times - 1);
}
}
})[shouldRecurse(times, DAYS_OF_CHRISTMAS)].apply();
}
private static String foldLeft(int times, IntToString function) {
return (new LazyStringOperation[]{
new LazyStringOperation() {
public String apply() {
return "";
}
},
new LazyStringOperation() {
public String apply() {
return function.apply(times - 1) + foldLeft(times - 1, function);
}
}
})[shouldRecurse(times, DAYS_OF_CHRISTMAS)].apply();
}
private static String verse(int verseNumber) {
return leadIn(verseNumber)
+ foldLeft(verseNumber + 1, new IntToString() {
public String apply(int n) {
return presents[n] + '\n';
}
})
+ '\n';
}
private static String leadIn(int verseNumber) {
return String.format("On the %s day of Christmas,\nMy true love sent to me\n",
ordinalNumbers[verseNumber]);
}
}
