# HG changeset patch
# User Christian Urban <christian.urban@kcl.ac.uk>
# Date 1607304341 0
# Node ID c02929f2647c923aeb1f8706624207ee0a46033f
# Parent  1bd800376e0c322147334cfdd8f8ae8db2f3af53
updated

diff -r 1bd800376e0c -r c02929f2647c progs/lecture4.scala
--- a/progs/lecture4.scala	Wed Dec 02 01:15:14 2020 +0000
+++ b/progs/lecture4.scala	Mon Dec 07 01:25:41 2020 +0000
@@ -271,40 +271,47 @@
               |1..5...92
               |..7.9.41.""".stripMargin.replaceAll("\\n", "")
 
-candidates(game0, (0, 0))
+
 
 type Pos = (Int, Int)
 val EmptyValue = '.'
 val MaxValue = 9
 
+def pretty(game: String): String = 
+  "\n" + (game.grouped(MaxValue).mkString("\n"))
+
+pretty(game0)
+
+
 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 emptyPosition(game: String) = {
+  val e = empty(game)
+  (e % MaxValue, e / MaxValue)
+}
 
 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))
 
-get_row(game0, 0)
+//get_row(game0, 0)
+//get_row(game0, 1)
+//get_col(game0, 0)
 
 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)))
+    (x0 until x0 + 3).toList
+      .flatMap(x => ys.map(y => game(x + y * MaxValue)))
 }
 
-//get_row(game0, 0)
-//get_row(game0, 1)
-//get_col(game0, 0)
+
 //get_box(game0, (3, 1))
 
 
@@ -313,26 +320,25 @@
   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))
+  (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"))
 
 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
+    cs.map(c => search(update(game, empty(game), c))).flatten
   }
 }
 
-List(List("sol1"), List("sol2", "sol3")).flatten
-
+pretty(game0)
 search(game0).map(pretty)
 
 val game1 = """23.915...
diff -r 1bd800376e0c -r c02929f2647c progs/lecture5.scala
--- a/progs/lecture5.scala	Wed Dec 02 01:15:14 2020 +0000
+++ b/progs/lecture5.scala	Mon Dec 07 01:25:41 2020 +0000
@@ -1,8 +1,6 @@
 // Scala Lecture 5
 //=================
 
-// TODO: word count for a very large file (40GB or so)
-// Transform Farenheit into Celsius
 
 
 // Laziness with style
@@ -174,7 +172,6 @@
 
 // (Immutable)
 // Object Oriented Programming in Scala
-//
 // =====================================
 
 
@@ -194,6 +191,13 @@
 println(Bird("Sparrow"))
 println(Bird("Sparrow").toString)
 
+Bird("Sparrow").copy(name = "House Sparrow")
+
+def group(a : Animal) = a match {
+  case Bird(_) => "It's a bird"
+  case Mammal(_) => "It's a mammal"
+}
+
 
 // There is a very convenient short-hand notation
 // for constructors:
@@ -204,11 +208,13 @@
 }
 
 val half = new Fraction(1, 2)
+half.numer
 
 case class Fraction(numer: Int, denom: Int)
 
 val half = Fraction(1, 2)
 
+half.numer
 half.denom
 
 
@@ -228,6 +234,9 @@
 
 val test = Complex(1, 2) + Complex (3, 4)
 
+import scala.language.postfixOps
+List(5,4,3,2,1).sorted.reverse
+
 // this could have equally been written as
 val test = Complex(1, 2).+(Complex (3, 4))
 
@@ -270,7 +279,7 @@
 }
 
 // BUT since we are completely IMMUTABLE, this is 
-// virtually of not concern to us.
+// virtually of no concern to us.
 
 
 
@@ -278,25 +287,26 @@
 import scala.language.implicitConversions
 import scala.language.reflectiveCalls
 
-
 case class Fraction(numer: Int, denom: Int) {
   override def toString = numer.toString + "/" + denom.toString
 
-  def +(other: Fraction) = Fraction(numer + other.numer, denom + other.denom)
-  def /(other: Fraction) = Fraction(numer * other.denom, denom * other.numer)
+  def +(other: Fraction) = 
+    Fraction(numer * other.denom + other.numer * denom, 
+             denom * other.denom)
+  def *(other: Fraction) = Fraction(numer * other.numer, denom * other.denom)
  }
 
 implicit def Int2Fraction(x: Int) = Fraction(x, 1)
 
-
 val half = Fraction(1, 2)
 val third = Fraction (1, 3)
 
 half + third
-half / third
+half * third
 
-(1 / 3) + half
-(1 / 2) + third
+1 + half
+
+
 
 
 // DFAs in Scala  
@@ -317,7 +327,7 @@
   }
 
   def accepts(s: List[C]) : Boolean = 
-    Try(fins(deltas(start, s))) getOrElse false
+    Try(fins(deltas(start, s))).getOrElse(false)
 }
 
 // the example shown in the handout 
@@ -359,7 +369,7 @@
   // 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]() 
+    Try(delta(q, c)).getOrElse(Set[A]()) 
 
   def nexts(qs: Set[A], c: C) : Set[A] =
     qs.flatMap(next(_, c))
@@ -398,6 +408,7 @@
 // A: Subset construction. Here the state type for the DFA is
 //    sets of states.
 
+
 def subset[A, C](nfa: NFA[A, C]) : DFA[Set[A], C] = {
   DFA(nfa.starts, 
       { case (qs, c) => nfa.nexts(qs, c) }, 
diff -r 1bd800376e0c -r c02929f2647c progs/sudoku.scala
--- a/progs/sudoku.scala	Wed Dec 02 01:15:14 2020 +0000
+++ b/progs/sudoku.scala	Mon Dec 07 01:25:41 2020 +0000
@@ -21,8 +21,12 @@
 
 def empty(game: String) = game.indexOf(emptyValue)
 def isDone(game: String) = empty(game) == -1 
-def emptyPosition(game: String) : Pos = 
-  (empty(game) % maxValue, empty(game) / maxValue)
+//def emptyPosition(game: String) : Pos = 
+//  (empty(game) % maxValue, empty(game) / maxValue)
+def emptyPosition(game: String) = {
+  val e = empty(game)
+  (e % maxValue, e / maxValue)
+}
 
 
 def get_row(game: String, y: Int) = indexes.map(col => game(y * maxValue + col))
@@ -65,7 +69,7 @@
 }
 
 def pretty(game: String): String = 
-  "\n" + (game.sliding(maxValue, maxValue).mkString(",\n"))
+  "\n" + (game.grouped(maxValue).mkString(",\n"))
 
 
 // a list of hard games according to Andrew Coles and Peter Norvig
@@ -78,8 +82,8 @@
        "6.2.5.........3.4..........43...8....1....2........7..5..27...........81...6.....",
        ".524.........7.1..............8.2...3.....6...9.5.....1.6.3...........897........",
        "6.2.5.........4.3..........43...8....1....2........7..5..27...........81...6.....",
-       ".923.........8.1...........1.7.4...........658.........6.5.2...4.....7.....9.....",
-
+       ".923.........8.1...........1.7.4...........658.........6.5.2...4.....7.....9.....")
+/*
        "85...24..72......9..4.........1.7..23.5...9...4...........8..7..17..........36.4.",
        "..53.....8......2..7..1.5..4....53...1..7...6..32...8..6.5....9..4....3......97..",
        "12..4......5.69.1...9...5.........7.7...52.9..3......2.9.6...5.4..9..8.1..3...9.4",
@@ -183,9 +187,9 @@
        "3...8.......7....51..............36...2..4....7...........6.13..452...........8..",
        "....14....3....2...7..........9...3.6.1.............8.2.....1.4....5.6.....7.8...",
        "4.....8.5.3..........7......2.....6.....8.4......1.......6.3.7.5..2.....1.4......")
-
-println("108:\n" ++ pretty(hard_games(108).replaceAll("\\.", " ")) ++ "\n")
-println("109:\n" ++ pretty(hard_games(109).replaceAll("\\.", " ")) ++ "\n")
+*/
+//println("108:\n" ++ pretty(hard_games(108).replaceAll("\\.", " ")) ++ "\n")
+//println("109:\n" ++ pretty(hard_games(109).replaceAll("\\.", " ")) ++ "\n")
 
 
 // for measuring time
diff -r 1bd800376e0c -r c02929f2647c progs/sudoku_test.scala
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/progs/sudoku_test.scala	Mon Dec 07 01:25:41 2020 +0000
@@ -0,0 +1,88 @@
+// Sudoku
+//========
+
+// call parallel version with
+//
+// scala -cp scala-parallel-collections_2.13-0.2.0.jar sudoku_test.scala 
+//
+// or
+//
+// scalac -cp scala-parallel-collections_2.13-0.2.0.jar sudoku_test.scala
+// java -cp .:scala-library-2.13.0.jar:scala-parallel-collections_2.13-0.2.0.jar Sudoku
+
+object Sudoku extends App { 
+
+import scala.collection.parallel.CollectionConverters._
+
+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) = {
+  val e = empty(game)
+  (e % maxValue, e / maxValue)
+}
+
+
+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)
+    for (x <- (x0 until x0 + 3).toList;
+         y <- (y0 until y0 + 3).toList) yield game(x + y * maxValue)
+}         
+
+
+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))
+
+def search(game: String): List[String] = {
+  if (isDone(game)) List(game)
+  else {
+    val cs = candidates(game, emptyPosition(game))
+    cs.par.map(c => search(update(game, empty(game), c))).toList.flatten
+  }
+}
+
+
+def pretty(game: String): String = 
+  "\n" + (game.grouped(maxValue).mkString(",\n"))
+
+
+val game2 = """8........
+              |..36.....
+              |.7..9.2..
+              |.5...7...
+              |....457..
+              |...1...3.
+              |..1....68
+              |..85...1.
+              |.9....4..""".stripMargin.replaceAll("\\n", "")
+
+// for measuring time
+def time_needed[T](i: Int, code: => T) = {
+  val start = System.nanoTime()
+  for (j <- 1 to i) code
+  val end = System.nanoTime()
+  s"${(end - start) / 1.0e9} secs"
+}
+
+
+println(time_needed(10, search(game2)))
+
+}
diff -r 1bd800376e0c -r c02929f2647c slides/slides05.pdf
Binary file slides/slides05.pdf has changed
diff -r 1bd800376e0c -r c02929f2647c slides/slides05.tex
--- a/slides/slides05.tex	Wed Dec 02 01:15:14 2020 +0000
+++ b/slides/slides05.tex	Mon Dec 07 01:25:41 2020 +0000
@@ -1,5 +1,5 @@
 % !TEX program = xelatex
-\documentclass[dvipsnames,14pt,t,xelatex]{beamer}
+\documentclass[dvipsnames,14pt,t,xelatex,aspectratio=169,xcolor={table}]{beamer}
 \usepackage{../slides}
 \usepackage{../graphics}
 \usepackage{../langs}
@@ -37,11 +37,11 @@
   \begin{center}
   \begin{tabular}{ll}
     Email:  & christian.urban at kcl.ac.uk\\
-    Office: & N\liningnums{7.07} (North Wing, Bush House)\bigskip\\
+    %Office: & N\liningnums{7.07} (North Wing, Bush House)\bigskip\\
     Slides \& Code: & KEATS\\
-                    & \onslide<2>{\alert{PDF: A Crash-Course in Scala}}\bigskip\\
-    Office Hours: &  Thursdays 12:00 -- 14:00\\
-    Additionally: & (for Scala) Tuesdays 10:45 -- 11:45\\ 
+    %                & \onslide<2>{\alert{PDF: A Crash-Course in Scala}}\bigskip\\
+    %Office Hours: &  Thursdays 12:00 -- 14:00\\
+    %Additionally: & (for Scala) Tuesdays 10:45 -- 11:45\\ 
   \end{tabular}
   \end{center}
 
@@ -50,23 +50,23 @@
 
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%     
 
-\begin{frame}[c]
-\frametitle{Marks for Preliminary 8}
-
-Raw marks (265 submissions):\bigskip
-
-\begin{itemize}
-\item 4\%: \hspace{4mm}211
-\item 3\%: \hspace{4mm}11
-\item 2\%: \hspace{4mm}14
-\item 1\%: \hspace{4mm}8
-\item 0\%: \hspace{4mm}21
-\end{itemize}\bigskip\bigskip  
-
-\footnotesize
-(plagiarism/collusion interviews ongoing again!)
-
-\end{frame}
+%\begin{frame}[c]
+%\frametitle{Marks for Preliminary 8}
+%
+%Raw marks (265 submissions):\bigskip
+%
+%\begin{itemize}
+%\item 4\%: \hspace{4mm}211
+%\item 3\%: \hspace{4mm}11
+%\item 2\%: \hspace{4mm}14
+%\item 1\%: \hspace{4mm}8
+%\item 0\%: \hspace{4mm}21
+%\end{itemize}\bigskip\bigskip  
+%
+%\footnotesize
+%(plagiarism/collusion interviews ongoing again!)
+%
+%\end{frame}
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%     
@@ -180,13 +180,13 @@
 \end{tikzpicture}
 \end{center}
 
-\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}$}}% 
+\begin{textblock}{10}(4,12)
+\LARGE{}\phantom{b}
+\only<-2>{\boldmath\textcolor{gray}{$a$}}\only<3->{\boldmath\alert{$a$}}%
+\only<-3>{\boldmath\textcolor{gray}{$b$}}\only<4->{\boldmath\alert{$b$}}%
+\only<-4>{\boldmath\textcolor{gray}{$a$}}\only<5->{\boldmath\alert{$a$}}%
+\only<-5>{\boldmath\textcolor{gray}{$a$}}\only<6->{\boldmath\alert{$a$}}%
+\only<-6>{\boldmath\textcolor{gray}{$a$}}\only<7->{\boldmath\alert{$a\quad\Rightarrow \textbf{yes}$}}% 
 \end{textblock}
   
 \end{frame}