CodeIQの問題「平成変換」を解いてみました 問題はこちら http://antimon2.hatenablog.jp/entry/2013/08/07/231634

answer.txt

[2]014->[4]014->[16014]->(256)4(4)(81)(9)[6]->1(64)[2]93(36)->(1849)(36)->(4)(36)->26

===考え方===
開始値からたどっていき総当りでルートを探していきました。
ただし、本当に全てたどるのは現実的に無理なので「それらしいもの」から調べていくことにしました。
ここでは調べるノードの「開始値からの距離+数値の桁数」を求めて、より小さくなるものがより「それらしい」とみなすことにしました。
未調査のノードのうち最もそれらしいノードを選び、そこから推移可能なノードを求めます。その中に目的の値があればそれを答えの候補として、ない場合はそれらの全ノードを未調査ノードの集合に加えます。この操作を繰り返します。
ただし、答えの候補が見つかった場合はそのルートの距離を基準としてそれよりも距離が長くなりそうな値は調査の対象から外します。
同じ数値が複数のルートから求められることもあるため、他に開始値からの距離が短いノードがある場合はそのノードは調査の対象から外します。

HeiseiConvert.java

package matsuri2013;

import java.math.BigDecimal;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.Iterator;
import java.util.List;
import java.util.Map;
import java.util.Set;
import java.util.TreeSet;

public class HeiseiConvert {

  private static final String START = "2014";
	private static final String END = "26";

	private static Map<String, String> sqrtMap = new HashMap<String, String>();
	private static Map<String, Node> nodeMap = new HashMap<String, HeiseiConvert.Node>();
	private static Set<Node> nodes = new TreeSet<HeiseiConvert.Node>();
	private static int threthold = 100;

	public static void main(String[] args) {
		
		Node root = new Node(START, START, null);
		addToNodes(root);

		int count = 0;
		List<Node> results = new ArrayList<HeiseiConvert.Node>();

		while (true) {
			Iterator<Node> it = nodes.iterator();
			Node node = it.next();
			nodes.remove(node);
			if (node.score > threthold) {
//				System.out.println("score is over" + threthold);
				break;
			}
			
//			System.out.println(node.parentsPath.size() + ":" + node.score + ":" + node.org);
			Node found = node.findChildren(END);
			if (found != null) {
				results.add(found);
				if (found.score + 2 < threthold) {
					threthold = found.score + 2;
				}
			}
			count++;
			if (count > 50000) {// 無限ループ防止のため
				break;
			}
		}
		for (Node result :results) {
			result.printPath();
		}
//		System.out.println("mapSize=" + nodeMap.size());
//		System.out.println("nodeSize=" + nodes.size());
	}

	static {
		for (int i = 2; i < 1000; i++) {
			int pow = i * i;
			sqrtMap.put(String.valueOf(pow), String.valueOf(i));
		}
	}

	private static void addToNodes(Node node) {
		if (node.score > threthold + 2) {
			return;
		}
		Node inMap = nodeMap.get(node.plain);
		if (inMap != null) {
			if (inMap.parentsPath.size() > node.parentsPath.size()) {
				nodeMap.put(node.plain, node);
				nodes.remove(inMap);
				nodes.add(node);
			}
		} else {
			nodeMap.put(node.plain, node);
			nodes.add(node);
		}
	}

	public static class Node implements Comparable<Node> {
		private final String org;
		private final String plain;
		private final int score;
		private final List<Node> parentsPath = new ArrayList<HeiseiConvert.Node>();

		public Node(String org, String plain, Node parent) {
			this.org = org;
			this.plain = plain;
			if (parent != null) {
				parentsPath.addAll(parent.parentsPath);
				parentsPath.add(parent);
			}
			this.score = plain.length() + parentsPath.size();
		}

		public Node findChildren(String end) {
			List<Node> children = createChildNodes(this, plain, new ArrayList<HeiseiConvert.SplitElement>());
			for (Node child : children) {
				addToNodes(child);
				if (child.plain.equals(end)) {
					return child;
				}
			}
			return null;
		}

		public void printPath() {
			StringBuilder str = new StringBuilder();
			for (Node parent : this.parentsPath) {
				if (parent != this.parentsPath.get(0)) {
					str.append(parent.org).append("->");
				}
			}
			str.append(this.org).append("->").append(this.plain);
			System.out.println(str.toString());
			System.out.println(this.parentsPath.size());
		}

		private static List<Node> createChildNodes(Node currentNode, String substr, List<SplitElement> partialSplitElements) {
			List<Node> children = new ArrayList<HeiseiConvert.Node>();
			for (int pos0 = 0; pos0 < substr.length(); pos0++) {
				for (int pos1 = pos0 + 1; pos1 <= substr.length(); pos1++) {
					String innerCode = substr.substring(pos0, pos1);
					if (innerCode.startsWith("0") || innerCode.equals("1")) {
						continue;
					}
					if (sqrtMap.containsKey(innerCode)) {
						children.addAll(createChildNodes(currentNode, substr, pos0, pos1, SplitType.PARENTHESE, partialSplitElements));
					}
					children.addAll(createChildNodes(currentNode, substr, pos0, pos1, SplitType.BRACKET, partialSplitElements));
				}
			}
			return children;
		}

		private static List<Node> createChildNodes(Node currentNode, String substr, int pos0, int pos1, SplitType splitType, List<SplitElement> partialSplitElements) {
			List<SplitElement> splitElements = new ArrayList<HeiseiConvert.SplitElement>();
			splitElements.addAll(partialSplitElements);

			if (pos0 != 0) {
				splitElements.add(new SplitElement(substr.substring(0, pos0), SplitType.NONE));
			}
			splitElements.add(new SplitElement(substr.substring(pos0, pos1), splitType));
			if (pos1 != substr.length()) {
				return createChildNodes(currentNode, substr.substring(pos1), splitElements);
			} else {
				List<Node> children = new ArrayList<HeiseiConvert.Node>();
				StringBuilder codeBuilder = new StringBuilder();
				StringBuilder resultBuilder = new StringBuilder();
				for (SplitElement elem : splitElements) {
					codeBuilder.append(elem.code);
					resultBuilder.append(elem.result);
				}
				Node child = new Node(codeBuilder.toString(), resultBuilder.toString(), currentNode);
				children.add(child);
				return children;
			}
		}

		@Override
		public int compareTo(Node o) {
			int comp1 = this.score - o.score;
			if (comp1 != 0) {
				return comp1;
			}
			int comp2 = this.parentsPath.size() - o.parentsPath.size();
			if (comp2 != 0) {
				return comp2;
			}
			return this.plain.compareTo(o.plain);
		}
	}

	public static class SplitElement {
		private final String code;
		private final String result;
		public SplitElement(String code, SplitType type) {
			if (type == SplitType.PARENTHESE) {
				if (!sqrtMap.containsKey(code)) {
					throw new RuntimeException();
				}
				this.result = sqrtMap.get(code);
				this.code = "(" + code + ")";
			} else if (type == SplitType.BRACKET) {
				BigDecimal num = new BigDecimal(code.substring(0, code.length()));
				this.result = num.multiply(num).toString();
				this.code = "[" + code + "]";
			} else {
				this.code = code;
				this.result = code;
			}
		}
	}

	public static enum SplitType {
		PARENTHESE, BRACKET, NONE;
	}
}