×

# SUMTRIAN - implementing memoization

 0 I have spent many hours trying to solve the SUMTRIAN problem (http://www.codechef.com/problems/SUMTRIAN/) I know how my program works, I am implementing recursion, and I am doing my best to implement memoization (this is new for me). The code works perfectly fine for small triangles. However, every submission to CodeChef exceeds the time limit. Can anyone give me any pointers, please? Thanks, public class Main { private static int[][] triangle = new int[0][0]; private static int[][] computedPaths = new int[0][0]; //for memoization public static void main(String[] args){ java.util.Scanner input = new java.util.Scanner(System.in); int cases = input.nextInt(); int[] solutions = new int[cases]; int solutionsIndex = 0; for(int i = 0; i < cases; i += 1){//for each triangle int lines = input.nextInt(); triangle = new int[lines][lines]; computedPaths = new int[lines][lines]; int level = 1; //top of triangle is level 1 and level increases as works towards base for(int y = 0; y < lines; y += 1){ for(int x = 0; x < level; x += 1){ triangle[y][x] = input.nextInt(); } level += 1; } //save outputs in array until all inputs are processed solutions[solutionsIndex] = findGreatestRouteValueRecursively(0,0); solutionsIndex += 1; } for(int i = 0; i < solutions.length; i += 1){ System.out.println(solutions[i]); } }//end main public static int findGreatestRouteValueRecursively(int y, int x){ if(y >= triangle.length) return 0; else if(computedPaths[y][x] == 0){ int value1 = findGreatestRouteValueRecursively(y+1, x); int value2 = findGreatestRouteValueRecursively(y+1, x+1); computedPaths[y][x] = Math.max(value1, value2) + triangle[y][x]; } return computedPaths[y][x]; }//end findGreatestRouteValueRecursively() }  asked 28 Jun '14, 06:49 2★slaynen 1●2 accept rate: 0%

 0 bump - any tips on how to memoize this would be greatly appreciated! the only code to rly look at is the findGreatestRouteValueRecursively at the bottom answered 28 Jun '14, 18:32 2★slaynen 1●2 accept rate: 0%
 0 Solved - for anyone curious, what made the difference was changing my input from Scanner to BufferedReader and InputStreamReader. Lesson learned :) Code below: public class SumsInATriangle { private static int[][] triangle = new int[0][0]; private static int[][] computedPaths = new int[0][0]; //for memoization public static void main(String[] args) throws java.io.IOException{ java.io.BufferedReader reader = new java.io.BufferedReader(new java.io.InputStreamReader(System.in)); String[] in = reader.readLine().split(" "); int cases = Integer.parseInt(in[0]); int[] solutions = new int[cases]; int solutionsIndex = 0; for(int i = 0; i < cases; i += 1){//for each triangle in = reader.readLine().split(" "); int lines = Integer.parseInt(in[0]); triangle = new int[lines][lines]; computedPaths = new int[lines][lines]; int level = 1; //top of triangle is level 1 and level increases as works towards base for(int y = 0; y < lines; y += 1){ in = reader.readLine().split(" "); for(int x = 0; x < level; x += 1){ triangle[y][x] = Integer.parseInt(in[x]); } level += 1; } //save outputs in array until all inputs are processed solutions[solutionsIndex] = findGreatestRouteValueRecursively(0,0); solutionsIndex += 1; } for(int i = 0; i < solutions.length; i += 1){ System.out.println(solutions[i]); } // int level = 1; //print triangle // for(int y = 0; y < triangle[0].length; y += 1, level += 1){ // for(int x = 0; x < level; x += 1){ // System.out.print(triangle[y][x] + " "); // } // System.out.println(); // } }//end main public static int findGreatestRouteValueRecursively(int y, int x){ if(y >= triangle.length) return 0; else if(computedPaths[y][x] == 0){ int value1 = findGreatestRouteValueRecursively(y+1, x); int value2 = findGreatestRouteValueRecursively(y+1, x+1); computedPaths[y][x] = Math.max(value1, value2) + triangle[y][x]; } return computedPaths[y][x]; }//end findGreatestRouteValueRecursively()  }//end class answered 28 Jun '14, 21:34 2★slaynen 1●2 accept rate: 0%
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×3,486
×1,214
×107
×53

question asked: 28 Jun '14, 06:49

question was seen: 1,179 times

last updated: 28 Jun '14, 21:34