Binary file cws/cw02.pdf has changed
--- a/cws/cw02.tex Fri Nov 11 11:17:40 2016 +0000
+++ b/cws/cw02.tex Sat Nov 12 18:18:59 2016 +0000
@@ -1,8 +1,7 @@
\documentclass{article}
-\usepackage{../style}
\usepackage{chessboard}
\usepackage[LSBC4,T1]{fontenc}
-
+\usepackage{../style}
\begin{document}
@@ -14,14 +13,26 @@
-\section*{Coursework 2 (Knight's Tour)}
+\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.
+
+\subsection*{Disclaimer}
-This coursework is worth XXX\% and is due on 21 November at 16:00. You
-are asked to implement a Scala program that solves the \textit{knight's
- tour problem} on an $n\times n$ chessboard. This problem is about
-finding a tour such that the knight visits every field on the
-chessboard once. One a $5\times 5$ chessboard, a knight's tour
-is as follows:
+It should be understood that the work you submit represents
+your own effort. You have not copied from anyone else. An
+exception is the Scala code I showed during the lectures or
+uploaded to KEATS, which you can freely use.\bigskip
+
+\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:
+
\chessboard[maxfield=e5,
pgfstyle= {[base,at={\pgfpoint{0pt}{-0.5ex}}]text},
@@ -53,18 +64,23 @@
]
\noindent
-The tour starts in the left-upper corner, then moves to field $(4,3)$,
-then $(5,1)$ and so on. A knight's tour is called \emph{closed}, if
+The tour starts in the right-upper corner, then moves to field $(4,3)$,
+then $(5,1)$ and so on. There are no knight's tours on $2\times 2$, $3\times 3$
+and $4\times 4$ chessboards, but for every bigger board there is.
+
+
+A knight's tour is called \emph{closed}, if
the last step in the tour is within a knight's move to the beginning
-of the tour. So the above knight's tour is not closed (that is it is
+of the tour. So the above knight's tour is \underline{not} closed (it is
open) because the last step on field $(1, 5)$ is not within the reach
of the first step on $(5, 5)$. It turns out there is no closed
-knight's tour on a $5\times 5$ board. But there is one on a $6\times
-6$ board.
+knight's tour on a $5\times 5$ board. But there are on a $6\times
+6$ board.\bigskip
-If you cannot remember how a knight moved in chess, below are all
-potential moves indicated for two knights, one on field $(3, 3)$ and
-another on $(8, 8)$:
+\noindent
+If you cannot remember how a knight moved in chess, or never played
+chess, below are all potential moves indicated for two knights, one on
+field $(3, 3)$ and another on $(8, 8)$:
\chessboard[color=blue!50,
@@ -78,12 +94,6 @@
setpieces={Nh8, Nc3}]
-\subsubsection*{Disclaimer}
-
-It should be understood that the work you submit represents
-your own effort. You have not copied from anyone else. An
-exception is the Scala code I showed during the lectures or
-uploaded to KEATS, which you can freely use.\bigskip
\subsubsection*{Task}
--- a/progs/drumb.scala Fri Nov 11 11:17:40 2016 +0000
+++ b/progs/drumb.scala Sat Nov 12 18:18:59 2016 +0000
@@ -1,4 +1,4 @@
-// Advanvced Part 3 about really dump investing strategy
+// Advanvced Part 3 about really dumb investing strategy
//=======================================================
//two test portfolios
--- a/progs/drumb_sol.scala Fri Nov 11 11:17:40 2016 +0000
+++ b/progs/drumb_sol.scala Sat Nov 12 18:18:59 2016 +0000
@@ -1,4 +1,4 @@
-// Advanvced Part 3 about really dump investing strategy
+// Advanvced Part 3 about really dumb investing strategy
//=======================================================
//two test portfolios
--- a/progs/knight2.scala Fri Nov 11 11:17:40 2016 +0000
+++ b/progs/knight2.scala Sat Nov 12 18:18:59 2016 +0000
@@ -26,9 +26,11 @@
// 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)
+ if (steps.length == n * n) // && moves(n)(steps.head).contains(steps.last))
+ List(steps)
else
- (for (x <- moves(n)(steps.head).par; if (!steps.contains(x))) yield tour(n)(x :: steps)).toList.flatten
+ (for (x <- moves(n)(steps.head).par;
+ if (!steps.contains(x))) yield tour(n)(x :: steps)).toList.flatten
}
//val n = 8
--- a/progs/lecture1.scala Fri Nov 11 11:17:40 2016 +0000
+++ b/progs/lecture1.scala Sat Nov 12 18:18:59 2016 +0000
@@ -68,8 +68,8 @@
List(1,2,3,4).drop(2).sum
List(1,2,3,4,3).indexOf(3)
-"1,2,3,4,5".split(",").toList
-
+"1,2,3,4,5".split(",").mkString("\n")
+"1,2,3,4,5".split(",3,").mkString("\n")
// Types
//=======
@@ -93,8 +93,9 @@
// Smart Strings
//===============
-println(">\n<")
+println(">\n\n<")
println(""">\n<""")
+println("""">\n<"""")
/* in Java
val lyrics = "Baa, Baa, Black Sheep \n" +
@@ -148,12 +149,26 @@
square(6)
+
+// The general scheme for a function: you have to give a type
+// to each argument and a return type of the function
+//
+// def fname(arg1: ty1, arg2: ty2,..., argn: tyn): rty = {
+// body
+// }
+
+
+
// If control structure
//======================
def fact(n: Int): Int =
if (n == 0) 1 else n * fact(n - 1)
+
+fact(5)
+fact(150)
+
/* boolean operators
== equals
@@ -239,19 +254,18 @@
-// with only a side-effect (no list is produced)
+// with only a side-effect (no list is produced),
// has no "yield"
for (n <- (1 to 10)) println(n)
-// concurrency (ONLY WORKS IN 2.11.8)
+// concurrency (ONLY WORKS IN SCALA 2.11.8, not in SCALA 2.12.0)
for (n <- (1 to 10)) println(n)
for (n <- (1 to 10).par) println(n)
-
-// for testing time
+// for measuring time
def time_needed[T](i: Int, code: => T) = {
val start = System.nanoTime()
for (j <- 1 to i) code
@@ -270,11 +284,12 @@
import io.Source
+// obtaining a webpage
val url = """http://www.inf.kcl.ac.uk/staff/urbanc/"""
Source.fromURL(url)("ISO-8859-1").mkString
-
+// function for looking up stockmarket data
def price_lookup(symbol: String): String = {
val url = "http://finance.yahoo.com/d/quotes.csv?s=" + symbol + "&f=snl1"
Source.fromURL(url).mkString.drop(1).dropRight(2)
@@ -292,6 +307,8 @@
// A Web Crawler
//===============
+//
+// the idea is to look for dead links
import io.Source
import scala.util.matching.Regex
@@ -330,26 +347,6 @@
-
-// Adding your own methods to Strings
-//====================================
-
-// imagine you want to implement an additional
-// method to strings, like
-//
-// "HAL".increment
-//
-// you can avoid ugly fudges, like a MyString
-// class by using implicit conversions
-
-
-implicit class MyString(s: String) {
- def increment = for (c <- s) yield (c + 1).toChar
-}
-
-"HAL".increment
-
-
// Further Information
//=====================
--- a/progs/lecture2.scala Fri Nov 11 11:17:40 2016 +0000
+++ b/progs/lecture2.scala Sat Nov 12 18:18:59 2016 +0000
@@ -1,2 +1,28 @@
// sudoku
// some none
+// pattern matching
+
+//type abbreviations
+type Pos = (int, Int)
+
+//sorting, higher-order functions
+//lexicographic ordering
+
+
+// Implicits
+//===========
+//
+// for example adding your own methods to Strings:
+// imagine you want to increment strings, like
+//
+// "HAL".increment
+//
+// you can avoid ugly fudges, like a MyString, by
+// using implicit conversions
+
+
+implicit class MyString(s: String) {
+ def increment = for (c <- s) yield (c + 1).toChar
+}
+
+"HAL".increment