1 \documentclass{article}[11pt]

     2 \usepackage{../style}

     3 \usepackage{../graphics}

     4 \usepackage{disclaimer}

     5 

     6 \begin{document}

     7 

     8 \section*{Resit Exam}

     9 

    10 The Scala part of the exam is worth 30\%. It is about `jumps'

    11 within lists.

    12 

    13 \IMPORTANTEXAM{}

    14 

    15 \DISCLAIMEREXAM{}

    16  

    17 %%\newpage

    18 

    19 \subsection*{Task}

    20 

    21 \noindent

    22 Suppose you are given a list of numbers. Each number indicates how many

    23 steps can be taken forward from this element. For example in the

    24 list 

    25 

    26 \begin{center}

    27 \begin{tikzpicture}[scale=0.8]

    28   \draw[line width=1mm,cap=round] (0,0) -- (5,0);

    29   \draw[line width=1mm,cap=round] (0,1) -- (5,1);

    30 

    31   \draw[line width=1mm,cap=round] (0,0) -- (0,1);

    32   \node at (0.5,0.5) {\textbf{\Large 3}};

    33 

    34   \draw[line width=1mm,cap=round] (1,0) -- (1,1);

    35   \node at (1.5,0.5) {\textbf{\Large 4}};

    36 

    37   \draw[line width=1mm,cap=round] (2,0) -- (2,1);

    38   \node at (2.5,0.5) {\textbf{\Large 2}};

    39 

    40   \draw[line width=1mm,cap=round] (3,0) -- (3,1);

    41   \node at (3.5,0.5) {\textbf{\Large 0}};

    42   

    43   \draw[line width=1mm,cap=round] (4,0) -- (4,1);

    44 

    45   \node at (4.5,0.5) {\textbf{\Large 1}};

    46   

    47   \draw[line width=1mm,cap=round] (5,0) -- (5,1);

    48 

    49   \draw[->,line width=0.5mm,cap=round,out=90,in=90,relative] (0.5,1) to (1.5,1);

    50   \draw[->,line width=0.5mm,cap=round,out=90,in=90,relative] (0.5,1) to (2.5,1);

    51   \draw[->,line width=0.5mm,cap=round,out=90,in=90,relative] (0.5,1) to (3.5,1);

    52 

    53   \draw[->,line width=0.5mm,cap=round,out=-90,in=-90,relative] (2.5,0) to (3.5,0);

    54   \draw[->,line width=0.5mm,cap=round,out=-90,in=-90,relative] (2.5,0) to (4.5,0);

    55 

    56   \draw[->,line width=0.5mm,cap=round,out=90,in=90,relative] (4.5,1) to (5.7,1);

    57   \node at (5.7, 0.8) {End};

    58 \end{tikzpicture}

    59 \end{center}  

    60 

    61 \noindent

    62 the first 3 indicates that you can step to the next three elements,

    63 that is 4, 2, and 0. The 2 in the middle indicates that you can step

    64 to elements 0 and 1.  From the final 1 you can step to the End of the

    65 list. You can also do this from element 4, since the end of this list

    66 is reachable from there. A 0 always indicates that you cannot

    67 step any further from this element.\medskip

    68 

    69 \noindent

    70 The problem is to calculate a sequence of steps to reach the end of

    71 the list by taking only steps indicated by the integers. For the list

    72 above, possible sequence of steps are 3 - 2 - 1 - End, but also 3 - 4

    73 - End.  This is a recursive problem that can be thought of as a tree

    74 where the root is a list and the children are all the lists that are

    75 reachable by a single step. For example for the list above this gives a

    76 tree like

    77 

    78 \begin{center}

    79 \begin{tikzpicture}[grow=right,level distance=30mm,child anchor=north]

    80   \node {[3,4,2,0,1]}

    81      child {node {[0,1]}}

    82      child {node {[2,0,1]}

    83         child {node {[1]} child [level distance=13mm] {node {End}}}

    84         child {node {[0,1]}}

    85      }

    86      child {node {[4,2,0,1]\ldots}};

    87 \end{tikzpicture}

    88 \end{center}

    89 

    90 \subsubsection*{Tasks}

    91 

    92 \begin{itemize}

    93 \item[(1)] Write a function, called \texttt{steps}, that calculates

    94   the children of a list. This function takes an integer as one argument

    95   indicating how many children should be returned. The other argument is a list

    96   of integers.  In case of 3 and the list [4,2,0,1], it should produce

    97   the list

    98 

    99   \begin{center}

   100   {\large[}\;[4,2,0,1],\; [2,0,1],\; [0,1]\;{\large]}

   101   \end{center}  

   102 

   103   Be careful to account properly for the end of the list. For example

   104   for the integer 4 and the list [2,0,1], the function should return the list

   105 

   106   \begin{center}

   107   {\large[}\;[2,0,1], [0,1],\; [1]\;{\large]}

   108   \end{center}  

   109 

   110 

   111   \mbox{}\hfill[Marks: 8\%]

   112  

   113 \item[(2)] Write a function \texttt{search} that tests whether there

   114   is a way to reach the end of a list.  This is not always the

   115   case, for example for the list

   116 

   117   \begin{center}

   118     [3,5,1,0,0,0,0,0,0,0,0,1]

   119   \end{center}

   120 

   121   \noindent

   122   there is no sequence of steps that can bring you to the end of the list.

   123   If there is a way, \texttt{search} should return true, otherwise false.

   124   In case of the empty list, \texttt{search} should return true since the

   125   end of the list is already reached.

   126   

   127   \mbox{}\hfill\mbox{[Marks: 10\%]}

   128 

   129 \item[(3)] Write a function \texttt{jumps} that calculates the

   130   shortest sequence of steps needed to reach the end of a list. One

   131   way to calculate this is to generate \emph{all} sequences to reach

   132   the end of a list and then select one that has the shortest length.

   133   This function needs to return a value of type

   134   \texttt{Option[List[Int]]} because for some lists there does not

   135   exists a sequence at all. If there exists such a sequence,

   136   \texttt{jumps} should return \texttt{Some(\ldots)}; otherwise

   137   \texttt{None}. In the special case of the empty list, \texttt{jumps}

   138   should return \texttt{None}

   139 

   140   \mbox{}\hfill\mbox{[Marks: 12\%]}

   141   

   142 \end{itemize}\bigskip

   143 

   144 

   145 \noindent

   146 \textbf{Hints:} useful list functions: \texttt{.minBy(..)} searches for

   147 the first element in a list that is the minimum according to

   148 a given measure; \texttt{.length} calculates the length of a list;

   149 \texttt{.exists(..)} returns true when an element in a list

   150 satisfies a given predicate, otherwise returns false;

   151 \texttt{.map(..)} applies a given function to each element

   152 in a list; \texttt{.flatten} turns a list of

   153 lists into just a list; \texttt{\_::\_} puts an element on the head of

   154 the list.

   155 

   156 

   157 \end{document}

   158 

   159 

   160 %%% Local Variables: 

   161 %%% mode: latex

   162 %%% TeX-master: t

   163 %%% End: