20
\$\begingroup\$

For my AP Computer Science class, I am required to write a program that prints the Twelve Days of Christmas without loops or conditionals using static methods.

public class TwelveDaysOfChristmas {

    public static final String[] lines = 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,"
    };

    public static final String[] days = new String[] {
        "first",
        "second",
        "third",
        "fourth",
        "fifth",
        "sixth",
        "seventh",
        "eighth",
        "ninth",
        "tenth",
        "eleventh",
        "twelfth"
    };

    public static final String verseText =
        "On the %s day of Christmas,\n" +
        "My true love sent to me\n" +
        "%s";

    public static void main(String[] args) {
        //Print the song
        System.out.println(song());
    }

    public static String song() {
        //The song consists of all verses up to verse 12, but the index starts from 0
        //Print verses 0 to 11
        return versesBelow(11);
    }

    public static String versesBelow(int verse) {
        //Evil hack that allows me to check whether the input is zero without using a conditional ;)
        try {
            //Divide by verse. If the verse is zero, then an ArithmeticException is thrown.
            //I am not using a conditional here!!!
            int i = 1 / verse;
        }
        catch(ArithmeticException ex) {
            //Stop the recursion
            return verse(verse);
        }
        //else return this verse and all the verses below this one.
        return versesBelow(verse - 1) + verse(verse);
    }

    public static String verse(int verse) {
        //Format the string with the correct day and verse and add a newline for a blank space after
        return String.format(verseText, days[verse], linesBelow(verse)) + '\n';
    }

    public static String linesBelow(int line) {
        //Same evil hack
        try {
            int i = 1 / line;
        }
        catch(ArithmeticException ex) {
            //Stop the recursion if line is zero
            return line(line);
        }
        //Else return this line and all the lines below this line
        return line(line) + linesBelow(line - 1);
    }

    public static String line(int line) {
        //Return this line and a newline
        return lines[line] + '\n';
    }
}

Is there a better way to accomplish this than my way? I do kind of cheat a little, but it's not technically a conditional, is it?

\$\endgroup\$
  • 4
    \$\begingroup\$ What's wrong with just printing the lyrics literally then, with these restrictions? \$\endgroup\$ – h.j.k. Dec 9 '15 at 5:57
  • 3
    \$\begingroup\$ @h.j.k. The assignment is worded such that it's not possible to just do that. \$\endgroup\$ – nimsson Dec 9 '15 at 13:10
  • 1
    \$\begingroup\$ I think there might be an slight extra issue to consider: as far as I remember the first verse goes: "On the first day of Christmas my true love sent to me a partridge in a pear tree." but the second and all subsequent verses end with: "AND a partridge in a pear tree" ie there's an extra "and" before the last line in verses 2-12 inclusive. Tricky without any conditionals though! Just in case it helps make the solution complete... \$\endgroup\$ – Bruce Lamond Dec 9 '15 at 18:16
  • 9
    \$\begingroup\$ It crushes my soul to see assignments like this, asking students to do useless things in roundabout and arcane ways. \$\endgroup\$ – Aurast Dec 9 '15 at 20:32
  • 1
    \$\begingroup\$ @Aurast I'd rather have my teacher assign one big assignment per chapter with useful applications of the chapters' contents as well \$\endgroup\$ – nimsson Dec 9 '15 at 20:38
22
\$\begingroup\$

Recursion is something that is often "unwrapped" to become loops, but the same is true, in the other direction. Almost all loops can be implemented as recursion.

Using your "trick" of throwing an exception to act as a conditional, it would be simple to turn all your code... this code:

public static final String verseText =
    "On the %s day of Christmas,\n" +
    "My true love sent to me\n" +
    "%s";

public static void main(String[] args) {
    //Print the song
    System.out.println(song());
}

public static String song() {
    //The song consists of all verses up to verse 12, but the index starts from 0
    //Print verses 0 to 11
    return versesBelow(11);
}

public static String versesBelow(int verse) {
    //Evil hack that allows me to check whether the input is zero without using a conditional ;)
    try {
        //Divide by verse. If the verse is zero, then an ArithmeticException is thrown.
        //I am not using a conditional here!!!
        int i = 1 / verse;
    }
    catch(ArithmeticException ex) {
        //Stop the recursion
        return verse(verse);
    }
    //else return this verse and all the verses below this one.
    return versesBelow(verse - 1) + verse(verse);
}

public static String verse(int verse) {
    //Format the string with the correct day and verse and add a newline for a blank space after
    return String.format(verseText, days[verse], linesBelow(verse)) + '\n';
}

public static String linesBelow(int line) {
    //Same evil hack
    try {
        int i = 1 / line;
    }
    catch(ArithmeticException ex) {
        //Stop the recursion if line is zero
        return line(line);
    }
    //Else return this line and all the lines below this line
    return line(line) + linesBelow(line - 1);
}

public static String line(int line) {
    //Return this line and a newline
    return lines[line] + '\n';
}

in to just:

public static void main(String[] args) {
    try {
        recurseDown(0);
    } catch (RuntimeException e) {
        // nothing.
    }
}

private static void recurseDown(int i) {
    System.out.println("\nOn the " + days[i] + " day of Christmas\nMy true love sent to me");
    try {
        recurseUp(i);
    } catch (RuntimeException e) {
        // nothing.
    }
    recurseDown(i + 1);
}

private static void recurseUp(int i) {
    System.out.println(lines[i]);
    recurseUp(i - 1);
}

you can see it running here: http://ideone.com/SAte6Z

Written properly, it would be:

public static void main(String[] args) {
    recurseDown(0);
}

private static void recurseDown(int i) {
    if (i == days.length) {
        return;
    }
    System.out.println("\nOn the " + days[i] + " day of Christmas\nMy true love sent to me");
    recurseUp(i);

    recurseDown(i + 1);
}

private static void recurseUp(int i) {
    if (i < 0) { 
        return;
    }
    System.out.println(lines[i]);
    recurseUp(i - 1);
}
\$\endgroup\$
  • 2
    \$\begingroup\$ Loops are a subset of recursion, so all loops can be implemented with recursion. \$\endgroup\$ – bjb568 Dec 9 '15 at 20:08
  • \$\begingroup\$ @bjb568 Not true, an endless while loop comes to mind. Trying to make an infinite loop through recursion instead of a regular loop will cause a stack overflow. \$\endgroup\$ – Kevin Dec 10 '15 at 13:32
  • \$\begingroup\$ @Kevin It depends on whether your language will support an infinite stack then :p \$\endgroup\$ – bjb568 Dec 10 '15 at 13:57
  • 1
    \$\begingroup\$ I guess that's a question for "Stack Overflow" ... kidding, but languages with support for tail recursion will do it... but this is Java. \$\endgroup\$ – rolfl Dec 10 '15 at 14:04
  • \$\begingroup\$ @bjb568 Infinite stacks come with hardware requirements (infinite storage, preferably in RAM), which are not realistically available. Loops have the possibility to run forever without ever changing the stack, you can't do this with recursion. Therefore, loops are not a subset of recursion. \$\endgroup\$ – Kevin Dec 10 '15 at 14:18
15
\$\begingroup\$

I am required to write a program that prints the Twelve Days of Christmas without loops or conditionals...

Usually, that's code for using try-catch to purposefully let parts of your code fail (e.g. when determining an array index), and then remediate that in the catch. Makes for a 'fun' academic exercise such as this, just bear in mind this should strictly be only for fun, and not for writing clean, quality code. :)

Commenting and hard-coding

public static String song() {
    //The song consists of all verses up to verse 12, but the index starts from 0
    //Print verses 0 to 11
    return versesBelow(11);
}

This comment is redundant as it does not say anything more than what the code is plainly doing, but more importantly, 11 is hard-coded here. Since you already have an array, you can do something like array.length - 1 here so that it's easier for you to add extra lines in the future (e.g. 365 days of Christmas for non-leap-years).

Code duplication

Your versesBelow() and linesBelow() methods are very similar, so you may want to consider doing some de-duplication here by generalizing the problem...

// Function<T, R> is a Java 8 feature
private static generate(int x, Function<Integer, String> function, 
                            String before, String after) {
    String previous;
    try {
        int i = 1 / x;
        previous = function.apply(x- 1);
    }
    catch(ArithmeticException ex) {
        previous = "";
    }
    return before + previous + after;
}
  • We know we need to append the output from the previous day, except for the first.
  • Using a previous placeholder, try to perform our 'stop condition'. If we catch the expected Exception, it means we can concatenate with "".
  • We need before and after here as both methods require the previous output to be concatenated differently.

The two methods can then be refactored as such (using method references):

// Changed visibility modifier to private
private static String versesBelow(int verse) {
    return generate(verse, TwelveDaysOfChristmas::versesBelow, "", verse(verse));
}

private static String linesBelow(int line) {
    return generate(line, TwelveDaysOfChristmas::linesBelow, line(line), "");
}

Alternate modeling

When you have two enumerated String[] arrays where there's a close relationship between one and the other, you can consider representing them as an enum. This lets you reference one value with the other, almost like a key-value relationship. For example:

enum Day {
    FIRST("A partridge in a pear tree."),
    SECOND("Two turtle doves and"),
    THIRD("Three French hens,"),
    FOURTH("Four calling birds,"),
    FIFTH("Five golden rings!"),
    SIXTH("Six geese a-laying,"),
    SEVENTH("Seven swans a-swimming,"),
    EIGHTH("Eight maids a-milking,"),
    NINETH("Nine ladies dancing,"),
    TENTH("Ten lords a-leaping,"),
    ELEVENTH("Eleven Pipers piping,"),
    TWELFTH("Twelve drummers drumming,");

    private final String line;

    private Day(String line) {
        this.line = line;
    }
}

Generating verses

With the enum in place, we now need to generate the verse for each Day. Since an enum is also a class, we can conveniently override its toString() for a more 'programmer-friendly' form.

enum Day {
    // ...

    private String getVerse() {
        String next;
        try {
            next = values()[ordinal() - 1].getVerse();
        } catch (ArrayIndexOutOfBoundsException e) {
            next = "";
        }
        return String.format("%s%n%s", line, next);
    }

    @Override
    public String toString() {
        return String.format("On the %s day of Christmas, my true love gave to me,%n%s",
                name().toLowerCase(), getVerse());
    }
}

Instead of catch-ing for an ArithmeticException, we can just handle for the case where ordinal() - 1 gives us -1, a special case only for the first day.

Look ma, no loops

What's wrong with just printing the lyrics literally then, with these restrictions? - myself

I meant that partly in-jest, but if we really need to avoid any loops, we can also call each enum value one-by-one to print them:

public static void main(String[] args) {
    System.out.println(Day.FIRST);
    System.out.println(Day.SECOND);
    System.out.println(Day.THIRD);
    System.out.println(Day.FOURTH);
    System.out.println(Day.FIFTH);
    System.out.println(Day.SIXTH);
    System.out.println(Day.SEVENTH);
    System.out.println(Day.EIGHTH);
    System.out.println(Day.NINETH);
    System.out.println(Day.TENTH);
    System.out.println(Day.ELEVENTH);
    System.out.println(Day.TWELFTH);
}
\$\endgroup\$
  • \$\begingroup\$ You could further reduce your main method to a recursive call that uses the iterator of Day.values() ;-) \$\endgroup\$ – Aron_dc Dec 9 '15 at 8:27
  • \$\begingroup\$ @Aron_dc of course, I simply picked that to showcase a literal implementation. :D \$\endgroup\$ – h.j.k. Dec 9 '15 at 8:43
  • 1
    \$\begingroup\$ Your suggestions are good, and I would normally do that, but part of the requirement was that you use static methods and I can't use Java 8 features :) \$\endgroup\$ – nimsson Dec 9 '15 at 13:02
10
\$\begingroup\$

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:

  1. n is positive
  2. 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]);
    }
}
\$\endgroup\$
  • \$\begingroup\$ Welcome to Code Review! You have presented an alternative solution, but haven't reviewed the code. Please explain your reasoning (how your solution works and how it improves upon the original) so that the author can learn from your thought process. \$\endgroup\$ – SuperBiasedMan Dec 9 '15 at 9:29
  • 1
    \$\begingroup\$ My bad, I though the extensive comments on what I was doing, and why, made both the technique for avoid using exceptions for branching and the other improvements clear and understandable. I'll expand them later today, as I've improved it a bit since then. \$\endgroup\$ – Morgen Dec 9 '15 at 14:46
  • \$\begingroup\$ Ah, I had missed the explanations in your comments. It's recommended that you don't use comments in the code to explain your suggestions. It's easy to miss, as I've just shown haha. People often answer by splitting up the code and having normal text between each code block to explain it. \$\endgroup\$ – SuperBiasedMan Dec 9 '15 at 14:49
  • \$\begingroup\$ Generics is introduced in Java 5. :) \$\endgroup\$ – h.j.k. Dec 10 '15 at 1:52
  • \$\begingroup\$ This probably violates the "only static methods" rule, though. \$\endgroup\$ – Petr Hudeček Dec 10 '15 at 11:16
6
\$\begingroup\$

Assuming you are allowed to use Java 8 streams, then you can accomplish this.

The IntStream deals with generating integers on the fly. Of particular interest to you would be the range static methods of this class which provide a way of generating a range of values with a start and end value as parameters.

This allows you to do IntStream.range(0, 12)

By doing this, you have just found a work around to using the try-catch blocks. Now how to use this?

Well probing deeper into the heart of the stream API's, they each seem to implement another method called mapToObj, which (if you can picture this) takes a type supplied by the current stream and "maps" those values to a function which takes object of the supplying stream and produces objects of another type (specified by the function's return type). Thanks to Java 8, we can satisfy this function requirement by supplying a function we have declared in the current class.

This gets you to this:

IntStream.range(0, 12)
    .mapToObj(TwelveDaysOfChristmas::versesBelow)

Now we have satisfied the recursion problem, and finally we can "collect" the results into a string by making use of another class of Streams called Collectors

This gets us here:

IntStream.range(0, 12)
    .mapToObj(TwelveDaysOfChristmas::versesBelow)
    .collect(Collectors.joining("\n\n"));

Moving on, it is time to actually do some work. Notice that we call the method versesBelow with an integer which represents the current day we are on. So in this method the first thing we want to print is the verseText formatted with the day, and finally the gifts received from day 1 to this day, but backwards.

You already know how to format a string using String.format method, so we will leave that, now inside this format method, we want to pass the day we are on, but print the gifts received backwards starting with the current day till day 1. We make use another IntStream,

String.format(verseText, days[day],
    IntStream.rangeClosed(0, day)

To make it appear as if the stream is backwards, you pipe this input to another stream which does the reversing

String.format(verseText, days[day],
    IntStream.rangeClosed(0, day)
        .map(i -> day - i)

Next we grab each line and collect that into a string with a newline seperating them:

String.format(verseText, days[day],
    IntStream.rangeClosed(0, day)
        .map(i -> day - i)
        .mapToObj(i -> lines[i])
        .collect(Collectors.joining("\n")));

Putting it all together:

import java.util.stream.Collectors;
import java.util.stream.IntStream;

public class TwelveDaysOfChristmas {

    public static final String[] lines = 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,"
    };

    public static final String[] days = new String[] {
            "first",
            "second",
            "third",
            "fourth",
            "fifth",
            "sixth",
            "seventh",
            "eighth",
            "ninth",
            "tenth",
            "eleventh",
            "twelfth"
    };

    public static final String verseText = "On the %s day of Christmas,\n" +
            "My true love sent to me\n%s";

    public static void main(String[] args) {

        //Print the song
        System.out.println(song());
    }

    public static String song() {
        //The song consists of all verses up to verse 12, but the index starts from 0
        //Print verses 0 to 11
        return IntStream.range(0, 12)
                .mapToObj(TwelveDaysOfChristmas::versesBelow)
                .collect(Collectors.joining("\n\n"));
    }

    public static String versesBelow(int day) {

        return String.format(verseText, days[day],
                IntStream.rangeClosed(0, day)
                    .map(i -> day - i)
                    .mapToObj(i -> lines[i])
                    .collect(Collectors.joining("\n")));
    }
}
\$\endgroup\$
  • 5
    \$\begingroup\$ Using a stream is similar to using a for-loop. I considered that too... and decided it was a cheat, but, that just goes to show that this sort of question is bad for code review... it's not looking to apply best practices. \$\endgroup\$ – rolfl Dec 9 '15 at 4:10
  • \$\begingroup\$ @rolfl, I will leave that decision up to the OP. I have never seen what the java stream methods look like (internally) nor do I care what they look like. All I was concerned with when writing this was not using conditionals or loops \$\endgroup\$ – smac89 Dec 9 '15 at 4:31
  • \$\begingroup\$ Thanks for the suggestion, but my school only has a Java 5 compiler :) \$\endgroup\$ – nimsson Dec 9 '15 at 13:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.