Alternativ lösning 1: Snabb även på lång input

2011-02-18 — Tobias Hill — 4 kommentar(er)

 Anders Ahlgrens lösare var en av de absolut snabbaste! Detta är den första alternativa lösningen till Citerus utmaning på JFokus 2011. Vi kommer att lyfta fram flera lösningar som är värda ett omnämnande.

/**
 * Puzzle where a string is simplified in steps by removing substrings from
 * a given set, to a as-short-as-possible result string.
 *
 * @author Anders Ahlgren
 */
public class EliminationPuzzle {
    /** Used by the transforms to give human readable output. */
    private static final String LEFT_MARKER = "(";
    private static final String RIGHT_MARKER = ")";

    /** Set of characters that might potentially be eliminated. */
    private final Set<Character> eliminableChars = new HashSet<Character>();

    /** Maps the first and last characters (the bracket) of strings that can be
     * removed to the interor characters. */
    private final Map<Bracket,Set<String>> bracketToMiddle = new HashMap<Bracket,Set<String>>();

    /** Memo tracking if a string can or cannot be reduced to empty string. */
    private final Map<String, Boolean> wipeMemo = new HashMap<String,Boolean>();

    /** Memo tracking best solutions for a given string. */
    private final Map<String,Transform> solutionMemo = new HashMap<String,Transform>();

    /** Create a puzzle instance given a collection of strings that can be
     * eliminated in a single step. In game terms, these define the "moves".
     *
     * @param moves collection of strings that can be eliminated
     * in a single step
     */
    public EliminationPuzzle(Collection<String> moves) {
        wipeMemo.put("", Boolean.TRUE);
        solutionMemo.put("", new TrivialWipeout());
        for (String move : moves) {
            addChars(move, eliminableChars);
            memoizeMove(move);
            addBracketMove(move);
        }
    }

    /** Add a specific move to the memos. */
    private void memoizeMove(String move) {
        wipeMemo.put(move, Boolean.TRUE);
        solutionMemo.put(move, new AtomicWipeout(move));
    }

    /** Add a specific move to the bracket map, if applicable. */
    private void addBracketMove(String move) {
        if (move.length() >= 2) {
            Bracket bracket = new Bracket(move);
            Set<String> middleSet = bracketToMiddle.get(bracket);
            if (middleSet == null) {
                middleSet = new HashSet<String>();
                bracketToMiddle.put(bracket, middleSet);
            }
            middleSet.add(move.substring(1, move.length()-1));
        }
    }

    /** Add the characters in the given string to the given set of characters.
     *
     * @param string string containing characters to add to {@code set}
     * @param set set to add the characters in {@code string} to
     */
    private static void addChars(String string, Set<Character> set) {
        int n = string.length();
        for (int i = 0; i < n; i++) {
            set.add(string.charAt(i));
        }
    }

    /** Given an input string, compute an optimal solution. In game terms, the
     * input is a "position" to solve. Note that we say <i>an</i> optimal
     * solution, as it need not be unique, for example if the moves are
     * {@code ab} and {@code bc}, and the position is {@code abc} then there are
     * two solutions that are equally good, namely {@code (ab)c} and
     * {@code a(bc)}, but we will return just one of them.
     *
     * @param input the string to eliminate as much as possible from
     * @return a transformation describing the steps performed
     */
    public Transform solve(String input) {
        Transform result = memoWipeout(input);
        if (result != null) {
            // Clearly, we cannot do better than a complete wipeout
            return result;
        }
        result = solutionMemo.get(input);
        if (result != null) {
            // We have already solved this problem, so reuse solution
            return result;
        }
        result = findBest(input);
        solutionMemo.put(input, result);
        return result;
    }

    /** Inner core of {@code solve}, without handling of memos and where
     * it is known there is no wipeout available.
     */
    private Transform findBest(String input) {
        // One possible outcome is that the first character isn't removed at all
        Transform bulk = solve(input.substring(1));
        Transform result = new SubstringTransform(input, bulk, 1, input.length());
        // If first char is eliminated, but not all characters are, then a
        // proper prefix must be wiped out (by the move that removes the first),
        // so we compute solutions for each corresponding suffix in turn
        int n = Math.min(input.length(), eliminableCharsPrefixLength(input) + 1);
        for (int split = 1; split < n; split++) {
            Transform left = memoWipeout(input.substring(0, split));
            if (left != null) {
                Transform right = solve(input.substring(split));
                if (right.getWeight() < result.getWeight()) {
                    result = new LeftRightTransform(left, right);
                }
            }
        }
        return result;
    }

    /** Return a solution for eliminating the input string completely, or
     * {@code null} if there is no such solution.
     *
     * @param source string to eliminate
     * @return transformation describing the steps performed, or {@code null}
     * if input cannot be reduced to empty string
     */
    private Transform memoWipeout(String source) {
        Boolean wipe = wipeMemo.get(source);
        if (wipe != null) {
            // We have already tried to find a wipeout for this string
            return wipe ? solutionMemo.get(source) : null;
        }
        Transform result = findWipeout(source);
        if (result == null) {
            wipeMemo.put(source, Boolean.FALSE);
        } else {
            wipeMemo.put(source, Boolean.TRUE);
            solutionMemo.put(source, result);
        }
        return result;
    }

    /** Inner core of {@code memoWipeout}, without memo handling. */
    private Transform findWipeout(String source) {
        if (eliminableCharsPrefixLength(source) != source.length()) {
            return null;
        }
        Transform result = findSplitWipeout(source);
        return result != null ? result : findBracketWipeout(source);
    }

    /** Return the length of the longest prefix containing only eliminable chars.
     *
     * @param s string to check
     * @return length of the longest prefix containing only eliminable chars
     */
    private int eliminableCharsPrefixLength(String s) {
        int n = s.length();
        for (int i = 0; i < n; i++) {
            if (!eliminableChars.contains(s.charAt(i))) {
                return i;
            }
        }
        return n;
    }

    /** Find a wipeout for the given string which breaks down into two parallell
     * wipeouts.
     *
     * @param input string to eliminate completely
     * @return transform satisfying the given criteria, or {@code null} if no
     * such exists
     */
    private Transform findSplitWipeout(String input) {
        int n = input.length();
        for (int split = 1; split < n; split++) {
            Transform left = memoWipeout(input.substring(0, split));
            if (left != null) {
                Transform right = memoWipeout(input.substring(split, n));
                if (right != null) {
                    return new LeftRightTransform(left, right);
                }
            }
        }
        return null;
    }

    /** Find a wipeout for the given string where the last step is eliminating
     * both the first and last character in the given input (possibly along with
     * some additional characters). Note that this is the only wipeout which
     * doesn't split into halves.
     *
     * @param input string to eliminate completely
     * @return solution satisfying the given criteria, or {@code null} if no
     * such exists
     */
    private Transform findBracketWipeout(String input) {
        for (String s : getMiddleSet(input)) {
            Transform result = findReduction(input.substring(1, input.length()-1), s);
            if (result != null) {
                return new BracketWipeout(input, result);
            }
        }
        return null;
    }

    /** Given an input, find the set of "middles", that is the moves matching
     * first and last character of input, with the first and last chars dropped.
     */
    private Set<String> getMiddleSet(String input) {
        Set<String> result = input.length() < 2 ? null
                : bracketToMiddle.get(new Bracket(input));
        return result == null ? Collections.<String>emptySet() : result;
    }

    /** 
     * Find a transform from a given source to a given target. This is
     * potentially the most demanding operation for longish targets. However,
     * as it is used then the target is very short (2 chars shorter than the
     * corresponding).
     *
     * @param source string to eliminate down to {@code except}
     * @return transform satisfying the given criteria, or {@code null} if no
     * such exists
     */
    private Transform findReduction(String source, String target) {
        int m = target.length();
        if (m == 0) {
            return memoWipeout(source);
        }
        int n = source.length();
        if (m > n) {
            return null;
        }
        char first = target.charAt(0);
        for (int i = 0; i < n; i++) {
            if (source.charAt(i) == first) {
                Transform left = memoWipeout(source.substring(0, i));
                if (left != null) {
                    String restInput = source.substring(i+1);
                    String restExcept = target.substring(1);
                    Transform right = findReduction(restInput, restExcept);
                    if (right != null) {
                        Transform midRight = new SubstringTransform(source.substring(i), right, 1, n - i);
                        return new LeftRightTransform(left, midRight);
                    }
                }
            }
        }
        return null;
    }

    /** Represents the first and last character of a string. */
    private static final class Bracket {
        private final String s;

        public Bracket(String s) {
            if (s.length() < 2) {
                throw new IllegalArgumentException("No bracket for: " + s);
            }
            this.s = s;
        }

        @Override
        public int hashCode() {
            return (s.charAt(0) << Character.SIZE) + s.charAt(s.length()-1);
        }

        @Override
        public boolean equals(Object obj) {
            if (!(obj instanceof Bracket)) {
                return false;
            }
            Bracket other = (Bracket) obj;
            return s.charAt(0) == other.s.charAt(0) && s.charAt(s.length()-1) == other.s.charAt(other.s.length()-1);
        }                   
    }

    /** Describes a sequence of eliminations (or moves). */
    public interface Transform {

        /** Returns the string at the end of the transform. 
         * 
         * @return string at the end of the transform
         */        
        String getTarget();
        
        /** Returns the same as {@code getTarget().length()}, but probably
         * does so faster.
         * 
         * @return number of characters left at the end of the transform
         */
        int getWeight();
    }

    /** Base class for tranforms that eliminate all characters. */
    private abstract static class Wipeout implements Transform {

        public String getTarget() {
            return "";
        }

        public int getWeight() {
            return 0;
        }
    }

    /** Trivial move of empty to empty. */
    private static class TrivialWipeout extends Wipeout {

        @Override
        public String toString() {
            return "";
        }
    }

    /** Wipeout which is specified directly by a single move. */
    private static class AtomicWipeout extends Wipeout {

        private final String original;

        public AtomicWipeout(String original) {
            this.original = original;
        }

        @Override
        public String toString() {
            return LEFT_MARKER + original + RIGHT_MARKER;
        }
    }

    /** Transform which transforms a substring and leaves rest as-is. */
    private static class SubstringTransform implements Transform {
        private final String original;
        private final Transform bulk;
        private final int from, to;

        public SubstringTransform(String original, Transform bulk, int from, int to) {
            this.original = original;
            this.bulk = bulk;
            this.from = from;
            this.to = to;
        }

        public int getWeight() {
            return from + original.length() - to + bulk.getWeight();
        }

        public String getTarget() {
            return original.substring(0, from) + bulk.getTarget() + original.substring(to);
        }

        @Override
        public String toString() {
            return original.substring(0, from) + bulk.toString() + original.substring(to);
        }                
    }

    /** A wipeout where an atomic move is the last move. */
    private static class BracketWipeout extends SubstringTransform {

        public BracketWipeout(String input, Transform bulk) {
            super(input, bulk, 1, input.length()-1);
        }

        @Override
        public String toString() {
            return LEFT_MARKER + super.toString() + RIGHT_MARKER;
        }

        @Override
        public int getWeight() {
            return 0;
        }

        @Override
        public String getTarget() {
            return "";
        }
    }

    /** A transform which does something to the a prefix of the input, and
     * something else to the rest of the input.
     */
    private static class LeftRightTransform implements Transform {
        private final Transform left, right;
        private final int weight; // Precomputed to avoid deep traverses

        public LeftRightTransform(Transform left, Transform right) {
            this.left = left;
            this.right = right;
            weight = left.getWeight() + right.getWeight();
        }

        public int getWeight() {
            return weight;
        }

        public String getTarget() {
            return left.getTarget() + right.getTarget();
        }

        @Override
        public String toString() {
            return left.toString() + right.toString();
        }
     }
}