Project Something . . .
Posted: Thu May 07, 2009 10:52 pm
by sparda
Alright, so avan presented a nifty website to us all, HERE. Here you are to solve a set of challenges. I've solved 10 problems out of the many there are. I've provided some code below for the people who have solved problem 1, 2, 5, 6, 7, 8, 9, 13, 16 and 20. The code is set up in spoiler tags, so don't see it unless you've solved those!
NOTE: this is really messy code. I just wanted the answer, so I ignored proper design principles, duh! There are problems where I use python code, the rest is in C/C++.
Also, there is a lot of useless code as well. And unfinished stuff for problem 10 (sieve of ero).
EDIT: Removed the project name, so as to inhibit googling. Hopefully google refreshes their cache of this forum soon.
NOTE: this is really messy code. I just wanted the answer, so I ignored proper design principles, duh! There are problems where I use python code, the rest is in C/C++.
Also, there is a lot of useless code as well. And unfinished stuff for problem 10 (sieve of ero).
EDIT: Removed the project name, so as to inhibit googling. Hopefully google refreshes their cache of this forum soon.
Click here to see the hidden message (It might contain spoilers)
Code: Select all
// By Sparda, public domain
#include <iostream>
#include <cstdlib>
#include <cmath>
#include <stdio.h>
#include <stdlib.h>
//Nice little preprocessor directive ;)
#define STRINGIZE(x) #x
// Globals
#define MIL 4000000
#define EMPTY -1
#define MAX 2000
const int fibo[34] =
{
0,
1,
1,
2,
3,
5,
8,
13,
21,
34,
55,
89,
144,
233,
377,
610,
987,
1597,
2584,
4181,
6765,
10946,
17711,
28657,
46368,
75025,
121393,
196418,
317811,
514229,
832040,
1346269,
2178309,
3524578
};
// user defined types
typedef unsigned int u32;
// Some prototypes
void process(int ListA[], int ListB[]);
int sum(int x);
int fib(u32 n);
long fourmillion(void);
unsigned long long divisible(int x);
int sums_problem(void);
int main(void)
{
long long sum_of_primes = 0;
// This bunch is for the prime generation
int *ListA(NULL), *ListB(NULL);
ListA = new int [MAX];
ListB = new int [MAX]; // Could be set dynamically with a prompt
// by the user instead of initializing to MAX.
for(int i = 0; i < MAX ; ++i){
ListA[i] = i + 2; ListB[i] = EMPTY; // Set inital values
}
ListB[0] = ListA[0];
process(ListA, ListB);
for(int i = 0, j=1; i < MAX ; ++i, j++){
if(ListB[i] != EMPTY && ListB[i] < MAX) {
printf("#%d, %d\n",j, ListB[i]);
sum_of_primes += ListB[i];
}
}
printf("Problem 1: %d\n", sum(1000));
printf("Problem 2: %d\n", fourmillion());
printf("Problem 4: %d\n");
printf("Problem 5: (did this one on paper) %s)\n", STRINGIZE(232792560));
printf("Problem 6: %d\n", sums_problem());
printf("Problem 7: %d\n", 104743); // Calulated with my function "Process()" above.
printf("Problem 10: %d\n", sum_of_primes);
//printf("\nProblem 3: %d\n", largest(NUM));
delete [] ListA, ListB;
return 0;
}
/* Problem 1 */
int sum(int x)
{
int i, j;
for(i = 0, j = 0; i < x; i++){
if(i%3==0 || i%5==0)
j+=i;
}
return j;
}
int fib(u32 n)
{
if(n <= 1) return n;
else {
return fib(n - 1) + fib(n - 2);
}
}
/* Problem 2 */
long fourmillion(void)
{
int i, sum, f = 0;
for(i = 0, sum = 0; i < 34; i++) {
if( (f = fibo[i]) % 2 == 0 )
sum += f;
}
return sum;
}
void process(int ListA[], int ListB[])
{
bool InitDone = false;
int Test = MAX - 1;
for(int i = 0, j = 0; i < MAX ; ++i){
if(!(ListA[i]%ListB[j]) && !InitDone)
ListA[i] = EMPTY;
if(i == Test && !InitDone){
i = 0; InitDone = true;
continue;
}
if(InitDone && ListA[i] == EMPTY) continue;
if(InitDone && ListA[i] != EMPTY){
j++; ListB[j] = ListA[i];
InitDone = false; i = 0;
continue;
}
if(j == Test) break;
}
}
int sums_problem(void)
{
int soq=0, qos=0;
for(int i = 1; i <= 100; i++) {
qos += i;
soq += pow(i, 2.0);
}
qos = pow(qos, 2.0 );
return qos - soq;
}
Code: Select all
#
# by sparda.
# Public Domain
# Im using python, as some of these problems require that I calculate huge
# integer values; I couldn't be bothered to use GMP, sorry to say.
#! /usr/bin/env python
from math import *
num = 600851475143L
jj = 7316717653133062491922511967442657474235534919493496983520312774506326239578318016984801869478851843858615607891129494954595017379583319528532088055111254069874715852386305071569329096329522744304355766896648950445244523161731856403098711121722383113622298934233803081353362766142828064444866452387493035890729629049156044077239071381051585930796086670172427121883998797908792274921901699720888093776657273330010533678812202354218097512545405947522435258490771167055601360483958644670632441572215539753697817977846174064955149290862569321978468622482839722413756570560574902614079729686524145351004748216637048440319989000889524345065854122758866688116427171479924442928230863465674813919123162824586178664583591245665294765456828489128831426076900422421902267105562632111110937054421750694165896040807198403850962455444362981230987879927244284909188845801561660979191338754992005240636899125607176060588611646710940507754100225698315520005593572972571636269561882670428252483600823257530420752963450
n = [
73167176531330624919225119674426574742355349194934L,
96983520312774506326239578318016984801869478851843L,
85861560789112949495459501737958331952853208805511L,
12540698747158523863050715693290963295227443043557L,
66896648950445244523161731856403098711121722383113L,
62229893423380308135336276614282806444486645238749L,
30358907296290491560440772390713810515859307960866L,
70172427121883998797908792274921901699720888093776L,
65727333001053367881220235421809751254540594752243L,
52584907711670556013604839586446706324415722155397L,
53697817977846174064955149290862569321978468622482L,
83972241375657056057490261407972968652414535100474L,
82166370484403199890008895243450658541227588666881L,
16427171479924442928230863465674813919123162824586L,
17866458359124566529476545682848912883142607690042L,
24219022671055626321111109370544217506941658960408L,
7198403850962455444362981230987879927244284909188L,
84580156166097919133875499200524063689912560717606L,
5886116467109405077541002256983155200055935729725L,
71636269561882670428252483600823257530420752963450L,
]
fifty = [
37107287533902102798797998220837590246510135740250L,
46376937677490009712648124896970078050417018260538L,
74324986199524741059474233309513058123726617309629L,
91942213363574161572522430563301811072406154908250L,
23067588207539346171171980310421047513778063246676L,
89261670696623633820136378418383684178734361726757L,
28112879812849979408065481931592621691275889832738L,
44274228917432520321923589422876796487670272189318L,
47451445736001306439091167216856844588711603153276L,
70386486105843025439939619828917593665686757934951L,
62176457141856560629502157223196586755079324193331L,
64906352462741904929101432445813822663347944758178L,
92575867718337217661963751590579239728245598838407L,
58203565325359399008402633568948830189458628227828L,
80181199384826282014278194139940567587151170094390L,
35398664372827112653829987240784473053190104293586L,
86515506006295864861532075273371959191420517255829L,
71693888707715466499115593487603532921714970056938L,
54370070576826684624621495650076471787294438377604L,
53282654108756828443191190634694037855217779295145L,
36123272525000296071075082563815656710885258350721L,
45876576172410976447339110607218265236877223636045L,
17423706905851860660448207621209813287860733969412L,
81142660418086830619328460811191061556940512689692L,
51934325451728388641918047049293215058642563049483L,
62467221648435076201727918039944693004732956340691L,
15732444386908125794514089057706229429197107928209L,
55037687525678773091862540744969844508330393682126L,
18336384825330154686196124348767681297534375946515L,
80386287592878490201521685554828717201219257766954L,
78182833757993103614740356856449095527097864797581L,
16726320100436897842553539920931837441497806860984L,
48403098129077791799088218795327364475675590848030L,
87086987551392711854517078544161852424320693150332L,
59959406895756536782107074926966537676326235447210L,
69793950679652694742597709739166693763042633987085L,
41052684708299085211399427365734116182760315001271L,
65378607361501080857009149939512557028198746004375L,
35829035317434717326932123578154982629742552737307L,
94953759765105305946966067683156574377167401875275L,
88902802571733229619176668713819931811048770190271L,
25267680276078003013678680992525463401061632866526L,
36270218540497705585629946580636237993140746255962L,
24074486908231174977792365466257246923322810917141L,
91430288197103288597806669760892938638285025333403L,
34413065578016127815921815005561868836468420090470L,
23053081172816430487623791969842487255036638784583L,
11487696932154902810424020138335124462181441773470L,
63783299490636259666498587618221225225512486764533L,
67720186971698544312419572409913959008952310058822L,
95548255300263520781532296796249481641953868218774L,
76085327132285723110424803456124867697064507995236L,
37774242535411291684276865538926205024910326572967L,
23701913275725675285653248258265463092207058596522L,
29798860272258331913126375147341994889534765745501L,
18495701454879288984856827726077713721403798879715L,
38298203783031473527721580348144513491373226651381L,
34829543829199918180278916522431027392251122869539L,
40957953066405232632538044100059654939159879593635L,
29746152185502371307642255121183693803580388584903L,
41698116222072977186158236678424689157993532961922L,
62467957194401269043877107275048102390895523597457L,
23189706772547915061505504953922979530901129967519L,
86188088225875314529584099251203829009407770775672L,
11306739708304724483816533873502340845647058077308L,
82959174767140363198008187129011875491310547126581L,
97623331044818386269515456334926366572897563400500L,
42846280183517070527831839425882145521227251250327L,
55121603546981200581762165212827652751691296897789L,
32238195734329339946437501907836945765883352399886L,
75506164965184775180738168837861091527357929701337L,
62177842752192623401942399639168044983993173312731L,
32924185707147349566916674687634660915035914677504L,
99518671430235219628894890102423325116913619626622L,
73267460800591547471830798392868535206946944540724L,
76841822524674417161514036427982273348055556214818L,
97142617910342598647204516893989422179826088076852L,
87783646182799346313767754307809363333018982642090L,
10848802521674670883215120185883543223812876952786L,
71329612474782464538636993009049310363619763878039L,
62184073572399794223406235393808339651327408011116L,
66627891981488087797941876876144230030984490851411L,
60661826293682836764744779239180335110989069790714L,
85786944089552990653640447425576083659976645795096L,
66024396409905389607120198219976047599490197230297L,
64913982680032973156037120041377903785566085089252L,
16730939319872750275468906903707539413042652315011L,
94809377245048795150954100921645863754710598436791L,
78639167021187492431995700641917969777599028300699L,
15368713711936614952811305876380278410754449733078L,
40789923115535562561142322423255033685442488917353L,
44889911501440648020369068063960672322193204149535L,
41503128880339536053299340368006977710650566631954L,
81234880673210146739058568557934581403627822703280L,
82616570773948327592232845941706525094512325230608L,
22918802058777319719839450180888072429661980811197L,
77158542502016545090413245809786882778948721859617L,
72107838435069186155435662884062257473692284509516L,
20849603980134001723930671666823555245252804609722L,
53503534226472524250874054075591789781264330331690L
]
def factorial(x):
if x <= 0:
return 1
else:
return factorial(x-1)*x
def main():
sums = 0
num = factorial(100)
l = str(num)
for i in l:
sums += int(i)
print sums
sums = 0
for i in fifty:
sums = sums + i
l = str(sums)
print len(l)
print sums
for i in range(11):
print l[i],
# Problem 16
x = pow(2, 1000)
x = int(x)
l = str(x)
sums = 0
for i in l:
sums += int(i)
print
print sums
print
#problem 8
max = 0
k = str(jj)
for i in range(len(k)-4):
if(int(k[i])*int(k[i+1])*int(k[i+2])*int(k[i+3])*int(k[i+4]) > max):
max = int(k[i])*int(k[i+1])*int(k[i+2])*int(k[i+3])*int(k[i+4])
print max
return
main()
