[NickDMax]

Every so often I read an assignment on here that I find interesting as a challenge.

One of the threads has a questions similar to my current challenge:

Write a program to find the maximum value of an arbitrary number of elements (integers if you must) without the use of the if-statement.

Now, one could use vargs and loop though using the max() function to find the max... but I wanted to challenge myself. Here was my first solution -- not the best but I like it for a first attempt.

#include <iostream>
#include <algorithm>
using namespace std;

/*
*  The challange: find the maximum value of a arbitraty list of values wihtout
*	  the use of the conditional-control strucutes.  
*/
template <class T>
class FindMax {
	  private:
	  T currentMax;
	  int state; //states 0 = no data; non-zero = current max stored.
	  public:
	  FindMax() : state(0) {  }
	  
	  void reset() {
		   state = 0;
	  }
	  
	  FindMax& operator<<(const T& rhs) {
		   currentMax = std::max(state ? currentMax : rhs , rhs);
		   state = 1;
	  }
			
	  T& operator()() {
		 return currentMax;
	  }
};

int main() {
	int a = 12, b= 37;
	FindMax<int> themax;
	themax << 1 << 2 << 10 << b << 6 << 36 << a;
	cout << themax() << endl;
	system("Pause");
	return 0;
}

What I really would like to do is find a way to make it look more like a function and avoid the use of "<<".

[RodgerB]

I don't understand whats wrong with a simple application like this:

// Get the maximum value without conditional-control structs.
int getMax(int * intArray, int count)
{
	int maxNum = 0;
	
	for(int i = 0; i < count; i++)
		maxNum = std::max(maxNum, intArray[i]);	

	return maxNum;
}

// Main entry point.
int main() {
	int findMax[] = { 1, 2, 10, 37, 39, 100 };

	cout << getMax(findMax, sizeof(findMax) / sizeof(findMax[0])) << "\n";
	
	system("Pause");
	return 0;
}

Either way, it is the same sort of result that is much easier and more efficient then that of a class definition and its members, and it is performing the same task. In the fine words of Chris, I'm not sayin', I'm just sayin'.

[Bench]

In theory, if you can find the maximum of two numbers without an if, then you can do it for any. The problem is, what do you class as an 'if'? I would rule out the ternary operator, since that's just an abbreviated if/else. Also, the std::max function may use an if or ternary operator behind-the-scenes.
- And of course, there's this "while" trick to emulate an if statement (Which can also be mimicked using 'for' too)

int max = 5;
int num = 6;
while( max < num )
{
	max = num;
	break;
} 

IMHO, that's cheating too, but it depends on the rules. and obviously there needs to be some kind of selection somewhere (even if its loop-based, or done by the compiler), computers can't make decisions based purely on sequence.


Also, what are the constraints by which the numbers must be stored or retrieved? must the numbers be known at compile time? Must they be retrieved from the user/a file? may they be stored in a container? If so, may the container be modified?

This would be one of my suggestions, although it has the same problem as std::max, being that sort() will do all kinds of 'if' statements behind the scenes

template<int N> int biggest(int (&arr)[N])
{ 
	std::sort( arr, arr+N, std::greater<int>() );
	return arr[0];
}

int main() 
{
	int num[] = { 3, 6, 9, 121, 2, -23, 17, 344 };
	std::cout << biggest(num);
} 

This post has been edited by Bench: 16 February 2008 - 04:30 AM

[Nayana]

int max = 5;
int num = 6;
while( max < num )
{
	max = num;
	break;
}

That is not really simulating an if either. It is using one. The code above is the same as:

  int max = 5, num = 6;

entrypoint:
  if(!(max < num)) goto endpoint;

  max = num;
  goto endpoint;

  goto entrypoint;
endpoint:

Obviously it's a lot more efficient to simply write

if(max < num)
  max = num;

[Bench]

It depends on the rules - whether the challenge is one for finding unorthodox ways to use high-level language constructs (from a language point of view, an if is different to while, which is different to for, etc), or whether the challenge is one of machine instruction constructs. I assume its the former, since to perform selection, whilst ruling out all possible machine constructs which allow it to perform selection, is paradoxical
(there's also the switch/case statement which could also be classed as 'cheating' along with the while/for statement)

This post has been edited by Bench: 16 February 2008 - 05:11 AM

[Bench]

This idea just came to me - it escapes from the usual program-flow selection, and goes with boolean logic for object/variable selection. (Though you could still argue that its like the ternary 'if' in disguise)

#include <iostream>

int greatest( int num1, int num2 )
{
	int nums[2] = { 0 };
	bool num1pos = ( num1 < num2 );
	nums[ num1pos ] = num1;
	nums[ !num1pos ] = num2;
	return nums[0];
}

int main() 
{
   std::cout << greatest( 50, 10 ) << ' '
			 << greatest( 10, 50 );

} 

This post has been edited by Bench: 16 February 2008 - 06:39 AM

[Nayana]

You win.

[baavgai]

Neat class. Seriously, I never got into << overloads, it a nice example of seeing them in action. Like the template to, can use it for anything.

Of course, what constitutes an "if" is subjective. Bench showed a while construct. No if, but still conditional. If you choose to call another function and declare a win, you've simple deferred your if.

The only thing really required is a single functioning max, from which you can derive the rest. Here's my solution.

#define max(a,b) ((a>b)?a:b)

No if, and a bonus type neutral. Enjoy.

[NickDMax]

I myself do not consider the Ternary operation a version of the if-statement. I is an operator -- an out of paradigm operator not a control structure.

I allowed the use of max since (AFAIK) it used the conditional operator not the if-statement. Personally I would also say that the use of assembly language to write your own if statement was perfectly valid (but I am a softy).

Here is my second attempt. This one uses the variable arguments approach:

template <class T>
class GetMax {
	  private:
	  T currentMax;
	  int state;
	  public:
	  GetMax() : state(0) { }
	  T operator()(const T& in) {
		   currentMax = std::max(state ? currentMax : in , in);
		   state = 1;
	  }
	  
	  T operator()() { return currentMax; state = 0; }
};						 
	   
template <class T, int len>
T maximum(T first, ...) {
	va_list args;
	va_start(args, first);
	GetMax<T> gm;
	gm(first);
	int length = len - 1; //One is used up by "first"
	for (; length > 0; --length) { gm(va_arg(args, T)); }
	va_end(args);
	return gm();
}

int main() {
	int a = maximum<int, 6>(55, 1, 2, 10, 37, 6);
	cout << a << endl;
	system("Pause");
	return 0;
}

This one is very much like the last one, but at least it looks more "function like" than using the "<<" operator. Now off to read all the other solutions -- I really didn't expect so much interest.

[NickDMax]

RogerB -- That works of course -- I myself was trying to avoid the use of the array argument but I like the simplicity.

Bench -- I like the while() trick. See this is exactly why I posted this topic. To see what I can learn from other peoples solutions.

BENCH!!! That is awesome! I was trying to think of a bit-twiddling way to find the max but I had not been using the full potential of the language in my thinking! I don't think this ever would have occurred to me. -- mostly because I never assume that true == 1... For the bool I believe it always does. Well done!

I suppose I could use a similar trick to avoid having to use the state variable in my class.

*edit: confused my true and false

[NickDMax]

Stealing shamelessly from Bench here is my newest edition. Now all I have to do is remove the use of the for loop and I am truly free of conditional control structures.

#include <iostream>
#include <iostream>
#include <cstdarg>
using namespace std;

/*
*  The challange: find the maximum value of a arbitraty list of values wihtout
*	  the use of the conditional-control strucutes.  
*  NOTE: The use of the chooseOne<T>() and greatest<T>() functions were inspired
*		by Bench's int greatest(int, int) function use arrays to resolve a binary condition.
*/

template <class T>
T chooseOne(T first, T second, bool choice) {
	T order[2];
	order[0] = first;
	order[1] = second;
	return order[choice]; 
}	

template <class T>
T greatest( T first, T second )
{
	return chooseOne<T>(first, second, (first < second)); //if (f < s) true = 1, return s, else return f
}

template <class T>
class GetMax {
	  private:
	  T currentMax;
	  int state;
	  public:
	  GetMax() : state(0) { }
	  T operator()(const T& in) {
		   currentMax = greatest<T>(chooseOne<T>(in, currentMax, state) , in);
		   state = 1;
	  }
	  
	  T operator()() { return currentMax; state = 0; }
};						 
	   
template <class T, int len>
T maximum(T first, ...) {
	va_list args;
	va_start(args, first);
	GetMax<T> gm;
	gm(first);
	int length = len - 1; //One is used up by "first"
	for (; length > 0; --length) { gm(va_arg(args, T)); }
	va_end(args);
	return gm();
}

int main() {
	int a = maximum<int, 6>(55, 1, 65, 10, 37, 6);
	cout << a << endl;
	system("Pause");
	return 0;
}

[Bench]

I had to check myself in TC++PL whether or not (true == 1) was standard, or just a convention - as far as I can tell, its standard, at least for C++ '03.

As for eliminating the control loop - I would try a recursive solution - using your 'chooseOne' function with 'T' as a function pointer. one of those functions would be a do-nothing function, to terminate the recursion, the other would point to the current function as per the usual recursion idiom. (Similar to the way in which template metaprogramming loops are usually implemented)
- I doubt whether its very elegant. I can't see exactly how it could fit into that program either, it may take some restructuring, but its the only method of looping I can think of, which wouldn't involve a control structure somewhere.


This certainly turned out to be an interesting little problem though

This post has been edited by Bench: 16 February 2008 - 01:57 PM

[NickDMax]

yea I am running into problems with the recursion approach and may have to restructure my little approach.

One of the things that sort of tickles at the side of my brain is that the chooseOne() function evaluates both arguments, even though it only returns one... so if you have a recursive call as one of the arguments you risk a continuous loop... so I am trying to avoid that little bitty thing.

[Bench]

Perhaps I'm misunderstanding you, though, I don't believe you need to have chooseOne actually run either of the functions, if you pass around function pointers, you only need to call the function which chooseOne actually returns.

I've tried a little recursive factorial program to illustrate the idea

typedef int (*func)(int);

template <typename T>
T ternary_if(bool cond, T true_out, T false_out)
{
	T arr[2];
	arr[cond] = false_out;
	arr[!cond] = true_out;
	return arr[0];
}

int stop(int dummy)
{
	return 1;
}

int factorial(int howmany)
{
	func run = ternary_if( (howmany > 1) , factorial, stop );
	return howmany * run(howmany-1);;
}

int main() 
{
	std::cout << factorial(5);
} 

[NickDMax]

Yea, I understood that after re-reading your post... by using the function pointers you avoid the condition I was referring too...