Lift

Lift.java

package common.search;

import yk.Util;

import java.util.*;

import static yk.Util.list;
import static yk.Util.map;

public class Lift {
    public static void main(String[] args) {
        
        State start = new State(1, map(
                Children.Митя, 1,

                Children.Петя, 2,
                Children.Тёма, 2,
                Children.Саша, 2,
                Children.Витя, 3,

                Children.Маша, 4,
                Children.Паша, 4
        ));

        final State end = new State(0, map(
                Children.Митя, 2,

                Children.Петя, 4,
                Children.Тёма, 2,
                Children.Саша, 3,
                Children.Витя, 2,

                Children.Маша, 1,
                Children.Паша, 4
                ));
        
        Search<State, Action> search = new Search<State, Action>(start) {
            @Override
            public List<Action> getActions(Node<State, Action> node) {
                List<Action> result = new ArrayList<Action>();
                if (node.state.liftFloor < 4) result.add(new Action(true));
                if (node.state.liftFloor > 1) result.add(new Action(false));
                for (Children c : node.state.floors.get(node.state.liftFloor)) {
                    if (node.state.liftFloor < 4) result.add(new Action(true, c));
                    if (node.state.liftFloor > 1) result.add(new Action(false, c));
                    for (Children c2 : node.state.floors.get(node.state.liftFloor)) {
                        if (c2 != c) {
                            if (node.state.liftFloor < 4) result.add(new Action(true, c, c2));
                            if (node.state.liftFloor > 1) result.add(new Action(false, c, c2));
                        }
                    }
                }
                return result;
            }

            @Override
            public int compare(Node<State, Action> a, Node<State, Action> b) {
                return a.state.distanceTo(end) - b.state.distanceTo(end);
            }

            @Override
            public boolean isEnd(State state) {
                return state.distanceTo(end) == 0;
            }

            @Override
            public State genState(State state, Action action) {
                State result = new State(state);
                int oldFloor = state.liftFloor;
                int newFloor = state.liftFloor + (action.up ? 1 : -1);
                result.liftFloor = newFloor;
                for (Children p : action.passangers) {
                    result.floors.get(oldFloor).remove(p);
                    result.floors.get(newFloor).add(p);
                }
                return result;
            }
        };
        for (Search.Node<State, Action> node : search.popNext(100)) {
            if (node.action != null) System.out.println(node.action);
        }
    }

    private static class State {
        int liftFloor;
        List<Set<Children>> floors = new ArrayList<Set<Children>>();
        private State(int liftFloor, Map<Children, Integer> state) {
            floors = list();
            for (int i = 0; i < 5; i++) floors.add(new HashSet<Children>());
            this.liftFloor = liftFloor;
            for (Map.Entry<Children, Integer> entry : state.entrySet()) {
                floors.get(entry.getValue()).add(entry.getKey());
            }
        }

        State(State s) {
            liftFloor = s.liftFloor;
            floors = list();
            for (int i = 0; i < 5; i++) floors.add(new HashSet<Children>());
            for (int i = 0; i < floors.size(); i++) floors.get(i).addAll(s.floors.get(i));
        }

        int getFloor(Children c) {
            for (int i = 0; i < floors.size(); i++) for (Children cc : floors.get(i)) if (cc == c) return i;
            throw new Error("can't find " + c);
        }

        public int distanceTo(State end) {
            int result = 0;
            for (Children c : Children.values()) result += Math.abs(end.getFloor(c) - getFloor(c));
            return result;
        }
    }
    
    private static class Action {
        boolean up;
        List<Children> passangers;

        private Action(boolean up, Children... passangers) {
            this.up = up;
            if (passangers.length > 2) throw new Error("too much " + passangers.length);
            this.passangers = Arrays.asList(passangers);
        }

        @Override
        public String toString() {
            return (up ? "вверх" : "вниз") + " " + (passangers.isEmpty() ? "пустой" : Util.append(passangers, ", "));
        }
    }
    
    private static enum Children {
        Митя,
        
        Петя,
        Тёма,
        Саша,
        Витя,
        
        Маша,
        Паша

    }


}

Lift2.java

package lift;

import java.util.*;

import static lift.Util.list;
import static lift.Util.map;
import static lift.Util.set;

public class Lift2 {
    public static void main(String[] args) {
        
        State start = new State(4, 2, map(
                Children.Мужчина, 2,

                Children.Женщина, 5,
                Children.Девочка, 5,
                Children.Мальчик, 8,
                Children.Кошка, 7
        ));

        final State end = new State(0, 0, map(
                Children.Мужчина, 8,

                Children.Женщина, 3,
                Children.Девочка, 6,
                Children.Мальчик, 2,
                Children.Кошка, 1
                ));
        
        Search<State, Action> search = new Search<State, Action>(start) {
            private List<Action> getLift1(Node<State, Action> node) {
                List<Action> result = new ArrayList<Action>();
                if (node.state.lift1Floor < 8) result.add(new Action(true, list()));
                if (node.state.lift1Floor > 1) result.add(new Action(false, list()));
                for (Children c : node.state.floors.get(node.state.lift1Floor)) {
                    if (node.state.lift1Floor < 8) result.add(new Action(true, list(c)));
                    if (node.state.lift1Floor > 1) result.add(new Action(false, list(c)));
                    for (Children c2 : node.state.floors.get(node.state.lift1Floor)) {
                        if (c2 != c) {
                            if (node.state.lift1Floor < 8) result.add(new Action(true, list(c, c2)));
                            if (node.state.lift1Floor > 1) result.add(new Action(false, list(c, c2)));
                        }
                    }
                }
                return result;
            }
            
            private List<Action> getLift2(Node<State, Action> node, Action l1) {
                List<Action> result = new ArrayList<Action>();
                if (node.state.lift2Floor < 8) result.add(new Action(l1, true, list()));
                if (node.state.lift2Floor > 1) result.add(new Action(l1, false, list()));
                for (Children c : node.state.floors.get(node.state.lift2Floor)) if (!l1.passangers1.contains(c)){
                    if (node.state.lift2Floor < 8) result.add(new Action(l1, true, list(c)));
                    if (node.state.lift2Floor > 1) result.add(new Action(l1, false, list(c)));
                }
                return result;
            }
            
            @Override
            public List<Action> getActions(Node<State, Action> node) {
                List<Action> result = list();
                for (Action a : getLift1(node)) result.addAll(getLift2(node, a));
                return result;
            }

            @Override
            public int compare(Node<State, Action> a, Node<State, Action> b) {
                return (int) Math.signum((a.w-b.w)*2 + a.state.distanceTo(end) - b.state.distanceTo(end));
            }

            @Override
            public boolean isEnd(State state) {
                return state.distanceTo(end) == 0;
            }

            @Override
            public State genState(State state, Action action) {
                State result = new State(state);

                int old1Floor = state.lift1Floor;
                int new1Floor = state.lift1Floor + (action.firstUp ? 1 : -1);
                result.lift1Floor = new1Floor;
                for (Children p : action.passangers1) {
                    result.floors.get(old1Floor).remove(p);
                    result.floors.get(new1Floor).add(p);
                }

                int old2Floor = state.lift2Floor;
                int new2Floor = state.lift2Floor + (action.secondUp ? 1 : -1);
                result.lift2Floor = new2Floor;
                for (Children p : action.passangers2) {
                    result.floors.get(old2Floor).remove(p);
                    result.floors.get(new2Floor).add(p);
                }
                return result;
            }
        };
        for (int i = 0; i < 100; i++) {
            List<Search.Node<State, Action>> res = search.popNext(100);
            if (res.size() - 1 <= 11)
            for (Search.Node<State, Action> node : res){
                if (node.action != null) {
                    System.out.println();
                    System.out.print("лифт 1, этаж " + node.prevNode.state.lift1Floor + ", движение: ");
                    System.out.println(node.action.l1());
                    System.out.print("лифт 2, этаж " + node.prevNode.state.lift2Floor + ", движение: ");
                    System.out.println(node.action.l2());
                }
            }
            System.out.println("--" + (res.size() - 1));
        }
    }

    private static class State {
        int lift1Floor;
        int lift2Floor;
        List<Set<Children>> floors = new ArrayList<Set<Children>>();
        
        private State(int liftFloor, int lift2Floor, Map<Children, Integer> state) {
            floors = list();
            for (int i = 0; i < 9; i++) floors.add(new HashSet<Children>());
            this.lift1Floor = liftFloor;
            this.lift2Floor = lift2Floor;
            for (Map.Entry<Children, Integer> entry : state.entrySet()) {
                floors.get(entry.getValue()).add(entry.getKey());
            }
        }

        State(State s) {
            lift1Floor = s.lift1Floor;
            lift2Floor = s.lift2Floor;
            floors = list();
            for (int i = 0; i < 9; i++) floors.add(new HashSet<Children>());
            for (int i = 0; i < floors.size(); i++) floors.get(i).addAll(s.floors.get(i));
        }

        int getFloor(Children c) {
            for (int i = 0; i < floors.size(); i++) for (Children cc : floors.get(i)) if (cc == c) return i;
            throw new Error("can't find " + c);
        }

        public int distanceTo(State end) {
            int result = 0;
            for (Children c : Children.values()) result += Math.abs(end.getFloor(c) - getFloor(c));
            return result;
        }

        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;

            State state = (State) o;

            if (lift1Floor != state.lift1Floor) return false;
            if (lift2Floor != state.lift2Floor) return false;
            if (!floors.equals(state.floors)) return false;

            return true;
        }

        @Override
        public int hashCode() {
            int result = lift1Floor;
            result = 31 * result + lift2Floor;
            result = 31 * result + floors.hashCode();
            return result;
        }
    }
    
    private static class Action {
        boolean firstUp;
        boolean secondUp;
        List<Children> passangers1;
        List<Children> passangers2;

        private Action(boolean up, List c1) {
            this.firstUp = up;
            if (c1.size() > 2) throw new Error("too much for 1" + c1.size());
            this.passangers1 = c1;
        }

        private Action(Action firstLift, boolean up2, List c2) {
            this.firstUp = firstLift.firstUp;
            this.secondUp = up2;
            if (c2.size() > 1) throw new Error("too much for 2 " + c2.size());
            this.passangers1 = firstLift.passangers1;
            this.passangers2 = c2;
        }

        public String l1() {
            return (firstUp ? "вверх" : "вниз") + " " + (passangers1.isEmpty() ? "пустой" : Util.append(passangers1, ", "));
        }

        public String l2() {
            return (secondUp ? "вверх" : "вниз") + " " + (passangers2.isEmpty() ? "пустой" : Util.append(passangers2, ", "));
        }
    }
    
    private static enum Children {
        Мужчина,
        Женщина,
        Девочка,
        Мальчик,
        Кошка,

    }


}

Search.java

package lift;

import java.util.*;

/**
 * Kravchik Yuri
 * Date: 09.01.12
 * Time: 10:34 PM
 */
//TO DO max edge size. List of actions?
abstract public class Search<STATE, ACTION> implements Comparator<Search.Node<STATE, ACTION>> {
    public boolean breadthFirst = true;
    protected boolean keepActionless;

    protected List<Node<STATE, ACTION>> edge = new ArrayList<Node<STATE, ACTION>>();
    public Map<STATE, Node<STATE, ACTION>> seen = new HashMap<STATE, Node<STATE, ACTION>>();
    public int iterations;

    /**
     * @return list of possible actions from given state
     */
    abstract public List<ACTION> getActions(Node<STATE, ACTION> node);

    abstract public boolean isEnd(STATE state);

    /**
     * @return new state, or null if new state is impossible or 'bad'
     */
    abstract public STATE genState(STATE state, ACTION action);

    /**
     * Override this to add an heuristic (A* would use distance to the target state as heuristics)
     */
    public int compare(Node<STATE, ACTION> a, Node<STATE, ACTION> b) {
        return breadthFirst ? a.w - b.w : b.w - a.w;
    }

    public Search(STATE begin) {
        iterations = 0;
        edge.add(new Node<STATE, ACTION>(null, null, begin));
    }

    public List<Node<STATE, ACTION>> popNext(int limit) {
        next(limit);
        return popResult();
    }

    private int curLimit;

    public void next(int limit) {
        curLimit += limit;
        while (!edge.isEmpty()) {
            Node<STATE, ACTION> current;
            iterations++;
            Collections.sort(edge, this);
            current = edge.get(0);
            if (isEnd(current.state)) break;
            if (current.w >= curLimit) break;
            edge.remove(0);
            List<ACTION> actions = getActions(current);
            if (keepActionless && actions.isEmpty()) {
                edge.add(current);
                current.w++;
            }
            for (ACTION action : actions) {
                STATE state = genState(current.state, action);
                if (state != null) {
                    Node<STATE, ACTION> newNode = new Node<STATE, ACTION>(current, action, state);
                    Node<STATE, ACTION> oldNode = seen.get(newNode.state);
                    if (oldNode == null || newNode.w + 1 < oldNode.w) {
                        edge.add(newNode);
                        seen.put(newNode.state, newNode);
                    }
                }
            }
        }
    }

    public List<Node<STATE, ACTION>> popResult() {
        List<Node<STATE, ACTION>> result = getResult();
        if (!edge.isEmpty()) edge.remove(0);
        return result;
    }

    public List<Node<STATE, ACTION>> getResult() {
        List<Node<STATE, ACTION>> result = new ArrayList<Node<STATE, ACTION>>();
        Node<STATE, ACTION> current = edge.isEmpty() ? null : edge.get(0);
        if (current == null) return null;
        while (current.prevNode != null) {
            result.add(0, current);
            current = current.prevNode;
        }
        result.add(0, current);
        return result;
    }

    public static class Node<STATE, ACTION> {
        public STATE state;
        public ACTION action;//action that leads to this state
        public Node<STATE, ACTION> prevNode;//node with state from which we get here with 'action'
        public int w;//number of steps taken on the route from the start

        public Node(Node<STATE, ACTION> prevNode, ACTION action, STATE state) {
            this.action = action;
            this.prevNode = prevNode;
            if (prevNode != null) this.w = prevNode.w + 1;
            this.state = state;
        }

        @Override
        public String toString() {
            return "Node{action=" + action + ", prevNode.state=" + (prevNode == null ? "null" : prevNode.state) + ", w=" + w + ", state=" + state + "}\n";
        }
    }

}

Util.java

package yk;

import java.util.*;

/**
 * Kravchik Yuri
 * Date: 11/24/11
 * Time: 12:43 AM
 */
public class Util {

    public static <K, V> Map<K, V> ext(Map<K, V> m, K k, V v) {
        Map<K, V> result = new HashMap<K, V>(m);
        result.put(k, v);
        return result;
    }

    public static <T> Set<T> subSet(Set<T> nn, T n) {
        Set<T> result = new LinkedHashSet<T>(nn);
        result.remove(n);
        return result;
    }

    public static float format(float v, int base) {
        float b = (float) Math.pow(10, base);
        return ((int) (v*b))/b;
    }

    public static <T> T car(List<T> list) {
        return list.get(0);
    }

    public static <T> List<T> cdr(List<T> list) {
        if (list.size() == 1) return new ArrayList<T>();
        return list.subList(1, list.size());
    }

    public static <T> Collection<T> sub(Collection<T> s, T item) {
        Set<T> result = new HashSet<T>();
        for (T t : s) if (t != item) result.add(t);
        return result;
    }

    public static <T> T car(Collection<T> list) {
        return list.iterator().next();
        //Iterator<T> it = list.iterator();
        //return it.hasNext() ? it.next() : null;
    }

    public static <T> Set<T> copy(Set<T> set) {
        return new LinkedHashSet<T>(set);
    }

    public static <K, V> Map<K, V> copy(Map<K, V> map) {
        return new HashMap<K, V>(map);
    }

    public static <K, V> Map<K, V> copy(Map<K, V> m, K k, V v, Object... other) {
        Map<K, V> result = copy(m);
        result.put(k, v);
        for (int i = 0; i < other.length; i += 2) {
            result.put((K)other[i], (V)other[i + 1]);
        }
        return result;
    }



    public static <T> Collection<T> cdr(Collection<T> list) {
        return sub(list, car(list));
    }

    public static String append(Collection ss, String appender) {
        return append("", ss, appender);
    }

    public static String append(String prefix, Collection ss, String appender) {
        boolean first = true;
        StringBuilder sb = new StringBuilder();
        for (Object o : ss) {
            if (first) first = false;
            else sb.append(appender);
            sb.append(prefix).append(o.toString());
        }
        return sb.toString();
    }

    public static <T> Set<T> set(T... tt) {
        return new LinkedHashSet<T>(Arrays.asList(tt));
    }

    public static <T> ArrayList<T> list(T... tt) {
        return new ArrayList<T>(Arrays.asList(tt));
    }

    public static <T> Set<T> set(Set<T> s) {
        return new LinkedHashSet<T>(s);
    }

    public static <K, V> Map<K, V> map(K k, V v, Object... oo) {
        Map<K, V> result = new HashMap<K, V>();
        result.put(k, v);
        for (int i = 0; i < oo.length; i+=2) result.put((K)oo[i], (V)oo[i+1]);
        return result;
    }

    public static <K, V> Map<K, V> map() {
        return new HashMap<K, V>();
    }

    public static <T> Set<T> addIf(Set<T> old, Set<T> toAdd) {
        if (toAdd == null) return old;
        if (old == null) return toAdd;
        old.addAll(toAdd);
        return old;
    }

    public static float sqr(float x) {
        return x * x;
    }

}