Results 1 to 5 of 5
  1. #1
    rfindle is offline Member
    Join Date
    Apr 2016
    Posts
    1
    Rep Power
    0

    Default Problem from TopCoder...

    Just doing a little practice on TopCoder:
    Problem Statement
    One day, Jamie noticed that many English words only use the letters A and B. Examples of such words include "AB" (short for abdominal), "BAA" (the noise a sheep makes), "AA" (a type of lava), and "ABBA" (a Swedish pop sensation).


    Inspired by this observation, Jamie created a simple game. You are given two s: initial and target. The goal of the game is to find a sequence of valid moves that will change initial into target. There are two types of valid moves:

    Add the letter A to the end of the string.
    Add the letter B to the end of the string and then reverse the entire string. (After the reversal the newly-added B becomes the first character of the string).
    Return "Possible" (quotes for clarity) if there is a sequence of valid moves that will change initial into target. Otherwise, return "Impossible".

    Definition
    Class: ABBADiv1
    Method: canObtain
    Parameters: String, String
    Returns: String
    Method signature: String canObtain(String initial, String target)
    (be sure your method is public)
    Limits
    Time limit (s): 2.000
    Memory limit (MB): 256
    Constraints
    - The length of initial will be between 1 and 49, inclusive.
    - The length of target will be between 2 and 50, inclusive.
    - target will be longer than initial.
    - Each character in initial and each character in target will be either 'A' or 'B'.
    Examples
    0)
    "A"
    "BABA"
    Returns: "Possible"
    Jamie can perform the following moves:
    Initially, the string is "A".
    Jamie adds a 'B' to the end of the string and then reverses the string. Now the string is "BA".
    Jamie adds a 'B' to the end of the string and then reverses the string. Now the string is "BAB".
    Jamie adds an 'A' to the end of the string. Now the string is "BABA".
    Since there is a sequence of moves which starts with "A" and creates the string "BABA", the answer is "Possible".
    1)
    "BAAAAABAA"
    "BAABAAAAAB"
    Returns: "Possible"
    Jamie can add a 'B' to the end of the string and then reverse the string.
    2)
    "A"
    "ABBA"
    Returns: "Impossible"
    3)
    "AAABBAABB"
    "BAABAAABAABAABBBAAAAAABBAABBBBBBBABB"
    Returns: "Possible"
    4)
    "AAABAAABB"
    "BAABAAABAABAABBBAAAAAABBAABBBBBBBABB"
    Returns: "Impossible"
    This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2003, TopCoder, Inc. All rights reserved.

    My Code:
    Java Code:
    public class ABBADiv1{
        public String canObtain(String initial, String target){
            //terminating conditions
            if(initial.equals(target)){return "Possible";}
            if(initial.length() >= target.length()){return "Impossible";}
            //case where A added to initial
            if(target.charAt(target.length() - 1) == 'A'){
                //perform reverse operations on target, then resubmit to canObtain
                return canObtain(initial, target.substring(0, target.length() - 1));
            }
            //case where B added, then initial reversed
            else{
                //perform reverse operations on target, then resubmit to canObtain
                char[] t = target.toCharArray();
                for(int i = 0; i < t.length/2; i++){
                    char temp = t[i];
                    t[i] = t[t.length - 1 - i];
                    t[t.length - 1 - i] = temp;
                }
                target = String.valueOf(t);
                return canObtain(initial, target.substring(0, target.length() - 1));
            }
        }
    
        public static void main(String[] args){
            ABBADiv1 A = new ABBADiv1();
            String result = A.canObtain(args[0], args[1]);
            System.out.println(result);
        }
    }
    For whatever reason, this code does not work for test case 3. I'm having trouble finding the bug, so any tips would be much appreciated.
    Last edited by Tolls; 04-08-2016 at 09:40 AM.

  2. #2
    Tolls is offline Moderator
    Join Date
    Apr 2009
    Posts
    13,541
    Rep Power
    26

    Default Re: Problem from TopCoder...

    When posting code please can you wrap it in code tags so it retains its formatting.
    Please do not ask for code as refusal often offends.

    ** This space for rent **

  3. #3
    Sizzlewump's Avatar
    Sizzlewump is offline Member
    Join Date
    Oct 2010
    Location
    MI, USA
    Posts
    68
    Rep Power
    0

    Default Re: Problem from TopCoder...

    What is the value of String initial?
    "The secret to getting what you want is to reject everything that you don't want." -Wolbers

  4. #4
    Sizzlewump's Avatar
    Sizzlewump is offline Member
    Join Date
    Oct 2010
    Location
    MI, USA
    Posts
    68
    Rep Power
    0

    Default Re: Problem from TopCoder...

    So according to the directions, we have:

    Constraints
    - The length of initial will be between 1 and 49, inclusive.
    - The length of target will be between 2 and 50, inclusive.

    I think this is what needs to be represented in your code next. Perhaps the out of bounds error exists since no upper limit for your strings was laid out.
    "The secret to getting what you want is to reject everything that you don't want." -Wolbers

  5. #5
    jim829 is offline Senior Member
    Join Date
    Jan 2013
    Location
    Northern Virginia, United States
    Posts
    6,226
    Rep Power
    14

    Default Re: Problem from TopCoder...

    It also doesn't work for i = "A", and t = "BABA"

    Here is what you do:

    Remove A leaving BAB.
    Reverse and remove B leaving BA
    Remove A leaving B.
    A and B do not compare.

    I believe the problem is because your code assumes that the last operation done was to append an A (since that is what you first test for).
    But in reality, the A could have been at the beginning and a B appended and reversed (resulting in an A on the end).

    Regards,
    Jim
    Last edited by jim829; 04-10-2016 at 08:23 PM.
    The JavaTM Tutorials | SSCCE | Java Naming Conventions
    Poor planning on your part does not constitute an emergency on my part

Similar Threads

  1. Replies: 5
    Last Post: 11-11-2015, 12:16 PM
  2. Replies: 0
    Last Post: 11-07-2012, 12:44 PM
  3. Small problem with problem with Java, C++ parse program.
    By dragstang86 in forum New To Java
    Replies: 4
    Last Post: 10-30-2011, 03:43 AM
  4. Replies: 9
    Last Post: 09-21-2010, 04:15 PM
  5. simple line problem / for loop problem
    By helpisontheway in forum New To Java
    Replies: 1
    Last Post: 11-17-2009, 06:12 AM

Posting Permissions

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