/prog/ - Project Euler

Name: Anonymous 2011-12-29 17:50

Hi /prog/,
I'm currently improving my fairly rudimentary programming skills by doing Project Euler exercises.
Problem 18 (http://projecteuler.net/problem=18) had me stuck for a while today, and now that I've solved it, I still can't help but feel that my way of doing it is awfully odd.
Here's a link to my solution: http://pastebin.com/YX4kW3dA
How would you have solved this problem?

Name: Anonymous 2011-12-29 17:54

Your solution seems fine to me.
You make use of a recursive function (a function that calls itself).
You do have to be careful with that 04 there, because of the 0 in front of it, Java will interpret it as an octal number.

Name: Anonymous 2011-12-29 18:01

Am I misunderstanding the problem, or is it just (foldl (lambda (x r) (+ (apply max x) r)) 0 triangle)?

Name: OP 2011-12-29 18:05

>>3
I have no clue how that code you've posted is supposed to work, but if the triangle was



  a

 b c

d e f

you'd just have to do a+b+d, a+b+e, a+c+e, a+c+f and see which is biggest.

Name: Anonymous 2011-12-29 18:25

>>4
If the triangle is called triangle, and is a list of lists:
((a) (b c) (d e f)), that code does this: (+ (max a) (max b c) (max d e f)), where (+ x y ... z) = x+y+...+z, and (max x y ... z) returns its biggest argument.

Name: Anonymous 2011-12-29 18:38

>>5
I don't think that's right, you have to follow a "path" through the triangle. If you have

the solution would not be 5 + 10 + 11 = 26 because you can't "reach" the 11 once you've gone to the 10. 5 + 10 + 9 = 24 would be the solution here.

Name: Anonymous 2011-12-29 18:53

I didn't check the triangle in the exercise, but in the general case you need to use backtracking to get the global maximum.

Name: Anonymous 2011-12-29 18:58

>>6
Yes, it's not right. I misunderstood the challenge, then.

Name: Anonymous 2011-12-29 19:00

you guyes could use dynamic programming to make it more efficient. Compute the best paths, starting from the bottom of the triangle, and then working your way up.

Name: Anonymous 2011-12-29 19:19

Every time there's a Project Euler thread on /prog/, this problem comes up. It's not even hard.

Name: Anonymous 2011-12-29 21:46

☑ em

Name: Anonymous 2011-12-29 22:12

>>11
Not bad.

Name: Anonymous 2011-12-30 12:19

>>9

This is much better.

Project Euler

1 Name: Anonymous 2011-12-29 17:50

2 Name: Anonymous 2011-12-29 17:54

3 Name: Anonymous 2011-12-29 18:01

4 Name: OP 2011-12-29 18:05

5 Name: Anonymous 2011-12-29 18:25

6 Name: Anonymous 2011-12-29 18:38

7 Name: Anonymous 2011-12-29 18:53

8 Name: Anonymous 2011-12-29 18:58

9 Name: Anonymous 2011-12-29 19:00

10 Name: Anonymous 2011-12-29 19:19

11 Name: Anonymous 2011-12-29 21:46

12 Name: Anonymous 2011-12-29 22:12

13 Name: Anonymous 2011-12-30 12:19