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) - Page 20  

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 #191 of 306
Ran a 50k iteration with Midpipps's code modified for file output. According to the logs it took just under 8 hours and the output file was 3.5 gigs... Then I realized I never closed the outputstream and I lost the last few iterations. Fixed the issue and reran it before I left for work. We'll see the results when I get home.
post #192 of 306
Quote:
Originally Posted by xtascox View Post
Ran a 50k iteration with Midpipps's code modified for file output. According to the logs it took just under 8 hours and the output file was 3.5 gigs... Then I realized I never closed the outputstream and I lost the last few iterations. Fixed the issue and reran it before I left for work. We'll see the results when I get home.
Sad to say I modified it again and during my initial test I was getting a 70% average increase in speed for 1000 primes. Good to read some more information on prime numbers have another possibility to speed it up but it is much more math intensive and I am not sure yet whether it will actually speed up as much

Code:
import java.io.FileWriter;
import java.io.IOException;
import java.io.PrintWriter;
import java.math.BigInteger;
import java.util.Vector;

public class PerrinNumber {

private static Vector<BigInteger> perrin = new Vector<BigInteger>();
private static Vector<BigInteger> oldPrimes = new Vector<BigInteger>();
private static BigInteger prime = BigInteger.valueOf(2);
private static BigInteger currentPerrinPosition = BigInteger.valueOf(3);
private static final int tests = 1000;
private static PrintWriter out = null;

public static void main(String[] args) {
try {
out = new PrintWriter(new FileWriter("output.txt"));
} catch (IOException e) {
e.printStackTrace();
}
long before = System.currentTimeMillis();
perrin.add(BigInteger.valueOf(-1));
perrin.add(BigInteger.valueOf(3));
perrin.add(BigInteger.valueOf(0));
perrin.add(BigInteger.valueOf(2));
printMessage(0);
oldPrimes.add(BigInteger.valueOf(2));
prime = prime.subtract(BigInteger.valueOf(1));
for (int i = 1; i < tests; i ++)
{
//makePrime();
makePrime2();
nextPerrin(prime);
printMessage(i);
//System.out.println("iteration = " + i 
//+ " makePrime = " + prime.toString() 
//+ "  makePrime2 = " + oldPrimes.get(oldPrimes.size() - 1));

}
long after = System.currentTimeMillis();
out.close();
System.out.println(((double)after-(double)before)/(double)1000);
}

private static void makePrime()
{
boolean primeFound = false;
while (!primeFound)
{
prime = prime.add(BigInteger.valueOf(2));
for (BigInteger a = BigInteger.valueOf(2); a.compareTo(prime) <= 0; a = a.add(BigInteger.valueOf(1)))
{
if (a.compareTo(prime) == 0)
primeFound = true;
if (prime.mod(a) == BigInteger.valueOf(0))
break;
}

}
}

private static void makePrime2()
{
boolean primeFound = false;
while (!primeFound)
{
prime = prime.add(BigInteger.valueOf(2));
for (int a = 0; a < oldPrimes.size(); a ++)
{
if (prime.mod(oldPrimes.get(a)) == BigInteger.valueOf(0))
break;
if ((oldPrimes.size() - 1) == a)
{
primeFound = true;
oldPrimes.add(prime);
}
}
}
}

private static void nextPerrin(BigInteger B)
{
while(currentPerrinPosition.compareTo(prime) <= 0)
{
perrin.add(perrin.get(2).add(perrin.get(1)));
perrin.remove(0);
currentPerrinPosition = currentPerrinPosition.add(BigInteger.valueOf(1));
}
}

private static void printMessage(int i)
{
System.out.println("P(" + (i+1) + ") = " + prime.toString()
+ "; A(P(" + (i+1) + ")) = " + perrin.get(3).toString()
+ "; " + perrin.get(3).toString() + " modulus " + prime.toString()
+ " => " + (perrin.get(3).mod(prime)));
/*out.println("P(" + (i+1) + ") = " + prime.toString()
+ "; A(P(" + (i+1) + ")) = " + perrin.get(3).toString()
+ "; " + perrin.get(3).toString() + " modulus " + prime.toString()
+ " => " + (perrin.get(3).mod(prime)));*/
}
}
big difference is I actually added the prime array back in but now cut out the checks for mod with nonprime numbers.
    
CPUMotherboardGraphicsRAM
Q6600 DG33TL XFX 6950 2GB 4gigs Corsair XMS2 DDR2 
Hard DriveOptical DriveOSMonitor
1.5TB seagate 2X640GB Samsung DVDRW Windows Vista & Debian Linux Samsung 19" + Acer 24" Wide 
KeyboardPowerCaseMouse
Microsoft SideWinder X6 Antec 750 TruePower Raidmax Smilodon COOLER MASTER Sentinel 
Mouse Pad
RocketFish 
  hide details  
    
CPUMotherboardGraphicsRAM
Q6600 DG33TL XFX 6950 2GB 4gigs Corsair XMS2 DDR2 
Hard DriveOptical DriveOSMonitor
1.5TB seagate 2X640GB Samsung DVDRW Windows Vista & Debian Linux Samsung 19" + Acer 24" Wide 
KeyboardPowerCaseMouse
Microsoft SideWinder X6 Antec 750 TruePower Raidmax Smilodon COOLER MASTER Sentinel 
Mouse Pad
RocketFish 
  hide details  
post #193 of 306
I think one of the features I'm going to add today is splitting the output into multiple files. It may add a little to the processing time but should give us a clearer and more manageable output. Imagine if we found a case where the property fails I'll include some log info in the files, such as processing time for that batch.
post #194 of 306
New challenge today?
post #195 of 306
Quote:
Originally Posted by xtascox View Post
New challenge today?
Wednesday is new challenge day
    
CPUMotherboardGraphicsRAM
Q6600 DG33TL XFX 6950 2GB 4gigs Corsair XMS2 DDR2 
Hard DriveOptical DriveOSMonitor
1.5TB seagate 2X640GB Samsung DVDRW Windows Vista & Debian Linux Samsung 19" + Acer 24" Wide 
KeyboardPowerCaseMouse
Microsoft SideWinder X6 Antec 750 TruePower Raidmax Smilodon COOLER MASTER Sentinel 
Mouse Pad
RocketFish 
  hide details  
    
CPUMotherboardGraphicsRAM
Q6600 DG33TL XFX 6950 2GB 4gigs Corsair XMS2 DDR2 
Hard DriveOptical DriveOSMonitor
1.5TB seagate 2X640GB Samsung DVDRW Windows Vista & Debian Linux Samsung 19" + Acer 24" Wide 
KeyboardPowerCaseMouse
Microsoft SideWinder X6 Antec 750 TruePower Raidmax Smilodon COOLER MASTER Sentinel 
Mouse Pad
RocketFish 
  hide details  
post #196 of 306
Quote:
Originally Posted by Midpipps View Post
Wednesday is new challenge day
And to think I actually thought it was Wednesday
post #197 of 306
Went with a little simpler one today will come back with a harder one again next week. This is the last one I have from MICS but I have more from ACM competitions. They are a little harder.

The MICS ones are designed to be given in sets of 5 or 6 and you have 3 hours or so to solve as many as you can in the fastest time you can so they are a little easier.

Quote:
The Maximum Sum of a Contiguous Subsequence

This problem is simple to state. It may or may not be simple to solve.
Given a sequence of integers, find the maximum sum of a contiguous subsequence of zero or more of those numbers.
For example, suppose the data is: 0, -1, 2, -1, 3, -1 0. The sum of the maximum subsequence is 4. The contiguous subsequence consists of 2, -1, 3.

Input:
Each line thereafter consists of a line containing the sequence.

Output:
For each of the lines, the program should produce a single number giving the sum of the maximum subsequence.


Sample Input:
1 2 3
0 -1 2 -1 3 -1 0
-1 0

Corresponding output:
6
4
0

One Note on this: Since 0 is a viable answer if you have something like -1 -1 -4 -2 your answer would be 0 because the largest list would be not to pick one and just stay with the 0.

Edited by Midpipps - 1/12/11 at 9:04am
    
CPUMotherboardGraphicsRAM
Q6600 DG33TL XFX 6950 2GB 4gigs Corsair XMS2 DDR2 
Hard DriveOptical DriveOSMonitor
1.5TB seagate 2X640GB Samsung DVDRW Windows Vista & Debian Linux Samsung 19" + Acer 24" Wide 
KeyboardPowerCaseMouse
Microsoft SideWinder X6 Antec 750 TruePower Raidmax Smilodon COOLER MASTER Sentinel 
Mouse Pad
RocketFish 
  hide details  
    
CPUMotherboardGraphicsRAM
Q6600 DG33TL XFX 6950 2GB 4gigs Corsair XMS2 DDR2 
Hard DriveOptical DriveOSMonitor
1.5TB seagate 2X640GB Samsung DVDRW Windows Vista & Debian Linux Samsung 19" + Acer 24" Wide 
KeyboardPowerCaseMouse
Microsoft SideWinder X6 Antec 750 TruePower Raidmax Smilodon COOLER MASTER Sentinel 
Mouse Pad
RocketFish 
  hide details  
post #198 of 306
The maximum sub sequence for the third sample sequence should be 1, not 0
It goes to eleven
(13 items)
 
  
CPUMotherboardGraphicsRAM
E6300 DS3 EVGA 8600GTS 2GB XMS2 DDR2-800 
Hard DriveOSMonitorKeyboard
1.294 TB Arch Linux/XP Samsung 226bw Eclipse II 
PowerCaseMouse
Corsair 520HX Lian-Li v1000B Plus G7 
  hide details  
It goes to eleven
(13 items)
 
  
CPUMotherboardGraphicsRAM
E6300 DS3 EVGA 8600GTS 2GB XMS2 DDR2-800 
Hard DriveOSMonitorKeyboard
1.294 TB Arch Linux/XP Samsung 226bw Eclipse II 
PowerCaseMouse
Corsair 520HX Lian-Li v1000B Plus G7 
  hide details  
post #199 of 306
Quote:
Originally Posted by rabidgnome229 View Post
The maximum sub sequence for the third sample sequence should be 1, not 0
You are right sorry I copied another line and never payed attention. Thank you and it is fixed.
    
CPUMotherboardGraphicsRAM
Q6600 DG33TL XFX 6950 2GB 4gigs Corsair XMS2 DDR2 
Hard DriveOptical DriveOSMonitor
1.5TB seagate 2X640GB Samsung DVDRW Windows Vista & Debian Linux Samsung 19" + Acer 24" Wide 
KeyboardPowerCaseMouse
Microsoft SideWinder X6 Antec 750 TruePower Raidmax Smilodon COOLER MASTER Sentinel 
Mouse Pad
RocketFish 
  hide details  
    
CPUMotherboardGraphicsRAM
Q6600 DG33TL XFX 6950 2GB 4gigs Corsair XMS2 DDR2 
Hard DriveOptical DriveOSMonitor
1.5TB seagate 2X640GB Samsung DVDRW Windows Vista & Debian Linux Samsung 19" + Acer 24" Wide 
KeyboardPowerCaseMouse
Microsoft SideWinder X6 Antec 750 TruePower Raidmax Smilodon COOLER MASTER Sentinel 
Mouse Pad
RocketFish 
  hide details  
post #200 of 306
Sweet I'm going to do this on a 10,000,000 index sequence of randomly generated numbers
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)