2011年9月13日火曜日

GDD2011JP DevQuiz スライドパズルの回答ソースコード

はっきり言って恥ずかしいコードだけど晒します。

基本、双方向幅優先で物理パワーでねじ伏せる作戦。
優先して残すのは、ゴールまでのマンハッタン距離が近いもの。

以下のコードで-Xmx4608M付けてXeonの6G、64ビットUbuntu10.10マシンで40時間かけると4872問解けます(残り128)。
更に残ったものについて、幅増やしたり上限増やしたりして残り49。
さらに、最初の10手はスタートからの遠さ優先その後ゴールまでの近さ優先、次最初の20手は...と繰り返して行って、残り14。あとは手動で小さいサイズの問題に帰着させて解かせた。

一番原始的な気がする。
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.BufferedReader;
import java.util.Hashtable;
import java.util.HashSet;
import java.util.ArrayList;
import java.util.Comparator;
import java.util.Arrays;
import java.util.Enumeration;

public class Panel2 {
    public static final int MAX_NUM = 10000;
    public static final int MAX_COUNT = 100;

    public class InnerPanel {
        int width, height;
        char maxc;
        int maxcount;
        String panel[];
        int distance;
        int zerox, zeroy;
        StringBuffer route;

        /**
          * コンストラクタ(初期状態用).
         */
        public InnerPanel(int width, int height, String panelstr) {
            // 幅高さ
            this.width = width;
            this.height = height;
            // 配列化
            panel = new String[height];
            for (int i = 0; i < height; i++)
                panel[i] = panelstr.substring(width * i, width * (i + 1));
            // 一番でかい文字保存&0位置保存
            maxc = '0';
            char c;
            for (int i = 0; i < panelstr.length(); i++) {
                c = panelstr.charAt(i);
                if (c == '=')
                    continue;
                if (c == '0') {
                    zeroy = i / width;
                    zerox = i % width;
                }
                if (maxc < c)
                    maxc = c;
            }
            maxcount = toInt(maxc);
            route = new StringBuffer();
        }

        /**
          * コンストラクタ(ゴール作成用).
         */
        private InnerPanel(int width, int height) {
            // 幅高さ
            this.width = width;
            this.height = height;
            this.route = new StringBuffer();
        }

        /**
          * ゴール作成.
         */
        public InnerPanel makeGoal() {
            InnerPanel goal = new InnerPanel(width, height);
            goal.maxc = maxc;
            goal.maxcount = maxcount;

            // 整列した状態作成
            goal.panel = new String[height];
            int count = 0;
            String line = null;
            char c;
            for (int i = 0; i < height; i++) {
                line = panel[i];
                StringBuffer sb = new StringBuffer();
                for (int j = 0; j < width; j++) {
                    count++;
                    c = line.charAt(j);
                    if (c == '=') {
                        sb.append(c);
                    } else if (count > maxcount) {
                        sb.append('0');
                        goal.zeroy = i;
                        goal.zerox = j;
                    } else {
                        sb.append(toChar(count));
                    }
                }
                goal.panel[i] = sb.toString();
            }
            return goal;
        }

        /**
         * 文字から数値へ.
         */
        public int toInt(char c) {
            if ('0' <= c && c <= '9')
                return c - '0';
            else
                return c - 'A' + 10;
        }

        /**
         * 数値から文字へ.
         */
        public char toChar(int i) {
            if (i < 10)
                return (char)('0' + i);
            else
                return (char)('A' + i - 10);
        }

        /**
         * パネル内容の表示.
         */
        public void print() {
            System.out.println("======");
            for (int i = 0; i < panel.length; i++)
                System.out.println(panel[i]);
        }

        public int getDistance(InnerPanel target) {
            String p1[] = panel;
            String p2[] = target.panel;

            // 文字->座標のHashtable作成
            Hashtable<Character, Integer> p1hash =
                new Hashtable<Character, Integer>();
            Hashtable<Character, Integer> p2hash =
                new Hashtable<Character, Integer>();
            String p1line = null, p2line = null;
            char c1, c2;
            for (int i = 0; i < p1.length; i++) {
                p1line = p1[i];
                p2line = p2[i];
                for (int j = 0; j < p1line.length(); j++) {
                    c1 = p1line.charAt(j);
                    if (c1 != '=' && c1 != '0') {
                        p1hash.put(c1, i * 10 + j);
                    }
                    c2 = p2line.charAt(j);
                    if (c2 != '=' && c2 != '0')
                        p2hash.put(c2, i * 10 + j);
                }
            }
            char c;
            Integer xy1, xy2;
            int sa, total = 0;
            for (int i = 1; i <= maxcount; i++) {
                c = toChar(i);
                xy1 = p1hash.get(c);
                if (xy1 == null)
                    continue;
                xy2 = p2hash.get(c);
                sa = Math.abs(xy1 / 10 - xy2 / 10) +
                    Math.abs(xy1 % 10 - xy2 % 10);
                total += sa;
            }
            return total;
        }

        /**
         * 距離を計算して保存.
         */
        public int calculateDistance(InnerPanel target) {
            distance = getDistance(target);
            return distance;
        }

        /**
         * String表現.
         */
        public String toString() {
            StringBuffer sb = new StringBuffer();
            for (int i = 0; i < height; i++)
                sb.append(panel[i]);
            return sb.toString();
        }

        /**
         * 次の状態.
         */
        public InnerPanel[] nextPanels() {
            ArrayList<InnerPanel> panel_array = new ArrayList<InnerPanel>();
            char up = 0, down = 0, left = 0, right = 0;
            if (zeroy > 0)
                up = panel[zeroy - 1].charAt(zerox);
            if (zeroy < height - 1)
                down = panel[zeroy + 1].charAt(zerox);
            if (zerox > 0)
                left = panel[zeroy].charAt(zerox - 1);
            if (zerox < width - 1)
                right = panel[zeroy].charAt(zerox + 1);

            try {
                if (up != 0 && up != '=')
                    panel_array.add(makeUp());
                if (down != 0 && down != '=')
                    panel_array.add(makeDown());
                if (left != 0 && left != '=')
                    panel_array.add(makeLeft());
                if (right != 0 && right != '=')
                    panel_array.add(makeRight());
            } catch (IOException ex) {
                ;
            }

            return (InnerPanel[])panel_array.toArray(new InnerPanel[0]);
        }

        /**
         * コピー作成.
         */
        public InnerPanel makeCopy() {
            InnerPanel copy = new InnerPanel(width, height);
            copy.maxc = maxc;
            copy.maxcount = maxcount;
            copy.panel = new String[panel.length];
            for (int i = 0; i < panel.length; i++)
                copy.panel[i] = panel[i];
            copy.distance = distance;
            copy.zerox = zerox;
            copy.zeroy = zeroy;
            copy.route = new StringBuffer(route.toString());
            return copy;
        }

        /**
         * 上へ移動.
         */
        public InnerPanel makeUp() throws IOException {
            InnerPanel copy = makeCopy();
            byte tline[] = copy.panel[zeroy - 1].getBytes("UTF-8");
            byte sline[] = copy.panel[zeroy].getBytes("UTF-8");
            byte b = sline[zerox];
            sline[zerox] = tline[zerox];
            tline[zerox] = b;
            copy.panel[zeroy - 1] = new String(tline, "UTF-8");
            copy.panel[zeroy] = new String(sline, "UTF-8");
            copy.zeroy--;
            copy.route.append('U');
            return copy;
        }

        /**
         * 下へ移動.
         */
        public InnerPanel makeDown() throws IOException {
            InnerPanel copy = makeCopy();
            byte tline[] = copy.panel[zeroy + 1].getBytes("UTF-8");
            byte sline[] = copy.panel[zeroy].getBytes("UTF-8");
            byte b = sline[zerox];
            sline[zerox] = tline[zerox];
            tline[zerox] = b;
            copy.panel[zeroy + 1] = new String(tline, "UTF-8");
            copy.panel[zeroy] = new String(sline, "UTF-8");
            copy.zeroy++;
            copy.route.append('D');
            return copy;
        }

        /**
         * 左へ移動.
         */
        public InnerPanel makeLeft() throws IOException {
            InnerPanel copy = makeCopy();
            byte tline[] = copy.panel[zeroy].getBytes("UTF-8");
            byte b = tline[zerox - 1];
            tline[zerox - 1] = tline[zerox];
            tline[zerox] = b;
            copy.panel[zeroy] = new String(tline, "UTF-8");
            copy.zerox--;
            copy.route.append('L');
            return copy;
        }

        /**
         * 右へ移動.
         */
        public InnerPanel makeRight() throws IOException {
            InnerPanel copy = makeCopy();
            byte tline[] = copy.panel[zeroy].getBytes("UTF-8");
            byte b = tline[zerox + 1];
            tline[zerox + 1] = tline[zerox];
            tline[zerox] = b;
            copy.panel[zeroy] = new String(tline, "UTF-8");
            copy.zerox++;
            copy.route.append('R');
            return copy;
        }
    }

    /**
     * メイン.
     */
    public static void main(String args[]) {
        int skip = 0;
        if (args.length > 0)
            skip = Integer.parseInt(args[0]);
        try {
            InputStreamReader isr = null;
            try {
                isr = new InputStreamReader(System.in, "UTF-8");
                BufferedReader br = null;
                try {
                    br = new BufferedReader(isr);
                    new Panel2().play(br, skip);
                } finally {
                    if (br != null) br.close();
                }
            } finally {
                if (isr != null) isr.close();
            }
        } catch (IOException ex) {
            ex.printStackTrace();
            System.exit(1);
        }
        System.exit(0);
    }

    public int lx = 0;
    public int rx = 0;
    public int ux = 0;
    public int dx = 0;
    public int cases = 0;

    /**
     * コンストラクタ.
     */
    public Panel2() {
    }

    /**
     * 開始.
     */
    public void play(BufferedReader br, int skip) throws IOException {
        String numberstr = br.readLine();
        String numbers[] = numberstr.split(" ");
        lx = Integer.parseInt(numbers[0]);
        rx = Integer.parseInt(numbers[1]);
        ux = Integer.parseInt(numbers[2]);
        dx = Integer.parseInt(numbers[3]);
        cases = Integer.parseInt(br.readLine());

        for (int i = 0; i < skip; i++)
            br.readLine();

        for (int i = 0; i < cases; i++) {
            solve(skip + i + 1, br.readLine());
        }
    }

    /**
     * 1問解く.
     */
    public void solve(int panel_num, String line) {
        String lines[] = line.split(",");
        int width = Integer.parseInt(lines[0]);
        int height = Integer.parseInt(lines[1]);
        InnerPanel start_panel = new InnerPanel(width, height, lines[2]);
        InnerPanel goal_panel = start_panel.makeGoal();
        Hashtable<String, String> route_hash = new Hashtable<String, String>();

        // 距離設定
        start_panel.calculateDistance(goal_panel);
        goal_panel.calculateDistance(start_panel);

        // 既出状態保存
        Hashtable<String, InnerPanel> start_already_hash = new Hashtable<String, InnerPanel>();
        Hashtable<String, InnerPanel> goal_already_hash = new Hashtable<String, InnerPanel>();

        // 先端状態保存
        ArrayList<InnerPanel> start_edge_array = new ArrayList<InnerPanel>();
        Hashtable<String, InnerPanel> start_edge_hash =
            new Hashtable<String, InnerPanel>();
        ArrayList<InnerPanel> start_next_array = new ArrayList<InnerPanel>();
        ArrayList<InnerPanel> goal_edge_array = new ArrayList<InnerPanel>();
        Hashtable<String, InnerPanel> goal_edge_hash =
            new Hashtable<String, InnerPanel>();
        ArrayList<InnerPanel> goal_next_array = new ArrayList<InnerPanel>();

        // 初期状態にする
        start_edge_array.add(start_panel);
        start_edge_hash.put(start_panel.toString(), start_panel);
        start_already_hash.put(start_panel.toString(), start_panel);
        goal_edge_array.add(goal_panel);
        goal_edge_hash.put(goal_panel.toString(), goal_panel);
        goal_already_hash.put(goal_panel.toString(), goal_panel);

        // ここからぶんまわす

        InnerPanel onePanel, newPanel, newPanels[], bingo;
        String sum = null;
        boolean bingo_flg = false;
int loop_count = 0;
        while (true) {

++loop_count;

            if (loop_count > MAX_COUNT) {
                System.out.println(panel_num + ":");
                break;
            }

            // ゴール側からの比較用Hashtableクリア
            start_edge_hash = new Hashtable<String, InnerPanel>();
            start_next_array = new ArrayList<InnerPanel>();


            // スタート状態からの先端状態モノでループ
            for (int i = 0; i < start_edge_array.size(); i++) {
                onePanel = start_edge_array.get(i);
                // 次の状態取得
                newPanels = onePanel.nextPanels();
                for (int j = 0; j < newPanels.length; j++) {
                    newPanel = newPanels[j];
                    sum = newPanel.toString();

                    // 既出なら捨てる
                    if (start_already_hash.containsKey(sum))
                        continue;
                    // 追加
                    start_already_hash.put(sum, newPanel);

                    // 既出とビンゴ?
                    bingo = goal_already_hash.get(sum);
                    if (bingo != null) {
                        checkMate(newPanel, bingo, true, panel_num, route_hash);
                        bingo_flg = true;
                    }
                    // ビンゴ?
                    bingo = goal_edge_hash.get(sum);
                    if (bingo != null) {
                        checkMate(newPanel, bingo, true, panel_num, route_hash);
                        bingo_flg = true;
                    }

                    // 既出じゃなければゴールとの距離計算
                    newPanel.calculateDistance(goal_panel);
                    if (newPanel.distance == 0) {
                        checkMate(newPanel, null, true, panel_num, route_hash);
                        bingo_flg = true;
                    }
                    // 次の先端状態モノに入れる
                    start_next_array.add(newPanel);
                    start_edge_hash.put(sum, newPanel);
                }
            }
            start_edge_array = sort(start_next_array);

            // スタート側からのがビンゴ
            if (bingo_flg)
                break;

            // スタート側からの比較用Hashtableクリア
            goal_edge_hash = new Hashtable<String, InnerPanel>();
            goal_next_array = new ArrayList<InnerPanel>();
            // ゴール側からの先端状態モノでループ
            for (int i = 0; i < goal_edge_array.size(); i++) {
                onePanel = goal_edge_array.get(i);
                // 次の状態取得
                newPanels = onePanel.nextPanels();
                for (int j = 0; j < newPanels.length; j++) {
                    newPanel = newPanels[j];
                    sum = newPanel.toString();

                    // 既出なら捨てる
                    if (goal_already_hash.containsKey(sum))
                        continue;
                    // 追加
                    goal_already_hash.put(sum, newPanel);

                    // 既出とビンゴ?
                    bingo = start_already_hash.get(sum);
                    if (bingo != null) {
                        checkMate(bingo, newPanel, false, panel_num, route_hash);
                        bingo_flg = true;
                    }
                    // ビンゴ?
                    bingo = start_edge_hash.get(sum);
                    if (bingo != null) {
                        checkMate(bingo, newPanel, false, panel_num, route_hash);
                        bingo_flg = true;
                    }

                    // 既出じゃなければ初期との距離計算
                    newPanel.calculateDistance(start_panel);
                    if (newPanel.distance == 0) {
                        checkMate(null, newPanel, true, panel_num, route_hash);
                        bingo_flg = true;
                    }
                    // 次の先端状態モノに入れる
                    goal_next_array.add(newPanel);
                    goal_edge_hash.put(sum, newPanel);
                }
            }
            goal_edge_array = sort(goal_next_array);

            // ゴール側からのがビンゴ
            if (bingo_flg)
                break;
        }
        Enumeration<String> e = route_hash.keys();
        while (e.hasMoreElements()) {
            String key = e.nextElement();
            System.out.println(panel_num + ":" + route_hash.get(key) + ":" + key);
        }
    }

    public ArrayList<InnerPanel> sort(ArrayList<InnerPanel> source) {
        InnerPanel source_array[] = source.toArray(new InnerPanel[0]);
        Arrays.sort(source_array, new PanelCompare());
        ArrayList<InnerPanel> sorted_list = new ArrayList<InnerPanel>();
        for (int i = 0; i < MAX_NUM && i < source_array.length; i++)
            sorted_list.add(source_array[i]);
        return sorted_list;
    }

    public class PanelCompare implements Comparator {
        public int compare(Object o1, Object o2) {
            InnerPanel p1 = (InnerPanel)o1;
            InnerPanel p2 = (InnerPanel)o2;
            return p1.distance - p2.distance;
        }
    }

    /**
     * チェックメイト.
     */
    public void checkMate(InnerPanel start_side, InnerPanel goal_side,
        boolean even, int panel_num, Hashtable<String, String> route_hash) {
        StringBuffer resolv_sb = null;
        if (start_side != null)
            resolv_sb = new StringBuffer(start_side.route.toString());
        else
            resolv_sb = new StringBuffer();

        StringBuffer goal_sb = null;
        if (goal_side != null)
            goal_sb = goal_side.route;
        else
            goal_sb = new StringBuffer();

        char c;
        for (int i = goal_sb.length() - 1; i >= 0; i--) {
            c = goal_sb.charAt(i);
            switch (c) {
                case 'U':
                    resolv_sb.append('D');
                    break;
                case 'D':
                    resolv_sb.append('U');
                    break;
                case 'L':
                    resolv_sb.append('R');
                    break;
                case 'R':
                    resolv_sb.append('L');
                    break;
            }
        }
        String result = resolv_sb.toString();

        // カウント
        int u_count = 0, d_count = 0, l_count = 0, r_count = 0;
        for (int i = 0; i < result.length(); i++) {
            c = result.charAt(i);
            switch (c) {
                case 'U':
                    u_count++;
                    break;
                case 'D':
                    d_count++;
                    break;
                case 'L':
                    l_count++;
                    break;
                case 'R':
                    r_count++;
                    break;
            }
        }
        StringBuffer save_sb = new StringBuffer();
        save_sb.append("U=");
        save_sb.append(u_count);
        save_sb.append(",D=");
        save_sb.append(d_count);
        save_sb.append(",L=");
        save_sb.append(l_count);
        save_sb.append(",R=");
        save_sb.append(r_count);
        route_hash.put(save_sb.toString(), result);
    }
}