In my last post, I described the first Schindler Milan office weekly riddle. It has been a big success, and it had a brilliant winning solution (one of mine 🙂 ). A simple problem, implementing increment by one without using addition, yet open enough to trigger a good number of solutions.
As the winner, it was my duty to invent the next riddle. A really daunting task if I wanted to live up to the expectations. Honestly, I didn’t invent anything, I just squeeze the web looking for a good programming riddle in the drops.
Eventually, I decided to go for determining the lowest of two numbers… using if-less programming. After all, if statement can be tricky and someone already pointed out that if statement should be considered harmful in the same way the infamous goto is.
As the riddle maker I couldn’t compete (judging would have been a bit cumbersome), but nothing prevented me to try outside the competition.
I found quite a number of solutions, but I’d like to present them alongside those of my colleagues.
There are three 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
Comparison Expression Values
One of the original design goals of C was simplicity. It had to be a simple language so that the compiler would have been easy to write. Stemming from BCPL where there was just one type – int – C also got rid of extra types, notably strings and booleans (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.
Here’s Mario‘s solution:
int Minimo(int x, int y)
{
int z = (x >= y) * y + (y > x) * x;
return z;
}
The expression (x >=y) evaluates to 1 if is true (when x is greater or equal to y), or to 0 if it is false (when x is less than y). Multiplication zero (0) and identity (1) elements do the rest.
Not happy with the C++ solution, Mario also submitted the same concept written in LOLCODE:
HAI 1.2
CAN HAS STDIO?
HOW IZ I MNIMUM YR X AN YR Y
I HAS A PICC_Y ITZ BOTH SAEM X AN BIGGR OF X AN Y
I HAS A PICC_X ITZ DIFFRINT X AN BIGGR OF X AN Y
I HAS A MNIMUM ITZ SUM OF PRODUKT OF PICC_Y AN Y AN PRODUKT OF PICC_X AN X
FOUND YR MNIMUM
IF U SAY SO
VISIBLE "WHATZ FRST TIEM 4 SPAGO?"
I HAS A X
GIMMEH X
VISIBLE "WHATZ SECUND TIEM 4 SPAGO?"
I HAS A Y
GIMMEH Y
I HAS A MINMUM ITZ I IZ MNIMUM YR X AN YR Y MKAY
VISIBLE "TIEM 4 SPAGO IZ " MINMUM
KTHXBYE
Esoteric programming languages have the expressive power to make you laugh. References to “Spago” and time are because of the way I formulated the puzzle, but I think that once you get over the confusing syntax is 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 of C behaviors, rather than by design.
Library functions
Although it may seem like cheating, I considered valid solutions using a library function. 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.
Anna submitted the shortest version in Python (one line shorter than the C++ equivalent):
def find_earlier(x,y) return min(x,y)
Other library usage includes various applications of containers.
Domenico proposed two solutions with containers – one with a standard array and then a sort operation –
int solution_array_sort(int x, int y)
{
std::array<int, 2> mArray{x, y};
std::sort(mArray.begin(), mArray.end());
return mArray[0];
}
The other one is more convoluted and uses an associative container which uses comparison results as keys for the result:
int solution_map(int x, int y) {
std::unordered_map<bool, int> mMap{
{true, x},
{false, y}
};
return mMap.at(x < y);
}
In the same direction, yours truly wrote the following code that avoids the associative container relying on indexes 0 and 1 as the result of the comparisons:
int m7( int x, int y )
{
int a[2];
a[x>=y] = x;
a[x<y] = y;
return a[0];
}
A different take on containers can be found in my solution:
int m5( int x, int y )
{
int a[2] = {x,y};
return *std::find_if( a, a+1, [y](auto _){ return _ < y; });
}
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_id 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. The first one is mine –
int m6( int x, int y )
{
auto xs = std::views::iota(0,x);
auto ys = std::views::iota(0,y);
std::vector<int> out;
std::ranges::set_intersection( xs, ys, std::back_inserter(out) );
return out.size();
}
This uses C++20 ranges, 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 is the solution.
The other solution by Phuong, uses sets, but determines the smaller one, by trying to access it out of range:
int smaller_things_2(int x, int y)
{
std::vector<int> A(x, 1);
std::vector<int> B(y, 1);
try {
A.at(y) = 1;
} catch (std::exception& e) {
std::cerr << "Exception caught : " << e.what() << std::endl;
return x;
}
try {
B.at(x) = 1;
} catch (std::exception& e) {
std::cerr << "Exception caught : " << e.what() << std::endl;
return y;
}
return 0;
}
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 reckless application of exceptions, and the ruthless use of vectors. That’s why I chose this as the winner of the contest (kudos Phuong!).
Note that relying on set cardinality works only for positive integers (which is consistent with my formulation of the problem).
I find Phuong‘s code the perfect link with the following section, since his solution not only employs sets but also finds a way to bend exceptions to work as ifs.
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.
My solution (indeed suggested by Alessandro) is the bending of the while statement –
int m8( int x, int y )
{
while( x < y )
{
return x;
}
return y;
}
The return statement just breaks the loop and it’s not different from the if statement.
Another solution from myself relies on conditional expression shortcuts:
int m1( int x, int y )
{
int result;
(x < y && (result = x)) || (result = y);
return result;
}
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
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 right 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 –
int m4( int x, int y)
{
int mid = (x+y)/2;
int delta = std::abs( x-y)/2;
return mid-delta; // or (x+y-std::abs(x-y))/2 to avoid a division
}
Nicola found another way to put it –
def get_min_without_less_operator(x, y):
scaled_solution = (abs(x-y) - (x - y)) * x + (abs(y-x) - (y - x)) * y
scale_factor = 2 * abs(x - y)
return scaled_solution / scale_factor
As put by Nicola 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).
The arithmetic solution is once again from Domenico, go down from x and y to zero and count the iterations:
unsigned int solution_while(unsigned int x, unsigned int y)
{
unsigned int count = 0;
while(x > 0 && y > 0) {
x--;
y--;
count++;
}
return count;
}
This solution applies only to positive integers.
The last mathematical solution is another code snippet by Nicola:
def in_luck_we_trust_tribute(x, y):
"""Inspired by your previous solutions, here is a solution that gives you
50% chance of a correct answer :D"""
return random.sample([x, y], 1)[0]
Notably, this code sometimes yields the right solution, sometimes doesn’t… if you trust in luck (and RNG) then this is for you 🙂
Using Information Theory
Although most programmers are familiar with the concept of Turing’s Machine, much less of them ever got in touch with Alonzo Church‘s work.
Alonzo Church was a bright mathematician, besides being a teacher of Turing, Church devised a computational model based on functions named Lambda Calculus. 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 in Lambda calculus.
The solution to the problem implemented in Lambda calculus is quite convoluted and I will write a dedicated post. In the meantime, I just note that numbers need to be converted to and from a specialized notation (Church’s numerals) in order to be processed by the algorithm.
Of course, no one sane in their mind would write production code like this (unless on a deserted island) 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:
package org.maxpagani.iflessmin
import scala.annotation.tailrec
trait Lambda {
def apply( x: Lambda ) : Lambda
}
object Main {
def toInt( y : Lambda ) : Int = {
case class Counter( counter: Int) extends Lambda {
def apply( x: Lambda ) : Lambda =
this
}
case object AddOne extends Lambda {
def apply( x: Lambda ) : Lambda = {
Counter( x.asInstanceOf[Counter].counter+1 )
}
}
y( AddOne )(Counter(0)).asInstanceOf[Counter].counter
}
val zero: Lambda = f => x => x
val identity: Lambda = x => x
val aTrue: Lambda = (x) => (y) => x
val aFalse: Lambda = (x) => (y) => y
val succ : Lambda = (n) => (f) => x => f(n(f)(x))
val pred : Lambda = (n) => (f) => (x) => n((g) => (h) => h(g(f)))((u) => x)((u) => u)
val sub : Lambda = (m) => (n) => n( pred )(m)
val isZero : Lambda = (n) => n( (x) => aFalse )( aTrue )
val leq : Lambda = (m) => (n) => isZero( sub(m)(n) )
def toChurch(n: Int ) : Lambda = {
if( n == 0 )
zero
else
succ(toChurch(n-1))
}
val aIf : Lambda = c => (t) => (f) => c(t)(f)
def main( args: Array[String] ) : Unit = {
val xx = toChurch(42)
val yy = toChurch(24)
val zz = aIf( leq(xx)(yy) )(xx)(yy)
println( toInt(zz) )
}
}
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].
Conclusions
This has been another really entertaining riddle proving that lateral thinking is a precious resource to get us out of stack situations. I’d like to thank the participants – Anna, Domenico, Mario, Matteo (whose solution included even unit tests), Nicola and Phuong, and all the colleagues that took the time to read my cumbersome puzzle. Also due thanks go to my employer Schindler who strives for engineer excellence and promotes these side activities.
2 thoughts on “What if “if” would go missing?”