aboutsummaryrefslogtreecommitdiff
path: root/Practical1
diff options
context:
space:
mode:
Diffstat (limited to 'Practical1')
-rw-r--r--Practical1/src/nl/camilstaps/cs/GarbageCollectionHelper.java2
-rw-r--r--Practical1/src/nl/camilstaps/cs/graphs/Graph.java260
-rw-r--r--Practical1/src/nl/camilstaps/cs/graphs/Node.java59
-rwxr-xr-xPractical1/tester/test.sh17
4 files changed, 235 insertions, 103 deletions
diff --git a/Practical1/src/nl/camilstaps/cs/GarbageCollectionHelper.java b/Practical1/src/nl/camilstaps/cs/GarbageCollectionHelper.java
index 282cfb3..0da2dc5 100644
--- a/Practical1/src/nl/camilstaps/cs/GarbageCollectionHelper.java
+++ b/Practical1/src/nl/camilstaps/cs/GarbageCollectionHelper.java
@@ -14,7 +14,7 @@ class GarbageCollectionHelper {
/**
* Read in a Graph from stdin and print whether we can place N bins to stdout
- * @param args
+ * @param args Command line arguments (are ignored)
*/
public static void main(String[] args) {
Graph graph = new Graph();
diff --git a/Practical1/src/nl/camilstaps/cs/graphs/Graph.java b/Practical1/src/nl/camilstaps/cs/graphs/Graph.java
index 0da1924..f1bf946 100644
--- a/Practical1/src/nl/camilstaps/cs/graphs/Graph.java
+++ b/Practical1/src/nl/camilstaps/cs/graphs/Graph.java
@@ -10,7 +10,8 @@ import java.util.stream.Collectors;
*/
public class Graph {
private final List<Node> nodes;
- private final Stack<List<Node>> removedStack = new Stack<>();
+ // When removing nodes, it's possible to create restore points to add them back later on.
+ private final Stack<List<Node>> restorePoints = new Stack<>();
public Graph() {
this.nodes = new ArrayList<>();
@@ -22,15 +23,24 @@ public class Graph {
restorePoint();
}
+ /**
+ * Computes the size of the maximum independent set using Robson's algorithm.
+ *
+ * @see #maximumIndependentSetSizeWith1From(Node, Node)
+ * @see #maximumIndependentSetSizeWith2From(Collection)
+ *
+ * @return the size of the maximum independent set
+ */
public int maximumIndependentSetSize() {
if (nodes.size() <= 1)
return nodes.size();
- int mis = 0;
+ int miss;
restorePoint();
- Graph partition = findPartition();
- if (partition.size() == size()) {
+ Graph stronglyConnectedComponent = findStronglyConnectedComponent();
+ if (stronglyConnectedComponent.size() == size()) {
+ // Case: connected graph. Pick a nice Node A (low degree) and a neighbour B with high degree.
Collections.sort(nodes);
Node A = nodes.get(0);
Collections.sort(A.getNeighbourhood(), Collections.reverseOrder());
@@ -39,14 +49,17 @@ public class Graph {
int try_1, try_2;
switch (A.getDegree()) {
case 1:
+ // One neighbour; pick A and continue with the rest of the Graph.
removeNodes(A.getInclusiveNeighbourhood());
- mis = 1 + maximumIndependentSetSize();
+ miss = 1 + maximumIndependentSetSize();
break;
case 2:
+ // Two neighbours: if they are connected pick A and continue with the rest of the Graph. If not,
+ // try both picking the neighbours and picking A with two of its second order neighbours.
Node B_ = A.getNeighbourhood().get(1);
if (B.getNeighbourhood().contains(B_)) {
removeNodes(A.getInclusiveNeighbourhood());
- mis = 1 + maximumIndependentSetSize();
+ miss = 1 + maximumIndependentSetSize();
} else {
restorePoint();
removeNodes(B.getInclusiveNeighbourhood());
@@ -55,50 +68,64 @@ public class Graph {
restore();
removeNodes(A.getInclusiveNeighbourhood());
try_2 = 1 + maximumIndependentSetSizeWith2From(A.getSecondNeighbourhood());
- mis = Math.max(try_1, try_2);
+ miss = Math.max(try_1, try_2);
}
break;
case 3:
+ // Three neighbours: either we pick two of the neighbours, or we pick A.
removeNode(A);
try_1 = maximumIndependentSetSizeWith2From(A.getNeighbourhood());
removeNodes(A.getNeighbourhood());
try_2 = 1 + maximumIndependentSetSize();
- mis = Math.max(try_1, try_2);
+ miss = Math.max(try_1, try_2);
break;
default:
+ // If A dominates his neighbour we may safely remove that neighbour. Otherwise, we try both with
+ // and without the neighbour.
if (A.dominates(B)) {
removeNode(B);
- mis = maximumIndependentSetSize();
+ miss = maximumIndependentSetSize();
} else {
removeNode(B);
try_1 = maximumIndependentSetSize();
removeNodes(B.getNeighbourhood());
try_2 = 1 + maximumIndependentSetSize();
- mis = Math.max(try_1, try_2);
+ miss = Math.max(try_1, try_2);
}
break;
}
} else {
- mis = partition.maximumIndependentSetSize();
- removeNodes(partition.nodes);
- mis += maximumIndependentSetSize();
+ // Case: at least two strongly connected components. Compute for the first component, and for the rest.
+ miss = stronglyConnectedComponent.maximumIndependentSetSize();
+ removeNodes(stronglyConnectedComponent.nodes);
+ miss += maximumIndependentSetSize();
}
restore();
- return mis;
+ return miss;
}
+ /**
+ * Compute the maximum independent set size if it should contain (at least) one of two nodes.
+ *
+ * This is a helper function for {@link #maximumIndependentSetSizeWith2From(Collection)}, which is a helper
+ * function for {@link #maximumIndependentSetSize()}, which uses Robson's algorithm.
+ *
+ * @param s_1 The first node
+ * @param s_2 The second node
+ * @return the maximum independent set size
+ */
private int maximumIndependentSetSizeWith1From(Node s_1, Node s_2) {
assert s_1.getDegree() <= s_2.getDegree();
- int mis = 0;
+ int miss;
restorePoint();
if (s_1.getDegree() <= 1) {
- mis = maximumIndependentSetSize();
+ miss = maximumIndependentSetSize();
} else if (s_1.getNeighbourhood().contains(s_2)) {
if (s_1.getDegree() <= 3) {
- mis = maximumIndependentSetSize();
+ miss = maximumIndependentSetSize();
} else {
int try_1, try_2;
restorePoint();
@@ -107,16 +134,16 @@ public class Graph {
restore();
removeNodes(s_2.getInclusiveNeighbourhood());
try_2 = maximumIndependentSetSize();
- mis = Math.max(try_1, try_2) + 1;
+ miss = 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);
+ miss = 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();
+ miss = 1 + maximumIndependentSetSize();
} else {
boolean subset = true;
for (Node n : E.getNeighbourhood())
@@ -128,7 +155,7 @@ public class Graph {
if (subset) {
removeNodes(s_1.getInclusiveNeighbourhood());
removeNodes(s_2.getInclusiveNeighbourhood());
- mis = 3 + maximumIndependentSetSize();
+ miss = 3 + maximumIndependentSetSize();
} else {
int try_1, try_2;
removeNodes(s_1.getInclusiveNeighbourhood());
@@ -137,7 +164,7 @@ public class Graph {
removeNodes(F.getInclusiveNeighbourhood());
removeNodes(s_2.getInclusiveNeighbourhood());
try_2 = 3 + maximumIndependentSetSize();
- mis = Math.max(try_1, try_2);
+ miss = Math.max(try_1, try_2);
}
}
} else {
@@ -149,40 +176,67 @@ public class Graph {
removeNodes(s_1.getInclusiveNeighbourhood());
removeNode(s_2);
try_2 = maximumIndependentSetSizeWith2From(s_2.getNeighbourhood());
- mis = Math.max(try_1, try_2);
+ miss = Math.max(try_1, try_2);
}
restore();
- return mis;
+ return miss;
}
+ /**
+ * Compute the maximum independent set size if at least two Nodes of some set should be in it.
+ *
+ * This is a helper function for {@link #maximumIndependentSetSize()}, which uses Robson's algorithm.
+ *
+ * @see #maximumIndependentSetSizeWith1From(Node, Node)
+ *
+ * @param Scol the set of which two Nodes should be in the maximum independent set
+ * @return the size of the maximum independent set
+ */
private int maximumIndependentSetSizeWith2From(Collection<Node> Scol) {
List<Node> S = new ArrayList<>(Scol);
- int mis = 0;
+ int miss;
restorePoint();
if (S.size() < 2) {
- mis = 0;
+ // Less than two Nodes to pick from; this is impossible
+ miss = 0;
} else if (S.size() == 2) {
+ // Two Nodes to pick from; try to pick both and fail otherwise.
if (S.get(0).getNeighbourhood().contains(S.get(1)))
- mis = 0;
+ miss = 0;
else {
removeNodes(S.get(0).getInclusiveNeighbourhood());
removeNodes(S.get(1).getInclusiveNeighbourhood());
- mis = 2 + maximumIndependentSetSize();
+ miss = 2 + maximumIndependentSetSize();
}
} else if (S.size() == 3) {
+ // Three Nodes to pick from. An ugly case distinction.
Node s_1 = S.get(0), s_2 = S.get(1), s_3 = S.get(2);
+
+ // If there is a Node with degree 0, we add it to the independent set and choose 1 Node from the other two
if (s_1.getDegree() == 0) {
removeNode(s_1);
- mis = maximumIndependentSetSizeWith1From(s_2, s_3);
- } else if (s_1.getNeighbourhood().contains(s_2) &&
+ miss = 1 + maximumIndependentSetSizeWith1From(s_2, s_3);
+ } else if (s_2.getDegree() == 0) {
+ removeNode(s_2);
+ miss = 1 + maximumIndependentSetSizeWith1From(s_1, s_3);
+ } else if (s_3.getDegree() == 0) {
+ removeNode(s_3);
+ miss = 1 + maximumIndependentSetSizeWith1From(s_1, s_2);
+ }
+ // If the Nodes are connected we can't choose two in an independent set.
+ 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)){
+ miss = 0;
+ }
+ // If there is at least one edge from s_1
+ 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 there are two edges among S, say si-sj-sk, we pick si and sk.
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)) {
@@ -191,34 +245,46 @@ public class Graph {
s_i = s_3; s_j = s_1; s_k = s_2;
}
- if (s_i != null) { // Case two edges
+ // Check if we managed to find two edges. If not, there must be at least one edge, say si-sj. We then
+ // choose sk and either si or sj. These are the cases that s_1 != sk.
+ 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
+ miss = 2 + maximumIndependentSetSize();
+ } else if (s_1.getNeighbourhood().contains(s_2)) { // Case one edge; s_1 - s_2
removeNodes(s_3.getInclusiveNeighbourhood());
- mis = 1 + maximumIndependentSetSizeWith1From(s_1, s_2);
- } else if (s_1.getNeighbourhood().contains(s_3)) { // Case one edge
+ miss = 1 + maximumIndependentSetSizeWith1From(s_1, s_2);
+ } else { // Case one edge; s_1 - s_3 (implicit)
removeNodes(s_2.getInclusiveNeighbourhood());
- mis = 1 + maximumIndependentSetSizeWith1From(s_1, s_3);
+ miss = 1 + maximumIndependentSetSizeWith1From(s_1, s_3);
}
- } else if (s_2.getNeighbourhood().contains(s_3)) {
- // Case si-sj with i=2, j=3
+ }
+ // Final case with one edge; between s_2 and s_3: pick s_1 and either s_2 or s_3.
+ else if (s_2.getNeighbourhood().contains(s_3)) {
removeNodes(s_1.getInclusiveNeighbourhood());
- mis = 1 + maximumIndependentSetSizeWith1From(s_2, s_3);
- } else if (!s_1.neighbourhoodsDisjoint(s_2)) {
+ miss = 1 + maximumIndependentSetSizeWith1From(s_2, s_3);
+ }
+ // When two neighbourhoods of two nodes si, sj aren't disjoint, we can remove the intersection, because
+ // either si or sj is in the independent set and so the intersection is not. The intersection has at most
+ // one member.
+ else if (!s_1.neighbourhoodsDisjoint(s_2)) {
removeNode(s_1.neighbourhoodIntersection(s_2).get(0));
- mis = maximumIndependentSetSizeWith2From(Scol);
+ miss = maximumIndependentSetSizeWith2From(Scol);
} else if (!s_1.neighbourhoodsDisjoint(s_3)) {
removeNode(s_1.neighbourhoodIntersection(s_3).get(0));
- mis = maximumIndependentSetSizeWith2From(Scol);
+ miss = 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) {
+ miss = maximumIndependentSetSizeWith2From(Scol);
+ }
+ // If s_1 has degree 1, we pick it and either s_2 or s_3
+ else if (s_1.getDegree() == 1) {
removeNodes(s_1.getInclusiveNeighbourhood());
- mis = 1 + maximumIndependentSetSizeWith1From(s_2, s_3);
- } else {
+ miss = 1 + maximumIndependentSetSizeWith1From(s_2, s_3);
+ }
+ // If all else fails, we try both picking s_1 with either s_2 or s_3, and picking s_1 and s_2 and at least
+ // one neighbour of s_1 (Note: Robson has forgotten to add 2 for s_2 and s_3 in this step).
+ else {
int try_1, try_2;
restorePoint();
removeNodes(s_1.getInclusiveNeighbourhood());
@@ -227,13 +293,15 @@ public class Graph {
removeNodes(s_2.getInclusiveNeighbourhood());
removeNodes(s_3.getInclusiveNeighbourhood());
removeNode(s_1);
- try_2 = maximumIndependentSetSizeWith2From(s_1.getNeighbourhood());
- mis = Math.max(try_1, try_2);
+ try_2 = 2 + maximumIndependentSetSizeWith2From(s_1.getNeighbourhood());
+ miss = Math.max(try_1, try_2);
}
} else if (S.size() == 4) {
+ // Four Nodes to pick from. If there's a node with degree <= 3 in the Graph, it's more efficient to just
+ // compute normally. If not, we try recursively both with and without the first Node in S.
Collections.sort(nodes);
if (nodes.get(0).getDegree() <= 3) {
- mis = maximumIndependentSetSize();
+ miss = maximumIndependentSetSize();
} else {
Node s_1 = S.get(0);
int try_1, try_2;
@@ -242,15 +310,24 @@ public class Graph {
try_1 = maximumIndependentSetSizeWith2From(S);
removeNodes(s_1.getNeighbourhood());
try_2 = 1 + maximumIndependentSetSize();
- mis = Math.max(try_1, try_2);
+ miss = Math.max(try_1, try_2);
}
+ } else {
+ miss = maximumIndependentSetSize();
}
restore();
- return mis;
+ return miss;
}
- private Graph findPartition() {
+ /**
+ * Find a strongly connected component of the graph. This may return itself, if the graph is empty or connected.
+ * It is not guaranteed that the smallest / largest strongly connected component is returned. The method simply
+ * returns the one that contains the first node (if it exists).
+ *
+ * @return some strongly connected component
+ */
+ private Graph findStronglyConnectedComponent() {
if (nodes.isEmpty())
return this;
@@ -267,71 +344,98 @@ public class Graph {
}
/**
- * Add a Node
- * @param node
+ * Add a Node, and update its neighbours to include it as a neighbour.
+ * @param node the Node to add
*/
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);
+ node.getNeighbourhood().stream()
+ .filter(nodes::contains)
+ .filter(n -> !n.getNeighbourhood().contains(node))
+ .forEach(n -> n.getNeighbourhood().add(node));
+ restorePoints.peek().remove(node);
}
/**
- * Get a Node
- * @param i
- * @return
+ * Get a Node by its index. Note: some internal methods may reorder the list; only use this directly after adding
+ * nodes.
+ * @param i the index in the list
+ * @return the Node
*/
public Node getNode(int i) {
return this.nodes.get(i);
}
/**
- * Remove a node
- * @param node
+ * Remove a node, and remove its reference from its neighbours that are still in the graph
+ *
+ * @see #removeNodes(Collection)
+ *
+ * @param node the Node
*/
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);
+ node.getNeighbourhood().stream()
+ .filter(nodes::contains)
+ .forEach(n -> n.getNeighbourhood().remove(node));
+ restorePoints.peek().add(node);
}
/**
* Remove a list of nodes, and update all references
- * @param ns
+ *
+ * @see #removeNode(Node)
+ *
+ * @param ns the Nodes to remove
*/
private void removeNodes(Collection<Node> ns) {
nodes.removeAll(ns);
for (Node n : nodes)
n.getNeighbourhood().removeAll(ns);
- removedStack.peek().addAll(ns);
+ restorePoints.peek().addAll(ns);
}
+ /**
+ * Create a restore point to return back to after removing some Nodes.
+ *
+ * @see #restore()
+ * @see #restorePoints
+ */
private void restorePoint() {
- removedStack.push(new ArrayList<>());
+ restorePoints.push(new ArrayList<>());
}
+ /**
+ * Go back to the last restore point, re-adding all Nodes that were removed since then.
+ *
+ * @see #restorePoint()
+ * @see #restorePoints
+ */
private void restore() {
- List<Node> removed = removedStack.pop();
+ List<Node> removed = restorePoints.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);
+ node.getNeighbourhood().stream()
+ .filter(nodes::contains)
+ .filter(n -> !n.getNeighbourhood().contains(node))
+ .forEach(n -> n.getNeighbourhood().add(node));
}
removed.clear();
}
+ /**
+ * The size of the graph is the number of Nodes.
+ * @return the number of Nodes.
+ */
public int size() {
return nodes.size();
}
+ /**
+ * Represent the Graph as a String
+ * @return a String representation of the Graph
+ */
public String toString() {
StringBuilder sb = new StringBuilder("Graph:");
for (Node n : nodes) {
diff --git a/Practical1/src/nl/camilstaps/cs/graphs/Node.java b/Practical1/src/nl/camilstaps/cs/graphs/Node.java
index 4edc666..b9d078e 100644
--- a/Practical1/src/nl/camilstaps/cs/graphs/Node.java
+++ b/Practical1/src/nl/camilstaps/cs/graphs/Node.java
@@ -2,6 +2,7 @@ package nl.camilstaps.cs.graphs;
import java.util.ArrayList;
import java.util.List;
+import java.util.stream.Collectors;
/**
* A Node is a simple point in a graph, with references to its neighbours. It holds an integer 'content' which can act
@@ -17,14 +18,23 @@ public class Node implements Comparable<Node> {
this.content = content;
}
+ /**
+ * @return the number of neighbours
+ */
public int getDegree() {
return neighbours.size();
}
+ /**
+ * @return the neighbours
+ */
public List<Node> getNeighbourhood() {
return neighbours;
}
+ /**
+ * @return the neighbours with the Node itself
+ */
public List<Node> getInclusiveNeighbourhood() {
List<Node> nb = new ArrayList<>();
nb.add(this);
@@ -32,16 +42,22 @@ public class Node implements Comparable<Node> {
return nb;
}
+ /**
+ * @return the neighbours of the neighbours, without this Node itself
+ */
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);
+ n.getNeighbourhood().stream().filter(n2 -> !nb.contains(n2)).forEach(nb::add);
nb.remove(this);
return nb;
}
+ /**
+ * Node a dominates a Node b if the inclusive neighbourhood of a is a subset of the inclusive neighbourhood of b.
+ * @param b the Node to compare to
+ * @return true iff this Node dominates Node b
+ */
public boolean dominates(Node b) {
for (Node nb : getInclusiveNeighbourhood())
if (!b.getInclusiveNeighbourhood().contains(nb))
@@ -49,34 +65,47 @@ public class Node implements Comparable<Node> {
return true;
}
+ /**
+ * @param b the Node to compare to
+ * @return true iff the neighbourhood of this Node is disjoint with the neighbourhood of Node b
+ */
public boolean neighbourhoodsDisjoint(Node b) {
return neighbourhoodIntersection(b).isEmpty();
}
+ /**
+ * @param b another Node
+ * @return the intersection of the neighbourhood of this Node and the neighbourhood of Node b
+ */
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;
+ return neighbours.stream().filter(n -> b.getNeighbourhood().contains(n)).collect(Collectors.toList());
}
+ /**
+ * @return a String representation of the Node
+ */
public String toString() {
return "<" + content + ">";
}
/**
* Nodes are equal if their identifiers are equal
- * @param another
- * @return
+ * @param b the Node to compare to
+ * @return true iff this Node is equivalent to Node b
*/
- public boolean equals(Object another) {
- return !(another == null || another.getClass() != this.getClass()) &&
- content == (((Node) another).content);
+ public boolean equals(Object b) {
+ return !(b == null || b.getClass() != this.getClass()) &&
+ content == (((Node) b).content);
}
+ /**
+ * This method allows sorting of Nodes by their degrees.
+ * @param b the Node to compare to
+ * @return 1 if d(this) > d(b), -1 if d(this) < d(b), 0 otherwise
+ */
@Override
- public int compareTo(Node node) {
- return node == null ? 1 : Integer.compare(neighbours.size(), node.neighbours.size());
+ @SuppressWarnings("NullableProblems")
+ public int compareTo(Node b) {
+ return Integer.compare(neighbours.size(), b.neighbours.size());
}
}
diff --git a/Practical1/tester/test.sh b/Practical1/tester/test.sh
index 068d6ea..83fdccb 100755
--- a/Practical1/tester/test.sh
+++ b/Practical1/tester/test.sh
@@ -4,8 +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/*.in
-do
+for tc in ../../../tester/samples/*.in; do
answer=$(cat ${tc/in/out})
header=$(head -n1 "$tc" | tr -d '\n')
echo -n "Running $(basename $tc) $(printf '%-12s' "($answer ")$(printf '%-12s' "/ $header)") ... "
@@ -13,20 +12,20 @@ do
result=$(eval "cat '$tc' | /usr/lib/jvm/java-8-openjdk-amd64/bin/java nl.camilstaps.cs.GarbageCollectionHelper")
time_end=$(($(date +%s%N)/1000000))
time=`expr $time_end - $time_start`
- if [ $result != $answer ]
- then
+ if [ $result != $answer ]; then
echo "failure ($time ms)."
failed=$(($failed+1))
else
echo "success ($time ms)."
fi
done
-cd -
+cd - >/dev/null
-if [ $failed -eq 0 ]
-then
- echo "All tests passed"
+if [ $failed -eq 0 ]; then
+ echo "All tests passed."
+elif [ $failed -eq 1 ]; then
+ echo "1 test failed."
else
- echo "$failed tests failed"
+ echo "$failed tests failed."
fi