--- a/TAs Fri Dec 14 20:01:49 2018 +0000
+++ b/TAs Sat Dec 15 13:46:54 2018 +0000
@@ -53,6 +53,18 @@
232 submissions
+CW9, Part 1
+
+ late (231)
+140 => 6 137
+53 => 5 56
+15 => 4 16
+5 => 3 5
+4 => 2 4
+0 => 1 0
+14 => 0 13
+--------
+231 submissions
=======================
Binary file cws/cw04.pdf has changed
--- a/cws/cw04.tex Fri Dec 14 20:01:49 2018 +0000
+++ b/cws/cw04.tex Sat Dec 15 13:46:54 2018 +0000
@@ -514,7 +514,7 @@
\end{lstlisting}
\noindent
-where the command \texttt{ldc} loads a constant onto a stack, and \texttt{imul},
+where the command \texttt{ldc} loads a constant onto the stack, and \texttt{imul},
\texttt{isub} and \texttt{iadd} are commands acting on the stack. Clearly this
is the arithmetic expression in postfix notation.\bigskip
Binary file cws/cw05.pdf has changed
--- a/cws/cw05.tex Fri Dec 14 20:01:49 2018 +0000
+++ b/cws/cw05.tex Sat Dec 15 13:46:54 2018 +0000
@@ -12,9 +12,6 @@
\begin{document}
-% BF IDE
-% https://www.microsoft.com/en-us/p/brainf-ck/9nblgggzhvq5
-
\section*{Coursework 10 (Scala)}
This coursework is worth 10\%. It is about a small programming
@@ -101,7 +98,15 @@
be implemented in brainf***. It just takes a lot of determination and
quite a lot of memory resources. Some relatively sophisticated sample
programs in brainf*** are given in the file \texttt{bf.scala}, including
-a brainf*** program for the Sierpinski triangle and the Mandelbrot set.\bigskip
+a brainf*** program for the Sierpinski triangle and the Mandelbrot set.
+There seems to be even a dedicated Windows IDE for bf programs, though
+I am not sure whether this is just an elaborate April fools' joke---judge
+yourself:
+
+\begin{center}
+\url{https://www.microsoft.com/en-us/p/brainf-ck/9nblgggzhvq5}
+\end{center}
+
\noindent
As mentioned above, brainf*** has 8 single-character commands, namely
--- a/progs/lecture1.scala Fri Dec 14 20:01:49 2018 +0000
+++ b/progs/lecture1.scala Sat Dec 15 13:46:54 2018 +0000
@@ -140,6 +140,8 @@
*/
+val name: String = "leo"
+
// Pairs/Tuples
//==============
--- a/progs/lecture5.scala Fri Dec 14 20:01:49 2018 +0000
+++ b/progs/lecture5.scala Sat Dec 15 13:46:54 2018 +0000
@@ -180,7 +180,7 @@
// input type: String
// output type: Int
-Integer.parseInt("123456")
+Integer.parseInt("123u456")
/* Note, in the previous lectures I did not show the type consraint
* I <% Seq[_] , which means that the input type I can be
@@ -241,7 +241,7 @@
val NumParser = RegexParser("[0-9]+".r)
def StringParser(s: String) = RegexParser(Regex.quote(s).r)
-println(NumParser.parse_all("12345"))
+NumParser.parse_all("12u345")
println(NumParser.parse_all("12u45"))
@@ -266,7 +266,7 @@
}
-val NumParserInt = NumParser ==> (s => s.toInt)
+val NumParserInt = NumParser ==> (s => 2 * s.toInt)
NumParser.parse_all("12345")
NumParserInt.parse_all("12345")
@@ -288,7 +288,7 @@
lazy val F: Parser[String, Int] =
("(" ~ E ~ ")") ==> { case ((x, y), z) => y } | NumParserInt
-println(E.parse_all("1+3+4"))
+
println(E.parse_all("4*2+3"))
println(E.parse_all("4*(2+3)"))
println(E.parse_all("(4)*((2+3))"))
@@ -331,7 +331,7 @@
//
// http://www.latkin.org/blog/2017/05/02/when-the-scala-compiler-doesnt-help/
-List(1, 2, 3) contains "your mom"
+List(1, 2, 3).contains("your mom")
// I like best about Scala that it lets me often write
// concise, readable code. And it hooks up with the
--- a/testing3/knight1.scala Fri Dec 14 20:01:49 2018 +0000
+++ b/testing3/knight1.scala Sat Dec 15 13:46:54 2018 +0000
@@ -1,121 +1,13 @@
-// Part 1 about finding Knight's tours
-//=====================================
+// Part 1 about finding and counting Knight's tours
+//==================================================
-// If you need any auxiliary function, feel free to
-// implement it, but do not make any changes to the
-// templates below. Also have a look whether the functions
-// at the end are of any help.
-
-
+//object CW8a { // for preparing the jar
type Pos = (Int, Int) // a position on a chessboard
type Path = List[Pos] // a path...a list of positions
-//(1) Complete the function that tests whether the position x
-// is inside the board and not yet element in the path.
-def is_legal(dim: Int, path: Path, x: Pos) : Boolean = {
- if ((x._1 < dim && x._2 < dim) && !(path.contains(x)))
- true
- else
- false
-}
-
-
-
-//(2) Complete the function that calculates for a position x
-// all legal onward moves that are not already in the path.
-// The moves should be ordered in a "clockwise" manner.
-
-
-def legal_moves(dim: Int, path: Path, x: Pos) : List[Pos] = {
- val legalMovesList = List((x._1 + 1, x._2 + 2), (x._1 + 2, x._2 + 1), (x._1 + 2, x._2 - 1), (x._1 + 1, x._2 - 2), (x._1 - 1, x._2 - 2), (x._1 - 2, x._2 - 1), (x._1 - 2, x._2 + 1), (x._1 - 1, x._2 + 2))
-
- for (i <- legalMovesList
- if (is_legal(dim, path, i)))
- yield i
-
-}
-
-
-//some test cases
-//
-//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)))
-
-
-//(3) Complete the two recursive functions below.
-// They exhaustively search for knight's tours starting from the
-// given path. The first function counts all possible tours,
-// and the second collects all tours in a list of paths.
-
-def count_tours(dim: Int, path: Path) : Int = {
- if (path.size == (dim ^ 2)){
- List(path).size
- } else {
- val totalTours = legal_moves(dim, path, path.head)
- totalTours.map(element => count_tours(dim, element :: path)).sum
- }
-}
-
-def enum_tours(dim: Int, path: Path) : List[Path] = {
- if (path.size == (dim ^ 2)){
- List(path)
- } else {
- val totalEnums = legal_moves(dim, path, path.head)
- totalEnums.map(element => enum_tours(dim, element :: path)).flatten
- }
-}
-
-
-//(5) 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.
-
-def first(xs: List[Pos], f: Pos => Option[Path]) : Option[Path] = {
- if (xs eq Nil) {
- None
- } else {
- if (f(xs.head) != None) {
- f(xs.head)
- } else {
- first(xs.tail, f)
- }
- }
-
-}
-
-
-// test cases
-//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
-// trying out onward moves, and searches recursively for a
-// knight tour on a dim * dim-board.
-
-
-//def first_tour(dim: Int, path: Path) : Option[Path] = ...
-
-
-
-
-
-
-/* Helper functions
-
-
-// for measuring time
+// for measuring time in the JAR
def time_needed[T](code: => T) : T = {
val start = System.nanoTime()
val result = code
@@ -124,11 +16,6 @@
result
}
-// can be called for example with
-// time_needed(count_tours(dim, List((0, 0))))
-// 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
@@ -140,5 +27,144 @@
}
}
+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)
+// testcases
+//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 add_pair(x: Pos, y: Pos): Pos =
+ (x._1 + y._1, x._2 + y._2)
+
+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, _))
+
+// 1 mark
+
+def legal_moves(dim: Int, path: Path, x: Pos): List[Pos] =
+ moves(x).filter(is_legal(dim, path, _))
+
+// 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)))
+//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)))
+
+// 2 marks
+
+def tcount_tours(dim: Int, path: Path): Int = {
+ if (path.length == dim * dim) 1
+ else
+ (for (x <- legal_moves(dim, path, path.head)) yield tcount_tours(dim, x::path)).sum
+}
+
+def count_tours(dim: Int, path: Path) =
+ time_needed(tcount_tours(dim: Int, path: Path))
+
+
+def tenum_tours(dim: Int, path: Path): List[Path] = {
+ if (path.length == dim * dim) List(path)
+ else
+ (for (x <- legal_moves(dim, path, path.head)) yield tenum_tours(dim, x::path)).flatten
+}
+
+def enum_tours(dim: Int, path: Path) =
+ time_needed(tenum_tours(dim: Int, path: Path))
+
+// test cases
+
+/*
+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] = {
+ (for (i <- (0 until dim).toList;
+ j <- (0 until dim).toList) yield enum_tours(dim, List((i, j)))).flatten
+}
+
+
+println("Number of tours starting from (0, 0)")
+
+for (dim <- 1 to 5) {
+ println(s"${dim} x ${dim} " + time_needed(0, count_tours(dim, List((0, 0)))))
+}
+
+println("Number of tours starting from all fields")
+
+for (dim <- 1 to 5) {
+ println(s"${dim} x ${dim} " + time_needed(0, count_all_tours(dim)))
+}
+
+for (dim <- 1 to 5) {
+ val ts = enum_tours(dim, List((0, 0)))
+ println(s"${dim} x ${dim} ")
+ if (ts != Nil) {
+ print_board(dim, ts.head)
+ println(ts.head)
+ }
+}
*/
+
+// 1 mark
+
+def first(xs: List[Pos], f: Pos => Option[Path]): Option[Path] = xs match {
+ case Nil => None
+ case x::xs => {
+ val result = f(x)
+ if (result.isDefined) result else first(xs, f)
+ }
+}
+
+// test cases
+//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)
+//first(List((1, 0),(2, 0),(3, 0)), foo)
+
+
+// 1 mark
+
+def tfirst_tour(dim: Int, path: Path): Option[Path] = {
+ if (path.length == dim * dim) Some(path)
+ else
+ first(legal_moves(dim, path, path.head), (x:Pos) => tfirst_tour(dim, x::path))
+}
+
+def first_tour(dim: Int, path: Path) =
+ time_needed(tfirst_tour(dim: Int, path: Path))
+
+
+/*
+for (dim <- 1 to 8) {
+ val t = first_tour(dim, List((0, 0)))
+ println(s"${dim} x ${dim} " + (if (t == None) "" else { print_board(dim, t.get) ; "" }))
+}
+*/
+
+// 15 secs for 8 x 8
+//val ts1 = time_needed(0,first_tour(8, List((0, 0))).get)
+
+// no result for 4 x 4
+//val ts2 = time_needed(0, first_tour(4, List((0, 0))))
+
+// 0.3 secs for 6 x 6
+//val ts3 = time_needed(0, first_tour(6, List((0, 0))))
+
+// 15 secs for 8 x 8
+//time_needed(0, print_board(8, first_tour(8, List((0, 0))).get))
+
+
+//}
+
+
--- a/testing3/knight2.scala Fri Dec 14 20:01:49 2018 +0000
+++ b/testing3/knight2.scala Sat Dec 15 13:46:54 2018 +0000
@@ -64,6 +64,9 @@
def first_closed_tour_heuristics(dim: Int, path: Path) =
time_needed(tfirst_closed_tour_heuristics(dim: Int, path: Path))
+def first_closed_tour_heuristic(dim: Int, path: Path) =
+ time_needed(tfirst_closed_tour_heuristics(dim: Int, path: Path))
+
// heuristic cannot be used to search for closed tours on 7 x 7 an beyond
//for (dim <- 1 to 6) {
@@ -82,6 +85,8 @@
def first_tour_heuristics(dim: Int, path: Path) =
time_needed(tfirst_tour_heuristics(dim: Int, path: Path))
+def first_tour_heuristic(dim: Int, path: Path) =
+ time_needed(tfirst_tour_heuristics(dim: Int, path: Path))
// will be called with boards up to 30 x 30
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/testing3/knight2_test.sh Sat Dec 15 13:46:54 2018 +0000
@@ -0,0 +1,177 @@
+#!/bin/bash
+
+# to make the script fail safely
+set -euo pipefail
+
+
+out=${1:-output}
+
+echo "" > $out
+
+echo "Below is the feedback and provisional marks for your submission" >> $out
+echo "for assignment 8 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
+
+# marks for CW8 part 2
+marks=$(( 0 ))
+
+# compilation tests
+
+function scala_compile {
+ (ulimit -t 30; JAVA_OPTS="-Xmx1g" scala -nc "$1" 2>> $out 1>> $out)
+}
+
+# functional tests
+
+
+function scala_assert {
+ (ulimit -t 30; JAVA_OPTS="-Xmx1g" scala -nc -i "$1" "$2" -e "") #2> /dev/null 1> /dev/null)
+}
+
+function scala_assert_slow {
+ (ulimit -t 120; JAVA_OPTS="-Xmx1g" scala -nc -i "$1" "$2" -e "" 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?" | tee -a $out
+
+
+if (scala_vars knight2.scala)
+then
+ echo -e " --> test failed" | tee -a $out
+ tsts0=$(( 0 ))
+else
+ echo -e " --> success" | tee -a $out
+ tsts0=$(( 0 ))
+fi
+
+
+# compilation test
+if [ $tsts0 -eq 0 ]
+then
+ echo -e "knight2.scala runs?" | tee -a $out
+
+ if (scala_compile knight2.scala)
+ then
+ echo -e " --> success" | tee -a $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))" | tee -a $out
+ echo -e " ordered_moves(8, List((4,0)), (0,0)) == List((2,1), (1,2))" | tee -a $out
+ echo -e " ordered_moves(8, List((0,4)), (0,0)) == List((1,2), (2,1))" | tee -a $out
+
+ if (scala_assert "knight2.scala" "knight_test6.scala")
+ then
+ echo -e " --> success" | tee -a $out
+ marks=$(( marks + 1 ))
+ 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?" | tee -a $out
+
+ if (scala_assert "knight2.scala" "knight_test7.scala")
+ then
+ echo -e " --> success" | tee -a $out
+ marks=$(( marks + 1 ))
+ 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?" | tee -a $out
+ echo -e " first_tour_heuristic(30, List((0,0))) found and correct?" | tee -a $out
+
+ if (scala_assert "knight2.scala" "knight_test8.scala")
+ then
+ echo -e " --> success" | tee -a $out
+ marks=$(( marks + 1 ))
+ 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?" | tee -a $out
+
+
+if (scala_vars knight3.scala)
+then
+ echo " --> test failed" | tee -a $out
+ tsts0=$(( 0 ))
+else
+ echo " --> success" | 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)
+ then
+ echo " --> success" | tee -a $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?" | tee -a $out
+
+ if (scala_assert "knight3.scala" "knight_test9.scala")
+ then
+ echo -e " --> success" | tee -a $out
+ marks=$(( marks + 1 ))
+ else
+ echo -e " --> \n ONE TEST FAILED\n" >> $out
+ fi
+fi
+
+
+## final marks
+echo "Overall mark for CW 8, Part 2" | tee -a $out
+echo "$marks" | tee -a $out
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/testing3/knight_test6.scala Sat Dec 15 13:46:54 2018 +0000
@@ -0,0 +1,19 @@
+
+
+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)))
+
+
+
+/*
+import scala.concurrent._
+import scala.concurrent.duration._
+import ExecutionContext.Implicits.global
+import scala.language.postfixOps
+
+lazy val f = Future {
+}
+
+Await.result(f, 120 second)
+*/
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/testing3/knight_test7.scala Sat Dec 15 13:46:54 2018 +0000
@@ -0,0 +1,31 @@
+
+//type Pos = (Int, Int)
+//type Path = List[Pos]
+
+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
+}
+
+def correct_closed_urban(dim: Int)(p: Path) =
+ correct_urban(6)(p) && moves_urban(p.head).contains(p.last)
+
+
+val tsc = first_closed_tour_heuristic(6, List((3, 3))).get
+assert(correct_closed_urban(6)(tsc) == true)
+
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/testing3/knight_test8.scala Sat Dec 15 13:46:54 2018 +0000
@@ -0,0 +1,31 @@
+
+//type Pos = (Int, Int)
+//type Path = List[Pos]
+
+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 ts8 = first_tour_heuristic(8, List((0,0))).get
+assert(correct_urban(8)(ts8) == true)
+
+val ts30 = first_tour_heuristic(30, List((0,0))).get
+assert(correct_urban(30)(ts30) == true)
+
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/testing3/knight_test9.scala Sat Dec 15 13:46:54 2018 +0000
@@ -0,0 +1,28 @@
+
+//type Pos = (Int, Int)
+//type Path = List[Pos]
+
+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 ts70 = tour_on_mega_board(70, List((0,0))).get
+assert(correct_urban(70)(ts70) == true)
+