Page 4 of 5 First 12345 Last
  1. #61
    AceInfinity's Avatar
    Join Date
    Feb 2012
    Location
    Canada
    Posts
    1,721

    Re: Project Euler

    For the conversion of double to int, it's probably this part:
    Code:
    int limit = ceil(sqrt(num));
    ceil returns a double I believe: ceil - C++ Reference

    You need this:
    Code:
    int limit = (int)ceil(sqrt(num));
    Although ceil isn't really required here if you want an int. Just casting to an int will round for you:
    Code:
    int limit = (int)sqrt(num);
    Also, & is not what you think it is...
    Code:
    if(num%i==0 & findIfPrime(num/i)){return num/i;}
    if(num%i==0 & findIfPrime(i)){return i;}
    For these lines, replace & with &&. && is a logical operator, and & is a bitwise operator: Operators - C++ Documentation
    \n\n

    Automation Programmer
    Development Site: aceinfinity.net


    • Ad Bot

      advertising
      Beep.

        
       

  2. #62
    Laxer's Avatar
    Join Date
    Feb 2012
    Location
    Portland, OR
    Posts
    3,848
    • specs System Specs
      • Motherboard:
        GIGABYTE GA-Z97MX
      • CPU:
        Intel 4690K @ 4.6Ghz
      • Memory:
        Corsair Vengeance Pro 16GB @ 2666Mhz
      • Graphics:
        2x Sapphire 7970s
      • Hard Drives:
        2x Corsair Force 3GT 120GB (RAID 0) + 2x Western Digital Red 3TB (RAID 1)
      • Disk Drives:
        LG Black 10X Blu-ray Burner
      • Power Supply:
        CORSAIR 950HX
      • Case:
        Corsair 350D
      • Cooling:
        Corsair H100i
      • Display:
        3 x 22" Samsung 1080p Displays
      • Operating System:
        Windows 8 Pro x64

    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;}
        }
    If you need help resolving it let us know

    (Ace gave you a hint above)
    Chikanman says thanks for this.

  3. #63
    AceInfinity's Avatar
    Join Date
    Feb 2012
    Location
    Canada
    Posts
    1,721

    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.
    \n\n

    Automation Programmer
    Development Site: aceinfinity.net

  4. #64

    Join Date
    Dec 2012
    Location
    UK
    Posts
    75

    Re: Project Euler

    Quote Originally Posted by Laxer View Post
    you have an infinite loop in your findHighestPrimeFactor() function
    Man, I'm an idiot. I even put it there and forgot to change it back...

    EDIT: I've fixed all of that, but it's now returning -443946297? Am I missing something here?

    Also, thanks for all your help so far. I'm not exactly an experienced coder so it's all really helpful.

  5. #65
    Laxer's Avatar
    Join Date
    Feb 2012
    Location
    Portland, OR
    Posts
    3,848
    • specs System Specs
      • Motherboard:
        GIGABYTE GA-Z97MX
      • CPU:
        Intel 4690K @ 4.6Ghz
      • Memory:
        Corsair Vengeance Pro 16GB @ 2666Mhz
      • Graphics:
        2x Sapphire 7970s
      • Hard Drives:
        2x Corsair Force 3GT 120GB (RAID 0) + 2x Western Digital Red 3TB (RAID 1)
      • Disk Drives:
        LG Black 10X Blu-ray Burner
      • Power Supply:
        CORSAIR 950HX
      • Case:
        Corsair 350D
      • Cooling:
        Corsair H100i
      • Display:
        3 x 22" Samsung 1080p Displays
      • Operating System:
        Windows 8 Pro x64

    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;}
        }
    I think that should work, up next is to allow it to work with large numbers

  6. #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.

  7. #67
    Laxer's Avatar
    Join Date
    Feb 2012
    Location
    Portland, OR
    Posts
    3,848
    • specs System Specs
      • Motherboard:
        GIGABYTE GA-Z97MX
      • CPU:
        Intel 4690K @ 4.6Ghz
      • Memory:
        Corsair Vengeance Pro 16GB @ 2666Mhz
      • Graphics:
        2x Sapphire 7970s
      • Hard Drives:
        2x Corsair Force 3GT 120GB (RAID 0) + 2x Western Digital Red 3TB (RAID 1)
      • Disk Drives:
        LG Black 10X Blu-ray Burner
      • Power Supply:
        CORSAIR 950HX
      • Case:
        Corsair 350D
      • Cooling:
        Corsair H100i
      • Display:
        3 x 22" Samsung 1080p Displays
      • Operating System:
        Windows 8 Pro x64

    Re: Project Euler

    Do you know what is going on behind the scenes that causes this? (Integer overflow - Wikipedia, the free encyclopedia)

  8. #68
    Laxer's Avatar
    Join Date
    Feb 2012
    Location
    Portland, OR
    Posts
    3,848
    • specs System Specs
      • Motherboard:
        GIGABYTE GA-Z97MX
      • CPU:
        Intel 4690K @ 4.6Ghz
      • Memory:
        Corsair Vengeance Pro 16GB @ 2666Mhz
      • Graphics:
        2x Sapphire 7970s
      • Hard Drives:
        2x Corsair Force 3GT 120GB (RAID 0) + 2x Western Digital Red 3TB (RAID 1)
      • Disk Drives:
        LG Black 10X Blu-ray Burner
      • Power Supply:
        CORSAIR 950HX
      • Case:
        Corsair 350D
      • Cooling:
        Corsair H100i
      • Display:
        3 x 22" Samsung 1080p Displays
      • Operating System:
        Windows 8 Pro x64

    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^32
    Last edited by Laxer; 06-27-2013 at 03:44 AM.

  9. #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;
    }
    VB.NET:
    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

  10. #70
    Laxer's Avatar
    Join Date
    Feb 2012
    Location
    Portland, OR
    Posts
    3,848
    • specs System Specs
      • Motherboard:
        GIGABYTE GA-Z97MX
      • CPU:
        Intel 4690K @ 4.6Ghz
      • Memory:
        Corsair Vengeance Pro 16GB @ 2666Mhz
      • Graphics:
        2x Sapphire 7970s
      • Hard Drives:
        2x Corsair Force 3GT 120GB (RAID 0) + 2x Western Digital Red 3TB (RAID 1)
      • Disk Drives:
        LG Black 10X Blu-ray Burner
      • Power Supply:
        CORSAIR 950HX
      • Case:
        Corsair 350D
      • Cooling:
        Corsair H100i
      • Display:
        3 x 22&quot; Samsung 1080p Displays
      • Operating System:
        Windows 8 Pro x64

    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 errors
    Last edited by Laxer; 06-27-2013 at 02:28 PM.

  11. #71
    Tekno Venus's Avatar
    Join Date
    Jul 2012
    Location
    UK
    Age
    20
    Posts
    5,873
    • specs System Specs
      • Manufacturer:
        Custom Built
      • Motherboard:
        ASUS Z170I ITX
      • CPU:
        Intel Core i7 6700K
      • Memory:
        16GB DDR4
      • Hard Drives:
        500GB Samsung 850 EVO, 2TB Seagate HDD
      • Power Supply:
        450W Corsair SFX
      • Case:
        Silverstone SG13 ITX
      • Cooling:
        Corsair H60i
      • Display:
        Dell U2715H - 2160x1440 27 inch
      • Operating System:
        Windows 10 Pro x64

    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


  12. #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;
    }

  13. #73
    Laxer's Avatar
    Join Date
    Feb 2012
    Location
    Portland, OR
    Posts
    3,848
    • specs System Specs
      • Motherboard:
        GIGABYTE GA-Z97MX
      • CPU:
        Intel 4690K @ 4.6Ghz
      • Memory:
        Corsair Vengeance Pro 16GB @ 2666Mhz
      • Graphics:
        2x Sapphire 7970s
      • Hard Drives:
        2x Corsair Force 3GT 120GB (RAID 0) + 2x Western Digital Red 3TB (RAID 1)
      • Disk Drives:
        LG Black 10X Blu-ray Burner
      • Power Supply:
        CORSAIR 950HX
      • Case:
        Corsair 350D
      • Cooling:
        Corsair H100i
      • Display:
        3 x 22&quot; Samsung 1080p Displays
      • Operating System:
        Windows 8 Pro x64

    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];
    }
    I forgot that you can navigate vectors like you do arrays so half way through I switched from iterators to a more user friendly array index and was too lazy to go back

    Answers:
    Read More:


    Project attached if you really want a copy...
    Attached Files Attached Files
    Last edited by Laxer; 06-27-2013 at 09:26 PM.

  14. #74
    AceInfinity's Avatar
    Join Date
    Feb 2012
    Location
    Canada
    Posts
    1,721

    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;
    }
    The rest is in the EulerUtils source file, but by the names of the functions it is pretty straightforward. It's been a collection of functions I've created myself in that file so far. I was up late on this one, I came up with a slow solution, but I wanted to improve this so I'm re-writing this one. When finished, I'll provide the full code.

    67 was an easy one though. :)
    Last edited by AceInfinity; 06-27-2013 at 11:24 PM.
    \n\n

    Automation Programmer
    Development Site: aceinfinity.net

  15. #75
    Laxer's Avatar
    Join Date
    Feb 2012
    Location
    Portland, OR
    Posts
    3,848
    • specs System Specs
      • Motherboard:
        GIGABYTE GA-Z97MX
      • CPU:
        Intel 4690K @ 4.6Ghz
      • Memory:
        Corsair Vengeance Pro 16GB @ 2666Mhz
      • Graphics:
        2x Sapphire 7970s
      • Hard Drives:
        2x Corsair Force 3GT 120GB (RAID 0) + 2x Western Digital Red 3TB (RAID 1)
      • Disk Drives:
        LG Black 10X Blu-ray Burner
      • Power Supply:
        CORSAIR 950HX
      • Case:
        Corsair 350D
      • Cooling:
        Corsair H100i
      • Display:
        3 x 22&quot; Samsung 1080p Displays
      • Operating System:
        Windows 8 Pro x64

    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

  16. #76
    Laxer's Avatar
    Join Date
    Feb 2012
    Location
    Portland, OR
    Posts
    3,848
    • specs System Specs
      • Motherboard:
        GIGABYTE GA-Z97MX
      • CPU:
        Intel 4690K @ 4.6Ghz
      • Memory:
        Corsair Vengeance Pro 16GB @ 2666Mhz
      • Graphics:
        2x Sapphire 7970s
      • Hard Drives:
        2x Corsair Force 3GT 120GB (RAID 0) + 2x Western Digital Red 3TB (RAID 1)
      • Disk Drives:
        LG Black 10X Blu-ray Burner
      • Power Supply:
        CORSAIR 950HX
      • Case:
        Corsair 350D
      • Cooling:
        Corsair H100i
      • Display:
        3 x 22&quot; Samsung 1080p Displays
      • Operating System:
        Windows 8 Pro x64

    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...
    Now to solve for the max X is a little more tricky:

    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;
    }
    Doing so yields a max X of:
    Code:
    99.083407789788918
    Screenshot of output:
    Read More:


    This gives us 3 points:
    Code:
    (0,120.38735983690112)(99.083407789788918,0)(-99.083407789788918,0)
    We know these points all lie on a parabola so we can solve for the curve. Seeing as my TI once again let me down do to lack of precision I was left with my computer.

    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
    Now I need to solve this equation for X so I can integrate it around the Y-axis using the shell method

    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
    Note: numbers removed(#) so you can't just put in the answer
    Probably a more bruteforce method than most people took but, it's solved
    AceInfinity says thanks for this.

  17. #77
    AceInfinity's Avatar
    Join Date
    Feb 2012
    Location
    Canada
    Posts
    1,721

    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.
    \n\n

    Automation Programmer
    Development Site: aceinfinity.net

  18. #78
    Laxer's Avatar
    Join Date
    Feb 2012
    Location
    Portland, OR
    Posts
    3,848
    • specs System Specs
      • Motherboard:
        GIGABYTE GA-Z97MX
      • CPU:
        Intel 4690K @ 4.6Ghz
      • Memory:
        Corsair Vengeance Pro 16GB @ 2666Mhz
      • Graphics:
        2x Sapphire 7970s
      • Hard Drives:
        2x Corsair Force 3GT 120GB (RAID 0) + 2x Western Digital Red 3TB (RAID 1)
      • Disk Drives:
        LG Black 10X Blu-ray Burner
      • Power Supply:
        CORSAIR 950HX
      • Case:
        Corsair 350D
      • Cooling:
        Corsair H100i
      • Display:
        3 x 22&quot; Samsung 1080p Displays
      • Operating System:
        Windows 8 Pro x64

    Re: Project Euler

    Quote Originally Posted by AceInfinity View Post
    You cheater, lol. :) Nice math though, that brings me back to my physics days, and graphing days in math, so I can understand this.
    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.

  19. #79
    AceInfinity's Avatar
    Join Date
    Feb 2012
    Location
    Canada
    Posts
    1,721

    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;
    }
    For that ugly nest-festation of a looping strategy, it still runs in under 1 second on my machine. Keep in mind I'm also outputting lots of junk data just for added effect and information I suppose... So a few ms could be spared.

    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;
    }
    \n\n

    Automation Programmer
    Development Site: aceinfinity.net

  20. #80
    Laxer's Avatar
    Join Date
    Feb 2012
    Location
    Portland, OR
    Posts
    3,848
    • specs System Specs
      • Motherboard:
        GIGABYTE GA-Z97MX
      • CPU:
        Intel 4690K @ 4.6Ghz
      • Memory:
        Corsair Vengeance Pro 16GB @ 2666Mhz
      • Graphics:
        2x Sapphire 7970s
      • Hard Drives:
        2x Corsair Force 3GT 120GB (RAID 0) + 2x Western Digital Red 3TB (RAID 1)
      • Disk Drives:
        LG Black 10X Blu-ray Burner
      • Power Supply:
        CORSAIR 950HX
      • Case:
        Corsair 350D
      • Cooling:
        Corsair H100i
      • Display:
        3 x 22&quot; Samsung 1080p Displays
      • Operating System:
        Windows 8 Pro x64

    Re: Project Euler

    Good work Ace, that one looked ugly >.<
    AceInfinity says thanks for this.

Page 4 of 5 First 12345 Last

Similar Threads

  1. [Project] StringCrypt - Work in Progress
    By AceInfinity in forum Programming
    Replies: 1
    Last Post: 10-01-2012, 11:38 PM
  2. Project Ideas
    By HonorGamer in forum Programming
    Replies: 15
    Last Post: 07-29-2012, 05:08 PM
  3. VB Project... To help me learn
    By GZ in forum Programming
    Replies: 7
    Last Post: 06-02-2012, 10:57 PM

Log in

Log in