author | Christian Urban <christian.urban@kcl.ac.uk> |
Thu, 10 Nov 2022 09:52:40 +0000 | |
changeset 441 | 3bfe81972674 |
parent 428 | cdfa6a293453 |
child 445 | b73e7ce91c10 |
permissions | -rw-r--r-- |
420 | 1 |
|
268 | 2 |
% !TEX program = xelatex |
6 | 3 |
\documentclass{article} |
426 | 4 |
\usepackage{../styles/style} |
166 | 5 |
\usepackage{disclaimer} |
426 | 6 |
\usepackage{../styles/langs} |
428
cdfa6a293453
updated solutions and templates
Christian Urban <christian.urban@kcl.ac.uk>
parents:
426
diff
changeset
|
7 |
\usepackage{graphicx} |
6 | 8 |
|
9 |
\begin{document} |
|
10 |
||
11 |
||
329 | 12 |
%% should ask to lower case the words. |
13 |
||
428
cdfa6a293453
updated solutions and templates
Christian Urban <christian.urban@kcl.ac.uk>
parents:
426
diff
changeset
|
14 |
\section*{Evil Wordle Game (Scala, 7 Marks)} |
6 | 15 |
|
420 | 16 |
\mbox{}\hfill\textit{``C makes it easy to shoot yourself in the foot; C++ makes it harder,}\\ |
17 |
\mbox{}\hfill\textit{ but when you do, it blows your whole leg off.''}\smallskip\\ |
|
18 |
\mbox{}\hfill\textit{ --- Bjarne Stroustrup (creator of the C++ language)}\bigskip\bigskip |
|
19 |
||
20 |
||
21 |
||
264 | 22 |
|
23 |
\noindent |
|
428
cdfa6a293453
updated solutions and templates
Christian Urban <christian.urban@kcl.ac.uk>
parents:
426
diff
changeset
|
24 |
You are asked to implement a Scala program for making the popular Wordle game as difficult |
cdfa6a293453
updated solutions and templates
Christian Urban <christian.urban@kcl.ac.uk>
parents:
426
diff
changeset
|
25 |
as possible.\bigskip |
50 | 26 |
|
349 | 27 |
\IMPORTANTNONE{} |
202 | 28 |
|
29 |
\noindent |
|
144 | 30 |
Also note that the running time of each part will be restricted to a |
202 | 31 |
maximum of 30 seconds on my laptop. |
39 | 32 |
|
166 | 33 |
\DISCLAIMER{} |
39 | 34 |
|
202 | 35 |
\subsection*{Reference Implementation} |
45 | 36 |
|
349 | 37 |
Like the C++ part, the Scala part works like this: you push your files |
38 |
to GitHub and receive (after sometimes a long delay) some automated |
|
39 |
feedback. In the end we will take a snapshot of the submitted files |
|
40 |
and apply an automated marking script to them.\medskip |
|
45 | 41 |
|
268 | 42 |
\noindent |
306 | 43 |
In addition, the Scala part comes with reference |
44 |
implementations in form of \texttt{jar}-files. This allows you to run |
|
202 | 45 |
any test cases on your own computer. For example you can call Scala on |
349 | 46 |
the command line with the option \texttt{-cp danube.jar} and then |
202 | 47 |
query any function from the template file. Say you want to find out |
349 | 48 |
what the function \texttt{} produces: for this you just need |
396 | 49 |
to prefix it with the object name \texttt{M2}. If you want to find out what |
202 | 50 |
these functions produce for the list \texttt{List("a", "b", "b")}, |
51 |
you would type something like: |
|
6 | 52 |
|
202 | 53 |
\begin{lstlisting}[language={},numbers=none,basicstyle=\ttfamily\small] |
428
cdfa6a293453
updated solutions and templates
Christian Urban <christian.urban@kcl.ac.uk>
parents:
426
diff
changeset
|
54 |
$ scala -cp wordle.jar |
cdfa6a293453
updated solutions and templates
Christian Urban <christian.urban@kcl.ac.uk>
parents:
426
diff
changeset
|
55 |
scala> val secretsURL = |
cdfa6a293453
updated solutions and templates
Christian Urban <christian.urban@kcl.ac.uk>
parents:
426
diff
changeset
|
56 |
| """https://nms.kcl.ac.uk/christian.urban/wordle.txt""" |
349 | 57 |
|
428
cdfa6a293453
updated solutions and templates
Christian Urban <christian.urban@kcl.ac.uk>
parents:
426
diff
changeset
|
58 |
scala> M2.get_wordle_list(secretsURL) |
cdfa6a293453
updated solutions and templates
Christian Urban <christian.urban@kcl.ac.uk>
parents:
426
diff
changeset
|
59 |
val res0: List[String] = List(aahed, aalii, ...) |
202 | 60 |
\end{lstlisting}%$ |
61 |
||
62 |
\subsection*{Hints} |
|
6 | 63 |
|
203 | 64 |
\noindent |
428
cdfa6a293453
updated solutions and templates
Christian Urban <christian.urban@kcl.ac.uk>
parents:
426
diff
changeset
|
65 |
Useful data functions: \texttt{Source.fromURL}, |
cdfa6a293453
updated solutions and templates
Christian Urban <christian.urban@kcl.ac.uk>
parents:
426
diff
changeset
|
66 |
\texttt{Source.fromFile} for obtaining a webpage and reading a file, |
301 | 67 |
\texttt{.getOrElse(..,..)} allows to query a Map, but also gives a |
203 | 68 |
default value if the Map is not defined, a Map can be `updated' by |
69 |
using \texttt{+}, \texttt{.contains} and \texttt{.filter} can test whether |
|
70 |
an element is included in a list, and respectively filter out elements in a list, |
|
71 |
\texttt{.sortBy(\_.\_2)} sorts a list of pairs according to the second |
|
72 |
elements in the pairs---the sorting is done from smallest to highest, |
|
428
cdfa6a293453
updated solutions and templates
Christian Urban <christian.urban@kcl.ac.uk>
parents:
426
diff
changeset
|
73 |
\texttt{.groupBy} orders lists according to same elements |
cdfa6a293453
updated solutions and templates
Christian Urban <christian.urban@kcl.ac.uk>
parents:
426
diff
changeset
|
74 |
. |
39 | 75 |
|
76 |
||
202 | 77 |
\newpage |
6 | 78 |
|
79 |
||
428
cdfa6a293453
updated solutions and templates
Christian Urban <christian.urban@kcl.ac.uk>
parents:
426
diff
changeset
|
80 |
\subsection*{Main Part 2 (6 Marks, file wordle.scala)} |
48 | 81 |
|
428
cdfa6a293453
updated solutions and templates
Christian Urban <christian.urban@kcl.ac.uk>
parents:
426
diff
changeset
|
82 |
You probably know the game of Wordle\footnote{\url{https://en.wikipedia.org/wiki/Wordle}} |
cdfa6a293453
updated solutions and templates
Christian Urban <christian.urban@kcl.ac.uk>
parents:
426
diff
changeset
|
83 |
where you are supposed to guess a five-letter word. The feedback for guesses can help |
cdfa6a293453
updated solutions and templates
Christian Urban <christian.urban@kcl.ac.uk>
parents:
426
diff
changeset
|
84 |
with the next guess (green letters are correct, orange letters are present, but in the |
cdfa6a293453
updated solutions and templates
Christian Urban <christian.urban@kcl.ac.uk>
parents:
426
diff
changeset
|
85 |
wrong place). For example: |
203 | 86 |
|
87 |
\begin{center} |
|
428
cdfa6a293453
updated solutions and templates
Christian Urban <christian.urban@kcl.ac.uk>
parents:
426
diff
changeset
|
88 |
\includegraphics[scale=0.2]{../pics/w.jpeg} |
cdfa6a293453
updated solutions and templates
Christian Urban <christian.urban@kcl.ac.uk>
parents:
426
diff
changeset
|
89 |
\end{center} |
203 | 90 |
|
91 |
\noindent |
|
428
cdfa6a293453
updated solutions and templates
Christian Urban <christian.urban@kcl.ac.uk>
parents:
426
diff
changeset
|
92 |
The idea of the program to be implemented here is to make the Wordle game as evil as possible |
cdfa6a293453
updated solutions and templates
Christian Urban <christian.urban@kcl.ac.uk>
parents:
426
diff
changeset
|
93 |
by finding words that are the most difficult to guess. A word list of five-letter words is available |
cdfa6a293453
updated solutions and templates
Christian Urban <christian.urban@kcl.ac.uk>
parents:
426
diff
changeset
|
94 |
from |
148 | 95 |
|
203 | 96 |
\begin{center} |
97 |
\begin{tabular}{ll} |
|
428
cdfa6a293453
updated solutions and templates
Christian Urban <christian.urban@kcl.ac.uk>
parents:
426
diff
changeset
|
98 |
\url{https://nms.kcl.ac.uk/christian.urban/wordle.txt} & (78 KByte)\\ |
203 | 99 |
\end{tabular} |
100 |
\end{center} |
|
101 |
||
102 |
\noindent |
|
428
cdfa6a293453
updated solutions and templates
Christian Urban <christian.urban@kcl.ac.uk>
parents:
426
diff
changeset
|
103 |
In your program you need to download this list and implement some |
cdfa6a293453
updated solutions and templates
Christian Urban <christian.urban@kcl.ac.uk>
parents:
426
diff
changeset
|
104 |
functions that in the end select the most difficult words (given an |
cdfa6a293453
updated solutions and templates
Christian Urban <christian.urban@kcl.ac.uk>
parents:
426
diff
changeset
|
105 |
input from the user). If bandwidth is an issue for you, download the |
cdfa6a293453
updated solutions and templates
Christian Urban <christian.urban@kcl.ac.uk>
parents:
426
diff
changeset
|
106 |
file locally, but in the submitted version use \texttt{Source.fromURL} |
cdfa6a293453
updated solutions and templates
Christian Urban <christian.urban@kcl.ac.uk>
parents:
426
diff
changeset
|
107 |
instead of \texttt{Source.fromFile}. |
203 | 108 |
|
109 |
\subsection*{Tasks} |
|
45 | 110 |
|
203 | 111 |
\begin{itemize} |
428
cdfa6a293453
updated solutions and templates
Christian Urban <christian.urban@kcl.ac.uk>
parents:
426
diff
changeset
|
112 |
\item[(1)] Implement the function \pcode{get_wordle_list} which takes an |
cdfa6a293453
updated solutions and templates
Christian Urban <christian.urban@kcl.ac.uk>
parents:
426
diff
changeset
|
113 |
URL-string as argument and requests the corresponding file. The function should |
cdfa6a293453
updated solutions and templates
Christian Urban <christian.urban@kcl.ac.uk>
parents:
426
diff
changeset
|
114 |
return the word list appropriately broken up into lines. |
cdfa6a293453
updated solutions and templates
Christian Urban <christian.urban@kcl.ac.uk>
parents:
426
diff
changeset
|
115 |
The result should be a list of strings (the lines in the file). In case |
cdfa6a293453
updated solutions and templates
Christian Urban <christian.urban@kcl.ac.uk>
parents:
426
diff
changeset
|
116 |
the url does not produce a file, return the empty list. |
cdfa6a293453
updated solutions and templates
Christian Urban <christian.urban@kcl.ac.uk>
parents:
426
diff
changeset
|
117 |
\mbox{}\hfill [0.5 Marks] |
203 | 118 |
|
428
cdfa6a293453
updated solutions and templates
Christian Urban <christian.urban@kcl.ac.uk>
parents:
426
diff
changeset
|
119 |
\item[(2)] Implement a polymorphic function \pcode{removeN}, which removes $n$ occurrences of an |
cdfa6a293453
updated solutions and templates
Christian Urban <christian.urban@kcl.ac.uk>
parents:
426
diff
changeset
|
120 |
element from a list (if this element is less than $n$ times present, then remove all occurrences). |
cdfa6a293453
updated solutions and templates
Christian Urban <christian.urban@kcl.ac.uk>
parents:
426
diff
changeset
|
121 |
For example |
203 | 122 |
|
123 |
\begin{lstlisting}[numbers=none] |
|
428
cdfa6a293453
updated solutions and templates
Christian Urban <christian.urban@kcl.ac.uk>
parents:
426
diff
changeset
|
124 |
removeN(List(1,2,3,2,1), 3, 2) => List(1, 2, 2, 1) |
cdfa6a293453
updated solutions and templates
Christian Urban <christian.urban@kcl.ac.uk>
parents:
426
diff
changeset
|
125 |
removeN(List(1,2,3,2,1), 2, 1) => List(1, 3, 2, 1) |
cdfa6a293453
updated solutions and templates
Christian Urban <christian.urban@kcl.ac.uk>
parents:
426
diff
changeset
|
126 |
removeN(List(1,2,3,2,1), 2, 2) => List(1, 3, 1) |
cdfa6a293453
updated solutions and templates
Christian Urban <christian.urban@kcl.ac.uk>
parents:
426
diff
changeset
|
127 |
removeN(List(1,2,3,2,1), 1, 1) => List(2, 3, 2, 1) |
cdfa6a293453
updated solutions and templates
Christian Urban <christian.urban@kcl.ac.uk>
parents:
426
diff
changeset
|
128 |
removeN(List(1,2,3,2,1), 1, 3) => List(2, 3, 2) |
cdfa6a293453
updated solutions and templates
Christian Urban <christian.urban@kcl.ac.uk>
parents:
426
diff
changeset
|
129 |
removeN(List(1,2,3,2,1), 0, 2) => List(1, 2, 3, 2, 1) |
cdfa6a293453
updated solutions and templates
Christian Urban <christian.urban@kcl.ac.uk>
parents:
426
diff
changeset
|
130 |
\end{lstlisting} |
cdfa6a293453
updated solutions and templates
Christian Urban <christian.urban@kcl.ac.uk>
parents:
426
diff
changeset
|
131 |
|
cdfa6a293453
updated solutions and templates
Christian Urban <christian.urban@kcl.ac.uk>
parents:
426
diff
changeset
|
132 |
Make sure you only remove at most $n$ occurrences of the element from the list. |
cdfa6a293453
updated solutions and templates
Christian Urban <christian.urban@kcl.ac.uk>
parents:
426
diff
changeset
|
133 |
This function should work for lists of integers but also lists of chars, strings etc.\\ |
cdfa6a293453
updated solutions and templates
Christian Urban <christian.urban@kcl.ac.uk>
parents:
426
diff
changeset
|
134 |
\mbox{}\hfill [0.5 Marks] |
cdfa6a293453
updated solutions and templates
Christian Urban <christian.urban@kcl.ac.uk>
parents:
426
diff
changeset
|
135 |
|
cdfa6a293453
updated solutions and templates
Christian Urban <christian.urban@kcl.ac.uk>
parents:
426
diff
changeset
|
136 |
\item[(3)] Implement a function \pcode{score} that calculates the |
cdfa6a293453
updated solutions and templates
Christian Urban <christian.urban@kcl.ac.uk>
parents:
426
diff
changeset
|
137 |
feedback for a word against a secret word using the rules of the |
cdfa6a293453
updated solutions and templates
Christian Urban <christian.urban@kcl.ac.uk>
parents:
426
diff
changeset
|
138 |
Wordle game. The output of \pcode{score} should be a list of 5 |
cdfa6a293453
updated solutions and templates
Christian Urban <christian.urban@kcl.ac.uk>
parents:
426
diff
changeset
|
139 |
elements of type \pcode{Tip} representing three outcomes: a letter |
cdfa6a293453
updated solutions and templates
Christian Urban <christian.urban@kcl.ac.uk>
parents:
426
diff
changeset
|
140 |
in the correct position, a letter that is present, but not in the |
cdfa6a293453
updated solutions and templates
Christian Urban <christian.urban@kcl.ac.uk>
parents:
426
diff
changeset
|
141 |
correct position and a letter that is absent. For example given the |
cdfa6a293453
updated solutions and templates
Christian Urban <christian.urban@kcl.ac.uk>
parents:
426
diff
changeset
|
142 |
secret word "chess" the score for the word "caves" is |
cdfa6a293453
updated solutions and templates
Christian Urban <christian.urban@kcl.ac.uk>
parents:
426
diff
changeset
|
143 |
|
cdfa6a293453
updated solutions and templates
Christian Urban <christian.urban@kcl.ac.uk>
parents:
426
diff
changeset
|
144 |
\begin{lstlisting}[numbers=none] |
cdfa6a293453
updated solutions and templates
Christian Urban <christian.urban@kcl.ac.uk>
parents:
426
diff
changeset
|
145 |
List(Correct, Absent, Absent, Present, Correct) |
cdfa6a293453
updated solutions and templates
Christian Urban <christian.urban@kcl.ac.uk>
parents:
426
diff
changeset
|
146 |
\end{lstlisting} |
cdfa6a293453
updated solutions and templates
Christian Urban <christian.urban@kcl.ac.uk>
parents:
426
diff
changeset
|
147 |
|
cdfa6a293453
updated solutions and templates
Christian Urban <christian.urban@kcl.ac.uk>
parents:
426
diff
changeset
|
148 |
You have to be careful with multiple occurrences of letters. For example |
cdfa6a293453
updated solutions and templates
Christian Urban <christian.urban@kcl.ac.uk>
parents:
426
diff
changeset
|
149 |
the secret "chess" with the guess "swiss" should produce |
cdfa6a293453
updated solutions and templates
Christian Urban <christian.urban@kcl.ac.uk>
parents:
426
diff
changeset
|
150 |
|
cdfa6a293453
updated solutions and templates
Christian Urban <christian.urban@kcl.ac.uk>
parents:
426
diff
changeset
|
151 |
\begin{lstlisting}[numbers=none] |
cdfa6a293453
updated solutions and templates
Christian Urban <christian.urban@kcl.ac.uk>
parents:
426
diff
changeset
|
152 |
List(Absent, Absent, Absent, Correct, Correct) |
cdfa6a293453
updated solutions and templates
Christian Urban <christian.urban@kcl.ac.uk>
parents:
426
diff
changeset
|
153 |
\end{lstlisting} |
cdfa6a293453
updated solutions and templates
Christian Urban <christian.urban@kcl.ac.uk>
parents:
426
diff
changeset
|
154 |
|
cdfa6a293453
updated solutions and templates
Christian Urban <christian.urban@kcl.ac.uk>
parents:
426
diff
changeset
|
155 |
even though the first 's' in "swiss" is present in the secret word, the 's' are already |
cdfa6a293453
updated solutions and templates
Christian Urban <christian.urban@kcl.ac.uk>
parents:
426
diff
changeset
|
156 |
`used up' by the two letters that are correct. To implement this you need to |
cdfa6a293453
updated solutions and templates
Christian Urban <christian.urban@kcl.ac.uk>
parents:
426
diff
changeset
|
157 |
implement first a function \pcode{pool} which calculates all the letters in |
cdfa6a293453
updated solutions and templates
Christian Urban <christian.urban@kcl.ac.uk>
parents:
426
diff
changeset
|
158 |
a secret that are not correct in a word. For example |
cdfa6a293453
updated solutions and templates
Christian Urban <christian.urban@kcl.ac.uk>
parents:
426
diff
changeset
|
159 |
|
cdfa6a293453
updated solutions and templates
Christian Urban <christian.urban@kcl.ac.uk>
parents:
426
diff
changeset
|
160 |
\begin{lstlisting}[numbers=none] |
cdfa6a293453
updated solutions and templates
Christian Urban <christian.urban@kcl.ac.uk>
parents:
426
diff
changeset
|
161 |
pool("chess", "caves") => List(h, e, s) |
cdfa6a293453
updated solutions and templates
Christian Urban <christian.urban@kcl.ac.uk>
parents:
426
diff
changeset
|
162 |
pool("chess", "swiss") => List(c, h, e) |
203 | 163 |
\end{lstlisting} |
164 |
||
428
cdfa6a293453
updated solutions and templates
Christian Urban <christian.urban@kcl.ac.uk>
parents:
426
diff
changeset
|
165 |
Now the helper function \pcode{aux} can analyse the arguments secret and word recursively letter-by-letter and |
cdfa6a293453
updated solutions and templates
Christian Urban <christian.urban@kcl.ac.uk>
parents:
426
diff
changeset
|
166 |
decide: if the letters are the same, then return \pcode{Correct} for the corresponding position. |
cdfa6a293453
updated solutions and templates
Christian Urban <christian.urban@kcl.ac.uk>
parents:
426
diff
changeset
|
167 |
If they are not the same, but the letter is in the pool, then return \pcode{Present} and also remove |
cdfa6a293453
updated solutions and templates
Christian Urban <christian.urban@kcl.ac.uk>
parents:
426
diff
changeset
|
168 |
this letter from the pool in the next recursive call of \pcode{aux}. Otherwise return \pcode{Absent} for the |
cdfa6a293453
updated solutions and templates
Christian Urban <christian.urban@kcl.ac.uk>
parents:
426
diff
changeset
|
169 |
corresponding position. The function \pcode{score} is a wrapper for the function \pcode{aux} |
cdfa6a293453
updated solutions and templates
Christian Urban <christian.urban@kcl.ac.uk>
parents:
426
diff
changeset
|
170 |
calling \pcode{aux} with the appropriate arguments (recall what is calculated with \pcode{pool}).\mbox{}\hfill [2 Marks] |
cdfa6a293453
updated solutions and templates
Christian Urban <christian.urban@kcl.ac.uk>
parents:
426
diff
changeset
|
171 |
|
cdfa6a293453
updated solutions and templates
Christian Urban <christian.urban@kcl.ac.uk>
parents:
426
diff
changeset
|
172 |
\item[(4)] Implement a function \pcode{eval} that gives an integer value to each of the |
cdfa6a293453
updated solutions and templates
Christian Urban <christian.urban@kcl.ac.uk>
parents:
426
diff
changeset
|
173 |
\pcode{Tip}s such that |
203 | 174 |
|
428
cdfa6a293453
updated solutions and templates
Christian Urban <christian.urban@kcl.ac.uk>
parents:
426
diff
changeset
|
175 |
\begin{center} |
cdfa6a293453
updated solutions and templates
Christian Urban <christian.urban@kcl.ac.uk>
parents:
426
diff
changeset
|
176 |
\begin{tabular}{lcl} |
cdfa6a293453
updated solutions and templates
Christian Urban <christian.urban@kcl.ac.uk>
parents:
426
diff
changeset
|
177 |
\textit{eval (Correct)} & $\dn$ & $10$\\ |
cdfa6a293453
updated solutions and templates
Christian Urban <christian.urban@kcl.ac.uk>
parents:
426
diff
changeset
|
178 |
\textit{eval (Present)} & $\dn$ & $1$\\ |
cdfa6a293453
updated solutions and templates
Christian Urban <christian.urban@kcl.ac.uk>
parents:
426
diff
changeset
|
179 |
\textit{eval (Absent)} & $\dn$ & $0$ |
cdfa6a293453
updated solutions and templates
Christian Urban <christian.urban@kcl.ac.uk>
parents:
426
diff
changeset
|
180 |
\end{tabular} |
cdfa6a293453
updated solutions and templates
Christian Urban <christian.urban@kcl.ac.uk>
parents:
426
diff
changeset
|
181 |
\end{center} |
cdfa6a293453
updated solutions and templates
Christian Urban <christian.urban@kcl.ac.uk>
parents:
426
diff
changeset
|
182 |
|
cdfa6a293453
updated solutions and templates
Christian Urban <christian.urban@kcl.ac.uk>
parents:
426
diff
changeset
|
183 |
The function \pcode{iscore} then takes an output of \pcode{score} and sums |
cdfa6a293453
updated solutions and templates
Christian Urban <christian.urban@kcl.ac.uk>
parents:
426
diff
changeset
|
184 |
up all corresponding values. For example for |
cdfa6a293453
updated solutions and templates
Christian Urban <christian.urban@kcl.ac.uk>
parents:
426
diff
changeset
|
185 |
|
cdfa6a293453
updated solutions and templates
Christian Urban <christian.urban@kcl.ac.uk>
parents:
426
diff
changeset
|
186 |
\begin{lstlisting}[numbers=none] |
cdfa6a293453
updated solutions and templates
Christian Urban <christian.urban@kcl.ac.uk>
parents:
426
diff
changeset
|
187 |
iscore("chess", "caves") => 21 |
cdfa6a293453
updated solutions and templates
Christian Urban <christian.urban@kcl.ac.uk>
parents:
426
diff
changeset
|
188 |
iscore("chess", "swiss") => 20 |
cdfa6a293453
updated solutions and templates
Christian Urban <christian.urban@kcl.ac.uk>
parents:
426
diff
changeset
|
189 |
\end{lstlisting} |
cdfa6a293453
updated solutions and templates
Christian Urban <christian.urban@kcl.ac.uk>
parents:
426
diff
changeset
|
190 |
\mbox{}\hfill [0.5 Marks] |
203 | 191 |
|
428
cdfa6a293453
updated solutions and templates
Christian Urban <christian.urban@kcl.ac.uk>
parents:
426
diff
changeset
|
192 |
\item[(5)] The function \pcode{evil} takes a list of secrets (the list from Task 1) |
cdfa6a293453
updated solutions and templates
Christian Urban <christian.urban@kcl.ac.uk>
parents:
426
diff
changeset
|
193 |
and a word as arguments, and calculates the list of words with the lowest |
cdfa6a293453
updated solutions and templates
Christian Urban <christian.urban@kcl.ac.uk>
parents:
426
diff
changeset
|
194 |
score (remember we want to make the Wordle game as difficult as possible---therefore |
cdfa6a293453
updated solutions and templates
Christian Urban <christian.urban@kcl.ac.uk>
parents:
426
diff
changeset
|
195 |
when the user gives us a word, we want to find the secrets that produce the lowest |
cdfa6a293453
updated solutions and templates
Christian Urban <christian.urban@kcl.ac.uk>
parents:
426
diff
changeset
|
196 |
score). For this implement a helper function \pcode{lowest} that goes through |
cdfa6a293453
updated solutions and templates
Christian Urban <christian.urban@kcl.ac.uk>
parents:
426
diff
changeset
|
197 |
the secrets one-by-one and calculates the score. The argument \pcode{current} is |
cdfa6a293453
updated solutions and templates
Christian Urban <christian.urban@kcl.ac.uk>
parents:
426
diff
changeset
|
198 |
the score of the ``currently'' found secrets. When the function \pcode{lowest} |
cdfa6a293453
updated solutions and templates
Christian Urban <christian.urban@kcl.ac.uk>
parents:
426
diff
changeset
|
199 |
is called for the first time then this will be set to the maximum integer value |
cdfa6a293453
updated solutions and templates
Christian Urban <christian.urban@kcl.ac.uk>
parents:
426
diff
changeset
|
200 |
\pcode{Int.MaxValue}. The accumulator will be first empty. If a secret is found |
cdfa6a293453
updated solutions and templates
Christian Urban <christian.urban@kcl.ac.uk>
parents:
426
diff
changeset
|
201 |
with the same score as \pcode{current} then this word is added to the accumulator. |
cdfa6a293453
updated solutions and templates
Christian Urban <christian.urban@kcl.ac.uk>
parents:
426
diff
changeset
|
202 |
If the secret has a lower score, then the accumulator will be discarded and this |
cdfa6a293453
updated solutions and templates
Christian Urban <christian.urban@kcl.ac.uk>
parents:
426
diff
changeset
|
203 |
secret will be the new accumulator. If the secret has a higher score, then it can be |
cdfa6a293453
updated solutions and templates
Christian Urban <christian.urban@kcl.ac.uk>
parents:
426
diff
changeset
|
204 |
ignored. For example \pcode{evil} (the wrapper for \pcode{lowest}) generates |
cdfa6a293453
updated solutions and templates
Christian Urban <christian.urban@kcl.ac.uk>
parents:
426
diff
changeset
|
205 |
|
cdfa6a293453
updated solutions and templates
Christian Urban <christian.urban@kcl.ac.uk>
parents:
426
diff
changeset
|
206 |
\begin{lstlisting}[numbers=none] |
cdfa6a293453
updated solutions and templates
Christian Urban <christian.urban@kcl.ac.uk>
parents:
426
diff
changeset
|
207 |
evil(secrets, "stent").length => 1907 |
cdfa6a293453
updated solutions and templates
Christian Urban <christian.urban@kcl.ac.uk>
parents:
426
diff
changeset
|
208 |
evil(secrets, "hexes").length => 2966 |
cdfa6a293453
updated solutions and templates
Christian Urban <christian.urban@kcl.ac.uk>
parents:
426
diff
changeset
|
209 |
evil(secrets, "horse").length => 1203 |
cdfa6a293453
updated solutions and templates
Christian Urban <christian.urban@kcl.ac.uk>
parents:
426
diff
changeset
|
210 |
evil(secrets, "hoise").length => 971 |
cdfa6a293453
updated solutions and templates
Christian Urban <christian.urban@kcl.ac.uk>
parents:
426
diff
changeset
|
211 |
evil(secrets, "house").length => 1228 |
cdfa6a293453
updated solutions and templates
Christian Urban <christian.urban@kcl.ac.uk>
parents:
426
diff
changeset
|
212 |
\end{lstlisting} |
45 | 213 |
|
428
cdfa6a293453
updated solutions and templates
Christian Urban <christian.urban@kcl.ac.uk>
parents:
426
diff
changeset
|
214 |
where \pcode{secrets} is the list generated under Task 1. |
cdfa6a293453
updated solutions and templates
Christian Urban <christian.urban@kcl.ac.uk>
parents:
426
diff
changeset
|
215 |
In all cases above the iscore of the resulting secrets is 0, but this does not need to be the case |
cdfa6a293453
updated solutions and templates
Christian Urban <christian.urban@kcl.ac.uk>
parents:
426
diff
changeset
|
216 |
in general.\\ |
cdfa6a293453
updated solutions and templates
Christian Urban <christian.urban@kcl.ac.uk>
parents:
426
diff
changeset
|
217 |
\mbox{}\hfill [1.5 Marks] |
cdfa6a293453
updated solutions and templates
Christian Urban <christian.urban@kcl.ac.uk>
parents:
426
diff
changeset
|
218 |
|
cdfa6a293453
updated solutions and templates
Christian Urban <christian.urban@kcl.ac.uk>
parents:
426
diff
changeset
|
219 |
\item[(6)] The secrets generated in Task 5 are the ones with the lowest score |
cdfa6a293453
updated solutions and templates
Christian Urban <christian.urban@kcl.ac.uk>
parents:
426
diff
changeset
|
220 |
with respect to the word. You can think of these as the secrets that are furthest ``away'' from the |
cdfa6a293453
updated solutions and templates
Christian Urban <christian.urban@kcl.ac.uk>
parents:
426
diff
changeset
|
221 |
given word. This is already quite evil for a secret word---remember we can choose |
cdfa6a293453
updated solutions and templates
Christian Urban <christian.urban@kcl.ac.uk>
parents:
426
diff
changeset
|
222 |
a secret \emph{after} a user has given a first word. Now we want to make it |
cdfa6a293453
updated solutions and templates
Christian Urban <christian.urban@kcl.ac.uk>
parents:
426
diff
changeset
|
223 |
even more evil by choosing words that have the most obscure letters. For this we |
cdfa6a293453
updated solutions and templates
Christian Urban <christian.urban@kcl.ac.uk>
parents:
426
diff
changeset
|
224 |
calculate the frequency of how many times certain letters occur in our secrets |
cdfa6a293453
updated solutions and templates
Christian Urban <christian.urban@kcl.ac.uk>
parents:
426
diff
changeset
|
225 |
list (see Task 1). The \emph{frequency} of the letter $c$, say, is given by the formula |
cdfa6a293453
updated solutions and templates
Christian Urban <christian.urban@kcl.ac.uk>
parents:
426
diff
changeset
|
226 |
|
cdfa6a293453
updated solutions and templates
Christian Urban <christian.urban@kcl.ac.uk>
parents:
426
diff
changeset
|
227 |
\begin{center} |
cdfa6a293453
updated solutions and templates
Christian Urban <christian.urban@kcl.ac.uk>
parents:
426
diff
changeset
|
228 |
$\textit{freq(c)} \dn 1 - \frac{\textit{number of occurrences of c}}{\textit{number of all letters}}$ |
cdfa6a293453
updated solutions and templates
Christian Urban <christian.urban@kcl.ac.uk>
parents:
426
diff
changeset
|
229 |
\end{center} |
cdfa6a293453
updated solutions and templates
Christian Urban <christian.urban@kcl.ac.uk>
parents:
426
diff
changeset
|
230 |
|
cdfa6a293453
updated solutions and templates
Christian Urban <christian.urban@kcl.ac.uk>
parents:
426
diff
changeset
|
231 |
That means that letters that occur fewer times in our secrets have a higher frequency. |
cdfa6a293453
updated solutions and templates
Christian Urban <christian.urban@kcl.ac.uk>
parents:
426
diff
changeset
|
232 |
For example the letter 'y' has the frequency 0.9680234350909651 while the much more |
cdfa6a293453
updated solutions and templates
Christian Urban <christian.urban@kcl.ac.uk>
parents:
426
diff
changeset
|
233 |
often occurring letter 'e' has only 0.897286463151403 (all calculations should be done |
cdfa6a293453
updated solutions and templates
Christian Urban <christian.urban@kcl.ac.uk>
parents:
426
diff
changeset
|
234 |
with Doubles). |
cdfa6a293453
updated solutions and templates
Christian Urban <christian.urban@kcl.ac.uk>
parents:
426
diff
changeset
|
235 |
|
cdfa6a293453
updated solutions and templates
Christian Urban <christian.urban@kcl.ac.uk>
parents:
426
diff
changeset
|
236 |
The function \pcode{frequencies} should calculate the frequencies for all lower-case letters |
cdfa6a293453
updated solutions and templates
Christian Urban <christian.urban@kcl.ac.uk>
parents:
426
diff
changeset
|
237 |
by generating a Map from letters (\pcode{Char}) to Doubles (frequencies).\\ |
203 | 238 |
\mbox{}\hfill [1 Mark] |
148 | 239 |
|
428
cdfa6a293453
updated solutions and templates
Christian Urban <christian.urban@kcl.ac.uk>
parents:
426
diff
changeset
|
240 |
\item[(7)] In this task we want to use the output of \pcode{evil}, rank each string in the |
cdfa6a293453
updated solutions and templates
Christian Urban <christian.urban@kcl.ac.uk>
parents:
426
diff
changeset
|
241 |
generated set and then filter out the strings that are ranked highest (the ones with the most obscure letters). |
cdfa6a293453
updated solutions and templates
Christian Urban <christian.urban@kcl.ac.uk>
parents:
426
diff
changeset
|
242 |
This list of strings often contains only a single word, but in general there might be more (see below). |
cdfa6a293453
updated solutions and templates
Christian Urban <christian.urban@kcl.ac.uk>
parents:
426
diff
changeset
|
243 |
First implement a function \pcode{rank} that takes a frequency map (from 6) and a string as arguments and |
cdfa6a293453
updated solutions and templates
Christian Urban <christian.urban@kcl.ac.uk>
parents:
426
diff
changeset
|
244 |
generates a rank by summing up all frequencies of the letters in the string. For example |
cdfa6a293453
updated solutions and templates
Christian Urban <christian.urban@kcl.ac.uk>
parents:
426
diff
changeset
|
245 |
|
cdfa6a293453
updated solutions and templates
Christian Urban <christian.urban@kcl.ac.uk>
parents:
426
diff
changeset
|
246 |
\begin{lstlisting}[numbers=none] |
cdfa6a293453
updated solutions and templates
Christian Urban <christian.urban@kcl.ac.uk>
parents:
426
diff
changeset
|
247 |
rank(frequencies(secrets), "adobe") => 4.673604687018193 |
cdfa6a293453
updated solutions and templates
Christian Urban <christian.urban@kcl.ac.uk>
parents:
426
diff
changeset
|
248 |
rank(frequencies(secrets), "gaffe") => 4.745205057045945 |
cdfa6a293453
updated solutions and templates
Christian Urban <christian.urban@kcl.ac.uk>
parents:
426
diff
changeset
|
249 |
rank(frequencies(secrets), "fuzzy") => 4.898735738513722 |
cdfa6a293453
updated solutions and templates
Christian Urban <christian.urban@kcl.ac.uk>
parents:
426
diff
changeset
|
250 |
\end{lstlisting} |
cdfa6a293453
updated solutions and templates
Christian Urban <christian.urban@kcl.ac.uk>
parents:
426
diff
changeset
|
251 |
|
cdfa6a293453
updated solutions and templates
Christian Urban <christian.urban@kcl.ac.uk>
parents:
426
diff
changeset
|
252 |
Finally, implement a function \pcode{ranked_evil} that selects from the output of \pcode{evil} |
cdfa6a293453
updated solutions and templates
Christian Urban <christian.urban@kcl.ac.uk>
parents:
426
diff
changeset
|
253 |
the string(s) which are highest ranked in evilness. |
cdfa6a293453
updated solutions and templates
Christian Urban <christian.urban@kcl.ac.uk>
parents:
426
diff
changeset
|
254 |
|
cdfa6a293453
updated solutions and templates
Christian Urban <christian.urban@kcl.ac.uk>
parents:
426
diff
changeset
|
255 |
|
cdfa6a293453
updated solutions and templates
Christian Urban <christian.urban@kcl.ac.uk>
parents:
426
diff
changeset
|
256 |
\begin{lstlisting}[numbers=none] |
cdfa6a293453
updated solutions and templates
Christian Urban <christian.urban@kcl.ac.uk>
parents:
426
diff
changeset
|
257 |
ranked_evil(secrets, "abbey") => List(whizz) |
cdfa6a293453
updated solutions and templates
Christian Urban <christian.urban@kcl.ac.uk>
parents:
426
diff
changeset
|
258 |
ranked_evil(secrets, "afear") => List(buzzy) |
cdfa6a293453
updated solutions and templates
Christian Urban <christian.urban@kcl.ac.uk>
parents:
426
diff
changeset
|
259 |
ranked_evil(secrets, "zincy") => List(jugum) |
cdfa6a293453
updated solutions and templates
Christian Urban <christian.urban@kcl.ac.uk>
parents:
426
diff
changeset
|
260 |
ranked_evil(secrets, "zippy") => List(chuff) |
cdfa6a293453
updated solutions and templates
Christian Urban <christian.urban@kcl.ac.uk>
parents:
426
diff
changeset
|
261 |
\end{lstlisting} |
cdfa6a293453
updated solutions and templates
Christian Urban <christian.urban@kcl.ac.uk>
parents:
426
diff
changeset
|
262 |
|
cdfa6a293453
updated solutions and templates
Christian Urban <christian.urban@kcl.ac.uk>
parents:
426
diff
changeset
|
263 |
This means if the user types in "abbey" then the most evil word to choose as secret is ``whizz'' (according to |
cdfa6a293453
updated solutions and templates
Christian Urban <christian.urban@kcl.ac.uk>
parents:
426
diff
changeset
|
264 |
our calculations). This word has a zero \pcode{iscore} and the most obscure letters. |
148 | 265 |
|
428
cdfa6a293453
updated solutions and templates
Christian Urban <christian.urban@kcl.ac.uk>
parents:
426
diff
changeset
|
266 |
% |
cdfa6a293453
updated solutions and templates
Christian Urban <christian.urban@kcl.ac.uk>
parents:
426
diff
changeset
|
267 |
%\color{red} |
cdfa6a293453
updated solutions and templates
Christian Urban <christian.urban@kcl.ac.uk>
parents:
426
diff
changeset
|
268 |
%\section*{Correction with \texttt{ranked\_evil}} |
cdfa6a293453
updated solutions and templates
Christian Urban <christian.urban@kcl.ac.uk>
parents:
426
diff
changeset
|
269 |
% |
cdfa6a293453
updated solutions and templates
Christian Urban <christian.urban@kcl.ac.uk>
parents:
426
diff
changeset
|
270 |
%The testcases above are actually not the maximum, but the minimum! I will make sure |
cdfa6a293453
updated solutions and templates
Christian Urban <christian.urban@kcl.ac.uk>
parents:
426
diff
changeset
|
271 |
%that the task will count as solved when either the minimum (as above) or the maximum (as intended) |
cdfa6a293453
updated solutions and templates
Christian Urban <christian.urban@kcl.ac.uk>
parents:
426
diff
changeset
|
272 |
%is used. The correct solutions for the above testcases using the maximum are: |
cdfa6a293453
updated solutions and templates
Christian Urban <christian.urban@kcl.ac.uk>
parents:
426
diff
changeset
|
273 |
%\color{black} |
cdfa6a293453
updated solutions and templates
Christian Urban <christian.urban@kcl.ac.uk>
parents:
426
diff
changeset
|
274 |
% |
cdfa6a293453
updated solutions and templates
Christian Urban <christian.urban@kcl.ac.uk>
parents:
426
diff
changeset
|
275 |
%\begin{lstlisting}[numbers=none] |
cdfa6a293453
updated solutions and templates
Christian Urban <christian.urban@kcl.ac.uk>
parents:
426
diff
changeset
|
276 |
%ranked_evil(secrets, "beats") => List(fuzzy) |
cdfa6a293453
updated solutions and templates
Christian Urban <christian.urban@kcl.ac.uk>
parents:
426
diff
changeset
|
277 |
%ranked_evil(secrets, "vitae") => List(fuzzy) |
cdfa6a293453
updated solutions and templates
Christian Urban <christian.urban@kcl.ac.uk>
parents:
426
diff
changeset
|
278 |
%ranked_evil(secrets, "bento") => List(fuzzy) |
cdfa6a293453
updated solutions and templates
Christian Urban <christian.urban@kcl.ac.uk>
parents:
426
diff
changeset
|
279 |
%ranked_evil(secrets, "belts") => List(fuzzy) |
cdfa6a293453
updated solutions and templates
Christian Urban <christian.urban@kcl.ac.uk>
parents:
426
diff
changeset
|
280 |
%\end{lstlisting} |
cdfa6a293453
updated solutions and templates
Christian Urban <christian.urban@kcl.ac.uk>
parents:
426
diff
changeset
|
281 |
% |
cdfa6a293453
updated solutions and templates
Christian Urban <christian.urban@kcl.ac.uk>
parents:
426
diff
changeset
|
282 |
%\noindent \textcolor{red}{Some further testcases for the maximum are:} |
cdfa6a293453
updated solutions and templates
Christian Urban <christian.urban@kcl.ac.uk>
parents:
426
diff
changeset
|
283 |
% |
cdfa6a293453
updated solutions and templates
Christian Urban <christian.urban@kcl.ac.uk>
parents:
426
diff
changeset
|
284 |
%\begin{lstlisting}[numbers=none] |
cdfa6a293453
updated solutions and templates
Christian Urban <christian.urban@kcl.ac.uk>
parents:
426
diff
changeset
|
285 |
%ranked_evil(secrets, "abbey") => List(whizz) |
cdfa6a293453
updated solutions and templates
Christian Urban <christian.urban@kcl.ac.uk>
parents:
426
diff
changeset
|
286 |
%ranked_evil(secrets, "afear") => List(buzzy) |
cdfa6a293453
updated solutions and templates
Christian Urban <christian.urban@kcl.ac.uk>
parents:
426
diff
changeset
|
287 |
%ranked_evil(secrets, "zincy") => List(jugum) |
cdfa6a293453
updated solutions and templates
Christian Urban <christian.urban@kcl.ac.uk>
parents:
426
diff
changeset
|
288 |
%ranked_evil(secrets, "zippy") => List(chuff) |
cdfa6a293453
updated solutions and templates
Christian Urban <christian.urban@kcl.ac.uk>
parents:
426
diff
changeset
|
289 |
%\end{lstlisting} |
cdfa6a293453
updated solutions and templates
Christian Urban <christian.urban@kcl.ac.uk>
parents:
426
diff
changeset
|
290 |
% |
cdfa6a293453
updated solutions and templates
Christian Urban <christian.urban@kcl.ac.uk>
parents:
426
diff
changeset
|
291 |
% |
349 | 292 |
|
428
cdfa6a293453
updated solutions and templates
Christian Urban <christian.urban@kcl.ac.uk>
parents:
426
diff
changeset
|
293 |
\mbox{}\hfill [1 Mark] |
203 | 294 |
\end{itemize} |
6 | 295 |
|
268 | 296 |
\end{document} |
6 | 297 |
|
298 |
%%% Local Variables: |
|
299 |
%%% mode: latex |
|
300 |
%%% TeX-master: t |
|
301 |
%%% End: |
|
349 | 302 |
|
303 |
||
304 |