Any interest in a Project Euler Group? - Page 7 - Computer Technical Help

Search youtube for the language you want + the word tutorial. There are lots of great ones on there. As far as the language to choose IMO go with something that is popular like Java, C++, Python, etc. because then you will have an easier time getting information.

Quote

04-21-2012 , 06:30 PM

#152

Xhad

Carpal \'Tunnel

Join Date: Jul 2005 Posts: 10,962

Any programming language with any measure of popularity has free implementations. Some of the nicer IDEs may be worth buying but I definitely wouldn't even consider that as a total beginner. You don't write code in something like Word, though a lot of people write code in programs closely resembling Notepad.

Personally, I would recommend Python. I first picked it up for mathematical computing stuff because I can't stand MATLAB. I'm going to anti-recommend C/C++ because if you're a total beginner it's going to make you worry about a low-level stuff that will only confuse and depress you at first. And while Python is generally slower, there's an a module called Numpy that gives you C-based arrays and matrices if you need them anyway.

Quote

04-22-2012 , 07:16 PM

#153

Bilbo Gbagbins

journeyman

Join Date: Apr 2011 Posts: 252

Does anyone else solve these in bursts? Like I do about 10 and then forget about it for a few months and then come back and get really into them again.

I've been using C# but I didn't actually know how to create libraries until a few weeks ago so I was rewriting a lot of the functions from scratch each time (or copying and pasting from old questions). Now I have a nice shiny class library with all the functions that come up again and again (Prime number Sieve, Chopping a number into its digits, Factorising a number etc etc).

Having used Mathematica in college and seen its wide ranging functionality I definitely think that it sucks the fun out of the whole thing. I actually feel kinda like a cheat using the BigInteger class in C# but I haven't come up with a way of representing gigantic numbers from scratch myself.

Can't believe there are so many guys on the solution forums using machine code. It looks so unintuitive.

Quote

04-22-2012 , 10:52 PM

#154

Xhad

Carpal \'Tunnel

Join Date: Jul 2005 Posts: 10,962

Quote:

Does anyone else solve these in bursts? Like I do about 10 and then forget about it for a few months and then come back and get really into them again.

This is exactly what I do.

Quote

04-23-2012 , 02:46 AM

#155

Ryanb9

Carpal \'Tunnel

Join Date: Aug 2006 Posts: 7,459

Quote:

Originally Posted by Xhad

This is exactly what I do.

+1. Sometimes I learn a new trick and am reminded about a problem I skipped and I go back to it too.

Quote

08-19-2012 , 03:52 PM

#156

checkm8

old hand

Join Date: Dec 2007 Posts: 1,495

I agree with the what's been said about enthusiasm in waves, so with that being said I took a crack at #5 after taking a hiatus.

So on number 5 (http://projecteuler.net/problem=5) I took an interesting(maybe not, maybe it's standard) approach, would like feedback..

"2520 is the smallest number that can be divided by each of the numbers from 1 to 10 without any remainder.

What is the smallest positive number that is evenly divisible by all of the numbers from 1 to 20?"

Spoiler:

Last edited by checkm8; 08-19-2012 at 04:03 PM.

Quote

05-23-2013 , 01:46 AM

#157

Ryanb9

Carpal \'Tunnel

Join Date: Aug 2006 Posts: 7,459

http://projecteuler.net/problem=15
"Lattice paths"

So, I'm wondering if I should do this in a run-it-and-count type of way or if there is a mathematical equation I should look up. I'm really good with tiles b/c I do a lot of pathfinding but idk if this is one of those where u dont need to brute force it or not

Quote

05-23-2013 , 01:49 AM

#158

Xhad

Carpal \'Tunnel

Join Date: Jul 2005 Posts: 10,962

There's definitely a better way than brute force, and it's not particularly mathy. (there's probably a mathy way too, but that's not where my mind went on that one and I have a math degree)

Quote

05-23-2013 , 05:29 AM

#159

Ryanb9

Carpal \'Tunnel

Join Date: Aug 2006 Posts: 7,459

Quote:

Originally Posted by Xhad

There's definitely a better way than brute force, and it's not particularly mathy. (there's probably a mathy way too, but that's not where my mind went on that one and I have a math degree)

I don't know if i actually meant "brute force" when I said "brute force." What I meant was writing a script that built a 20x20 grid and making ... crawlers (or w/e) take a path that hasn't been taken to the end and just recording how many did it successfully (as opposed to something like "blah blah 4 to the power of 20 * 20 b/c blah b/c of Maxwell's blah calculus &etc.").

Quote

05-23-2013 , 12:09 PM

#160

Xhad

Carpal \'Tunnel

Join Date: Jul 2005 Posts: 10,962

that's actually getting kind of close, but you can make certain simplifications based on the fact that the only possible directions are right and down. There's a pretty straightforward algorithm that visits each intersection exactly one time.

Quote

05-24-2013 , 12:59 PM

#161

WeAreSamurai

newbie

Join Date: Nov 2010 Posts: 22

Quote:

Originally Posted by Ryanb9

The trick to this problem is to realize that for any n by n grid, to get from top left to bottom right you always have to move n times to the right and n times down. So the question boils down to how many different ways can you arrange n rights and n downs. For a formula you can look up binomial coefficients. The Wikipedia page even has a section for programming implementations.

Quote

06-03-2013 , 11:16 PM

#162

greenbast

adept

Join Date: Jul 2009 Posts: 758

I have been working on these, only have 24 done but my goal was to try get to 50 this month. Ive been working in C++ but a few of them ive solved on paper first then wrote the program to match. Often times I get the solution then spend the rest of the day looking at ways people optimized it.. Insane the amount of 1 liners on the forum.

Quote

06-11-2013 , 04:52 AM

#163

MelchyBeau

Carpal \'Tunnel

Join Date: Sep 2004 Posts: 6,043

Quote:

Originally Posted by Xhad

There's definitely a better way than brute force, and it's not particularly mathy. (there's probably a mathy way too, but that's not where my mind went on that one and I have a math degree)

The solution requires no programming at all. I guess my mind went directly to the math solution as I am working on my Ph.D in mathematics (graph theory focus). I'll provide the solution in spoilers.

Spoiler:

Quote

06-11-2013 , 09:40 AM

#164

Xhad

Carpal \'Tunnel

Join Date: Jul 2005 Posts: 10,962

That makes sense. The programming way is similarly easy once you realize:

Spoiler:

FWIW out of the 80 I've done I've only done one on pen & paper, partially because I deliberately avoided it. The only exception was 79, because there's enough ambiguity in the problem that I wasn't sure any algorithm would return a correct answer.

Quote

11-20-2014 , 11:33 PM

#165

STinLA

old hand

Join Date: May 2009 Posts: 1,882

Project Euler Novice here (23 solved so far). I have a theoretical question about #17. After I solved it I noticed in the Problem 17 thread that many people took the numbers, assigned strings to each digit in the number, then counted the number of characters in the string. For example:

Spoiler:

Other (like me), just assigned a value to each digit in each place without converting to a string:

Spoiler:

Code:

public class ProjectEuler17 {

    public static void main(String[] args) {
        int sum = 11; // one thousand 11
        for (int i=1; i < 1000; i++) {
            int lastTwo = i % 100;
            
            if (lastTwo > 0) {
                if (i > 99) {
                    sum += 3; // and 3
                }
               if ((lastTwo < 20) && (lastTwo > 9)) {
                    switch(lastTwo) {
                        case 10:    sum += 3; // ten 3
                                    break;
                        case 11:    sum += 6; // eleven 6
                                    break;
                        case 12:    sum += 6; // twelve 6
                                    break;
                        case 13:    sum += 8; // thirteen 8
                                    break;
                        case 14:    sum += 8; // fourteen 8
                                    break;
                        case 15:    sum += 7; // fifteen 7
                                    break;
                        case 16:    sum += 7; // sixteen 7
                                    break;
                        case 17:    sum += 9; // seventeen 9
                                    break;
                        case 18:    sum += 8; // eighteen 8
                                    break;
                        case 19:    sum += 8; // nineteen 8
                                    break;
                    }
                } else {
                    int tensPlace = lastTwo/10;
                    switch (tensPlace) {
                        case 0: break;
                        case 2: sum += 6; // twenty 6
                                break;
                        case 3: sum += 6; // thirty 6
                                break;
                        case 4: sum += 5; // forty 5
                                break;
                        case 5: sum += 5; // fifty 5
                                break;                        
                        case 6: sum += 5; // sixty 5
                                break;                        
                        case 7: sum += 7; // seventy 7
                                break;                        
                        case 8: sum += 6; // eighty 6
                                break;                        
                        case 9: sum += 6; // ninety 6
                                break;                            
                    }
                    
                    int onesPlace = i % 10;
                    switch (onesPlace) {
                        case 0: break;
                        case 1: sum += 3; // one 3
                                break;
                        case 2: sum += 3; // two 3
                                break;
                        case 3: sum += 5; // three 5
                                break;
                        case 4: sum += 4; // four 4
                                break;
                        case 5: sum += 4; // five 4
                                break;                        
                        case 6: sum += 3; // six 3
                                break;                        
                        case 7: sum += 5; // seven 5
                                break;                        
                        case 8: sum += 5; // eight 5
                                break;                        
                        case 9: sum += 4; // nine 4
                                break;                            
                    }
                }
            }
            
            int hundredsPlace = (i % 1000)/100;
            if (hundredsPlace != 0) {
                sum += 7; // hundred 7
                switch (hundredsPlace) {
                    case 1: sum += 3; // one 3
                            break;
                    case 2: sum += 3; // two 3
                            break;
                    case 3: sum += 5; // three 5
                            break;
                    case 4: sum += 4; // four 4
                            break;
                    case 5: sum += 4; // five 4
                            break;                        
                    case 6: sum += 3; // six 3
                            break;                        
                    case 7: sum += 5; // seven 5
                            break;                        
                    case 8: sum += 5; // eight 5
                            break;                        
                    case 9: sum += 4; // nine 4
                            break;                            
                }
            }
            
        }
        
        System.out.println(sum);
    }
        
}

From a computational efficiency standpoint, which is better? I realize that neither example I posted is anywhere near optimal, but which approach is closer to optimal?

Quote

11-20-2014 , 11:44 PM

#166

Xhad

Carpal \'Tunnel

Join Date: Jul 2005 Posts: 10,962

The second is probably faster I think, but even faster would be to combine the two approaches; have an array/hashtable that you index into, but have the values be integers insted of strings.

Quote

11-21-2014 , 07:08 PM

#167

STinLA

old hand

Join Date: May 2009 Posts: 1,882

Quote:

Originally Posted by Xhad

The second is probably faster I think, but even faster would be to combine the two approaches; have an array/hashtable that you index into, but have the values be integers instead of strings.

By this, do you means create an array that holds all the possible values that the length of the written number can take, then use the number itself (and its order of magnitude) as the key to find the correct value in the array?

So for the simple case of 1-9

Code:

int[] wordLenArr = {3, 4, 5};
int lengthCounter = 0;

for (int i=1; i<10; i++)  {
     switch(i) {
          case 1: case 2: case 6:
               lengthCounter += wordLenArr[0];
               break;
          case 4: case 5: case 9:
               lengthCounter += wordLenArr[1];
               break;
          case 3: case 7: case 8: 
               lengthCounter += wordLenArr[2];
               break;
     }
}

Last edited by STinLA; 11-21-2014 at 07:17 PM.

Quote

11-21-2014 , 10:46 PM

#168

Xhad

Carpal \'Tunnel

Join Date: Jul 2005 Posts: 10,962

I was thinking of something more along these lines:

Code:

// zero only there because something has to be there
int[] wordLenArr = {0, 3, 3, 5, 4, 4, 3, 5, 5, 4}
int lengthCounter = 0;

for(int i=1; i<10; i++) lengthCounter += wordLenArr[i];

Quote

11-24-2014 , 01:51 PM

#169

RoundTower

ɹǝʍoʇpunoɹ

Join Date: Feb 2005 Posts: 14,563

I expect they are both roughly the same. The gotcha here is if you join all the strings first, and then calculate the length. This would be way slower because concatenating strings is a surprisingly slow operation. The longer the strings, the longer it will take. I would explain this but there is probably a much better explanation just a Google away.

If you are in a situation where you need to repeatedly join thousands of strings, you should find the library function that makes this faster. In Java I believe you need to look for StringBuilder.

Quote

11-24-2014 , 01:56 PM

#170

Xhad

Carpal \'Tunnel

Join Date: Jul 2005 Posts: 10,962

it's not catting strings; just summing their lengths. It's easy to miss because the person who wrote it clearly didn't look at their code after finishing it (see: the temp variable that isn't actually used)

Quote

11-24-2014 , 06:46 PM

#171

RoundTower

ɹǝʍoʇpunoɹ

Join Date: Feb 2005 Posts: 14,563

yeah I made that mistake, then reread and ninja edited

Quote

11-25-2014 , 01:11 AM

#172

STinLA

old hand

Join Date: May 2009 Posts: 1,882

Well, after not touching Project Euler for over three years, I've now done two problems in one week. I mostly stopped because I didn't find problem 17 interesting, but I was too neurotic to skip it.

Quote

11-25-2014 , 01:27 AM

#173

Xhad

Carpal \'Tunnel

Join Date: Jul 2005 Posts: 10,962

Yeah, it's probably better if you're willing to skip some because there isn't really a steady increase in difficulty. My current policy is "filter out the ones I've done and only do the ones on the first page", so I'm not combing through the entire history of the site but I'm also not letting myself get stuck forever on one hard problem. That said, I haven't touched it in ages, either.

Quote

11-26-2014 , 03:06 AM

#174

Xhad

Carpal \'Tunnel

Join Date: Jul 2005 Posts: 10,962

so this thread bump made me do three problems today (!) and I think I'm well on my way to a fourth for tomorrow evening

it's cool to walk away for awhile and then come back and realize you know more.

Quote

Page 7 of 7

First

2 3 4 5 6 7

Last

Post Reply Subscribe

...

Page 7 of 7

First

2 3 4 5 6 7

Last