Author Topic: C Coding Competition - Win an Arduino  (Read 7750 times)

0 Members and 1 Guest are viewing this topic.

Offline Chet T16

  • Frequent Contributor
  • **
  • Posts: 522
  • Country: ie
    • Retro-Renault
C Coding Competition - Win an Arduino
« on: July 19, 2012, 12:10:47 am »
Firstly, I've asked Dave and he said it's fine to do this.

I have a little Arduino Pro Mini to give away to the winner of this coding competition. They're tiny and you could fit one anywhere!



To win the competition all you have to do is write the code which can find the first five "Perfect Numbers" in the fastest time.

From wikipedia:
Quote
In number theory, a perfect number is a positive integer that is equal to the sum of its proper positive divisors, that is, the sum of its positive divisors excluding the number itself.

For example, the first perfect number is 6, as the factors of 6 (excluding itself) are 1, 2 and 3, and 1+2+3=6.

The first four numbers are:

6
28
496
8128

The fifth is a little bigger  ;D

Rules:
  • The code must be plain old C
  • Only standard libraries to be used
  • Numbers must be found based on the definition above i.e. by finding and adding factors only
  • nything that runs for over an hour will be disqualified  ;)

You can PM me your code and i will compile and run it on my machine, it's a bit slow so it may give a time greater than you measured but rest assured all code will be ran equally.

Closing date is undecided until i see what interest there is but i will give plenty of notice.

Chet
Paid Electron Wrestler
 

Offline RCMR

  • Frequent Contributor
  • **
  • Posts: 405
Re: C Coding Competition - Win an Arduino
« Reply #1 on: July 19, 2012, 12:38:28 am »
You don't state the target system -- so are we to assume it's an Arduino?
 

Offline Chet T16

  • Frequent Contributor
  • **
  • Posts: 522
  • Country: ie
    • Retro-Renault
Re: C Coding Competition - Win an Arduino
« Reply #2 on: July 19, 2012, 12:43:46 am »
I'll be compiling with gcc in cygwin. I think an arduino would crap itself!
Chet
Paid Electron Wrestler
 

Offline slateraptor

  • Frequent Contributor
  • **
  • Posts: 833
  • Country: us
Re: C Coding Competition - Win an Arduino
« Reply #3 on: July 19, 2012, 12:53:03 am »
To win the competition all you have to do is write the code which can find the first five "Perfect Numbers" in the fastest time.

The challenge states "find" rather than calculate...look-up tables count? ;)

EDIT:

  • Numbers must be found based on the definition above i.e. by finding and adding factors only

Not winning. :P
« Last Edit: July 19, 2012, 12:58:36 am by slateraptor »
 

Offline adam1213

  • Regular Contributor
  • *
  • Posts: 119
  • Country: au
Re: C Coding Competition - Win an Arduino
« Reply #4 on: July 19, 2012, 02:07:01 am »
somehow this sounds like a university assignment.

You could just directly print the numbers (solutions won't get much faster than this)
 

Offline slateraptor

  • Frequent Contributor
  • **
  • Posts: 833
  • Country: us
Re: C Coding Competition - Win an Arduino
« Reply #5 on: July 19, 2012, 03:30:06 am »
somehow this sounds like a university assignment.

More like a Project Euler puzzle with facebook puzzle caveats.
 

Offline slateraptor

  • Frequent Contributor
  • **
  • Posts: 833
  • Country: us
Re: C Coding Competition - Win an Arduino
« Reply #6 on: July 19, 2012, 04:01:57 am »
@Chet T16: PM sent. :)

P.S. Benchmarks as entries are tested would be nice.
« Last Edit: July 19, 2012, 04:20:57 am by slateraptor »
 

Offline free_electron

  • Super Contributor
  • ***
  • Posts: 7261
  • Country: us
    • SiliconValleyGarage
Re: C Coding Competition - Win an Arduino
« Reply #7 on: July 19, 2012, 06:13:51 am »
void main void{printf ("6\n28\n496\n8128\n33550336")};

you can keep the arduino. don't need it.

« Last Edit: July 19, 2012, 06:15:34 am by free_electron »
Professional Electron Wrangler.
Any comments, or points of view expressed, are my own and not endorsed , induced or compensated by my employer(s).
 

Offline nitro2k01

  • Frequent Contributor
  • **
  • Posts: 844
  • Country: 00
Re: C Coding Competition - Win an Arduino
« Reply #8 on: July 19, 2012, 06:30:54 am »
  • Numbers must be found based on the definition above i.e. by finding and adding factors only
This raises the question of what optimizations we're allowed to do, exactly. For example, are we allowed to check only every second number, under the assumption that all perfect numbers are even? (If odd perfect numbers exist, they're certainly much greater than the numbers relevant for this contest.) The current reading of that rule makes sure the programs are going to heat your room more than your brain. A more interesting rule, IMO, would be:
  • Each number must be iterated and individually qualified according to known general mathematical properties of perfect numbers.
That way, the contest would actually be interesting.
Whoa! How the hell did Dave know that Bob is my uncle? Amazing!
 

Offline Mechatrommer

  • Super Contributor
  • ***
  • Posts: 9320
  • Country: my
  • reassessing directives...
Re: C Coding Competition - Win an Arduino
« Reply #9 on: July 19, 2012, 06:33:47 am »
next stop... the fastest sin(x) generator. prize = my "untested" PC display card backyard. winner pay shipping.
rule... no table lookup. memory consumption... less than 11 bytes.
if something can select, how cant it be intelligent? if something is intelligent, how cant it exist?
 

Offline amyk

  • Super Contributor
  • ***
  • Posts: 6587
Re: C Coding Competition - Win an Arduino
« Reply #10 on: July 19, 2012, 06:59:56 am »
  • Numbers must be found based on the definition above i.e. by finding and adding factors only
This raises the question of what optimizations we're allowed to do, exactly. For example, are we allowed to check only every second number, under the assumption that all perfect numbers are even? (If odd perfect numbers exist, they're certainly much greater than the numbers relevant for this contest.) The current reading of that rule makes sure the programs are going to heat your room more than your brain. A more interesting rule, IMO, would be:
  • Each number must be iterated and individually qualified according to known general mathematical properties of perfect numbers.
That way, the contest would actually be interesting.
The problem with competitions like this is that the output is known a priori and so a highly optimising compiler could replace the entire program with one output, as the program takes no external input. This would make all your attempted algorithmic optimisations useless, and in fact may confuse the optimiser so it no longer can produce that truly optimal solution. Programs that consume input, however, are much more interesting and that is why you'll see a lot of competitions like this one specify the expected output given a particular input.

 

Offline Chet T16

  • Frequent Contributor
  • **
  • Posts: 522
  • Country: ie
    • Retro-Renault
Re: C Coding Competition - Win an Arduino
« Reply #11 on: July 19, 2012, 07:18:52 am »
OK, to clarify, the intention is to find the first five numbers by finding the factors and adding them up and checking the sum. The idea then is to find the best possible way of factorising large numbers as this is where 99.999% of the time goes.

This is based on a university assignment I had a few years ago while learning C, not something due now :p
Chet
Paid Electron Wrestler
 

Offline _Sin

  • Regular Contributor
  • *
  • Posts: 247
  • Country: gb
Re: C Coding Competition - Win an Arduino
« Reply #12 on: July 19, 2012, 04:59:12 pm »
OK, to clarify, the intention is to find the first five numbers by finding the factors and adding them up and checking the sum. The idea then is to find the best possible way of factorising large numbers as this is where 99.999% of the time goes.

This is based on a university assignment I had a few years ago while learning C, not something due now :p

Why would you generate a number as a sum of factors, and then factorise it?

The following code ought to print out the first 8 perfect numbers with all factors, but it's not done the way you've asked so I guess it's not valid (and I'm not interested in the arduino anyway)

Code: [Select]
#include <stdio.h>
#include <math.h>

int isPrime(long long val)
{
int p,i;
if(val == 2) return 1;
if((val & 1) == 0) return 0;

p = (int) sqrt((float)val);
for(i = 3 ; i <= p ; i ++)
{
if((val % i) == 0) return 0;
}
return 1;
}

void main()
{
int i,j;
for(i = 2 ; i < 32 ; i++)
{
if(isPrime(i))
{
long long pn = (1 << i) - 1;
if(isPrime(pn))
{
printf("%lld\n", ((long long) (1 << (i - 1))) * pn);
for(j = 0 ; j < i; j ++)
{
printf("%d ", 1 << j);
}
for(j = 0 ; j < (i - 1); j ++)
{
printf("%lld ", (((long long)1) << j) * pn);
}
printf("\n\n");
}
}
}
}
Programmer with a soldering iron - fear me.
 

Offline grumpydoc

  • Super Contributor
  • ***
  • Posts: 2688
  • Country: gb
Re: C Coding Competition - Win an Arduino
« Reply #13 on: July 19, 2012, 07:35:04 pm »
Here is an integer only solution which is fairly compact, though almost totally naïve in its approach.

Code: [Select]
include <stdio.h>
#include <limits.h>

void main(int argc, char *argv[])
{
  unsigned int p, f, t;

  for (p = 2; p < UINT_MAX; p += 2) {
    if (p == 6 || (p-1)/9*9 == (p-1)) {
      for (t = 0, f = 1; f*f <= p; f++) {
if (p/f*f == p) {
  t += f;
  if (p/f != f && f!=1) t += p/f;
}
      }
      if (t == p)
printf ("%d\n", p);
    }
  }
}

I'm not sure that it's a terribly interesting problem at the level of "print the first 6" though. I agree with the others who have pointed out that once you have exploited some property of perfect numbers such as "they're probably even"1 to avoid factorising each positive integer summing the factors and checking to see if that equals the original number you might as well go for the printf("6\n28\n496\n8128\n33550336\n"); approach.

_Sin's code is actually more interesting, and much faster (Oh, BTW I don't want the Arduino either). It exploits the fact that 2p-1(2p-1) is an even perfect number if 2p-1 is prime. the test for primeality in that code is a very simple one so, it's not as interesting as it could be.

If you want an interesting problem prove that 2p-1(2p-1) is perfect for p=25964951 :)

[1] It has not been proven that there are no odd perfect numbers.
« Last Edit: July 19, 2012, 07:38:20 pm by grumpydoc »
 

Offline Chet T16

  • Frequent Contributor
  • **
  • Posts: 522
  • Country: ie
    • Retro-Renault
Re: C Coding Competition - Win an Arduino
« Reply #14 on: July 19, 2012, 07:52:10 pm »
There are lots of properties of perfect numbers that can be exploited but thats not the idea, its about being able factorise and add all the numbers up to and including the last one - following the definition of a perfect number
Chet
Paid Electron Wrestler
 

Offline grumpydoc

  • Super Contributor
  • ***
  • Posts: 2688
  • Country: gb
Re: C Coding Competition - Win an Arduino
« Reply #15 on: July 19, 2012, 08:13:49 pm »
So the competition is about being able to write a fast factoriser.

Sorry, I'll do my own crypto cracking, not yours :)

It's still not interesting if you only want the first 5 or 6 perfect Nos.
 

Offline Chet T16

  • Frequent Contributor
  • **
  • Posts: 522
  • Country: ie
    • Retro-Renault
Re: C Coding Competition - Win an Arduino
« Reply #16 on: July 19, 2012, 08:22:41 pm »
So the competition is about being able to write a fast factoriser.

Sorry, I'll do my own crypto cracking, not yours :)

It's still not interesting if you only want the first 5 or 6 perfect Nos.

I'm sorry to disappoint but the competition is all i say it is, no other motives. I thought it might be nice to have something different than the threads that descend into negativity that have become so common on here lately but it looks likes that's failed!
Chet
Paid Electron Wrestler
 

Offline SeanB

  • Super Contributor
  • ***
  • Posts: 15259
  • Country: za
Re: C Coding Competition - Win an Arduino
« Reply #17 on: July 19, 2012, 08:28:26 pm »
Nice idea, nice to do, and I would enter if I could code better than a dyslexic gibbon let loose on a keyboard.............

Oh wait, That is me all the time I think. ;)

 

Offline slateraptor

  • Frequent Contributor
  • **
  • Posts: 833
  • Country: us
Re: C Coding Competition - Win an Arduino
« Reply #18 on: July 19, 2012, 08:45:30 pm »
I'm sorry to disappoint but the competition is all i say it is, no other motives. I thought it might be nice to have something different than the threads that descend into negativity that have become so common on here lately but it looks likes that's failed!

:( Well, I guess I'll be going back to Project Euler to get my coding challenge fix...a shame, really.
« Last Edit: July 19, 2012, 08:57:53 pm by slateraptor »
 

Offline Chet T16

  • Frequent Contributor
  • **
  • Posts: 522
  • Country: ie
    • Retro-Renault
Re: C Coding Competition - Win an Arduino
« Reply #19 on: July 19, 2012, 08:58:54 pm »
If you want something interesting I have a program that takes a 4 digit input (numbers and letters) and outputs a 4 digit code (numbers only) that I would like to reverse engineer :D
Chet
Paid Electron Wrestler
 

Offline Chet T16

  • Frequent Contributor
  • **
  • Posts: 522
  • Country: ie
    • Retro-Renault
Re: C Coding Competition - Win an Arduino
« Reply #20 on: July 19, 2012, 09:00:55 pm »
Oh and regarding the challenge this is obviously aimed at people who only have a little experience coding. People like me!
Chet
Paid Electron Wrestler
 

Offline _Sin

  • Regular Contributor
  • *
  • Posts: 247
  • Country: gb
Re: C Coding Competition - Win an Arduino
« Reply #21 on: July 19, 2012, 09:17:30 pm »
I wasn't trying to be negative, I just went off on a tangent and thought someone might be interested...

Programmer with a soldering iron - fear me.
 

Offline slateraptor

  • Frequent Contributor
  • **
  • Posts: 833
  • Country: us
Re: C Coding Competition - Win an Arduino
« Reply #22 on: July 19, 2012, 09:36:16 pm »
If you want something interesting I have a program that takes a 4 digit input (numbers and letters) and outputs a 4 digit code (numbers only) that I would like to reverse engineer :D

Roughly 15 million input permutations mapped to 10k possible outputs...brute forcing a reverse engineered sol'n would be trivial. :-\
 

Offline Chet T16

  • Frequent Contributor
  • **
  • Posts: 522
  • Country: ie
    • Retro-Renault
Re: C Coding Competition - Win an Arduino
« Reply #23 on: July 19, 2012, 09:47:33 pm »

Roughly 15 million input permutations mapped to 10k possible outputs...brute forcing a reverse engineered sol'n would be trivial. :-\

Is that an offer? :p
Chet
Paid Electron Wrestler
 

Offline grumpydoc

  • Super Contributor
  • ***
  • Posts: 2688
  • Country: gb
Re: C Coding Competition - Win an Arduino
« Reply #24 on: July 19, 2012, 09:58:23 pm »
Quote
I wasn't trying to be negative, I just went off on a tangent and thought someone might be interested...

Which I thought to be perfectly valid, it's much more efficient to generate perfect numbers from Mersenne primes than by factorising each positive integer. Even if you replace the "computing 101" factorisation algorithm from the code I posted with a more efficient one it will still be slower than yours at generating perfect numbers.

Yours can still be improved though as your primeality test is fairly simplistic - perhaps by dividing by primes less than the square root of the number of interest, rather than potentially by all integers >= 3. Or even just dividing by odd numbers.

Chet T16 - the code I posted was intentionally a bit simplistic but if you are a beginner in C programming it is probably worth making sure you understand it, then make sure you understand _Sin's. Then see if you can spot the (obviously deliberate :) ) errors of coding style in both - there are things in _Sin's that I would reject at code review. There again there are things in mine that I would also question now that I re-read it. No-one's perfect!!
 


Share me

Digg  Facebook  SlashDot  Delicious  Technorati  Twitter  Google  Yahoo
Smf