No Iterations, and No Conditions, Please

The Problem

While the title doesn't do justice to Radiohead’s No Surprises, it fits well enough with the subject I would like to discuss.

One day, what was pretty much a homework question popped up on my Quora feed. The question was “Can one write Java code that prints 1 through 100 without using any loop or conditions?”.

Straightforward question with more or less inspired responses, each of them more or less wrong.

The Jokers

I will leave aside the snarky, and low hanging fruit jokes, such as

System.out.println("1 through 100 [without using any loop or condition]");

, and

System.out.println("1");

...

System.out.println("99");
System.out.println("100");

I would like to point out that the latter is one correct solution to the problem, albeit not the one that is expected, since the point of the exercise must be to actually write a lot of numbers without automating the work, and without intensive manual labor.

In other words, the solution must be solvable in a decent number of steps, not necessarily linearly dependent on the number of values, with a fixed number of print calls that will still print all the numbers.

Imagine fully unrolling a loop and getting a smaller chunk of code than you would expect, which still does the same job.

The Misguided

So what does no loops and no conditions mean? The most straightforward answer is that you are not allowed to solve this specific problem with a code that looks like this:

for(int i=1; i<=100; i++) {
  System.out.println(i);
}

If the condition above was not explicit enough, it can’t look like this, either:

int i=1;while(i <= 100) {  System.out.println(i++);}

However, most of the answers tried to circumvent the iteration and condition with various tricks:

If it’s built-in, then it’s not a loop

IntStream.range(1, 101).forEach(System.out::println);

If it’s a recursive call then it’s not a loop…

boolean print(int n) {
  System.out.println(n);
  return n == 100 ? true : print(n + 1);
}
/* called with print(1) */

… especially if it throws an exception to avoid a condition

void print(int n) {
  System.out.println(n);
  int i = 1 / (n - 100); /* runtime division by zero exception */
  print(n+1);
}
/* called with print(1) */

Now it’s time to understand what we mean by iterations, loops, conditions, exceptions and recursion to make sure that we’re not making any confusions.

An iteration is the repeated application of a procedure to the result of a previous application of that procedure for the purpose of refining the result.

A loop is a procedure (meaning a group of instructions) that is continually repeated. The difference here being that there are no state assumptions, so loop doesn’t need to maintain a state, or to even complete, for that matter. However, in the case of our problem, the loop involved would be an iteration

A condition is the representation of a state of an entity. In the case of conditional constructs in programming (if-then-else) a binary-state is required and a boolean condition is used for the decision making process. However, the condition does not need to be represented as a boolean, it’s whatever works to represent two mutually exclusive possible states.

An exception is an exceptional condition in the flow of an application, a binary state differentiating between normal execution and abnormal execution. There is no difference between an exeption and a conditional other than the syntactic sugar that enables them in different languages. In fact, not all languages have an exception handling mechanism, thus relying on explicit conditionals.

Recursion is an approach to solving a specific problem by resolving one or more other instances of the same problem. Recursion is a different way to express an iteration, while hiding certain implementation details. Certain compilers will actually convert a tail-recursive call into an explicit loop.

Most of solutions given to this problem were a variation of these solutions. However, in each case a repetitive operation (either explicit or implicit) is clearly involved, and a condition is also present, whether hidden (within an iterator), or not (ternary operator, exceptions).

The Close Encounter

There is one solution I have seen that deserves its own category, because the thought process is a bit different, and because it almost avoids the pitfalls from the other solutions. It is somewhat similar to the problem of expressing a monetary value in amounts of differently valued coins.

The problem is that the output process still includes an iterative refinement, as can bee seen below:

public class Printout {
  int currentValue = 1;
  void print1() {
    System.out.println(currentValue++);
  }
  void print2() {
    print1();
    print1();
  }
  void print5() {
    print1();
    print2();
    print2();
  }
  void print10() {
    print5();
    print5();
  }
  void print30() {    
    print10();    
    print10();    
    print10();
  }
  void print100() {    
    print30();    
    print30();    
    print30();    
    print10();  
   }
 }
 /* run with: new Printout().print100(); */

All the methods resolve to print1(), which will be called 100 times without iterating over each call, however the output is iterated over as a side-effect, by incrementing currentValue.

While not completely satisfactory, this problem points in the right direction by managing to remove the conditional.

The Solution

Let’s consider the following question: Is there any way of representing a set of 100 elements into multiple equivalent sets of smaller cardinalities such that the sum of those cardinalities is less than 100? Keep in mind that those cardinalities multiplied would still need to be 100.

The answer is yes. If we get the prime factors of 100 we obtain: 100 = 2 * 2 * 5 * 5. This means that we can have a bijective function that takes a number between 1 and 100 and can transform it into 4 numbers each part of its respective interval. Furthermore, the sum of the cardinalities of these sets is 14, which tells us that we can write 4 functions, each corresponding to an interval, and each providing a partial mapping of the bijective function, which will require us to write 14 lines of code (leaving out the method declaration) calls between all of them. Applying the inverse function for the given bijection we will get the equivalent number from the 100 elements interval.

This is not the first time this problem is encountered. Think of the representation of a number as multi-byte. The single value may not fit in a single byte so it will be broken into multiple values in the [0, 255] interval (if byte==8 bits). The only difference between this problem and ours is that, in our case, we have to deal with intervals with different cardinalities, rather than settling on a fixed representation. Sure, we could use a small enough fixed value, but the smaller the value the more functions we have to write, because we get more intervals. As we’re going to see, later on, these intervals may require some extra help.

One thing to note here, which we will address later, is that we can actually cut down the number of functions from 4 to 3, because 2 * 2 = 2 + 2 = 4, so we can use the 100 = 4 x 5 x 5 equivalence without overhead, actually quite the opposite.

We’ll consider indexes starting from 0 to simplify things and we’ll add the one at when we print the number. This will not be a side-effect recursion because the operation at each step is not based on a previous step and it will not help the next step, we just add it as a starting value. Thus, a quick way to solve the problem is the code below: 4 calls x 5 calls x 5 calls = 100 calls. 4 calls + 5 calls + 5 calls = 14 lines of code.

public class Printout1To100 {
  static void println(int index1, int index2) {
    System.out.println(25 * index1 +5 * index2 + 1);
    System.out.println(25 * index1 +5 * index2 + 2);
    System.out.println(25 * index1 +5 * index2 + 3);
    System.out.println(25 * index1 +5 * index2 + 4);
    System.out.println(25 * index1 +5 * index2 + 5);
  }
  static void println(int index1) {
    println(index1, 0);
    println(index1, 1);
    println(index1, 2);
    println(index1, 3);
    println(index1, 4);
  }
  public static void main(String[] argv) {
    println(0);
    println(1);
    println(2);
    println(3);
  }
}
  

Now imagine that your homework becomes not printing 1 to 100, but 1 to 101. We get the prime factors and we’re stumped. “There can be only one”, and it’s 101!

More on that in the next iteration of this document, where we go meta.