Project Euler Problem 13
Posted on January 17, 2012 by Sameer
Problem 13
#include “stdio.h”
#include “conio.h”
#include “iostream”
#include “fstream”
#include “string”
#include “list”
using namespace std;
void print(list<__int8> *integer)
{
int size=integer->size();
char *buffer= new char[size+1];
*(buffer+size)=’\0′;
int j=size-1;
for (list<__int8>::iterator i=integer->begin();i!=integer->end();i++, j–)
{
*(buffer+j)=*i+’0′;
}
cout<<buffer;
delete buffer;
}
void main ()
{
string STRING;
size_t chars_read = 0;
const int SIZE=51;
char buffer[SIZE]=”\0″; //initiating all values of the arrqay to 0;
list<__int8> *integer = new list<__int8>();//Sameer,dont want to use pointers but list wont accept anything wihtout pointer
ifstream infile (“num.txt”);
//the number of numbers to add is 100
for (int i=0;i<100;i++)
{
if (infile.eof())
{
break;
}
else
{
//read 51 because the return character will be the ‘\0′
infile.read(buffer,SIZE);
if(integer->empty())
{
for (int i=SIZE-1;i>=0;i–)// add the digits into the list in reverse order.
{
integer->push_back(buffer[i]-’0′);// deducting the character value by ’0′ char value gives us the integer.
}
}
else
{
/*__int8 is used to reduce memory consumption.
loop through the integer array and buffer. add the numbers.*/
int sum =0;
list<__int8>::iterator it=integer->begin();
for (int j=SIZE-1;j>=0;j–)
{//I think this variable is worngfully called sum. It should be called partial sum since it adds 2 single digit numbers (max can be 9+9 = 18) and the rest it shifts over to the next number
sum += (buffer[j] -’0′) + *it;
if(sum>9)
*it++ = sum -10; //18-10 = 8 equals remainder or 19-10 = 9 (if there is a remainder from previous sum value i.e sum/=10 equals 1
else
*it++ = sum;
sum/=10; //so sum will either be 1 or 0
}
while(it!=integer->end() && sum>0)
{
sum+=*it;
if(sum>9)
*it++ = sum -10;
else
*it++ = sum;
sum/=10;
}
if (sum>0 && it==integer->end())
{
integer->push_back(sum);
}
}
}
}
print(integer);
delete integer;
}
Following link was helpful:
http://mafahir.wordpress.com/2010/12/04/adding-50-digit-numbers-cc-implementation/
Project Euler Problem 22
Posted on March 14, 2012 by Sameer
Project Euler Problem 22
Language: C++
#include "stdafx.h"
#include "stdio.h"
#include "conio.h"
#include "iostream"
#include "fstream"
#include "string"
#include "list"
#include "vector"
#include "map"
#include "sstream"
#include "iomanip"//for using setw
using namespace std;
map <long int, string> CharNumberValue;
vector <string> line(103);
int number[103][103];
int main ()
{
vector <vector <string> > data;
vector <string> NamesUnsorted;
vector <char[300]> CharUnsorted;
long long int tempNameValue=0;
//vector <string> NamesSorted;
string NamesSorted;
vector <int> NameValue;
ifstream infile( "names.txt" );
while (infile)
{
string s;
if (!getline( infile, s )) break;
istringstream ss( s );
while (ss)
{
string s;
if (!getline( ss, s, ',' )) break;
NamesUnsorted.push_back( s );
}
// data.push_back( NamesUnsorted );//meaningless
}
//selection sort or insertion sort: Since its a large list, I will go with insertion sort.
for (int iCv=1;iCv<NamesUnsorted.size();iCv++)
{
//the new value to be inserted into a temporary location
NamesSorted = NamesUnsorted[iCv];
// k is the index of the number to the left of the iCv.
int k;
for (k = iCv-1; k >= 0 && NamesUnsorted[k] > NamesSorted; k--)
{
NamesUnsorted[k+1] = NamesUnsorted[k];
}
NamesUnsorted[k+1] = NamesSorted;
}
//for(int iCv=0;iCv<NamesUnsorted.size();iCv++) cout<<NamesUnsorted[iCv]<<" ";
//cout<<endl;
//after the sort, multiply the position to the char value
//string to char conversion
for(int iCv=0;iCv<NamesUnsorted.size();iCv++)
{
char *a=new char[NamesUnsorted[iCv].size()+1];
a[NamesUnsorted[iCv].size()]=0;
memcpy(a,NamesUnsorted[iCv].c_str(),NamesUnsorted[iCv].size());
int i=0, temp=0;
while(a[i]!='\0')
{
//take another var and multiply the i
if(a[i] != '"')
{
temp += int(a[i]) ;
temp -=64; //For ascii TO alphabetical places
}
i++;
}
temp *= (iCv+1); //Mul the location to value-----array starts at 0 so +1 i.e val of iCv + 1
tempNameValue += temp;
cout<<endl<<" Count Value of "<<NamesUnsorted[iCv]<<" is: "<< temp<<".Total Value is: "<< tempNameValue;
}
if (!infile.eof())
{
cerr << "Fooey!\n";
}
return 0;
}
Following link was helpful:
http://www.daniweb.com/software-development/cpp/threads/64778/1780074#post1780074
Project Euler Problem 21
Posted on February 22, 2012 by Sameer
Project Euler Problem 21
Language: C++
#include "stdafx.h"
#include "stdio.h"
#include "conio.h"
#include "iostream"
#include "fstream"
#include "string"
#include "list"
#include "vector"
#include "map"
using namespace std;
map<int, int> DivisorSumMap ;
int SumOfDivisors(int i)
{
int sum = 0;
for (int j=1;j<i;j++)//Just proper Divisors
{
if(i%j ==0)
{
sum += j;
}
}
return sum;
}
int main()
{
long long int AmicableSum = 0;
string printword ="";
for(int i=1; i< 10000; i++)
{
DivisorSumMap[i] = SumOfDivisors(i);
}
for (int i=2;i< 10000; i++)
{
int xval1,yval1,xval2,yval2;
map< int, int>:: iterator it1 = DivisorSumMap.find(i);
xval1=it1->first;
yval1=it1->second;
//if some values in the map are greater than the 10000, just take the value less than 10000 into consideration
if(yval1>10000)
{
yval2=SumOfDivisors(yval1);
}
else
{
map<int, int>:: iterator it2 = DivisorSumMap.find(yval1);
xval2=it2->first;
yval2=it2->second;
}
if(yval2==xval1)
{
AmicableSum +=xval1;
if(xval1 != xval2)
{
AmicableSum +=xval2;
}
else//if they are perfect
{
AmicableSum -=xval2;
}
//To avoid re adding
DivisorSumMap[xval1]=92;
DivisorSumMap[xval2]=91;
cout<<xval1 << " and " << xval2 << "are amicable.Amicable Sum was "<<AmicableSum<<endl;
}
}
return 0;
}
Project Euler Problem 20
Posted on January 26, 2012 by Sameer
Project Euler Problem 20
Language Used:C++ (Not external library like GMP or additional functions)
#include “stdio.h”
#include “conio.h”
#include “iostream”
#include “fstream”
#include “string”
#include “list”
#include “vector”
#include “map”
//#include “math.h”
void main()
{
//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
long k;
int count1=0;
cout<<”Enter a number whose factorial needs to be calculated:”;
cin>>k;
//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
/////////////////code for numbers which are less than 33 and greater than 3///////////////////////////////////////////////////////////
if (k<=33)
{
unsigned double long fact=1;
fact=1;
for(int b=k;b>=1;b–)
{
fact=fact*b;
}
cout<<”The factorial of “<<k<<” is “<<fact<<endl;
}
/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
////////////////code for numbers which are greater than 33 ///////////////////////////////////////////////////////////
else
{
//Sameer, Increased the size of the array from 10000 to 100000
int numArr[100000];
int total,rem=0,count; //rem use to save remainder of division(Carry Number).
register int i; //register will enhance performance by minimizing access time
//int i;
for(i=0;i<100000;i++)
numArr[i]=0; //set all array on NULL.
numArr[100000]=1; //start from end of array.
for(count=2;count<=k;count++)
{
while(i>0)
{
total=numArr[i]*count+rem; //rem will add the carry number to the next array digit that is multiplied to the count
rem=0;
if(total>9)
{
numArr[i]=total%10;
rem=total/10;
}
else
{
numArr[i]=total; //numArr[i] is being accessed in this for loop because we have made i as register which means the memory is allocated
}
i–;
}
rem=0;
total=0;
i=100000;
}
cout<<”The factorial of “<<k<<” is “;
for(i=0;i<100000;i++)
{
if(numArr[i]!=0 || count==1)
{
cout<<numArr[i];
count=1;
count1 +=numArr[i];
}
}
cout<<endl;
}
cout<< endl<<count1;
}
This link was helpful:
http://www.daniweb.com/software-development/cpp/code/250350
Project Euler Problem 67 and 18
Posted on January 19, 2012 by Sameer
The following is the solution to two similar problems: Problem 18 and Problem 67
Language:C++
#include “stdafx.h”
#include “stdio.h”
#include “conio.h”
#include “iostream”
#include “fstream”
#include “string”
#include “list”
#include “vector”
#include “map”
using namespace std;
map CharNumberValue;
vector line(103);
int number[103][103];
int getMax(int a, int b) {
int c = a – b;
int k = (c >> 31) & 0×1;
int max = a – k * c;
return max;
}
void main ()
{
string STRING;
char col[5000];
size_t chars_read = 0;
int i=0,j=0, partialsum[15];
int depth;
ifstream infile;
infile.open (“Prob67.txt”);//change for Prob18
while( infile ) {
if( infile )
{
string Tline;
std::getline(infile,Tline);
line[i] = Tline;
//following 3 lines convert the string to char
char *a=new char[line[i].size()+1];
a[line[i].size()]=0;
memcpy(a,line[i].c_str(),line[i].size());
//following 4 lines seperates the values after whitespace
char *p = strtok(a, ” “);
while (p)
{
number[i][j]=atoi(p);//convert p to int
//cout<
}
Following links were helpful:
http://blog.vi-kan.net/2010/project-euler-problem-18-67/
http://stackoverflow.com/questions/5792721/problem-with-project-euler-problem-18
Project Euler Problem 17
Posted on January 17, 2012 by Sameer
Problem 17
#include “stdio.h”
#include “conio.h”
#include “iostream”
#include “fstream”
#include “string”
#include “list”
#include “vector”
#include “map”
using namespace std;
map<long int, string> CharNumberValue ;
int main()
{
CharNumberValue[0] =”zero”;
CharNumberValue[1] =”one”;
CharNumberValue[2] =”two”;
CharNumberValue[3] =”three”;
CharNumberValue[4] =”four”;
CharNumberValue[5] =”five”;
CharNumberValue[6] =”six”;
CharNumberValue[7] =”seven”;
CharNumberValue[8] =”eight”;
CharNumberValue[9] =”nine”;
CharNumberValue[10] =”ten”;
CharNumberValue[11] =”eleven”;
CharNumberValue[12] =”twelve”;
CharNumberValue[13] =”thirteen”;
CharNumberValue[14] =”fourteen”;
CharNumberValue[15] =”fifteen”;
CharNumberValue[16] =”sixteen”;
CharNumberValue[17] =”seventeen”;
CharNumberValue[18] =”eighteen”;
CharNumberValue[19] =”nineteen”;
CharNumberValue[20] =”twenty”;
CharNumberValue[30] =”thirty”;
CharNumberValue[40] =”forty”;
CharNumberValue[50] =”fifty”;
CharNumberValue[60] =”sixty”;
CharNumberValue[70] =”seventy”;
CharNumberValue[80] =”eighty”;
CharNumberValue[90] =”ninety”;
CharNumberValue[100] =”hundred”;//Sameer,remember 100 is one hundred
CharNumberValue[1000] =”thousand”;//Sameer,remember 1000 is one thousand
long long int count = 0;
string printword =”";
for(int i=1; i<= 1000; i++)
{
if(i<=100)
{
int ten = (i/10)*10;
int unit = i%10;
map<long int, string>:: iterator it = CharNumberValue.find(i);
map<long int, string>:: iterator it1 = CharNumberValue.find(unit);
map<long int, string>:: iterator it2 = CharNumberValue.find(ten);
if(i<10)
{
count += it1->second.length();
printword = it1->second;
cout<<printword<<endl;
}
if(i>=10 && i<=20)
{
count += it->second.length();//These are unique
printword = it->second;
cout<<printword<<endl;
}
if(i>20 && i<100)
{
count += it2->second.length();
printword = it2->second ;
if ((i != 30)&&(i != 40)&&(i != 50)&&(i != 60)&&(i != 70)&&(i != 80)&&(i!= 90)&&(i!= 100))
{
count += it1->second.length();
printword = it2->second + ” ” + it1->second ;
}
cout<<printword<<endl;
}
if(i==100)
{
count += 10;//Add one hundred
}
}
if(i>100 && i<1000)
{
int hun = i/100;
int ten=i%100;
int mten = (ten/10)*10;//modified ten
int unit = ten%10;
map<long int, string>:: iterator it = CharNumberValue.find(unit);
map<long int, string>:: iterator it1 = CharNumberValue.find(mten);
map<long int, string>:: iterator it2 = CharNumberValue.find(ten);
map<long int, string>:: iterator it3 = CharNumberValue.find(hun);
int counttemp = CharNumberValue[100].length();
count += it3->second.length() + CharNumberValue[100].length();
printword = it3->second + ” ” + CharNumberValue[100];
if((i != 200)&&(i != 300)&&(i != 400)&&(i != 500)&&(i != 600)&&(i != 700)&&(i != 800)&&(i != 900))
{
if( ten<=20)
{
count += 3/*for and */+ it2->second.length() ;//These are unique
printword = it3->second + ” ” + CharNumberValue[100] + ” and “ + it2->second ;
cout<<printword<<endl;
}
if(ten>20 && ten<=99)
{
count += 3/*for and */+ it1->second.length();
printword = it3->second + ” ” + CharNumberValue[100] + ” and “ + it1->second;
if ((ten != 30)&&(ten != 40)&&(ten != 50)&&(ten != 60)&&(ten != 70)&&(ten != 80)&&(ten!= 90)&&(ten!= 100))
{
count += it->second.length();
printword = it3->second + ” ” + CharNumberValue[100] + ” and “ + it1->second +” “+ it->second ;
}
cout<<printword<<endl;
}
}
else
{
cout<<printword<<endl;
}
}
}
count += 11;//for one thousand
cout<< count;
return 0;
}
Follwoing links were helpful:
http://blog.functionalfun.net/2008/08/project-euler-problem-17-converting.html
Project Euler Problem 13
Posted on January 17, 2012 by Sameer
Problem 13
#include “stdio.h”
#include “conio.h”
#include “iostream”
#include “fstream”
#include “string”
#include “list”
using namespace std;
void print(list<__int8> *integer)
{
int size=integer->size();
char *buffer= new char[size+1];
*(buffer+size)=’\0′;
int j=size-1;
for (list<__int8>::iterator i=integer->begin();i!=integer->end();i++, j–)
{
*(buffer+j)=*i+’0′;
}
cout<<buffer;
delete buffer;
}
void main ()
{
string STRING;
size_t chars_read = 0;
const int SIZE=51;
char buffer[SIZE]=”\0″; //initiating all values of the arrqay to 0;
list<__int8> *integer = new list<__int8>();//Sameer,dont want to use pointers but list wont accept anything wihtout pointer
ifstream infile (“num.txt”);
//the number of numbers to add is 100
for (int i=0;i<100;i++)
{
if (infile.eof())
{
break;
}
else
{
//read 51 because the return character will be the ‘\0′
infile.read(buffer,SIZE);
if(integer->empty())
{
for (int i=SIZE-1;i>=0;i–)// add the digits into the list in reverse order.
{
integer->push_back(buffer[i]-’0′);// deducting the character value by ’0′ char value gives us the integer.
}
}
else
{
/*__int8 is used to reduce memory consumption.
loop through the integer array and buffer. add the numbers.*/
int sum =0;
list<__int8>::iterator it=integer->begin();
for (int j=SIZE-1;j>=0;j–)
{//I think this variable is worngfully called sum. It should be called partial sum since it adds 2 single digit numbers (max can be 9+9 = 18) and the rest it shifts over to the next number
sum += (buffer[j] -’0′) + *it;
if(sum>9)
*it++ = sum -10; //18-10 = 8 equals remainder or 19-10 = 9 (if there is a remainder from previous sum value i.e sum/=10 equals 1
else
*it++ = sum;
sum/=10; //so sum will either be 1 or 0
}
while(it!=integer->end() && sum>0)
{
sum+=*it;
if(sum>9)
*it++ = sum -10;
else
*it++ = sum;
sum/=10;
}
if (sum>0 && it==integer->end())
{
integer->push_back(sum);
}
}
}
}
print(integer);
delete integer;
}
Following link was helpful:
http://mafahir.wordpress.com/2010/12/04/adding-50-digit-numbers-cc-implementation/
Project Euler Problem 8
Posted on January 17, 2012 by Sameer
Problem 8
#include “stdio.h”
#include “conio.h”
void main()
{
int just5=0;
int tempbigi=0,tempbiga=0,tempbigb=0,tempbigc=0,tempbigd=0;
int bigbigi=1,bigbiga=1,bigbigb=1,bigbigc=1,bigbigd=1;
char a1[1001]=”7316717653133062491922511967442657474235534919493496983520312774506326239578318016984801869478851843858615607891129494954595017379583319528532088055111254069874715852386305071569329096329522744304355766896648950445244523161731856403098711121722383113622298934233803081353362766142828064444866452387493035890729629049156044077239071381051585930796086670172427121883998797908792274921901699720888093776657273330010533678812202354218097512545405947522435258490771167055601360483958644670632441572215539753697817977846174064955149290862569321978468622482839722413756570560574902614079729686524145351004748216637048440319989000889524345065854122758866688116427171479924442928230863465674813919123162824586178664583591245665294765456828489128831426076900422421902267105562632111110937054421750694165896040807198403850962455444362981230987879927244284909188845801561660979191338754992005240636899125607176060588611646710940507754100225698315520005593572972571636269561882670428252483600823257530420752963450″;
//find product of consecutive 5 numbers
int i=0,a=1,b=2,c=3,d=4,count=0;
//i
while(a1[i] != ‘\0′)
{
just5 = (i+4);
count =0;
tempbigi = 1;
for(int j=i; j<=just5;j++)//j:1,2
{
count++;
int f=a1[j]-’0′; //7
tempbigi *= f; //21
}
bigbigi=(tempbigi>bigbigi)?tempbigi:bigbigi;
i += 5;
}
printf(“1st(i)=%d”, bigbigi);
//a
i=1;
while(a1[a] != ‘\0′)
{
just5 = (a+4);
count =0;
tempbiga = 1;
for(int j=i; j<=just5;j++)//j:1,2
{
count++;
int f=a1[j]-’0′; //7
tempbiga *= f; //21
}
bigbiga=(tempbiga>bigbiga)?tempbiga:bigbiga;
a += 5;
}
printf(“\n2nd(a) %d”, bigbiga);
//b
i=2;
while(a1[b] != ‘\0′)
{
just5 = (b+4);
count =0;
tempbigb = 1;
for(int j=i; j<=just5;j++)//j:1,2
{
count++;
int f=a1[j]-’0′; //7
tempbigb *= f; //21
if(tempbigb == 1666980)
{
printf(“hi”);
}
}
bigbigb=(tempbigb>bigbigb)?tempbigb:bigbigb;
b += 5;
}
printf(“\n3rd(b) %d”, bigbigb);
//c
i=3;
while(a1[c] != ‘\0′)
{
just5 = (c+4);
count =0;
tempbigc = 1;
for(int j=i; j<=just5;j++)//j:1,2
{
count++;
int f=a1[j]-’0′; //7
tempbigc *= f; //21
}
bigbigc=(tempbigc>bigbigc)?tempbigc:bigbigc;
c += 5;
}
printf(“\n4th(c) %d”, bigbigc);
//d
i=4;
while(a1[d] != ‘\0′)
{
just5 = (d+4);
count =0;
tempbigd = 1;
for(int j=i; j<=just5;j++)//j:1,2
{
count++;
int f=a1[j]-’0′; //7
tempbigd *= f; //21
}
bigbigd=(tempbigd>bigbigd)?tempbigd:bigbigd;
d += 5;
}
printf(“\n5th(d) %d”, bigbigd);
getch();
}
Problem 11
#include “stdio.h”
#include “conio.h”
int mul(int one, int two, int three, int four)
{
int product = one*two*three*four;
return product;
}
void main()
{
int grid [20][20]={
{8, 2, 22, 97, 38, 15, 0, 40, 0, 75, 4, 5, 7, 78, 52, 12, 50, 77, 91, 8},
{49, 49, 99, 40, 17, 81, 18, 57, 60, 87, 17, 40, 98, 43, 69, 48, 4, 56, 62, 0},
{81, 49, 31, 73, 55, 79, 14, 29, 93, 71, 40, 67, 53, 88, 30, 3, 49, 13, 36, 65},
{52, 70, 95, 23, 4, 60, 11, 42, 69, 24, 68, 56, 1, 32, 56, 71, 37, 2, 36, 91},
{22, 31, 16, 71, 51, 67, 63, 89, 41, 92, 36, 54, 22, 40, 40, 28, 66, 33, 13, 80},
{24, 47, 32, 60, 99, 3, 45, 2, 44, 75, 33, 53, 78, 36, 84, 20, 35, 17, 12, 50},
{32, 98, 81, 28, 64, 23, 67, 10, 26, 38, 40, 67, 59, 54, 70, 66, 18, 38, 64, 70},
{67, 26, 20, 68, 2, 62, 12, 20, 95, 63, 94, 39, 63, 8, 40, 91, 66, 49, 94, 21},
{24, 55, 58, 5, 66, 73, 99, 26, 97, 17, 78, 78, 96, 83, 14, 88, 34, 89, 63, 72},
{21, 36, 23, 9, 75, 0, 76, 44, 20, 45, 35, 14, 0, 61, 33, 97, 34, 31, 33, 95},
{78, 17, 53, 28, 22, 75, 31, 67, 15, 94, 3, 80, 4, 62, 16, 14, 9, 53, 56, 92},
{16, 39, 5, 42, 96, 35, 31, 47, 55, 58, 88, 24, 0, 17, 54, 24, 36, 29, 85, 57},
{86, 56, 0, 48, 35, 71, 89, 7, 5, 44, 44, 37, 44, 60, 21, 58, 51, 54, 17, 58},
{19, 80, 81, 68, 5, 94, 47, 69, 28, 73, 92, 13, 86, 52, 17, 77, 4, 89, 55, 40},
{4, 52, 8, 83, 97, 35, 99, 16, 7, 97, 57, 32, 16, 26, 26, 79, 33, 27, 98, 66},
{88, 36, 68, 87, 57, 62, 20, 72, 3, 46, 33, 67, 46, 55, 12, 32, 63, 93, 53, 69},
{4, 42, 16, 73, 38, 25, 39, 11, 24, 94, 72, 18, 8, 46, 29, 32, 40, 62, 76, 36},
{20, 69, 36, 41, 72, 30, 23, 88, 34, 62, 99, 69, 82, 67, 59, 85, 74, 4, 36, 16},
{20, 73, 35, 29, 78, 31, 90, 1, 74, 31, 49, 71, 48, 86, 81, 16, 23, 57, 5, 54},
{1, 70, 54, 71, 83, 51, 54, 69, 16, 92, 33, 48, 61, 43, 52, 1, 89, 19, 67, 48}
};
int max=0,product=0;
//row
for (int i=0; i<20; i++)
{
for(int j=0;j<17;j++)
{
printf(“\n%d %d %d %d”,grid[i][j],grid[i][j+1],grid[i][j+2],grid[i][j+3] );
product = mul(grid[i][j],grid[i][j+1],grid[i][j+2],grid[i][j+3]);
max=(max>product)?max:product;
printf(“\n Maxproduct here is %d”,max);
}
}
//col
for (int i=0; i<17; i++)
{
for(int j=0;j<20;j++)
{
printf(“\n%d %d %d %d”,grid[i][j],grid[i+1][j],grid[i+2][j],grid[i+3][j] );
//row
product = mul(grid[i][j],grid[i+1][j],grid[i+2][j],grid[i+3][j]);
max=(max>product)?max:product;
printf(“\n Maxproduct here is %d”,max);
}
}
//right diagonal
for (int i=0; i<17; i++)
{
for(int j=0;j<17;j++)
{
printf(“\n%d %d %d %d”,grid[i][j],grid[i+1][j+1],grid[i+2][j+2],grid[i+3][j+3] );
//row
product = mul(grid[i][j],grid[i+1][j+1],grid[i+2][j+2],grid[i+3][j+3]);
max=(max>product)?max:product;
printf(“\n Maxproduct here is %d”,max);
}
}
//left diagonal
for (int i=0; i<17; i++)
{
for(int j=0;j<17;j++)
{
printf(“\n%d %d %d %d”,grid[i][j+3],grid[i+1][j+2],grid[i+2][j+1],grid[i+3][j] );
product = mul(grid[i][j+3],grid[i+1][j+2],grid[i+2][j+1],grid[i+3][j]);
max=(max>product)?max:product;
printf(“\n Maxproduct here is %d”,max);
}
}
printf(“\n Final Max is %d”,max);
getch();
}
Following link was helpful:
http://johnnycoder.com/blog/page/2/
Problem 19
Posted on January 24, 2012 by Sameer
Problem 19
Language:C++
using namespace std;
bool isLeapYear(int year) {
bool retval = false;
if (year % 100 == 0) {//this saves comparing every number by 400, just the one with 100
if (year % 400 == 0) {
retval = true;
}
} else if (year % 4 == 0) {
retval = true;
}
return retval;
}
void main()
{
int months[13] = {0,31,28,31,30,31,30,31,31,30,31,30,31};
int i4=1;
int countsun=0;
string tmonth;
vector <string> month;
tmonth = “”;
month.push_back(tmonth);
tmonth = “jan”;
month.push_back(tmonth);
tmonth = “feb”;
month.push_back(tmonth);
tmonth = “mar”;
month.push_back(tmonth);
tmonth = “apr”;
month.push_back(tmonth);
tmonth = “may”;
month.push_back(tmonth);
tmonth = “jun”;
month.push_back(tmonth);
tmonth = “jul”;
month.push_back(tmonth);
tmonth = “aug”;
month.push_back(tmonth);
tmonth = “sep”;
month.push_back(tmonth);
tmonth = “oct”;
month.push_back(tmonth);
tmonth = “nov”;
month.push_back(tmonth);
tmonth = “dec”;
month.push_back(tmonth);
string tweek;
vector <string> week;
tweek = “”;
week.push_back(tweek);
tweek = “mon”;//since first jan of 1900 was Mon
week.push_back(tweek);
tweek = “tue”;
week.push_back(tweek);
tweek = “wed”;
week.push_back(tweek);
tweek = “thu”;
week.push_back(tweek);
tweek = “fri”;
week.push_back(tweek);
tweek = “sat”;
week.push_back(tweek);
tweek = “sun”;
week.push_back(tweek);
//make 4 loops one inside another for years,months and days
//year (its between 1900 and 2000 not including these years)
for(int i1=1901;i1<2000;i1++)
{
bool leap = isLeapYear(i1);//check if leapyear or not
for (int i2=1;i2<=12;i2++)
{
int monthdays=months[i2];//based on the year and month selected, get the number of days in a month.
if( leap == true && i2 == 2)
{
monthdays = 29;
}
for (int i3=1;i3<=monthdays;i3++)
{
if(i4<=7)
{
cout<<endl<<”Today is “<<week[i4]<<” “<<i3<<” “<<month[i2]<< ” “<<i1;
if(week[i4]==”sun” && i3 == 1)
{countsun++;}
i4++;
}
else
{
i4=1;
cout<<endl<<”Today is “<<week[i4]<<” “<<i3<<” “<<month[i2]<< ” “<<i1;
if(week[i4]==”sun” && i3 == 1)
{countsun++;}
i4++;
}
}
}
}
cout<<endl<<”Total Sundays: “<<countsun;
}
Project Euler Problem 16
Posted on January 19, 2012 by Sameer
Problem 16
Language:C++
#include “stdafx.h”
#include “stdio.h”
#include “conio.h”
#include “iostream”
#include “fstream”
#include “string”
#include “list”
#include “vector”
#include “map”
#include “string”
using namespace std;
using namespace System;
using namespace System::Collections::Generic;
size_t int_read = 0;
const int SIZE=10;//need to 2 raised to 1000-30, 1000-30 times
int buffer[SIZE]; //initiating all values of the array to 0;
list<__int8> *integer = new list<__int8>();
//2 raised to 30 is the maximum value that a long integer can hold.
void print(list<__int8> *integer)
{
int size=integer->size();
char *buffer= new char[size+1];
*(buffer+size)=’\0′;
int j=size-1;
for (list<__int8>::iterator i=integer->begin();i!=integer->end();i++, j–)
{
*(buffer+j)=*i+’0′;
}
cout<<buffer;
delete buffer;
}
int main ()
{
for (int i = 0; i < 1000-30; i++)
{
buffer[0]=1;
buffer[1]=0;
buffer[2]=7;
buffer[3]=3;
buffer[4]=7;
buffer[5]=4;
buffer[6]=1;
buffer[7]=8;
buffer[8]=2;
buffer[9]=4;
if(integer->empty())
{
for (int i=SIZE-1;i>=0;i–)// add the digits into the list in reverse order.
{
integer->push_back(buffer[i]);// deducting the character value by ’0′ char value gives us the integer.
}
}
else
{
int sum=0;
list<__int8>::iterator it=integer->begin();
for (int j=SIZE-1;j>=0;j–)
{// Sum calculates partial sum. It adds 2 single digit numbers (max can be 9+9 = 18) and the rest it shifts over to the next number
sum += (buffer[j] ) + *it;
if(sum>9)
*it++ = sum -10; //18-10 = 8 equalls remainder or 19-10 = 9 (if there is a remainder from previous sum value i.e sum/=10 equals 1
else
*it++ = sum;
sum/=10; //so sum will either be 1 or 0
}
while(it!=integer->end() && sum>0)
{
sum+=*it;
if(sum>9)
*it++ = sum -10;
else
*it++ = sum;
sum/=10;
}
if (sum>0 && it==integer->end())
{
integer->push_back(sum);
}
}
}
print(integer);
delete integer;
return 0;
}
Project Euler Problem 14
Posted on January 19, 2012 by Sameer
Problem 14
Language: C++
#include “stdafx.h”
#include “stdio.h”
#include “conio.h”
#include “iostream”
#include “fstream”
#include “string”
#include “list”
#include “vector”
using namespace std;
//traverse the array for max term
long int max_array(vector<long int> a ,long int num_elements)
{
long int i, max=-32000;
for (i=0; i<num_elements; i++)
{
if (a[i]>max)
{
max=a[i];
}
}
return(max);
}
//recursive function to calculate and count based on Collatz_conjecture
long int Collatz( long int c1)
{
long long int b1 = c1;
long int counter = 1;
while (b1 != 1) {
++counter;
b1 = (b1 % 2 == 0) ? b1/2 : 3*b1+1;
}
return counter;
}
int main()
{
long int t1,max=0,major=0,minor=0,majora=0;
//vector<long int> totalcounter (1000000);
for (long int i=13;i<1000001;i++)
{
minor=Collatz(i);
major = (major > minor ) ? major : minor;
majora =
//cout << “The Counter for no ” << i <<” is ” << totalcounter[i] << ‘\n’;
cout <<”i:”<<i <<” “<< major <<’\n’;
}
// max = max_array(totalcounter, 1000000);
//cout << “The max is ” << max << ‘\n’;
cout << “The max is ” << major << ‘\n’;
return 0;
}
Project Euler Problem 12
Posted on January 19, 2012 by Sameer
Problem 12
Language:C
#include “stdafx.h”
#include “stdio.h”
#include “conio.h”
#include “math.h”
long int divisor_count(long int x)
{
long int count =0 ;
// typecast x to long double for calculating sq root and then typecast it again to increment the counter.
for (long int i=2; i< int(sqrt(long double(x))); i++)
{
if ( x % i == 0)
{
if (i != int(sqrt(long double(x))))
{
count += 2;
}
else count += 1;
}
}
return count;
}
void main()
{
long int i = 1, answer;
while (i>=1)
{
long int num = long int (0.5 * i * (i+1));
if ( divisor_count(num) >= 501)
{
answer = num;
break;
}
i++;
}
printf(“%li”,answer);
getch();
}
Project Euler Problem 11
Posted on January 17, 2012 by Sameer
Problem 11
#include “stdio.h”
#include “conio.h”
int mul(int one, int two, int three, int four)
{
int product = one*two*three*four;
return product;
}
void main()
{
int grid [20][20]={
{8, 2, 22, 97, 38, 15, 0, 40, 0, 75, 4, 5, 7, 78, 52, 12, 50, 77, 91, 8},
{49, 49, 99, 40, 17, 81, 18, 57, 60, 87, 17, 40, 98, 43, 69, 48, 4, 56, 62, 0},
{81, 49, 31, 73, 55, 79, 14, 29, 93, 71, 40, 67, 53, 88, 30, 3, 49, 13, 36, 65},
{52, 70, 95, 23, 4, 60, 11, 42, 69, 24, 68, 56, 1, 32, 56, 71, 37, 2, 36, 91},
{22, 31, 16, 71, 51, 67, 63, 89, 41, 92, 36, 54, 22, 40, 40, 28, 66, 33, 13, 80},
{24, 47, 32, 60, 99, 3, 45, 2, 44, 75, 33, 53, 78, 36, 84, 20, 35, 17, 12, 50},
{32, 98, 81, 28, 64, 23, 67, 10, 26, 38, 40, 67, 59, 54, 70, 66, 18, 38, 64, 70},
{67, 26, 20, 68, 2, 62, 12, 20, 95, 63, 94, 39, 63, 8, 40, 91, 66, 49, 94, 21},
{24, 55, 58, 5, 66, 73, 99, 26, 97, 17, 78, 78, 96, 83, 14, 88, 34, 89, 63, 72},
{21, 36, 23, 9, 75, 0, 76, 44, 20, 45, 35, 14, 0, 61, 33, 97, 34, 31, 33, 95},
{78, 17, 53, 28, 22, 75, 31, 67, 15, 94, 3, 80, 4, 62, 16, 14, 9, 53, 56, 92},
{16, 39, 5, 42, 96, 35, 31, 47, 55, 58, 88, 24, 0, 17, 54, 24, 36, 29, 85, 57},
{86, 56, 0, 48, 35, 71, 89, 7, 5, 44, 44, 37, 44, 60, 21, 58, 51, 54, 17, 58},
{19, 80, 81, 68, 5, 94, 47, 69, 28, 73, 92, 13, 86, 52, 17, 77, 4, 89, 55, 40},
{4, 52, 8, 83, 97, 35, 99, 16, 7, 97, 57, 32, 16, 26, 26, 79, 33, 27, 98, 66},
{88, 36, 68, 87, 57, 62, 20, 72, 3, 46, 33, 67, 46, 55, 12, 32, 63, 93, 53, 69},
{4, 42, 16, 73, 38, 25, 39, 11, 24, 94, 72, 18, 8, 46, 29, 32, 40, 62, 76, 36},
{20, 69, 36, 41, 72, 30, 23, 88, 34, 62, 99, 69, 82, 67, 59, 85, 74, 4, 36, 16},
{20, 73, 35, 29, 78, 31, 90, 1, 74, 31, 49, 71, 48, 86, 81, 16, 23, 57, 5, 54},
{1, 70, 54, 71, 83, 51, 54, 69, 16, 92, 33, 48, 61, 43, 52, 1, 89, 19, 67, 48}
};
int max=0,product=0;
//row
for (int i=0; i<20; i++)
{
for(int j=0;j<17;j++)
{
printf(“\n%d %d %d %d”,grid[i][j],grid[i][j+1],grid[i][j+2],grid[i][j+3] );
product = mul(grid[i][j],grid[i][j+1],grid[i][j+2],grid[i][j+3]);
max=(max>product)?max:product;
printf(“\n Maxproduct here is %d”,max);
}
}
//col
for (int i=0; i<17; i++)
{
for(int j=0;j<20;j++)
{
printf(“\n%d %d %d %d”,grid[i][j],grid[i+1][j],grid[i+2][j],grid[i+3][j] );
//row
product = mul(grid[i][j],grid[i+1][j],grid[i+2][j],grid[i+3][j]);
max=(max>product)?max:product;
printf(“\n Maxproduct here is %d”,max);
}
}
//right diagonal
for (int i=0; i<17; i++)
{
for(int j=0;j<17;j++)
{
printf(“\n%d %d %d %d”,grid[i][j],grid[i+1][j+1],grid[i+2][j+2],grid[i+3][j+3] );
//row
product = mul(grid[i][j],grid[i+1][j+1],grid[i+2][j+2],grid[i+3][j+3]);
max=(max>product)?max:product;
printf(“\n Maxproduct here is %d”,max);
}
}
//left diagonal
for (int i=0; i<17; i++)
{
for(int j=0;j<17;j++)
{
printf(“\n%d %d %d %d”,grid[i][j+3],grid[i+1][j+2],grid[i+2][j+1],grid[i+3][j] );
product = mul(grid[i][j+3],grid[i+1][j+2],grid[i+2][j+1],grid[i+3][j]);
max=(max>product)?max:product;
printf(“\n Maxproduct here is %d”,max);
}
}
printf(“\n Final Max is %d”,max);
getch();
}
Following link was helpful:
http://johnnycoder.com/blog/page/2/
No comments:
Post a Comment