diff options
47 files changed, 1063 insertions, 118 deletions
@@ -75,3 +75,6 @@ com_crashlytics_export_strings.xml crashlytics.properties crashlytics-build.properties fabric.properties + +# Specials +!**/samples/*.out diff --git a/Practical1/src/nl/camilstaps/cs/GarbageCollectionHelper.java b/Practical1/src/nl/camilstaps/cs/GarbageCollectionHelper.java index 8367ea2..282cfb3 100644 --- a/Practical1/src/nl/camilstaps/cs/GarbageCollectionHelper.java +++ b/Practical1/src/nl/camilstaps/cs/GarbageCollectionHelper.java @@ -17,9 +17,9 @@ class GarbageCollectionHelper { * @param args */ public static void main(String[] args) { - GarbageCollectionMap graph = new GarbageCollectionMap(); + Graph graph = new Graph(); int n_bins = readGraph(new Scanner(System.in), graph); - System.out.println(graph.canPlaceNBins(n_bins) ? "possible" : "impossible"); + System.out.println(graph.maximumIndependentSetSize() >= n_bins ? "possible" : "impossible"); } /** @@ -47,8 +47,8 @@ class GarbageCollectionHelper { 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)); + graph.getNode(fst - 1).getNeighbourhood().add(graph.getNode(snd - 1)); + graph.getNode(snd - 1).getNeighbourhood().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 deleted file mode 100644 index e700cb0..0000000 --- a/Practical1/src/nl/camilstaps/cs/GarbageCollectionMap.java +++ /dev/null @@ -1,80 +0,0 @@ -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 index ef89258..0da1924 100644 --- a/Practical1/src/nl/camilstaps/cs/graphs/Graph.java +++ b/Practical1/src/nl/camilstaps/cs/graphs/Graph.java @@ -9,19 +9,261 @@ import java.util.stream.Collectors; * @author Camil Staps */ public class Graph { - protected final List<Node> nodes; + private final List<Node> nodes; + private final Stack<List<Node>> removedStack = new Stack<>(); public Graph() { this.nodes = new ArrayList<>(); + restorePoint(); } - /** - * 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())); + public Graph(List<Node> nodes) { + this.nodes = nodes; + restorePoint(); + } + + public int maximumIndependentSetSize() { + if (nodes.size() <= 1) + return nodes.size(); + + int mis = 0; + restorePoint(); + + Graph partition = findPartition(); + if (partition.size() == size()) { + Collections.sort(nodes); + Node A = nodes.get(0); + Collections.sort(A.getNeighbourhood(), Collections.reverseOrder()); + Node B = A.getNeighbourhood().get(0); + + int try_1, try_2; + switch (A.getDegree()) { + case 1: + removeNodes(A.getInclusiveNeighbourhood()); + mis = 1 + maximumIndependentSetSize(); + break; + case 2: + Node B_ = A.getNeighbourhood().get(1); + if (B.getNeighbourhood().contains(B_)) { + removeNodes(A.getInclusiveNeighbourhood()); + mis = 1 + maximumIndependentSetSize(); + } else { + restorePoint(); + removeNodes(B.getInclusiveNeighbourhood()); + removeNodes(B_.getInclusiveNeighbourhood()); + try_1 = 2 + maximumIndependentSetSize(); + restore(); + removeNodes(A.getInclusiveNeighbourhood()); + try_2 = 1 + maximumIndependentSetSizeWith2From(A.getSecondNeighbourhood()); + mis = Math.max(try_1, try_2); + } + break; + case 3: + removeNode(A); + try_1 = maximumIndependentSetSizeWith2From(A.getNeighbourhood()); + removeNodes(A.getNeighbourhood()); + try_2 = 1 + maximumIndependentSetSize(); + mis = Math.max(try_1, try_2); + break; + default: + if (A.dominates(B)) { + removeNode(B); + mis = maximumIndependentSetSize(); + } else { + removeNode(B); + try_1 = maximumIndependentSetSize(); + removeNodes(B.getNeighbourhood()); + try_2 = 1 + maximumIndependentSetSize(); + mis = Math.max(try_1, try_2); + } + break; + } + } else { + mis = partition.maximumIndependentSetSize(); + removeNodes(partition.nodes); + mis += maximumIndependentSetSize(); + } + + restore(); + return mis; + } + + private int maximumIndependentSetSizeWith1From(Node s_1, Node s_2) { + assert s_1.getDegree() <= s_2.getDegree(); + + int mis = 0; + restorePoint(); + + if (s_1.getDegree() <= 1) { + mis = maximumIndependentSetSize(); + } else if (s_1.getNeighbourhood().contains(s_2)) { + if (s_1.getDegree() <= 3) { + mis = maximumIndependentSetSize(); + } else { + int try_1, try_2; + restorePoint(); + removeNodes(s_1.getInclusiveNeighbourhood()); + try_1 = maximumIndependentSetSize(); + restore(); + removeNodes(s_2.getInclusiveNeighbourhood()); + try_2 = maximumIndependentSetSize(); + mis = Math.max(try_1, try_2) + 1; + } + } else if (!s_1.neighbourhoodsDisjoint(s_2)) { + removeNodes(s_1.neighbourhoodIntersection(s_2)); + mis = maximumIndependentSetSizeWith1From(s_1, s_2); + } else if (s_2.getDegree() == 2) { + Node E = s_1.getNeighbourhood().get(0), F = s_1.getNeighbourhood().get(1); + if (E.getNeighbourhood().contains(F)) { + removeNodes(s_1.getInclusiveNeighbourhood()); + mis = 1 + maximumIndependentSetSize(); + } else { + boolean subset = true; + for (Node n : E.getNeighbourhood()) + if (n != s_1 && !s_2.getNeighbourhood().contains(n)) + subset = false; + for (Node n : F.getNeighbourhood()) + if (n != s_1 && !s_2.getNeighbourhood().contains(n)) + subset = false; + if (subset) { + removeNodes(s_1.getInclusiveNeighbourhood()); + removeNodes(s_2.getInclusiveNeighbourhood()); + mis = 3 + maximumIndependentSetSize(); + } else { + int try_1, try_2; + removeNodes(s_1.getInclusiveNeighbourhood()); + try_1 = 1 + maximumIndependentSetSize(); + removeNodes(E.getInclusiveNeighbourhood()); + removeNodes(F.getInclusiveNeighbourhood()); + removeNodes(s_2.getInclusiveNeighbourhood()); + try_2 = 3 + maximumIndependentSetSize(); + mis = Math.max(try_1, try_2); + } + } + } else { + int try_1, try_2; + restorePoint(); + removeNodes(s_2.getInclusiveNeighbourhood()); + try_1 = maximumIndependentSetSize(); + restore(); + removeNodes(s_1.getInclusiveNeighbourhood()); + removeNode(s_2); + try_2 = maximumIndependentSetSizeWith2From(s_2.getNeighbourhood()); + mis = Math.max(try_1, try_2); + } + + restore(); + return mis; + } + + private int maximumIndependentSetSizeWith2From(Collection<Node> Scol) { + List<Node> S = new ArrayList<>(Scol); + int mis = 0; + restorePoint(); + + if (S.size() < 2) { + mis = 0; + } else if (S.size() == 2) { + if (S.get(0).getNeighbourhood().contains(S.get(1))) + mis = 0; + else { + removeNodes(S.get(0).getInclusiveNeighbourhood()); + removeNodes(S.get(1).getInclusiveNeighbourhood()); + mis = 2 + maximumIndependentSetSize(); + } + } else if (S.size() == 3) { + Node s_1 = S.get(0), s_2 = S.get(1), s_3 = S.get(2); + if (s_1.getDegree() == 0) { + removeNode(s_1); + mis = maximumIndependentSetSizeWith1From(s_2, s_3); + } else if (s_1.getNeighbourhood().contains(s_2) && + s_2.getNeighbourhood().contains(s_3) && + s_3.getNeighbourhood().contains(s_1)) { + mis = 0; + } else if (s_1.getNeighbourhood().contains(s_2) || s_1.getNeighbourhood().contains(s_3)){ + Node s_i, s_j, s_k; + s_i = s_j = s_k = null; + if (s_1.getNeighbourhood().contains(s_2) && s_1.getNeighbourhood().contains(s_3)) { + s_i = s_1; s_j = s_2; s_k = s_3; + } else if (s_2.getNeighbourhood().contains(s_1) && s_2.getNeighbourhood().contains(s_3)) { + s_i = s_2; s_j = s_1; s_k = s_3; + } else if (s_3.getNeighbourhood().contains(s_1) && s_3.getNeighbourhood().contains(s_2)) { + s_i = s_3; s_j = s_1; s_k = s_2; + } + + if (s_i != null) { // Case two edges + removeNodes(s_j.getInclusiveNeighbourhood()); + removeNodes(s_k.getInclusiveNeighbourhood()); + mis = 2 + maximumIndependentSetSize(); + } else if (s_1.getNeighbourhood().contains(s_2)) { // Case one edge + removeNodes(s_3.getInclusiveNeighbourhood()); + mis = 1 + maximumIndependentSetSizeWith1From(s_1, s_2); + } else if (s_1.getNeighbourhood().contains(s_3)) { // Case one edge + removeNodes(s_2.getInclusiveNeighbourhood()); + mis = 1 + maximumIndependentSetSizeWith1From(s_1, s_3); + } + } else if (s_2.getNeighbourhood().contains(s_3)) { + // Case si-sj with i=2, j=3 + removeNodes(s_1.getInclusiveNeighbourhood()); + mis = 1 + maximumIndependentSetSizeWith1From(s_2, s_3); + } else if (!s_1.neighbourhoodsDisjoint(s_2)) { + removeNode(s_1.neighbourhoodIntersection(s_2).get(0)); + mis = maximumIndependentSetSizeWith2From(Scol); + } else if (!s_1.neighbourhoodsDisjoint(s_3)) { + removeNode(s_1.neighbourhoodIntersection(s_3).get(0)); + mis = maximumIndependentSetSizeWith2From(Scol); + } else if (!s_2.neighbourhoodsDisjoint(s_3)) { + removeNode(s_2.neighbourhoodIntersection(s_3).get(0)); + mis = maximumIndependentSetSizeWith2From(Scol); + } else if (s_1.getDegree() == 1) { + removeNodes(s_1.getInclusiveNeighbourhood()); + mis = 1 + maximumIndependentSetSizeWith1From(s_2, s_3); + } else { + int try_1, try_2; + restorePoint(); + removeNodes(s_1.getInclusiveNeighbourhood()); + try_1 = 1 + maximumIndependentSetSizeWith1From(s_2, s_3); + restore(); + removeNodes(s_2.getInclusiveNeighbourhood()); + removeNodes(s_3.getInclusiveNeighbourhood()); + removeNode(s_1); + try_2 = maximumIndependentSetSizeWith2From(s_1.getNeighbourhood()); + mis = Math.max(try_1, try_2); + } + } else if (S.size() == 4) { + Collections.sort(nodes); + if (nodes.get(0).getDegree() <= 3) { + mis = maximumIndependentSetSize(); + } else { + Node s_1 = S.get(0); + int try_1, try_2; + removeNode(s_1); + S.remove(s_1); + try_1 = maximumIndependentSetSizeWith2From(S); + removeNodes(s_1.getNeighbourhood()); + try_2 = 1 + maximumIndependentSetSize(); + mis = Math.max(try_1, try_2); + } + } + + restore(); + return mis; + } + + private Graph findPartition() { + if (nodes.isEmpty()) + return this; + + List<Node> seen = new ArrayList<>(); + Queue<Node> queue = new LinkedList<>(); + queue.add(nodes.get(0)); + while (!queue.isEmpty()) { + Node n = queue.remove(); + queue.addAll(n.getNeighbourhood().stream().filter(x -> !seen.contains(x)).collect(Collectors.toList())); + seen.add(n); + } + + return new Graph(seen); } /** @@ -30,6 +272,11 @@ public class Graph { */ public void addNode(Node node) { this.nodes.add(node); + for (Node n : node.getNeighbourhood()) + if (nodes.contains(n)) + if (!n.getNeighbourhood().contains(node)) + n.getNeighbourhood().add(node); + removedStack.peek().remove(node); } /** @@ -43,25 +290,53 @@ public class Graph { /** * Remove a node - * @param n + * @param node */ - public void removeNode(Node n) { - nodes.remove(n); + private void removeNode(Node node) { + nodes.remove(node); + for (Node n : node.getNeighbourhood()) + if (nodes.contains(n)) + n.getNeighbourhood().remove(node); + removedStack.peek().add(node); } /** * Remove a list of nodes, and update all references * @param ns */ - public void removeNodes(Collection<Node> ns) { + private void removeNodes(Collection<Node> ns) { nodes.removeAll(ns); + for (Node n : nodes) + n.getNeighbourhood().removeAll(ns); + removedStack.peek().addAll(ns); + } + + private void restorePoint() { + removedStack.push(new ArrayList<>()); + } + + private void restore() { + List<Node> removed = removedStack.pop(); + Collections.reverse(removed); + for (Node node : removed) { + this.nodes.add(node); + for (Node n : node.getNeighbourhood()) + if (nodes.contains(n)) + if (!n.getNeighbourhood().contains(node)) + n.getNeighbourhood().add(node); + } + removed.clear(); + } + + public int size() { + return nodes.size(); } 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); + for (Node n2 : n.getNeighbourhood()) 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 index 87471e8..4edc666 100644 --- a/Practical1/src/nl/camilstaps/cs/graphs/Node.java +++ b/Practical1/src/nl/camilstaps/cs/graphs/Node.java @@ -9,7 +9,7 @@ import java.util.List; * * @author Camil Staps */ -public class Node { +public class Node implements Comparable<Node> { private final int content; private final List<Node> neighbours = new ArrayList<>(); @@ -17,19 +17,50 @@ public class Node { 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 int getDegree() { + return neighbours.size(); } - public List<Node> getNeighbours() { + public List<Node> getNeighbourhood() { return neighbours; } + public List<Node> getInclusiveNeighbourhood() { + List<Node> nb = new ArrayList<>(); + nb.add(this); + nb.addAll(neighbours); + return nb; + } + + public List<Node> getSecondNeighbourhood() { + List<Node> nb = new ArrayList<>(); + for (Node n : getNeighbourhood()) + for (Node n2 : n.getNeighbourhood()) + if (!nb.contains(n2)) + nb.add(n2); + nb.remove(this); + return nb; + } + + public boolean dominates(Node b) { + for (Node nb : getInclusiveNeighbourhood()) + if (!b.getInclusiveNeighbourhood().contains(nb)) + return false; + return true; + } + + public boolean neighbourhoodsDisjoint(Node b) { + return neighbourhoodIntersection(b).isEmpty(); + } + + public List<Node> neighbourhoodIntersection(Node b) { + List<Node> intersection = new ArrayList<>(); + for (Node n : neighbours) + if (b.getNeighbourhood().contains(n)) + intersection.add(n); + return intersection; + } + public String toString() { return "<" + content + ">"; } @@ -43,4 +74,9 @@ public class Node { return !(another == null || another.getClass() != this.getClass()) && content == (((Node) another).content); } + + @Override + public int compareTo(Node node) { + return node == null ? 1 : Integer.compare(neighbours.size(), node.neighbours.size()); + } } diff --git a/Practical1/tester/cases.py b/Practical1/tester/cases.py index d09ff27..9fa7792 100644 --- a/Practical1/tester/cases.py +++ b/Practical1/tester/cases.py @@ -1,12 +1,11 @@ -rows, cols, bins = 3, 3, 5 -#rows, cols, bins = 4, 4, 7 -#rows, cols, bins = 5, 5, 10 -rows, cols, bins = 6, 6, 14 -#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 +# These are the highest numbers of bins that are still possible +rows, cols, bins = 3, 3, 4 +rows, cols, bins = 4, 4, 6 +rows, cols, bins = 5, 5, 9 +rows, cols, bins = 6, 6, 12 +rows, cols, bins = 7, 7, 17 +rows, cols, bins = 8, 8, 22 +rows, cols, bins = 9, 9, 27 print 3 * (rows - 1) * (cols - 1) + (rows - 1) + (cols - 1), rows * cols, bins for r in range(rows - 1): diff --git a/Practical1/tester/samples/big_1.out b/Practical1/tester/samples/big_1.out new file mode 100644 index 0000000..9f56e79 --- /dev/null +++ b/Practical1/tester/samples/big_1.out @@ -0,0 +1 @@ +possible diff --git a/Practical1/tester/samples/big_2.out b/Practical1/tester/samples/big_2.out new file mode 100644 index 0000000..9f56e79 --- /dev/null +++ b/Practical1/tester/samples/big_2.out @@ -0,0 +1 @@ +possible diff --git a/Practical1/tester/samples/big_3.out b/Practical1/tester/samples/big_3.out new file mode 100644 index 0000000..9f56e79 --- /dev/null +++ b/Practical1/tester/samples/big_3.out @@ -0,0 +1 @@ +possible diff --git a/Practical1/tester/samples/big_4.out b/Practical1/tester/samples/big_4.out new file mode 100644 index 0000000..496b703 --- /dev/null +++ b/Practical1/tester/samples/big_4.out @@ -0,0 +1 @@ +impossible diff --git a/Practical1/tester/samples/big_5.out b/Practical1/tester/samples/big_5.out new file mode 100644 index 0000000..9f56e79 --- /dev/null +++ b/Practical1/tester/samples/big_5.out @@ -0,0 +1 @@ +possible diff --git a/Practical1/tester/samples/big_6.out b/Practical1/tester/samples/big_6.out new file mode 100644 index 0000000..496b703 --- /dev/null +++ b/Practical1/tester/samples/big_6.out @@ -0,0 +1 @@ +impossible diff --git a/Practical1/tester/samples/cases_3.in b/Practical1/tester/samples/cases_3_imp.in index a9b8617..a9b8617 100644 --- a/Practical1/tester/samples/cases_3.in +++ b/Practical1/tester/samples/cases_3_imp.in diff --git a/Practical1/tester/samples/cases_3_imp.out b/Practical1/tester/samples/cases_3_imp.out new file mode 100644 index 0000000..496b703 --- /dev/null +++ b/Practical1/tester/samples/cases_3_imp.out @@ -0,0 +1 @@ +impossible diff --git a/Practical1/tester/samples/cases_3_pos.in b/Practical1/tester/samples/cases_3_pos.in new file mode 100644 index 0000000..e84ddc6 --- /dev/null +++ b/Practical1/tester/samples/cases_3_pos.in @@ -0,0 +1,17 @@ +16 9 4 +1 2 +1 4 +1 5 +2 3 +2 5 +2 6 +3 6 +4 5 +4 7 +4 8 +5 6 +5 8 +5 9 +6 9 +7 8 +8 9 diff --git a/Practical1/tester/samples/cases_3_pos.out b/Practical1/tester/samples/cases_3_pos.out new file mode 100644 index 0000000..9f56e79 --- /dev/null +++ b/Practical1/tester/samples/cases_3_pos.out @@ -0,0 +1 @@ +possible diff --git a/Practical1/tester/samples/cases_4.in b/Practical1/tester/samples/cases_4_imp.in index 33d82b8..33d82b8 100644 --- a/Practical1/tester/samples/cases_4.in +++ b/Practical1/tester/samples/cases_4_imp.in diff --git a/Practical1/tester/samples/cases_4_imp.out b/Practical1/tester/samples/cases_4_imp.out new file mode 100644 index 0000000..496b703 --- /dev/null +++ b/Practical1/tester/samples/cases_4_imp.out @@ -0,0 +1 @@ +impossible diff --git a/Practical1/tester/samples/cases_4_pos.in b/Practical1/tester/samples/cases_4_pos.in new file mode 100644 index 0000000..cc9320f --- /dev/null +++ b/Practical1/tester/samples/cases_4_pos.in @@ -0,0 +1,34 @@ +33 16 6 +1 2 +1 5 +1 6 +2 3 +2 6 +2 7 +3 4 +3 7 +3 8 +4 8 +5 6 +5 9 +5 10 +6 7 +6 10 +6 11 +7 8 +7 11 +7 12 +8 12 +9 10 +9 13 +9 14 +10 11 +10 14 +10 15 +11 12 +11 15 +11 16 +12 16 +13 14 +14 15 +15 16 diff --git a/Practical1/tester/samples/cases_4_pos.out b/Practical1/tester/samples/cases_4_pos.out new file mode 100644 index 0000000..9f56e79 --- /dev/null +++ b/Practical1/tester/samples/cases_4_pos.out @@ -0,0 +1 @@ +possible diff --git a/Practical1/tester/samples/cases_5.in b/Practical1/tester/samples/cases_5_imp.in index 396c395..396c395 100644 --- a/Practical1/tester/samples/cases_5.in +++ b/Practical1/tester/samples/cases_5_imp.in diff --git a/Practical1/tester/samples/cases_5_imp.out b/Practical1/tester/samples/cases_5_imp.out new file mode 100644 index 0000000..496b703 --- /dev/null +++ b/Practical1/tester/samples/cases_5_imp.out @@ -0,0 +1 @@ +impossible diff --git a/Practical1/tester/samples/cases_5_pos.in b/Practical1/tester/samples/cases_5_pos.in new file mode 100644 index 0000000..e0bcb6d --- /dev/null +++ b/Practical1/tester/samples/cases_5_pos.in @@ -0,0 +1,57 @@ +56 25 9 +1 2 +1 6 +1 7 +2 3 +2 7 +2 8 +3 4 +3 8 +3 9 +4 5 +4 9 +4 10 +5 10 +6 7 +6 11 +6 12 +7 8 +7 12 +7 13 +8 9 +8 13 +8 14 +9 10 +9 14 +9 15 +10 15 +11 12 +11 16 +11 17 +12 13 +12 17 +12 18 +13 14 +13 18 +13 19 +14 15 +14 19 +14 20 +15 20 +16 17 +16 21 +16 22 +17 18 +17 22 +17 23 +18 19 +18 23 +18 24 +19 20 +19 24 +19 25 +20 25 +21 22 +22 23 +23 24 +24 25 diff --git a/Practical1/tester/samples/cases_5_pos.out b/Practical1/tester/samples/cases_5_pos.out new file mode 100644 index 0000000..9f56e79 --- /dev/null +++ b/Practical1/tester/samples/cases_5_pos.out @@ -0,0 +1 @@ +possible diff --git a/Practical1/tester/samples/cases_6.in b/Practical1/tester/samples/cases_6_imp.in index ea922dd..d15b984 100644 --- a/Practical1/tester/samples/cases_6.in +++ b/Practical1/tester/samples/cases_6_imp.in @@ -1,4 +1,4 @@ -85 36 14 +85 36 13 1 2 1 7 1 8 diff --git a/Practical1/tester/samples/cases_6_imp.out b/Practical1/tester/samples/cases_6_imp.out new file mode 100644 index 0000000..496b703 --- /dev/null +++ b/Practical1/tester/samples/cases_6_imp.out @@ -0,0 +1 @@ +impossible diff --git a/Practical1/tester/samples/cases_6_pos.in b/Practical1/tester/samples/cases_6_pos.in new file mode 100644 index 0000000..9ebb4db --- /dev/null +++ b/Practical1/tester/samples/cases_6_pos.in @@ -0,0 +1,86 @@ +85 36 12 +1 2 +1 7 +1 8 +2 3 +2 8 +2 9 +3 4 +3 9 +3 10 +4 5 +4 10 +4 11 +5 6 +5 11 +5 12 +6 12 +7 8 +7 13 +7 14 +8 9 +8 14 +8 15 +9 10 +9 15 +9 16 +10 11 +10 16 +10 17 +11 12 +11 17 +11 18 +12 18 +13 14 +13 19 +13 20 +14 15 +14 20 +14 21 +15 16 +15 21 +15 22 +16 17 +16 22 +16 23 +17 18 +17 23 +17 24 +18 24 +19 20 +19 25 +19 26 +20 21 +20 26 +20 27 +21 22 +21 27 +21 28 +22 23 +22 28 +22 29 +23 24 +23 29 +23 30 +24 30 +25 26 +25 31 +25 32 +26 27 +26 32 +26 33 +27 28 +27 33 +27 34 +28 29 +28 34 +28 35 +29 30 +29 35 +29 36 +30 36 +31 32 +32 33 +33 34 +34 35 +35 36 diff --git a/Practical1/tester/samples/cases_6_pos.out b/Practical1/tester/samples/cases_6_pos.out new file mode 100644 index 0000000..9f56e79 --- /dev/null +++ b/Practical1/tester/samples/cases_6_pos.out @@ -0,0 +1 @@ +possible diff --git a/Practical1/tester/samples/cases_7.in b/Practical1/tester/samples/cases_7_imp.in index 1097fb4..1097fb4 100644 --- a/Practical1/tester/samples/cases_7.in +++ b/Practical1/tester/samples/cases_7_imp.in diff --git a/Practical1/tester/samples/cases_7_imp.out b/Practical1/tester/samples/cases_7_imp.out new file mode 100644 index 0000000..496b703 --- /dev/null +++ b/Practical1/tester/samples/cases_7_imp.out @@ -0,0 +1 @@ +impossible diff --git a/Practical1/tester/samples/cases_7_pos.in b/Practical1/tester/samples/cases_7_pos.in new file mode 100644 index 0000000..973d5ab --- /dev/null +++ b/Practical1/tester/samples/cases_7_pos.in @@ -0,0 +1,121 @@ +120 49 17 +1 2 +1 8 +1 9 +2 3 +2 9 +2 10 +3 4 +3 10 +3 11 +4 5 +4 11 +4 12 +5 6 +5 12 +5 13 +6 7 +6 13 +6 14 +7 14 +8 9 +8 15 +8 16 +9 10 +9 16 +9 17 +10 11 +10 17 +10 18 +11 12 +11 18 +11 19 +12 13 +12 19 +12 20 +13 14 +13 20 +13 21 +14 21 +15 16 +15 22 +15 23 +16 17 +16 23 +16 24 +17 18 +17 24 +17 25 +18 19 +18 25 +18 26 +19 20 +19 26 +19 27 +20 21 +20 27 +20 28 +21 28 +22 23 +22 29 +22 30 +23 24 +23 30 +23 31 +24 25 +24 31 +24 32 +25 26 +25 32 +25 33 +26 27 +26 33 +26 34 +27 28 +27 34 +27 35 +28 35 +29 30 +29 36 +29 37 +30 31 +30 37 +30 38 +31 32 +31 38 +31 39 +32 33 +32 39 +32 40 +33 34 +33 40 +33 41 +34 35 +34 41 +34 42 +35 42 +36 37 +36 43 +36 44 +37 38 +37 44 +37 45 +38 39 +38 45 +38 46 +39 40 +39 46 +39 47 +40 41 +40 47 +40 48 +41 42 +41 48 +41 49 +42 49 +43 44 +44 45 +45 46 +46 47 +47 48 +48 49 diff --git a/Practical1/tester/samples/cases_7_pos.out b/Practical1/tester/samples/cases_7_pos.out new file mode 100644 index 0000000..9f56e79 --- /dev/null +++ b/Practical1/tester/samples/cases_7_pos.out @@ -0,0 +1 @@ +possible diff --git a/Practical1/tester/samples/cases_8.in b/Practical1/tester/samples/cases_8_imp.in index dd23253..dd23253 100644 --- a/Practical1/tester/samples/cases_8.in +++ b/Practical1/tester/samples/cases_8_imp.in diff --git a/Practical1/tester/samples/cases_8_imp.out b/Practical1/tester/samples/cases_8_imp.out new file mode 100644 index 0000000..496b703 --- /dev/null +++ b/Practical1/tester/samples/cases_8_imp.out @@ -0,0 +1 @@ +impossible diff --git a/Practical1/tester/samples/cases_8_pos.in b/Practical1/tester/samples/cases_8_pos.in new file mode 100644 index 0000000..5cf2f0e --- /dev/null +++ b/Practical1/tester/samples/cases_8_pos.in @@ -0,0 +1,162 @@ +161 64 22 +1 2 +1 9 +1 10 +2 3 +2 10 +2 11 +3 4 +3 11 +3 12 +4 5 +4 12 +4 13 +5 6 +5 13 +5 14 +6 7 +6 14 +6 15 +7 8 +7 15 +7 16 +8 16 +9 10 +9 17 +9 18 +10 11 +10 18 +10 19 +11 12 +11 19 +11 20 +12 13 +12 20 +12 21 +13 14 +13 21 +13 22 +14 15 +14 22 +14 23 +15 16 +15 23 +15 24 +16 24 +17 18 +17 25 +17 26 +18 19 +18 26 +18 27 +19 20 +19 27 +19 28 +20 21 +20 28 +20 29 +21 22 +21 29 +21 30 +22 23 +22 30 +22 31 +23 24 +23 31 +23 32 +24 32 +25 26 +25 33 +25 34 +26 27 +26 34 +26 35 +27 28 +27 35 +27 36 +28 29 +28 36 +28 37 +29 30 +29 37 +29 38 +30 31 +30 38 +30 39 +31 32 +31 39 +31 40 +32 40 +33 34 +33 41 +33 42 +34 35 +34 42 +34 43 +35 36 +35 43 +35 44 +36 37 +36 44 +36 45 +37 38 +37 45 +37 46 +38 39 +38 46 +38 47 +39 40 +39 47 +39 48 +40 48 +41 42 +41 49 +41 50 +42 43 +42 50 +42 51 +43 44 +43 51 +43 52 +44 45 +44 52 +44 53 +45 46 +45 53 +45 54 +46 47 +46 54 +46 55 +47 48 +47 55 +47 56 +48 56 +49 50 +49 57 +49 58 +50 51 +50 58 +50 59 +51 52 +51 59 +51 60 +52 53 +52 60 +52 61 +53 54 +53 61 +53 62 +54 55 +54 62 +54 63 +55 56 +55 63 +55 64 +56 64 +57 58 +58 59 +59 60 +60 61 +61 62 +62 63 +63 64 diff --git a/Practical1/tester/samples/cases_8_pos.out b/Practical1/tester/samples/cases_8_pos.out new file mode 100644 index 0000000..9f56e79 --- /dev/null +++ b/Practical1/tester/samples/cases_8_pos.out @@ -0,0 +1 @@ +possible diff --git a/Practical1/tester/samples/cases_9.in b/Practical1/tester/samples/cases_9_imp.in index e382d8e..e382d8e 100644 --- a/Practical1/tester/samples/cases_9.in +++ b/Practical1/tester/samples/cases_9_imp.in diff --git a/Practical1/tester/samples/cases_9_imp.out b/Practical1/tester/samples/cases_9_imp.out new file mode 100644 index 0000000..496b703 --- /dev/null +++ b/Practical1/tester/samples/cases_9_imp.out @@ -0,0 +1 @@ +impossible diff --git a/Practical1/tester/samples/cases_9_pos.in b/Practical1/tester/samples/cases_9_pos.in new file mode 100644 index 0000000..4dcd696 --- /dev/null +++ b/Practical1/tester/samples/cases_9_pos.in @@ -0,0 +1,209 @@ +208 81 27 +1 2 +1 10 +1 11 +2 3 +2 11 +2 12 +3 4 +3 12 +3 13 +4 5 +4 13 +4 14 +5 6 +5 14 +5 15 +6 7 +6 15 +6 16 +7 8 +7 16 +7 17 +8 9 +8 17 +8 18 +9 18 +10 11 +10 19 +10 20 +11 12 +11 20 +11 21 +12 13 +12 21 +12 22 +13 14 +13 22 +13 23 +14 15 +14 23 +14 24 +15 16 +15 24 +15 25 +16 17 +16 25 +16 26 +17 18 +17 26 +17 27 +18 27 +19 20 +19 28 +19 29 +20 21 +20 29 +20 30 +21 22 +21 30 +21 31 +22 23 +22 31 +22 32 +23 24 +23 32 +23 33 +24 25 +24 33 +24 34 +25 26 +25 34 +25 35 +26 27 +26 35 +26 36 +27 36 +28 29 +28 37 +28 38 +29 30 +29 38 +29 39 +30 31 +30 39 +30 40 +31 32 +31 40 +31 41 +32 33 +32 41 +32 42 +33 34 +33 42 +33 43 +34 35 +34 43 +34 44 +35 36 +35 44 +35 45 +36 45 +37 38 +37 46 +37 47 +38 39 +38 47 +38 48 +39 40 +39 48 +39 49 +40 41 +40 49 +40 50 +41 42 +41 50 +41 51 +42 43 +42 51 +42 52 +43 44 +43 52 +43 53 +44 45 +44 53 +44 54 +45 54 +46 47 +46 55 +46 56 +47 48 +47 56 +47 57 +48 49 +48 57 +48 58 +49 50 +49 58 +49 59 +50 51 +50 59 +50 60 +51 52 +51 60 +51 61 +52 53 +52 61 +52 62 +53 54 +53 62 +53 63 +54 63 +55 56 +55 64 +55 65 +56 57 +56 65 +56 66 +57 58 +57 66 +57 67 +58 59 +58 67 +58 68 +59 60 +59 68 +59 69 +60 61 +60 69 +60 70 +61 62 +61 70 +61 71 +62 63 +62 71 +62 72 +63 72 +64 65 +64 73 +64 74 +65 66 +65 74 +65 75 +66 67 +66 75 +66 76 +67 68 +67 76 +67 77 +68 69 +68 77 +68 78 +69 70 +69 78 +69 79 +70 71 +70 79 +70 80 +71 72 +71 80 +71 81 +72 81 +73 74 +74 75 +75 76 +76 77 +77 78 +78 79 +79 80 +80 81 diff --git a/Practical1/tester/samples/cases_9_pos.out b/Practical1/tester/samples/cases_9_pos.out new file mode 100644 index 0000000..9f56e79 --- /dev/null +++ b/Practical1/tester/samples/cases_9_pos.out @@ -0,0 +1 @@ +possible diff --git a/Practical1/tester/samples/small_1.out b/Practical1/tester/samples/small_1.out new file mode 100644 index 0000000..9f56e79 --- /dev/null +++ b/Practical1/tester/samples/small_1.out @@ -0,0 +1 @@ +possible diff --git a/Practical1/tester/samples/small_2.out b/Practical1/tester/samples/small_2.out new file mode 100644 index 0000000..496b703 --- /dev/null +++ b/Practical1/tester/samples/small_2.out @@ -0,0 +1 @@ +impossible diff --git a/Practical1/tester/samples/small_3.out b/Practical1/tester/samples/small_3.out new file mode 100644 index 0000000..9f56e79 --- /dev/null +++ b/Practical1/tester/samples/small_3.out @@ -0,0 +1 @@ +possible diff --git a/Practical1/tester/samples/small_4.out b/Practical1/tester/samples/small_4.out new file mode 100644 index 0000000..9f56e79 --- /dev/null +++ b/Practical1/tester/samples/small_4.out @@ -0,0 +1 @@ +possible diff --git a/Practical1/tester/samples/small_5.out b/Practical1/tester/samples/small_5.out new file mode 100644 index 0000000..496b703 --- /dev/null +++ b/Practical1/tester/samples/small_5.out @@ -0,0 +1 @@ +impossible diff --git a/Practical1/tester/samples/small_6.out b/Practical1/tester/samples/small_6.out new file mode 100644 index 0000000..9f56e79 --- /dev/null +++ b/Practical1/tester/samples/small_6.out @@ -0,0 +1 @@ +possible diff --git a/Practical1/tester/test.sh b/Practical1/tester/test.sh index a13fd63..068d6ea 100755 --- a/Practical1/tester/test.sh +++ b/Practical1/tester/test.sh @@ -4,7 +4,7 @@ java="/usr/lib/jvm/java-8-openjdk-amd64/bin/java" failed=0 cd "$(dirname $0)/../out/production/Practical1" -for tc in ../../../tester/samples/cas*.in +for tc in ../../../tester/samples/*.in do answer=$(cat ${tc/in/out}) header=$(head -n1 "$tc" | tr -d '\n') @@ -16,7 +16,7 @@ do if [ $result != $answer ] then echo "failure ($time ms)." - failed+=1 + failed=$(($failed+1)) else echo "success ($time ms)." fi |