1. Member
Join Date
Apr 2016
Posts
1
Rep Power
0

## 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
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){
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. Moderator
Join Date
Apr 2009
Posts
13,541
Rep Power
26

## Re: Problem from TopCoder...

When posting code please can you wrap it in code tags so it retains its formatting.

3. ## Re: Problem from TopCoder...

What is the value of String initial?

4. ## 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.

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

## 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.

#### Posting Permissions

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