topcoderの過去問 - ABBA
今日すること
こんにちはふるてつです。
今日は Topcoder の過去問です。
問題について
今日の問題は ABBA。
引数で開始文字と目標文字が与えられます。
可能な操作は開始文字に対して末尾に "A" を追加する。
もしくは文字を反転（A ⇒ B、B ⇒ A）し、末尾に "B" を追加する。
この2つの操作を繰り返して、目標文字と一致したら "Possible" 、一致しなければ "Impossible" を返します。
英語の原文はこちらです
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.
Reverse the string and then add the letter B to the end 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: ABBA
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 999, inclusive.
- The length of target will be between 2 and 1000, inclusive.
- target will be longer than initial.
- Each character in initial and each character in target will be either 'A' or 'B'.
Examples
0)
"B"
"ABBA"
Returns: "Possible"
Jamie can perform the following moves:
Initially, the string is "B".
Jamie adds an 'A' to the end of the string. Now the string is "BA".
Jamie reverses the string and then adds a 'B' to the end of the string. Now the string is "ABB".
Jamie adds an 'A' to the end of the string. Now the string is "ABBA".
Since there is a sequence of moves which starts with "B" and creates the string "ABBA", the answer is "Possible".
1)
"AB"
"ABB"
Returns: "Impossible"
The only strings of length 3 Jamie can create are "ABA" and "BAB".
2)
"BBAB"
"ABABABABB"
Returns: "Impossible"
3)
"BBBBABABBBBBBA"
"BBBBABABBABBBBBBABABBBBBBBBABAABBBAA"
Returns: "Possible"
4)
"A"
"BB"
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.
わたしの解答
わたしの解答コードは下記になります。
while文で目標文字と一致するまで2つの操作を繰り返しました。
目標文字より桁数が大きくなり一致しようがなくなった場合は "Impossible" を返して終了です。
package practice;
/**
* ABBA
* @author furutetsu
*
*/
public class ABBA {
private static final String MSG_POSSIBLE = "Possible";
private static final String MSG_IMPOSSIBLE = "Impossible";
private static final String CHAR_A = "A";
private static final String CHAR_B = "B";
private static final String CHAR_TEMPORARY = "@";
/**
* canObtain
* @param initial 初期の文字
* @param target 目標の文字
* @return 可能/不可能
*/
public String canObtain(String initial, String target) {
String abba = initial;
System.out.println("abba:" + abba);
while (true) {
if (over(abba, target)) {
return MSG_IMPOSSIBLE;
}
abba = addA(abba);
System.out.println("abba:" + abba);
if (isMatchTarget(abba, target)) {
return MSG_POSSIBLE;
}
abba = reverse(abba);
System.out.println("abba:" + abba);
if (isMatchTarget(abba, target)) {
return MSG_POSSIBLE;
}
}
}
/**
* 終了判定
* @param abba ABBAの文字
* @param target 目標の文字
* @return ABBAの文字
*/
private boolean over(String abba, String target) {
return abba.length() > target.length();
}
/**
* 末尾にAを追加
* @param abba ABBAの文字
* @return ABBAの文字
*/
private String addA(String abba) {
return abba + CHAR_A;
}
/**
* 反転して末尾にBを追加
* @param abba ABBAの文字
* @return ABBAの文字
*/
private String reverse(String abba) {
return abba.replaceAll(CHAR_A, CHAR_TEMPORARY).replaceAll(CHAR_B, CHAR_A).replaceAll(CHAR_TEMPORARY, CHAR_B)
+ CHAR_B;
}
/**
* 一致判定
* @param abba ABBAの文字
* @param target 目標の文字
* @return ABBAの文字
*/
private boolean isMatchTarget(String abba, String target) {
return abba.equals(target);
}
}
下はテストコードです。
package test;
import static org.hamcrest.CoreMatchers.*;
import static org.junit.Assert.*;
import org.junit.jupiter.api.Test;
import practice.ABBA;
class ABBATest extends ABBA {
@Test
void testCanObtain() {
assertThat(canObtain("B", "ABBA"), is("Possible"));
assertThat(canObtain("AB", "ABB"), is("Impossible"));
assertThat(canObtain("BBAB", "ABABABABB"), is("Impossible"));
assertThat(canObtain("A", "BB"), is("Impossible"));
}
}
今日の感想
今日の問題の難易度は「Medium」でした。
これまでに解いた「Easy」の問題とあまり違いは感じなかったですけど、今日もいい頭の体操になりました。
ではまた。
