diff options
-rw-r--r-- | .gitignore | 48 | ||||
-rw-r--r-- | Practical1/src/nl/camilstaps/cs/GarbageCollectionHelper.java | 57 | ||||
-rw-r--r-- | Practical1/src/nl/camilstaps/cs/GarbageCollectionMap.java | 80 | ||||
-rw-r--r-- | Practical1/src/nl/camilstaps/cs/graphs/Graph.java | 68 | ||||
-rw-r--r-- | Practical1/src/nl/camilstaps/cs/graphs/Node.java | 46 | ||||
-rw-r--r-- | Practical1/testcases.py | 19 |
6 files changed, 318 insertions, 0 deletions
@@ -27,3 +27,51 @@ *.synctex.gz _minted-*/ +# Covers JetBrains IDEs: IntelliJ, RubyMine, PhpStorm, AppCode, PyCharm, CLion, Android Studio + +*.iml + +## Directory-based project format: +.idea/ +# if you remove the above rule, at least ignore the following: + +# User-specific stuff: +# .idea/workspace.xml +# .idea/tasks.xml +# .idea/dictionaries +# .idea/shelf + +# Sensitive or high-churn files: +# .idea/dataSources.ids +# .idea/dataSources.xml +# .idea/sqlDataSources.xml +# .idea/dynamic.xml +# .idea/uiDesigner.xml + +# Gradle: +# .idea/gradle.xml +# .idea/libraries + +# Mongo Explorer plugin: +# .idea/mongoSettings.xml + +## File-based project format: +*.ipr +*.iws + +## Plugin-specific files: + +# IntelliJ +*/out/ + +# mpeltonen/sbt-idea plugin +.idea_modules/ + +# JIRA plugin +atlassian-ide-plugin.xml + +# Crashlytics plugin (for Android Studio and IntelliJ) +com_crashlytics_export_strings.xml +crashlytics.properties +crashlytics-build.properties +fabric.properties 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); + } +} diff --git a/Practical1/testcases.py b/Practical1/testcases.py new file mode 100644 index 0000000..7c9c497 --- /dev/null +++ b/Practical1/testcases.py @@ -0,0 +1,19 @@ +rows, cols, bins = 3, 3, 5 +rows, cols, bins = 4, 4, 7 +#rows, cols, bins = 5, 5, 10 +#rows, cols, bins = 7, 7, 18 +rows, cols, bins = 8, 8, 23 +#rows, cols, bins = 9, 9, 28 +#rows, cols, bins = 10, 10, 36 +#rows, cols, bins = 11, 11, 42 + +print 3 * (rows - 1) * (cols - 1) + (rows - 1) + (cols - 1), rows * cols, bins +for r in range(rows - 1): + for c in range(r * cols + 1, (r+1) * cols): + print c, c + 1 + print c, c + cols + print c, c + cols + 1 + print (r+1) * cols, (r+2) * cols +for c in range(rows * cols - cols + 1, rows * cols): + print c, c + 1 + |