What if "if" would go missing? "A puzzle for if-less programmers"

Date:: 3/21/23

One of the key skills required for engineering is the ability to reach some goal, complying with several constraints. Many times these constraints prevent you from going from A to B on a straight line, and you are required to find sideway methods, or avoid using the most obvious approach.

The corresponding pattern is "how can you do X without using Y?". This is the same pattern for the successful first Schindler Milan office weekly riddle [1], as well as the pattern for the second one, that I’m going to describe in this post.

This puzzle, I devised as prescribed for the winner of the previous one, is about determining the least of two numbers without using the if statement. After all, if statement can be tricky and someone already pointed out that if statement should be considered harmful [2] in the same way the "harmful" goto statement is [3].

The puzzle had many submissions, that I’m going to present alongside my solution. In the interest of presentation, I will not attribute solutions. To all purposes here, you may consider them a team effort.

I have classified the submissions by their approach to the solution. There are five main approaches:

Comparison expressions evaluate to 1 if they are true and 0 if they are false
Using library functions
Bending other conditional constructs
Using math
Using information theory

Evaluation of Comparison Expressions

One of the original design goals of C was simplicity. It had to be a simple language so that the compiler would be easy to write. Stemming from BCPL [4] where there was just one type - int - C also got rid of extra types, notably strings and boolean expressions (and defaulted types to int).

So every boolean expression (e.g. a>b) is of type int and evaluates to 1 if the expression is true, or 0 if the expression is false.

This can be leveraged in a number of ways to determine the lower value between two numbers, in this way:

The expression (x>=y) evaluates to 1 when x is greater or equal to y, or to 0 otherwise. Multiplication elements zero (0) and identity (1) do the rest [5][6].

The most original solution that I received with this approach was written in LOLCODE [7]:

Esoteric programming languages [8] have the expressive power to make you laugh. Once you get over the confusing and exhilarating syntax, it’s easy to identify the input request for two numbers and the output of the lowest.

I believe that most of these esoteric languages are translated into C and then compiled, that’s why they could inherit some C behaviors, rather than by design.

Library functions

Although it may seem like cheating, I considered using a library function a valid solution. First, hiding a low-level construct under a higher abstraction level contraption is the right way to go, since it enables us to tackle increasingly complex problems. Moreover, knowing your tools is always an important asset for programmers, regardless of the language and the library used.

This is the shortest version (the same code in C++ is one line longer):

Other library usage includes various applications of containers.

For example, you can fill a container with the two values and then sorting it -

Another, more convoluted way, is to use an associative container whose key is the comparison results:

If you want to pursue this approach, you can avoid the associative container, and just use the good old array relying on indexes 0 and 1 as the result of the comparisons:

We can find a different take on containers in this solution:

The array is filled with the two values, then a find is performed on a range that includes just the first item in the array. If std::find_if doesn’t find any item that satisfies the predicate, then it returns the end() iterator. Since end() is one past the last item of the range, it points to the other value.

Sets

Two solutions are based on sets. This is the first one -

This uses C++20 ranges, std::views::iota produces a sequence of integers from the first to the second argument. Then, an output vector is filled with the intersection. Per construction, the intersection is equal to the set with the lower cardinality. And cardinality of the intersection is the solution.

The other solution uses sets, but determines the smaller one, by trying to access it out of range:

Note the use of this std::vector constructor that creates a vector of size equal to the value of the first argument and then fills the vector with the value of the second argument.

I liked this solution for the creative approach and the creative application of exceptions, and the peculiar use of vectors.

Note that relying on set cardinality works only for positive integers (which is consistent with my formulation of the problem).

Bending other conditional constructs

It is true that the if statement is the first we turn to when we need to make a binary decision, but the conditional branching - core to the Turing Machine - resurfaces also in other commands - switch, for and while just to name a few.

You can bend the while statement -

Or conditional expression shortcuts:

when the result of a boolean expression is determined, then the remaining part is not evaluated. Interestingly (and a bit upsetting to purists) assignment is an expression, so it can be written in logical expressions. Even more upsetting to purists is the use of the comma operator that is needed in order to avoid considering the result of the assignment in the expression. Suppose you call this function with (0,3) arguments, then x < y yields true. The shortcut to && cannot be applied since the right-hand side term may be false. Evaluating result = x always yields true, but when x is 0, in that case, the result is false. The use of the comma operator discards this result and replaces it with its right-hand side term, i.e. true. Now the shortcut kicks in for || since the result is not determined.

Using Math

There are two directions for employing mathematics: devise a formula that produces the lower of two numbers or approach it with arithmetic and sequence.

Finding a formula is not rightly intuitive, but it can be achieved by considering the two values as points A and B on a line. There will be a medium point M equally distant from A and B. If you subtract half of the distance AB from M, then you get the lower value. This is what my solution does -

Another way to put it -

As put by the author - This relies on the fact that [abs(x-y) - (x - y)] = 0 if x > y, else it is equal to 2 * abs(x-y). The solution works ONLY if x is different from y (otherwise there is a division by 0).

Another arithmetic solution is to go down from x and y to zero and count the iterations:

This solution applies only to positive integers.

The last mathematical solution is based on randomness:

Notably, this code sometimes yields the right solution, sometimes doesn’t... if you trust in luck (and RNG [9]) then this is for you.

Using Information Theory

Although most programmers are familiar with the concept of Turing’s Machine [10], much fewer have ever been in touch with Alonzo Church’s work [11].

Alonzo Church was a bright mathematician. Besides being a teacher of Turing, Church devised a computational model based on functions named Lambda Calculus [12]. It has been demonstrated that Lambda calculus is equivalent to Turing’s Machine, meaning that any algorithm that can be implemented on a Turing’s Machine can also be implemented with Lambda calculus.

The solution to the problem implemented in Lambda calculus is quite convoluted and I fully explain it in my blog [13]. A quick rough idea presentation follows. Just keep in mind that in lambda calculus, everything (really everything) is a function.

First numbers to compare have to be converted into a special notation called Church’s numerals [14]. This notation that encodes the numbers is a well-defined pattern of functions.

The next step is to subtract the two numbers with a properly defined subtraction, which yields zero when you try to subtract a greater value from a lesser value.

A function for checking zero is then used to understand which number is the least one. And the if instruction is defined to call the then branch or else branch according to the if argument.

Of course, no one would write production code like this [15] in the same way no one would write code using Turing’s Machine notation. On the other hand, I find it very fascinating how something so functional, in the mathematical sense, can compute algorithms.

Being purely functional opens the way to mathematical tools and, therefore, to rock-solid certainties.

I tried for a while to write this in C++, but I haven’t found a good solution that avoids slicing, so I resorted to a better-suited language – Scala:

If you read this and don’t understand it, it is perfectly normal, since "in mathematics, you don’t understand things. You just get used to them" [Von Neuman [16]].

Conclusions

This has been another really entertaining riddle proving that lateral thinking is a precious resource to get us out of sticky situations.

A task that could be deemed impossible at first sight turns out to be accomplished in many different ways. Surely most of them are impractical or even laughable, but this is like brainstorming where the goal is not to produce the perfect solution, but to explore the solution space and to get around all the roadblocks set by the problem.

Special Thanks

I’d like to mention here all the colleagues that contributed with their solutions to the contest – Anna, Domenico, Mario, Matteo, Nicola and Phuong. Thank you, without your code this post wouldn’t have been happened.

About the Author

Massimiliano Pagani started coding back in the 80s, when computers were laughably slow, never had enough RAM and used tape recorders as storage memory. Since then, he never stopped writing bugs and other features. He worked in the video game industry, had some exposure to server and service development, got fascinated by functional programming, and spent several years in writing firmware and embedded software. When he is struck by something he reckons interesting, and has enough spare time, he writes on his blog at https://www.maxpagani.org/.

References