Overclock.net › Forums › Software, Programming and Coding › Coding and Programming › Programming Challenge (Out-of-Date)
New Posts  All Forums:Forum Nav:

Programming Challenge (Out-of-Date)  

Poll Results: Are you interested in participating in and/or helping organise and post these programming challenges?

 
  • 100% (2)
    I want to participate.
  • 0% (0)
    I want to contribute by helping posting and organise these challenges.
  • 0% (0)
    I'll only take part if other people are willing to participate.
  • 0% (0)
    I can help and participate - I love programming!
  • 0% (0)
    I do not wish to participate or help.
2 Total Votes  
post #1 of 306
Thread Starter 

{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

Main Rig
(15 items)
 
  
Main Rig
(15 items)
 
  
post #2 of 306
Thread Starter 
Times up, Xaimus is the only one that got an entry in.

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 == '-';
}
Main Rig
(15 items)
 
  
Main Rig
(15 items)
 
  
post #3 of 306
Thread Starter 
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.
Main Rig
(15 items)
 
  
Main Rig
(15 items)
 
  
post #4 of 306
10 minutes of coding
5 minutes of refreshing PHP knowledge
5 minutes for debugging and formatting

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.
My System
(13 items)
 
  
CPUMotherboardOSMonitor
Barton 3000+ Socket A EPoX 8RDA6+ Pro Win XP Pro SP2 2x LCD 
KeyboardPowerCaseMouse
Regular Ultra 500 Watt Antec Lanboy Razer Diamondback 
  hide details  
My System
(13 items)
 
  
CPUMotherboardOSMonitor
Barton 3000+ Socket A EPoX 8RDA6+ Pro Win XP Pro SP2 2x LCD 
KeyboardPowerCaseMouse
Regular Ultra 500 Watt Antec Lanboy Razer Diamondback 
  hide details  
post #5 of 306
Thread Starter 
Quote:
Originally Posted by FaKk2
10 minutes of coding
5 minutes of refreshing PHP knowledge
5 minutes for debugging and formatting

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.
Main Rig
(15 items)
 
  
Main Rig
(15 items)
 
  
post #6 of 306
Thread Starter 
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)
Main Rig
(15 items)
 
  
Main Rig
(15 items)
 
  
post #7 of 306
Thread Starter 
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:
 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 ).
Main Rig
(15 items)
 
  
Main Rig
(15 items)
 
  
post #8 of 306
My entry:

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.
Bob
(13 items)
 
  
CPUMotherboardGraphicsRAM
AMD Athlon 64 3800+ ASUS A8N- SLI Premium XFX GeForce 7800GT Extreme Edition 2GB (2X1GB) Corsair XMS Pro LED TwinX DDR400 
Hard DriveOptical DriveOSMonitor
2x200GB Barracuda SATA RAID0 + 250Gb ATA SONY CDR-RW Ultra speed Windows Vista Home Premium x64 Hanns G 19" widescreen HW191D 
PowerCaseMouse
Antec TruePower 550W Thermaltake Armour Logitech LX5 
  hide details  
Bob
(13 items)
 
  
CPUMotherboardGraphicsRAM
AMD Athlon 64 3800+ ASUS A8N- SLI Premium XFX GeForce 7800GT Extreme Edition 2GB (2X1GB) Corsair XMS Pro LED TwinX DDR400 
Hard DriveOptical DriveOSMonitor
2x200GB Barracuda SATA RAID0 + 250Gb ATA SONY CDR-RW Ultra speed Windows Vista Home Premium x64 Hanns G 19" widescreen HW191D 
PowerCaseMouse
Antec TruePower 550W Thermaltake Armour Logitech LX5 
  hide details  
post #9 of 306
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
TITAN-6
(16 items)
 
  
CPUMotherboardGraphicsRAM
i7 2600K @ 4GHZ ASRock Extreme 3 Gen 3 Gigabyte Nvidia GTX 570 8GB G.skill Sniper DDR3 1866 
Hard DriveOptical DriveCoolingOS
Crucial M4 CT128M4SSD2 2.5" 128GB SATA III MATSHITA BD-CMB UJ160 Blu Ray DVD writer Cooler Master Hyper 212+ Windows 7 x64 
MonitorMonitorKeyboardPower
Sceptre 24" LCD BENQ 3D 24" LCD Logitech G510 Corsair 750W HX professional single rail 
CaseMouseMouse PadAudio
CM Storm Sniper Razer Naga left-handed version None Onboard 
  hide details  
TITAN-6
(16 items)
 
  
CPUMotherboardGraphicsRAM
i7 2600K @ 4GHZ ASRock Extreme 3 Gen 3 Gigabyte Nvidia GTX 570 8GB G.skill Sniper DDR3 1866 
Hard DriveOptical DriveCoolingOS
Crucial M4 CT128M4SSD2 2.5" 128GB SATA III MATSHITA BD-CMB UJ160 Blu Ray DVD writer Cooler Master Hyper 212+ Windows 7 x64 
MonitorMonitorKeyboardPower
Sceptre 24" LCD BENQ 3D 24" LCD Logitech G510 Corsair 750W HX professional single rail 
CaseMouseMouse PadAudio
CM Storm Sniper Razer Naga left-handed version None Onboard 
  hide details  
post #10 of 306
Thread Starter 
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.
Main Rig
(15 items)
 
  
Main Rig
(15 items)
 
  
New Posts  All Forums:Forum Nav:
  Return Home
  Back to Forum: Coding and Programming
This thread is locked  
Overclock.net › Forums › Software, Programming and Coding › Coding and Programming › Programming Challenge (Out-of-Date)