10-GOTO-10 C++ Coding challenge #1

  • (3 Pages)
  • +
  • 1
  • 2
  • 3

31 Replies - 11704 Views - Last Post: 05 November 2012 - 02:29 PM

#1 NickDMax  Icon User is offline

  • Can grep dead trees!
  • member icon

Reputation: 2250
  • View blog
  • Posts: 9,245
  • Joined: 18-February 07

10-GOTO-10 C++ Coding challenge #1

Posted 15 December 2010 - 10:14 AM

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 :P

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. :)

Is This A Good Question/Topic? 1
  • +

Replies To: 10-GOTO-10 C++ Coding challenge #1

#2 ishkabible  Icon User is offline

  • spelling expret
  • member icon




Reputation: 1623
  • View blog
  • Posts: 5,713
  • Joined: 03-August 09

Re: 10-GOTO-10 C++ Coding challenge #1

Posted 15 December 2010 - 10:28 AM

i don't have a compiler right now to test but i have an idea of how i would do it.

edit: i was going to solve this using a radix sort then i realized that to make a radix sort there are several comparative loop statements needed for it to work. o well, it was a nice thought in my head.

This post has been edited by ishkabible: 18 December 2010 - 04:19 PM

Was This Post Helpful? 0
  • +
  • -

#3 ivarneli  Icon User is offline

  • New D.I.C Head

Reputation: 4
  • View blog
  • Posts: 1
  • Joined: 17-December 10

Re: 10-GOTO-10 C++ Coding challenge #1

Posted 17 December 2010 - 11:36 AM

Two possible solutions that don't use any library calls:

Solution 1:

Spoiler


Solution 2:

Spoiler


Both implementations assume an initial array length of at least 2. A check for this could be trivially added with the same technique, but has been left out for brevity.
Was This Post Helpful? 4
  • +
  • -

#4 NickDMax  Icon User is offline

  • Can grep dead trees!
  • member icon

Reputation: 2250
  • View blog
  • Posts: 9,245
  • Joined: 18-February 07

Re: 10-GOTO-10 C++ Coding challenge #1

Posted 17 December 2010 - 12:34 PM

Nice! Much shorter than my solution due to the use of &&. I thought I had spotted a bug but they don't see to be viable in test so I will have to over the logic a little more and see what I missed. I like that it really makes me think.
Was This Post Helpful? 0
  • +
  • -

#5 ishkabible  Icon User is offline

  • spelling expret
  • member icon




Reputation: 1623
  • View blog
  • Posts: 5,713
  • Joined: 03-August 09

Re: 10-GOTO-10 C++ Coding challenge #1

Posted 17 December 2010 - 02:48 PM

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.
Was This Post Helpful? 0
  • +
  • -

#6 baavgai  Icon User is offline

  • Dreaming Coder
  • member icon

Reputation: 5936
  • View blog
  • Posts: 12,862
  • Joined: 16-October 07

Re: 10-GOTO-10 C++ Coding challenge #1

Posted 18 December 2010 - 03:49 AM

This is probably as good as I'm going to get. :P

Spoiler

Was This Post Helpful? 1
  • +
  • -

#7 Munawwar  Icon User is offline

  • D.I.C Regular
  • member icon

Reputation: 162
  • View blog
  • Posts: 457
  • Joined: 20-January 10

Re: 10-GOTO-10 C++ Coding challenge #1

Posted 18 December 2010 - 06:33 AM

Made this from the different ideas I picked from others:
Spoiler


I don't know how statements separated by commas are allowed and evaluated within an expression:
int a,b;
cout<<(a=20, b=54)<<endl; //output: 54


Probably it's some undefined behavior, but both GCC and MS 2010 gives the same result!?

This post has been edited by Munawwar: 18 December 2010 - 06:34 AM

Was This Post Helpful? 1
  • +
  • -

#8 NickDMax  Icon User is offline

  • Can grep dead trees!
  • member icon

Reputation: 2250
  • View blog
  • Posts: 9,245
  • Joined: 18-February 07

Re: 10-GOTO-10 C++ Coding challenge #1

Posted 18 December 2010 - 07:18 AM

Quote

Note, I used the define so I could match the given main call. Perhaps not the best practice. But then, none of it is.


:) true. But I think it does help explore the language and what is possible.

I have been trying to see if there are any features in C++0x that might be jimmied into a solution. Lambdas seem promising but I have yet to really figure it out yet...

@Munawwar actually the comma operator is a sequence point and defines an order of execution. The expressions will be executed left to right and the overall expression will take the value of the right most expression.
Was This Post Helpful? 0
  • +
  • -

#9 ishkabible  Icon User is offline

  • spelling expret
  • member icon




Reputation: 1623
  • View blog
  • Posts: 5,713
  • Joined: 03-August 09

Re: 10-GOTO-10 C++ Coding challenge #1

Posted 18 December 2010 - 12:33 PM

ok i stole the idea from ivarneli but didn't do the same thing with it. did it in C

Spoiler

This post has been edited by ishkabible: 18 December 2010 - 12:57 PM

Was This Post Helpful? 1
  • +
  • -

#10 NickDMax  Icon User is offline

  • Can grep dead trees!
  • member icon

Reputation: 2250
  • View blog
  • Posts: 9,245
  • Joined: 18-February 07

Re: 10-GOTO-10 C++ Coding challenge #1

Posted 18 December 2010 - 01:05 PM

I posted this on the blog too but since the discussion has forked I will post it here too:

Quote

So on my quest for a C++0x solution I passed though functors and this was what I came up with...

Spoiler


and from there it was not hard to replace the functor with a lambda...
Spoiler

Was This Post Helpful? 0
  • +
  • -

#11 AdamSpeight2008  Icon User is offline

  • MrCupOfT
  • member icon


Reputation: 2271
  • View blog
  • Posts: 9,500
  • Joined: 29-May 08

Re: 10-GOTO-10 C++ Coding challenge #1

Posted 18 December 2010 - 01:13 PM

I'll apologise in advance, its not in c++, but some will transcode it to c++

To solve the challenge I thought about it mathematically.
What are the numerical value results of comparisons.
a == b ---> c
c=0 if a doesn't equal b, and -1 if it does.

Now if I take the absolute value of the result and multiply it by the value on the left of the comparison, I get the value back or Zero.

So if sum together the result of the possible solutions.
m = a( a>B )+b( b>a )+a( a==B )

I'll get the maximum of the two.

Spoiler

This post has been edited by AdamSpeight2008: 18 December 2010 - 01:13 PM

Was This Post Helpful? 1
  • +
  • -

#12 AdamSpeight2008  Icon User is offline

  • MrCupOfT
  • member icon


Reputation: 2271
  • View blog
  • Posts: 9,500
  • Joined: 29-May 08

Re: 10-GOTO-10 C++ Coding challenge #1

Posted 18 December 2010 - 02:10 PM

I had a thought how to make them generic.
Spoiler

Was This Post Helpful? 1
  • +
  • -

#13 ishkabible  Icon User is offline

  • spelling expret
  • member icon




Reputation: 1623
  • View blog
  • Posts: 5,713
  • Joined: 03-August 09

Re: 10-GOTO-10 C++ Coding challenge #1

Posted 18 December 2010 - 04:18 PM

i figured out another way around this problem, not as nifty as the && operator but it's unique out of the solutions i have seen so far. also you can use a really big array with this solution because it doesn't use recursion. only works on gcc however

Spoiler

This post has been edited by ishkabible: 18 December 2010 - 04:20 PM

Was This Post Helpful? 1
  • +
  • -

#14 NickDMax  Icon User is offline

  • Can grep dead trees!
  • member icon

Reputation: 2250
  • View blog
  • Posts: 9,245
  • Joined: 18-February 07

Re: 10-GOTO-10 C++ Coding challenge #1

Posted 18 December 2010 - 06:38 PM

@ishkabible -- Well using assembly language is not only a gcc option although the syntax is not standard.

@AdamSpeight2008 -- Nice mathematical solution for the Max function, although I think you can simplify it a bit. In C++ the expression a == b will evaluate to either 0 for false or 1 for true. However, unfortunately I have to give you a D- for the overall challenge because you use a For loop!!! WTF Can't you follow simple instructions :) back to the drawing board with you.
Was This Post Helpful? 0
  • +
  • -

#15 AdamSpeight2008  Icon User is offline

  • MrCupOfT
  • member icon


Reputation: 2271
  • View blog
  • Posts: 9,500
  • Joined: 29-May 08

Re: 10-GOTO-10 C++ Coding challenge #1

Posted 18 December 2010 - 08:37 PM

@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.
Was This Post Helpful? 0
  • +
  • -

  • (3 Pages)
  • +
  • 1
  • 2
  • 3