Results 1 to 3 of 3
  1. #1
    Rendar- is offline Member
    Join Date
    Jan 2014
    Posts
    2
    Rep Power
    0

    Default Can't Figure Out What Memoization Code Is Doing

    Hi there, I'm new to the forum and am working on a Computer Science project for school where I have to refactor a program involving memoization. The issue is, I can't exactly figure out what the program is doing.

    I have begun changing some of the variable names, but I won't be able to further optimize the code until I figure out what's going on.

    The tests we've been given for the code are to input "2", "babgbag", "bag", "rabbbit" and "rabbit".

    This outputs the numbers 5 and 3.

    I have figured out that the first number input is how many pairs of strings we are going to input, then it looks like it compares the characters at each location of each set. So "babgbag" and "bag" are compared as are "rabbbit" and "rabbit". But I can't figure out where these numbers 5 and 3 are coming from.

    When I step through the program in debug mode in Eclipse, I can't seem to find an end to the loops.

    Can someone point me in the right direction as to where these numbers are coming from?

    P.S.: The code is supposed to be messy, the point of this class is to learn how to clean it up.

    Java Code:
    public class Project1 
    {
    	static String x, z;
    	static int rem[][];
    	static String strInput;
    	static int intPairs;//n
    	static BufferedReader ir;
    
    	/**
    	 * @param args
    	 * @throws IOException
    	 */
    	public static void main(String[] args) throws IOException 
    	{
    		
    		ir = new BufferedReader(new InputStreamReader(System.in));
    		strInput = new String(ir.readLine());
    		intPairs = Integer.parseInt(strInput);
    		
    		for (int i = 0; i < intPairs; i++) 
    		{
    			z = new String(ir.readLine());
    			x = new String(ir.readLine());
    			System.out.println(answer(x, z));
    		}
    	}
    
    	public static int answer(String x1, String z1) 
    	{
    		// # characters in the string minus 1
    		int xLengthMinusOne = x1.length() - 1;
    		int zLengthMinusOne = z1.length() - 1;
    		rem = new int[xLengthMinusOne + 1][zLengthMinusOne + 1];
    		
    		for (int k = 0; k < xLengthMinusOne + 1; k++)
    		{
    			for (int j = 0; j < zLengthMinusOne + 1; j++)
    			{
    				rem[k][j] = -1;
    			}
    		}
    		return cShell(xLengthMinusOne, zLengthMinusOne);
    	}
    
    	private static int cShell(int xE, int zE) 
    	{
    		// If String x has a length of 0
    		if (xE == -1)
    		{
    			return 1;
    		}
    		
    		// If the value in rem at indices [xLengthMinusOne][zLengthMinusOne] == -1
    		if (rem[xE][zE] == -1)
    		{
    			rem[xE][zE] = cMeat(xE, zE);
    		}
    		return rem[xE][zE];
    	}
    
    	/**
    	 * @param xE
    	 * @param zE
    	 * @return
    	 */
    	private static int cMeat(int xE, int zE) 
    	{
    		// If String x has a length of 0
    		if (xE == -1)
    		{
    			return 1;
    		}
    		
    		// If String x is longer than String z
    		if (xE > zE)
    		{
    			return 0;
    		}
    		
    		// If both Strings are the same length
    		if (xE == zE) 
    		{
    			// If both Strings are equal
    			if (sameish(xE))
    			{
    				return 1;
    			}
    			
    			// Else both Strings are not equal
    			return 0;
    		}
    		
    		// If String x is shorter than String z AND both Strings have the same ending character
    		if (x.charAt(xE) == z.charAt(zE)) 
    		{
    			// cShell(xLength - 2, zLength -2) + cShell(xLength - 1, zLength - 2)
    			return (cShell(xE - 1, zE - 1)) + cShell(xE, zE - 1);
    		}
    		
    		// cShell(xLength - 1, zLength - 2);
    		return (cShell(xE, zE - 1));
    	}
    
    	private static boolean sameish(int end) 
    	{
    		for (int i = 0; i <= end; i++)
    		{
    			if (x.charAt(i) != z.charAt(i))
    			{
    				return false;
    			}
    		}
    		return true;
    	}
    
    }

  2. #2
    jim829 is offline Senior Member
    Join Date
    Jan 2013
    Location
    Northern Virginia, United States
    Posts
    4,036
    Rep Power
    6

    Default Re: Can't Figure Out What Memoization Code Is Doing

    Well, one thing you can do is formulate some hypothesis on what is going on and then create your own pairs to prove or disprove it.

    Regards,
    Jim
    The JavaTM Tutorials | SSCCE | Java Naming Conventions
    Poor planning on your part does not constitute an emergency on my part

  3. #3
    Rendar- is offline Member
    Join Date
    Jan 2014
    Posts
    2
    Rep Power
    0

    Default Re: Can't Figure Out What Memoization Code Is Doing

    Quote Originally Posted by jim829 View Post
    Well, one thing you can do is formulate some hypothesis on what is going on and then create your own pairs to prove or disprove it.

    Regards,
    Jim
    I finally figured that part out, it's looking for subsequences of the second string in the first string. I still can't quite figure out what "rem" is doing. What is that actually storing in the long term if anything at all?

Similar Threads

  1. can't figure out how jvm evaluates the code
    By ftftftftftftftft in forum New To Java
    Replies: 4
    Last Post: 08-03-2012, 08:52 PM
  2. Replies: 5
    Last Post: 04-14-2012, 01:18 PM
  3. Replies: 5
    Last Post: 06-05-2011, 03:19 AM
  4. Replies: 7
    Last Post: 11-04-2010, 05:10 PM
  5. Replies: 3
    Last Post: 01-11-2010, 07:48 AM

Tags for this Thread

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •