Friday, October 28, 2011

Too Slow - 11849 CD

So I was writing a program today to solve this problem. First I had some issues compiling because my arrays were too big. It seems that if you allocate them within the main function it takes up stack space where as initializing them as global variables takes up heap space. Good to know! The first five times I submitted I got a response of time limit exceeded. I did some minor things the first two times to break out of a loop if I had incremented my counter and if the CD number of Jack's was bigger than Jill's because all CDs were in order. This helped a little bit and then I remembered reading an article on competitive coding tips that suggested using scanf/printf functions instead of cin/cout. This dramatically improved my time, but was still getting rejected for exceeding the limit. I tried a couple other minor tweaks that improved my timing and finally decided a linear search was just too slow to work. Went to a binary search and submitted which gave me a response of ACCEPTED. :)


#include <stdio.h>

int array[1000000];
int array2[1000000];

int binary_search(int a[], int low, int high, int target) {
    while (low <= high) {
        int middle = low + (high - low)/2;
        if (target < a[middle])
            high = middle - 1;
        else if (target > a[middle])
            low = middle + 1;
        else
            return middle;
    }
    return -1;
}

int main()
{
int a = 1, b = 1;

scanf("%d %d", &a, &b);
while(a != 0 && b != 0)
{
int count = 0;
int i = 0;
for(i = 0; i < a; ++i)
{
int temp;
scanf("%d", &temp);
array[i] = temp;
}

for(i = 0; i < b; ++i)
{
int temp;
scanf("%d", &temp);
int found = binary_search(array, 0, a - 1, temp);
if(array[found] == temp)
++count;

}
printf("%d\n", count);
count = 0;
scanf("%d %d", &a, &b);
}
return 0;
}

Friday, October 21, 2011

Big Integers in C#


Problem 13 in Project Euler(www.projecteuler.net) asks the participant to find the first 10 digits of the sum of fifty 100 digit numbers given. Most the trouble in doing this is finding something that can handle arithmetic on such large numbers. I knew that C# had a data type called BigInteger, which should be able to handle pretty much anything you throw at it. Made this one a Windows Form just for the hell of it. After that it was a simple read in the text file full of numbers into a text box, add them up, and then print out the first ten digits.

You can get the Visual Studio project file here. Contains source code and a runnable .exe:
http://www.sendspace.com/file/mic4n0

SPOILER ALERT: Answer is after the jump.

Thursday, October 20, 2011

Triangle Numbers

I use a website called Project Euler (www.projecteuler.net) to find problems to work on. Problem 12 on the website asks you to find the first triangle number with 500 or more divisors. SPOILER ALERT: The answer is at the very bottom of this post. Click on Read More to see it. Here is the code I used to figure it out:


/* Chuck Woodraska
Program Description - projecteuler.net Problem 12
The sequence of triangle numbers is generated by adding the natural numbers.
So the 7th triangle number would be 1 + 2 + 3 + 4 + 5 + 6 + 7 = 28. The first ten terms would be:

1, 3, 6, 10, 15, 21, 28, 36, 45, 55, ...

Let us list the factors of the first seven triangle numbers:

 1: 1
 3: 1,3
 6: 1,2,3,6
10: 1,2,5,10
15: 1,3,5,15
21: 1,3,7,21
28: 1,2,4,7,14,28
We can see that 28 is the first triangle number to have over five divisors.

What is the value of the first triangle number to have over five hundred divisors?
*/

#include <iostream>
#include <math.h>

using namespace std;
int main()
{
// start with the 1st triangle number
int start = 1;

int i = 2; // count for getting the next triangle number (1 + 2 + 3 ...)
int count = 0; // count for how many divisors the particular triangle number has

// Just trying to find the first triangle number to have 500 divisors
while(start < 1000000000)
{
int temp = 1; // reset temp to start the test divisor at 1
// finding all the divisors
while(temp < sqrt(start))
{
//cout << "Test mod: " << start % temp << endl;
// checking if temp is a divisor
if(start % temp == 0)
{
++count;
}
++temp;
}
// double the number of divisors because they come in pairs and we only found the 1st half
// NOTE: if the number is a perfect square this program will not correctly give the number of divisors
// it will give one to many because it will be counting the same number twice
count = count * 2;

// print out the triangle number and its number of divisors
// cout << "Triangle number is: " << start << endl;
// cout << "Divisor total: " << count << endl;

// quit once we find one with more than 500
if(count > 500)
{
cout << "Triangle number is: " << start << endl;
cout << "Divisor total: " << count << endl;
exit(0);
}

// find the next triangle number
start = start +i;
++i;
count = 0;
}

return 0;
}


Monday, October 17, 2011

The beginning of spider ape

Just a blog mostly dedicated to programming, but with other thoughts interspersed too. Don't really know whats going to come of it. Plus everyone else has a blog so why shouldn't I.

Hopefully this blog helps me with two things.

  1. Sometimes I feel I don't give enough back to the interwebs. So maybe somebody will find the code I post on here useful.
  2. I float from project to project and maybe this will make me finish some things up.