[AdamSpeight2008]

ishkabible, on 17 December 2010 - 09:48 PM, said:

i didn't get how it worked for a while. i was scratching my head trying to figure out how it didn't just loop forever.

If the first comparision evaluates to false then the AND expression can never be true, so exits early.

[ishkabible]

i would have to agree with Adam on this one. he did not use any conditional expresion to make that control structure. c++0x will have ranged based for loop that can do the same thing.

on another note i expanded my inline assembly solution to work with MSVC

Spoiler

#include <stdio.h>
#include <stdlib.h>

int Max(int _array_[],size_t _size_) {
	int _retval_ = _array_[0];
	--_size_;
	#ifdef __GNUC__
	asm (
		"	movl $1,%%esi\n"
		"FOR:\n"
		"	cmpl %%edx,%%esi\n"
		"	jnl FOREND\n"
		"	movl %%esi,%%eax\n"
		"	imull $4,%%eax\n"
		"	addl %%ecx,%%eax\n"
		"	movl (%%eax),%%eax\n"
		"	cmp %%eax,%%ebx\n"
		"	jnl IFEND\n"
		"	movl %%eax,%%ebx\n"
		"IFEND:\n"
		"	incl %%esi\n"
		"	jmp FOR\n"
		"FOREND:\n"
		:"=b"(_retval_)
		:"b"(_retval_),"c"(_array_),"d"(_size_)
	);
	#else
	__asm {
		mov ebx, _retval_
		mov ecx, _array_
		mov edx, _size_
		mov esi,1
	FOR:
		cmp esi,edx
		jnl FOREND
		mov eax,esi
		imul eax,4
		add eax,ecx
		mov eax,[eax]
		cmp ebx,eax
		jnl IFEND
		mov ebx,eax
	IFEND:
		inc esi
		jmp FOR
	FOREND:
		mov _retval_,eax
	}
	#endif
	return _retval_;
}

int main() {
    int x[] = {1,7,3,7,9,3,1,56,83,12};
    size_t size = sizeof(x)/sizeof(x[0]);
	int i = Max(x,size);
	printf("%i\n",i);
	scanf("%i");
    return 0;
}

edit: also i figured out how it worked Adam. you can see in my earlier solution that i used it.

This post has been edited by ishkabible: 18 December 2010 - 09:08 PM

[shad0wk1]

This might be a bit too much to me, but I want to try too.

Spoiler

Note that for loop just used for output, not the operation. And very simple because I still a beginner.

#include <iostream>
#include <algorithm>
using namespace std;
 
int main()
{
    int array[] = {3,1,4,15,9,2,6,5,35,8,97,93,23,84,62,64,33,83,27,950,28,841,971,69,39,937,510};
    int size = sizeof(array)/sizeof(int);
    cout << "The array is as follows: " ;
    for (int counter=0;counter<size;counter++)
    {
        cout << array[counter] << " ";
    }
    cout << endl;
    cout << "The largest element is : " << *max_element(array,array+size) << endl;
    sort(array,array+size);
    cout << "The sorted array is : " ;
    for (int counter=0;counter<size;counter++)
    {
        cout << array[counter] << " ";
    }
    cin.get();
    return 0;
}

This post has been edited by shad0wk1: 18 December 2010 - 09:24 PM

[NickDMax]

AdamSpeight2008, on 18 December 2010 - 10:37 PM, said:

@NickDMax Rules you seemed to have forgotten yourself, as your last two used for each.

I was sure of if it was.
False = 0, True=-1 (Not 0)
False = 0, True= 1

IComparable say result is < 0 for A being less than B (it doesn't say it has to be -1). So the result could be the result of a simple subtraction A-B. The sign Function normalises this to range -1 to +1.

The for_each is not a control structure, it is a template function. i.e. it is not on the list of banned structures + :?-operator.

Though you are correct that for_each is a pretty weak solution. So is using stl::max_element but the idea of the challenge was find different ways of approaching the problem rather than the usual direct approach. So I specifically allowed stl solutions include max_element because they are not on the list of banned structures.

As for the values of a boolean expression, they change from language to language. In QBasic and old VB a boolean expression generally evaluated to 0 or ~0 which is -1 -- a property that I often exploited back in my BASIC programming days. I don't know what VB.Net does with boolean expressions or even if they are a "thing" in .NET.

[AdamSpeight2008]

Recursion who need that crutch.

Spoiler

not me. This one going screw with you.

  Function Max(Of T As IComparable)(ByVal c As T()) As T
    Return Enumerable.Aggregate(c, c(0), Function(a, e) (Function(_x As T, _y As T) {_y, _x, _x}(Math.Sign(_x.CompareTo(_y)) + 1))(a, e))
  End Function

And still generic.
FTW!!

This post has been edited by AdamSpeight2008: 18 December 2010 - 11:09 PM

[baavgai]

I previously did my maxPair as:

Spoiler

int maxPair(int x, int y) {
	(y>x) && (x=y);
	return x;
}

I got the idea reading this that you could also do:

Spoiler

int maxPair(int x, int y) { return ((x>y) * x) + ((x<=y) * y); }

Which has it's own charm.

Further, I notice there was another looping structure available that hadn't been forbidden. It was even in the title! So, rather than loop by all that stack pushing and jumping, I thought old school would be fun.

What you are about to see should only be done by trained professionals. Please, don't do this at home. Ever.

Also, only works in GCC.

Spoiler

int findMax(int *a, int pos) {
	unsigned int g_again = (unsigned int)&&top, g_last = (unsigned int)&&last;
	int result = a[pos--] - 1;
top:
	int nextValue = a[pos--];
	int nextValueGt = (nextValue>result);
	result = (!nextValueGt)*result+(nextValueGt)*nextValue;
	
	int lastValue = (pos<0);
	unsigned int g_next = ((!lastValue)*g_again+(lastValue)*g_last);
	goto *g_next;
	
last:
	return result;
}

Two tricks here. Gotos ( ack, I used gotos ). And GCC's ability to reference a label by a memory location. This is probably how I'd do it in assembly.

I suppose you could make a more generic version with function pointers...

[Munawwar]

Hey, I thought using assembly was cheating, even though NickDMax didn't specifically state that in the question.
ishkabible you are banned ....
Just kidding. It's great to see people try out new things. This question even sparked the curiosity of a VB programmer . Nice!

This post has been edited by Munawwar: 19 December 2010 - 06:40 AM

[NickDMax]

Actually I was hoping that someone WOULD use assembly. The rules only ban those specific structures and 1 operator. Anything outside of those is perfectly ok.

Though if you use goto you have to live with yourself. I am sure that baavgai had to really concentrate on actually getting his figures to type "goto" into actual code!

@baavgai I wasn't aware the GCC could do that. I have always been irritated that C/C++ didn't have the ability to change goto labels into addresses. I am pretty sure that this CAN be done using inline assembly in VS but I have not worked up an example. However I believe that C/C++ labels are treated like assembly labels inside of assembly language so you could do anything you wanted with them. I will check it out.

[ishkabible]

inline assembly in MSVC can jump to labels defined outside the assembly block but gcc cant. the other thing is that inline asm is not cap sensitive so the following is ambiguous.

L1:
__asm {
   jMp l1
}
l1:

also notice that i used a capital M becuase im showing that it's not caps sensitive at all. i believe this is however fine if you leave it in c/c++ code. gcc wont allow you to jump to a label inside assembly nor form outside to a label inside assembly. also gcc isn't caps sensitive either.

edit: also i believe that the following code will allow you to reference a label in MSVC but i didn't test it

void(*mylable)();
asm {
   mov eax,somelable
   mov mylable,eax
}
somelable:

edit2: you may also want to use a void pointer for this instead of a function pointer because this code will expect a return statement somewhere and will most likly cause something to crash or loop endlessly. bottom line i have no clue what this will do, it's just a hunch.

This post has been edited by ishkabible: 19 December 2010 - 11:17 AM

[Munawwar]

So I was thinking what would be the shortest non-STL solution (shortest code). This is the best I could get:

Spoiler

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

int findMax(int *ar, int size, int pos=0, int temp=0) {
    return (pos<size && (temp=( (int[]){(temp=findMax(ar,size,pos+1)),ar[pos]}[(ar[pos]>temp)] ))) || (temp=numeric_limits<int>::min()), temp;
}
int main(){
    int array[] = { 3, 1, 4, 15, 9, 2, 6, 5, 35, 8, 97, 93, 23, 84, 62, 64, 33, 83, 27, 950, 0, 841, 971, 69, 39, 937, 510 };
    cout << findMax(array, sizeof(array)/sizeof(array[0])) << endl;
    return 0;
}

This post has been edited by Munawwar: 19 December 2010 - 02:56 PM

[ishkabible]

lol nice one. not very readable but defiantly neat!! i found out that GCC will allow you to jump to other labels defined in other asm blocks and tried to use it to rework the control flow of my Radix Sort by no such luck. i may need to use a debugger for it.

[shib.paul]

NickDMax, on 15 December 2010 - 09:14 AM, said:

I was instructed to spam this forum with a link to my C++ coding challenge. Of course everyone here reads my blog (10-GOTO-10) so of course this is redundant

The challenge:

Quote

Problem: Write a program that will find the largest element of an arbitrary array without using any conditional structures: banned { if/if-else/switch/for/while/do/?:-operator }

bonus: Display the array sorted from smallest to largest with the same conditions.

i.e. write the function max in this little program:

int main() {
    int array[] = { 3, 1, 4, 15, 9, 2, 6, 5, 35, 8, 97, 93, 23, 84, 62, 64, 33, 83, 27, 950, 28, 841, 971, 69, 39, 937, 510 };
    cout << "Largest element is: " << max(array) << endl;
    return 0;
}

...hints...


Post all answers in SPOILER tags!
[spoiler] [code] -- paste your answer like this -- [/code] [/spoiler]

There are already two STL solutions counted get yours in before all the different avenues are explored.

Here is a simple solution.

Spoiler

#include<iostream>
using namespace std;
#define SIZE 10

int a[SIZE]={2, 10, 87, 1000, 23, 31, 45, 85, 988, 344};
int cnt=1;
static int iMax=a[0];

int getMax()
{
	iMax = iMax*(iMax>a[cnt]) + a[cnt]*(a[cnt]>iMax);

	return cnt++<SIZE && getMax();
}

int main()
{
	getMax();
	cout << "Maximum = " << iMax << endl;
	return 0;
}

This post has been edited by NickDMax: 20 December 2010 - 07:46 AM
Reason for edit:: added code tags and spoiler tags

[baavgai]

Well, if asm is on the table...

I've already used gotos. Here's the last silly.

Spoiler

int findMax(int *a, int size) {
	int result;
	asm (
		"movl (%%eax),%%ebx\n"
		"TOP:\n"
		"	dec %%ecx\n"
		"	jz DONE\n"
		"	addl $4, %%eax\n"
		"	cmp (%%eax),%%ebx\n"
		"	jnl TOP\n"
		"	movl (%%eax),%%ebx\n"
		"	jmp TOP\n"
		"DONE:\n"
		:"=b"(result)
		:"a"(a),"c"(size)
	);
	return result;
}

I kind of burnt myself putting that one together. Bloody 64bit machine. Compiled in 32 bits for simple sanity.

[NathanMullenax]

Hey folks. This is my first post, so I hope I'm not tagging it wrong. This could probably be shortened quite a bit. Also, one could certainly do better than a bubble-sort.

Spoiler

#include<iostream>
int 
max(int b, int c)
{
    int x( b*(b>c) ),y( c*(c>B)/> ),z( c*(c==B)/> );
    return x + y + z;
}

int
min(int b, int c)
{
    return b*(b<c) + c*(c<B)/> + c*(b==c);
}

int 
max( int const *b, int cm, size_t start, size_t len )
{
    int m = max(cm,b[start]);
    bool quittin_time = (start < len - 1 && (m=max(b,m,start+1,len)),true );
    return m;
}

int
max( int const *b, size_t start, size_t len )
{
    int m(b[start]),i(start+1);
    bool quittin_time = (start < len - 1 && (m=max(b,m,start+1,len)),true );
    return m;
}

int 
max( int const *b )
{
    return max( b, 0, 27 );
}

bool
sort( int *a, int *b )
{
    bool ck = (*a)==min(*a,*B)/>;
    int aa = *a;
    int bb = *b;
    *a = min(aa,bb);
    *b = max(aa,bb);
    return ck;
}

bool
sort( int *b, bool sorted, size_t start, size_t len )
{
    sorted = sort( b+start, b+start+1 ) && sorted;
    bool g = (start < len-1) && (sorted=sort(b,sorted,start+1,len) && sorted,true);
    return sorted;
}

bool
sort( int *b )
{
    return sort(b,true,0,27) || sort(B)/>;
}

void
print_ns( int *b, size_t i, size_t len )
{
    bool ck = (i<len) && ((std::cout << *(b+i) << "\n"), print_ns(b,i+1,len),true);
}

int
main()
{
    int array[] = { 3, 1, 4, 15, 9, 
                    2, 6, 5, 35, 8, 
                    97, 93, 23, 84, 62, 
                    64, 33, 83, 27, 950, 
                    28, 841, 971, 69, 39, 
                    937, 510 };
    std::cout << max(array);
    
    sort(array);
    
    print_ns(array,0,27);
    return 0;
}

[NathanMullenax]

Ack. Every uppercase 'B' is supposed to be a lowercase one. Some formatting glitch, it appears.