Archive for December, 2011

Project Euler Problem 17

I’ve been having some fun doing the first few problems of Project Euler and figured I’d share my solution to problem 17 here.

The Problem
If the numbers 1 to 5 are written out in words: one, two, three, four, five, then there are 3 + 3 + 5 + 4 + 4 = 19 letters used in total.

If all the numbers from 1 to 1000 (one thousand) inclusive were written out in words, how many letters would be used?

NOTE: Do not count spaces or hyphens. For example, 342 (three hundred and forty-two) contains 23 letters and 115 (one hundred and fifteen) contains 20 letters. The use of “and” when writing out numbers is in compliance with British usage.

The Solution
The reason I love this solution is I found a PHP library that writes out these numbers for you. It comes from PECL 1.0 and is part of PHP 5.3 via that NumberFormatter class. This class did most of the work for me.

<?
$res = "";
 
$f = new NumberFormatter("en", NumberFormatter::SPELLOUT);
 
for($i = 1; $i format($i));
	if($i > 100 && $i % 100 != 0) {
		$res .= 'and';
	}
}
echo strlen($res)."\n";

My first submission was incorrect and I quickly figured out it was because the NumberFormatter class was missing the “and” after the hundreds. I simply added that at the end since we’re only looking for a count and came up with the correct result.

Installing the NumberFormatter class in Debian squeeze was pretty easy. I simply had to install the PHP5 international compatibility package: sudo apt-get instal php5-intl

How do I perform integer division in PHP

PHP’s division operator returns a floating point result from the division operator unless both operands are integers and they are evenly divisible (the result is an integer). I was recently working on Project Euler Problem 13 and needed to do integer division, something I haven’t come across in PHP before.

Integer division in PHP is pretty straight forward. Casting the result as an integer will yield an integer. That is:

var_dump(25/7);         // float(3.5714285714286) 
var_dump((int) (25/7)); // int(3)
var_dump(round(25/7));  // float(4)

Project Euler Problem 10

I’ve been having some fun doing the first few problems of Project Euler and figured I’d share my solution to problem 10 here.

The Problem
The sum of the primes below 10 is 2 + 3 + 5 + 7 = 17.
Find the sum of all the primes below two million.

The Solution
My solution is fairly simple, testing primality for all the numbers below 2,000,000. If prime, adding them to a running total.

/**
 * Calculate the sum of all the primes below two million. 
 **/
#include 
#include 
using namespace std;
 
bool isPrime(long num) {
	if(num<=1)
		return false;
	for(long i=2; i<=sqrt(num*1.0); i++)
	{
		if(num%i==0)
			return false;
	}
	return true;
}
 
int main () {
	long upperlimit = 2000000, sum = 0;
 
	for (long i = 2; i < upperlimit; i++) {
		if(isPrime(i)) {
			sum += i;
			cout << "Prime found: " << i << endl;
		}
	}
 
	cout << "The sum of primes below " << upperlimit << " is " << sum << endl;
 
	return (0);
}

The interesting part of this problem for me was I updated my primality test to include the fact that if a number n has a factor greater than sqrt(n) it must also have one less than sqrt(n), so we only have to test up to sqrt(n) in our primality test:

bool isPrime(long num) {
	if(num<=1)
		return false;
	for(long i=2; i<=sqrt(num*1.0); i++)
	{
		if(num%i==0)
			return false;
	}
	return true;
}

Project Euler Problem 9

I’ve been having some fun doing the first few problems of Project Euler and figured I’d share my solution to problem 9 here.

The Problem
A Pythagorean triplet is a set of three natural numbers, a b c, for which,a^2 + b^2 = c^2
There exists exactly one Pythagorean triplet for which a + b + c = 1000. Find the product abc.

The Solution
This is pretty basic and inefficient, but I decided to loop through a and b, calculating c from the difference.

#include 
using namespace std;
 
int main () {
 
        for(int a = 1; a < 1000; a++) {
                for(int b = 1; b < 1000; b++) {
                        cout << "a: " << a << " b: " << b << " c: " << (1000 - a - b) << " a^2 + b^2: " << (a * a + b * b) << " c^2: " << (1000 - a - b) * (1000 - a - b) << endl;
                        if(a * a + b * b == (1000 - a - b) * (1000 - a - b)) {
                                return (0);
                        }
                }
        }
        return (0);
}

There you have it, the program stops at a^2 + b^2 = c^2 where c = (1000 – a – b). I then took a*b*c to get the answer.

Removing more WordPress Meta tags

If you have a relatively new installation of wordpress you will notice there are a bunch of meta tags in the source that are not that common to see. “Which ones do I need?” I thought. Well since I was using a wordpress page to run code that would generate dynamic content for multiple urls I knew I needed to get rid of the ones showing the actual page URL.

EditURI and Windows Live Writer

<link rel="EditURI" type="application/rsd+xml" title="RSD" href="http://yoursite.com/xmlrpc.php?rsd" />
<link rel="wlwmanifest" type="application/wlwmanifest+xml" href="http://yoursite.com/wp-includes/wlwmanifest.xml" />

EditURI will help client software discover your site. “wlwmanifest” sets up support for Windows Live Writer tagging. This maybe valuable to some of us and it didn’t really hurt my case so I left it. If you’d like to remove them, add these lines of code to your functions.php file in your theme:

remove_action('wp_head', 'wlwmanifest_link');
remove_action('wp_head', 'rsd_link');

index, prev, next

<link rel='index' title='indextitle' href='http://yoursite.com/' />
<link rel='prev' title='prev_page_title' href='http://yoursite.com/prev/' />
<link rel='next' title='next_page_title' href='http://yoursite.com/next/' />

These are here to help explain to search engines how your page hierarchy is displayed. If you are running a straight up blog like ServerSideGuy.com, then this will probably work. But it seems like it trips up on pages. You should have a good sitemap.xml file with good prioritization so I really didn’t see the value here. I left the index as that will always be the same.

remove_action( 'wp_head', 'adjacent_posts_rel_link_wp_head', 10, 0 );

Note: Older wordpress versions use ‘adjacent_posts_rel_link’ as the action

Generator
This one I would recommend every wordpress user in removing. It’s there to tell search engines that this is a wordpress site. But this is only used in data gathering so WordPress can say they have X percent marketshare. Since it plainly displays the version of wordpress, I say it needs to go. You never know when the next exploit will be found and if its in the version you are using do you really want hackers to see that?

<meta name="generator" content="WordPress 3.2.1" />

Remove this with:

remove_action( 'wp_head', 'wp_generator');

Canonical URLs: How to Disable in WordPress

Canonical URL tags help eliminate self-created duplicate content in the index, which is an important addition to good SEO practices.

In the newer version of wordpress (version 2.9+) they included and canonical URL function.  Since any good SEO plugin handles these links in a better format, you can just disable the auto generated one.  Adding the following anywhere in your theme’s functions.php will solve the problem splendidly:

# Remove canonical links function
remove_action('wp_head', 'rel_canonical');

Project Euler Problem 7

I mentioned yesterday, I’ve been doing the first few problems of Project Euler and figured I’d share my solution to problem 7 here.

The Problem
By listing the first six prime numbers: 2, 3, 5, 7, 11, and 13, we can see that the 6th prime is 13.
What is the 10,001st prime number?

The Solution
Let’s define a function isPrime(num) (granted, could be more efficient) and loop through the natural numbers, counting those that are prime.

/**
 * Find the difference between the sum of the squares of the first one hundred natural numbers and the square of the sum.
 **/
#include
using namespace std;
 
bool isPrime ( unsigned long num ) {
        for(int i = num - 1; i > 1; i--) {
                if(num % i == 0) {
                        return false;
                }
        }
        return true;
}
 
int main () {
        unsigned long num = 2, primeCount = 0;
 
        while ( primeCount < 10001 ) {
                if ( isPrime (num) ) {
                        primeCount++;
                        cout << "Prime " << primeCount << " " << num << " is prime" << endl;
                }
                num++;
        }
 
        return(0);
}

Project Euler Problem 6

I mentioned yesterday, I’ve been doing the first few problems of Project Euler and figured I’d share my solution to problem 6 here.

The Problem
Find the difference between the sum of the squares of the first one hundred natural numbers and the square of the sum.

The Solution
This one is pretty straight forward. Find a data structure capable of holding the square of the sum of numbers 1 to 100 and subtract the squares of the first 100 natural numbers.

#include 
using namespace std;
 
int main () {
        unsigned long sumsquares = 0, sums = 0;
        int n;
 
        cout <> n;
 
        while (n < 0) {
                cout <> n;
        }
 
        for(int i = 1; i <= n; i++) {
                cout << "i: " << i << endl;
                sumsquares += i * i;
                cout << "sumsquares: " << sumsquares << endl;
                sums += i;
                cout << "sums: " << sums << endl;
        }
 
        cout << "The sum of squares from 1 to " << n << ": " << sumsquares << endl;
        cout << "The square of sums from 1 to " << n << ": " << sums * sums << endl << endl;
        cout << "The difference: " << (sums * sums - sumsquares) << endl;
 
        return(0);
}

As you can see, there is a loop creating the sum and the sum of squares. From there, it subtracts the square of the sum and the sum of squares to get the answer.

Project Euler Problem 5

I’ve been having some fun doing the first few problems of Project Euler and figured I’d share my solution to problem 5 here.

The Problem
2520 is the smallest number that can be divided by each of the numbers from 1 to 10 without any remainder. What is the smallest positive number that is evenly divisible by all of the numbers from 1 to 20?

The Solution
This problem, worded another way, asks what the least common multiple of all the integers between 1 and 20 is. Since multiplication is commutative, the least common multiple of a series is the same as computing the least common multiple of all the numbers before it and the current. So, LCM(1…6) is the same as LCM(6, LCM(5, LCM(4, LCM(3, LCM(2, 1))))).

#include 
using namespace std;
 
unsigned long gcd(unsigned long a, unsigned long b) {
	if(b == 0)
		return a;
	return gcd(b, a%b);
}
 
unsigned long lcm(unsigned long a, unsigned long b) {
	return a * b / gcd(a,b);
}
 
int main ()
{
	unsigned long answer = 1;
	for(long i = 1; i <= 20; i++) {
		cout << "i: " << i;
		answer = lcm(answer, i);
		cout << " lcm: " << answer << endl;
	}
 
	return 0;
}

My solution uses an algorithm to compute the least common multiple that involves finding the greatest common divisor as follows: lcm(a, b) = a*b / gcd(a, b). I used the Euclid method of finding the greatest common divisor: gcd(a,0) = a; gcd(a, b) = gcd(b, a mod b).

“mysql_connect(): [2002] No such file or directory” error on Apple OS

I ran into a problem setting up a php framework on a Mac Mini. Once I thought I had everything configured I found this error:

“Warning:mysql_connect(): [2002] No such file or directory”

I went and rechecked everything but without any results plus the error is not very descriptive of the problem.

After some search engine tech support, I realized this error is related to the mysql socket. It seems the OS can put the needed socket in different directories. In my case, it was in /tmp/mysql.sock while php was looking at /var/mysql/mysql.sock. I copied it to the path php was looking for and the error disappeared. This may happen the other way around where you’d need to copy the file to /tmp/mysql.sock but I am not sure what criteria gives what result.