# HG changeset patch # User Christian Urban # Date 1511493023 0 # Node ID 371acb50643d10d47a87244a862ff932b7266d55 # Parent 39c6b93718f0b2f1cea81e6e4901b661ac70c973 updated diff -r 39c6b93718f0 -r 371acb50643d cws/cw03.pdf Binary file cws/cw03.pdf has changed diff -r 39c6b93718f0 -r 371acb50643d cws/cw03.tex --- a/cws/cw03.tex Fri Nov 24 01:26:01 2017 +0000 +++ b/cws/cw03.tex Fri Nov 24 03:10:23 2017 +0000 @@ -517,7 +517,11 @@ given brainfu** program and memory, and the program counter and memory counter set to~$0$. Like \texttt{run} it returns the memory after the execution of the program finishes. You can test your brainf**k interpreter with the - Sierpinski triangle or the Hello world programs.\\\mbox{}\hfill[2 Marks] + Sierpinski triangle or the Hello world programs or have a look at + + \begin{center} + \url{https://esolangs.org/wiki/Brainfuck} + \end{center}\hfill[2 Marks] \begin{figure}[p] \begin{center} diff -r 39c6b93718f0 -r 371acb50643d progs/catastrophic.py --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/progs/catastrophic.py Fri Nov 24 03:10:23 2017 +0000 @@ -0,0 +1,24 @@ +#!/usr/bin/env python +import re +import sys + +# case of catastrophic backtracking in Python +# +# regex: (a?){n} a{n} +# strings: aa... +# +# call with timing as: +# +# > time ./catastrophic.py 20 + +# counter n given on the command line +cn = sys.argv[1] + +# constructing the regex +r1 = '((a?){%s})' % cn +r2 = 'a{%s}' % cn + +# calling the matching function +m = re.match(r1 + r2 , "a" * int(cn)) + +print m.group(0) diff -r 39c6b93718f0 -r 371acb50643d progs/lecture2.scala --- a/progs/lecture2.scala Fri Nov 24 01:26:01 2017 +0000 +++ b/progs/lecture2.scala Fri Nov 24 03:10:23 2017 +0000 @@ -346,126 +346,6 @@ better_first_word("").map(duplicate).map(valid_msg) -// Pattern Matching -//================== - -// A powerful tool which is supposed to come to Java in a few years -// time (https://www.youtube.com/watch?v=oGll155-vuQ)...Scala already -// has it for many years ;o) - -// The general schema: -// -// expression match { -// case pattern1 => expression1 -// case pattern2 => expression2 -// ... -// case patternN => expressionN -// } - - -// remember -val lst = List(None, Some(1), Some(2), None, Some(3)).flatten - - -def my_flatten(xs: List[Option[Int]]): List[Int] = { - ...? -} - - - - - -def my_flatten(lst: List[Option[Int]]): List[Int] = lst match { - case Nil => Nil - case None::xs => my_flatten(xs) - case Some(n)::xs => n::my_flatten(xs) -} - - -// another example including a catch-all pattern -def get_me_a_string(n: Int): String = n match { - case 0 => "zero" - case 1 => "one" - case 2 => "two" - case _ => "many" -} - -get_me_a_string(0) - -// you can also have cases combined -def season(month: String) = month match { - case "March" | "April" | "May" => "It's spring" - case "June" | "July" | "August" => "It's summer" - case "September" | "October" | "November" => "It's autumn" - case "December" | "January" | "February" => "It's winter" -} - -println(season("November")) - -// What happens if no case matches? - -println(season("foobar")) - - -// User-defined Datatypes -//======================== - -abstract class Colour -case class Red() extends Colour -case class Green() extends Colour -case class Blue() extends Colour - -def fav_colour(c: Colour) : Boolean = c match { - case Red() => false - case Green() => true - case Blue() => false -} - - -// actually colors can be written with "object", -// because they do not take any arguments - - -// another example -//================= - -// Once upon a time, in a complete fictional country there were persons... - -abstract class Person -case class King() extends Person -case class Peer(deg: String, terr: String, succ: Int) extends Person -case class Knight(name: String) extends Person -case class Peasant(name: String) extends Person - - -def title(p: Person): String = p match { - case King() => "His Majesty the King" - case Peer(deg, terr, _) => s"The ${deg} of ${terr}" - case Knight(name) => s"Sir ${name}" - case Peasant(name) => name -} - - -def superior(p1: Person, p2: Person): Boolean = (p1, p2) match { - case (King(), _) => true - case (Peer(_,_,_), Knight(_)) => true - case (Peer(_,_,_), Peasant(_)) => true - case (Peer(_,_,_), Clown()) => true - case (Knight(_), Peasant(_)) => true - case (Knight(_), Clown()) => true - case (Clown(), Peasant(_)) => true - case _ => false -} - -val people = List(Knight("David"), - Peer("Duke", "Norfolk", 84), - Peasant("Christian"), - King(), - Clown()) - -println(people.sortWith(superior(_, _)).mkString(", ")) - - @@ -509,24 +389,8 @@ time_needed(10, count_intersection2(A, B)) -// Implicits (Cool Feature) -//========================= -// -// 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 - // No returns in Scala diff -r 39c6b93718f0 -r 371acb50643d progs/lecture3.scala --- a/progs/lecture3.scala Fri Nov 24 01:26:01 2017 +0000 +++ b/progs/lecture3.scala Fri Nov 24 03:10:23 2017 +0000 @@ -1,7 +1,72 @@ // Scala Lecture 3 //================= -// adding two binary strings very, very lazy manner +// Pattern Matching +//================== + +// A powerful tool which is supposed to come to Java in a few years +// time (https://www.youtube.com/watch?v=oGll155-vuQ)...Scala already +// has it for many years. Other functional languages have it for +// decades. I think I would refuse to program in a language that +// does not have pattern matching....its is just so elegant. ;o) + +// The general schema: +// +// expression match { +// case pattern1 => expression1 +// case pattern2 => expression2 +// ... +// case patternN => expressionN +// } + + +// remember +val lst = List(None, Some(1), Some(2), None, Some(3)).flatten + + +def my_flatten(xs: List[Option[Int]]): List[Int] = { + ...? +} + + + + + +def my_flatten(lst: List[Option[Int]]): List[Int] = lst match { + case Nil => Nil + case None::xs => my_flatten(xs) + case Some(n)::xs => n::my_flatten(xs) +} + + +// another example including a catch-all pattern +def get_me_a_string(n: Int): String = n match { + case 0 => "zero" + case 1 => "one" + case 2 => "two" + case _ => "many" +} + +get_me_a_string(0) + +// you can also have cases combined +def season(month: String) = month match { + case "March" | "April" | "May" => "It's spring" + case "June" | "July" | "August" => "It's summer" + case "September" | "October" | "November" => "It's autumn" + case "December" | "January" | "February" => "It's winter" +} + +println(season("November")) + +// What happens if no case matches? + +println(season("foobar")) + + +// Collatz function on binary strings + +// adding two binary strings in a very, very lazy manner def badd(s1: String, s2: String) : String = (BigInt(s1, 2) + BigInt(s2, 2)).toString(2) @@ -21,33 +86,26 @@ bcollatz(100000000000000000L.toBinaryString) bcollatz(BigInt("1000000000000000000000000000000000000000000000000000000000000000000000000000").toString(2)) -def conv(c: Char) : Int = c match { - case '0' => 0 - case '1' => 1 + + + +// User-defined Datatypes +//======================== + +abstract class Colour +case class Red() extends Colour +case class Green() extends Colour +case class Blue() extends Colour + +def fav_colour(c: Colour) : Boolean = c match { + case Red() => false + case Green() => true + case Blue() => false } -def badds(s1: String, s2: String, carry: Int) : String = (s1, s2, carry) match { - case ("", "", 1) => "1" - case ("", "", 0) => "" - case (cs1, cs2, carry) => (conv(cs1.last) + conv(cs2.last) + carry) match { - case 3 => badds(cs1.dropRight(1), cs2.dropRight(1), 1) + '1' - case 2 => badds(cs1.dropRight(1), cs2.dropRight(1), 1) + '0' - case 1 => badds(cs1.dropRight(1), cs2.dropRight(1), 0) + '1' - case 0 => badds(cs1.dropRight(1), cs2.dropRight(1), 0) + '0' - } -} -def bcollatz2(s: String) : Long = (s.dropRight(1), s.last) match { - case ("", '1') => 1 // we reached 1 - case (rest, '0') => 1 + bcollatz2(rest) // even number => divide by two - case (rest, '1') => 1 + bcollatz2(badds(s + '1', '0' + s, 0)) // odd number => s + '1' is 2 * s + 1 - // add another s gives 3 * s + 1 -} - -bcollatz2(9.toBinaryString) -bcollatz2(837799.toBinaryString) -bcollatz2(100000000000000000L.toBinaryString) -bcollatz2(BigInt("1000000000000000000000000000000000000000000000000000000000000000000000000000").toString(2)) +// actually colors can be written with "object", +// because they do not take any arguments @@ -88,108 +146,190 @@ RomanNumeral2Int(List(M,M,X,V,I,I)) // 2017 -// Tail recursion -//================ + +// another example +//================= + +// Once upon a time, in a complete fictional country there were persons... -def my_contains(elem: Int, lst: List[Int]): Boolean = lst match { - case Nil => false - case x::xs => - if (x == elem) true else my_contains(elem, xs) +abstract class Person +case class King() extends Person +case class Peer(deg: String, terr: String, succ: Int) extends Person +case class Knight(name: String) extends Person +case class Peasant(name: String) extends Person + + +def title(p: Person): String = p match { + case King() => "His Majesty the King" + case Peer(deg, terr, _) => s"The ${deg} of ${terr}" + case Knight(name) => s"Sir ${name}" + case Peasant(name) => name } -my_contains(4, List(1,2,3)) -my_contains(2, List(1,2,3)) -my_contains(1000000, (1 to 1000000).toList) -my_contains(1000001, (1 to 1000000).toList) +def superior(p1: Person, p2: Person): Boolean = (p1, p2) match { + case (King(), _) => true + case (Peer(_,_,_), Knight(_)) => true + case (Peer(_,_,_), Peasant(_)) => true + case (Peer(_,_,_), Clown()) => true + case (Knight(_), Peasant(_)) => true + case (Knight(_), Clown()) => true + case (Clown(), Peasant(_)) => true + case _ => false +} + +val people = List(Knight("David"), + Peer("Duke", "Norfolk", 84), + Peasant("Christian"), + King(), + Clown()) + +println(people.sortWith(superior(_, _)).mkString(", ")) -//factorial V0.1 -import scala.annotation.tailrec + + +// Tail recursion +//================ def fact(n: Long): Long = if (n == 0) 1 else n * fact(n - 1) -fact(10000) // produces a stackoverflow +fact(10) //ok +fact(10000) // produces a stackoverflow + +def factT(n: BigInt, acc: BigInt): BigInt = + if (n == 0) acc else factT(n - 1, n * acc) + +factT(100000, 1) + +// there is a flag for ensuring a function is tail recursive +import scala.annotation.tailrec @tailrec def factT(n: BigInt, acc: BigInt): BigInt = if (n == 0) acc else factT(n - 1, n * acc) -println(factT(10000, 1)) -// the functions my_contains and factT are tail-recursive -// you can check this with - -import scala.annotation.tailrec - -// and the annotation @tailrec - -// for tail-recursive functions the scala compiler +// for tail-recursive functions the Scala compiler // generates loop-like code, which does not need // to allocate stack-space in each recursive -// call; scala can do this only for tail-recursive +// call; Scala can do this only for tail-recursive // functions -// consider the following "stupid" version of the -// coin exchange problem: given some coins and a -// total, what is the change can you get? + + +// sudoku again + +val game0 = """.14.6.3.. + |62...4..9 + |.8..5.6.. + |.6.2....3 + |.7..1..5. + |5....9.6. + |..6.2..3. + |1..5...92 + |..7.9.41.""".stripMargin.replaceAll("\\n", "") -val coins = List(4,5,6,8,10,13,19,20,21,24,38,39,40) +type Pos = (Int, Int) +val EmptyValue = '.' +val MaxValue = 9 + +val allValues = "123456789".toList +val indexes = (0 to 8).toList + + +def empty(game: String) = game.indexOf(EmptyValue) +def isDone(game: String) = empty(game) == -1 +def emptyPosition(game: String) = + (empty(game) % MaxValue, empty(game) / MaxValue) + -def first_positive[B](lst: List[Int], f: Int => Option[B]): Option[B] = lst match { - case Nil => None - case x::xs => - if (x <= 0) first_positive(xs, f) - else { - val fx = f(x) - if (fx.isDefined) fx else first_positive(xs, f) +def get_row(game: String, y: Int) = + indexes.map(col => game(y * MaxValue + col)) +def get_col(game: String, x: Int) = + indexes.map(row => game(x + row * MaxValue)) + +def get_box(game: String, pos: Pos): List[Char] = { + def base(p: Int): Int = (p / 3) * 3 + val x0 = base(pos._1) + val y0 = base(pos._2) + val ys = (y0 until y0 + 3).toList + (x0 until x0 + 3).toList.flatMap(x => ys.map(y => game(x + y * MaxValue))) +} + +// this is not mutable!! +def update(game: String, pos: Int, value: Char): String = + game.updated(pos, value) + +def toAvoid(game: String, pos: Pos): List[Char] = + (get_col(game, pos._1) ++ get_row(game, pos._2) ++ get_box(game, pos)) + +def candidates(game: String, pos: Pos): List[Char] = + allValues.diff(toAvoid(game,pos)) + +//candidates(game0, (0,0)) + +def pretty(game: String): String = + "\n" + (game sliding (MaxValue, MaxValue) mkString "\n") + +// not tail recursive +def search(game: String): List[String] = { + if (isDone(game)) List(game) + else { + val cs = candidates(game, emptyPosition(game)) + cs.map(c => search(update(game, empty(game), c))).toList.flatten } } - -import scala.annotation.tailrec - -def search(total: Int, coins: List[Int], cs: List[Int]): Option[List[Int]] = { - if (total < cs.sum) None - else if (cs.sum == total) Some(cs) - else first_positive(coins, (c: Int) => search(total, coins, c::cs)) +// tail recursive version that searches +// for all solution +def searchT(games: List[String], sols: List[String]): List[String] = games match { + case Nil => sols + case game::rest => { + if (isDone(game)) searchT(rest, game::sols) + else { + val cs = candidates(game, emptyPosition(game)) + searchT(cs.map(c => update(game, empty(game), c)) ::: rest, sols) + } + } } -search(11, coins, Nil) -search(111, coins, Nil) -search(111111, coins, Nil) - -val junk_coins = List(4,-2,5,6,8,0,10,13,19,20,-3,21,24,38,39, 40) -search(11, junk_coins, Nil) -search(111, junk_coins, Nil) - - -import scala.annotation.tailrec - -@tailrec -def searchT(total: Int, coins: List[Int], - acc_cs: List[List[Int]]): Option[List[Int]] = acc_cs match { +// tail recursive version that searches +// for a single solution +def search1T(games: List[String]): Option[String] = games match { case Nil => None - case x::xs => - if (total < x.sum) searchT(total, coins, xs) - else if (x.sum == total) Some(x) - else searchT(total, coins, coins.filter(_ > 0).map(_::x) ::: xs) + case game::rest => { + if (isDone(game)) Some(game) + else { + val cs = candidates(game, emptyPosition(game)) + search1T(cs.map(c => update(game, empty(game), c)) ::: rest) + } + } } -val start_acc = coins.filter(_ > 0).map(List(_)) -searchT(11, junk_coins, start_acc) -searchT(111, junk_coins, start_acc) -searchT(111111, junk_coins, start_acc) +// game with multiple solutions +val game3 = """.8...9743 + |.5...8.1. + |.1....... + |8....5... + |...8.4... + |...3....6 + |.......7. + |.3.5...8. + |9724...5.""".stripMargin.replaceAll("\\n", "") + +searchT(List(game3), List()).map(pretty) +search1T(List(game3)).map(pretty) // Moral: Whenever a recursive function is resource-critical // (i.e. works with large recursion depths), then you need to // write it in tail-recursive fashion. // -// Unfortuantely, the Scala is because of current limitations in -// the JVM not as clever as other functional languages. It can +// Unfortuantely, Scala because of current limitations in +// the JVM is not as clever as other functional languages. It can // only optimise "self-tail calls". This excludes the cases of // multiple functions making tail calls to each other. Well, // nothing is perfect. @@ -230,59 +370,43 @@ def first[A, B](xs: List[A], f: A => Option[B]): Option[B] = ... -// polymorphic classes -//(trees with some content) - -abstract class Tree[+A] -case class Node[A](elem: A, left: Tree[A], right: Tree[A]) extends Tree[A] -case object Leaf extends Tree[Nothing] -val t0 = Node('4', Node('2', Leaf, Leaf), Node('7', Leaf, Leaf)) +// Cool Stuff +//============ -def insert[A](tr: Tree[A], n: A): Tree[A] = tr match { - case Leaf => Node(n, Leaf, Leaf) - case Node(m, left, right) => - if (n == m) Node(m, left, right) - else if (n < m) Node(m, insert(left, n), right) - else Node(m, left, insert(right, n)) -} + -// the A-type needs to be ordered - -abstract class Tree[+A <% Ordered[A]] -case class Node[A <% Ordered[A]](elem: A, left: Tree[A], - right: Tree[A]) extends Tree[A] -case object Leaf extends Tree[Nothing] +// 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. -def insert[A <% Ordered[A]](tr: Tree[A], n: A): Tree[A] = tr match { - case Leaf => Node(n, Leaf, Leaf) - case Node(m, left, right) => - if (n == m) Node(m, left, right) - else if (n < m) Node(m, insert(left, n), right) - else Node(m, left, insert(right, n)) +implicit class MyString(s: String) { + def increment = for (c <- s) yield (c + 1).toChar } +"HAL".increment -val t1 = Node(4, Node(2, Leaf, Leaf), Node(7, Leaf, Leaf)) -insert(t1, 3) - -val t2 = Node('b', Node('a', Leaf, Leaf), Node('f', Leaf, Leaf)) -insert(t2, 'e') // Regular expressions - the power of DSLs in Scala //================================================== - abstract class Rexp -case object ZERO extends Rexp -case object ONE extends Rexp -case class CHAR(c: Char) extends 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 SEQ(r1: Rexp, r2: Rexp) extends Rexp // sequence r1 o r2 case class STAR(r: Rexp) extends Rexp // star r* @@ -326,63 +450,6 @@ val number = sign ~ digit ~ digit.% -//implement print_re - - - -// Lazyness with style -//===================== - -// The concept of lazy evaluation doesn’t really exist in -// non-functional languages, but it is pretty easy to grasp. -// Consider first - -def square(x: Int) = x * x - -square(42 + 8) - -// this is called strict evaluation - - -def expensiveOperation(n: BigInt): Boolean = expensiveOperation(n + 1) -val a = "foo" -val b = "bar" - -val test = if ((a == b) || expensiveOperation(0)) true else false - -// this is called lazy evaluation -// you delay compuation until it is really -// needed; once calculated though, does not -// need to be re-calculated - -// a useful example is -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) + " secs" -} - - -// streams (I do not care how many) -// primes: 2, 3, 5, 7, 9, 11, 13 .... - -def generatePrimes (s: Stream[Int]): Stream[Int] = - s.head #:: generatePrimes(s.tail filter (_ % s.head != 0)) - -val primes: Stream[Int] = generatePrimes(Stream.from(2)) - -primes.take(10).toList - -primes.filter(_ > 100).take(2000).toList - -time_needed(1, primes.filter(_ > 100).take(2000).toList) -time_needed(1, primes.filter(_ > 100).take(2000).toList) - - - -// streams are useful for implementing search problems ;o) - @@ -397,5 +464,5 @@ // You can be productive on Day 1, but the language is deep. // I like best about Scala that it lets me write -// concise, readable code +// concise, readable code. diff -r 39c6b93718f0 -r 371acb50643d slides/slides03.pdf Binary file slides/slides03.pdf has changed diff -r 39c6b93718f0 -r 371acb50643d slides/slides03.tex --- a/slides/slides03.tex Fri Nov 24 01:26:01 2017 +0000 +++ b/slides/slides03.tex Fri Nov 24 03:10:23 2017 +0000 @@ -2,7 +2,7 @@ \usepackage{../slides} \usepackage{../graphics} \usepackage{../langs} -%\usepackage{../data} +%%\usepackage{../data} \usepackage[export]{adjustbox} \hfuzz=220pt @@ -21,9 +21,59 @@ % beamer stuff \renewcommand{\slidecaption}{PEP (Scala) 03, King's College London} +\begin{filecontents}{re3a.data} +1 0.00003 +500001 0.22527 +1000001 0.62752 +1500001 0.88485 +2000001 1.39815 +2500001 1.68619 +3000001 1.94957 +3500001 2.15878 +4000001 2.59918 +4500001 5.90679 +5000001 13.11295 +5500001 19.15376 +6000001 40.16373 +\end{filecontents} +\begin{filecontents}{re-python2.data} +1 0.033 +5 0.036 +10 0.034 +15 0.036 +18 0.059 +19 0.084 +20 0.141 +21 0.248 +22 0.485 +23 0.878 +24 1.71 +25 3.40 +26 7.08 +27 14.12 +28 26.69 +\end{filecontents} + +\begin{filecontents}{re-java.data} +5 0.00298 +10 0.00418 +15 0.00996 +16 0.01710 +17 0.03492 +18 0.03303 +19 0.05084 +20 0.10177 +21 0.19960 +22 0.41159 +23 0.82234 +24 1.70251 +25 3.36112 +26 6.63998 +27 13.35120 +28 29.81185 +\end{filecontents} \begin{document} - %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{frame}[t] \frametitle{% @@ -35,9 +85,11 @@ \normalsize \begin{center} \begin{tabular}{ll} - Email: & christian.urban at kcl.ac.uk\\ - Office: & S1.27 (1st floor Strand Building)\\ - Slides \& Code: & KEATS + Email: & christian.urban at kcl.ac.uk\\ + Office: & N7.07 (North Wing, Bush House)\\ + Slides \& Code: & KEATS\medskip\\ + Scala Office & \\ + Hours: & Thursdays 11 -- 13\\ \end{tabular} \end{center} @@ -45,181 +97,79 @@ \end{frame} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\begin{frame}[c, fragile] -\frametitle{The Joy of Immutability} - -\begin{itemize} -\item If you need to manipulate some data in a list say, then you make - a new list with the updated values, rather than revise the original - list. Easy!\medskip - - {\small - \begin{lstlisting}[language=Scala, numbers=none, xleftmargin=-1mm] - val old_list = List(1, 2, 3, 5) - val new_list = 0 :: old_list - \end{lstlisting}} - -\item You do not have to be defensive about who can access the data - (concurrency, lazyness). -\end{itemize} -\end{frame} - - -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\begin{frame}[t] -\frametitle{Email: Hate 'val'} - -\mbox{}\\[-25mm]\mbox{} - -\begin{center} - \begin{bubble}[10.5cm] - Subject: \textbf{Hate '\textbf{\texttt{val}}'}\hfill 01:00 AM\medskip\\ - - Hello Mr Urban,\medskip\\ - - I just wanted to ask, how are we suppose to work - with the completely useless \textbf{\texttt{val}}, that can’t be changed ever? Why is - this rule active at all? I’ve spent 4 hours not thinking on the - coursework, but how to bypass this annoying rule. What’s the whole - point of all these coursework, when we can’t use everything Scala - gives us?!?\medskip\\ - - Regards.\\ - \mbox{}\hspace{5mm}\textcolor{black!50}{<>}\\ - \end{bubble} -\end{center} - -\end{frame} -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% - -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\begin{frame}[c] - -\mbox{}\\[-25mm]\mbox{} - -\begin{center} - \begin{bubble}[10.5cm] - Subject: \textbf{Re: Hate '\textbf{\texttt{val}}'}\hfill 01:02 AM\bigskip\bigskip\\ - - \textcolor{black!70}{ - \textit{\large<>}}\bigskip\bigskip\bigskip - - PS: What are you trying to do where you desperately want to use \texttt{var}? - \end{bubble} -\end{center} - -\end{frame} -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{frame}[c,fragile] \begin{textblock}{6}(0.5,0.5) \begin{bubble}[11.5cm] - \small - Subject: \textbf{Re: Re: Hate '\textbf{\texttt{val}}'}\hfill 01:04 AM\medskip\\ +\footnotesize +\begin{lstlisting}[language=Scala, numbers=none, xleftmargin=-1mm] +import java.util.concurrent._ +import java.util.concurrent.atomic._ - \textbf{Right now my is\_legal function works fine:} - -\footnotesize\begin{lstlisting}[language=Scala, numbers=none, xleftmargin=-1mm] - def is_legal(dim: Int, path: Path)(x: Pos): Boolean = { - var boolReturn = false - if(x._1 > dim || x._2 > dim || x._1 < 0 || x._2 < 0) { - else { var breakLoop = false - if(path == Nil) { boolReturn = true } - else { for(i <- 0 until path.length) { - if(breakLoop == false) { - if(path(i) == x) { - boolReturn = true - breakLoop = true - } - else { boolReturn = false } - } else breakLoop + 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); } - } - boolReturn - } + val max = new AtomicInteger(); + max.set(List(0)); + val index = new AtomicInteger(); + index.set(1); + \end{lstlisting} \end{bubble} \end{textblock} -\begin{textblock}{6}(8.2,11.8) -\begin{bubble}[5.5cm]\footnotesize\bf -\ldots{}but I can’t make it work with boolReturn being val. What approach would -you recommend in this case, and is using var in this case justified? -\end{bubble} -\end{textblock} - -\only<2>{ -\begin{textblock}{6}(0.3,11.8) - \begin{bubble}[3.1cm] - \textbf{Me:} \includegraphics[scale=0.08, valign=t]{../pics/throwup.jpg} - \end{bubble} -\end{textblock}} - \end{frame} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\begin{frame}[t,fragile] - -\mbox{}\\[-25mm]\mbox{} +\begin{frame}[c,fragile] -\begin{textblock}{6}(0.5,2) - \begin{bubble}[11.5cm] - Subject: \textbf{Re: Re: Re: Hate '\textbf{\texttt{val}}'}\hfill 01:06 AM\bigskip\\ - \small - - OK. So you want to make sure that the \texttt{x}-position is not outside the - board....and furthermore you want to make sure that the \texttt{x}-position - is not yet in the path list. How about something like\bigskip +\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()+ ")"); + } -\footnotesize\begin{lstlisting}[language=Scala, numbers=none, xleftmargin=-1mm] - def is_legal(dim: Int, path: Path)(x: Pos): Boolean = - ...<>... && !path.contains(x) -\end{lstlisting}\bigskip - - \small Does not even contain a \texttt{val}. - \end{bubble} -\end{textblock} - -\begin{textblock}{6}(7,12) -\footnotesize\textcolor{black!50}{(This is all on one line)} + 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} \end{frame} -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% - - -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\begin{frame}[t,fragile] - -\mbox{}\\[-15mm]\mbox{} - -\begin{textblock}{6}(1,3) - \begin{bubble}[10.5cm] - Subject: \textbf{Re: Re: Re: Re: Hate '\textbf{\texttt{val}}'}\hfill 11:02 AM\bigskip\bigskip\\ - - THANK YOU! You made me change my coding perspective. Because of you, - I figured out the next one\ldots - \end{bubble} -\end{textblock} - -\only<2>{ -\begin{textblock}{6}(0.3,11.8) - \begin{bubble}[3.1cm] - \textbf{Me:} \includegraphics[scale=0.08]{../pics/happy.jpg} - \end{bubble} -\end{textblock}} - -\end{frame} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{frame}[c] - \frametitle{CW3: Regexes (1 Part)} + \frametitle{CW3 (1 Part): Regexes} \begin{center} Graphs: $(a^*)^* b$ and strings $\underbrace{\;a\ldots a\;}_{n}$\bigskip @@ -287,32 +237,77 @@ %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\begin{frame}[c] -\frametitle{\begin{tabular}{c}\\[3cm]\alert{Questions?}\end{tabular}} +\begin{frame}[c,fragile] +\frametitle{\alert{Questions?}} -\mbox{}\footnotesize -Thanks: ``\it{}By the way - Scala is really getting quite fun -when you start to get the hang of it\ldots'' +{\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)} +\frametitle{Marks for CW6 (Part 1 + 2)} -Absolute raw marks, alleged collusions still included: +Raw marks: \begin{itemize} -\item 0\%: 18 students -\item 1\%: 2 -\item 2\%: 11 -\item 3\%: 29 +\item 0\%: 21 students +\item 1\%: 1 +\item 2\%: 2 +\item 3\%: 13 \item 4\%: 18 -\item 5\%: 33 -\item 6\%: 55 -\item 7\%: 62 +\item 5\%: 66 +\item 6\%: 154 \end{itemize} \end{frame}