Binary file cws/cw03.pdf has changed
--- a/cws/cw03.tex Thu Oct 31 09:49:33 2019 +0000
+++ b/cws/cw03.tex Thu Oct 31 10:44:10 2019 +0000
@@ -210,7 +210,7 @@
-\subsection*{Part 1 (6 Marks)}
+\subsection*{Preliminary Part (4 Marks)}
You are asked to implement the knight's tour problem such that the
dimension of the board can be changed. Therefore most functions will
@@ -296,8 +296,10 @@
19591828170979904, respectively.}\smallskip
+\subsection*{Core Part (6 Marks)}
-\subsubsection*{Tasks (cont.)}
+
+\subsubsection*{Tasks (file knight1.scala cont.)}
\begin{itemize}
\item[(4)] Implement a \texttt{first}-function. This function takes a list of
@@ -341,12 +343,10 @@
sizes of up to $8 \times 8$.
\bigskip
+%%\newpage
-%%\newpage
-\subsection*{Advanced Part 2 (4 Marks)}
-
-As you should have seen in Part 1, a naive search for tours beyond
+As you should have seen in the earlier parts, a naive search for tours beyond
$8 \times 8$ boards and also searching for closed tours even on small
boards takes too much time. There is a heuristic, called \emph{Warnsdorf's
Rule} that can speed up finding a tour. This heuristic states that a
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/mk_jars Thu Oct 31 10:44:10 2019 +0000
@@ -0,0 +1,13 @@
+#!/bin/sh
+set -e
+
+for sd in solutions*; do
+ cd $sd
+ for fl in *.scala; do
+ echo "$fl compiled to ${fl%".scala"}.jar"
+ scalac -d ${fl%".scala"}.jar $fl
+ echo "copied to ../template${sd#"solutions"}"
+ cp ${fl%".scala"}.jar ../template${sd#"solutions"}
+ done
+ cd ..
+done
Binary file solutions1/collatz.jar has changed
Binary file solutions1/drumb.jar has changed
Binary file solutions2/danube.jar has changed
Binary file solutions2/docdiff.jar has changed
Binary file solutions3/knight1.jar has changed
Binary file solutions3/knight2.jar has changed
Binary file solutions3/knight3.jar has changed
Binary file solutions4/postfix.jar has changed
Binary file solutions4/postfix2.jar has changed
Binary file solutions4/re.jar has changed
Binary file solutions5/bf.jar has changed
Binary file solutions5/bfc.jar has changed
--- a/templates3/knight1.scala Thu Oct 31 09:49:33 2019 +0000
+++ b/templates3/knight1.scala Thu Oct 31 10:44:10 2019 +0000
@@ -1,5 +1,8 @@
-// Part 1 about finding Knight's tours
-//=====================================
+// Preliminary Part about finding Knight's tours
+//===============================================
+
+
+object CW8a {
// If you need any auxiliary function, feel free to
// implement it, but do not make any changes to the
@@ -26,7 +29,7 @@
//def legal_moves(dim: Int, path: Path, x: Pos) : List[Pos] = ...
-//some test cases
+//some testcases
//
//assert(legal_moves(8, Nil, (2,2)) ==
// List((3,4), (4,3), (4,1), (3,0), (1,0), (0,1), (0,3), (1,4)))
@@ -46,7 +49,7 @@
//def enum_tours(dim: Int, path: Path) : List[Path] = ...
-//(5) Implement a first-function that finds the first
+//(4) Implement a first-function that finds the first
// element, say x, in the list xs where f is not None.
// In that case Return f(x), otherwise None. If possible,
// calculate f(x) only once.
@@ -54,16 +57,15 @@
//def first(xs: List[Pos], f: Pos => Option[Path]) : Option[Path] = ...
-// test cases
+// testcases
+//
//def foo(x: (Int, Int)) = if (x._1 > 3) Some(List(x)) else None
//
//first(List((1, 0),(2, 0),(3, 0),(4, 0)), foo) // Some(List((4,0)))
//first(List((1, 0),(2, 0),(3, 0)), foo) // None
-
-
-//(6) Implement a function that uses the first-function from (5) for
+//(5) Implement a function that uses the first-function from (5) for
// trying out onward moves, and searches recursively for a
// knight tour on a dim * dim-board.
@@ -92,6 +94,9 @@
// in order to print out the time that is needed for
// running count_tours
+
+
+
// for printing a board
def print_board(dim: Int, path: Path): Unit = {
println
@@ -105,3 +110,5 @@
*/
+
+}
--- a/templates3/knight2.scala Thu Oct 31 09:49:33 2019 +0000
+++ b/templates3/knight2.scala Thu Oct 31 10:44:10 2019 +0000
@@ -1,5 +1,9 @@
-// Part 2 about finding a single tour for a board using the Warnsdorf Rule
-//=========================================================================
+// Core Part about finding a single tour for a board using the
+// Warnsdorf Rule
+//==============================================================
+
+object CW8b {
+
// !!! Copy any function you need from file knight1.scala !!!
//
@@ -34,3 +38,6 @@
//def first_tour_heuristic(dim: Int, path: Path) : Option[Path] = ...
+
+
+}
--- a/templates3/knight3.scala Thu Oct 31 09:49:33 2019 +0000
+++ b/templates3/knight3.scala Thu Oct 31 10:44:10 2019 +0000
@@ -1,6 +1,7 @@
// Finding a single tour on a "mega" board
//=========================================
+object CW8c {
// !!! Copy any function you need from file knight1.scala !!!
// !!! or knight2.scala !!!
@@ -22,3 +23,4 @@
//def tour_on_mega_board(dim: Int, path: Path) : Option[Path] = ...
+}
--- a/testing3/knight2.scala Thu Oct 31 09:49:33 2019 +0000
+++ b/testing3/knight2.scala Thu Oct 31 10:44:10 2019 +0000
@@ -1,7 +1,7 @@
// Part 3 about finding a single tour using the Warnsdorf Rule
//=============================================================
-//object CW8b { // for preparing the jar
+object CW8b {
type Pos = (Int, Int)
type Path = List[Pos]
@@ -91,4 +91,4 @@
// will be called with boards up to 30 x 30
-//}
+}
--- a/testing3/knight2_test.sh Thu Oct 31 09:49:33 2019 +0000
+++ /dev/null Thu Jan 01 00:00:00 1970 +0000
@@ -1,173 +0,0 @@
-#!/bin/bash
-
-# to make the script fail safely
-set -euo pipefail
-
-
-out=${1:-output}
-
-echo "" > $out
-
-echo -e "Below is the feedback for your submission of CW 8, Core Part." >> $out
-echo -e "" >> $out
-
-
-
-# compilation tests
-
-function scala_compile {
- (ulimit -t 30; JAVA_OPTS="-Xmx1g" scala "$1" 2>> $out 1>> $out)
-}
-
-# functional tests
-
-function scala_assert_slow {
- (ulimit -t 120; JAVA_OPTS="-Xmx1g" scala -i "$1" "-- $2" 2> /dev/null 1> /dev/null)
-}
-
-function scala_assert_thirty {
- (ulimit -t 30; JAVA_OPTS="-Xmx1g" scala -i "$1" -- "$2" 2> /dev/null 1> /dev/null)
-}
-
-function scala_assert_quick {
- (ulimit -t 30; JAVA_OPTS="-Xmx1g" scala -i "$1" -- "$2" 2> /dev/null 1> /dev/null)
-}
-
-
-# purity test
-
-function scala_vars {
- (egrep '\bvar\b|\breturn\b|\.par|ListBuffer|mutable|new Array' "$1" 2> /dev/null 1> /dev/null)
-}
-
-
-
-
-
-
-
-
-# knights2: purity test
-#
-echo -e "knight2.scala does not contain vars, returns, Arrays, ListBuffers etc?" >> $out
-
-
-if (scala_vars knight2.scala)
-then
- echo -e " --> fail (make triple-sure your program conforms to the required format)" >> $out
- tsts0=$(( 0 ))
-else
- echo -e " --> success" >> $out
- tsts0=$(( 0 ))
-fi
-
-
-# compilation test
-if [ $tsts0 -eq 0 ]
-then
- echo -e "knight2.scala runs?" >> $out
-
- if (scala_compile knight2.scala)
- then
- echo -e " --> success" >> $out
- tsts1=$(( 0 ))
- else
- echo -e " --> SCALA DID NOT RUN KNIGHT2.SCALA\n" >> $out
- tsts1=$(( 1 ))
- fi
-else
- tsts1=$(( 1 ))
-fi
-
-# ordered move test
-
-if [ $tsts1 -eq 0 ]
-then
- echo -e " ordered_moves(8, List((3,4), (3,2)), (1,3)) == List((0,1), (0,5), (2,1), (2,5))" >> $out
- echo -e " ordered_moves(8, List((4,0)), (0,0)) == List((2,1), (1,2))" >> $out
- echo -e " ordered_moves(8, List((0,4)), (0,0)) == List((1,2), (2,1))" >> $out
-
- if (scala_assert "knight2.scala" "knight_test6.scala")
- then
- echo -e " --> success" >> $out
- else
- echo -e " --> \n ONE TEST FAILED\n" >> $out
- fi
-fi
-
-
-# first-closed-tour test
-
-if [ $tsts1 -eq 0 ]
-then
- echo -e " first_closed_tour_heuristic(6, List((3,3))) found and correct?" >> $out
-
- if (scala_assert "knight2.scala" "knight_test7.scala")
- then
- echo -e " --> success" >> $out
- else
- echo -e " --> \n ONE TEST FAILED\n" >> $out
- fi
-fi
-
-
-
-if [ $tsts1 -eq 0 ]
-then
- echo -e " first_tour_heuristic(8, List((0,0))) found and correct?" >> $out
- echo -e " first_tour_heuristic(30, List((0,0))) found and correct?" >> $out
-
- if (scala_assert "knight2.scala" "knight_test8.scala")
- then
- echo -e " --> success" >> $out
- else
- echo -e " --> \n ONE TEST FAILED\n" >> $out
- fi
-fi
-
-
-# knights3: purity test
-#
-echo -e "knight3.scala does not contain vars, returns, Arrays, ListBuffers etc?" >> $out
-
-
-if (scala_vars knight3.scala)
-then
- echo " --> test failed" >> $out
- tsts0=$(( 0 ))
-else
- echo " --> success" >> $out
- tsts0=$(( 0 ))
-fi
-
-
-# compilation test
-if [ $tsts0 -eq 0 ]
-then
- echo "knight3.scala runs?" >> $out
-
- if (scala_compile knight3.scala)
- then
- echo " --> success" >> $out
- tsts1=$(( 0 ))
- else
- echo -e " --> SCALA DID NOT RUN KNIGHT3.SCALA\n" >> $out
- tsts1=$(( 1 ))
- fi
-else
- tsts1=$(( 1 ))
-fi
-
-
-if [ $tsts1 -eq 0 ]
-then
- echo -e " tour_on_mega_board(70, List((0,0))) found and correct?" >> $out
-
- if (scala_assert "knight3.scala" "knight_test9.scala")
- then
- echo -e " --> success" >> $out
- else
- echo -e " --> \n ONE TEST FAILED\n" >> $out
- fi
-fi
-
--- a/testing3/knight3.scala Thu Oct 31 09:49:33 2019 +0000
+++ b/testing3/knight3.scala Thu Oct 31 10:44:10 2019 +0000
@@ -1,7 +1,7 @@
// Part 3 about finding a single tour using the Warnsdorf Rule
//=============================================================
-//object CW8c { // for preparing the jar
+object CW8c {
type Pos = (Int, Int)
type Path = List[Pos]
@@ -60,4 +60,4 @@
def tour_on_mega_board(dim: Int, path: Path) =
time_needed(ttour_on_mega_board(dim: Int, path: Path))
-//}
+}
--- a/testing3/knight_test.sh Thu Oct 31 09:49:33 2019 +0000
+++ b/testing3/knight_test.sh Thu Oct 31 10:44:10 2019 +0000
@@ -7,7 +7,13 @@
echo -e "Below is the feedback for your submission of CW 8" >> $out
echo -e "" >> $out
-
+echo -e "!! Important: !!" >> $out
+echo -e "Because of limitations with our testing infrastructure, we can only" >> $out
+echo -e "let code run for 10 seconds and then have to kill it. This might" >> $out
+echo -e "mean your code is correct, but still marked as Fail. Remember" >> $out
+echo -e "you can test your code on your own machine and benchmark it" >> $out
+echo -e "against the reference implementation." >> $out
+echo -e "" >> $out
# compilation tests
@@ -26,7 +32,7 @@
}
function scala_assert_quick {
- (ulimit -t 30; JAVA_OPTS="-Xmx1g" scala -i "$1" -- "$2" 2> /dev/null 1> /dev/null)
+ (ulimit -t 30; JAVA_OPTS="-Xmx1g" scala -i "$1" -- "$2" 2> /dev/null 1> /dev/null)
}
# purity test
@@ -134,7 +140,7 @@
if [ $tsts1 -eq 0 ]
then
- echo -e "Takes 10 seconds or less to execute: " >> $out
+ echo -e "For testing needs to take 10 seconds or less to execute: " >> $out
echo -e " Let f = (x:(Int, Int)) => if (x._1 > 3) Some(List(x)) else None " >> $out
echo -e " first(List((1,0),(2,0),(3,0),(4,0)), f) == Some(List((4,0)))" >> $out
echo -e " first(List((1,0),(2,0),(3,0)), f) == None" >> $out
@@ -152,7 +158,7 @@
if [ $tsts1 -eq 0 ]
then
- echo -e "Takes 10 seconds or less to execute: " >> $out
+ echo -e "For testing needs to take 10 seconds or less to execute: " >> $out
echo -e " is first_tour(6, List((0, 0))) ok? " >> $out
echo -e " is first_tour(4, List((0, 0))) == None " >> $out
@@ -164,3 +170,139 @@
fi
fi
+
+echo -e "" >> $out
+echo -e "" >> $out
+
+
+# knights2: purity test
+#
+echo -e "knight2.scala does not contain vars, returns, Arrays, ListBuffers etc?" >> $out
+
+if (scala_vars knight2.scala)
+then
+ echo -e " --> Fail (make triple-sure your program conforms to the required format)" >> $out
+ tsts0=$(( 0 ))
+else
+ echo -e " --> success" >> $out
+ tsts0=$(( 0 ))
+fi
+
+
+# compilation test
+if [ $tsts0 -eq 0 ]
+then
+ echo -e "knight2.scala runs?" >> $out
+
+ if (scala_compile knight2.scala)
+ then
+ echo -e " --> success" >> $out
+ tsts1=$(( 0 ))
+ else
+ echo -e " --> SCALA DID NOT RUN KNIGHT2.SCALA\n" >> $out
+ tsts1=$(( 1 ))
+ fi
+else
+ tsts1=$(( 1 ))
+fi
+
+
+# ordered move test
+
+if [ $tsts1 -eq 0 ]
+then
+ echo -e "For testing needs to take 10 seconds or less to execute: " >> $out
+ echo -e " ordered_moves(8, List((3,4), (3,2)), (1,3)) == List((0,1), (0,5), (2,1), (2,5))" >> $out
+ echo -e " ordered_moves(8, List((4,0)), (0,0)) == List((2,1), (1,2))" >> $out
+ echo -e " ordered_moves(8, List((0,4)), (0,0)) == List((1,2), (2,1))" >> $out
+
+ if (scala_assert_quick "knight2.scala" "knight_test6.scala")
+ then
+ echo -e " --> success" >> $out
+ else
+ echo -e " --> \n ONE TEST FAILED\n" >> $out
+ fi
+fi
+
+
+# first-closed-tour test
+
+if [ $tsts1 -eq 0 ]
+then
+ echo -e "For testing needs to take 10 seconds or less to execute: " >> $out
+ echo -e " first_closed_tour_heuristic(6, List((3,3))) found and correct?" >> $out
+
+ if (scala_assert_quick "knight2.scala" "knight_test7.scala")
+ then
+ echo -e " --> success" >> $out
+ else
+ echo -e " --> \n ONE TEST FAILED\n" >> $out
+ fi
+fi
+
+
+
+if [ $tsts1 -eq 0 ]
+then
+ echo -e "For testing needs to take 10 seconds or less to execute: " >> $out
+ echo -e " first_tour_heuristic(8, List((0,0))) found and correct?" >> $out
+ echo -e " first_tour_heuristic(30, List((0,0))) found and correct?" >> $out
+
+ if (scala_assert_quick "knight2.scala" "knight_test8.scala")
+ then
+ echo -e " --> success" >> $out
+ else
+ echo -e " --> \n ONE TEST FAILED\n" >> $out
+ fi
+fi
+
+
+echo -e "" >> $out
+echo -e "" >> $out
+
+# knights3: purity test
+#
+echo -e "knight3.scala does not contain vars, returns, Arrays, ListBuffers etc?" >> $out
+
+
+if (scala_vars knight3.scala)
+then
+ echo " --> Fail (make triple-sure your program conforms to the required format)xsxs" >> $out
+ tsts0=$(( 0 ))
+else
+ echo " --> success" >> $out
+ tsts0=$(( 0 ))
+fi
+
+
+# compilation test
+if [ $tsts0 -eq 0 ]
+then
+ echo "knight3.scala runs?" >> $out
+
+ if (scala_compile knight3.scala)
+ then
+ echo " --> success" >> $out
+ tsts1=$(( 0 ))
+ else
+ echo -e " --> SCALA DID NOT RUN KNIGHT3.SCALA\n" >> $out
+ tsts1=$(( 1 ))
+ fi
+else
+ tsts1=$(( 1 ))
+fi
+
+
+if [ $tsts1 -eq 0 ]
+then
+ echo -e "For testing needs to take 10 seconds or less to execute: " >> $out
+ echo -e " tour_on_mega_board(70, List((0,0))) found and correct?" >> $out
+
+ if (scala_assert_quick "knight3.scala" "knight_test9.scala")
+ then
+ echo -e " --> success" >> $out
+ else
+ echo -e " --> \n ONE TEST FAILED\n" >> $out
+ fi
+fi
+
--- a/testing3/knight_test4.scala Thu Oct 31 09:49:33 2019 +0000
+++ b/testing3/knight_test4.scala Thu Oct 31 10:44:10 2019 +0000
@@ -1,3 +1,4 @@
+import CW8a._
val f_urban = (x:(Int, Int)) => if (x._1 > 3) Some(List(x)) else None
--- a/testing3/knight_test5.scala Thu Oct 31 09:49:33 2019 +0000
+++ b/testing3/knight_test5.scala Thu Oct 31 10:44:10 2019 +0000
@@ -1,3 +1,5 @@
+import CW8a._
+
//type Pos = (Int, Int) // a position on a chessboard
//type Path = List[Pos] // a path...a list of positions
--- a/testing3/knight_test6.scala Thu Oct 31 09:49:33 2019 +0000
+++ b/testing3/knight_test6.scala Thu Oct 31 10:44:10 2019 +0000
@@ -1,4 +1,4 @@
-
+import CW8b._
assert(ordered_moves(8, List((3,4), (3,2)), (1, 3)) == List((0,1), (0,5), (2,1), (2,5)))
assert(ordered_moves(8, List((4,0)), (0,0)) == List((2,1), (1,2)))
--- a/testing3/knight_test7.scala Thu Oct 31 09:49:33 2019 +0000
+++ b/testing3/knight_test7.scala Thu Oct 31 10:44:10 2019 +0000
@@ -1,3 +1,4 @@
+import CW8b._
//type Pos = (Int, Int)
//type Path = List[Pos]
--- a/testing3/knight_test8.scala Thu Oct 31 09:49:33 2019 +0000
+++ b/testing3/knight_test8.scala Thu Oct 31 10:44:10 2019 +0000
@@ -1,3 +1,5 @@
+import CW8b._
+
//type Pos = (Int, Int)
//type Path = List[Pos]
--- a/testing3/knight_test9.scala Thu Oct 31 09:49:33 2019 +0000
+++ b/testing3/knight_test9.scala Thu Oct 31 10:44:10 2019 +0000
@@ -1,3 +1,4 @@
+import CW8c._
//type Pos = (Int, Int)
//type Path = List[Pos]