
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} 




