1 

     2 % !TEX program = xelatex

     3 \documentclass{article}

     4 \usepackage{../styles/style}

     5 \usepackage{disclaimer}

     6 \usepackage{../styles/langs}

     7 \usepackage{graphicx}

     8 

     9 \begin{document}

    10 

    11 

    12 %% should ask to lower case the words.

    13 

    14 \section*{Resit: Evil Wordle Game (Scala, 6 Marks)}

    15 

    16 

    17 \noindent

    18 You are asked to implement a Scala program for making the popular Wordle game as difficult

    19 as possible. The deadline for your submission is on 4th August at 16:00. There will be no

    20 automated tests for the resit, but there are plenty of testcases in the template and the

    21 task description. \bigskip

    22 

    23 \IMPORTANTNONE{}

    24 

    25 \noindent

    26 Also note that the running time of each part will be restricted to a

    27 maximum of 30 seconds on my laptop.

    28 

    29 \DISCLAIMER{}

    30 

    31 \subsection*{Hints}

    32 

    33 \noindent

    34 Useful data functions: \texttt{Source.fromURL},

    35 \texttt{Source.fromFile} for obtaining a webpage and reading a file,

    36 \texttt{.getOrElse(..,..)} allows to query a Map, but also gives a

    37 default value if the Map is not defined, a Map can be `updated' by

    38 using \texttt{+}, \texttt{.contains} and \texttt{.filter} can test whether

    39 an element is included in a list, and respectively filter out elements in a list,

    40 \texttt{.sortBy(\_.\_2)} sorts a list of pairs according to the second

    41 elements in the pairs---the sorting is done from smallest to highest,

    42 \texttt{.groupBy} orders lists according to same elements

    43 .

    44 

    45 

    46 \newpage

    47 

    48 

    49 \subsection*{Resit (6 Marks, file wordle.scala)}

    50 

    51 You probably know the game of Wordle\footnote{\url{https://en.wikipedia.org/wiki/Wordle}}

    52 where you are supposed to guess a five-letter word. The feedback for guesses can help

    53 with the next guess (green letters are correct, orange letters are present, but in the

    54 wrong place). For example:

    55 

    56 \begin{center}

    57 \includegraphics[scale=0.2]{../pics/w.jpeg}

    58 \end{center}  

    59 

    60 \noindent

    61 The idea of the program to be implemented here is to make the Wordle game as evil as possible

    62 by finding words that are the most difficult to guess. A word list of five-letter words is available

    63 from 

    64 

    65 \begin{center}

    66 \begin{tabular}{ll}  

    67   \url{https://nms.kcl.ac.uk/christian.urban/wordle.txt} & (78 KByte)\\

    68 \end{tabular}

    69 \end{center}

    70 

    71 \noindent

    72 In your program you need to download this list and implement some

    73 functions that in the end select the most difficult words (given an

    74 input from the user).  If bandwidth is an issue for you, download the

    75 file locally, but in the submitted version use \texttt{Source.fromURL}

    76 instead of \texttt{Source.fromFile}.

    77 

    78 \subsection*{Tasks}

    79 

    80 \begin{itemize}

    81 \item[(1)] Implement the function \pcode{get_wordle_list} which takes an

    82   URL-string as argument and requests the corresponding file. The function should

    83   return the word list appropriately broken up into lines.

    84   The result should be a list of strings (the lines in the file). In case

    85   the url does not produce a file, return the empty list.\\

    86   \mbox{}\hfill [0.25 Marks]

    87 

    88 \item[(2)] Implement a polymorphic function \pcode{removeN}, which removes $n$ occurences of an

    89   element from a list (if this element is less than $n$ times pressent, then remove all occurences).

    90   For example

    91 

    92 \begin{lstlisting}[numbers=none]

    93 removeN(List(1,2,3,2,1), 3, 2)  => List(1, 2, 2, 1)

    94 removeN(List(1,2,3,2,1), 2, 1)  => List(1, 3, 2, 1)

    95 removeN(List(1,2,3,2,1), 2, 2)  => List(1, 3, 1)

    96 removeN(List(1,2,3,2,1), 1, 1)  => List(2, 3, 2, 1)

    97 removeN(List(1,2,3,2,1), 1, 3)  => List(2, 3, 2)

    98 removeN(List(1,2,3,2,1), 0, 2)  => List(1, 2, 3, 2, 1)

    99 \end{lstlisting}

   100 

   101 Make sure you only remove at most $n$ occurrences of the element from the list.

   102 This function should work for lists of intergers but also lists of chars, strings etc.\\

   103   \mbox{}\hfill [0.25 Marks]

   104 

   105 \item[(3)] Implement a function \pcode{score} that calculates the

   106   feedback for a word against a secret word using the rules of the

   107   Wordle game. The output of \pcode{score} should be a list of 5

   108   elements of type \pcode{Tip} representing three outcomes: a letter

   109   in the correct position, a letter that is present, but not in the

   110   correct position and a letter that is absent. For example given the

   111   secret word "chess" the score for the word "caves" is

   112 

   113 \begin{lstlisting}[numbers=none]

   114 List(Correct, Absent, Absent, Present, Correct)

   115 \end{lstlisting}

   116 

   117   You have to be careful with multiple occurrences of letters. For example

   118   the secret "chess" with the guess "swiss" should produce

   119 

   120 \begin{lstlisting}[numbers=none]

   121 List(Absent, Absent, Absent, Correct, Correct)

   122 \end{lstlisting}

   123 

   124 even though the first 's' in "swiss" is present in the secret word, the 's' are already

   125 `used up' by the two letters that are correct. To implement this you need to

   126 implement first a function \pcode{pool} which calculates all the letters in

   127 a secret that are not correct in a word. For example

   128 

   129 \begin{lstlisting}[numbers=none]

   130   pool("chess", "caves")  => List(h, e, s)

   131   pool("chess", "swiss")  => List(c, h, e)

   132 \end{lstlisting}

   133 

   134   Now the helper function \pcode{aux} can analyse the arguments secret and word recursively letter-by-letter and

   135   decide: if the letters are the same, then return \pcode{Correct} for the corresponding position.

   136   If they are not the same, but the letter is in the pool, then return \pcode{Present} and also remove

   137   this letter from the pool in the next recursive call of \pcode{aux}. Otherwise return \pcode{Absent} for the

   138   corresponding position. The function \pcode{score} is a wrapper for the function \pcode{aux}

   139   calling \pcode{aux} with the appropriate arguments (recall what is calculated with \pcode{pool}).\mbox{}\hfill [1.5 Marks]

   140 

   141 \item[(4)] Implement a function \pcode{eval} that gives an integer value to each of the

   142   \pcode{Tip}s such that

   143 

   144   \begin{center}

   145   \begin{tabular}{lcl}  

   146     \textit{eval (Correct)} & $\dn$ & $10$\\

   147     \textit{eval (Present)} & $\dn$ & $1$\\

   148     \textit{eval (Absent)} & $\dn$ & $0$

   149   \end{tabular}                                   

   150   \end{center}  

   151 

   152   The function \pcode{iscore} then takes an output of \pcode{score} and sums

   153   up all corresponding values. For example for 

   154 

   155 \begin{lstlisting}[numbers=none]

   156   iscore("chess", "caves")  => 21

   157   iscore("chess", "swiss")  => 20

   158 \end{lstlisting}

   159   \mbox{}\hfill [0.5 Marks]

   160 

   161 \item[(5)] The function \pcode{evil} takes a list of secrets (the list from Task 1)

   162   and a word as arguments, and calculates the list of words with the lowest

   163   score (remember we want to make the Wordle game as difficult as possible---therefore

   164   when the user gives us a word, we want to find the secrets that produce the lowest

   165   score). For this implement a helper function \pcode{lowest} that goes through

   166   the secrets one-by-one and calculates the score. The argument \pcode{current} is

   167   the score of the ``currently'' found secrets. When the function \pcode{lowest}

   168   is called for the first time then this will be set to the maximum integer value

   169   \pcode{Int.MaxValue}. The accumulator will be first empty. If a secret is found

   170   with the same score as \pcode{current} then this word is added to the accumulator.

   171   If the secret has a lower score, then the accumulator will be discarded and this

   172   secret will be the new accumulator. If the secret has a higher score, then it can be

   173   ignored. For example \pcode{evil} (the wrapper for \pcode{lowest}) generates

   174 

   175 \begin{lstlisting}[numbers=none]

   176 evil(secrets, "stent").length => 1907

   177 evil(secrets, "hexes").length => 2966

   178 evil(secrets, "horse").length => 1203

   179 evil(secrets, "hoise").length => 971

   180 evil(secrets, "house").length => 1228

   181 \end{lstlisting}

   182 

   183 where \pcode{secrets} is the list generated under Task 1.

   184 In all cases above the iscore of the resulting secrets is 0, but this does not need to be the case

   185 in general.\\

   186   \mbox{}\hfill [1.5 Marks]

   187 

   188 \item[(6)] The secrets generated in Task 5 are the ones with the lowest score

   189   with respect to the word, or the secrets that are furthest ``away'' from the

   190   given word. This is already quite evil for a secret word---remember we can choose

   191   a secret \emph{after} a user has given a first word. Now we want to make it

   192   even more evil by choosing words that have the most obscure letters. For this we

   193   calculate the frequency of how many times certain letters occur in our secrets

   194   list (see Task 1). The \emph{frequency} of the letter $c$, say, is given by the formula

   195 

   196   \begin{center}

   197   $\textit{freq(c)} \dn 1 - \frac{\textit{number of occurrences of c}}{\textit{number of all letters}}$  

   198   \end{center}  

   199 

   200   That means that letters that occur fewer times in our secrets have a higher frequency.

   201   For example the letter 'y' has the frequency 0.9680234350909651 while the much more

   202   often occurring letter 'e' has only 0.897286463151403 (all calculations should be done

   203   with Doubles).

   204 

   205   The function \pcode{frequencies} should calculate the frequencies for all lower-case letters

   206   by generating a Map from letters (\pcode{Char}) to Doubles (frequencies).\\ 

   207   \mbox{}\hfill [1 Mark]

   208 

   209 \item[(7)] In this task we want to use the output of \pcode{evil}, rank each string in the

   210   generated set and then filter out the strings that are ranked highest (the ones with the most obscure letters).

   211   This list of strings often contains only a single word, but in general there might be more (see below).

   212   First implement a function \pcode{rank} that takes a frequency map (from 6) and a string as arguments and

   213   generates a rank by summing up all frequencies of the letters in the string. For example

   214 

   215 \begin{lstlisting}[numbers=none]

   216 rank(frequencies(secrets), "adobe") => 4.673604687018193

   217 rank(frequencies(secrets), "gaffe") => 4.745205057045945

   218 rank(frequencies(secrets), "fuzzy") => 4.898735738513722

   219 \end{lstlisting}

   220 

   221   Finally, implement a function \pcode{ranked_evil} that selects from the output of \pcode{evil}

   222   the string(s) which are highest ranked in evilness.

   223 

   224   

   225 \begin{lstlisting}[numbers=none]

   226 ranked_evil(secrets, "abbey") => List(whizz)

   227 ranked_evil(secrets, "afear") => List(buzzy)

   228 ranked_evil(secrets, "zincy") => List(jugum)

   229 ranked_evil(secrets, "zippy") => List(chuff)

   230 \end{lstlisting}

   231 

   232 This means if the user types in "abbey" then the most evil word to choose as secret is "whizzy" (according to

   233 our calculations). This word has a zero \pcode{iscore} and the most obscure letters.

   234 

   235 %

   236 %\color{red}

   237 %\section*{Correction with \texttt{ranked\_evil}}

   238 %

   239 %The testcases above are actually not the maximum, but the minimum! I will make sure

   240 %that the task will count as solved when either the minimum (as above) or the maximum (as intended)

   241 %is used. The correct solutions for the above testcases using the maximum are:

   242 %\color{black}

   243 %

   244 %\begin{lstlisting}[numbers=none]

   245 %ranked_evil(secrets, "beats") => List(fuzzy)

   246 %ranked_evil(secrets, "vitae") => List(fuzzy)

   247 %ranked_evil(secrets, "bento") => List(fuzzy)

   248 %ranked_evil(secrets, "belts") => List(fuzzy)

   249 %\end{lstlisting}

   250 %

   251 %\noindent \textcolor{red}{Some further testcases for the maximum are:}

   252 %

   253 %\begin{lstlisting}[numbers=none]

   254 %ranked_evil(secrets, "abbey") => List(whizz)

   255 %ranked_evil(secrets, "afear") => List(buzzy)

   256 %ranked_evil(secrets, "zincy") => List(jugum)

   257 %ranked_evil(secrets, "zippy") => List(chuff)

   258 %\end{lstlisting}

   259 % 

   260 %

   261 

   262 \mbox{}\hfill [1 Mark]  

   263 \end{itemize}

   264 

   265 \end{document} 

   266 

   267 %%% Local Variables: 

   268 %%% mode: latex

   269 %%% TeX-master: t

   270 %%% End: 

   271 

   272 

   273