# HG changeset patch # User Christian Urban # Date 1478974739 0 # Node ID 135f6a0830ace023f0167e362ef6c92f7e430881 # Parent c6fe374a5fcac2337773eba34c5568b2783ac367# Parent 9fea5f751be4d9a4edde7a0085e3ac9dcf906d89 updated diff -r 9fea5f751be4 -r 135f6a0830ac cws/cw02.pdf Binary file cws/cw02.pdf has changed diff -r 9fea5f751be4 -r 135f6a0830ac cws/cw02.tex --- 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} diff -r 9fea5f751be4 -r 135f6a0830ac progs/collatz.scala diff -r 9fea5f751be4 -r 135f6a0830ac progs/drumb.scala --- 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 diff -r 9fea5f751be4 -r 135f6a0830ac progs/drumb_sol.scala --- 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 diff -r 9fea5f751be4 -r 135f6a0830ac progs/knight2.scala --- 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 diff -r 9fea5f751be4 -r 135f6a0830ac progs/lecture1.scala --- 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 //===================== diff -r 9fea5f751be4 -r 135f6a0830ac progs/lecture2.scala --- 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