--- a/cws/main_cw02.tex Sat Oct 08 00:30:51 2022 +0100
+++ b/cws/main_cw02.tex Tue Nov 01 15:03:48 2022 +0000
@@ -4,13 +4,14 @@
\usepackage{../styles/style}
\usepackage{disclaimer}
\usepackage{../styles/langs}
+\usepackage{graphicx}
\begin{document}
%% should ask to lower case the words.
-\section*{Main Part 2 (Scala, 6 Marks)}
+\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\\
@@ -20,8 +21,8 @@
\noindent
-You are asked to implement a Scala program for recommending movies
-according to a ratings list.\bigskip
+You are asked to implement a Scala program for making the popular Wordle game as difficult
+as possible.\bigskip
\IMPORTANTNONE{}
@@ -31,7 +32,6 @@
\DISCLAIMER{}
-
\subsection*{Reference Implementation}
Like the C++ part, the Scala part works like this: you push your files
@@ -51,163 +51,246 @@
you would type something like:
\begin{lstlisting}[language={},numbers=none,basicstyle=\ttfamily\small]
-$ scala -cp danube.jar
-scala> val ratings_url =
- | """https://nms.kcl.ac.uk/christian.urban/ratings.csv"""
+$ scala -cp wordle.jar
+scala> val secretsURL =
+ | """https://nms.kcl.ac.uk/christian.urban/wordle.txt"""
-scala> M2.get_csv_url(ratings_url)
-val res0: List[String] = List(1,1,4 ...)
+scala> M2.get_wordle_list(secretsURL)
+val res0: List[String] = List(aahed, aalii, ...)
\end{lstlisting}%$
\subsection*{Hints}
\noindent
-Use \texttt{.split(",").toList} for splitting
-strings according to commas (similarly for the newline character \mbox{$\backslash$\texttt{n}}),
+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{.take(n)} for taking some elements in a list (takes fewer if the list
-contains less than \texttt{n} elements).
+\texttt{.groupBy} orders lists according to same elements
+.
\newpage
-\subsection*{Main Part 2 (6 Marks, file danube.scala)}
-
-You are creating Danube.co.uk which you hope will be the next big thing
-in online movie renting. You know that you can save money by
-anticipating what movies people will rent; you will pass these savings
-on to your users by offering a discount if they rent movies that
-Danube.co.uk recommends.
+\subsection*{Main Part 2 (6 Marks, file wordle.scala)}
-Your task is to generate \emph{two} movie recommendations for every
-movie a user rents. To do this, you calculate what other
-renters, who also watched this movie, suggest by giving positive ratings.
-Of course, some suggestions are more popular than others. You need to find
-the two most-frequently suggested movies. Return fewer recommendations,
-if there are fewer movies suggested.
-
-The calculations will be based on the small datasets which the research lab
-GroupLens provides for education and development purposes.
+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}
-\url{https://grouplens.org/datasets/movielens/}
-\end{center}
+\includegraphics[scale=0.2]{../pics/w.jpeg}
+\end{center}
\noindent
-The slightly adapted CSV-files should be downloaded in your Scala
-file from the URLs:
-
+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/ratings.csv} & (940 KByte)\\
- \url{https://nms.kcl.ac.uk/christian.urban/movies.csv} & (280 KByte)\\
+ \url{https://nms.kcl.ac.uk/christian.urban/wordle.txt} & (78 KByte)\\
\end{tabular}
\end{center}
\noindent
-The ratings.csv file is organised as userID,
-movieID, and rating (which is between 0 and 5, with \emph{positive} ratings
-being 4 and 5). The file movie.csv is organised as
-movieID and full movie name. Both files still contain the usual
-CSV-file header (first line). In this part you are asked
-to implement functions that process these files. If bandwidth
-is an issue for you, download the files locally, but in the submitted
-version use \texttt{Source.fromURL} instead of \texttt{Source.fromFile}.
+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_csv_url} which takes an
- URL-string as argument and requests the corresponding file. The two
- URLs of interest are \pcode{ratings_url} and \pcode{movies_url},
- which correspond to CSV-files mentioned above. The function should
- return the CSV-file appropriately broken up into lines, and the
- first line should be dropped (that is omit the header of the CSV-file).
- The result is a list of strings (the lines in the file). In case
- the url does not produce a file, return the empty list.\\
- \mbox{}\hfill [1 Mark]
+\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.
+ \mbox{}\hfill [0.5 Marks]
-\item[(2)] Implement two functions that process the (broken up)
- CSV-files from (1). The \pcode{process_ratings} function filters out all
- ratings below 4 and returns a list of (userID, movieID) pairs. The
- \pcode{process_movies} function returns a list of (movieID, title) pairs.
- Note the input to these functions will be the output of the function
- \pcode{get_csv_url}.\\
- \mbox{}\hfill [1 Mark]
-%\end{itemize}
-%
-%
-%\subsection*{Part 3 (4 Marks, file danube.scala)}
-%
-%\subsection*{Tasks}
-%
-%\begin{itemize}
-\item[(3)] Implement a kind of grouping function that calculates a Map
- containing the userIDs and all the corresponding recommendations for
- this user (list of movieIDs). This should be implemented in a
- tail-recursive fashion using a Map as accumulator. This Map is set to
- \pcode{Map()} at the beginning of the calculation. For example
+\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]
-val lst = List(("1", "a"), ("1", "b"),
- ("2", "x"), ("3", "a"),
- ("2", "y"), ("3", "c"))
-groupById(lst, Map())
+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}
-returns the ratings map
+ 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}
- \pcode{Map(1 -> List(b, a), 2 -> List(y, x), 3 -> List(c, a))}.
-\end{center}
+ \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]
-\noindent
-In which order the elements of the list are given is unimportant.\\
-\mbox{}\hfill [1 Mark]
+\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}
-\item[(4)] Implement a function that takes a ratings map and a movieID
- as arguments. The function calculates all suggestions containing the
- given movie in its recommendations. It returns a list of all these
- recommendations (each of them is a list and needs to have the given
- movie deleted, otherwise it might happen we recommend the same movie
- ``back''). For example for the Map from above and the movie
- \pcode{"y"} we obtain \pcode{List(List("x"))}, and for the movie
- \pcode{"a"} we get \pcode{List(List("b"), List("c"))}.\\
+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[(5)] Implement a suggestions function which takes a ratings map
- and a movieID as arguments. It calculates all the recommended movies
- sorted according to the most frequently suggested movie(s) sorted
- first. This function returns \emph{all} suggested movieIDs as a list of
- strings.\\
- \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 and
+ 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.
-\item[(6)]
- Implement then a recommendation function which generates a maximum
- of two most-suggested movies (as calculated above). But it returns
- the actual movie name, not the movieID. If fewer movies are recommended,
- then return fewer than two movie names.\\
- \mbox{}\hfill [1 Mark]
+%
+%\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}
+%
+%
-%\item[(7)] Calculate the recommendations for all movies according to
-% what the recommendations function in (6) produces (this
-% can take a few seconds). Put all recommendations into a list
-% (of strings) and count how often the strings occur in
-% this list. This produces a list of string-int pairs,
-% where the first component is the movie name and the second
-% is the number of how many times the movie was recommended.
-% Sort all the pairs according to the number
-% of times they were recommended (most recommended movie name
-% first).\\
-% \mbox{}\hfill [1 Mark]
-
+\mbox{}\hfill [1 Mark]
\end{itemize}
\end{document}