import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;
import java.util.Random;


public class Sample177 {
	private static final char[] CHARACTERS = "ABCDEFGHIJKLMNOPQRSTUVWXYZ".toCharArray();
	private static final int INITIAL_COUNT = 300;
	private static final int CREATE_COUNT = 3;


	private final Random random_ = new Random();
	private List<String> cache_ = new ArrayList<String>();

	private final String target_;
	private final Comparator<String> comparator_;


	public Sample177(String target) {
		target_ = target;
		comparator_ = new StringDistanceComparator(target);
		init();
	}
	private void init() {
		for (int count = 0; count < INITIAL_COUNT; count++) {
			cache_.add(createString(target_.length()));
		}
		Collections.sort(cache_, comparator_);
	}
	private String createString(int length) {
		StringBuilder builder = new StringBuilder(length);
		for (int index = 0; index < length; index++) {
			builder.append(CHARACTERS[random_.nextInt(CHARACTERS.length)]);
		}
		return builder.toString();
	}

	public String getTop() {
		return cache_.get(0);
	}

	public void nextStep() {
		for (String str: cache_.toArray(new String[0])) {
			for (int index = 0; index < CREATE_COUNT; index++) {
				cache_.add(changeCharacter(str));
			}
		}
		Collections.sort(cache_, comparator_);
		cache_ = cache_.subList(0, INITIAL_COUNT);
	}
	public String changeCharacter(String str) {
		StringBuilder builder = new StringBuilder(str);
		builder.setCharAt(random_.nextInt(str.length()), CHARACTERS[random_.nextInt(CHARACTERS.length)]);
		return builder.toString();
	}


	static class StringDistanceComparator implements Comparator<String> {
		private final String target_;
		public StringDistanceComparator(String target) {
			target_ = target;
		}

		@Override
		public int compare(String o1, String o2) {
			return calcDistance(o1) - calcDistance(o2);
		}
		private int calcDistance(String other) {
			int distance = 0;
			for (int index = 0, len = target_.length(); index < len; index++) {
				distance += (target_.charAt(index) == other.charAt(index))? 0 : 1;
			}
			return distance;
		}
	}


	public static void main(String[] args) {
		String target = "METHINKSITISAWEASEL";
		Sample177 sample = new Sample177(target);

		int index = 1;
		String top = sample.getTop();
		System.out.println(index++ + ":" + top);
		while (!top.equals(target)) {
			sample.nextStep();
			top = sample.getTop();
			System.out.println(index++ + ":" + top);
		}
	}
}