Welcome to the Java Programming Forums


The professional, friendly Java community. 21,500 members and growing!


The Java Programming Forums are a community of Java programmers from all around the World. Our members have a wide range of skills and they all have one thing in common: A passion to learn and code Java. We invite beginner Java programmers right through to Java professionals to post here and share your knowledge. Become a part of the community, help others, expand your knowledge of Java and enjoy talking with like minded people. Registration is quick and best of all free. We look forward to meeting you.


>> REGISTER NOW TO START POSTING


Members have full access to the forums. Advertisements are removed for registered users.

Results 1 to 3 of 3

Thread: Problem with Project Euler problem 18

  1. #1
    Junior Member
    Join Date
    Apr 2012
    Posts
    1
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Default Problem with Project Euler problem 18

    By starting at the top of the triangle below and moving to adjacent numbers on the row below, the maximum total from top to bottom is 23.

    3
    7 4
    2 4 6
    8 5 9 3
    That is, 3 + 7 + 4 + 9 = 23.

    Find the maximum total from top to bottom of the triangle
    this is my code but it gives 21 instead of 23 what is wrong in the code thanks
        public static void main(String[] args) {
                    List<List<Integer>> twoDim = new ArrayList<List<Integer>>();
                    int  tempSum;
                    int temp ;
     
            String[] inputLines = {"3","7 4","2 4 6","8 5 9 3"};
     
            for (String line : inputLines) {
                List<Integer> row = new ArrayList<Integer>();
     
                Scanner s = new Scanner(line);
                while (s.hasNextInt())
                    row.add(s.nextInt());
     
                twoDim.add(row);
            }
            int lines = twoDim.size();
     
    for (int i = lines-2 ; i >= 0; i--) {
       for (int j = 0; j <= i; j++) 
        {
     
           twoDim.get(i).add(j,twoDim.get(i).get(j)+Math.max(twoDim.get(i+1).get(j),twoDim.get(i+1).get(j+1)));
     
     
     
        }
    }
    System.out.println(twoDim.get(0).get(0));
        }


  2. #2
    Super Moderator
    Join Date
    Jun 2013
    Location
    So. Maryland, USA
    Posts
    5,520
    My Mood
    Mellow
    Thanks
    215
    Thanked 698 Times in 680 Posts

    Default Re: Problem with Project Euler problem 18

    While your approach may be clever - then again, maybe TOO clever - it is not easy to understand or troubleshoot. I suggest you simplify the part of your program that chooses which value of the next row to add to the total so that you can add test lines to see what is going wrong. Think about how you'd do it in your head or with pencil and paper and code that.

  3. #3
    Super Moderator helloworld922's Avatar
    Join Date
    Jun 2009
    Posts
    2,896
    Thanks
    23
    Thanked 619 Times in 561 Posts
    Blog Entries
    18

    Default Re: Problem with Project Euler problem 18

    Choosing the maximum adjacent value is not guaranteed to give the maximum sum from top to bottom (as demonstrated here).

    Here's a more obvious example:

    1
    1 1
    2 1 1
    1 1 8 9

    Your approach will choose 1 + 1 + 2 + 1, but the best approach is 1 + 1 + 1 + 9.

    If you want to solve this problem the "lazy way", you can use a brute force solver and try every path. As the problem hint suggests, this will work here, but not on problem 67.

    There's a more efficient solution, though (as the problem suggested). As a hint, think about the problem going backwards.

Similar Threads

  1. [SOLVED] Project Euler problem one
    By lanmonster in forum What's Wrong With My Code?
    Replies: 3
    Last Post: February 3rd, 2013, 05:10 PM
  2. [SOLVED] Project Euler Questio 2
    By goldenpsycho in forum What's Wrong With My Code?
    Replies: 2
    Last Post: June 12th, 2012, 07:25 AM
  3. Euler Paths with dfs algorithm problem
    By claudio.r in forum Algorithms & Recursion
    Replies: 18
    Last Post: March 22nd, 2012, 04:39 PM
  4. [SOLVED] Project Euler: Truncatable Primes
    By Staticity in forum What's Wrong With My Code?
    Replies: 7
    Last Post: October 10th, 2011, 12:27 PM
  5. Project Euler
    By helloworld922 in forum The Cafe
    Replies: 5
    Last Post: September 9th, 2009, 02:51 PM