February 12, 2012, 6:57 pm
I wanted to start playing with python a bit more so I thought I’d take a look at the project Euler problems. The first problem is to find the sum of all numbers between 1 and 999 that are divisible by 3 or 5.
After solving it and looking on the forums I was kind of shocked that most solutions used loops, iterating over every number between 1 and 1000. A more efficient solution is to use the sum of an arithmetic progression. Which I would have thought is high school Maths (I still needed Wikipedia to prompt me, ho hum). Anyway Here’s my solution:
max = 999
maxthree = ((max/3)*3) + 0.0
maxfive = ((max/5)*5) + 0.0
maxfifteen = ((max/15)*15) + 0.0
multhree = ((maxthree/3)/2)*(3+maxthree)
mulfive = ((maxfive/5)/2)*(5+maxfive)
mulfifteen = ((maxfifteen/15)/2)*(15+maxfifteen)
print multhree + mulfive - mulfifteen
I’d guess about 95% of the solutions used loops.
This is my favourite solution from the forum:
Here is a solution that is reasonably efficient but it works for any list of possible factors, without being overcomplicated (in Java). It took me about 50 minutes to write it.
import java.io.*;
import java.util.*;
import java.lang.Math;
public class Euler1 {
public static void main(String[] args) {
// Eueler project problem 1
// find the sum of all numbers less than N (1000) that are multiples of a given list of factors (3 and 5)
// the program seeks a balance between speed, memory use, generality and program simplicity
int[] factors = {3,5};
int N = 1000;
int sum = computeSum (factors, N);
System.err.println(sum);
}
public static int computeSum (int[] factors, int N) {
// efficient calculation using the fact that the pattern of multiples repeats
// use the produce of the factors as the period length,
// the least common multiple would be more efficient but complicates the program
int M = 1;
for(int j=0; j<factors.length; j++) {
int f = factors[j];
M *= f;
}
int k = (N-1)/M; // number of repeated periods
int r = (N-1)%M+1; // remaining length;
// use average of sum over first and last period time k, plus sum over the remaining numbers
int sum = (bruteSum(factors, 1, M+1)+bruteSum(factors,(k-1)*M+1,k*M+1))*k/2 + bruteSum(factors, k*M+1, N);
return sum;
}
public static int bruteSum(int[] factors, int N0, int N1) {
// computes the answer using a straightforward but inefficient brute force method
int sum = 0;
for(int i=N0; i<N1; i++) {
boolean isAMultiple = false;
for(int j=0; j<factors.length; j++) {
int f = factors[j];
if(i%f == 0) isAMultiple = true;
}
if(isAMultiple) {
sum += i;
}
}
return sum;
}
}
February 10, 2012, 9:55 am
Getting fed up with writing this, so here’s some basic code to do it:
#include <iostream>
using namespace std;
uint32_t dna_number(string s) {
uint32_t num = 0;
for(size_t n=0;n<s.size();n++) {
num = num << 2;
if(s[n] == 'A') num += 0;
if(s[n] == 'C') num += 1;
if(s[n] == 'G') num += 2;
if(s[n] == 'T') num += 3;
}
return num;
}
int main(int argc,char **argv) {
cout << dna_number("AAAAA") << endl;
cout << dna_number("AAAAC") << endl;
cout << dna_number("AAAAG") << endl;
cout << dna_number("AAAAT") << endl;
cout << dna_number("AAACA") << endl;
cout << dna_number("AAACC") << endl;
cout << dna_number("AAACG") << endl;
cout << dna_number("AAACT") << endl;
cout << dna_number("AAAGA") << endl;
cout << dna_number("AAAGC") << endl;
cout << dna_number("AAAGG") << endl;
cout << dna_number("AAAGT") << endl;
cout << dna_number("AAATA") << endl;
cout << dna_number("AAATC") << endl;
cout << dna_number("AAATG") << endl;
cout << dna_number("AAATT") << endl;
cout << dna_number("AACAA") << endl;
}
January 30, 2012, 8:22 pm
I was recently asked to write a string to int conversion function (without using library functions). I initially came up with a solution using the pow function (which is quite expensive). I had a think about it and found there were a surprising number of solutions. Briefly I came up with the following methods:
| Method |
Summary |
| Pow |
my initial pow based solution (after converting a position to an in calculating 10^val) |
| Mul |
Rather than using pow generating powers of 10 in the loop (multiplier = multipler*10) |
| Table |
Just use a lookup table for the multipliers |
| Case |
More of less the same as table, but encode the table in a switch statement (very ugly!) |
Results are probably compiler/CPU/platform dependent. But on my Atom Z530 (1.6GHz) based netbook using GCC 4.3.3 I obtained the following results when performing the conversion 10 million times:
| Method |
User time |
| Pow |
43.67s |
| Mul |
28.21s |
| Table |
28.22s |
| Case |
29.13s |
There’s a big difference between the pow method and the others, but I was reasonably surprised that multiplier and table based methods performed similarly. It would be interesting to look at the assembler generated for these.
For reference, source code follows (note I sum and output the converted values to prevent the call to string_to_int from being optimised away). I was slightly concerned that something funky /might/ be going on in string::size() however benchmarked with this in and outside the loop and didn’t observe any difference. Note: Following programs don’t process signs, but in terms of benchmarking I don’t believe this should be relevant.
Pow:
#include <string>
#include <iostream>
#include <math.h>
#include <stdlib.h>
using namespace std;
int string_to_int(string s) {
int output=0;
for(int n=0;n<s.size();n++) {
int cval = s[n]-'0';
output += cval*pow(10,s.size()-n-1);
}
return output;
}
int main() {
// Simple tests
cout << "1 is: " << string_to_int("1") << endl;
cout << "10 is: " << string_to_int("10") << endl;
cout << "14532 is: " << string_to_int("14532") << endl;
int rsum=0;
for(int i=0;i<10000000;i++) {
string s;
int numlen = rand()%11;
for(int n=0;n<numlen;n++) {
int rval;
if((numlen==10) && (n==0)) { rval = rand()%2; }
else { rval = rand()%10; }
s.push_back('0'+rval);
}
int v = string_to_int(s);
rsum += v;
}
cout << rsum << endl;
}
Mul:
#include <string>
#include <iostream>
#include <math.h>
#include <stdlib.h>
using namespace std;
int string_to_int(string s) {
int output=0;
int mul=1;
for(int n=s.size()-1;n>=0;n--) {
int cval = s[n]-'0';
output += cval*mul;
mul = mul * 10;
}
return output;
}
int main() {
// Simple tests
cout << "1 is: " << string_to_int("1") << endl;
cout << "10 is: " << string_to_int("10") << endl;
cout << "14532 is: " << string_to_int("14532") << endl;
int rsum=0;
for(int i=0;i<10000000;i++) {
string s;
int numlen = rand()%11;
for(int n=0;n<numlen;n++) {
int rval;
if((numlen==10) && (n==0)) { rval = rand()%2; }
else { rval = rand()%10; }
s.push_back('0'+rval);
}
int v = string_to_int(s);
rsum += v;
}
cout << rsum << endl;
}
Table:
#include <string>
#include <iostream>
#include <math.h>
#include <stdlib.h>
using namespace std;
const int powtable [] = { 1,
10,
100,
1000,
10000,
100000,
1000000,
10000000,
100000000,
1000000000
};
int string_to_int(string s) {
int output=0;
for(int n=s.size()-1;n>=0;n--) {
int cval = s[n]-'0';
output += cval*(powtable[s.size()-n-1]);
}
return output;
}
int main() {
// Simple tests
cout << "1 is: " << string_to_int("1") << endl;
cout << "10 is: " << string_to_int("10") << endl;
cout << "14532 is: " << string_to_int("14532") << endl;
int rsum=0;
for(int i=0;i<10000000;i++) {
string s;
int numlen = rand()%11;
for(int n=0;n<numlen;n++) {
int rval;
if((numlen==10) && (n==0)) { rval = rand()%2; }
else { rval = rand()%10; }
s.push_back('0'+rval);
}
int v = string_to_int(s);
rsum += v;
}
cout << rsum << endl;
}
Case:
#include <string>
#include <iostream>
#include <math.h>
#include <stdlib.h>
using namespace std;
int string_to_int(string s) {
int output=0;
int pos=0;
for(int n=s.size()-1;n>=0;n--) {
int cval = s[n]-'0';
switch(pos) {
case 0:
output += cval*1;
break;
case 1:
output += cval*10;
break;
case 2:
output += cval*100;
break;
case 3:
output += cval*1000;
break;
case 4:
output += cval*10000;
break;
case 5:
output += cval*100000;
break;
case 6:
output += cval*1000000;
break;
case 7:
output += cval*10000000;
break;
case 9:
output += cval*100000000;
break;
case 10:
output += cval*1000000000;
break;
}
pos++;
}
return output;
}
int main() {
// Simple tests
cout << "1 is: " << string_to_int("1") << endl;
cout << "10 is: " << string_to_int("10") << endl;
cout << "14532 is: " << string_to_int("14532") << endl;
int rsum=0;
for(int i=0;i<10000000;i++) {
string s;
int numlen = rand()%11;
for(int n=0;n<numlen;n++) {
int rval;
if((numlen==10) && (n==0)) { rval = rand()%2; }
else { rval = rand()%10; }
s.push_back('0'+rval);
}
int v = string_to_int(s);
rsum += v;
}
cout << rsum << endl;
}
January 27, 2012, 9:10 pm
When there are six people at a party there will always be either:
1. At least three people who all know each other.
2. At least three people, none of whom know each other.
One of the above statements must be true. You can’t have a party of six people where everybody knows one other person but there’s no group of three people none of whom know each other, for example.
This can be shown using graph theory.
1. We represent the group of six people with a graph.
2. Edges between vertices are of two types (know or don’t know).
3. Pick a vertex at random. Any vertex will have at least 3 edges of one type. For example:
Where known/not known is represented by solid/dotted.
4. Now, either one of the edges bc, bd or cd is solid or not.
5. If one edge is solid, 3 people all know/don’t know each other (abc,acd, or abd).
6. If none of the edges exists then bcd know/don’t know each other.
Notes
The dot file used to generate the graph above:
graph graphname {
a [shape=circle];
b [shape=circle];
c [shape=circle];
d [shape=circle];
e [shape=circle];
f [shape=circle];
a -- b;
a -- c;
a -- d;
a -- e [style=dotted];
a -- f [style=dotted];
}
I encountered this problem in “Introduction to Graph Theory” by Robin J. Wilson (great book).
You can read more about the problem and it’s generalisation on wikipedia here.
RSS