# HG changeset patch # User Christian Urban # Date 1605573295 0 # Node ID 1bde878ba6c99f28585a2ee20a9e572602e89fe9 # Parent f88b5cec2e5dfbf8a323607a44a1fee4f8bb7da2 updated diff -r f88b5cec2e5d -r 1bde878ba6c9 pre_testing1/collatz.scala --- a/pre_testing1/collatz.scala Sun Nov 15 13:10:43 2020 +0000 +++ b/pre_testing1/collatz.scala Tue Nov 17 00:34:55 2020 +0000 @@ -1,50 +1,54 @@ -// Basic Part about the 3n+1 conjecture -//================================== - -// generate jar with -// > scala -d collatz.jar collatz.scala +object CW6a { -object CW6a { // for purposes of generating a jar +//(1) Complete the collatz function below. It should +// recursively calculate the number of steps needed +// until the collatz series reaches the number 1. +// If needed, you can use an auxiliary function that +// performs the recursion. The function should expect +// arguments in the range of 1 to 1 Million. -def collatz(n: Long): Long = - if (n == 1) 0 else - if (n % 2 == 0) 1 + collatz(n / 2) else - 1 + collatz(3 * n + 1) +def collatz(n: Long) : Long = + if ( n == 1) 1; + else if (n % 2 == 0) 1 + collatz( n / 2); + else 1 + collatz( n * 3 + 1); -def collatz_max(bnd: Long): (Long, Long) = { - val all = for (i <- (1L to bnd)) yield (collatz(i), i) - all.maxBy(_._1) -} +//(2) Complete the collatz_max function below. It should +// calculate how many steps are needed for each number +// from 1 up to a bound and then calculate the maximum number of +// steps and the corresponding number that needs that many +// steps. Again, you should expect bounds in the range of 1 +// up to 1 Million. The first component of the pair is +// the maximum number of steps and the second is the +// corresponding number. -//collatz_max(1000000) -//collatz_max(10000000) -//collatz_max(100000000) - -/* some test cases -val bnds = List(10, 100, 1000, 10000, 100000, 1000000) +def collatz_max(bnd: Long) : (Long, Long) = + ((1.toLong to bnd).toList.map + (n => collatz(n)).max , + (1.toLong to bnd).toList.map + (n => collatz(n)).indexOf((1.toLong to bnd).toList.map + (n => collatz(n)).max) + 1); -for (bnd <- bnds) { - val (steps, max) = collatz_max(bnd) - println(s"In the range of 1 - ${bnd} the number ${max} needs the maximum steps of ${steps}") -} - -*/ +//(3) Implement a function that calculates the last_odd +// number in a collatz series. For this implement an +// is_pow_of_two function which tests whether a number +// is a power of two. The function is_hard calculates +// whether 3n + 1 is a power of two. Again you can +// assume the input ranges between 1 and 1 Million, +// and also assume that the input of last_odd will not +// be a power of 2. +//idk + def is_pow_of_two(n: Long) : Boolean = + if ( n & ( n - 1) == 0) true; + else false; -def is_pow(n: Long) : Boolean = (n & (n - 1)) == 0 - -def is_hard(n: Long) : Boolean = is_pow(3 * n + 1) - -def last_odd(n: Long) : Long = - if (is_hard(n)) n else - if (n % 2 == 0) last_odd(n / 2) else - last_odd(3 * n + 1) +def is_hard(n: Long) : Boolean = + if ( (3*n + 1) & 3*n == 0) true; + else false; -//for (i <- 130 to 10000) println(s"$i: ${last_odd(i)}") -//for (i <- 1 to 100) println(s"$i: ${collatz(i)}") - -} +def last_odd(n: Long) : Long = ??? +} diff -r f88b5cec2e5d -r 1bde878ba6c9 progs/lecture2.scala --- a/progs/lecture2.scala Sun Nov 15 13:10:43 2020 +0000 +++ b/progs/lecture2.scala Tue Nov 17 00:34:55 2020 +0000 @@ -210,28 +210,34 @@ def odd(x: Int) : Boolean = x % 2 == 1 val lst = (1 to 10).toList -lst.reverse.sorted - lst.filter(even) lst.count(odd) lst.find(even) lst.exists(even) +lst.find(_ < 4) lst.filter(_ < 4) -lst.filter(x => x % 2 == 1) + +def less4(x: Int) : Boolean = x < 4 +lst.find(less4) +lst.find(_ < 4) + +lst.filter(x => x % 2 == 0) lst.filter(_ % 2 == 0) -lst.sortWith((x, y) => x > y) -lst.sortWith(_ < _) +lst.sortWith((x, y) => x < y) +lst.sortWith(_ > _) // but this only works when the arguments are clear, but // not with multiple occurences lst.find(n => odd(n) && n > 2) -val ps = List((3, 0), (3, 2), (4, 2), (2, 2), (2, 0), (1, 1), (1, 0)) + +val ps = List((3, 0), (3, 2), (4, 2), (2, 2), + (2, 0), (1, 1), (1, 0)) def lex(x: (Int, Int), y: (Int, Int)) : Boolean = if (x._1 == y._1) x._2 < y._2 else x._1 < y._1 @@ -251,12 +257,26 @@ def double(x: Int): Int = x + x def square(x: Int): Int = x * x - val lst = (1 to 10).toList +lst.map(square) lst.map(x => (double(x), square(x))) -lst.map(square) +// works also for strings +def tweet(c: Char) = c.toUpper + +"Hello World".map(tweet) + + +// this can be iterated + +lst.map(square).filter(_ > 4) + +(lst.map(square) + .find(_ > 4) + .map(square)) + +lst.map(square).find(_ > 4) // this is actually how for-comprehensions are // defined in Scala @@ -264,20 +284,10 @@ lst.map(n => square(n)) for (n <- lst) yield square(n) -// this can be iterated - -lst.map(square).filter(_ > 4) - -(lst.map(square) - .filter(_ > 4) - .map(square)) - - // lets define our own higher-order functions // type of functions is for example Int => Int - def my_map_int(lst: List[Int], f: Int => Int) : List[Int] = { if (lst == Nil) Nil else f(lst.head) :: my_map_int(lst.tail, f) @@ -290,10 +300,10 @@ // of switch statement on steroids (see more later on) 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) -} + lst match { + case Nil => Nil + case x::xs => f(x)::my_map_int(xs, f) + } // other function types @@ -693,16 +703,16 @@ /* * 1 - * / | \ - * / | \ - * / | \ - * 2 3 8 - * / \ / \ / \ - * 4 5 6 7 9 10 - * Preorder: 1,2,4,5,3,6,7,8,9,10 - * InOrder: 4,2,5,1,6,3,7,9,8,10 - * PostOrder: 4,5,2,6,7,3,9,10,8,1 - * + * / | \ + * / | \ + * / | \ + * 2 3 8 + * / \ / \ / \ + * 4 5 6 7 9 10 + * Preorder: 1,2,4,5,3,6,7,8,9,10 + * InOrder: 4,2,5,1,6,3,7,9,8,10 + * PostOrder: 4,5,2,6,7,3,9,10,8,1 + * show inorder, preorder, postorder diff -r f88b5cec2e5d -r 1bde878ba6c9 slides/slides02.pdf Binary file slides/slides02.pdf has changed diff -r f88b5cec2e5d -r 1bde878ba6c9 slides/slides02.tex --- a/slides/slides02.tex Sun Nov 15 13:10:43 2020 +0000 +++ b/slides/slides02.tex Tue Nov 17 00:34:55 2020 +0000 @@ -58,105 +58,105 @@ %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\begin{frame}[t,fragile] -\frametitle{For-Comprehensions} +% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +% \begin{frame}[t,fragile] +% \frametitle{For-Comprehensions} -%\small -\begin{lstlisting}[language=Scala,numbers=none] -for (n <- List(1, 2, 3, 4, 5)) yield n * n -\end{lstlisting} +% %\small +% \begin{lstlisting}[language=Scala,numbers=none] +% for (n <- List(1, 2, 3, 4, 5)) yield n * n +% \end{lstlisting} -\begin{textblock}{5}(2,6) -\includegraphics[scale=0.3]{../pics/fun.png} -\end{textblock} +% \begin{textblock}{5}(2,6) +% \includegraphics[scale=0.3]{../pics/fun.png} +% \end{textblock} -\begin{textblock}{5}(9,6) -\includegraphics[scale=0.3]{../pics/fun.png} -\end{textblock} +% \begin{textblock}{5}(9,6) +% \includegraphics[scale=0.3]{../pics/fun.png} +% \end{textblock} -\end{frame} +% \end{frame} -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\begin{frame}[t] -\frametitle{For-Comprehensions} +% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +% \begin{frame}[t] +% \frametitle{For-Comprehensions} -\begin{center} - \begin{tikzpicture}[scale=1, - node/.style={ - rectangle,rounded corners=3mm, - very thick,draw=black!50, - minimum height=18mm, minimum width=20mm, - top color=white,bottom color=black!20}] +% \begin{center} +% \begin{tikzpicture}[scale=1, +% node/.style={ +% rectangle,rounded corners=3mm, +% very thick,draw=black!50, +% minimum height=18mm, minimum width=20mm, +% top color=white,bottom color=black!20}] - \node (A0) at (0.1,0) {\texttt{\textcolor{purple}{\textbf{for}} (\alert<2->{n} <- List(}}; - \node (A1) at (2.3,0) {\texttt{\phantom{,}1,}}; - \node (A2) at (3.2,0) {\texttt{\phantom{,}2,}}; - \node (A3) at (4.1,0) {\texttt{\phantom{,}3,}}; - \node (A4) at (5.0,0) {\texttt{\phantom{,}4,}}; - \node (A5) at (5.9,0) {\texttt{\phantom{))}5))}}; - \node (A6) at (8,0) {\texttt{\textcolor{purple}{\textbf{yield}} \alert<2->{n\,*\,n}}}; +% \node (A0) at (0.1,0) {\texttt{\textcolor{purple}{\textbf{for}} (\alert<2->{n} <- List(}}; +% \node (A1) at (2.3,0) {\texttt{\phantom{,}1,}}; +% \node (A2) at (3.2,0) {\texttt{\phantom{,}2,}}; +% \node (A3) at (4.1,0) {\texttt{\phantom{,}3,}}; +% \node (A4) at (5.0,0) {\texttt{\phantom{,}4,}}; +% \node (A5) at (5.9,0) {\texttt{\phantom{))}5))}}; +% \node (A6) at (8,0) {\texttt{\textcolor{purple}{\textbf{yield}} \alert<2->{n\,*\,n}}}; - \onslide<2->{ - \node (B0) at (1.4,-3) {\texttt{List(}}; - \node (B1) at (2.3,-3) {\texttt{\phantom{,}1,}}; - \node (B2) at (3.6,-3) {\texttt{\phantom{,}4,}}; - \node (B3) at (4.9,-3) {\texttt{\phantom{,}9,}}; - \node (B4) at (6.2,-3) {\texttt{\phantom{,}16,}}; - \node (B5) at (7.5,-3) {\texttt{\phantom{,}25)}};} +% \onslide<2->{ +% \node (B0) at (1.4,-3) {\texttt{List(}}; +% \node (B1) at (2.3,-3) {\texttt{\phantom{,}1,}}; +% \node (B2) at (3.6,-3) {\texttt{\phantom{,}4,}}; +% \node (B3) at (4.9,-3) {\texttt{\phantom{,}9,}}; +% \node (B4) at (6.2,-3) {\texttt{\phantom{,}16,}}; +% \node (B5) at (7.5,-3) {\texttt{\phantom{,}25)}};} - \onslide<2->{ - \draw [->,line width=1mm] (A1.south) -- (B1.north); - \draw [->,line width=1mm] (A2.south) -- (B2.north); - \draw [->,line width=1mm] (A3.south) -- (B3.north); - \draw [->,line width=1mm] (A4.south) -- (B4.north); - \draw [->,line width=1mm] (A5.south) -- (B5.north);} +% \onslide<2->{ +% \draw [->,line width=1mm] (A1.south) -- (B1.north); +% \draw [->,line width=1mm] (A2.south) -- (B2.north); +% \draw [->,line width=1mm] (A3.south) -- (B3.north); +% \draw [->,line width=1mm] (A4.south) -- (B4.north); +% \draw [->,line width=1mm] (A5.south) -- (B5.north);} - \onslide<2->{ - \node (Q1) at (-0.45,-0.1) {}; - \node (Q2) at (-0.45,-2.8) {}; - \node (Q3) at (-0.45,-2.95) {\alert<2->{\texttt{n\,*\,n:}}}; - \draw [->,red,line width=1mm] (Q1.south) -- (Q2.north);} - \end{tikzpicture} -\end{center} +% \onslide<2->{ +% \node (Q1) at (-0.45,-0.1) {}; +% \node (Q2) at (-0.45,-2.8) {}; +% \node (Q3) at (-0.45,-2.95) {\alert<2->{\texttt{n\,*\,n:}}}; +% \draw [->,red,line width=1mm] (Q1.south) -- (Q2.north);} +% \end{tikzpicture} +% \end{center} -\onslide<3>{This is for when the for-comprehension\\ \textbf{yields / produces} a result.} +% \onslide<3>{This is for when the for-comprehension\\ \textbf{yields / produces} a result.} -\end{frame} -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +% \end{frame} +% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\begin{frame}[t] -\frametitle{For-Comprehensions Again} +% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +% \begin{frame}[t] +% \frametitle{For-Comprehensions Again} -\begin{center} - \begin{tikzpicture}[scale=1, - node/.style={ - rectangle,rounded corners=3mm, - very thick,draw=black!50, - minimum height=18mm, minimum width=20mm, - top color=white,bottom color=black!20}] +% \begin{center} +% \begin{tikzpicture}[scale=1, +% node/.style={ +% rectangle,rounded corners=3mm, +% very thick,draw=black!50, +% minimum height=18mm, minimum width=20mm, +% top color=white,bottom color=black!20}] - \node (A0) at (0,0) - {\texttt{\textcolor{purple}{\textbf{for}} (n <- List(1, 2, 3, 4, 5)) - \textcolor{purple}{\textbf{yield}} n\,*\,n}}; +% \node (A0) at (0,0) +% {\texttt{\textcolor{purple}{\textbf{for}} (n <- List(1, 2, 3, 4, 5)) +% \textcolor{purple}{\textbf{yield}} n\,*\,n}}; - \node (A1) at (0,-1.5) {\LARGE\textbf{vs}}; +% \node (A1) at (0,-1.5) {\LARGE\textbf{vs}}; - \node (A2) at (0,-3) - {\texttt{\textcolor{purple}{\textbf{for}} (n <- List(1, 2, 3, 4, 5)) println(n)}}; - \end{tikzpicture} -\end{center}\bigskip +% \node (A2) at (0,-3) +% {\texttt{\textcolor{purple}{\textbf{for}} (n <- List(1, 2, 3, 4, 5)) println(n)}}; +% \end{tikzpicture} +% \end{center}\bigskip -The second version is in case the for \textbf{does not} -produce any result. +% The second version is in case the for \textbf{does not} +% produce any result. -\end{frame} -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +% \end{frame} +% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% @@ -236,7 +236,7 @@ List(7,2,3,4,5,6).find(_ < 4) \end{lstlisting} -\UParrow{1}{10}{11} +\UParrow{1}{8}{11} \end{frame} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% @@ -260,6 +260,26 @@ \end{frame} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +\begin{frame}[c,fragile] +\frametitle{Anonymous Functions} + + +\begin{lstlisting}[language=Scala, numbers=none, xleftmargin=1mm] +def less4(x: Int) = x < 4 +\end{lstlisting} + +\begin{center} +vs +\end{center} + +\begin{lstlisting}[language=Scala, numbers=none, xleftmargin=1mm] + (x: Int) => x < 4 +\end{lstlisting} + +\end{frame} +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{frame}[c,fragile]