Overclock.net banner

Are you interested in participating in and/or helping organise and post these programming challenges

  • I want to participate.

    Votes: 0 0.0%
  • I want to contribute by helping posting and organise these challenges.

    Votes: 0 0.0%
  • I'll only take part if other people are willing to participate.

    Votes: 0 0.0%
  • I can help and participate - I love programming!

    Votes: 0 0.0%
  • I do not wish to participate or help.

    Votes: 0 0.0%
Status
Not open for further replies.
1 - 20 of 306 Posts

·
Some call me... Bifford
Joined
·
5,265 Posts
Discussion Starter #1
{Unregistered} : Redirect to this thread.

OK,

Since we have a few programmers here I thought I would issue a programming challenge. It really isn't that difficult, but I would like you to focus on elegance and effciency. There really aren't any rules just submit your code as a text file and compilied (if required). Depending on the turnout I may try to do this on a weekly basis. There aren't any prizes this is just for fun.

Challenge #1:

Given a comma seperated list of numbers:
1,2,3,5,10,11,12,13,25

Convert to
1-3,5,10-13,25

So that sequential numbers are listed as start-end and all others are simply comma seperated. Please assume that the initial list is in order, but of any length. I recently had to do this for a client and thought it was something that might work as a simple challenge.

Please respond to this thread if you are interested in playing. The deadline for entries is 1/25/06 11:59 PM GMT-6. Try to stick to one of the top 20 languages on this list.

Current challenge at post #10
 

·
Some call me... Bifford
Joined
·
5,265 Posts
Discussion Starter #2
Times up, Xaimus is the only one that got an entry in.

Code:

Code:
#include <iostream>
#include <string>
#include <sstream>

using namespace std;

string intToStr(int);
bool isNumber(char);
bool isNegate(char);

int main(int argv, char** argc) {
    if (argv < 2) {
        cout << "usage: \
"
             << argc[0] << " list,of,integers\
";
        return 1;
    }

    string list = argc[1], output;
    bool start = true, chain = false, negate = false;
    int current = 0, next = 0, i = 0;

    while (isNumber(list[i]) || isNegate(list[i])) {
        if (isNumber(list[i])) {
            current = (current * 10) + (list[i] - '0');
        } else {
            negate = !negate;
        }
        i++;
    }
    if (negate) {
        current *= -1;
    }

    while (i < list.length()) {
        negate = false;
        next = 0;

        if (isNumber(list[i]) || isNegate(list[i])) {
            while(isNumber(list[i]) || isNegate(list[i])) {
                if (isNumber(list[i])) {
                    next = (next * 10) + (list[i] - '0');
                } else {
                    negate = !negate;
                }
                i++;
            }
            if (negate) {
                next *= -1;
            }

            if (next - 1 == current) {
                if (!chain) {
                    if (start) {
                        start = false;
                    } else {
                        output += ',';
                    }
                    output += intToStr(current) + '-';
                    chain = true;
                }
            } else {
                if (chain) {
                    output += intToStr(current);
                    chain = false;
                } else {
                    if (start) {
                        start = false;
                    } else {
                        output += ',';
                    }
                    output += intToStr(current);
                }
            }
            current = next;
        } else {
            i++;
        }
    }

    if (chain || start) {
        output += intToStr(next);
    } else {
        output += ',' + intToStr(next);
    }
    cout << output << endl;
    return 0;
}

string intToStr(int x) {
    ostringstream o;
    o << x;
    return o.str();
}

bool isNumber(char x) {
    return x <= '9' && x >= '0';
}

bool isNegate(char x) {
    return x == '-';
}
 

·
Some call me... Bifford
Joined
·
5,265 Posts
Discussion Starter #3
OK, Here is the next challenge.

Create a web-based application to display Pascals Triangle. Please allow your code to create any number of levels based on user input. Also include processing time.

Ex. (excuse spacing)

1
11
121
1331

Excuted to 4 levels.

Deadline for entries is Feb. 10th 11:59 PM GMT-6.
 

·
Registered
Joined
·
18 Posts
10 minutes of coding
5 minutes of refreshing PHP knowledge
5 minutes for debugging and formatting


Code:

Code:
<?
/* Challenge #2
Pascal Triangle
$_GET['level'] represents the triangle's level.
*/

$level = $_GET['level'];
$triangle = array();

$triangle[0][0] = 1;
for ($i = 1; $i < $level; $i++)
{
    $triangle[$i][0] = 1;
    $triangle[$i][count($triangle[$i-1])] = 1;
    for ($j = 1; $j < count($triangle[$i-1]); $j++)
    {
        $triangle[$i][$j] = $triangle[$i-1][$j-1] + $triangle[$i-1][$j];
    }
}

echo "[TABLE]";
for ($i = 0; $i < $level; $i++)
{
    echo "[TR]";
    for ($j = 0; $j < count($triangle[$i]); $j++)
        echo "[TD]".$triangle[$i][$j]."[/TD]";
    echo "[/TR]";
}
echo "[/TABLE]";
?>
Could be improved of course. For example get rid of the multidimensional array and render directly.
 

·
Some call me... Bifford
Joined
·
5,265 Posts
Discussion Starter #5
Quote:

Originally Posted by FaKk2
10 minutes of coding
5 minutes of refreshing PHP knowledge
5 minutes for debugging and formatting


Code:

Code:
<?
/* Challenge #2
Pascal Triangle
$_GET['level'] represents the triangle's level.
*/

$level = $_GET['level'];
$triangle = array();

$triangle[0][0] = 1;
for ($i = 1; $i < $level; $i++)
{
    $triangle[$i][0] = 1;
    $triangle[$i][count($triangle[$i-1])] = 1;
    for ($j = 1; $j < count($triangle[$i-1]); $j++)
    {
        $triangle[$i][$j] = $triangle[$i-1][$j-1] + $triangle[$i-1][$j];
    }
}

echo "[TABLE]";
for ($i = 0; $i < $level; $i++)
{
    echo "[TR]";
    for ($j = 0; $j < count($triangle[$i]); $j++)
        echo "[TD]".$triangle[$i][$j]."[/TD]";
    echo "[/TR]";
}
echo "[/TABLE]";
?>
Could be improved of course. For example get rid of the multidimensional array and render directly.
Very nice. I didn't think of doing that way, I used a mathmatical formula to produce the results. Nice job of thinking simple. It is often times the simplest solution that is the best.
 

·
Some call me... Bifford
Joined
·
5,265 Posts
Discussion Starter #6
OK, I borrowed this one from another site.

Find the largest number less than 100 quintillion* which is a palindrome and is also divisible by all primes between 10 and 30.

* American quintillion

EDIT: All entries must also include a manner of documenting how long it takes to find the answer.

PM me your answer and it if is correct I will then post your code after the deadline. Until then I will just post who completed here. The deadline for entries is Oct 14th. As stated before this is from a know challenge site, so don't just google the answer. This is about programming not the use of google.


===========================================
Results
===========================================

rabidgnome229: Solution in Progress
Burn: Solution in Progress
FrankenPC: Completed Challenge (~15 seconds)
someone153: Solution in Progress
sniperscope: Completed Challenge (~5 seconds)
 

·
Some call me... Bifford
Joined
·
5,265 Posts
Discussion Starter #7
Ok times up.

sniperscope and FrankenPC completed the challenge.

Kudos go to both members as they were able to use some lateral thinking and come up with a solution without using the obvious route. In this particular case the obvious route would have been to start with the largest possible number "99999999999999999999" and work your way down until a match was found. As some of you found out that this takes a very very long time. What I found most interesting about this excersize is that the two solutions are completely different. I will post my code and a brief explanation of what I did. I will let the other two guys do the same.

My Way (which as it turns out isn't the fastest):

Code:

Code:
 class Program
{
static void Main(string[] args)
{
//Initialize Timer
DateTime startTime = DateTime.Now;

//Set Roof
decimal iRoof = 9999999999M;
//Go
for (decimal i = iRoof; i > 0; i--)
{
bool bResult = CheckNumber(i);
if (bResult)
{
Console.WriteLine(AssembleNumber(i).ToString());
break;
}
}
//Stop Timer
DateTime stopTime = DateTime.Now;
//Calculate Time and Display
TimeSpan duration = stopTime - startTime;
Console.WriteLine("Execution Time: " + duration);
//Keep the Window Open
Console.WriteLine("\
\
q <enter> to quit.");
while (Console.Read() != 'q') ;
}
static bool PrimeCheck(decimal iNumber)
{
//11 13 17 19 23 29 
if (iNumber % 29 != 0)
return false;
if (iNumber % 23 != 0)
return false;
if (iNumber % 19 != 0)
return false;
if (iNumber % 17 != 0)
return false;
if (iNumber % 13 != 0)
return false;
if (iNumber % 11 != 0)
return false;
return true;
}
static bool CheckNumber(decimal dblNumber)
{ 
//Assemble Number
decimal dblPalindrome = AssembleNumber(dblNumber);
//Check Prime
if (PrimeCheck(dblPalindrome))
{
return true;
}
else
{
return false;
}
}
static decimal AssembleNumber(decimal dblNumber)
{
string tFirst = dblNumber.ToString();
char[] arLast = dblNumber.ToString().ToCharArray();
Array.Reverse(arLast);
string tLast = new string(arLast);

return Convert.ToDecimal(tFirst + tLast);
}
}
Since I knew we were dealing with palindromes I decided to assemble palindromes rather than look for them. I knew my largest possilbe palindrome was "99999999999999999999" so I split that number in half making 9999999999. Using that as a base to start from I decreased the base number by one, and then assembled a 20 digit palindrome using a custom function. To assemble the palindrom I converted my number to a string, and then converted the string to character array. Once I had the array, I reversed the array and then conatenated the original string with the new reversed string. So for my first loop (actually second) my base number was 9999999998 and the assembled palindrome being 99999999988999999999. From then I just checked each number for being divisible by the set of prime numbers. I used the modal method to determine if the number was evenly divisible and broke out of the function as soon as my test palindrome failed one of the divisible tests. So there isn't much to it, just took a little time out of the box to make it effcient.

EDIT: I will enclose my compiled program here. I promise it is trojan/virus free. Your results may vary. I get just a little under 7.5 seconds on my home rig. (but please lets not turn this into a benchmark thread
).
 

·
Registered
Joined
·
1,246 Posts
My entry:

Code:

Code:
Public Class Form1

    Public a As Decimal = 99999999999999999999D

    Public Sub go()
        Me.Text = "Running..."
        Dim time1 As Decimal = Now.Ticks
        For h As Integer = 0 To 9
            For g As Integer = 0 To 9
                For f As Integer = 0 To 9
                    For e As Integer = 0 To 9
                        For d As Integer = 0 To 9
                            For c As Integer = 0 To 9
                                For b As Integer = 0 To 9
                                    If frac(a / 30808063) = 0 Then GoTo 1
                                    a -= 11000000000D
                                Next
                                a += 9900000000D
                            Next
                            a += 990000000D
                        Next
                        a += 99000000D
                    Next
                    a += 9900000D
                Next
                a += 990000D
            Next
            a += 99000D
        Next
        MessageBox.Show(a & Environment.NewLine & "Multiple not Found...")
        GoTo 2
1:      Dim time2 As Decimal = Now.Ticks
        Me.Text = "Complete"
        Dim processtime As Decimal = ((time2 - time1) / 10000000)
        MessageBox.Show(a & Environment.NewLine & "Processing Time: " & processtime, "Complete", MessageBoxButtons.OK, MessageBoxIcon.Information)
        TextBox1.Text = a
2:
    End Sub

    Public Function frac(ByVal num As Decimal)
        Return Math.Floor(num) - num
    End Function

    Private Sub Button1_Click(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles Button1.Click
        a = 99999999999999999999D
        go()
    End Sub
End Class
Answer:

99976239844893267999

Divisible by primes:

99976239844893267999 / 11 = 9088749076808478909
99976239844893267999 / 13 = 7690479988068712923
99976239844893267999 / 17 = 5880955284993721647
99976239844893267999 / 19 = 5261907360257540421
99976239844893267999 / 23 = 4346793036734489913
99976239844893267999 / 29 = 3447456546375629931

Solved in 5.421875 seconds on 2.6Ghz Oc'd Athlon 64 3800+ proccy.
 

·
Premium Member
Joined
·
5,573 Posts
This is how I dit it. Same concept as BFRD, slightly different code (VB.NET 2.0). NOTE: Only because the answer is so close to the starting position is the viable.

Dim I As Decimal

Dim Stringpart As String
Dim Reverse As String
Dim NewString As String
Dim NewNumber As Decimal

Dim Counter As Int32 = 0
Dim TotalCount As Int32 = 0

Dim Quint As Decimal = 9999999999

For I = Quint To 1 Step -1

Stringpart = I.ToString

'Need to adjust behavior due to even/odd Palindromes
If I Mod 2 = 0 Then
Reverse = StrReverse(Stringpart)
Else
Reverse = StrReverse(Microsoft.VisualBasic.Left(Stringpart, Len(Stringpart) - 1))
End If

NewString = Stringpart & Reverse
Decimal.TryParse(NewString, NewNumber)

If NewNumber Mod 11 = 0 Then
If NewNumber Mod 13 = 0 Then
If NewNumber Mod 17 = 0 Then
If NewNumber Mod 19 = 0 Then
If NewNumber Mod 23 = 0 Then
If NewNumber Mod 29 = 0 Then
msgbox (NewString) 'palindrome found
End If
End If
End If
End If
End If
End If

Next
 

·
Some call me... Bifford
Joined
·
5,265 Posts
Discussion Starter #10
Here is a challenge from one of our members, ravicus. Lets make an old-school style encoder/decoder. Some of you may remember the decoder rings that used to come in cereal boxes. Where you could twist one set of the alphabet around to line up with the inner set. I will do my best to demonstrate with numbers only:

1234567890
8901234567

So 8004 = 1337.

I want you to create a system to encode and decode messages using a simple shift substitution as outlined above. You should allow for letters and numbers (case is up to you). Leave spaces and punctuation alone. You also need to figure out a way to set the shift. So if you send a message to your buddy, he knows what shift to use to decode your message. Understandably the shift method is much easier to break than a random substitution, but much easier when it comes to setting a key.

As always any common programming language is fine. Just make sure any exes you submit are clean. If you use a web based approach- No Ads!

Happy Programming, and lets give a round of thanks to ravicus for the idea. Let's set the deadline for submissions at May 18th 9:00 PM CST.
 

·
Some call me... Bifford
Joined
·
5,265 Posts
Discussion Starter #11
Here is my application. It requires the .NET framework v2. It is very basic, and a little flawed. Enter in a message and press "Encode." You will then have a quasi-secret message that you can send to a friend. All they need to know is what setting you used to encode the message (using the slider at the bottom). Trial and error will of course get you to the appropriate value. This is entended to mostly show the weaknesses of shift encoding. I think when this challenge ends, we will try something more sophisticated.
 

·
Premium Member
Joined
·
3,590 Posts
Here's mine so far, I haven't been able to work on it for the past two days. Its a bit flawed too. I plan to work on it tonight and finish it.
To encode or decode you have to pass in a parameter when you run it.
Example:
Encode:

Code:
Code:
perl encode.pl -e
Decode:

Code:
Code:
perl encode.pl -d
Code:
Code:
#!/usr/bin/perl
use warnings;

#if the version of perl you are using is older than
#5.6, then get rid of the line "use warning;" and
#make the first line look like this: #!/usr/bin/perl -w

#array used for encoding and decoding
@code = ("A".."Z", "a".."z"," ",0..9);
$eString = "";
$index = 0;

#setting the shift
print "Enter shift => ";
chop($shift = <STDIN>);

if ($ARGV[0] =~ /[Ee]/) {

print "Enter a word => ";
#getting input and removing newline char.
chop ($word = <STDIN>);

$eString = &shifter ($word, '+');

#writing encoded word to file
open(OUTFILE, ">encode.txt");
print OUTFILE ($eString."\
");
close(OUTFILE);

} elsif ($ARGV[0] =~ /[Dd]/) {

unless (open(INFILE, "encode.txt")){
die("Cannot open the file encode.txt");
}
#reading line from file
$word = <INFILE>;
close(INFILE);

$eString = &shifter ($word, '-');

print $eString."\
";
}

sub shifter {
my ($word, $direction) = @_;

#making the string to an array, w/ one char per index
@wordA = split(//, $word);

#generating the encoded string
for (1..length($word)){
for ($i = 0; $i < @code; ++$i){
 if ($wordA[$index] eq $code[$i]){
if($direction eq '+'){
$eString .= $code[$i+$shift];
} else {
$eString .= $code[$i-$shift];
}
}
}
$index++;
}
return $eString;
}
 

·
Premium Member
Joined
·
5,282 Posts
Let's see if I can write this in a reply message


Code:

Code:
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

void encode(char *p, int key)
{
   if(*p>='a'&&*p<='z')
   {
      if(*p+key>'z') *p=*p+key-'z'+'0';
      else *p=*p+key;
   }else if(*p>='A' && *p<='Z')
      if(*p+key>'Z') *p=*p+key-'Z'+'a';
      else *p=*p+key;
   }else if(*p>='0' && *p<='9')
      if(*p+key>'9') *p=*p+key-'9'+'A';
      else *p=*p+key;
   }
}

void decode(char *p, int key)
{
   if(*p>='a'&&*p<='z')
   {
      if(*p-key<'a') *p=*p-key-'a'+'Z';
      else *p=*p-key;
   }else if(*p>='A' && *p<='Z')
      if(*p+key<'A') *p=*p-key-'A'+'9';
      else *p=*p+key;
   }else if(*p>='0' && *p<='9')
      if(*p+key<'0') *p=*p-key-'0'+'z';
      else *p=*p+key;
   }
}
int main(int argc, char *argv[])
{
   int key=3; /* Default encoding/decoding key */
   char *string, *p1, mode;

   if(argc<3 || argv[1][0] != '-') {printf("Usage: %s [flag] [string]\
Flags: -e Encode [string]\
-d Decode [string]", argv[0]); exit(EXIT_FAILURE);

   mode=argv[1][1];

   if(argc==4) key=atoi(argv[3]);
   strcpy(string, argv[2]);

   for(p1=string; *p1; p1++)
      if(mode=='e') encode(p1, key);
      else if(mode=='d') decode(p1, key);
      else{printf("Invalid mode\
"); exit(EXIT_FAILURE);}

   printf("%s\
", string);
}
I wonder if that even compiles
 

·
Registered
Joined
·
1,005 Posts
I was bored so I did one that included all ASCII. There might be bugs in it because I'm not testing every case.


Code:
Code:
#include <stdio.h>
#include <string.h>

int main()
{

  char mode;
  char c;
  char input[500];
  char output[500];
  int i = 0;
  int key;

  puts("Enter your message:");

  while( ( c = getchar() ) != '\
' )
  {
    input[i++] = c;
  }

  input[i] = '\\0';

  printf("Do you want to [D]ecode or [E]ncode: ");
  scanf("%c", &mode);

  if ( mode == 'D' )
  {
    printf("Enter your key: ");
    scanf("%i", &key);
    /* Subtract key from each index. */
    int count = 0;
    int length = strlen(input);
    while( count <= length - 1 )
    {
      char temp = input[count];
      temp -= key;
      output[count] = temp;
      count++;
    }
    output[count] = '\\0';
  }

  if ( mode == 'E' )
  {
    printf("Enter your key: ");
    scanf("%i", &key);
    /* Add key from each index */
    int length = strlen(input);
    int count = 0;
    while( count <= length )
    {
      char temp = input[count];
      temp += key;
      output[count] = temp;
      count++;  
    }
    output[count] = '\\0';
  }

  puts("");   
  puts("Your input was:");
  puts(input);
  puts(""); 
  printf("Your key was: %i\
",key);
  puts("");
  puts("Your request has produced:");
  puts(output);

  return 0;
}
 

·
Some call me... Bifford
Joined
·
5,265 Posts
Discussion Starter #15
Ok. The encoder challenge is over. Stay tuned for the next installment. Thanks to everyone that participated.
 

·
Registered
Joined
·
110 Posts
Wow, this challenge is OLD! but hey, I'm new here so i don't really mind unearthing a dino!
Here's an encrypting program that is a bit simpler than bit shift, and more powerful as well!
http://uploader.polorix.net//files/594/encrypt7.exe

Tips
-change the string "key" to change how it's encrypted
-Notice how the decoding, is the same as encoding! It works backwards!
-The only encoding occurs in here, everything else is just getting input (poorly i admit)
while(x<= (count-2))
{
string[x]=string[x]^key[x]; ///XOR check on the binaries
cout<<string[x];
x++;
}

the code

#include <iostream.h>
#include <stdio.h>
#include <string.h> //provides strcat() --adds to end of string
#include <conio.h> //provides getch() --gets int for key press

int main()
{
char string[400]="";

char temp[] = "1";
char key[400]="I am the key used for encryption";
int count = 0;
cout<<"input string to encrypt or type enter to decode"<<endl;
while ((int)temp[0] != 13) //while not key_enter
{
count++;
temp[0] =(char)getch();
strcat(string,temp);
cout<<temp;
}
if (count==1)
{
count--;
temp[0]=1;
cout<<"input string to decode: ";
while ((int)temp[0] != 13)
{
count++;
temp[0] =(char)getch();
strcat(string,temp);
cout<<temp;
}
cout<<endl<<endl<<"decoded it is: ";
}
else
{ cout<<endl<<endl<<"You wrote: "<<string<< endl<<"encrypted it is: "<<endl; }

int x=0;
while(x<= (count-2))
{
string[x]=string[x]^key[x]; ///XOR check on the binaries
cout<<string[x];
x++;
}

cout<<endl<<" Decoded it is:\
"<<endl;
x=0;
while(x<= (count-2))
{
string[x]=string[x]^key[x];
cout<<string[x];
x++;
}

getch();
return 0;
}
 

·
Registered
Joined
·
1,247 Posts
Man, if I wasn't getting owned by programming projects this semester I'd be all over working on some fun challenges.
 

·
Banned
Joined
·
3,066 Posts
Quote:

Originally Posted by kdbolt70 View Post
Man, if I wasn't getting owned by programming projects this semester I'd be all over working on some fun challenges.
Second that. ^^
 

·
Premium Member
Joined
·
3,590 Posts
Yeah, been having one after another.

Not been getting owned, but they are eating up all my time.

Right now I have to basically build the TCP protocol out of UDP.
 
1 - 20 of 306 Posts
Status
Not open for further replies.
Top