# HG changeset patch
# User Christian Urban <christian dot urban at kcl dot ac dot uk>
# Date 1479000452 0
# Node ID a5106bc13db65ba370c0f00ee9071b158366c24f
# Parent  1fe8205f6bdb3e79f1e35214a09c109d7a7ec9c4
updated

diff -r 1fe8205f6bdb -r a5106bc13db6 cws/cw01.pdf
Binary file cws/cw01.pdf has changed
diff -r 1fe8205f6bdb -r a5106bc13db6 cws/cw01.tex
--- a/cws/cw01.tex	Sat Nov 12 22:28:14 2016 +0000
+++ b/cws/cw01.tex	Sun Nov 13 01:27:32 2016 +0000
@@ -215,7 +215,7 @@
 \end{itemize}\medskip  
 
 \noindent
-\textbf{Tasks (file drump.scala):}
+\textbf{Tasks (file drumb.scala):}
 
 \begin{itemize}
 \item[(1.a)] Write a function that queries the Yahoo financial data
diff -r 1fe8205f6bdb -r a5106bc13db6 cws/cw02.pdf
Binary file cws/cw02.pdf has changed
diff -r 1fe8205f6bdb -r a5106bc13db6 cws/cw02.tex
--- a/cws/cw02.tex	Sat Nov 12 22:28:14 2016 +0000
+++ b/cws/cw02.tex	Sun Nov 13 01:27:32 2016 +0000
@@ -15,10 +15,13 @@
 
 \section*{Coursework 7 (Scala, Knight's Tour)}
 
-This coursework is worth 10\%. The first part is due on 23 November
-at 11pm; the second, more advanced part, is due on 30 November at
-11pm. You are asked to implement Scala programs that solve various
-versions of the \textit{Knight's Tour Problem} on a chessboard.
+This coursework is about depth-first search in Scala and worth
+10\%. The first part is due on 23 November at 11pm; the second, more
+advanced part, is due on 30 November at 11pm. You are asked to
+implement Scala programs that solve various versions of the
+\textit{Knight's Tour Problem} on a chessboard. Make sure the files
+you submit can be processed by just calling \texttt{scala
+  <<filename.scala>>}.
  
 \subsection*{Disclaimer}
 
@@ -30,8 +33,9 @@
 \subsection*{Background}
 
 The \textit{Knight's Tour Problem} is about finding a tour such that
-the knight visits every field on a $n\times n$ chessboard once. For
-example on a $5\times 5$ chessboard, a knight's tour is as follows:
+the knight visits every field on a $n\times n$ chessboard once and
+only once. For example on a $5\times 5$ chessboard, a knight's tour is
+as follows:
 
 
 \chessboard[maxfield=e5, 
diff -r 1fe8205f6bdb -r a5106bc13db6 progs/knight2.scala
--- a/progs/knight2.scala	Sat Nov 12 22:28:14 2016 +0000
+++ b/progs/knight2.scala	Sun Nov 13 01:27:32 2016 +0000
@@ -1,41 +1,44 @@
 import scala.util._
 type Pos = (Int, Int)
 
-
-def print_board(n: Int)(steps: List[Pos]): Unit = {
-  for (i <- 0 until n) {
-    for (j <- 0 until n) {
-      print(f"${steps.indexOf((i, j))}%3.0f ")
-    }
-    println
-  } 
-  //readLine()
-  System.exit(0)
-}
-
-def add_pair(x: Pos)(y: Pos) = 
+def add_pair(x: Pos)(y: Pos): Pos = 
   (x._1 + y._1, x._2 + y._2)
 
-def is_legal(n: Int)(x: Pos) = 
-  0 <= x._1 && 0 <= x._2 && x._1 < n && x._2 < n
+def is_legal(dim: Int, path: List[Pos])(x: Pos): Boolean = 
+  0 <= x._1 && 0 <= x._2 && x._1 < dim && x._2 < dim && !path.contains(x)
 
-def moves(n: Int)(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)).filter(is_legal(n))
+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))
+}
+
+def legal_moves(dim: Int, path: List[Pos], x: Pos): List[Pos] = {
+  moves(x).filter(is_legal(dim, path))
 }
 
+
 // non-circle tours
-def tour(n: Int)(steps: List[Pos]): List[List[Pos]] = {
-  if (steps.length ==  n * n) // && moves(n)(steps.head).contains(steps.last)) 
-    List(steps)
+/*
+def tour(dim: Int, path: List[Pos]): List[List[Pos]] = {
+  if (path.length ==  dim * dim) // && moves(n)(path.head).contains(path.last)) 
+    List(path)
   else 
-    (for (x <- moves(n)(steps.head).par; 
-          if (!steps.contains(x))) yield tour(n)(x :: steps)).toList.flatten
+    (for (x <- legal_moves(dim, path, path.head)) yield tour(dim, x::path)).flatten
+}
+*/
+
+def tour(dim: Int, path: List[Pos]): Int = {
+  if (path.length == dim * dim) 1
+  else 
+    (for (x <- legal_moves(dim, path, path.head)) yield tour(dim, x::path)).sum
 }
 
 //val n = 8
 val n = 6
 println(s"number simple tours: n = $n")
 
-println(tour(n)(List((1,1))).distinct.size)
-//println((for (i <- 0 until n; j <- 0 until n) yield tour(n)(List((i, j)))).flatten.distinct.size) 
+//println(tour(n, List((0, 0))))
+
+for (d <- 1 to 6) {
+  println(s"${d} x ${d} " + (for (i <- 0 until d; j <- 0 until d) yield tour(d, List((i, j)))).sum)
+} 
diff -r 1fe8205f6bdb -r a5106bc13db6 style.sty
--- a/style.sty	Sat Nov 12 22:28:14 2016 +0000
+++ b/style.sty	Sun Nov 13 01:27:32 2016 +0000
@@ -4,7 +4,8 @@
 \setmainfont[Ligatures=TeX]{Palatino Linotype}
 \usepackage{amssymb}
 \usepackage{amsmath}
-\usepackage{menukeys}
+%%\usepackage{menukeys}
+
 \definecolor{darkblue}{rgb}{0,0,0.6}
 \usepackage[colorlinks=true,urlcolor=darkblue,linkcolor=darkblue]{hyperref}