Overclock.net › Forums › Software, Programming and Coding › Coding and Programming › Project Euler Discussion
New Posts  All Forums:Forum Nav:

Project Euler Discussion

post #1 of 15
Thread Starter 
Quote:
Originally Posted by projecteuler.net/about 
What is Project Euler?

Project Euler is a series of challenging mathematical/computer programming problems that will require more than just mathematical insights to solve. Although mathematics will help you arrive at elegant and efficient methods, the use of a computer and programming skills will be required to solve most problems.

The motivation for starting Project Euler, and its continuation, is to provide a platform for the inquiring mind to delve into unfamiliar areas and learn new concepts in a fun and recreational context.

The intent of this thread is to be a platform for OCN users to discuss algorithms, logic, and mathematical theory for solving Project Euler problems. Additionally, I encourage anyone with a particularly elegant or quick solution to share.

If you're unfamiliar with Project Euler, please follow the URL from the above quote. Essentially, it is a collection of math problems that you are challenged to solve with your computer. The Project Euler web site tracks your progress and will award achievement-like awards when appropriate.

Introduce yourself

If enough users take an interest in this thread, maybe it can be a club? If you are interested in this idea, please introduce yourself here with the following information:
  • Profile image
  • Language/utility of choice
  • Friend key (optional)

For example:

Language: Python 2.6 and Python 3.3
Friend key: 95121290449814_e7a159893feb86066de5c1f6b0bad8b0


The profile image can be obtained by:
  1. Log into projecteuler.net
  2. Click the "Account" button at the top of the page
  3. You will see your image with its URL under it at the top-right of the page

The friend key can be obtained by:
  1. Log into projecteuler.net
  2. Click the "Friends" button at the top of the page
  3. Copy the text in the box by "My friend key:"
  4. If there is no key in the box, click "Generate New Key"

Also, if you will be posting code please use the CODE and SPOILER tags. This will ensure code readability and will prevent accidental spoilers for those still working the same problem.
Edited by Ferrari8608 - 5/22/13 at 8:17am
post #2 of 15
Great idea, I am also part of Project Euler but cannot figure out a solution to most of the problems. This will be a good place to come for math advice thumb.gif
Lightweight gamer
(11 items)
 
  
CPUMotherboardGraphicsRAM
AMD FX-8320 ASRock 960GM/U3S3 Sapphire Radeon HD 6670 Generic RAM from Ebay 
Hard DriveHard DriveHard DriveOS
Western Digital Caviar SE WD1600 Seagate Barracuda 7200.9 OCZ Vector Windows 7 Professional Edition x64 
PowerCaseMouse
Rosewill 500-watt PSU Rosewill REDBONE Logitech M215 Cordless Mouse 
  hide details  
Reply
Lightweight gamer
(11 items)
 
  
CPUMotherboardGraphicsRAM
AMD FX-8320 ASRock 960GM/U3S3 Sapphire Radeon HD 6670 Generic RAM from Ebay 
Hard DriveHard DriveHard DriveOS
Western Digital Caviar SE WD1600 Seagate Barracuda 7200.9 OCZ Vector Windows 7 Professional Edition x64 
PowerCaseMouse
Rosewill 500-watt PSU Rosewill REDBONE Logitech M215 Cordless Mouse 
  hide details  
Reply
post #3 of 15

I'm not necessarily up for solving all the problems from Project Euler, I'm certainly up for intelligent discussion about said topics.

post #4 of 15
This seems like a fun way of challenging myself whenever I'm a little bored. I've been looking for something like this, in fact I wish I'd heard of it years ago. I'll be posting here once I get started on one or more of these.
I took some abstract algebra back in university. It wasn't fun at the time, but I turned out to be not too bad at it. Now I finally have a use for it!


Language: C#, Java,
Friend Key: 57670709480090_cc05ee82ea63e81eab16eb7083b77bb9
Edited by wedge - 5/21/13 at 8:55pm
Death Star
(21 items)
 
Darksaber
(11 items)
 
 
CPUMotherboardGraphicsRAM
Athlon II x2 245 Asus M3A78 Radeon HD6570 1GB Mushkin Silverline 2GB DDR2  
Hard DriveOptical DriveOSMonitor
OCZ Vertex 2 120GB Samsung Blu-Ray Windows 7 Samsung 46" DLP 
PowerCaseOther
Silverstone Strider Essentials 400W Silverstone Milo ML03B Hauppage WinTV 1250 
  hide details  
Reply
Death Star
(21 items)
 
Darksaber
(11 items)
 
 
CPUMotherboardGraphicsRAM
Athlon II x2 245 Asus M3A78 Radeon HD6570 1GB Mushkin Silverline 2GB DDR2  
Hard DriveOptical DriveOSMonitor
OCZ Vertex 2 120GB Samsung Blu-Ray Windows 7 Samsung 46" DLP 
PowerCaseOther
Silverstone Strider Essentials 400W Silverstone Milo ML03B Hauppage WinTV 1250 
  hide details  
Reply
post #5 of 15
Thread Starter 
Quote:
Originally Posted by Algorithm View Post

Great idea, I am also part of Project Euler but cannot figure out a solution to most of the problems. This will be a good place to come for math advice thumb.gif
Yeah, usually when I get stumped on a problem it's because I lack the necessary mathematical knowledge. The programming bit is easy.
Quote:
Originally Posted by hajile View Post

I'm not necessarily up for solving all the problems from Project Euler, I'm certainly up for intelligent discussion about said topics.
The more the merrier!
Quote:
Originally Posted by wedge View Post

This seems like a fun way of challenging myself whenever I'm a little bored. I've been looking for something like this, in fact I wish I'd heard of it years ago. I'll be posting here once I get started on one or more of these.
I took some abstract algebra back in university. It wasn't fun at the time, but I turned out to be not too bad at it. Now I finally have a use for it!


Language: C#, Java,
Friend Key: 57670709480090_cc05ee82ea63e81eab16eb7083b77bb9
You're gonna have a blast man. Once you solve the first couple problems, it can get quite addicting. I've been using the site to sharpen my number skills in programming since I already have practice in working with files and parsing text at work. It's definitely helping.
post #6 of 15
Quote:
Originally Posted by Ferrari8608 View Post

You're gonna have a blast man. Once you solve the first couple problems, it can get quite addicting. I've been using the site to sharpen my number skills in programming since I already have practice in working with files and parsing text at work. It's definitely helping.

Okay, working on my first problem, and I've run into a snag I have no idea how to solve, I need a little help. This is the one I'm attempting: http://projecteuler.net/problem=426

My solution for works. I can correctly solve the example sequence (2,2,2,1,2) my program reaches the final state [1,2,3]. It also reaches the correct final state given for (t0, t1, …, t10).
My problem is when trying to solve for (..., t10000000), the program just runs forever. So, even though my algorithm works, it's apparently inefficient.

This is a completely unknown territory for me. I've never worked with such large numbers and computations that performance/memory is an issue. I don't know how to debug this kind of problem.

If I let it run for a short time, and pause the app, it always pauses in the same place, and gives me a weird error: "Cannot evaluate expression because a thread is stopped at a point where garbage collection is impossible". So I'm guessing that is the point at which I need to fix up. That point is the method where I am determining the next available open box when moving a ball. This is what I'm doing:
Code:
while (i++ < box.Count-1)
            {
                if (box[i] == false)
                {
                    return i;
                }
            }
'i' is initially equal to the position of the ball being moved
box is a List of type bool
box.Count is the value that is throwing "Cannot evaluate expression because a thread is stopped at a point where garbage collection is impossible"

so it looks like the list eventually gets too big to handle, and some loops take so long to run that the GC tries to kick in and messes up the whole works.


I've been through my whole code several times, and I don't see anything obvious that I can 'optimize'. How do I even troubleshoot a problem like this?
Death Star
(21 items)
 
Darksaber
(11 items)
 
 
CPUMotherboardGraphicsRAM
Athlon II x2 245 Asus M3A78 Radeon HD6570 1GB Mushkin Silverline 2GB DDR2  
Hard DriveOptical DriveOSMonitor
OCZ Vertex 2 120GB Samsung Blu-Ray Windows 7 Samsung 46" DLP 
PowerCaseOther
Silverstone Strider Essentials 400W Silverstone Milo ML03B Hauppage WinTV 1250 
  hide details  
Reply
Death Star
(21 items)
 
Darksaber
(11 items)
 
 
CPUMotherboardGraphicsRAM
Athlon II x2 245 Asus M3A78 Radeon HD6570 1GB Mushkin Silverline 2GB DDR2  
Hard DriveOptical DriveOSMonitor
OCZ Vertex 2 120GB Samsung Blu-Ray Windows 7 Samsung 46" DLP 
PowerCaseOther
Silverstone Strider Essentials 400W Silverstone Milo ML03B Hauppage WinTV 1250 
  hide details  
Reply
post #7 of 15
Thread Starter 
When I debug, I start inserting print statements everywhere. I don't know what your language's equivalent of Python's print is, but just have your program tell you what it's doing as it's doing everything. Doing this, you may also notice a pattern of some kind that will help you optimize.

My programs always start out as a 'brute force' solution, and then I scour the internet for mathematical insight to help me formulate a more efficient algorithm (which I believe is what you're doing). Stack Overflow is always a great resource.

That looks like a fun problem though. I think I might try to whip up a Python solution today.

Also, Project Euler has its own forums. I try to keep out of there though as my solutions are almost always 100% my code, and I like to keep it that way. There's just too many spoilers there.
Edited by Ferrari8608 - 5/22/13 at 11:05am
post #8 of 15
Quote:
Originally Posted by Ferrari8608 View Post

As for optimizing, I'm sorry but I can't really help much with that. My programs always start out as a 'brute force' solution, and then I scour the internet for mathematical insight to help me formulate a more efficient algorithm (which I believe is what you're doing). Stack Overflow is always a great resource.
Dude, that is exactly what I'm doing smile.gif

C# is my language of choice. One issue is that this problem requires an open-ended array. Which C# does not support which makes this a real PITA. Which is why I had to use a List instead. But I know Lists have a much bigger performance penalty vs array's... Which I think is part of my problem

I won't give any ideas yet. But I've got two or three ideas for alternative solutions, which I believe should work. I'll give'em a try and let you know how it goes.

And yeah, I'm also trying to stay away from any potential spoilers. That would defeat the whole purpose.
Death Star
(21 items)
 
Darksaber
(11 items)
 
 
CPUMotherboardGraphicsRAM
Athlon II x2 245 Asus M3A78 Radeon HD6570 1GB Mushkin Silverline 2GB DDR2  
Hard DriveOptical DriveOSMonitor
OCZ Vertex 2 120GB Samsung Blu-Ray Windows 7 Samsung 46" DLP 
PowerCaseOther
Silverstone Strider Essentials 400W Silverstone Milo ML03B Hauppage WinTV 1250 
  hide details  
Reply
Death Star
(21 items)
 
Darksaber
(11 items)
 
 
CPUMotherboardGraphicsRAM
Athlon II x2 245 Asus M3A78 Radeon HD6570 1GB Mushkin Silverline 2GB DDR2  
Hard DriveOptical DriveOSMonitor
OCZ Vertex 2 120GB Samsung Blu-Ray Windows 7 Samsung 46" DLP 
PowerCaseOther
Silverstone Strider Essentials 400W Silverstone Milo ML03B Hauppage WinTV 1250 
  hide details  
Reply
post #9 of 15
Thread Starter 
I have a basic script wrote up, but it doesn't quite work yet. I always have issues when I try to use a while loop in Python.

I kinda figured an array (dictionary in Python) would be the way to go. I still haven't quite mastered iterating over them properly, but this is a good exercise for that.

Edit: Broken unfinished attempt at a solution (Click to show)
Code:
#!/usr/bin/env python

import sys

def final_state(boxes):
    (tcount,fcount) = 0,0
    state = []
    for box in sorted(boxes):
        if tcount > 0:
            if boxes[box] == True:
                tcount += 1
            else:
                state.append(tcount)
                tcount = 0
        elif fcount > 0:
            if boxes[box] == False:
                fcount += 1
            else:
                state.append(fcount)
                fcount = 0
        else:
            if boxes[box] == True:
                tcount += 1
            else:
                fcount += 1
    return state

def main():
    max_turns = int(sys.argv[1])
    boxes = { 1 : True,
              2 : True,
              3 : False,
              4 : False,
              5 : True,
              6 : True }
    turn = 1
    while turn <= max_turns:
#        print 'Turn:',turn
        for box in sorted(boxes):
            nextbox = box + 1
#            print 'Box:',box,'=',boxes[box]
            while boxes[box] == True:
                try:
                    if boxes[nextbox] == False:
                        (boxes[box],boxes[nextbox]) = False,True
                    else:
                        nextbox += 1
                except KeyError:
                    boxes[nextbox] = False
                    if boxes[nextbox] == False:
                        (boxes[box],boxes[nextbox]) = False,True
                    else:
                        nextbox += 1
        turn += 1

    print boxes
    print final_state(boxes)

if __name__ == '__main__':
    main()

I might try to finish it up tonight when I get home from work. It's quite ugly in its current state, and again it doesn't work. This is what the script currently returns lol:
Code:
$ ./problem_426.py 10
{1: False, 2: False, 3: False, 4: False, 5: False, 6: False, 7: False, 8: False, 9: False, 10: False, 11: False, 12: False, 13: False, 14: False, 15: False, 16: False, 17: False, 18: False, 19: False, 20: False, 21: False, 22: False, 23: False, 24: False, 25: False, 26: False, 27: False, 28: False, 29: False, 30: False, 31: False, 32: False, 33: False, 34: False, 35: False, 36: False, 37: False, 38: False, 39: False, 40: False, 41: False, 42: False, 43: True, 44: True, 45: True, 46: True}
[42]

Edited by Ferrari8608 - 5/22/13 at 12:56pm
post #10 of 15

There should be a shortcut for the problem.

The first few states don't have a specific order and are completely dependent on the previous states.

This changes when the following state is achieved:

[*][ ][*][*][ ][ ][ ][ ][ ][*][*][*]

At this point, the first, second, and third groups become independent of each other (in this specific case). As a result, for each cycle, the group with one dot will move one space, the group with 2 dots will move 2 spaces, and the last group with 3 dots will move 3 spaces.

 

As you can see, the second group is moving twice as fast as the first while the third group is moving three times as fast. Given this and the initial spaces between the groups (1 and 5), for any given cycle past the 3rd cycle (zero indexed) the following formula will hold true:

 

let x be the 3rd cycle

let N be the final number of cycles minus x (remember that x represents the 4th cycle)

[1, (1 + N), 2, (5 + N), 3]

 

The question of interest for this problem set seems to be determining if ALL similar systems must ultimately fall into a pattern from smallest to largest group separated by spaces equal to or greater than the preceding group. Once this is calculated (assuming it exists) via brute force, all future outputs can be reduced according to the difference in the number of items of a given group and the following group.

 

If such a result were not possible for some systems, then linear bruteforce solutions would be the only acceptable answers.

 

@wedge

the penalties for sequential reading of a list are nearly equal to arrays. The only noticeable penalty in nearly every application is the size. 

 

Keep in mind that you don't need very much variation in array size. If you have N dots, then the maximum array size (assuming space, ball, space, ball, ... ball, space) would be (2*N + 1). Since empty spaces before the first ball are not being used, nor are spaces after, the actual formula is (2*n - 1). In this case, six balls means that the maximum size is 11. All you need to do is keep track of the numbers in each array spot so if you had [3,3,2,4,1], the next cycle would be [3,2,2,3,1] and the size of the array would not change.

New Posts  All Forums:Forum Nav:
  Return Home
  Back to Forum: Coding and Programming
Overclock.net › Forums › Software, Programming and Coding › Coding and Programming › Project Euler Discussion