-
06-26-2013, 07:20 PM #61
Re: Project Euler
For the conversion of double to int, it's probably this part:
Code:int limit = ceil(sqrt(num));
You need this:
Code:int limit = (int)ceil(sqrt(num));
Code:int limit = (int)sqrt(num);
Code:if(num%i==0 & findIfPrime(num/i)){return num/i;} if(num%i==0 & findIfPrime(i)){return i;}
-
Ad Bot
- Beep.
-
06-26-2013, 11:15 PM #62
Re: Project Euler
@Chikanman, to avoid telling you the answer you have an infinite loop in your findHighestPrimeFactor() function:
Code:for(int i = max; i >= 2; i++){ if(num%i==0 & findIfPrime(i)){return i;} }
(Ace gave you a hint above)
-
06-27-2013, 12:14 AM #63
Re: Project Euler
I wasn't looking there because I was only responding to the erorrs/warnings he was getting, but that is a 2 char replacement fix.
-
06-27-2013, 02:02 AM #64
- Join Date
- Dec 2012
- Location
- UK
- Posts
- 75
Re: Project Euler
-
06-27-2013, 02:39 AM #65
Re: Project Euler
Change the for loop to a --
Code:for(int i = max; i >= 2; i--){ if(num%i==0 && findIfPrime(i)){return i;} }
-
06-27-2013, 02:46 AM #66
- Join Date
- Dec 2012
- Location
- UK
- Posts
- 75
Re: Project Euler
That's one of the problems I fixed, and it seems to work up till about 10 digits. After that I get some really weird answers and then it goes negative.
-
06-27-2013, 02:57 AM #67
Re: Project Euler
Do you know what is going on behind the scenes that causes this? (Integer overflow - Wikipedia, the free encyclopedia)
-
06-27-2013, 03:39 AM #68
Re: Project Euler
I'm not sure how much longer I will be awake so I will advance onto the next topic and that is:
How do we store very large numbers?
The first thing we need to identify is how large is our number?
Thinking in terms of bits here(binary) we can arrive at the following equation:
The max number stored per bit(n) is: 2^n - 1
4 bits: 15
8 bits: 255
16 bits: 65,535
32 bits: 4,294,967,295
64 bits: 18,446,744,073,709,551,615
This leads us to our next point which is: Do we need signed numbers? (Do we need negative values?)
If yes we still can store the same number of numbers but we have to assign a range to them:
4 bits: -8 to 7
8 bits: -128 to 127
16 bits: –32,768 to 32,767
32 bits: –2,147,483,648 to 2,147,483,647
64 bits: –9,223,372,036,854,775,808 to 9,223,372,036,854,775,807
Note: by default most languages assume you are using signed numbers unless you specify.
In the case of c++ just add unsigned prior to the variable declaration like so:
unsigned int x;
Taking everything listed above into account lets look at the problem once again:
We need to store: 600,851,475,143
Comparing this to the charts above it is quite clear that we need to use a 64 bit value regardless of if we decide to be signed or unsigned.
There are a few options to accomplish this easily in c++ and that is by changing the data type from long(32 bit) to something larger like:
int64_t(64bits) or long long(32-64bits).
In this case it is more memory efficient to use long long as the number isn't a full 64 bits.
Simply put: change all your integer declarations to of type: long long and you should be set.
If you need to store even larger numbers than those described above you have to do some interesting things like creating your own data types and overloading basic operators... It's great fun
Anyway, did I make that clear? Sorry if it was a little over-kill, I don't know your experience so it's better to be safe than sorry.
Here is one solutions using your code:
Read More:
Note: the findIfPrime function doesn't really need to support long long as it only ever sees the sqrt() of a long long -> sqrt(2^64) = 2^32Last edited by Laxer; 06-27-2013 at 03:44 AM.
-
06-27-2013, 05:01 AM #69
- Join Date
- Dec 2012
- Location
- UK
- Posts
- 75
Re: Project Euler
Stephen and I are currently in Computing and we just finished Euler 5. I did the C++ and he converted it into VB, since our school apparently hates .cpp files and refuses to compile them in any way...
C++:
Code:#include "stdafx.h" #include <iostream> #include <cmath> using namespace std; bool isDivisible(long num){ for(int i=11;i<=20;i++){ if(num%i != 0){return false;} } return true; } int main(){ long test = 2520; while(!isDivisible(test)){test+=20;} cout << test << endl; cin.get(); cin.get(); return 0; }
Code:Module Module1 Private Function checker(ByVal num As Long) As Boolean For i As Integer = 11 To 20 Step 1 If num Mod i <> 0 Then Return False Next Return True End Function Sub Main() Dim test As Long = 2520 Do While Not checker(test) test = test + 20 Loop Console.WriteLine(test) Console.ReadLine() End Sub End Module
-
06-27-2013, 01:36 PM #70
Re: Project Euler
@Chikanman, throw this on a flashdrive: Codeblocks
Its a great portable IDE and comes with mingw so you should be able to compile anywhere.
I generally use that on the go and visual c when I am at home, they use different compilers but it hasn't given me any weird errorsLast edited by Laxer; 06-27-2013 at 02:28 PM.
-
06-27-2013, 04:14 PM #71
Re: Project Euler
#7 in VB.NET
Code:Option Strict On Module Module1 Private Function isPrime(ByVal num As Long) As Boolean Dim limit As Long = CLng(num / 2) If num = 2 Then Return True If num Mod 2 = 0 Then Return False For i As Long = 3 To limit Step 2 If num Mod i = 0 Then Return False Next Return True End Function Private Function primeCounter(ByVal n As Long) As Long Dim currentPrime As Integer = 1 If n = 1 Then Return 2 For i As Integer = 3 To 999999999 Step 2 If isPrime(i) Then currentPrime += 1 If currentPrime = n Then Return i Next Return 0 End Function Sub Main() Dim input As Long Console.WriteLine("Please enter the number prime you want to find. E.G. If you want to find the 6th prime number, type 6") Console.WriteLine(ControlChars.NewLine) input = CLng(Console.ReadLine()) Console.WriteLine(ControlChars.NewLine) Console.WriteLine("The {0}th prime is {1}", input, primeCounter(input)) Console.ReadLine() End Sub End Module
-
06-27-2013, 05:46 PM #72
- Join Date
- Dec 2012
- Location
- UK
- Posts
- 75
Re: Project Euler
You forgot to mention the bit where we got Sysnative filtered in school...
Anyway, have some lovely C++ for task 3 (which I finally completed):
Code:#include "stdafx.h" #include <iostream> #include <cmath> using namespace std; bool findIfPrime(long long num) { if(num==2){return true;} if((num==1)||(num%2==0)){return false;} int limit = (int)sqrt(num); for(int i=3;i<=limit;i+=2){ if(num%i==0){return false;} } return true; } long long findHighestPrimeFactor(long long num) { if(findIfPrime(num)){return num;} int max = (int)sqrt(num); for(int i = 2; i <= max; i++){ if(num%(num/i)==0 && findIfPrime(num/i)){return num/i;} } for(int i = max; i >= 2; i--){ if(num%i==0 && findIfPrime(i)){return i;} } return 0; } int main() { long long test = 600851475143; cout << findHighestPrimeFactor(test); cin.get(); cin.get(); return 1; }
-
06-27-2013, 09:22 PM #73
Re: Project Euler
Congrats, you guys have inspired me
I picked a problem at random: 67
Consequently by solving this one I also solved 18 so I just combined the problems.
I was going to solve this using my preferred language: PHP but, I don't have a local server set up right now so just went with c++.
I thought about solving this like it should be solved with a weighted graph and a maximum spanning tree/longest path using something similar to Dijkstra's/Primm's solution but... The data set is fairly small and I am lazy so I solved it with containers(std::vectors)
Code:#include <fstream> #include <iostream> #include <sstream> #include <ctime> #include <vector> using namespace std; vector<vector<int> > getData(string); void print(vector<vector<int> >&); //for debugging int maxPath(vector<vector<int> >); int main() { clock_t start = clock(); vector<vector<int> > p18 = getData("triangle2.txt"); cout << "Answer to 18: " << maxPath(p18) << " ("; cout << (double)(clock() - start)/CLOCKS_PER_SEC << " secs)\n"; start = clock(); vector<vector<int> > p67 = getData("triangle.txt"); cout << "Answer to 67: " << maxPath(p67) << " ("; cout << (double)(clock() - start)/CLOCKS_PER_SEC << " secs)\n"; return 0; } vector<vector<int> > getData(string file) { vector<vector<int> > tree; ifstream fin; fin.open(file); if(!fin) { cout << "File not found!" << endl; return tree; //returns an empty tree } string line; while (getline(fin,line)) { stringstream sin(line); vector<int> row; while (sin.good()) { int a; sin >> a; row.push_back(a); } tree.push_back(row); } return tree; } void print(vector<vector<int> > &tree) { for(auto j = tree.begin(); j!=tree.end();++j) { for(auto i = j->begin(); i!=j->end();++i) cout << *i << " "; cout << endl; } } int maxPath(vector<vector<int> > tree) { for(auto j = tree.rbegin()+1; j!=tree.rend();++j) for(int i = 0; i<j->size();i++) (*j)[i] += max((j-1)->at(i),(j-1)->at(i+1)); return tree[0][0]; }
Answers:
Read More:
Project attached if you really want a copy...Last edited by Laxer; 06-27-2013 at 09:26 PM.
-
06-27-2013, 11:20 PM #74
Re: Project Euler
@Laxer - Now try #61
That's the one I've been working on, but I'm still thinking on a good efficient way to do this. I'm thinking on creating and using some kind of boolean table for each starting and ending value in the cyclic sequence. Anyways here's what I got so far:
Code:// Project_Euler.cpp #include "stdafx.h" #include <Windows.h> #include <iostream> #include <fstream> #include <ctime> #include "EulerUtils.h" // #include "gmp-5.1.2\include\gmp.h" // #include "mapm-4.9.5a\m_apm.h" /* Summary - 61 */ // Find the sum of the only ordered set of six cyclic 4-digit // numbers for which each polygonal type: triangle, square, // pentagonal, hexagonal, heptagonal, and octagonal, is represented // by a different number in the set. #define N 6 #define P(n, i) POLYGON_##n = i enum POLYGON_NUMBER { P(NONE, 0), P(OCTAGONAL, 1), P(HEPTAGONAL, 2), P(HEXAGONAL, 3), P(PENTAGONAL, 4), P(TRIANGLE, 5), P(SQUARE, 6) }; typedef std::vector<int>::iterator vector_iter; typedef std::vector<int>::const_iterator cvector_iter; typedef std::vector<int>::reverse_iterator rev_vector_iter; typedef std::vector<int>::const_reverse_iterator crev_vector_iter; typedef std::map<POLYGON_NUMBER,std::vector<int>>::iterator map_iter; int getFirstTwo(int n) { return n / 100; } int getLastTwo(int n) { return n - (n / 100 * 100); } POLYGON_NUMBER getPolygonType(int n) { if (isOctaNum(n)) return POLYGON_OCTAGONAL; if (isHeptaNum(n)) return POLYGON_HEPTAGONAL; if (isHexaNum(n)) return POLYGON_HEXAGONAL; if (isPentaNum(n)) return POLYGON_PENTAGONAL; if (isTriNum(n)) return POLYGON_TRIANGLE; if (isSquareNum(n)) return POLYGON_SQUARE; return POLYGON_NONE; } int getCyclicMap(std::map<POLYGON_NUMBER,std::vector<int>>& cyclic_map, std::vector<int>& first_digits, std::vector<int>& last_digits, int min, int exclusiveMax) { int count=0; POLYGON_NUMBER poly_type; for (int i=min; i<exclusiveMax; (i+1)%1000==0?i+=11:i++) { if((poly_type=getPolygonType(i)) != POLYGON_NONE) { cyclic_map[poly_type].push_back(i); int d = getFirstTwo(i); if (std::find(first_digits.begin(), first_digits.end(), d) == first_digits.end()) first_digits.push_back(d); d = i - (d * 100); if (std::find(last_digits.begin(), last_digits.end(), d) == last_digits.end()) last_digits.push_back(d); count++; } } return count; } char* getEnumName(POLYGON_NUMBER poly_num) { switch(poly_num) { case POLYGON_OCTAGONAL: return "OCTAGONAL"; case POLYGON_HEPTAGONAL: return "HEPTAGONAL"; case POLYGON_HEXAGONAL: return "HEXAGONAL"; case POLYGON_PENTAGONAL: return "PENTAGONAL"; case POLYGON_TRIANGLE: return "TRIANGLE"; case POLYGON_SQUARE: return "SQUARE"; } return "NONE"; } void solve() { std::vector<int> first_digits; std::vector<int> last_digits; std::map<POLYGON_NUMBER,std::vector<int>> cyclic_map; { int map_count = getCyclicMap(cyclic_map, first_digits, last_digits, 1000, 10000); std::cout << "Valid Numbers Found: " << map_count << '\n'; std::cout << "Distinct Starting Digits Found: " << first_digits.size() << '\n'; std::cout << "Distinct Ending Digits Found: " << last_digits.size() << "\n\n"; for (int i=1;i<=N;i++) std::cout << getEnumName((POLYGON_NUMBER)i) << ": " << cyclic_map[(POLYGON_NUMBER)i].size() << '\n'; std::cout << std::endl; } // ------------------------------------------------------- // # Find similar numeric values that can be paired off // (using last 2 digits or the first 2 digits) // # NOTE: Only 1 number from each group can be used to make // the 6 polygonal type, cyclical series. // # The sum of this series is the answer. // ------------------------------------------------------- } int main() { clock_t t1(clock()); solve(); clock_t t2(clock()); clock_t result = t2 - t1; double secs = (double)result / CLOCKS_PER_SEC; std::cout << "Time: " << secs << " seconds (approx ~" << secs * 1000 << "ms : " << result << " ticks)"; std::cout << "..." << std::endl; FlashWindow(GetConsoleWindow(), true); getchar(); return 0; }
67 was an easy one though. :)Last edited by AceInfinity; 06-27-2013 at 11:24 PM.
-
06-27-2013, 11:44 PM #75
Re: Project Euler
Maybe if I get really bored
67 was straight forward which was awesome.
Looking at your code you are far... less lazy? Than I am... Any time I have to tweak around with iterators or odd types I just use auto and let the compiler figure things out for me
-
06-28-2013, 06:47 PM #76
Re: Project Euler
Sorry Ace, I didn't do #61 but...
Reading back through the thread I was intrigued by my post: Project Euler
and went to work on Euler problem 317:
I solved it first using pencil, paper and my TI but it requires something nuts like 15+ sig figs so had to do it with the computer again...
First thing lets find some easy points: X=0 (max height)
This is pretty basic newton mechanics
y = (vi^2-vf^2)/2a + yi
vf = 0 at the max point giving us:
y = 20^2/(2*9.81) + 100 =
Code:120.38735983690112...
First thing we need to find is flight time
dy = vyt+at^2/2
solving for t we get: |vy+sqrt(vy^2-2gdy)/g|
Note: vy = vsin(theta)
We can then solve for the distance:
X = vxt
Note: vx = vcos(theta)
Plugging t in we get:
X=vcos(theta)*|vsin(theta)+sqrt(vsin(theta)^2-2gdy)/g|
At this point you could simplify with trig but I am lazy
Plugging in our known values:
X=20cos(theta)*|20sin(theta)+sqrt(20sin(theta)^2-2*-9.81*100)/-9.81|
From the optimal angle calculation I did on my TI I know that the optimal angle is somewhere between 22.3 and 22.4 degrees but need more precision than that so I just brute forced it in C++:
Code:#include <iostream> #include <iomanip> #include <ctime> #include <cmath> using namespace std; #define PI 3.14159265 int main() { clock_t start = clock(); cout << setprecision(15) << fixed; long double high = 0; for(double i=22.3;i<=22.4;i+=0.000000001) { long double theta = i * PI / 180; long double temp, t; t = abs((20*sin(theta)+sqrt(pow(20*sin(theta),2)-(2*-9.81*100)))/-9.81); temp = 20*cos(theta)*t; if(temp>high) high=temp; } cout << high << endl; cout << (double)(clock() - start)/CLOCKS_PER_SEC << " secs)\n"; return 0; }
Code:99.083407789788918
Read More:
This gives us 3 points:Code:(0,120.38735983690112)(99.083407789788918,0)(-99.083407789788918,0)
Being the lazy individual I am I just asked WolframAlpha: parabola (0,120.38735983690112) (99.083407789788918,0)(-99.083407789788918,0)
This gave me the equation:Code:y = 120.38735983690112-0.01226250000000000*x^2
Doing so gives me: Integral from 0 to 120.38735983690112 of pi*(-(y-120.38735983690)/0.012262500000000)
After solving this we arrive at our answer:
Code:1856532.####275
Probably a more bruteforce method than most people took but, it's solved
-
06-28-2013, 09:58 PM #77
Re: Project Euler
You cheater, lol. :) Nice math though, that brings me back to my physics days, and graphing days in math, so I can understand this.
-
06-28-2013, 10:14 PM #78
Re: Project Euler
It's not like I didn't know how to do it just didn't want to do it... Using my resources is hardly considered cheating
I used wolfram quite frequently for my calc based physics class especially for the extra credit problems he would assign as my calculus background is somewhat limited as I took it almost 5 years ago.
-
06-29-2013, 08:49 PM #79
Re: Project Euler
I solved #61 finally...
Answer #61:
Code:// Project_Euler.cpp #include "stdafx.h" #include <Windows.h> #include <iostream> #include <ctime> #include "EulerUtils.h" // #include "gmp-5.1.2\include\gmp.h" // #include "mapm-4.9.5a\m_apm.h" /* Summary - 61 */ // Find the sum of the only ordered set of six cyclic 4-digit // numbers for which each polygonal type: triangle, square, // pentagonal, hexagonal, heptagonal, and octagonal, is represented // by a different number in the set. #define N 6 #define P(n, i) POLYGON_##n = i enum POLYGON_NUMBER { P(NONE, 0), P(OCTAGONAL, 1), P(HEPTAGONAL, 2), P(HEXAGONAL, 3), P(PENTAGONAL, 4), P(TRIANGLE, 5), P(SQUARE, 6) }; typedef std::map<POLYGON_NUMBER,std::map<int,int>> poly_cyclic_map; typedef std::map<int,int>::iterator map_iter; POLYGON_NUMBER getPolygonType(int n) { if (isOctaNum(n)) return POLYGON_OCTAGONAL; if (isHeptaNum(n)) return POLYGON_HEPTAGONAL; if (isHexaNum(n)) return POLYGON_HEXAGONAL; if (isPentaNum(n)) return POLYGON_PENTAGONAL; if (isTriNum(n)) return POLYGON_TRIANGLE; if (isSquareNum(n)) return POLYGON_SQUARE; return POLYGON_NONE; } int getCyclicMap(poly_cyclic_map& cyclic_map, int min, int exclusiveMax) { int count=0; POLYGON_NUMBER poly_type; for (int i=min; i<exclusiveMax; (i+1)%1000==0?i+=11:i++) { if((poly_type=getPolygonType(i)) != POLYGON_NONE) { int first = i / 100; cyclic_map[poly_type].insert(std::pair<int,int>(first, i - (first * 100))); count++; } } return count; } char* getEnumName(POLYGON_NUMBER poly_num) { switch(poly_num) { case POLYGON_OCTAGONAL: return "OCTAGONAL"; case POLYGON_HEPTAGONAL: return "HEPTAGONAL"; case POLYGON_HEXAGONAL: return "HEXAGONAL"; case POLYGON_PENTAGONAL: return "PENTAGONAL"; case POLYGON_TRIANGLE: return "TRIANGLE"; case POLYGON_SQUARE: return "SQUARE"; } return "NONE"; } bool findCyclicSet(POLYGON_NUMBER order[N], poly_cyclic_map& m, int* result) { for (map_iter it0 = m[order[0]].begin(); it0 != m[order[0]].end(); it0++) { for (map_iter it1 = m[order[1]].begin(); it1 != m[order[1]].end(); it1++) { if ((it0->first == it1->first && it0->second == it1->second) || it0->second != it1->first) continue; for (map_iter it2 = m[order[2]].begin(); it2 != m[order[2]].end(); it2++) { if ((it1->first == it2->first && it1->second == it2->second) || it1->second != it2->first) continue; for (map_iter it3 = m[order[3]].begin(); it3 != m[order[3]].end(); it3++) { if ((it2->first == it3->first && it2->second == it3->second) || it2->second != it3->first) continue; for (map_iter it4 = m[order[4]].begin(); it4 != m[order[4]].end(); it4++) { if ((it3->first == it4->first && it3->second == it4->second) || it3->second != it4->first) continue; for (map_iter it5 = m[order[5]].begin(); it5 != m[order[5]].end(); it5++) { if ((it4->first == it5->first && it4->second == it5->second) || it4->second != it5->first) continue; if (it5->second == it0->first) { result[0] = (it0->first * 100) + it0->second; result[1] = (it1->first * 100) + it1->second; result[2] = (it2->first * 100) + it2->second; result[3] = (it3->first * 100) + it3->second; result[4] = (it4->first * 100) + it4->second; result[5] = (it5->first * 100) + it5->second; return true; } } } } } } } return false; } void solve() { poly_cyclic_map cyclic_map; { int map_count = getCyclicMap(cyclic_map, 1000, 10000); std::cout << "Valid Numbers Found: " << map_count << '\n'; for (int i=1;i<=N;i++) std::cout << getEnumName((POLYGON_NUMBER)i) << ": " << cyclic_map[(POLYGON_NUMBER)i].size() << '\n'; std::cout << std::endl; } POLYGON_NUMBER order[N] = { POLYGON_OCTAGONAL, POLYGON_HEPTAGONAL, POLYGON_HEXAGONAL, POLYGON_PENTAGONAL, POLYGON_TRIANGLE, POLYGON_SQUARE }; int* result = new int[N]; do { if (findCyclicSet(order, cyclic_map, result)) break; } while (std::next_permutation(order, order+N)); int sum = result[0] + result[1] + result[2] + result[3] + result[4] + result[5]; std::cout << "Series: " << result[0] << ", " << result[1] << ", " << result[2] << ", " << result[3] << ", " << result[4] << ", " << result[5] << std::endl; std::cout << "Answer: " << sum << std::endl; delete[] result; } int main() { clock_t t1(clock()); solve(); clock_t t2(clock()); clock_t result = t2 - t1; double secs = (double)result / CLOCKS_PER_SEC; std::cout << "Time: " << secs << " seconds (approx ~" << secs * 1000 << "ms : " << result << " ticks)"; std::cout << "..." << std::endl; FlashWindow(GetConsoleWindow(), true); getchar(); return 0; }
From EulerUtils:
Code:bool isTriNum(int n) { if (n == 1) return true; int x = 1; for (int i = 1; i <= n; i += x) { if (i == n) return true; x++; } return false; } bool isSquareNum(int n) { int product; for (int i = 1; (product = i * i) <= n; i++) { if (product == n) return true; } return false; } bool isPentaNum(int n) { int x = 1; for (int i = 1; i <= n; i += x) { if (i == n) return true; x += 3; } return false; } bool isHexaNum(int n) { int x = 1; for (int i = 1; i <= n; i += x) { if (i == n) return true; x += 4; } return false; } bool isHeptaNum(int n) { int x = 1; for (int i = 1; i <= n; i += x) { if (i == n) return true; x += 5; } return false; } bool isOctaNum(int n) { int x = 1; for (int i = 1; i <= n; i += x) { if (i == n) return true; x += 6; } return false; }
-
06-29-2013, 11:50 PM #80
Re: Project Euler
Good work Ace, that one looked ugly >.<
Similar Threads
-
[Project] StringCrypt - Work in Progress
By AceInfinity in forum ProgrammingReplies: 1Last Post: 10-01-2012, 11:38 PM -
Project Ideas
By HonorGamer in forum ProgrammingReplies: 15Last Post: 07-29-2012, 05:08 PM -
VB Project... To help me learn
By GZ in forum ProgrammingReplies: 7Last Post: 06-02-2012, 10:57 PM