diff -r 20f02c5ff53f -r a2c4c6bf319d cws/cw06.tex --- a/cws/cw06.tex Fri Apr 26 17:29:30 2024 +0100 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,164 +0,0 @@ -\documentclass{article}[11pt] -\usepackage{../style} -\usepackage{../graphics} -\usepackage{disclaimer} - -\begin{document} - -\section*{Resit Exam} - -The Scala part of the exam is worth 50\%. It is about `jumps' -within lists. - -\IMPORTANTEXAM{} - -\DISCLAIMEREXAM{} - -%%\newpage - -\subsection*{Task} - -\noindent -Suppose you are given a list of numbers. Each number indicates how many -steps can be taken forward from this element. For example in the -list - -\begin{center} -\begin{tikzpicture}[scale=0.8] - \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} - -\noindent -the first 3 indicates that you can step to the next three elements, -that is 4, 2, and 0. The 2 in the middle indicates that you can step -to elements 0 and 1. From the final 1 you can step to the End of the -list. You can also do this from element 4, since the end of this list -is reachable from there. A 0 always indicates that you cannot -step any further from this element.\medskip - -\noindent -The problem is to calculate a sequence of steps to reach the end of -the list by taking only steps indicated by the integers. For the list -above, possible sequences of steps are 3 - 2 - 1 - End, but also 3 - 4 -- End. This is a recursive problem that can be thought of as a tree -where the root is a list and the children are all the lists that are -reachable by a single step. For example for the list above this gives a -tree like - -\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} - -\subsubsection*{Tasks} - -\begin{itemize} -\item[(1)] Write a function, called \texttt{steps}, that calculates - the children of a list. This function takes an integer as one argument - indicating how many children should be returned. The other argument is a list - of integers. In case of 3 and the list [4,2,0,1], it should produce - the list - - \begin{center} - {\large[}\;[4,2,0,1],\; [2,0,1],\; [0,1]\;{\large]} - \end{center} - - Be careful to account properly for the end of the list. For example - for the integer 4 and the list [2,0,1], the function should return the list - - \begin{center} - {\large[}\;[2,0,1], [0,1],\; [1]\;{\large]} - \end{center} - - - \mbox{}\hfill[Marks: 12\%] - -\item[(2)] Write a function \texttt{search} that tests whether there - is a way to reach the end of a list. This is not always the - case, for example for the list - - \begin{center} - [3,5,1,0,0,0,0,0,0,0,0,1] - \end{center} - - \noindent - there is no sequence of steps that can bring you to the end of the list. - If there is a way, \texttt{search} should return true, otherwise false. - In case of the empty list, \texttt{search} should return true since the - end of the list is already reached. - - \mbox{}\hfill\mbox{[Marks: 18\%]} - -\item[(3)] Write a function \texttt{jumps} that calculates the - shortest sequence of steps needed to reach the end of a list. One - way to calculate this is to generate \emph{all} sequences to reach - the end of a list and then select one that has the shortest length. - This function needs to return a value of type - \texttt{Option[List[Int]]} because for some lists there does not - exists a sequence at all. If there exists such a sequence, - \texttt{jumps} should return \texttt{Some(\ldots)}; otherwise - \texttt{None}. In the special case of the empty list, \texttt{jumps} - should return \texttt{None} - - \mbox{}\hfill\mbox{[Marks: 20\%]} - -\end{itemize}\bigskip - - -\noindent -\textbf{Hints:} useful list functions: \texttt{.minBy(..)} searches for -the first element in a list that is the minimum according to -a given measure; \texttt{.length} calculates the length of a list; -\texttt{.exists(..)} returns true when an element in a list -satisfies a given predicate, otherwise returns false; -\texttt{.map(..)} applies a given function to each element -in a list; \texttt{.flatten} turns a list of -lists into just a list; \texttt{\_::\_} puts an element on the head of -the list. - - -\end{document} - - -%%% Local Variables: -%%% mode: latex -%%% TeX-master: t -%%% End: