AOJ2273 Shiritori

問題リンク Shiritori

• 解法

プログラムからは、常に同じアルファベットで終わる単語を発言し続ければ、AIは最大27回までしか正しい返答を返せません。
こちらから投げる単語が不正でないか、AIが不正な答えを返してないかをチェックしながらこれを実装します。

• ソース

import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;

//Shiritori
public class AOJ2273 {

	Set<String> words;

	String make(char s, char t){
		String x = s+""+t;
		if(!words.contains(x))return x;
		for(int i=0;i<26;i++){
			String r = s + ""+((char)(i+'a')) + t + "";
			if(!words.contains(r))return r;
		}
		return s+"a"+t;
	}

	void run(){
		Scanner sc = new Scanner(System.in);
		words = new HashSet<String>();
		System.out.println("?a");
		System.out.flush();
		words.add("a");
		while(true){
			String res = sc.next();
			if(res.length()==1 || res.charAt(0)!='a' || words.contains(res)){
				System.out.println("!OUT");
				System.out.flush();
				break;
			}
			words.add(res);
			char h = res.charAt(1);
			String n = make(h, 'a');
			words.add(n);
			System.out.println("?"+n);
			System.out.flush();
		}
	}

	public static void main(String[] args) {
		new AOJ2273().run();
	}
}