Binary file cws/cw01.pdf has changed
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/cws/cw01.tex Thu Nov 03 00:53:53 2016 +0000
@@ -0,0 +1,217 @@
+\documentclass{article}
+\usepackage{style}
+%%\usepackage{../langs}
+
+\begin{document}
+
+\section*{Coursework 1 (Strand 1)}
+
+This coursework is worth 4\% and is due on 25 October at
+16:00. You are asked to implement a regular expression matcher
+and submit a document containing the answers for the questions
+below. You can do the implementation in any programming
+language you like, but you need to submit the source code with
+which you answered the questions, otherwise a mark of 0\% will
+be awarded. You can submit your answers in a txt-file or pdf.
+Code send as code.
+
+
+
+\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}
+
+The task is to implement a regular expression matcher based on
+derivatives of regular expressions. The implementation should
+be able to deal with the usual (basic) regular expressions
+
+\[
+\ZERO,\; \ONE,\; c,\; r_1 + r_2,\; r_1 \cdot r_2,\; r^*
+\]
+
+\noindent
+but also with the following extended regular expressions:
+
+\begin{center}
+\begin{tabular}{ll}
+$[c_1 c_2 \ldots c_n]$ & a range of characters\\
+$r^+$ & one or more times $r$\\
+$r^?$ & optional $r$\\
+$r^{\{n,m\}}$ & at least $n$-times $r$ but no more than $m$-times\\
+$\sim{}r$ & not-regular expression of $r$\\
+\end{tabular}
+\end{center}
+
+\noindent In the case of $r^{\{n,m\}}$ you can assume the
+convention that $0 \le n \le m$. The meanings of the extended
+regular expressions are
+
+\begin{center}
+\begin{tabular}{r@{\hspace{2mm}}c@{\hspace{2mm}}l}
+$L([c_1 c_2 \ldots c_n])$ & $\dn$ & $\{[c_1], [c_2], \ldots, [c_n]\}$\\
+$L(r^+)$ & $\dn$ & $\bigcup_{1\le i}. L(r)^i$\\
+$L(r^?)$ & $\dn$ & $L(r) \cup \{[]\}$\\
+$L(r^{\{n,m\}})$ & $\dn$ & $\bigcup_{n\le i \le m}. L(r)^i$\\
+$L(\sim{}r)$ & $\dn$ & $\Sigma^* - L(r)$
+\end{tabular}
+\end{center}
+
+\noindent whereby in the last clause the set $\Sigma^*$ stands
+for the set of \emph{all} strings over the alphabet $\Sigma$
+(in the implementation the alphabet can be just what is
+represented by, say, the type \texttt{Char}). So $\sim{}r$
+means `all the strings that $r$ cannot match'.
+
+Be careful that your implementation of \textit{nullable} and
+\textit{der} satisfies for every $r$ the following two
+properties (see also Question 2):
+
+\begin{itemize}
+\item $\textit{nullable}(r)$ if and only if $[]\in L(r)$
+\item $L(der\,c\,r) = Der\,c\,(L(r))$
+\end{itemize}
+
+\noindent {\bf Important!} Your implementation should have
+explicit cases for the basic regular expressions, but also
+explicit cases for the extended regular expressions. That
+means do not treat the extended regular expressions by just
+translating them into the basic ones. See also Question 2,
+where you are asked to explicitly give the rules for
+\textit{nullable} and \textit{der} for the extended regular
+expressions.
+
+
+\subsection*{Question 1}
+
+What is your King's email address (you will need it in
+Question 3)?
+
+\subsection*{Question 2}
+
+This question does not require any implementation. From the
+lectures you have seen the definitions for the functions
+\textit{nullable} and \textit{der} for the basic regular
+expressions. Give the rules for the extended regular
+expressions:
+
+\begin{center}
+\begin{tabular}{@ {}l@ {\hspace{2mm}}c@ {\hspace{2mm}}l@ {}}
+$\textit{nullable}([c_1 c_2 \ldots c_n])$ & $\dn$ & $?$\\
+$\textit{nullable}(r^+)$ & $\dn$ & $?$\\
+$\textit{nullable}(r^?)$ & $\dn$ & $?$\\
+$\textit{nullable}(r^{\{n,m\}})$ & $\dn$ & $?$\\
+$\textit{nullable}(\sim{}r)$ & $\dn$ & $?$\medskip\\
+$der\, c\, ([c_1 c_2 \ldots c_n])$ & $\dn$ & $?$\\
+$der\, c\, (r^+)$ & $\dn$ & $?$\\
+$der\, c\, (r^?)$ & $\dn$ & $?$\\
+$der\, c\, (r^{\{n,m\}})$ & $\dn$ & $?$\\
+$der\, c\, (\sim{}r)$ & $\dn$ & $?$\\
+\end{tabular}
+\end{center}
+
+\noindent
+Remember your definitions have to satisfy the two properties
+
+\begin{itemize}
+\item $\textit{nullable}(r)$ if and only if $[]\in L(r)$
+\item $L(der\,c\,r)) = Der\,c\,(L(r))$
+\end{itemize}
+
+\subsection*{Question 3}
+
+Implement the following regular expression for email addresses
+
+\[
+([a\mbox{-}z0\mbox{-}9\_\!\_\,.-]^+)\cdot @\cdot ([a\mbox{-}z0\mbox{-}9\,.-]^+)\cdot .\cdot ([a\mbox{-}z\,.]^{\{2,6\}})
+\]
+
+\noindent and calculate the derivative according to your email
+address. When calculating the derivative, simplify all regular
+expressions as much as possible by applying the
+following 7 simplification rules:
+
+\begin{center}
+\begin{tabular}{l@{\hspace{2mm}}c@{\hspace{2mm}}ll}
+$r \cdot \ZERO$ & $\mapsto$ & $\ZERO$\\
+$\ZERO \cdot r$ & $\mapsto$ & $\ZERO$\\
+$r \cdot \ONE$ & $\mapsto$ & $r$\\
+$\ONE \cdot r$ & $\mapsto$ & $r$\\
+$r + \ZERO$ & $\mapsto$ & $r$\\
+$\ZERO + r$ & $\mapsto$ & $r$\\
+$r + r$ & $\mapsto$ & $r$\\
+\end{tabular}
+\end{center}
+
+\noindent Write down your simplified derivative in a readable
+notation using parentheses where necessary. That means you
+should use the infix notation $+$, $\cdot$, $^*$ and so on,
+instead of code.
+
+\subsection*{Question 4}
+
+Suppose \textit{[a-z]} stands for the range regular expression
+$[a,b,c,\ldots,z]$. Consider the regular expression $/ \cdot * \cdot
+(\sim{}([a\mbox{-}z]^* \cdot * \cdot / \cdot [a\mbox{-}z]^*)) \cdot *
+\cdot /$ and decide wether the following four strings are matched by
+this regular expression. Answer yes or no.
+
+\begin{enumerate}
+\item \texttt{"/**/"}
+\item \texttt{"/*foobar*/"}
+\item \texttt{"/*test*/test*/"}
+\item \texttt{"/*test/*test*/"}
+\end{enumerate}
+
+\noindent
+Also test your regular expression matcher with the regular
+expression $a^{\{3,5\}}$ and the strings
+
+\begin{enumerate}
+\setcounter{enumi}{4}
+\item \texttt{aa}
+\item \texttt{aaa}
+\item \texttt{aaaaa}
+\item \texttt{aaaaaa}
+\end{enumerate}
+
+\noindent
+Does your matcher produce the expected results?
+
+\subsection*{Question 5}
+
+Let $r_1$ be the regular expression $a\cdot a\cdot a$ and $r_2$ be
+$(a^{\{19,19\}}) \cdot (a^?)$. Decide whether the following three
+strings consisting of $a$s only can be matched by $(r_1^+)^+$.
+Similarly test them with $(r_2^+)^+$. Again answer in all six cases
+with yes or no. \medskip
+
+\noindent
+These are strings are meant to be entirely made up of $a$s. Be careful
+when copy-and-pasting the strings so as to not forgetting any $a$ and
+to not introducing any other character.
+
+\begin{enumerate}
+\item \texttt{"aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa\\
+aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa\\
+aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"}
+\item \texttt{"aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa\\
+aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa\\
+aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"}
+\item \texttt{"aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa\\
+aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa\\
+aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"}
+\end{enumerate}
+
+
+\end{document}
+
+%%% Local Variables:
+%%% mode: latex
+%%% TeX-master: t
+%%% End:
Binary file cws/cw02.pdf has changed
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/cws/cw02.tex Thu Nov 03 00:53:53 2016 +0000
@@ -0,0 +1,111 @@
+\documentclass{article}
+\usepackage{../style}
+\usepackage{chessboard}
+\usepackage[LSBC4,T1]{fontenc}
+
+
+\begin{document}
+
+\setchessboard{smallboard,
+ showmover=false,
+ boardfontencoding=LSBC4,
+ hlabelformat=\arabic{ranklabel},
+ vlabelformat=\arabic{filelabel}}
+
+
+
+\section*{Coursework 2 (Knight's Tour)}
+
+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:
+
+\chessboard[maxfield=e5,
+ pgfstyle= {[base,at={\pgfpoint{0pt}{-0.5ex}}]text},
+ text = \bf\small 24, markfield=a5,
+ text = \small 11, markfield=b5,
+ text = \small 6, markfield=c5,
+ text = \small 17, markfield=d5,
+ text = \small 0, markfield=e5,
+ text = \small 19, markfield=a4,
+ text = \small 16, markfield=b4,
+ text = \small 23, markfield=c4,
+ text = \small 12, markfield=d4,
+ text = \small 7, markfield=e4,
+ text = \small 10, markfield=a3,
+ text = \small 5, markfield=b3,
+ text = \small 18, markfield=c3,
+ text = \small 1, markfield=d3,
+ text = \small 22, markfield=e3,
+ text = \small 15, markfield=a2,
+ text = \small 20, markfield=b2,
+ text = \small 3, markfield=c2,
+ text = \small 8, markfield=d2,
+ text = \small 13, markfield=e2,
+ text = \small 4, markfield=a1,
+ text = \small 9, markfield=b1,
+ text = \small 14, markfield=c1,
+ text = \small 21, markfield=d1,
+ text = \small 2, markfield=e1
+ ]
+
+\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 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
+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.
+
+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)$:
+
+
+\chessboard[color=blue!50,
+ linewidth=0.2em,
+ shortenstart=0.5ex,
+ shortenend=0.5ex,
+ markstyle=cross,
+ markfields={b5, d5, a4, e4, a2, e2, b1, d1},
+ color=red!50,
+ markfields={g6, f7},
+ 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}
+
+The task is to implement a regular expression matcher based on
+derivatives of regular expressions. The implementation should
+be able to deal with the usual (basic) regular expressions
+
+\noindent {\bf Important!} Your implementation should have
+explicit cases for the basic regular expressions, but also
+explicit cases for the extended regular expressions. That
+means do not treat the extended regular expressions by just
+translating them into the basic ones. See also Question 2,
+where you are asked to explicitly give the rules for
+\textit{nullable} and \textit{der} for the extended regular
+expressions.
+
+
+
+\end{document}
+
+%%% Local Variables:
+%%% mode: latex
+%%% TeX-master: t
+%%% End:
Binary file cws/cw03.pdf has changed
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/cws/cw03.tex Thu Nov 03 00:53:53 2016 +0000
@@ -0,0 +1,226 @@
+\documentclass{article}
+\usepackage{style}
+%%\usepackage{../langs}
+
+\begin{document}
+
+\section*{Coursework 3}
+
+This coursework is worth XXX\% and is due on XXXX at
+16:00. You are asked to implement a regular expression matcher.
+
+
+
+
+\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}
+
+The task is to implement a regular expression matcher based on
+derivatives of regular expressions. The implementation should
+be able to deal with the usual (basic) regular expressions
+
+\begin{center}
+\begin{tabular}{lcll}
+ $r$ & $::=$ & $\ZERO$ & cannot match anything\\
+ & $|$ & $\ONE$ & can only match the empty string\\
+ & $|$ & $c$ & can match a character $c$\\
+ & $|$ & $r_1 + r_2$ & can match either with $r_1$ or with $r_2$\\
+ & $|$ & $r_1 \cdot r_2$ & can match first with $r_1$ and then with $r_2$\\
+ & $|$ & $r^*$ & can match zero or more times $r$\\
+ & $|$ & $r^{\{\uparrow n\}}$ & can match zero upto $n$ times $r$\\
+ & $|$ & $r^{\{n\}}$ & can match exactly $n$ times $r$\\
+\end{tabular}
+\end{center}
+
+\noindent
+Implement a function called \textit{nullable} by recursion over
+regular expressions:
+
+\begin{center}
+\begin{tabular}{lcl}
+$\textit{nullable}(\ZERO)$ & $\dn$ & $\textit{false}$\\
+$\textit{nullable}(\ONE)$ & $\dn$ & $\textit{true}$\\
+$\textit{nullable}(c)$ & $\dn$ & $\textit{false}$\\
+$\textit{nullable}(r_1 + r_2)$ & $\dn$ & $\textit{nullable}(r_1) \vee \textit{nullable}(r_2)$\\
+$\textit{nullable}(r_1 \cdot r_2)$ & $\dn$ & $\textit{nullable}(r_1) \wedge \textit{nullable}(r_2)$\\
+$\textit{nullable}(r^*)$ & $\dn$ & $\textit{true}$\\
+$\textit{nullable}(r^{\{\uparrow n\}})$ & $\dn$ & $\textit{true}$\\
+$\textit{nullable}(r^{\{n\}})$ & $\dn$ &
+ $\textit{if}\;n = 0\; \textit{then} \; \textit{true} \; \textit{else} \; \textit{nullable}(r)$\\
+\end{tabular}
+\end{center}
+
+\begin{center}
+\begin{tabular}{lcl}
+$\textit{der}\;c\;(\ZERO)$ & $\dn$ & $\ZERO$\\
+$\textit{der}\;c\;(\ONE)$ & $\dn$ & $\ZERO$\\
+$\textit{der}\;c\;(d)$ & $\dn$ & $\textit{if}\; c = d\;\textit{then} \;\ONE \; \textit{else} \;\ZERO$\\
+$\textit{der}\;c\;(r_1 + r_2)$ & $\dn$ & $(\textit{der}\;c\;r_1) + (\textit{der}\;c\;r_2)$\\
+$\textit{der}\;c\;(r_1 \cdot r_2)$ & $\dn$ & $\textit{if}\;\textit{nullable}(r_1)$\\
+ & & $\textit{then}\;((\textit{der}\;c\;r_1)\cdot r_2) + (\textit{der}\;c\;r_2)$\\
+ & & $\textit{else}\;(\textit{der}\;c\;r_1)\cdot r_2$\\
+$\textit{der}\;c\;(r^*)$ & $\dn$ & $(\textit{der}\;c\;r)\cdot (r^*)$\\
+$\textit{der}\;c\;(r^{\{\uparrow n\}})$ & $\dn$ & $\textit{if}\;n = 0\;\textit{then}\;\ZERO\;\text{else}\;
+ (\textit{der}\;c\;r)\cdot (r^{\{\uparrow n-1\}})$\\
+$\textit{der}\;c\;(r^{\{n\}})$ & $\dn$ &
+ $\textit{if}\;n = 0\; \textit{then} \; \ZERO\; \textit{else}\;$\\
+ & & $\textit{if} \;\textit{nullable}(r)\;\textit{then}\;(\textit{der}\;c\;r)\cdot (r^{\{\uparrow n-1\}})$\\
+ & & $\textit{else}\;(\textit{der}\;c\;r)\cdot (r^{\{n-1\}})$
+\end{tabular}
+\end{center}
+
+
+Be careful that your implementation of \textit{nullable} and
+\textit{der}\;c\; satisfies for every $r$ the following two
+properties (see also Question 2):
+
+\begin{itemize}
+\item $\textit{nullable}(r)$ if and only if $[]\in L(r)$
+\item $L(der\,c\,r) = Der\,c\,(L(r))$
+\end{itemize}
+
+\noindent {\bf Important!} Your implementation should have
+explicit cases for the basic regular expressions, but also
+explicit cases for the extended regular expressions. That
+means do not treat the extended regular expressions by just
+translating them into the basic ones. See also Question 2,
+where you are asked to explicitly give the rules for
+\textit{nullable} and \textit{der}\;c\; for the extended regular
+expressions.
+
+
+\subsection*{Question 1}
+
+What is your King's email address (you will need it in
+Question 3)?
+
+\subsection*{Question 2}
+
+This question does not require any implementation. From the
+lectures you have seen the definitions for the functions
+\textit{nullable} and \textit{der}\;c\; for the basic regular
+expressions. Give the rules for the extended regular
+expressions:
+
+\begin{center}
+\begin{tabular}{@ {}l@ {\hspace{2mm}}c@ {\hspace{2mm}}l@ {}}
+$\textit{nullable}([c_1 c_2 \ldots c_n])$ & $\dn$ & $?$\\
+$\textit{nullable}(r^+)$ & $\dn$ & $?$\\
+$\textit{nullable}(r^?)$ & $\dn$ & $?$\\
+$\textit{nullable}(r^{\{n,m\}})$ & $\dn$ & $?$\\
+$\textit{nullable}(\sim{}r)$ & $\dn$ & $?$\medskip\\
+$der\, c\, ([c_1 c_2 \ldots c_n])$ & $\dn$ & $?$\\
+$der\, c\, (r^+)$ & $\dn$ & $?$\\
+$der\, c\, (r^?)$ & $\dn$ & $?$\\
+$der\, c\, (r^{\{n,m\}})$ & $\dn$ & $?$\\
+$der\, c\, (\sim{}r)$ & $\dn$ & $?$\\
+\end{tabular}
+\end{center}
+
+\noindent
+Remember your definitions have to satisfy the two properties
+
+\begin{itemize}
+\item $\textit{nullable}(r)$ if and only if $[]\in L(r)$
+\item $L(der\,c\,r)) = Der\,c\,(L(r))$
+\end{itemize}
+
+\subsection*{Question 3}
+
+Implement the following regular expression for email addresses
+
+\[
+([a\mbox{-}z0\mbox{-}9\_\!\_\,.-]^+)\cdot @\cdot ([a\mbox{-}z0\mbox{-}9\,.-]^+)\cdot .\cdot ([a\mbox{-}z\,.]^{\{2,6\}})
+\]
+
+\noindent and calculate the derivative according to your email
+address. When calculating the derivative, simplify all regular
+expressions as much as possible by applying the
+following 7 simplification rules:
+
+\begin{center}
+\begin{tabular}{l@{\hspace{2mm}}c@{\hspace{2mm}}ll}
+$r \cdot \ZERO$ & $\mapsto$ & $\ZERO$\\
+$\ZERO \cdot r$ & $\mapsto$ & $\ZERO$\\
+$r \cdot \ONE$ & $\mapsto$ & $r$\\
+$\ONE \cdot r$ & $\mapsto$ & $r$\\
+$r + \ZERO$ & $\mapsto$ & $r$\\
+$\ZERO + r$ & $\mapsto$ & $r$\\
+$r + r$ & $\mapsto$ & $r$\\
+\end{tabular}
+\end{center}
+
+\noindent Write down your simplified derivative in a readable
+notation using parentheses where necessary. That means you
+should use the infix notation $+$, $\cdot$, $^*$ and so on,
+instead of code.
+
+\subsection*{Question 4}
+
+Suppose \textit{[a-z]} stands for the range regular expression
+$[a,b,c,\ldots,z]$. Consider the regular expression $/ \cdot * \cdot
+(\sim{}([a\mbox{-}z]^* \cdot * \cdot / \cdot [a\mbox{-}z]^*)) \cdot *
+\cdot /$ and decide wether the following four strings are matched by
+this regular expression. Answer yes or no.
+
+\begin{enumerate}
+\item \texttt{"/**/"}
+\item \texttt{"/*foobar*/"}
+\item \texttt{"/*test*/test*/"}
+\item \texttt{"/*test/*test*/"}
+\end{enumerate}
+
+\noindent
+Also test your regular expression matcher with the regular
+expression $a^{\{3,5\}}$ and the strings
+
+\begin{enumerate}
+\setcounter{enumi}{4}
+\item \texttt{aa}
+\item \texttt{aaa}
+\item \texttt{aaaaa}
+\item \texttt{aaaaaa}
+\end{enumerate}
+
+\noindent
+Does your matcher produce the expected results?
+
+\subsection*{Question 5}
+
+Let $r_1$ be the regular expression $a\cdot a\cdot a$ and $r_2$ be
+$(a^{\{19,19\}}) \cdot (a^?)$. Decide whether the following three
+strings consisting of $a$s only can be matched by $(r_1^+)^+$.
+Similarly test them with $(r_2^+)^+$. Again answer in all six cases
+with yes or no. \medskip
+
+\noindent
+These are strings are meant to be entirely made up of $a$s. Be careful
+when copy-and-pasting the strings so as to not forgetting any $a$ and
+to not introducing any other character.
+
+\begin{enumerate}
+\item \texttt{"aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa\\
+aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa\\
+aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"}
+\item \texttt{"aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa\\
+aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa\\
+aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"}
+\item \texttt{"aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa\\
+aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa\\
+aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"}
+\end{enumerate}
+
+
+\end{document}
+
+%%% Local Variables:
+%%% mode: latex
+%%% TeX-master: t
+%%% End:
--- a/progs/knight2.scala Wed Nov 02 13:26:26 2016 +0000
+++ b/progs/knight2.scala Thu Nov 03 00:53:53 2016 +0000
@@ -24,22 +24,15 @@
(-1, -2),(-2, -1),(-2, 1),(-1, 2)).map(add_pair(x)).filter(is_legal(n))
}
-def ordered_moves(n: Int)(steps: List[Pos])(x : Pos): List[Pos] =
- moves(n)(x).sortBy((x: Pos) => moves(n)(x).filterNot(steps.contains(_)).length)
-
-moves(8)(1,3)
-ordered_moves(8)(Nil)(1,3)
-ordered_moves(8)(List((2, 4), (2, 6)))(1,3)
-
-// non-circle tour
-def tour(n: Int)(steps: List[Pos]): Unit = {
- if (steps.length == n * n)
- print_board(n)(steps)
+// non-circle tours
+def tour(n: Int)(steps: List[Pos]): List[List[Pos]] = {
+ if (steps.length == n * n) List(steps)
else
- for (x <- moves(n)(steps.head); if (!steps.contains(x))) tour(n)(x :: steps)
+ (for (x <- moves(n)(steps.head); if (!steps.contains(x))) yield tour(n)(x :: steps)).flatten
}
-val n = 8
-println(s"simple tour: n = $n")
+//val n = 8
+val n = 6
+println(s"number simple tours: n = $n")
-for (i <- 0 until n; j <- 0 until n) tour(n)(List((i, j)))
+println((for (i <- 0 until n; j <- 0 until n) yield tour(n)(List((i, j)))).flatten.distinct.size)