Programming Game #1

**Artificial** · 12 Jan. 2010 07:54am

Bored, time for a small programming game. Here it is, plain and simple. I tell you a function you have to write (and what must be done in that function), and whoever can code it in the smallest amount of characters wins. It will teach you to optimize your code, although you might have to use some abhorred programming techniques along the way.

You can use any language.

Not limited to one entry per person. If someone beats you, go back to your code and try and make it smaller. Once nobody can beat it anymore, game over.

Prize: 50k LG to winner.

Function you have to make
Return a list of all prime numbers between a lower limit and upper limit.

Function must:
- be named Primes.
- not return 1 as a prime number (i.e. if 1 is entered as lower limit, 2 will be the first prime).
- return null result if upper limit lower than lower limit.

Rules:
- spaces not included in total character length (new lines don't count as well)
- don't just use someone elses code and optimize it. Use your own code.

My entry (coded in PHP)

PHP Code:

 function Primes($l, $u)
{
    if($l <= 1) $l = 2;
    if($u <= $l) return;

    for($x = $l; $x <= $u; $x++)
        $z[] = $x;

    for($i = 0; $c*$c < $u; $i++)
    {
        $c = $z[$i];
        foreach($z as $d => $v)
            if($v % $c == 0 && $v != $c)
                unset($z[$d]);

        $z = array_values($z);
    }

    return $z;
}

Char length: 201.

Code:

print_r(Primes(0,30)); returns:

Array
(
    [0] => 2
    [1] => 3
    [2] => 5
    [3] => 7
    [4] => 11
    [5] => 13
    [6] => 17
    [7] => 19
    [8] => 23
    [9] => 29
)

**Confide** · 12 Jan. 2010 08:02am

PHP Code:

   function Primes($l, $u)

{

    if($l <= 1) $l = 2;

    if($u <= $l) return;

 
    for($x = $l; $x <= $u; $x++)

        $z[] = $x;

 
    for($i = 0; $c*$c < $u; $i++)

    {

        $c = $z[$i];

        foreach($z as $d => $v)

            if($v % $c == 0 && $v != $c)

                unset($z[$d]);

 
        $z = array_value($z);

    }

 
    return $z;

}

200 chars.

**Riddle** · 12 Jan. 2010 06:35pm

Mine:

Code:

def Primes(l,u,p):
    if l<2:
        l=2
    if u<2:
        return
    u+=1
    for i in range(l,u):
        f=True
        for x in range(l,u):
            if i%x==0 and i!=x and i>x:
                f=False
        if f:
            p.append(i)
    return p

Output:

Code:

>>> p = Primes(0,30,[])
>>> for i in p:
	print(i)

	
2
3
5
7
11
13
17
19
23
29
>>>

Characters (without \n and spaces): 133

**Smithno13** · 12 Jan. 2010 09:46pm

No precoded functions, right? Java (Lame, I know, but all I remember right now xD) has a prime checking function that I could just run numbers through.

**MattSmith** · 13 Jan. 2010 01:14am

;D Woo. Something i can participate in >.< -Makin mine in C, give me 15 mins or soo-

EDIT:: =.= getting caught up in something, ill have to do it later.

**ʝдɮ** · 13 Jan. 2010 01:21am

What's the time limit?

**Artificial** · 13 Jan. 2010 01:58am

Originally Posted by Smithno13

No precoded functions, right? Java (Lame, I know, but all I remember right now xD) has a prime checking function that I could just run numbers through.

I know I said all languages, but that's too easy for sure. Riddle is in the lead, time to go change mine up.

**Smithno13** · 13 Jan. 2010 02:19am

Yea, I figured not. I really need to learn more coding languages but I have never really had need or inspiration to do so.

**ʝдɮ** · 13 Jan. 2010 02:31am

Originally Posted by Riddle

Mine:

Code:

def Primes(l,u,p):
    if l<2:
        l=2
    if u<2:
        return
    u+=1
    for i in range(l,u):
        f=True
        for x in range(l,u):
            if i%x==0 and i!=x and i>x:
                f=False
        if f:
            p.append(i)
    return p

Output:

Code:

>>> p = Primes(0,30,[])
>>> for i in p:
	print(i)

	
2
3
5
7
11
13
17
19
23
29
>>>

Characters (without \n and spaces): 133

Pardon my nubness, what language is that?

**Artificial** · 13 Jan. 2010 02:35am

It's python.

I only managed to shorten mine down by an additional 30 characters <.< I'll have another go later, and if unable to may swap language. Python is such a simple language, not sure I'll be able to.

PHP Code:

 function Primes($l, $u)
{
    if($l < 2) $l = 2;
    if($u < 2) return;

    $z = range($l,$u);
    foreach($z as $i => $c)
        foreach($z as $d => $v)
            if($v % $c == 0 && $v != $c) 
                unset($z[$d]);
            else $a[$i][] = $z[$d];

    return $a[$i];
}

13 Jan. 2010 03:39am

Program:
MEGAUPLOAD - Primes.rar

Source:

Code:

Imports System.ComponentModel

Public Class Primes
    Private backgroundCalculator As System.ComponentModel.BackgroundWorker

    Public Sub New()

        InitializeComponent()

        backgroundCalculator = New BackgroundWorker()
        backgroundCalculator.WorkerReportsProgress = True
        backgroundCalculator.WorkerSupportsCancellation = True

        AddHandler backgroundCalculator.DoWork, New DoWorkEventHandler(AddressOf backgroundCalculator_DoWork)
        AddHandler backgroundCalculator.ProgressChanged, New ProgressChangedEventHandler(AddressOf backgroundCalculator_ProgressChanged)
        AddHandler backgroundCalculator.RunWorkerCompleted, New RunWorkerCompletedEventHandler(AddressOf backgroundCalculator_RunWorkerCompleted)

        updateStatus(String.Empty)

    End Sub

#Region "Synchronous calculation"

    Private Function getNextPrimeSync(ByVal start As Integer) As Integer

        Dim percentComplete As Integer = 0

        start += 1
        While isPrime(start) = False

            start += 1

            percentComplete += 1

            updateProgress(percentComplete Mod 100)
        End While
        Return start
    End Function

    Private Sub nextPrimeButton_Click(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles NextPrime.Click
        enableCalcButtons(False)
        updateStatus("Calculating...")

        Dim start As Integer
        Integer.TryParse(TextPrime.Text, start)

        If start = 0 Then
            reportError("The Prime number must be a valid integer")
        Else
            Try
                Dim prime As Integer = getNextPrimeSync(start)
                reportPrime(prime)
            Catch err As ApplicationException
                reportError(err)
            End Try
            CalcProgress.Value = 0
        End If


        enableCalcButtons(True)

    End Sub
#End Region

#Region "Asynchronous calculation"

    Private Function getNextPrimeAsync(ByVal start As Integer, ByVal worker As BackgroundWorker, ByVal e As DoWorkEventArgs) As Integer

        Dim percentComplete As Integer = 0

        start += 1

        While isPrime(start) = False

            If worker.CancellationPending = True Then
                e.Cancel = True
                Exit While
            Else

                start += 1

                percentComplete += 1

                worker.ReportProgress(percentComplete Mod 100)
            End If
        End While

        Return start
    End Function

    Sub backgroundCalculator_RunWorkerCompleted(ByVal sender As Object, ByVal e As RunWorkerCompletedEventArgs)

        If e.Cancelled Then
            updateStatus("Cancelled.")
        ElseIf e.Error IsNot Nothing Then
            reportError(e.Error)
        Else
            reportPrime(CInt(e.Result))
        End If

        calcProgress.Value = 0
        enableCalcButtons(True)
    End Sub

    Sub backgroundCalculator_ProgressChanged(ByVal sender As Object, ByVal e As ProgressChangedEventArgs)
        updateProgress(e.ProgressPercentage)
    End Sub

    Sub backgroundCalculator_DoWork(ByVal sender As Object, ByVal e As DoWorkEventArgs)
        Dim start As Integer = CInt(e.Argument)
        e.Result = getNextPrimeAsync(start, CType(sender, BackgroundWorker), e)
    End Sub

    Private Sub nextPrimeAsyncButton_Click(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles NextPrime.Click
        enableCalcButtons(False)
        updateStatus("Calculating...")

        Dim start As Integer
        Integer.TryParse(TextPrime.Text, start)

        If start = 0 Then
            reportError("The Prime Number must be a valid integer")
        Else
            backgroundCalculator.RunWorkerAsync(start)
        End If
    End Sub

    Private Sub cancelPrimeButton_Click(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles NextPrime.Click
        If backgroundCalculator.IsBusy Then
            updateStatus("Cancelling...")
            backgroundCalculator.CancelAsync()
        End If
    End Sub
#End Region

#Region "User Feedback"
    Private Sub updateStatus(ByVal status As String)
        CalcStatus.Text = status
    End Sub

    Private Sub updateProgress(ByVal percentComplete As Integer)
        CalcProgress.Value = percentComplete
    End Sub

    Private Sub reportPrime(ByVal prime As Integer)
        TextPrime.Text = prime.ToString()
        updateStatus("Done!")
    End Sub

    Private Sub reportError(ByVal e As Exception)
        updateStatus("Error!")
        MessageBox.Show("The following error occurred: " + ControlChars.CrLf + e.Message, "Error", MessageBoxButtons.OK, MessageBoxIcon.Error)
    End Sub

    Private Sub reportError(ByVal message As String)
        updateStatus("Error!")
        MessageBox.Show("The following error occurred: " + ControlChars.CrLf + message, "Error", MessageBoxButtons.OK, MessageBoxIcon.Error)
    End Sub

    Private Sub enableCalcButtons(ByVal bEnable As Boolean)
        NextPrime.Enabled = True
    End Sub

#End Region

    Private Function isPrime(ByVal candidate As Integer) As Boolean

        Dim retVal As Boolean = True

        For i As Integer = candidate / 2 + 1 To 2 Step -1

            If candidate Mod i = 0 Then
                retVal = False
                Exit For
            End If
        Next

        Return retVal
    End Function
End Class

This should work... The download is to the project files which I saved. So they are virus free, thought it would be easier than having you troubleshoot with my weirdly named tools for hours...

Now to see if it can be shortened... D:

EDIT: Nvm Python will always be shorter than my vb script...

**Riddle** · 13 Jan. 2010 04:59am

Eternal: All you have to include is a function that meets the requirements set up by Alex.

Alex: Python is basically cheating, since the syntax does not require any parenthesis or semicolons, plus, it's a language designed to be short and simple, perfect for stuff like this.

**ʝдɮ** · 13 Jan. 2010 05:08am

He did say any language man.

13 Jan. 2010 11:07pm

Originally Posted by Riddle

Eternal: All you have to include is a function that meets the requirements set up by Alex.

Alex: Python is basically cheating, since the syntax does not require any parenthesis or semicolons, plus, it's a language designed to be short and simple, perfect for stuff like this.

Yeah, I was editing the code last night, out of boredom...

Well Python isn't really cheating, just an excellent choice... "it's a language designed to be short and simple, perfect for stuff like this." and thats why its unbeatable and a good language for him to choose.

I wouldn't be able to compete with python anyway...

**Chad** · 14 Jan. 2010 12:05am

Originally Posted by Eternal Darkness

Yeah, I was editing the code last night, out of boredom...

Well Python isn't really cheating, just an excellent choice... "it's a language designed to be short and simple, perfect for stuff like this." and thats why its unbeatable and a good language for him to choose.

I wouldn't be able to compete with python anyway...

You can if you do certain things. You might not come at all close to winning but at least you would learn how to optimize your code.

**MattSmith** · 14 Jan. 2010 02:24am

Alrighty, since i have to learn some more complicated C and java than what i already know for the robotics team, im going to pawn you guys at this. Give me a few days as im very busy ATM.

**Riddle** · 14 Jan. 2010 02:28am

It only takes you 5-10 minutes to come up with something that meets the requirements. >_>

**MattSmith** · 14 Jan. 2010 02:32am

ATM, i dont have 2mins for something that isnt necessary.

**Artificial** · 17 Jan. 2010 02:17am

Sk8er took too long. Riddle wins, giving 50k LG now.

**Riddle** · 17 Jan. 2010 11:39pm

I'll buy that "Riddle The Slug Rider" rank for 50k LG. XD

18 Jan. 2010 11:12pm

If I'm not mistaken, Riddle's doesn't work. His inner loop goes from lower to upper. That will only work if lower is <= 2, otherwise it won't check to see if the number is divisible by numbers < lower.
e.g. prime numbers between 10 and 20. It will erroneously believe 12 is prime because it's not divisible by 10 or 11.

My submission even though this ended, 'cause I didn't read it until just now:

PHP Code:

 <?php

function find_primes($lower = 2, $upper = 100)
{
    $primes = Array();
    if ($lower < 2 && $upper < 2)
        return $primes;
    $temp = $upper;
    $upper = max(2, $lower, $upper); // "cache"d to prevent recalculating with each loop
    $lower = min(max(2, $lower), max(2, $temp)); // making it longer, but faster
    for ($x = $lower; $x <= $upper; ++$x)
    {
        $prime = true;
        for ($y = 2; $y < $x; ++$y)
        {
            if ($x % $y == 0)
                $prime = false;
        }
        if ($prime)
            array_push($primes, $x);
    }
    return $primes;
}

echo '<pre>';
print_r(find_primes());
print_r(find_primes(1, 30));
print_r(find_primes(30, 10));
echo '</pre>';

?>

I went for speed and functionality over character count. Note default values, the fact that the numbers can be in any order, returns an empty array instead of null, only loops from 2 to $x (instead of all the way till $upper and ignoring values where $upper > $x; compared to checking if "i > x" in Riddle's), and it supports lower values > 2 (unlike Riddle's, if I'm not mistaken).

Do I win 50k?

Since all the previous submissions do not work when lower > 2, they should be disqualified.

Revised to meet the technical requirements in the first post:

PHP Code:

 <?php

function Primes($lower = 2, $upper = 100)
{
    if ($lower < 2 && $upper < 2)
        return null;
    $primes = Array();
    $temp = $upper;
    $upper = max(2, $lower, $upper); // "cache"d to prevent recalculating with each loop
    $lower = min(max(2, $lower), max(2, $temp)); // making it longer, but faster
    for ($x = $lower; $x <= $upper; ++$x)
    {
        $prime = true;
        for ($y = 2; $y < $x; ++$y)
        {
            if ($x % $y == 0)
                $prime = false;
        }
        if ($prime)
            array_push($primes, $x);
    }
    return $primes;
}

echo '<pre>';
print_r(find_primes());
print_r(find_primes(1, 30));
print_r(find_primes(30, 10));
echo '</pre>';

?>

Shortened for character count and awesome shit removed:

PHP Code:

 <?php
function Primes($l,$u){$l=max(2,$l);if($u>$l)return null;$p=Array();for($x=$l;$x<=$u;++$x){$q=1;for($y=2;$y<$x;++$y){if($x%$y==0)$q=0;}if($q)$p[]=$x;}return $p;}
?>

Characters: 161

**Riddle** · 19 Jan. 2010 02:17am

You sir, are completely right.

Fixed:

Code:

def Primes(l,u,p):
    if l<2:
        l=2
    if u<2:
        return
    u+=1
    for i in range(l,u):
        f=True
        for x in range(2,u):
            if i%x==0 and i!=x and i>x:
                f=False
        if f and i>=l:
            p.append(i)
    return p

Added about 7 characters: 140 total

**Artificial** · 19 Jan. 2010 02:56am

Intriguing. The chief has potential. I should throw you some LGG for pointing that out and producing a decent function.

19 Jan. 2010 04:08am

This should decrease the length of yours by a bit, Riddle (and increase loading speeds):

Change:

Code:

for x in range(2,u):
            if i%x==0 and i!=x and i>x:

To:

Code:

for x in range(2,i-1):
            if i%x==0:

Looping simply to i - 1, x will never be equal to i, nor will i exceed x, so we can remove both checks.

I can has the full 50k?

I am the first to actually fulfill the requirements in the original post. :flirt:

Thread: Programming Game #1

LinkBack

Thread Tools

Search Thread

Rate This Thread

Display

Programming Game #1

Vb.Net Version

Posting Permissions