# HG changeset patch
# User Christian Urban <urbanc@in.tum.de>
# Date 1573555647 0
# Node ID b84ea52bfd8ffb90c434014bea385c5efa5fa4f3
# Parent  029e2862bb4e28ecfc9771e84e32b452448d96bd
updated

diff -r 029e2862bb4e -r b84ea52bfd8f progs/lecture2.scala
--- a/progs/lecture2.scala	Tue Nov 12 00:41:00 2019 +0000
+++ b/progs/lecture2.scala	Tue Nov 12 10:47:27 2019 +0000
@@ -75,11 +75,14 @@
 // the same for files
 Try(Some(Source.fromFile("text.txt").mkString)).getOrElse(None)
 
-// how to implement a function for reading something from files...
 
+// how to implement a function for reading 
+// (lines) something from files...
+//
 def get_contents(name: String) : List[String] = 
   Source.fromFile(name).getLines.toList
 
+get_contents("text.txt")
 get_contents("test.txt")
 
 // slightly better - return Nil
@@ -156,6 +159,7 @@
 //========================
 
 // functions can take functions as arguments
+// and produce functions as result
 
 def even(x: Int) : Boolean = x % 2 == 0
 def odd(x: Int) : Boolean = x % 2 == 1
@@ -204,8 +208,8 @@
 
 lst.map(square)
 
-// this is actually how for-comprehensions 
-// defined as in Scala
+// this is actually how for-comprehensions are
+// defined in Scala
 
 lst.map(n => square(n))
 for (n <- lst) yield square(n)
@@ -232,7 +236,8 @@
 // same function using pattern matching: a kind
 // of switch statement on steroids (see more later on)
 
-def my_map_int(lst: List[Int], f: Int => Int) : List[Int] = lst match {
+def my_map_int(lst: List[Int], f: Int => Int) : List[Int] = 
+lst match {
   case Nil => Nil
   case x::xs => f(x)::my_map_int(xs, f)
 }
@@ -268,10 +273,10 @@
 // sometimes it is needed that you specify the type. 
 (1 to 100).filter((x: Int) => x % 2 == 0).sum 
 
-// in this case it is clear that x mist be an Int
+// in this case it is clear that x must be an Int
 (1 to 100).filter(x => x % 2 == 0).sum
 
-// As each parameter (only x in this case) is passed only once
+// When each parameter (only x in this case) is used only once
 // you can use the wizardy placeholder syntax
 (1 to 100).filter(_ % 2 == 0).sum
 
@@ -334,7 +339,7 @@
 facsMap.get(1)
 facsMap2.get(1)
 
-// groupBy function on maps
+// groupBy function on Maps
 
 val ls = List("one", "two", "three", "four", "five")
 ls.groupBy(_.length)
@@ -361,18 +366,17 @@
 //    }
 
 
-
-
-// remember?
+// recall
 val lst = List(None, Some(1), Some(2), None, Some(3)).flatten
 
-
 def my_flatten(xs: List[Option[Int]]): List[Int] = xs match {
   case Nil => Nil 
   case None::rest => my_flatten(rest)
   case Some(v)::rest => v :: my_flatten(rest)
 }
 
+my_flatten(List(None, Some(1), Some(2), None, Some(3)))
+
 
 // another example with a default case
 def get_me_a_string(n: Int): String = n match {
@@ -538,4 +542,73 @@
 
 
 
+// Jumping Towers
+//================
 
+
+def moves(xs: List[Int], n: Int) : List[List[Int]] = (xs, n) match {
+  case (Nil, _) => Nil
+  case (xs, 0) => Nil
+  case (x::xs, n) => (x::xs) :: moves(xs, n - 1)
+}
+
+
+moves(List(5,1,0), 1)
+moves(List(5,1,0), 2)
+moves(List(5,1,0), 5)
+
+// checks whether a jump tour exists at all
+
+def search(xs: List[Int]) : Boolean = xs match {
+  case Nil => true
+  case (x::xs) =>
+    if (xs.length < x) true else moves(xs, x).exists(search(_))
+}
+
+
+search(List(5,3,2,5,1,1))
+search(List(3,5,1,0,0,0,1))
+search(List(3,5,1,0,0,0,0,1))
+search(List(3,5,1,0,0,0,1,1))
+search(List(3,5,1))
+search(List(5,1,1))
+search(Nil)
+search(List(1))
+search(List(5,1,1))
+search(List(3,5,1,0,0,0,0,0,0,0,0,1))
+
+// generate *all* jump tours
+//    if we are only interested in the shortes one, we could
+//    shortcircut the calculation and only return List(x) in
+//    case where xs.length < x, because no tour can be shorter
+//    than 1
+// 
+
+def jumps(xs: List[Int]) : List[List[Int]] = xs match {
+  case Nil => Nil
+  case (x::xs) => {
+    val children = moves(xs, x)
+    val results = children.map(cs => jumps(cs).map(x :: _)).flatten
+    if (xs.length < x) List(x) :: results else results
+  }
+}
+
+jumps(List(3,5,1,2,1,2,1))
+jumps(List(3,5,1,2,3,4,1))
+jumps(List(3,5,1,0,0,0,1))
+jumps(List(3,5,1))
+jumps(List(5,1,1))
+jumps(Nil)
+jumps(List(1))
+jumps(List(5,1,2))
+moves(List(1,2), 5)
+jumps(List(1,5,1,2))
+jumps(List(3,5,1,0,0,0,0,0,0,0,0,1))
+
+jumps(List(5,3,2,5,1,1)).minBy(_.length)
+jumps(List(1,3,5,8,9,2,6,7,6,8,9)).minBy(_.length)
+jumps(List(1,3,6,1,0,9)).minBy(_.length)
+jumps(List(2,3,1,1,2,4,2,0,1,1)).minBy(_.length)
+
+
+
diff -r 029e2862bb4e -r b84ea52bfd8f progs/lecture4.scala
--- a/progs/lecture4.scala	Tue Nov 12 00:41:00 2019 +0000
+++ b/progs/lecture4.scala	Tue Nov 12 10:47:27 2019 +0000
@@ -434,7 +434,7 @@
 // Conversions add a wrapper when a member of T is requested 
 // from an instance of C.
 
-//Another example
+//Another example (TimeUnit in 2.13?)
 
 case class Duration(time: Long, unit: TimeUnit) {
   def +(o: Duration) = Duration(time + unit.convert(o.time, o.unit), unit)
diff -r 029e2862bb4e -r b84ea52bfd8f slides/slides02.pdf
Binary file slides/slides02.pdf has changed
diff -r 029e2862bb4e -r b84ea52bfd8f slides/slides02.tex
--- a/slides/slides02.tex	Tue Nov 12 00:41:00 2019 +0000
+++ b/slides/slides02.tex	Tue Nov 12 10:47:27 2019 +0000
@@ -441,7 +441,7 @@
 \end{lstlisting}
 \end{onlyenv}\bigskip\bigskip\bigskip
  
-in the Scala code it is clear from the type I have to deal 
+in the Scala code it is clear from the type I that have to deal 
 with the \pcode{None}-case; no JavaDoc needed
   
 \end{frame}
@@ -574,9 +574,24 @@
 
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%     
 \begin{frame}[c,fragile]
-\frametitle{Recursion}
+\frametitle{Pattern Matching}
+
+\ldots on pairs:\bigskip
 
+\begin{lstlisting}[language=Scala, numbers=none, xleftmargin=-2mm]
+def fizz_buzz(n: Int) : String = 
+ (n % 3, n % 5) match {
+   case (0, 0) => "fizz buzz"
+   case (0, _) => "fizz"
+   case (_, 0) => "buzz"
+   case _ => n.toString  
+ }
+\end{lstlisting}
+\end{frame}
 
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%     
+\begin{frame}[c,fragile]
+\frametitle{Recursion}
 
 \begin{lstlisting}[language=Scala, numbers=none, xleftmargin=-2mm]
 def fib(n: Int) : Int = { 
@@ -646,11 +661,84 @@
   
   \begin{textblock}{14}(2,11.4)
   \large\bf{}Mind-Blowing Programming Languages:\\ 
-  \centering PHP
+  \centering PHP \textcolor{gray}{(7.0)}
   \end{textblock}
   \end{frame}
   %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%     
+
+\begin{frame}[c]
+\frametitle{Jumping Towers}
+
+\begin{center}
+\begin{tikzpicture}[scale=1.2]
+  \draw[line width=1mm,cap=round] (0,0) -- (5,0);
+  \draw[line width=1mm,cap=round] (0,1) -- (5,1);
+
+  \draw[line width=1mm,cap=round] (0,0) -- (0,1);
+  \node at (0.5,0.5) {\textbf{\Large 3}};
+
+  \draw[line width=1mm,cap=round] (1,0) -- (1,1);
+  \node at (1.5,0.5) {\textbf{\Large 4}};
+
+  \draw[line width=1mm,cap=round] (2,0) -- (2,1);
+  \node at (2.5,0.5) {\textbf{\Large 2}};
+
+  \draw[line width=1mm,cap=round] (3,0) -- (3,1);
+  \node at (3.5,0.5) {\textbf{\Large 0}};
+  
+  \draw[line width=1mm,cap=round] (4,0) -- (4,1);
+
+  \node at (4.5,0.5) {\textbf{\Large 1}};
+  
+  \draw[line width=1mm,cap=round] (5,0) -- (5,1);
+
+  \draw[->,line width=0.5mm,cap=round,out=90,in=90,relative] (0.5,1) to (1.5,1);
+  \draw[->,line width=0.5mm,cap=round,out=90,in=90,relative] (0.5,1) to (2.5,1);
+  \draw[->,line width=0.5mm,cap=round,out=90,in=90,relative] (0.5,1) to (3.5,1);
+
+  \draw[->,line width=0.5mm,cap=round,out=-90,in=-90,relative] (2.5,0) to (3.5,0);
+  \draw[->,line width=0.5mm,cap=round,out=-90,in=-90,relative] (2.5,0) to (4.5,0);
+
+  \draw[->,line width=0.5mm,cap=round,out=90,in=90,relative] (4.5,1) to (5.7,1);
+  \node at (5.7, 0.8) {End};
+\end{tikzpicture}
+\end{center}\bigskip
+
+
+shortest: 3 $\rightarrow$ 4 $\rightarrow$ End
+
+\end{frame}
+
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%     
+
+\begin{frame}[c]
+\frametitle{``Children'' / moves}
+
+\begin{center}
+  \begin{tikzpicture}
+    [grow=right,level distance=30mm,child anchor=north,line width=0.5mm]
+  \node {$[3,4,2,0,1]$}
+     child {node {$[0,1]$}}
+     child {node {$[2,0,1]$}
+        child {node {$[1]$} child [level distance=13mm] {node {End}}}
+        child {node {$[0,1]$}}
+     }
+     child {node {$[4,2,0,1]$\ldots}};
+\end{tikzpicture}
+\end{center}
+
+
+
+\end{frame}
+
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 
 \end{document}