# HG changeset patch # User Christian Urban # Date 1479907921 0 # Node ID 3506b681c191f7a8f73a36c5335012c5ecfd022f # Parent f59e70e2ad824c5bdd06a04b34efbd90f26d09f4 updated diff -r f59e70e2ad82 -r 3506b681c191 progs/knight2_sol.scala --- a/progs/knight2_sol.scala Tue Nov 22 01:35:40 2016 +0000 +++ b/progs/knight2_sol.scala Wed Nov 23 13:32:01 2016 +0000 @@ -43,11 +43,13 @@ first(legal_moves(dim, path, path.head), (x: Pos) => first_tour(dim, x::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) ; "" })) } +*/ +print_board(8, first_tour(8, List((0, 0))).get) - diff -r f59e70e2ad82 -r 3506b681c191 progs/knight3_sol.scala --- a/progs/knight3_sol.scala Tue Nov 22 01:35:40 2016 +0000 +++ b/progs/knight3_sol.scala Wed Nov 23 13:32:01 2016 +0000 @@ -31,7 +31,10 @@ def ordered_moves(dim: Int, path: Path, x: Pos): List[Pos] = legal_moves(dim, path, x).sortBy((x) => legal_moves(dim, path, x).length) +import scala.annotation.tailrec +/* +@tailrec def first(xs: List[Pos], f: Pos => Option[Path]): Option[Path] = xs match { case Nil => None case x::xs => { @@ -39,6 +42,10 @@ if (result.isDefined) result else first(xs, f) } } +*/ + +def first[A, B](xs: List[A], f: A => Option[B]): Option[B] = + xs.flatMap(f(_)).headOption def first_closed_tour_heuristics(dim: Int, path: Path): Option[Path] = { @@ -47,19 +54,46 @@ first(ordered_moves(dim, path, path.head), (x: Pos) => first_closed_tour_heuristics(dim, x::path)) } +/* for (dim <- 1 to 6) { val t = first_closed_tour_heuristics(dim, List((dim / 2, dim / 2))) println(s"${dim} x ${dim} closed: " + (if (t == None) "" else { print_board(dim, t.get) ; "" })) } +*/ + +//@tailrec +def first_tour_heuristics(dim: Int, path: Path): Option[Path] = { + + @tailrec + def aux(dim: Int, path: Path, moves: List[Position]): Option[Path + if (path.length == dim * dim) Some(path) + else + moves match { + case Nil => None + case x::xs => { + val r = first_tour_heuristics(dim, x::path) + if (r.isDefined) Some(r) else aux(dim, path, xs) + } + aux(dim, path, ordered_moves(dim, path, path.head)) +} +/* def first_tour_heuristics(dim: Int, path: Path): Option[Path] = { if (path.length == dim * dim) Some(path) else - first(ordered_moves(dim, path, path.head), (x: Pos) => first_tour_heuristics(dim, x::path)) + for (p <- ordered_moves(dim, path, path.head)) + val r = first_tour_heuristics(dim, x::path) + //first(ordered_moves(dim, path, path.head), (x: Pos) => first_tour_heuristics(dim, x::path)) + ordered_moves(dim, path, path.head).view.flatMap((x: Pos) => first_tour_heuristics(dim, x::path)).headOption } +*/ +/* for (dim <- 1 to 50) { val t = first_tour_heuristics(dim, List((dim / 2, dim / 2))) println(s"${dim} x ${dim}: " + (if (t == None) "" else { print_board(dim, t.get) ; "" })) } +*/ + +print_board(50, first_tour_heuristics(50, (25,25)::Nil).get) diff -r f59e70e2ad82 -r 3506b681c191 slides/slides02.tex --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/slides/slides02.tex Wed Nov 23 13:32:01 2016 +0000 @@ -0,0 +1,141 @@ +\documentclass[dvipsnames,14pt,t,xelatex]{beamer} +\usepackage{../slides} +\usepackage{../graphics} +\usepackage{../langs} +%\usepackage{../data} + +\hfuzz=220pt + +%\setmonofont[Scale=.88]{Consolas} +%\newfontfamily{\consolas}{Consolas} + +\lstset{language=Scala, + style=mystyle, + numbersep=0pt, + numbers=none, + xleftmargin=0mm} + +\newcommand{\bl}[1]{\textcolor{blue}{#1}} + +% beamer stuff +\renewcommand{\slidecaption}{PEP (Scala) 02, King's College London} + + +\begin{document} + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +\begin{frame}[t] +\frametitle{% + \begin{tabular}{@ {}c@ {}} + \\[5mm] + \huge PEP Scala (2) + \end{tabular}} + + \normalsize + \begin{center} + \begin{tabular}{ll} + Email: & christian.urban at kcl.ac.uk\\ + Office: & S1.27 (1st floor Strand Building)\\ + Slides \& Code: & KEATS + \end{tabular} + \end{center} + + +\end{frame} +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + +\begin{frame}[t] +\frametitle{\begin{tabular}{c}Why Scala?\end{tabular}} + + +\begin{itemize} +\item \large {\bf You can avoid \textcolor{blue}{\texttt{null}}}: +\end{itemize} + + +\begin{textblock}{6}(1,5) + \begin{bubble}[10.5cm]\small + ``I call it my billion-dollar mistake. It was the invention of + the null reference in 1965. At that time, I was designing the + first comprehensive type system for references in an object + oriented language (ALGOL W). My goal was to ensure that all use + of references should be absolutely safe, with checking performed + automatically by the compiler. But I couldn't resist the + temptation to put in a null reference, simply because it was so + easy to implement. This has led to innumerable errors, + vulnerabilities, and system crashes, which have probably caused + a billion dollars of pain and damage in the last forty years.'' + \hfill Sir Tony (Hoare) +\end{bubble} +\end{textblock} + +\begin{textblock}{5}(11.8,1) +\includegraphics[scale=0.20]{hoare.jpg}\\ +\end{textblock} + +\end{frame} + + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +\begin{frame}[c] +\frametitle{\huge\textbf{\texttt{return}}} + +\begin{center}\LARGE +you should never use it +\end{center} + +\end{frame} +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +\begin{frame}[c] +\frametitle{Types} + +\begin{itemize} +\item Base types\smallskip + + \begin{tabular}{@{}l@{}} + \textcolor{codegreen}{\texttt{Int}}, + \textcolor{codegreen}{\texttt{Long}}, + \textcolor{codegreen}{\texttt{BigInt}}, + \textcolor{codegreen}{\texttt{Float}}, + \textcolor{codegreen}{\texttt{Double}}\\ + \textcolor{codegreen}{\texttt{String}}, + \textcolor{codegreen}{\texttt{Char}}\\ + \textcolor{codegreen}{\texttt{Boolean}} + \end{tabular} + +\item Compound types \smallskip + + \begin{tabular}{@{}ll@{}} + \textcolor{codegreen}{\texttt{List[Int]}} & lists of Int's \\ + \textcolor{codegreen}{\texttt{Set[Double]}} & sets of Double's \\ + \textcolor{codegreen}{\texttt{(Int, String)}} & Int-String pair\\ + \textcolor{codegreen}{\texttt{List[(BigInt, String)]}} & + lists of BigInt-String\\ + & pairs\\ + \textcolor{codegreen}{\texttt{List[List[Int]]}} & list of lists of Int's\\ + \end{tabular} + +\end{itemize} + +\end{frame} +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +\begin{frame}[c] +\frametitle{\begin{tabular}{c}\\[3cm]\alert{Questions?}\end{tabular}} + +\mbox{} +\end{frame} +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +\end{document} + + +\end{document} + +%%% Local Variables: +%%% mode: latex +%%% TeX-master: t +%%% End: + diff -r f59e70e2ad82 -r 3506b681c191 slides/slides03.tex --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/slides/slides03.tex Wed Nov 23 13:32:01 2016 +0000 @@ -0,0 +1,141 @@ +\documentclass[dvipsnames,14pt,t,xelatex]{beamer} +\usepackage{../slides} +\usepackage{../graphics} +\usepackage{../langs} +%\usepackage{../data} + +\hfuzz=220pt + +%\setmonofont[Scale=.88]{Consolas} +%\newfontfamily{\consolas}{Consolas} + +\lstset{language=Scala, + style=mystyle, + numbersep=0pt, + numbers=none, + xleftmargin=0mm} + +\newcommand{\bl}[1]{\textcolor{blue}{#1}} + +% beamer stuff +\renewcommand{\slidecaption}{PEP (Scala) 02, King's College London} + + +\begin{document} + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +\begin{frame}[t] +\frametitle{% + \begin{tabular}{@ {}c@ {}} + \\[5mm] + \huge PEP Scala (2) + \end{tabular}} + + \normalsize + \begin{center} + \begin{tabular}{ll} + Email: & christian.urban at kcl.ac.uk\\ + Office: & S1.27 (1st floor Strand Building)\\ + Slides \& Code: & KEATS + \end{tabular} + \end{center} + + +\end{frame} +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + +\begin{frame}[t] +\frametitle{\begin{tabular}{c}Why Scala?\end{tabular}} + + +\begin{itemize} +\item \large {\bf You can avoid \textcolor{blue}{\texttt{null}}}: +\end{itemize} + + +\begin{textblock}{6}(1,5) + \begin{bubble}[10.5cm]\small + ``I call it my billion-dollar mistake. It was the invention of + the null reference in 1965. At that time, I was designing the + first comprehensive type system for references in an object + oriented language (ALGOL W). My goal was to ensure that all use + of references should be absolutely safe, with checking performed + automatically by the compiler. But I couldn't resist the + temptation to put in a null reference, simply because it was so + easy to implement. This has led to innumerable errors, + vulnerabilities, and system crashes, which have probably caused + a billion dollars of pain and damage in the last forty years.'' + \hfill Sir Tony (Hoare) +\end{bubble} +\end{textblock} + +\begin{textblock}{5}(11.8,1) +\includegraphics[scale=0.20]{hoare.jpg}\\ +\end{textblock} + +\end{frame} + + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +\begin{frame}[c] +\frametitle{\huge\textbf{\texttt{return}}} + +\begin{center}\LARGE +you should never use it +\end{center} + +\end{frame} +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +\begin{frame}[c] +\frametitle{Types} + +\begin{itemize} +\item Base types\smallskip + + \begin{tabular}{@{}l@{}} + \textcolor{codegreen}{\texttt{Int}}, + \textcolor{codegreen}{\texttt{Long}}, + \textcolor{codegreen}{\texttt{BigInt}}, + \textcolor{codegreen}{\texttt{Float}}, + \textcolor{codegreen}{\texttt{Double}}\\ + \textcolor{codegreen}{\texttt{String}}, + \textcolor{codegreen}{\texttt{Char}}\\ + \textcolor{codegreen}{\texttt{Boolean}} + \end{tabular} + +\item Compound types \smallskip + + \begin{tabular}{@{}ll@{}} + \textcolor{codegreen}{\texttt{List[Int]}} & lists of Int's \\ + \textcolor{codegreen}{\texttt{Set[Double]}} & sets of Double's \\ + \textcolor{codegreen}{\texttt{(Int, String)}} & Int-String pair\\ + \textcolor{codegreen}{\texttt{List[(BigInt, String)]}} & + lists of BigInt-String\\ + & pairs\\ + \textcolor{codegreen}{\texttt{List[List[Int]]}} & list of lists of Int's\\ + \end{tabular} + +\end{itemize} + +\end{frame} +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +\begin{frame}[c] +\frametitle{\begin{tabular}{c}\\[3cm]\alert{Questions?}\end{tabular}} + +\mbox{} +\end{frame} +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +\end{document} + + +\end{document} + +%%% Local Variables: +%%% mode: latex +%%% TeX-master: t +%%% End: +