# HG changeset patch # User Christian Urban # Date 1543549467 0 # Node ID e52cc402caee08416d449609ac188663626e6d6b # Parent 9e7897f25e13fcda1d2e00ffdd09cfde6d6258af updated diff -r 9e7897f25e13 -r e52cc402caee cws/cw04.tex --- a/cws/cw04.tex Thu Nov 29 17:15:11 2018 +0000 +++ b/cws/cw04.tex Fri Nov 30 03:44:27 2018 +0000 @@ -451,7 +451,8 @@ width=6cm, height=5.5cm, legend entries={Python, Java 8, JavaScript}, - legend pos=north west] + legend pos=north west, + legend cell align=left] \addplot[blue,mark=*, mark options={fill=white}] table {re-python2.data}; \addplot[cyan,mark=*, mark options={fill=white}] table {re-java.data}; \addplot[red,mark=*, mark options={fill=white}] table {re-js.data}; diff -r 9e7897f25e13 -r e52cc402caee pics/sahara.jpg Binary file pics/sahara.jpg has changed diff -r 9e7897f25e13 -r e52cc402caee progs/lecture4.scala --- a/progs/lecture4.scala Thu Nov 29 17:15:11 2018 +0000 +++ b/progs/lecture4.scala Fri Nov 30 03:44:27 2018 +0000 @@ -1,3 +1,54 @@ +// Scala Lecture 4 +//================= + + +// Polymorphic Types +//=================== + +// You do not want to write functions like contains, first, +// length and so on for every type of lists. + + +def length_string_list(lst: List[String]): Int = lst match { + case Nil => 0 + case x::xs => 1 + length_string_list(xs) +} + +def length_int_list(lst: List[Int]): Int = lst match { + case Nil => 0 + case x::xs => 1 + length_int_list(xs) +} + +length_string_list(List("1", "2", "3", "4")) +length_int_list(List(1, 2, 3, 4)) + +//----- +def length[A](lst: List[A]): Int = lst match { + case Nil => 0 + case x::xs => 1 + length(xs) +} +length(List("1", "2", "3", "4")) +length(List(1, 2, 3, 4)) + + +def map[A, B](lst: List[A], f: A => B): List[B] = lst match { + case Nil => Nil + case x::xs => f(x)::map(xs, f) +} + +map(List(1, 2, 3, 4), (x: Int) => x * x) + + +// Remember? +def first[A, B](xs: List[A], f: A => Option[B]) : Option[B] = ... + + +// distinct / distinctBy + +val ls = List(1,2,3,3,2,4,3,2,1) +ls.distinct + + def distinctBy[B, C](xs: List[B], f: B => C, acc: List[C] = Nil): List[B] = xs match { case Nil => Nil case (x::xs) => { @@ -7,5 +58,383 @@ } } +distinctBy(ls, (x: Int) => x) + + +val cs = List('A', 'b', 'a', 'c', 'B', 'D', 'd') + +distinctBy(cs, (c:Char) => c.toUpper) + + + +// Type inference is local in Scala + +def id[T](x: T) : T = x + + +val x = id(322) // Int +val y = id("hey") // String +val z = id(Set(1,2,3,4)) // Set[Int] + + + +// The type variable concept in Scala can get really complicated. +// +// - variance (OO) +// - bounds (subtyping) +// - quantification + +// Java has issues with this too: Java allows +// to write the following, but raises an exception +// at runtime + +//Object[] arr = new Integer[10]; +//arr[0] = "Hello World"; + + +// Scala gives you a compile-time error + +var arr = Array[Int]() +arr(0) = "Hello World" + + + + + + +// +// Object Oriented Programming in Scala +// +// ===================================== + +abstract class Animal +case class Bird(name: String) extends Animal +case class Mammal(name: String) extends Animal +case class Reptile(name: String) extends Animal + +println(new Bird("Sparrow")) +println(Bird("Sparrow").toString) + + +// you can override methods +case class Bird(name: String) extends Animal { + override def toString = name +} + + +// There is a very convenient short-hand notation +// for constructors + +class Fraction(x: Int, y: Int) { + def numer = x + def denom = y +} + + +case class Fraction(numer: Int, denom: Int) + +val half = Fraction(1, 2) + +half.denom + + +// in mandelbrot.scala I used complex (imaginary) numbers and implemented +// the usual arithmetic operations for complex numbers + +case class Complex(re: Double, im: Double) { + // represents the complex number re + im * i + def +(that: Complex) = Complex(this.re + that.re, this.im + that.im) + def -(that: Complex) = Complex(this.re - that.re, this.im - that.im) + def *(that: Complex) = Complex(this.re * that.re - this.im * that.im, + this.re * that.im + that.re * this.im) + def *(that: Double) = Complex(this.re * that, this.im * that) + def abs = Math.sqrt(this.re * this.re + this.im * this.im) +} + +val test = Complex(1, 2) + Complex (3, 4) + +// this could have equally been written as +val test = Complex(1, 2).+(Complex (3, 4)) + +// this applies to all methods, but requires +import scala.language.postfixOps + +List(5, 2, 3, 4).sorted +List(5, 2, 3, 4) sorted + + +// to allow the notation n + m * i +import scala.language.implicitConversions +object i extends Complex(0, 1) +implicit def double2complex(re: Double) = Complex(re, 0) + + +val inum1 = -2.0 + -1.5 * i +val inum2 = 1.0 + 1.5 * i + + + +// all is public by default....so no public +// you can have the usual restrictions about private values +// and methods, if you are MUTABLE(!!!) + +case class BankAccount(init: Int) { + + private var balance = init + + def deposit(amount: Int): Unit = { + if (amount > 0) balance = balance + amount + } + + def withdraw(amount: Int): Int = + if (0 < amount && amount <= balance) { + balance = balance - amount + balance + } else throw new Error("insufficient funds") +} + +// BUT since we are IMMUTABLE, this is virtually of not +// concern to us. + + + + + +// DFAs in Scala +import scala.util.Try +// A is the state type +// C is the input (usually characters) + +case class DFA[A, C](start: A, // starting state + delta: (A, C) => A, // transition function + fins: A => Boolean) { // final states + + def deltas(q: A, s: List[C]) : A = s match { + case Nil => q + case c::cs => deltas(delta(q, c), cs) + } + + def accepts(s: List[C]) : Boolean = + Try(fins(deltas(start, s))) getOrElse false +} + +// the example shown in the handout +abstract class State +case object Q0 extends State +case object Q1 extends State +case object Q2 extends State +case object Q3 extends State +case object Q4 extends State + +val delta : (State, Char) => State = + { case (Q0, 'a') => Q1 + case (Q0, 'b') => Q2 + case (Q1, 'a') => Q4 + case (Q1, 'b') => Q2 + case (Q2, 'a') => Q3 + case (Q2, 'b') => Q2 + case (Q3, 'a') => Q4 + case (Q3, 'b') => Q0 + case (Q4, 'a') => Q4 + case (Q4, 'b') => Q4 + case _ => throw new Exception("Undefined") } + +val dfa = DFA(Q0, delta, Set[State](Q4)) + +dfa.accepts("abaaa".toList) // true +dfa.accepts("bbabaab".toList) // true +dfa.accepts("baba".toList) // false +dfa.accepts("abc".toList) // false + +// another DFA test with a Sink state +abstract class S +case object S0 extends S +case object S1 extends S +case object S2 extends S +case object Sink extends S + +// transition function with a sink state +val sigma : (S, Char) :=> S = + { case (S0, 'a') => S1 + case (S1, 'a') => S2 + case _ => Sink + } + +val dfa2 = DFA(S0, sigma, Set[S](S2)) + +dfa2.accepts("aa".toList) // true +dfa2.accepts("".toList) // false +dfa2.accepts("ab".toList) // false + + + + +// NFAs (Nondeterministic Finite Automata) + + +case class NFA[A, C](starts: Set[A], // starting states + delta: (A, C) => Set[A], // transition function + fins: A => Boolean) { // final states + + // given a state and a character, what is the set of + // next states? if there is none => empty set + def next(q: A, c: C) : Set[A] = + Try(delta(q, c)) getOrElse Set[A]() + + def nexts(qs: Set[A], c: C) : Set[A] = + qs.flatMap(next(_, c)) + + // depth-first version of accepts + def search(q: A, s: List[C]) : Boolean = s match { + case Nil => fins(q) + case c::cs => next(q, c).exists(search(_, cs)) + } + + def accepts(s: List[C]) : Boolean = + starts.exists(search(_, s)) +} + + + +// NFA examples + +val nfa_trans1 : (State, Char) => Set[State] = + { case (Q0, 'a') => Set(Q0, Q1) + case (Q0, 'b') => Set(Q2) + case (Q1, 'a') => Set(Q1) + case (Q2, 'b') => Set(Q2) } + +val nfa = NFA(Set[State](Q0), nfa_trans1, Set[State](Q2)) + +nfa.accepts("aa".toList) // false +nfa.accepts("aaaaa".toList) // false +nfa.accepts("aaaaab".toList) // true +nfa.accepts("aaaaabbb".toList) // true +nfa.accepts("aaaaabbbaaa".toList) // false +nfa.accepts("ac".toList) // false + + +// Q: Why the kerfuffle about the polymorphic types in DFAs/NFAs +// A: Subset construction + +def subset[A, C](nfa: NFA[A, C]) : DFA[Set[A], C] = { + DFA(nfa.starts, + { case (qs, c) => nfa.nexts(qs, c) }, + _.exists(nfa.fins)) +} + +subset(nfa1).accepts("aa".toList) // false +subset(nfa1).accepts("aaaaa".toList) // false +subset(nfa1).accepts("aaaaab".toList) // true +subset(nfa1).accepts("aaaaabbb".toList) // true +subset(nfa1).accepts("aaaaabbbaaa".toList) // false +subset(nfa1).accepts("ac".toList) // false + + + + + + + +// Cool Stuff in Scala +//===================== + + +// Implicits or How to Pimp my Library +//===================================== +// +// 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 + + + + +// Regular expressions - the power of DSLs in Scala +//================================================== + +abstract class Rexp +case object ZERO extends Rexp // nothing +case object ONE extends Rexp // the empty string +case class CHAR(c: Char) extends Rexp // a character c +case class ALT(r1: Rexp, r2: Rexp) extends Rexp // alternative r1 + r2 +case class SEQ(r1: Rexp, r2: Rexp) extends Rexp // sequence r1 . r2 +case class STAR(r: Rexp) extends Rexp // star r* + + + +// (ab)* +val r0 = STAR(SEQ(CHAR('a'), CHAR('b'))) + + +// some convenience for typing in regular expressions +import scala.language.implicitConversions +import scala.language.reflectiveCalls + +def charlist2rexp(s: List[Char]): Rexp = s match { + case Nil => ONE + case c::Nil => CHAR(c) + case c::s => SEQ(CHAR(c), charlist2rexp(s)) +} +implicit def string2rexp(s: String): Rexp = charlist2rexp(s.toList) + + +val r1 = STAR("ab") +val r2 = STAR(ALT("ab", "baa baa black sheep")) +val r3 = STAR(SEQ("ab", ALT("a", "b"))) + +implicit def RexpOps (r: Rexp) = new { + def | (s: Rexp) = ALT(r, s) + def % = STAR(r) + def ~ (s: Rexp) = SEQ(r, s) +} + +implicit def stringOps (s: String) = new { + def | (r: Rexp) = ALT(s, r) + def | (r: String) = ALT(s, r) + def % = STAR(s) + def ~ (r: Rexp) = SEQ(s, r) + def ~ (r: String) = SEQ(s, r) +} + +//example regular expressions +val digit = "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9" +val sign = "+" | "-" | "" +val number = sign ~ digit ~ digit.% + + + +// Lazy Evaluation +//================= +// +// do not evaluate arguments just yet + +def time_needed[T](i: Int, code: => T) = { + val start = System.nanoTime() + for (j <- 1 to i) code + val end = System.nanoTime() + (end - start)/(i * 1.0e9) +} + +// same examples using the internal regexes +val evil = "(a*)*b" + +("a" * 10 ++ "b").matches(evil) +("a" * 10).matches(evil) +("a" * 10000).matches(evil) +("a" * 20000).matches(evil) + +time_needed(2, ("a" * 10000).matches(evil)) diff -r 9e7897f25e13 -r e52cc402caee slides/slides04.tex --- a/slides/slides04.tex Thu Nov 29 17:15:11 2018 +0000 +++ b/slides/slides04.tex Fri Nov 30 03:44:27 2018 +0000 @@ -4,6 +4,7 @@ \usepackage{../langs} %%\usepackage{../data} \usepackage[export]{adjustbox} +\usetikzlibrary{shapes} \hfuzz=220pt @@ -16,10 +17,26 @@ numbers=none, xleftmargin=0mm} +\newcommand{\LEFTarrow}[3]{% +\begin{textblock}{0}(#2,#3)% +\onslide<#1>{% +\begin{tikzpicture}% +\node at (0,0) [single arrow, shape border rotate=180, fill=red,text=red]{a};% +\end{tikzpicture}}% +\end{textblock}} +\newcommand{\DOWNarrow}[3]{% +\begin{textblock}{0}(#2,#3)% +\onslide<#1>{% +\begin{tikzpicture}% +\node at (0,0) [single arrow, shape border rotate=270, fill=red,text=red]{a};% +\end{tikzpicture}}% +\end{textblock}} + + \newcommand{\bl}[1]{\textcolor{blue}{#1}} % beamer stuff -\renewcommand{\slidecaption}{PEP (Scala) 03, King's College London} +\renewcommand{\slidecaption}{PEP (Scala) 04, King's College London} \begin{filecontents}{re3a.data} 1 0.00003 @@ -54,6 +71,20 @@ 28 26.69 \end{filecontents} +\begin{filecontents}{re-js.data} +5 0.061 +10 0.061 +15 0.061 +20 0.070 +23 0.131 +25 0.308 +26 0.564 +28 1.994 +30 7.648 +31 15.881 +32 32.190 +\end{filecontents} + \begin{filecontents}{re-java.data} 5 0.00298 10 0.00418 @@ -73,23 +104,50 @@ 28 29.81185 \end{filecontents} +\begin{filecontents}{re-java9.data} +1000 0.01410 +2000 0.04882 +3000 0.10609 +4000 0.17456 +5000 0.27530 +6000 0.41116 +7000 0.53741 +8000 0.70261 +9000 0.93981 +10000 0.97419 +11000 1.28697 +12000 1.51387 +14000 2.07079 +16000 2.69846 +20000 4.41823 +24000 6.46077 +26000 7.64373 +30000 9.99446 +34000 12.966885 +38000 16.281621 +42000 19.180228 +46000 21.984721 +50000 26.950203 +60000 43.0327746 +\end{filecontents} + + \begin{document} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{frame}[t] \frametitle{% \begin{tabular}{@ {}c@ {}} \\[5mm] - \huge PEP Scala (3) + \huge PEP Scala (4) \end{tabular}} \normalsize \begin{center} \begin{tabular}{ll} Email: & christian.urban at kcl.ac.uk\\ - Office: & N7.07 (North Wing, Bush House)\\ + Office: & N\liningnums{7.07} (North Wing, Bush House)\\ Slides \& Code: & KEATS\medskip\\ - Scala Office & \\ - Hours: & Thursdays 11 -- 13\\ + Office Hours: & Mondays 12:00 -- 14:00\\ \end{tabular} \end{center} @@ -97,85 +155,209 @@ \end{frame} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + +\begin{frame}[c] +\frametitle{Somewhere Remote} + +\begin{center} +\includegraphics[scale=0.37]{../pics/sahara.jpg} +\end{center} + +\end{frame} + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + +\begin{frame}[t] +\frametitle{This is a bit harsh\ldots} + +\mbox{}\\[-22mm]\mbox{} + +\begin{center} +\begin{bubble}[10.5cm] + ...trying a new method because the fucking github reports dont tell me + which test failed. It's not really helpful when the inline tests work + and it compiles but all i get is 'one test failed'... really helpful my dude. +\end{bubble} +\end{center} + +\begin{center} +\begin{bubble}[10.5cm] + ...Reverted back and finished part 5, this is ridiculous how one test works + and all I get is 'ONE TEST FAILED'. Fix your reports before giving us + assignments like this... +\end{bubble} +\end{center} + + +\end{frame} + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + +\begin{frame}[t,fragile] +\frametitle{Needless to say I tried it out} + +\mbox{}\\[-7mm]\mbox{}\footnotesize + +\begin{lstlisting}[language=Scala, numbers=none, xleftmargin=-4mm] +> legal_moves(8, Nil, (2,2)) + = List((3,4), (4,3), (4,1), (3,0), (1,0), (0,1), (0,3), (1,4)) + +> legal_moves(8, Nil, (7,7)) + = List((6,5), (5,6)) + +> legal_moves(8, List((4,1), (1,0)), (2,2)) + = List((3,4), (4,3), (3,0), (0,1), (0,3), (1,4)) + +> legal_moves(1, Nil, (0,0)) + = List((-1,-2), (-2,-1)) + +> legal_moves(2, Nil, (0,0)) + = List((1,-2), (-1,-2), (-2,-1), (-2,1)) + +> legal_moves(3, Nil, (0,0)) + = List((1,2), (2,1), (2,-1), (1,-2), (-1,-2), (-2,-1), (-2,1), (-1,2)) +\end{lstlisting} + +\LEFTarrow{1}{9}{9} +\LEFTarrow{1}{12}{11} +\DOWNarrow{1}{10}{13} + +\end{frame} + + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{frame}[c,fragile] - -\begin{textblock}{6}(0.5,0.5) -\begin{bubble}[11.5cm] -\footnotesize -\begin{lstlisting}[language=Scala, numbers=none, xleftmargin=-1mm] -import java.util.concurrent._ -import java.util.concurrent.atomic._ +\small + +\begin{lstlisting}[language=Scala, numbers=none, xleftmargin=-7mm] +def is_legal(dim: Int, p: Path, x: Pos): Boolean = { + if (......some_really_long_condition.....) false + else true +} +\end{lstlisting} - def collatz(input:Int){ - CollatzConjecture(input); - println(count.get()); - } - def collatz_max(input:Int){ - val List = new Array[Int](input) - for (i <- 0 to input-1){ - CollaĵConjecture(i); - List(i)=count.get(); - count.set(0); - } - val max = new AtomicInteger(); - max.set(List(0)); - val index = new AtomicInteger(); - index.set(1); - -\end{lstlisting} -\end{bubble} -\end{textblock} +\pause +\bigskip +\rule{11cm}{0.3mm} +\bigskip + +\begin{lstlisting}[language=Scala, numbers=none, xleftmargin=-7mm] +def is_legal(dim: Int, p: Path, x: Pos): Boolean = + ......some_really_long_condition..... +\end{lstlisting}\pause + \end{frame} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\begin{frame}[c,fragile] +\begin{frame}[c] +\frametitle{DFAs} + +\begin{center} +\begin{tikzpicture}[>=stealth',very thick,auto, + every state/.style={minimum size=0pt,inner sep=2pt, + draw=blue!50,very thick,fill=blue!20},] + +\only<1,3->{\node[state,initial] (Q_0) {$\mbox{Q}_0$};} +\only<2>{\node[state,initial,fill=red] (Q_0) {$\mbox{Q}_0$};} +\only<1,2,4->{\node[state] (Q_1) [right=of Q_0] {$\mbox{Q}_1$};} +\only<3>{\node[state,fill=red] (Q_1) [right=of Q_0] {$\mbox{Q}_1$};} +\only<-3,5->{\node[state] (Q_2) [below right=of Q_0] {$\mbox{Q}_2$};} +\only<4>{\node[state,fill=red] (Q_2) [below right=of Q_0] {$\mbox{Q}_2$};} +\only<-4,6->{\node[state] (Q_3) [right=of Q_2] {$\mbox{Q}_3$};} +\only<5>{\node[state,fill=red] (Q_3) [right=of Q_2] {$\mbox{Q}_3$};} +\only<-5>{\node[state, accepting] (Q_4) [right=of Q_1] {$\mbox{Q}_4$};} +\only<6->{\node[state, accepting,fill=red] (Q_4) [right=of Q_1] {$\mbox{Q}_4$};} + +\path[->] (Q_0) edge node [above] {\alert{$a$}} (Q_1); +\path[->] (Q_1) edge node [above] {\alert{$a$}} (Q_4); +\path[->] (Q_4) edge [loop right] node {\alert{$a, b$}} (); +\path[->] (Q_3) edge node [right] {\alert{$a$}} (Q_4); +\path[->] (Q_2) edge node [above] {\alert{$a$}} (Q_3); +\path[->] (Q_1) edge node [right] {\alert{$b$}} (Q_2); +\path[->] (Q_0) edge node [above] {\alert{$b$}} (Q_2); +\path[->] (Q_2) edge [loop left] node {\alert{$b$}} (); +\path[->] (Q_3) edge [bend left=95, looseness=1.3] node [below] {\alert{$b$}} (Q_0); +\end{tikzpicture} +\end{center} -\begin{textblock}{6}(0.5,0.5) -\begin{bubble}[11.5cm] -\footnotesize -\begin{lstlisting}[language=Scala, numbers=none, xleftmargin=-1mm] - for(i<-0 to input-1){ - val temp :Int=max.get(); - if (temp < List(i)){ - max.set(List(i)); - index.set(i); - } - } - println("("+max.get() +","+ index.get()+ ")"); - } +\begin{textblock}{9}(4,12) +\LARGE{} +\only<3->{\boldmath\alert{$a$}}% +\only<4->{\boldmath\alert{$b$}}% +\only<5->{\boldmath\alert{$a$}}% +\only<6->{\boldmath\alert{$a$}}% +\only<7->{\boldmath\alert{$a\quad\Rightarrow \textbf{yes}$}}% +\end{textblock} + +\end{frame} +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +\begin{frame}[t] +\frametitle{DFAs} - def CollatzConjecture(n: Long): Long = { - count.incrementAndGet(); - if (n <= 1) - 1 - else if (n\%2 ==0) - CollatzConjecture(n/2); - else - CollatzConjecture((3*n)+1); - } - } -\end{lstlisting} -\end{bubble} -\end{textblock} +A \alert{\bf deterministic finite automaton}, DFA, consists of +5 things: + +\begin{itemize} +\item an alphabet \bl{$\varSigma$} +\item a set of states \bl{$\mbox{Qs}$} +\item one of these states is the start state \bl{$\mbox{Q}_0$} +\item some states are accepting states \bl{$F$}, and +\item there is transition function \bl{$\delta$}\bigskip + +\small +which takes a state and a character as arguments and produces a +new state; this function might not be everywhere defined +\end{itemize} + +\begin{center} +\bl{$A(\varSigma, \mbox{Qs}, \mbox{Q}_0, F, \delta)$} +\end{center} \end{frame} -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +\begin{frame}[c] +\frametitle{NFAs} +\begin{center} +\begin{tikzpicture}[>=stealth',very thick, auto, + every state/.style={minimum size=0pt,inner sep=3pt, + draw=blue!50,very thick,fill=blue!20},scale=2] +\node[state,initial] (Q_0) {$\mbox{Q}_0$}; +\node[state] (Q_1) [right=of Q_0] {$\mbox{Q}_1$}; +\node[state, accepting] (Q_2) [right=of Q_1] {$\mbox{Q}_2$}; +\path[->] (Q_0) edge [loop above] node {\alert{$b$}} (); +\path[<-] (Q_0) edge node [below] {\alert{$b$}} (Q_1); +\path[->] (Q_0) edge [bend left] node [above] {\alert{$a$}} (Q_1); +\path[->] (Q_0) edge [bend right=45,looseness=1.3] node [below] {\alert{$a$}} (Q_2); +\path[->] (Q_1) edge [loop above] node {\alert{$a,b$}} (); +\path[->] (Q_1) edge node [above] {\alert{$a$}} (Q_2); +\end{tikzpicture} +\end{center} + +\end{frame} +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{frame}[c] - \frametitle{CW3 (1 Part): Regexes} + \frametitle{CW\liningnums{9} (\liningnums{1} Part): Regexes} \begin{center} Graphs: $(a^*)^* b$ and strings $\underbrace{\;a\ldots a\;}_{n}$\bigskip \begin{tabular}[t]{@{\hspace{-8mm}}c@{\hspace{-4mm}}c@{}} -\raisebox{6mm}{\begin{tikzpicture} +\only<1>{\raisebox{6mm}{\begin{tikzpicture} \begin{axis}[ xlabel={$n$}, x label style={at={(1.05,0.0)}}, @@ -189,15 +371,36 @@ axis lines=left, width=5.5cm, height=5cm, - legend entries={Python, Java 8}, + legend entries={\small{}Python, \small{}Java 8, \small{}JavaScript}, legend pos=north west, legend cell align=left] \addplot[blue,mark=*, mark options={fill=white}] table {re-python2.data}; \addplot[cyan,mark=*, mark options={fill=white}] table {re-java.data}; +\addplot[red,mark=*, mark options={fill=white}] table {re-js.data}; \end{axis} -\end{tikzpicture}} +\end{tikzpicture}}}% +\only<2>{\raisebox{0mm}{\begin{tikzpicture} +\begin{axis}[ + xlabel={$n$}, + x label style={at={(1.05,0.0)}}, + ylabel={time in secs}, + %y label style={at={(0.06,0.5)}}, + enlargelimits=false, + %xtick={0,30000,...,60000}, + xmax=65000, + ymax=35, + ytick={0,5,...,30}, + scaled ticks=true, + axis lines=left, + width=5.5cm, + height=5cm, + legend entries={\small{}Java 9}, + legend pos=north west] +\addplot[cyan,mark=*, mark options={fill=white}] table {re-java9.data}; +\end{axis} +\end{tikzpicture}}} & -\onslide<2>{\begin{tikzpicture} +\onslide<1-2>{\begin{tikzpicture} \begin{axis}[ xlabel={$n$}, x label style={at={(1.05,0.0)}}, @@ -210,7 +413,7 @@ width=5.5cm, height=5cm] %%\addplot[green,mark=square*,mark options={fill=white}] table {re2a.data}; -\addplot[red,mark=square*,mark options={fill=white}] table {re3a.data}; +\addplot[magenta,mark=square*,mark options={fill=white}] table {re3a.data}; \end{axis} \end{tikzpicture}} \end{tabular} @@ -221,16 +424,12 @@ %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{frame}[c] -\frametitle{Where to go on from here?} +\frametitle{Hint} -\begin{itemize} -\item Martin Odersky (EPFL)\ldots he is currently throwing out everything - and starts again with the dotty compiler for Scala\medskip +\begin{center} +\LARGE\textbf{\alert{Pattern-Matching}} +\end{center} -\item Elm (\url{http://elm-lang.org})\ldots web applications with style\medskip - -\item Haskell, Ocaml, Standard ML, Scheme, \ldots -\end{itemize} \end{frame} @@ -240,81 +439,9 @@ \begin{frame}[c,fragile] \frametitle{\alert{Questions?}} -{\tiny -\begin{verbatim} - * - * * - * * - * * * * - * * - * * * * - * * * * - * * * * * * * * - * * - * * * * - * * * * - * * * * * * * * - * * * * - * * * * * * * * - * * * * * * * * - * * * * * * * * * * * * * * * * - * * - * * * * - * * * * - * * * * * * * * - * * * * - * * * * * * * * - * * * * * * * * - * * * * * * * * * * * * * * * * - * * * * - * * * * * * * * - * * * * * * * * - * * * * * * * * * * * * * * * * - * * * * * * * * - * * * * * * * * * * * * * * * * - * * * * * * * * * * * * * * * * -* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * -\end{verbatim}} - - -\begin{textblock}{6}(8.5,3.5) -\begin{bubble}[5cm] -\footnotesize -\begin{lstlisting}[language=Scala, numbers=none, xleftmargin=-1mm] -++++++++[>+>++++<<-]>++>> -+<[-[>>+<<-]+>>]>+[-<<<[- ->[+[-]+>++>>>-<<]<[<]>>++ -++++[<<+++++>>-]+<<++.[-] -<<]>.>+[>>]>+] -\end{lstlisting} -\end{bubble} -\end{textblock} - \end{frame} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% - -\begin{frame}[c] -\frametitle{Marks for CW6 (Part 1 + 2)} - -Raw marks: - -\begin{itemize} -\item 6\%: 154 students -\item 5\%: 66 -\item 4\%: 18 -\item 3\%: 13 -\item 2\%: 2 -\item 1\%: 1 -\item 0\%: 21 -\end{itemize} -\end{frame} - - -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% - -\end{document} \end{document} diff -r 9e7897f25e13 -r e52cc402caee testing3/knight1.scala --- a/testing3/knight1.scala Thu Nov 29 17:15:11 2018 +0000 +++ b/testing3/knight1.scala Fri Nov 30 03:44:27 2018 +0000 @@ -7,39 +7,44 @@ // at the end are of any help. + type Pos = (Int, Int) // a position on a chessboard type Path = List[Pos] // a path...a list of positions //(1) Complete the function that tests whether the position x // is inside the board and not yet element in the path. -def is_legal(dim: Int, path: Path, x: Pos) : Boolean = ((!(path.contains(x))) && (x._1 < dim) && (x._2 < dim)) +def is_legal(dim: Int, path: Path, x: Pos) : Boolean = { + if ((x._1 < dim && x._2 < dim) && !(path.contains(x))) + true + else + false +} //(2) Complete the function that calculates for a position x // all legal onward moves that are not already in the path. // The moves should be ordered in a "clockwise" manner. + +def legal_moves(dim: Int, path: Path, x: Pos) : List[Pos] = { + val legalMovesList = List((x._1 + 1, x._2 + 2), (x._1 + 2, x._2 + 1), (x._1 + 2, x._2 - 1), (x._1 + 1, x._2 - 2), (x._1 - 1, x._2 - 2), (x._1 - 2, x._2 - 1), (x._1 - 2, x._2 + 1), (x._1 - 1, x._2 + 2)) -def legal_moves(dim: Int, path: Path, x: Pos) : List[Pos] ={ - val y = List((x._1 + 1, x._2 + 2), - (x._1 + 2, x._2 + 1), - (x._1 + 2, x._2 - 1), - (x._1 + 1, x._2 - 2), - (x._1 - 1, x._2 - 2), - (x._1 - 2, x._2 - 1), - (x._1 - 2, x._2 + 1), - (x._1 - 1, x._2 + 2) - ) - y.filter(next => is_legal(dim, path, next)) + for (i <- legalMovesList + if (is_legal(dim, path, i))) + yield i + } + //some test cases // -//assert(legal_moves(8, Nil, (2,2)) == List((3,4), (4,3), (4,1), (3,0), (1,0), (0,1), (0,3), (1,4))) +//assert(legal_moves(8, Nil, (2,2)) == +// List((3,4), (4,3), (4,1), (3,0), (1,0), (0,1), (0,3), (1,4))) //assert(legal_moves(8, Nil, (7,7)) == List((6,5), (5,6))) -//assert(legal_moves(8, List((4,1), (1,0)), (2,2)) == List((3,4), (4,3), (3,0), (0,1), (0,3), (1,4))) +//assert(legal_moves(8, List((4,1), (1,0)), (2,2)) == +// List((3,4), (4,3), (3,0), (0,1), (0,3), (1,4))) //assert(legal_moves(8, List((6,6)), (7,7)) == List((6,5), (5,6))) @@ -49,35 +54,43 @@ // and the second collects all tours in a list of paths. def count_tours(dim: Int, path: Path) : Int = { - if(path.length == dim*dim) 1 else - (for(i <- legal_moves(dim, path, path.head)) yield - count_tours(dim, i :: path) - ).sum + if (path.size == (dim ^ 2)){ + List(path).size + } else { + val totalTours = legal_moves(dim, path, path.head) + totalTours.map(element => count_tours(dim, element :: path)).sum + } } -def enum_tours(dim: Int, path: Path) : List[Path] ={ - if(path.length == dim*dim) List(path) else - (for(i <- legal_moves(dim, path, path.head)) yield - enum_tours(dim, i :: path) - ).flatten +def enum_tours(dim: Int, path: Path) : List[Path] = { + if (path.size == (dim ^ 2)){ + List(path) + } else { + val totalEnums = legal_moves(dim, path, path.head) + totalEnums.map(element => enum_tours(dim, element :: path)).flatten + } } + //(5) Implement a first-function that finds the first // element, say x, in the list xs where f is not None. // In that case Return f(x), otherwise None. If possible, // calculate f(x) only once. def first(xs: List[Pos], f: Pos => Option[Path]) : Option[Path] = { - if(xs == Nil) None - else( - for(x <- xs) yield{ - val a = f(x) - if(a != None) a - else first(xs.drop(1), f) + if (xs eq Nil) { + None + } else { + if (f(xs.head) != None) { + f(xs.head) + } else { + first(xs.tail, f) } - ).head + } + } + // test cases //def foo(x: (Int, Int)) = if (x._1 > 3) Some(List(x)) else None // @@ -92,10 +105,13 @@ // knight tour on a dim * dim-board. -// def first_tour(dim: Int, path: Path) : Option[Path] = { -// first(legal_moves(dim, path, path.head), (x : Pos => )) -// } +//def first_tour(dim: Int, path: Path) : Option[Path] = ... + + + + + /* Helper functions