First version practical 1 (garbage collection)

4 files changed, 251 insertions, 0 deletions

diff --git a/Practical1/src/nl/camilstaps/cs/GarbageCollectionHelper.java b/Practical1/src/nl/camilstaps/cs/GarbageCollectionHelper.java
new file mode 100644
index 0000000..8367ea2
--- /dev/null
+++ b/Practical1/src/nl/camilstaps/cs/GarbageCollectionHelper.java
@@ -0,0 +1,57 @@
+package nl.camilstaps.cs;
+
+import nl.camilstaps.cs.graphs.Graph;
+import nl.camilstaps.cs.graphs.Node;
+
+import java.util.Scanner;
+
+/**
+ * Solution for the Garbage Collection problem.
+ *
+ * @author Camil Staps
+ */
+class GarbageCollectionHelper {
+
+    /**
+     * Read in a Graph from stdin and print whether we can place N bins to stdout
+     * @param args
+     */
+    public static void main(String[] args) {
+        GarbageCollectionMap graph = new GarbageCollectionMap();
+        int n_bins = readGraph(new Scanner(System.in), graph);
+        System.out.println(graph.canPlaceNBins(n_bins) ? "possible" : "impossible");
+    }
+
+    /**
+     * Read a Graph in the defined format:
+     *
+     *      [n_edges] [n_nodes] [n_bins]
+     *      [fst] [snd]
+     *      [fst] [snd]
+     *      [fst] [snd]
+     *      ...
+     *
+     * @param sc the Scanner to use
+     * @param graph the Graph to build
+     * @return the number of bins
+     */
+    private static int readGraph(Scanner sc, Graph graph) {
+        int n_edges = sc.nextInt();
+        int n_nodes = sc.nextInt();
+        int n_bins  = sc.nextInt();
+
+        for (int i = 1; i <= n_nodes; i++) {
+            graph.addNode(new Node(i));
+        }
+
+        for (int i = 0; i < n_edges; i++) {
+            int fst = sc.nextInt();
+            int snd = sc.nextInt();
+            graph.getNode(fst - 1).getNeighbours().add(graph.getNode(snd - 1));
+            graph.getNode(snd - 1).getNeighbours().add(graph.getNode(fst - 1));
+        }
+
+        return n_bins;
+    }
+
+}
diff --git a/Practical1/src/nl/camilstaps/cs/GarbageCollectionMap.java b/Practical1/src/nl/camilstaps/cs/GarbageCollectionMap.java
new file mode 100644
index 0000000..e700cb0
--- /dev/null
+++ b/Practical1/src/nl/camilstaps/cs/GarbageCollectionMap.java
@@ -0,0 +1,80 @@
+package nl.camilstaps.cs;
+
+import nl.camilstaps.cs.graphs.Graph;
+import nl.camilstaps.cs.graphs.Node;
+
+import java.util.*;
+import java.util.stream.Collectors;
+
+/**
+ * The garbage collection map is simply a Graph with extended functionality.
+ *
+ * @author Camil Staps
+ */
+class GarbageCollectionMap extends Graph {
+
+    public GarbageCollectionMap() {
+        super();
+    }
+
+    private GarbageCollectionMap(Graph g) {
+        super(g);
+    }
+
+    /**
+     * We want to choose a node with few neighbours, to minimise the branching factor at each reduction step.
+     * @return the node with the fewest neighbours
+     */
+    protected Node bestNode() {
+        Node best = null;
+        for (Node n : nodes)
+            if (best == null || best.getNeighbours().size() > n.getNeighbours().size())
+                best = n;
+        return best;
+    }
+
+    /**
+     * Check if we can place N bins in this map.
+     *
+     *  - Choose the {@link #bestNode} and try if we can place N-1 bins if we remove this node and all its neighbours
+     *  - If not, remove the node and try for all its neighbours the same thing.
+     *  - If it doesn't work for the best node or for one of its neighbours, it is impossible to place N bins.
+     *
+     * @param bins the number of bins we want to place
+     * @return whether this is possible
+     */
+    protected boolean canPlaceNBins(int bins) {
+        if (this.nodes.size() < bins)
+            return false;
+        if (bins < 1)
+            return true;
+
+        // A queue with the nodes we want to check
+        Queue<Node> q = new LinkedList<>();
+        boolean first_go = true;
+
+        q.add(bestNode());
+        while (!q.isEmpty()) {
+            Node n = q.remove();
+            removeNode(n);
+
+            // Recursively check the subgraph without the node we're checking and its children
+            GarbageCollectionMap gcm = new GarbageCollectionMap(this);
+            gcm.removeNodes(n.getNeighbours());
+            if (gcm.canPlaceNBins(bins - 1))
+                return true;
+
+            // Check children
+            if (first_go)
+                q.addAll(n.getNeighbours().stream().filter(nodes::contains).collect(Collectors.toList()));
+
+            // Restore graph
+            addNode(n);
+            nodes.remove(n);
+            first_go = false;
+        }
+
+        return false;
+    }
+
+}
diff --git a/Practical1/src/nl/camilstaps/cs/graphs/Graph.java b/Practical1/src/nl/camilstaps/cs/graphs/Graph.java
new file mode 100644
index 0000000..ef89258
--- /dev/null
+++ b/Practical1/src/nl/camilstaps/cs/graphs/Graph.java
@@ -0,0 +1,68 @@
+package nl.camilstaps.cs.graphs;
+
+import java.util.*;
+import java.util.stream.Collectors;
+
+/**
+ * A Graph is a list of Nodes.
+ *
+ * @author Camil Staps
+ */
+public class Graph {
+    protected final List<Node> nodes;
+
+    public Graph() {
+        this.nodes = new ArrayList<>();
+    }
+
+    /**
+     * Create a copy of another Graph, also copying all the Nodes
+     * @param g
+     */
+    public Graph(Graph g) {
+        this();
+        this.nodes.addAll(g.nodes.stream().map(Node::new).collect(Collectors.toList()));
+    }
+
+    /**
+     * Add a Node
+     * @param node
+     */
+    public void addNode(Node node) {
+        this.nodes.add(node);
+    }
+
+    /**
+     * Get a Node
+     * @param i
+     * @return
+     */
+    public Node getNode(int i) {
+        return this.nodes.get(i);
+    }
+
+    /**
+     * Remove a node
+     * @param n
+     */
+    public void removeNode(Node n) {
+        nodes.remove(n);
+    }
+
+    /**
+     * Remove a list of nodes, and update all references
+     * @param ns
+     */
+    public void removeNodes(Collection<Node> ns) {
+        nodes.removeAll(ns);
+    }
+
+    public String toString() {
+        StringBuilder sb = new StringBuilder("Graph:");
+        for (Node n : nodes) {
+            sb.append("\n  ").append(n).append(":   ");
+            for (Node n2 : n.getNeighbours()) sb.append(" - ").append(n2);
+        }
+        return sb.toString();
+    }
+}
diff --git a/Practical1/src/nl/camilstaps/cs/graphs/Node.java b/Practical1/src/nl/camilstaps/cs/graphs/Node.java
new file mode 100644
index 0000000..87471e8
--- /dev/null
+++ b/Practical1/src/nl/camilstaps/cs/graphs/Node.java
@@ -0,0 +1,46 @@
+package nl.camilstaps.cs.graphs;
+
+import java.util.ArrayList;
+import java.util.List;
+
+/**
+ * A Node is a simple point in a graph, with references to its neighbours. It holds an integer 'content' which can act
+ * as an identifier.
+ *
+ * @author Camil Staps
+ */
+public class Node {
+    private final int content;
+    private final List<Node> neighbours = new ArrayList<>();
+
+    public Node(int content) {
+        this.content = content;
+    }
+
+    /**
+     * Create a copy of another Node
+     * @param copy
+     */
+    public Node(Node copy) {
+        this.content = copy.content;
+        this.neighbours.addAll(copy.neighbours);
+    }
+
+    public List<Node> getNeighbours() {
+        return neighbours;
+    }
+
+    public String toString() {
+        return "<" + content + ">";
+    }
+
+    /**
+     * Nodes are equal if their identifiers are equal
+     * @param another
+     * @return
+     */
+    public boolean equals(Object another) {
+        return !(another == null || another.getClass() != this.getClass()) &&
+                content == (((Node) another).content);
+    }
+}