Binary file cws/cw01.pdf has changed
--- a/cws/cw01.tex Thu Dec 08 12:50:54 2016 +0000
+++ b/cws/cw01.tex Tue Dec 13 13:02:52 2016 +0000
@@ -21,7 +21,8 @@
code! It has a different meaning in Scala, than in Java.
Do not use \texttt{var}! This declares a mutable variable. Make sure the
functions you submit are defined on the ``top-level'' of Scala, not
-inside a class or object.
+inside a class or object. Also note that the running time of
+each part will be restricted to a maximum of 360 seconds.
\subsection*{Disclaimer}
Binary file cws/cw02.pdf has changed
--- a/cws/cw02.tex Thu Dec 08 12:50:54 2016 +0000
+++ b/cws/cw02.tex Tue Dec 13 13:02:52 2016 +0000
@@ -34,7 +34,9 @@
copy any code you need from files \texttt{knight1.scala},
\texttt{knight2.scala} and \texttt{knight3.scala}. Make sure the
functions you submit are defined on the ``top-level'' of Scala, not
-inside a class or object.
+inside a class or object. Also note that the running time of
+each part will be restricted to a maximum of 360 seconds.
+
\subsection*{Disclaimer}
@@ -319,19 +321,19 @@
\item[(3a)] Write a function ordered-moves that calculates a list of
onward moves like in (1b) but orders them according to the
Warnsdorf’s rule. That means moves with the fewest legal onward moves
- should come first (in order to be tried out first).
+ should come first (in order to be tried out first). \hfill[1 Mark]
\item[(3b)] Implement a first-closed-tour-heuristic function that searches for a
\textbf{closed} tour on a $6\times 6$ board. It should use the
first-function from (2a) and tries out onward moves according to
the ordered-moves function from (3a). It is more likely to find
a solution when started in the middle of the board (that is
- position $(dimension / 2, dimension / 2)$).
+ position $(dimension / 2, dimension / 2)$). \hfill[1 Mark]
\item[(3c)] Implement a first-tour-heuristic function for boards up to $50\times 50$.
It is the same function as in (3b) but searches for \textbf{open} tours. You have
to be careful to write a tail-recursive version of the first-tour-heuristic
- function otherwise you will get problems with stack-overflows.
+ function otherwise you will get problems with stack-overflows. \hfill[1 Mark]
\end{itemize}
\end{document}
Binary file cws/cw03.pdf has changed
--- a/cws/cw03.tex Thu Dec 08 12:50:54 2016 +0000
+++ b/cws/cw03.tex Tue Dec 13 13:02:52 2016 +0000
@@ -20,7 +20,9 @@
code! It has a different meaning in Scala, than in Java. Do not use
\texttt{var}! This declares a mutable variable. Make sure the
functions you submit are defined on the ``top-level'' of Scala, not
-inside a class or object.
+inside a class or object. Also note that the running time of
+each part will be restricted to a maximum of 360 seconds.
+
\subsection*{Disclaimer!!!!!!!!}
--- a/marking/knight1b_test.scala Thu Dec 08 12:50:54 2016 +0000
+++ b/marking/knight1b_test.scala Tue Dec 13 13:02:52 2016 +0000
@@ -4,16 +4,42 @@
import ExecutionContext.Implicits.global
import scala.language.postfixOps
-lazy val f = Future {
- assert(legal_moves(8, Nil, (2,2)) ==
- List((3,4), (4,3), (4,1), (3,0), (1,0), (0,1), (0,3), (1,4)))
- assert(legal_moves(8, Nil, (7,7)) == List((6,5), (5,6)))
- assert(legal_moves(8, List((4,1), (1,0)), (2,2)) ==
- List((3,4), (4,3), (3,0), (0,1), (0,3), (1,4)))
- assert(legal_moves(8, List((6,6)), (7,7)) == List((6,5), (5,6)))
- assert(legal_moves(1, Nil, (0,0)) == List())
- assert(legal_moves(2, Nil, (0,0)) == List())
- assert(legal_moves(3, Nil, (0,0)) == List((1,2), (2,1)))
+
+def count_all_tours(dim: Int) = {
+ for (i <- (0 until dim).toList;
+ j <- (0 until dim).toList) yield count_tours(dim, List((i, j)))
}
-Await.result(f, 120 second)
+def add_pair_urban(x: Pos)(y: Pos): Pos =
+ (x._1 + y._1, x._2 + y._2)
+
+def is_legal_urban(dim: Int, path: Path)(x: Pos): Boolean =
+ 0 <= x._1 && 0 <= x._2 && x._1 < dim && x._2 < dim && !path.contains(x)
+
+def moves_urban(x: Pos): List[Pos] =
+ List(( 1, 2),( 2, 1),( 2, -1),( 1, -2),
+ (-1, -2),(-2, -1),(-2, 1),(-1, 2)).map(add_pair_urban(x))
+
+def legal_moves_urban(dim: Int, path: Path, x: Pos): List[Pos] =
+ moves_urban(x).filter(is_legal_urban(dim, path))
+
+def correct_urban(dim: Int)(p: Path): Boolean = p match {
+ case Nil => true
+ case x::Nil => true
+ case x::y::p => if (legal_moves_urban(dim, p, y).contains(x)) correct_urban(dim)(y::p) else false
+}
+
+
+lazy val f = Future {
+ assert(count_all_tours(1) == List(1))
+ assert(count_all_tours(2) == List(0, 0, 0, 0))
+ assert(count_all_tours(3) == List(0, 0, 0, 0, 0, 0, 0, 0, 0))
+ assert(count_all_tours(4) == List(0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0))
+ assert(count_all_tours(5) == List(304, 0, 56, 0, 304, 0, 56, 0, 56, 0, 56, 0, 64, 0, 56, 0, 56, 0, 56, 0, 304, 0, 56, 0, 304))
+
+ val ts = enum_tours(5, List((0, 2)))
+ assert(ts.map(correct_urban(5)).forall(_ == true) == true)
+ assert(ts.length == 56)
+}
+
+Await.result(f, 360 second)
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/marking/knight2b_test.scala Tue Dec 13 13:02:52 2016 +0000
@@ -0,0 +1,38 @@
+
+import scala.concurrent._
+import scala.concurrent.duration._
+import ExecutionContext.Implicits.global
+import scala.language.postfixOps
+
+
+def add_pair_urban(x: Pos)(y: Pos): Pos =
+ (x._1 + y._1, x._2 + y._2)
+
+def is_legal_urban(dim: Int, path: Path)(x: Pos): Boolean =
+ 0 <= x._1 && 0 <= x._2 && x._1 < dim && x._2 < dim && !path.contains(x)
+
+def moves_urban(x: Pos): List[Pos] =
+ List(( 1, 2),( 2, 1),( 2, -1),( 1, -2),
+ (-1, -2),(-2, -1),(-2, 1),(-1, 2)).map(add_pair_urban(x))
+
+def legal_moves_urban(dim: Int, path: Path, x: Pos): List[Pos] =
+ moves_urban(x).filter(is_legal_urban(dim, path))
+
+def correct_urban(dim: Int)(p: Path): Boolean = p match {
+ case Nil => true
+ case x::Nil => true
+ case x::y::p =>
+ if (legal_moves_urban(dim, p, y).contains(x)) correct_urban(dim)(y::p) else false
+}
+
+
+lazy val f = Future {
+
+ val ts1 = first_tour(8, List((0, 0))).get
+ assert(correct_urban(8)(ts1) == true)
+
+ val ts2 = first_tour(4, List((0, 0)))
+ assert(ts2 == None)
+}
+
+Await.result(f, 300 second)
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/marking/knight3a_test.scala Tue Dec 13 13:02:52 2016 +0000
@@ -0,0 +1,15 @@
+
+import scala.concurrent._
+import scala.concurrent.duration._
+import ExecutionContext.Implicits.global
+import scala.language.postfixOps
+
+lazy val f = Future {
+
+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)))
+assert( ordered_moves(8, List((0,4)), (0,0)) == List((1,2), (2,1)))
+
+}
+
+Await.result(f, 120 second)
--- a/marking/mark01b Thu Dec 08 12:50:54 2016 +0000
+++ b/marking/mark01b Tue Dec 13 13:02:52 2016 +0000
@@ -39,7 +39,7 @@
if (scala_compile drumb.scala)
then
- echo " --> success" | tee -a $out
+ echo " --> yes" | tee -a $out
tsts=$(( 0 ))
else
echo " --> scala did not run drumb.scala" | tee -a $out
--- a/marking/mark02 Thu Dec 08 12:50:54 2016 +0000
+++ b/marking/mark02 Tue Dec 13 13:02:52 2016 +0000
@@ -6,7 +6,7 @@
echo "" > $out
echo "Below is the feedback and provisional mark for your submission" >> $out
-echo "for CW 7. Please note all marks are provisional until" >> $out
+echo "for CW 7, Part 1. Please note all marks are provisional until" >> $out
echo "ratified by the assessment board -- this is not an official" >> $out
echo "results transcript." >> $out
echo "" >> $out
@@ -33,38 +33,57 @@
# marks for CW2
marks=$(( 0 ))
-# var, comments test
-echo "knight1.scala contains any vars, returns etc?" | tee -a $out
+# knights1: var, comments test
+
+echo "knight1.scala does not contain vars, returns etc?" | tee -a $out
if (scala_vars knight1.scala)
then
echo " --> fail" | tee -a $out
tsts0=$(( 1 ))
else
- echo " --> success" | tee -a $out
+ echo " --> yes" | tee -a $out
tsts0=$(( 0 ))
fi
# compilation test
-if [ $tsts0 -eq 0 ]
+
+if [ $tsts0 -eq 0 ]
then
echo "knight1.scala runs?" | tee -a $out
if (scala_compile knight1.scala.bak)
then
- echo " --> success" | tee -a $out
+ echo " --> yes" | tee -a $out
tsts1=$(( 0 ))
else
echo " --> scala did not run knight1.scala" | tee -a $out
tsts1=$(( 1 ))
fi
+else
+ tsts1=$(( 1 ))
fi
### knight1a test
if [ $tsts1 -eq 0 ]
then
+ echo " is_legal(8, Nil) (3,4) == true " | tee -a $out
+ echo " is_legal(8, (4,1) (1,0)) (4,1) == false " | tee -a $out
+ echo " is_legal(2, Nil) (0,0) == true" | tee -a $out
+
+ if (scala_assert "knight1.scala.bak" "../../../marking/knight1c_test.scala")
+ then
+ echo " --> success" | tee -a $out
+ marks=$(( marks + 1 ))
+ else
+ echo " --> test failed" | tee -a $out
+ fi
+fi
+
+if [ $tsts1 -eq 0 ]
+then
echo " legal_moves(8, Nil, (2,2)) = (3,4), (4,3), (4,1), (3,0), (1,0), (0,1), (0,3), (1,4)" | tee -a $out
echo " legal_moves(8, Nil, (7,7)) = (6,5), (5,6)" | tee -a $out
echo " legal_moves(8, (4,1), (1,0), (2,2)) = (3,4), (4,3), (3,0), (0,1), (0,3), (1,4)" | tee -a $out
@@ -73,7 +92,7 @@
echo " legal_moves(2, Nil, (0,0)) = Nil" | tee -a $out
echo " legal_moves(3, Nil, (0,0)) = (1,2), (2,1)" | tee -a $out
- if (scala_assert "knight1.scala" "../../../marking/knight1_test.scala")
+ if (scala_assert "knight1.scala.bak" "../../../marking/knight1_test.scala")
then
echo " --> success" | tee -a $out
marks=$(( marks + 1 ))
@@ -82,44 +101,126 @@
fi
fi
+### knight1b test
+
+if [ $tsts1 -eq 0 ]
+then
+ echo " all_tours from every position on the board" | tee -a $out
+ echo " dim = 1: 1" | tee -a $out
+ echo " 2: 0,0,0,0" | tee -a $out
+ echo " 3: 0,0,0,0,0,0,0,0,0" | tee -a $out
+ echo " 4: 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0" | tee -a $out
+ echo " 5: 304,0,56,0,304,0,56,0,56,0,56,0,64,0,56,0,56,0,56,0,304,0,56,0,304" | tee -a $out
+ echo " enum_tours(5, (0,2) ) = 56 and all correct?" | tee -a $out
+
+ if (scala_assert "knight1.scala.bak" "../../../marking/knight1b_test.scala")
+ then
+ echo " --> success" | tee -a $out
+ marks=$(( marks + 2 ))
+ else
+ echo " --> test failed" | tee -a $out
+ fi
+fi
+
+
+
+# knights2: var, comments test
+
+echo "knight2.scala does not contain vars, returns etc?" | tee -a $out
+
+if (scala_vars knight2.scala)
+then
+ echo " --> fail" | tee -a $out
+ tsts0=$(( 1 ))
+else
+ echo " --> yes" | tee -a $out
+ tsts0=$(( 0 ))
+fi
+
+
+# compilation test
+if [ $tsts0 -eq 0 ]
+then
+ echo "knight2.scala runs?" | tee -a $out
+
+ if (scala_compile knight2.scala.bak)
+ then
+ echo " --> yes" | tee -a $out
+ tsts1=$(( 0 ))
+ else
+ echo " --> scala did not run knight2.scala" | tee -a $out
+ tsts1=$(( 1 ))
+ fi
+else
+ tsts1=$(( 1 ))
+fi
+
### knight2 test
-#if [ $tsts -eq 0 ]
+if [ $tsts1 -eq 0 ]
+then
+ echo " Let f = (x:(Int, Int)) => if (x._1 > 3) Some(List(x)) else None " | tee -a $out
+ echo " first((1,0),(2,0),(3,0),(4,0), f) == Some(List((4,0)))" | tee -a $out
+ echo " first((1,0),(2,0),(3,0), f) == None" | tee -a $out
+
+ if (scala_assert "knight2.scala.bak" "../../../marking/knight2_test.scala")
+ then
+ echo " --> success" | tee -a $out
+ marks=$(( marks + 1 ))
+ else
+ echo " --> test failed" | tee -a $out
+ fi
+fi
+
+### knight2b test
+
+if [ $tsts1 -eq 0 ]
+then
+ echo " is first_tour(8, (0, 0)) ok? " | tee -a $out
+ echo " is first_tour(4, (0, 0)) == None " | tee -a $out
+
+ if (scala_assert "knight2.scala.bak" "../../../marking/knight2b_test.scala")
+ then
+ echo " --> success" | tee -a $out
+ marks=$(( marks + 2 ))
+ else
+ echo " --> test failed" | tee -a $out
+ fi
+fi
+
+
+# knights3: var, comments test
+#
+#echo "knight3.scala does not contain vars, returns etc?" | tee -a $out
+
+#if (scala_vars knight3.scala)
#then
-# echo " legal_moves(8, Nil, (2,2) = (3,4), (4,3), (4,1), (3,0), (1,0), (0,1), (0,3), (1,4)" | tee -a $out
-# echo " List(List(Some(0.07596697626574789), None), " | tee -a $out
-# echo " List(Some(-0.152620823795232), None)," | tee -a $out
-# echo " List(Some(0.20126676681483952), Some(0.9277165354330709))," | tee -a $out
-# echo " List(Some(0.09141762603007778), Some(2.119679764725104)))" | tee -a $out
-#
-# if (scala_assert "drumb.scala" "../drumb_test2.scala")
-# then
-# echo " --> success" | tee -a $out
-# marks=$(( marks + 1 ))
-# else
-# echo " --> test failed" | tee -a $out
-# fi
+# echo " --> fail" | tee -a $out
+# tsts0=$(( 1 ))
+#else
+# echo " --> success" | tee -a $out
+# tsts0=$(( 0 ))
#fi
-### knight3 test
-#if [ $tsts -eq 0 ]
-#then
-# echo " yearly_yield(IBM + BIDU, 04 - 08, 100, 0) - 107).abs <= 2 " | tee -a $out
-# echo " yearly_yield(IBM + BIDU, 04 - 08, 100, 1) - 85).abs <= 2 " | tee -a $out
-# echo " yearly_yield(IBM + BIDU, 04 - 08, 100, 2) - 156).abs <= 2 " | tee -a $out
-# echo " yearly_yield(IBM + BIDU, 04 - 08, 100, 3) - 210).abs <= 2 " | tee -a $out
-# echo " investment(List(\"IBM\", \"BIDU\"), 2004 to 2008, 100) - 298).abs <= 10" | tee -a $out
-#
-# if (scala_assert "drumb.scala" "../drumb_test3.scala")
+# compilation test
+#if [ $tsts0 -eq 0 ]
+#then
+# echo "knight3.scala runs?" | tee -a $out
+#
+# if (scala_compile knight3.scala.bak)
# then
# echo " --> success" | tee -a $out
-# marks=$(( marks + 1 ))
+# tsts1=$(( 0 ))
# else
-# echo " --> test failed" | tee -a $out
+# echo " --> scala did not run knight3.scala" | tee -a $out
+# tsts1=$(( 1 ))
# fi
+#else
+# tsts1=$(( 1 ))
#fi
+
## final marks
-echo "Overall mark for CW 2" | tee -a $out
+echo "Overall mark for CW 2, Part 1 " | tee -a $out
echo "$marks" | tee -a $out
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/marking/mark02b Tue Dec 13 13:02:52 2016 +0000
@@ -0,0 +1,74 @@
+#!/bin/bash
+set -e
+
+out=${1:-output}
+
+echo "" > $out
+
+echo "Below is the feedback and provisional mark for your submission" >> $out
+echo "for CW 7, Part 2. Please note all marks are provisional until" >> $out
+echo "ratified by the assessment board -- this is not an official" >> $out
+echo "results transcript." >> $out
+echo "" >> $out
+
+function scala_vars {
+ (egrep 'var|return|ListBuffer|mutable' "$1" 2> /dev/null 1> /dev/null)
+}
+
+
+# compilation tests
+
+function scala_compile {
+ (scala "$1" 2> /dev/null 1> /dev/null)
+}
+
+
+# functional tests
+
+function scala_assert {
+ (scala -i "$1" "$2" -e "" 2> /dev/null 1> /dev/null)
+}
+
+
+# marks for CW2b
+marks=$(( 0 ))
+
+
+# knights3: var, comments test
+#
+echo "knight3.scala does not contain vars, returns etc?" | tee -a $out
+
+if (scala_vars knight3.scala)
+then
+ echo " --> fail" | tee -a $out
+ tsts0=$(( 1 ))
+else
+ echo " --> yes" | tee -a $out
+ tsts0=$(( 0 ))
+fi
+
+
+# compilation test
+if [ $tsts0 -eq 0 ]
+then
+ echo "knight3.scala runs?" | tee -a $out
+
+ if (scala_compile knight3.scala.bak)
+ then
+ echo " --> yes" | tee -a $out
+ tsts1=$(( 0 ))
+ else
+ echo " --> scala knight3.scala did not run successfully" | tee -a $out
+ tsts1=$(( 1 ))
+ fi
+else
+ tsts1=$(( 1 ))
+fi
+
+
+
+
+
+## final marks
+echo "Overall mark for CW 7, Part 2" | tee -a $out
+echo "$marks" | tee -a $out
--- a/progs/knight1_sol.scala Thu Dec 08 12:50:54 2016 +0000
+++ b/progs/knight1_sol.scala Tue Dec 13 13:02:52 2016 +0000
@@ -20,6 +20,10 @@
def is_legal(dim: Int, path: Path)(x: Pos): Boolean =
0 <= x._1 && 0 <= x._2 && x._1 < dim && x._2 < dim && !path.contains(x)
+assert(is_legal(8, Nil)((3,4)) == true)
+assert(is_legal(8, List((4,1), (1,0)))((4,1)) == false)
+assert(is_legal(2, Nil)((0,0)) == true)
+
def moves(x: Pos): List[Pos] =
List(( 1, 2),( 2, 1),( 2, -1),( 1, -2),
(-1, -2),(-2, -1),(-2, 1),(-1, 2)).map(add_pair(x))
@@ -50,9 +54,9 @@
(for (x <- legal_moves(dim, path, path.head)) yield enum_tours(dim, x::path)).flatten
}
-def count_all_tours(dim: Int): Int = {
- (for (i <- (0 until dim).toList;
- j <- (0 until dim).toList) yield count_tours(dim, List((i, j)))).sum
+def count_all_tours(dim: Int) = {
+ for (i <- (0 until dim).toList;
+ j <- (0 until dim).toList) yield count_tours(dim, List((i, j)))
}
def enum_all_tours(dim: Int): List[Path] = {
@@ -60,6 +64,29 @@
j <- (0 until dim).toList) yield enum_tours(dim, List((i, j)))).flatten
}
+
+def add_pair_urban(x: Pos)(y: Pos): Pos =
+ (x._1 + y._1, x._2 + y._2)
+
+def is_legal_urban(dim: Int, path: Path)(x: Pos): Boolean =
+ 0 <= x._1 && 0 <= x._2 && x._1 < dim && x._2 < dim && !path.contains(x)
+
+def moves_urban(x: Pos): List[Pos] =
+ List(( 1, 2),( 2, 1),( 2, -1),( 1, -2),
+ (-1, -2),(-2, -1),(-2, 1),(-1, 2)).map(add_pair_urban(x))
+
+def legal_moves_urban(dim: Int, path: Path, x: Pos): List[Pos] =
+ moves_urban(x).filter(is_legal_urban(dim, path))
+
+def correct_urban(dim: Int)(p: Path): Boolean = p match {
+ case Nil => true
+ case x::Nil => true
+ case x::y::p => if (legal_moves_urban(dim, p, y).contains(x)) correct_urban(dim)(y::p) else false
+}
+
+enum_tours(5, List((0, 2))).map(correct_urban(5)).forall(_ == true)
+
+
for (dim <- 1 to 5) {
println(s"${dim} x ${dim} " + count_tours(dim, List((0, 0))))
}
--- a/progs/knight2_sol.scala Thu Dec 08 12:50:54 2016 +0000
+++ b/progs/knight2_sol.scala Tue Dec 13 13:02:52 2016 +0000
@@ -36,6 +36,10 @@
}
}
+first(List((1, 0),(2, 0),(3, 0),(4, 0)), (x => if (x._1 > 3) Some(List(x)) else None))
+first(List((1, 0),(2, 0),(3, 0)), (x => if (x._1 > 3) Some(List(x)) else None))
+
+
def first_tour(dim: Int, path: Path): Option[Path] = {
if (path.length == dim * dim) Some(path)
@@ -49,7 +53,36 @@
println(s"${dim} x ${dim} " + (if (t == None) "" else { print_board(dim, t.get) ; "" }))
}
*/
+
+def add_pair_urban(x: Pos)(y: Pos): Pos =
+ (x._1 + y._1, x._2 + y._2)
+
+def is_legal_urban(dim: Int, path: Path)(x: Pos): Boolean =
+ 0 <= x._1 && 0 <= x._2 && x._1 < dim && x._2 < dim && !path.contains(x)
+
+def moves_urban(x: Pos): List[Pos] =
+ List(( 1, 2),( 2, 1),( 2, -1),( 1, -2),
+ (-1, -2),(-2, -1),(-2, 1),(-1, 2)).map(add_pair_urban(x))
+
+def legal_moves_urban(dim: Int, path: Path, x: Pos): List[Pos] =
+ moves_urban(x).filter(is_legal_urban(dim, path))
+
+def correct_urban(dim: Int)(p: Path): Boolean = p match {
+ case Nil => true
+ case x::Nil => true
+ case x::y::p =>
+ if (legal_moves_urban(dim, p, y).contains(x)) correct_urban(dim)(y::p) else false
+}
+
+
+
+val ts1 = first_tour(8, List((0, 0))).get
+ assert(correct_urban(8)(ts1) == true)
+
+val ts2 = first_tour(4, List((0, 0)))
+assert(ts2 == None)
+
print_board(8, first_tour(8, List((0, 0))).get)