Google FooBar challenge 4-2 Maximum Cardinality Matching

foobar_4_2.java

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.HashSet;
import java.util.List;
import java.util.Objects;
import java.util.Set;
import java.util.StringTokenizer;
import java.util.stream.Collectors;
import java.util.stream.Stream;

public class Solution {
    private static class Pair {
        private final int x;
        private final int y;

        public Pair(int x, int y) {
            this.x = x;
            this.y = y;
        }

        public Pair reverse() {
            return new Pair(y, x);
        }

        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;
            Pair pair = (Pair) o;
            return x == pair.x && y == pair.y;
        }

        @Override
        public int hashCode() {
            return Objects.hash(x, y);
        }

        @Override
        public String toString() {
            return "Pair{" + "x=" + x + ", y=" + y + '}';
        }
    }

    public static class Graph {
        protected final Node[] nodes;

        public Graph(int n) {
            this.nodes = new Node[n];
            for (int i = 0; i < this.nodes.length; i++) {
                this.nodes[i] = new Node(i);
            }
        }

        private Graph(Node[] nodes) {
            this.nodes = nodes;
        }

        public void addUndirectedEdge(int v, int w) {
            this.nodes[v].addChild(w);
            this.nodes[w].addChild(v);
        }

        public void addDirectedEdge(int v, int w) {
            this.nodes[v].addChild(w);
            this.nodes[w].parent = v;
        }

        public int root(int node) {
            if (this.nodes[node].parent == -1) {
                return node;
            }
            return root(this.nodes[node].parent);
        }

        public Stream<Integer> nodesToRoot(int node) {
            if (this.nodes[node].parent == -1) {
                return Stream.of(node);
            }
            return Stream.concat(
                    Stream.of(node),
                    this.nodesToRoot(this.nodes[node].parent)
            );
        }

        public int distanceToTreeRoot(int node) {
            if (this.nodes[node].parent == -1) {
                return 0;
            }
            return 1 + this.distanceToTreeRoot(this.nodes[node].parent);
        }

        public Stream<Node> treeNodes(int root) {
            return Stream.concat(
                    Stream.of(nodes[root]),
                    nodes[root].children.stream().flatMap(this::treeNodes)
            );
        }

        public List<Pair> allMatching() {
            List<Pair> matching = new ArrayList<>();
            for (Node node : this.nodes) {
                if (node.matching == -1) continue;
                matching.add(new Pair(node.id, node.matching));
            }
            return matching;
        }

        public Graph contractByBlossom(Blossom b) {
            Node[] nodes = new Node[this.nodes.length];
            for (int i = 0; i < this.nodes.length; i++) {
                Node n = this.nodes[i];
                if (b.contains(i)) {
                    // dont pass information of contracted nodes to contracted graph
                    nodes[i] = new Node(i);
                    continue;
                }
                nodes[i] = new Node(
                        n.id,
                        n.children.stream()
                                .map(c -> b.contains(c) ? b.contractTo : c)
                                .distinct()
                                .collect(Collectors.toList()),
                        n.parent,
                        n.matching
                );
            }
            // contracted node
            Node n = this.nodes[b.contractTo];
            nodes[b.contractTo] = new Node(
                    n.id,
                    b.nodes.stream().flatMap(c -> this.nodes[c].children.stream()) // add up blossom's edges
                            .filter(c -> !b.contains(c)) // exclude edges to blossom self
                            .distinct() // exclude duplicates
                            .collect(Collectors.toList()),
                    b.contains(n.parent) ? b.contractTo : n.parent,
                    b.contains(n.parent) ? b.contractTo : n.matching
            );
            return new Graph(nodes);
        }
    }

    public static class Node {
        private final int id;
        private final List<Integer> children;
        private int parent;
        private int matching;

        public Node(int id) {
            this.id = id;
            this.children = new ArrayList<>();
            this.parent = -1;
            this.matching = -1;
        }

        public Node(int id, List<Integer> children) {
            this.id = id;
            this.children = children;
            this.parent = -1;
            this.matching = -1;
        }

        public Node(int id, List<Integer> children, int parent, int matching) {
            this.id = id;
            this.children = children;
            this.parent = parent;
            this.matching = matching;
        }

        public void addChild(int child) {
            this.children.add(child);
        }

        public Node cloneNode() {
            return new Node(this.id, new ArrayList<>(this.children), this.parent, this.matching);
        }

        public int getMatching() {
            return matching;
        }
    }

    public static int solution(int[] banana_list) {
        // https://en.wikipedia.org/wiki/Maximum_cardinality_matching
        Graph g = new Graph(banana_list.length);

        for (int i = 0; i < g.nodes.length - 1; i++) {
            for (int j = i + 1; j < g.nodes.length; j++) {
                if (simulate(banana_list[i], banana_list[j])) {
                    g.addUndirectedEdge(i, j);
                }
            }
        }
        findMaximumMatching(g);
        return (int) Arrays.stream(g.nodes).filter(node -> node.matching == -1).count();
    }

    /**
     * Finds maximum cardinality matching of general graph, using Blossom algorithm.
     * (NOT bipartite graph, there is a better algorithm)
     * @param g Graph G with matching M
     */
    public static void findMaximumMatching(Graph g) {
        while (true) {
            List<Integer> path = findAugmentingPath(g);
            if (path.isEmpty()) {
                // no more augmenting paths, g has maximum matching
                return;
            }
            // augment matching via path
            assert path.size() % 2 == 0;
            for (int i = 0; i < path.size() / 2; i++) {
                Node n1 = g.nodes[path.get(i * 2)];
                Node n2 = g.nodes[path.get(i * 2 + 1)];
                n1.matching = n2.id;
                n2.matching = n1.id;
            }
        }
    }

    private static class Forest extends Graph {
        private final List<Integer> roots;

        public Forest(int n) {
            super(n);
            this.roots = new ArrayList<>();
        }

        public void addRoot(int root) {
            this.roots.add(root);
        }

        public boolean hasNode(int id) {
            return this.allNodes().anyMatch(n -> n.id == id);
        }

        public Stream<Node> allNodes() {
            return this.roots.stream().flatMap(this::treeNodes);
        }
    }

    private static class Blossom {
        private final Graph g;
        private final List<Integer> nodes;
        public final int contractTo;

        public Blossom(Graph g, List<Integer> nodes) {
            if (nodes.isEmpty()) throw new Error("empty blossom nodes");
            this.g = g;
            this.nodes = nodes;
            this.contractTo = this.root();
        }

        public boolean contains(int node) {
            return this.nodes.contains(node);
        }

        public int root() {
            return this.nodes.stream()
                    .filter(n -> !contains(this.g.nodes[n].matching))
                    .findFirst()
                    .orElse(-1);
        }

        private boolean ensureAlternating(List<Integer> ids) {
            assert ids.size() > 2;
            boolean last = g.nodes[ids.get(0)].matching == ids.get(1);
            for (int i = 1; i < ids.size() - 1; i++) {
                boolean next = g.nodes[ids.get(i)].matching == ids.get(i + 1);
                if (last == next) {
                    return false;
                }
                last = next;
            }
            return true;
        }

        public List<Integer> lift(int to) {
            int innerFrom = root();
            int innerTo = nodes.stream().filter(id -> g.nodes[id].children.contains(to)).findFirst().orElse(-1);
            if (innerTo == -1) throw new Error("could not find inner to node in blossom");

            if (innerFrom == innerTo) {
                return Collections.singletonList(innerFrom);
            }
            final int iFrom = this.nodes.indexOf(innerFrom);
            final int iTo = this.nodes.indexOf(innerTo);

            // try 2 cases and choose valid path
            // case: step: 1
            List<Integer> nodeIds = new ArrayList<>();
            for (int i = iFrom; i != iTo;) {
                nodeIds.add(nodes.get(i));
                i++;
                i %= nodes.size();
            }
            nodeIds.add(innerTo);
            nodeIds.add(to);
            if (ensureAlternating(nodeIds)) {
                return nodeIds.subList(0, nodeIds.size() - 1);
            }
            // case: step: -1
            nodeIds = new ArrayList<>();
            for (int i = iFrom; i != iTo;) {
                nodeIds.add(nodes.get(i));
                i--;
                i += nodes.size();
                i %= nodes.size();
            }
            nodeIds.add(innerTo);
            nodeIds.add(to);
            assert ensureAlternating(nodeIds);
            return nodeIds.subList(0, nodeIds.size() - 1);
        }

        public List<Integer> lift(int from, int to) {
            int innerFrom = nodes.stream().filter(id -> g.nodes[id].children.contains(from)).findFirst().orElse(-1);
            int innerTo = nodes.stream().filter(id -> g.nodes[id].children.contains(to)).findFirst().orElse(-1);

            if (innerFrom == -1 || innerTo == -1) throw new Error("could not find inner from/to node in blossom");
            if (innerFrom == innerTo) {
                return Collections.singletonList(innerFrom);
            }
            final int iFrom = this.nodes.indexOf(innerFrom);
            final int iTo = this.nodes.indexOf(innerTo);

            // try 2 cases and choose valid path
            // case: step: 1
            List<Integer> nodeIds = new ArrayList<>();
            nodeIds.add(from);
            for (int i = iFrom; i != iTo;) {
                nodeIds.add(nodes.get(i));
                i++;
                i %= nodes.size();
            }
            nodeIds.add(innerTo);
            nodeIds.add(to);
            if (ensureAlternating(nodeIds)) {
                return nodeIds.subList(1, nodeIds.size() - 1);
            }
            // case: step: -1
            nodeIds = new ArrayList<>();
            nodeIds.add(from);
            for (int i = iFrom; i != iTo;) {
                nodeIds.add(nodes.get(i));
                i--;
                i += nodes.size();
                i %= nodes.size();
            }
            nodeIds.add(innerTo);
            nodeIds.add(to);
            assert ensureAlternating(nodeIds);
            return nodeIds.subList(1, nodeIds.size() - 1);
        }
    }

    /**
     * Finds augmenting path in G and matching M of G, if any.
     * @param g Graph G with matching M
     * @return Augmenting path P in G, or empty path if none found.
     */
    private static List<Integer> findAugmentingPath(Graph g) {
        Forest f = new Forest(g.nodes.length);
        // unmark all vertices and edges in G, mark all edges of M
        Set<Integer> markedVertices = new HashSet<>();
        Set<Pair> markedEdges = new HashSet<>(g.allMatching());
        for (int i = 0; i < g.nodes.length; i++) {
            if (g.nodes[i].matching == -1) {
                f.addRoot(i);
            }
        }
        while (true) {
            Node vv = f.allNodes()
                    .filter(n -> !markedVertices.contains(n.id))
                    .filter(n -> f.distanceToTreeRoot(n.id) % 2 == 0)
                    .findFirst().orElse(null);
            if (vv == null) {
                return new ArrayList<>();
            }

            Node v = g.nodes[vv.id];
            for (int wi : v.children) {
                Pair edge = new Pair(vv.id, wi);
                if (markedEdges.contains(edge)) continue;
                Node w = g.nodes[wi];

                if (!f.hasNode(w.id)) {
                    int xi = w.matching;
                    f.addDirectedEdge(v.id, wi);
                    f.addDirectedEdge(wi, xi);
                } else {
                    if (f.distanceToTreeRoot(wi) % 2 == 0) {
                        if (f.root(v.id) != f.root(wi)) {
                            List<Integer> vPath = f.nodesToRoot(v.id).collect(Collectors.toList());
                            Collections.reverse(vPath);
                            List<Integer> path = new ArrayList<>(vPath);
                            path.addAll(f.nodesToRoot(wi).collect(Collectors.toList()));
                            return path;
                        } else {
                            List<Integer> vPath = f.nodesToRoot(v.id).collect(Collectors.toList());
                            List<Integer> wPath = f.nodesToRoot(wi).collect(Collectors.toList());
                            for (int i = 0; i < wPath.size(); i++) {
                                int lcaOfVPath = vPath.indexOf(wPath.get(i));
                                if (lcaOfVPath != -1) {
                                    vPath = vPath.subList(0, lcaOfVPath + 1);
                                    wPath = wPath.subList(0, i);
                                    break;
                                }
                            }
                            List<Integer> blossomNodes = new ArrayList<>(vPath);
                            Collections.reverse(wPath);
                            blossomNodes.addAll(wPath);
                            assert blossomNodes.size() > 1 && blossomNodes.size() % 2 == 1;
                            Blossom blossom = new Blossom(g, blossomNodes);
                            Graph contractedGraph = g.contractByBlossom(blossom);
                            List<Integer> path = findAugmentingPath(contractedGraph);
                            if (path.contains(blossom.contractTo)) {
                                int indexBlossom = path.indexOf(blossom.contractTo);
                                if (indexBlossom > 0 && indexBlossom < path.size() - 1) {
                                    int from = path.get(indexBlossom - 1);
                                    int to = path.get(indexBlossom + 1);
                                    List<Integer> partialLiftedPath = blossom.lift(from, to);
                                    List<Integer> liftedPath = new ArrayList<>(path.subList(0, indexBlossom));
                                    liftedPath.addAll(partialLiftedPath);
                                    liftedPath.addAll(path.subList(indexBlossom + 1, path.size()));
                                    return liftedPath;
                                } else {
                                    int to = indexBlossom == 0 ? path.get(1) : path.get(path.size() - 2);
                                    List<Integer> partialLiftedPath = blossom.lift(to);
                                    List<Integer> liftedPath = new ArrayList<>();
                                    if (indexBlossom == 0) {
                                        liftedPath.addAll(partialLiftedPath);
                                        liftedPath.addAll(path.subList(1, path.size()));
                                    } else {
                                        liftedPath.addAll(path.subList(0, path.size() - 1));
                                        Collections.reverse(partialLiftedPath);
                                        liftedPath.addAll(partialLiftedPath);
                                    }
                                    return liftedPath;
                                }
                            } else {
                                return path;
                            }
                        }
                    }
                }
                markedEdges.add(edge);
                markedEdges.add(edge.reverse());
            }
            markedVertices.add(v.id);
        }
    }

    // simulates the thumb wrestling and
    // returns true if it continues forever.
    private static boolean simulate(int b1, int b2) {
        if ((b1 + b2) % 2 == 1) {
            return true;
        }
        if (b1 == b2) {
            return false;
        }
        Set<Integer> bananas = new HashSet<>();
        final int mod = (b1 + b2) / 2;
        if (mod % 2 == 1) {
            return true;
        }
        int b = b1 > mod ? b2 : b1;
        // Not sure why there is a threshold of about log2(n)
        final int THRESHOLD = 40;
        while (b != mod) {
            if (bananas.contains(b) || bananas.size() > THRESHOLD) {
                return true;
            }
            bananas.add(b);

            b *= 2;
            if (b > mod) {
                b = 2 * mod - b;
            }
        }
        return false;
    }
}