+
−
% !TEX program = xelatex+
−
\documentclass{article}+
−
\usepackage{../styles/style}+
−
\usepackage{disclaimer}+
−
\usepackage{../styles/langs}+
−
\usepackage{graphicx}+
−
+
−
\begin{document}+
−
+
−
+
−
%% should ask to lower case the words.+
−
+
−
\section*{Evil Wordle Game (Scala, 7 Marks)}+
−
+
−
\mbox{}\hfill\textit{``C makes it easy to shoot yourself in the foot; C++ makes it harder,}\\+
−
\mbox{}\hfill\textit{ but when you do, it blows your whole leg off.''}\smallskip\\+
−
\mbox{}\hfill\textit{ --- Bjarne Stroustrup (creator of the C++ language)}\bigskip\bigskip+
−
+
−
+
−
+
−
+
−
\noindent+
−
You are asked to implement a Scala program for making the popular Wordle game as difficult+
−
as possible.\bigskip+
−
+
−
\IMPORTANTNONE{}+
−
+
−
\noindent+
−
Also note that the running time of each part will be restricted to a+
−
maximum of 30 seconds on my laptop.+
−
+
−
\DISCLAIMER{}+
−
+
−
\subsection*{Reference Implementation}+
−
+
−
Like the C++ part, the Scala part works like this: you push your files+
−
to GitHub and receive (after sometimes a long delay) some automated+
−
feedback. In the end we will take a snapshot of the submitted files+
−
and apply an automated marking script to them.\medskip+
−
+
−
\noindent+
−
In addition, the Scala part comes with a reference+
−
implementation in form of \texttt{jar}-files. This allows you to run+
−
any test cases on your own computer. For example you can call \texttt{scala-cli} on+
−
the command line with the option \texttt{--extra-jars wordle.jar} and then+
−
query any function from the template file. Say you want to find out+
−
what the function \texttt{} produces: for this you just need+
−
to prefix it with the object name \texttt{M2}.  If you want to find out what+
−
these functions produce for the list \texttt{List("a", "b", "b")},+
−
you would type something like:+
−
+
−
\begin{lstlisting}[language={},numbers=none,basicstyle=\ttfamily\small]+
−
$ scala-cli --extra-jars wordle.jar+
−
scala> val secretsURL =+
−
     | """https://nms.kcl.ac.uk/christian.urban/wordle.txt"""+
−
+
−
scala> M2.get_wordle_list(secretsURL)+
−
val res0: List[String] = List(aahed, aalii, ...)+
−
\end{lstlisting}%$+
−
+
−
\subsection*{Hints}+
−
+
−
\noindent+
−
Useful data functions: \texttt{Source.fromURL},+
−
\texttt{Source.fromFile} for obtaining a webpage and reading a file,+
−
\texttt{.getOrElse(..,..)} allows to query a Map, but also gives a+
−
default value if the Map is not defined, a Map can be `updated' by+
−
using \texttt{+}, \texttt{.contains} and \texttt{.filter} can test whether+
−
an element is included in a list, and respectively filter out elements in a list,+
−
\texttt{.sortBy(\_.\_2)} sorts a list of pairs according to the second+
−
elements in the pairs---the sorting is done from smallest to highest,+
−
\texttt{.groupBy} orders lists according to same elements+
−
.+
−
+
−
+
−
\newpage+
−
+
−
+
−
\subsection*{Main Part 2 (7 Marks, file wordle.scala)}+
−
+
−
You probably know the game of Wordle\footnote{\url{https://en.wikipedia.org/wiki/Wordle}}+
−
where you are supposed to guess a five-letter word. The feedback for guesses can help+
−
with the next guess (green letters are correct, orange letters are present, but in the+
−
wrong place). For example:+
−
+
−
\begin{center}+
−
\includegraphics[scale=0.2]{../pics/w.jpeg}+
−
\end{center}  +
−
+
−
\noindent+
−
The idea of the program to be implemented here is to make the Wordle game as evil as possible+
−
by finding words that are the most difficult to guess. A word list of five-letter words is available+
−
from +
−
+
−
\begin{center}+
−
\begin{tabular}{ll}  +
−
  \url{https://nms.kcl.ac.uk/christian.urban/wordle.txt} & (78 KByte)\\+
−
\end{tabular}+
−
\end{center}+
−
+
−
\noindent+
−
In your program you need to download this list and implement some+
−
functions that in the end select the most difficult words (given an+
−
input from the user).  If bandwidth is an issue for you, download the+
−
file locally, but in the submitted version use \texttt{Source.fromURL}+
−
instead of \texttt{Source.fromFile}.+
−
+
−
\subsection*{Tasks}+
−
+
−
\begin{itemize}+
−
\item[(1)] Implement the function \pcode{get_wordle_list} which takes an+
−
  URL-string as argument and requests the corresponding file. The function should+
−
  return the word list appropriately broken up into lines.+
−
  The result should be a list of strings (the lines in the file). In case+
−
  the url does not produce a file, return the empty list.+
−
+
−
  In what follows we will use \texttt{secrets} to refer  to the list of words listed+
−
  in \texttt{wordle.txt}.\\  +
−
  \mbox{}\hfill [0.5 Marks]+
−
+
−
\item[(2)] Implement a polymorphic function \pcode{removeN}, which removes $n$ occurrences of an+
−
  element from a list (if this element is less than $n$ times present, then remove all occurrences).+
−
  For example+
−
+
−
\begin{lstlisting}[numbers=none]+
−
removeN(List(1,2,3,2,1), 3, 2)  => List(1, 2, 2, 1)+
−
removeN(List(1,2,3,2,1), 2, 1)  => List(1, 3, 2, 1)+
−
removeN(List(1,2,3,2,1), 2, 2)  => List(1, 3, 1)+
−
removeN(List(1,2,3,2,1), 1, 1)  => List(2, 3, 2, 1)+
−
removeN(List(1,2,3,2,1), 1, 3)  => List(2, 3, 2)+
−
removeN(List(1,2,3,2,1), 0, 2)  => List(1, 2, 3, 2, 1)+
−
\end{lstlisting}+
−
+
−
Make sure you only remove at most $n$ occurrences of the element from the list.+
−
This function should work for lists of integers but also lists of chars, strings etc.\\+
−
  \mbox{}\hfill [0.5 Marks]+
−
+
−
\item[(3)] Implement a function \pcode{score} that calculates the+
−
  feedback for a word against a secret word using the rules of the+
−
  Wordle game. The output of \pcode{score} should be a list of 5+
−
  elements of type \pcode{Tip} representing three outcomes: a letter+
−
  in the correct position, a letter that is present, but not in the+
−
  correct position and a letter that is absent. For example given the+
−
  secret word "chess" the score for the word "caves" is+
−
+
−
\begin{lstlisting}[numbers=none]+
−
List(Correct, Absent, Absent, Present, Correct)+
−
\end{lstlisting}+
−
+
−
  You have to be careful with multiple occurrences of letters. For example+
−
  the secret "chess" with the guess "swiss" should produce+
−
+
−
\begin{lstlisting}[numbers=none]+
−
List(Absent, Absent, Absent, Correct, Correct)+
−
\end{lstlisting}+
−
+
−
even though the first 's' in "swiss" is present in the secret word, the 's' are already+
−
`used up' by the two letters that are correct. To implement this you need to+
−
implement first a function \pcode{pool} which calculates all the letters in+
−
a secret that are not correct in a word. For example+
−
+
−
\begin{lstlisting}[numbers=none]+
−
  pool("chess", "caves")  => List(h, e, s)+
−
  pool("chess", "swiss")  => List(c, h, e)+
−
\end{lstlisting}+
−
+
−
  Now the helper function \pcode{aux} can analyse the arguments secret and word recursively letter-by-letter and+
−
  decide: if the letters are the same, then return \pcode{Correct} for the corresponding position.+
−
  If they are not the same, but the letter is in the pool, then return \pcode{Present} and also remove+
−
  this letter from the pool in the next recursive call of \pcode{aux}. Otherwise return \pcode{Absent} for the+
−
  corresponding position. The function \pcode{score} is a wrapper for the function \pcode{aux}+
−
  calling \pcode{aux} with the appropriate arguments (recall what is calculated with \pcode{pool}).\mbox{}\hfill [2 Marks]+
−
+
−
\item[(4)] Implement a function \pcode{eval} that gives an integer value to each of the+
−
  \pcode{Tip}s such that+
−
+
−
  \begin{center}+
−
  \begin{tabular}{lcl}  +
−
    \textit{eval (Correct)} & $\dn$ & $10$\\+
−
    \textit{eval (Present)} & $\dn$ & $1$\\+
−
    \textit{eval (Absent)} & $\dn$ & $0$+
−
  \end{tabular}                                   +
−
  \end{center}  +
−
+
−
  The function \pcode{iscore} then takes an output of \pcode{score} and sums+
−
  up all corresponding values. For example for +
−
+
−
\begin{lstlisting}[numbers=none]+
−
  iscore("chess", "caves")  => 21+
−
  iscore("chess", "swiss")  => 20+
−
\end{lstlisting}+
−
  \mbox{}\hfill [0.5 Marks]+
−
+
−
\item[(5)] The function \pcode{evil} takes a list of secrets (the list from Task 1)+
−
  and a word as arguments, and calculates the list of words with the lowest+
−
  score (remember we want to make the Wordle game as difficult as possible---therefore+
−
  when the user gives us a word, we want to find the secrets that produce the lowest+
−
  score). For this implement a helper function \pcode{lowest} that goes through+
−
  the secrets one-by-one and calculates the score. The argument \pcode{current} is+
−
  the score of the ``currently'' found secrets. When the function \pcode{lowest}+
−
  is called for the first time then this will be set to the maximum integer value+
−
  \pcode{Int.MaxValue}. The accumulator will be first empty. If a secret is found+
−
  with the same score as \pcode{current} then this word is added to the accumulator.+
−
  If the secret has a lower score, then the accumulator will be discarded and this+
−
  secret will be the new accumulator. If the secret has a higher score, then it can be+
−
  ignored. For example \pcode{evil} (the wrapper for \pcode{lowest}) generates+
−
+
−
\begin{lstlisting}[numbers=none]+
−
evil(secrets, "stent").length => 1907+
−
evil(secrets, "hexes").length => 2966+
−
evil(secrets, "horse").length => 1203+
−
evil(secrets, "hoise").length => 971+
−
evil(secrets, "house").length => 1228+
−
\end{lstlisting}+
−
+
−
where \pcode{secrets} is the list generated under Task 1.+
−
In all cases above the iscore of the resulting secrets is 0, but this does not need to be the case+
−
in general.\\+
−
\mbox{}\hfill [1.5 Marks]+
−
+
−
\item[(6)] The secrets generated in Task 5 are the ones with the lowest score+
−
  with respect to the word. You can think of these as the secrets that are furthest ``away'' from the+
−
  given word. This is already quite evil for a secret word---remember we can choose+
−
  a secret \emph{after} a user has given a first word. Now we want to make it+
−
  even more evil by choosing words that have the most obscure letters. For this we+
−
  calculate the frequency of how many times certain letters occur in our secrets+
−
  list (see Task 1). The \emph{frequency} of the letter $c$, say, is given by the formula+
−
+
−
  \begin{center}+
−
  $\textit{freq(c)} \dn 1 - \frac{\textit{number of occurrences of c}}{\textit{number of all letters}}$  +
−
  \end{center}  +
−
+
−
  That means that letters that occur fewer times in our secrets have a higher frequency.+
−
  For example the letter 'y' has the frequency 0.9680234350909651 while the much more+
−
  often occurring letter 'e' has only 0.897286463151403 (all calculations should be done+
−
  with Doubles).+
−
+
−
  The function \pcode{frequencies} should calculate the frequencies for all lower-case letters+
−
  by generating a Map from letters (\pcode{Char}) to Doubles (frequencies).\\ +
−
  \mbox{}\hfill [1 Mark]+
−
+
−
\item[(7)] In this task we want to use the output of \pcode{evil}, rank each string in the+
−
  generated set and then filter out the strings that are ranked highest (the ones with the most obscure letters).+
−
  This list of strings often contains only a single word, but in general there might be more (see below).+
−
  First implement a function \pcode{rank} that takes a frequency map (from 6) and a string as arguments.+
−
  In the testcases, the frequency map is generated for all words in \texttt{secrets}, that is the+
−
  whole list in \texttt{wordle.txt}. The function  +
−
  generates a rank by summing up all frequencies of the letters in the string. For example+
−
+
−
\begin{lstlisting}[numbers=none]+
−
rank(frequencies(secrets), "adobe") => 4.673604687018193+
−
rank(frequencies(secrets), "gaffe") => 4.745205057045945+
−
rank(frequencies(secrets), "fuzzy") => 4.898735738513722+
−
\end{lstlisting}+
−
+
−
+
−
  Finally, implement a function \pcode{ranked_evil} that selects from the output of \pcode{evil}+
−
  the string(s) which are highest ranked in evilness.+
−
+
−
  +
−
\begin{lstlisting}[numbers=none]+
−
ranked_evil(secrets, "abbey") => List(whizz)+
−
ranked_evil(secrets, "afear") => List(buzzy)+
−
ranked_evil(secrets, "zincy") => List(jugum)+
−
ranked_evil(secrets, "zippy") => List(chuff)+
−
\end{lstlisting}+
−
+
−
This means if the user types in "abbey" then the most evil word to choose as secret is ``whizz'' (according to+
−
our calculations). This word has a zero \pcode{iscore} and the most obscure letters.+
−
+
−
%+
−
%\color{red}+
−
%\section*{Correction with \texttt{ranked\_evil}}+
−
%+
−
%The testcases above are actually not the maximum, but the minimum! I will make sure+
−
%that the task will count as solved when either the minimum (as above) or the maximum (as intended)+
−
%is used. The correct solutions for the above testcases using the maximum are:+
−
%\color{black}+
−
%+
−
%\begin{lstlisting}[numbers=none]+
−
%ranked_evil(secrets, "beats") => List(fuzzy)+
−
%ranked_evil(secrets, "vitae") => List(fuzzy)+
−
%ranked_evil(secrets, "bento") => List(fuzzy)+
−
%ranked_evil(secrets, "belts") => List(fuzzy)+
−
%\end{lstlisting}+
−
%+
−
%\noindent \textcolor{red}{Some further testcases for the maximum are:}+
−
%+
−
%\begin{lstlisting}[numbers=none]+
−
%ranked_evil(secrets, "abbey") => List(whizz)+
−
%ranked_evil(secrets, "afear") => List(buzzy)+
−
%ranked_evil(secrets, "zincy") => List(jugum)+
−
%ranked_evil(secrets, "zippy") => List(chuff)+
−
%\end{lstlisting}+
−
% +
−
%+
−
+
−
\mbox{}\hfill [1 Mark]  +
−
\end{itemize}+
−
+
−
\end{document} +
−
+
−
%%% Local Variables: +
−
%%% mode: latex+
−
%%% TeX-master: t+
−
%%% End: +
−
+
−
+
−
+
−