\documentclass{article}[11pt]

\usepackage{../style}

\usepackage{../graphics}

\usepackage{disclaimer}

\begin{document}

\section*{Resit Exam}

The Scala part of the exam is worth 30\%. 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: 8\%]

\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: 10\%]}

\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: 12\%]}

\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: