% !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 reference

implementations in form of \texttt{jar}-files. This allows you to run

any test cases on your own computer. For example you can call Scala on

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 -cp 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

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.

  \textcolor{red}{

    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.

\color{red}

  Note that the template gives as type for \texttt{evil}:

  \begin{center}

  \texttt{def evil(secrets: List[String], word: String) = ???}  

  \end{center}

  where the return type is left unspecified. This return type is not needed when

  functions are not recursive---\texttt{evil} is meant to be just a wrapper that

  calls \texttt{lowest} with appropriate default arguments and returns whatever

  \texttt{lowest} returns. Therefore a return type is not needed. But a slightly

  more accurate template definition for \texttt{evil} is:\medskip\medskip

  \begin{minipage}{1.05\textwidth}

  \begin{center}

  \texttt{def evil(secrets: List[String], word: String) : List[String] = ???}  

  \end{center}

  \end{minipage}\medskip\medskip

  where also the return type is explicitly given.\\\color{black}

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

  \textcolor{red}{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}

  \color{red}

  The return type for \texttt{rank} is \texttt{Double}:

  \begin{center}

  \texttt{def rank(frqs: Map[Char, Double], s: String) : Double = ???}  

  \end{center}

  \color{black}

  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}

  The return type for \texttt{ranked\_evil} is \texttt{List[String]}:

  \begin{center}

  \texttt{def ranked\_evil(secrets: List[String], word: String) : List[String] = ???}  

  \end{center}

  \color{black}

%

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