diff -r 3c81352ec565 -r 6e990ae2c6a3 cws/main_cw02.tex --- 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}