Binary file cws/core_cw03.pdf has changed
--- a/cws/core_cw03.tex Thu Nov 02 13:53:37 2023 +0000
+++ b/cws/core_cw03.tex Thu Nov 02 23:34:53 2023 +0000
@@ -64,11 +64,11 @@
\subsection*{Core Part (3 Marks, files postfix.scala, postfix2.scala)}
-The \emph{Shunting Yard Algorithm} has been developed by Edsger Dijkstra,
+The \textit{Shunting Yard Algorithm} has been developed by Edsger Dijkstra,
an influential computer scientist who developed many well-known
algorithms. This algorithm transforms the usual infix notation of
arithmetic expressions into the postfix notation, sometimes also
-called reverse Polish notation.
+called \textit{Reverse Polish Notation}.
Why on Earth do people use the postfix notation? It is much more
convenient to work with the usual infix notation for arithmetic
@@ -92,9 +92,9 @@
\end{lstlisting}
\noindent
-where the command \texttt{ldc} loads a constant onto the stack, and \texttt{imul},
-\texttt{isub} and \texttt{iadd} are commands acting on the stack. Clearly this
-is the arithmetic expression in postfix notation.\bigskip
+where the command \texttt{ldc} loads a number onto the stack, and \texttt{imul},
+\texttt{isub} and \texttt{iadd} perform arithmetic operations on the stack. Clearly, this
+is the arithmetic expression from above but in postfix notation.\bigskip
\noindent
The shunting yard algorithm processes an input token list using an
@@ -123,7 +123,13 @@
processing the input list.
\item If the input is empty, then you move all remaining operators
from the stack to the output list.
-\end{itemize}
+\end{itemize}
+
+\noindent
+BTW, the rules above are written ``If\ldots'', but this is because English does not
+include very sophisticated pattern matching. But clearly the rules above should be implemented
+in Scala using pattern matching.
+
\subsubsection*{Tasks (file postfix.scala)}
Binary file cws/main_cw02.pdf has changed
--- a/cws/main_cw02.tex Thu Nov 02 13:53:37 2023 +0000
+++ b/cws/main_cw02.tex Thu Nov 02 23:34:53 2023 +0000
@@ -40,10 +40,10 @@
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
-the command line with the option \texttt{-cp wordle.jar} and then
+In addition, the Scala part comes with a reference
+implementation in form of \texttt{jar}-files. This allows you to run
+any test cases on your own computer. For example you can call \texttt{scala-cli} on
+the command line with the option \texttt{--extra-jars wordle.jar} and then
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
@@ -51,7 +51,7 @@
you would type something like:
\begin{lstlisting}[language={},numbers=none,basicstyle=\ttfamily\small]
-$ scala -cp wordle.jar
+$ scala-cli --extra-jars wordle.jar
scala> val secretsURL =
| """https://nms.kcl.ac.uk/christian.urban/wordle.txt"""
@@ -115,10 +115,8 @@
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}.
- }
+ 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
@@ -218,29 +216,8 @@
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]
+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
@@ -267,8 +244,8 @@
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
+ 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]
@@ -277,13 +254,6 @@
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.
@@ -299,14 +269,6 @@
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}}
Binary file cws/main_cw03.pdf has changed
--- a/cws/main_cw03.tex Thu Nov 02 13:53:37 2023 +0000
+++ b/cws/main_cw03.tex Thu Nov 02 23:34:53 2023 +0000
@@ -144,10 +144,10 @@
This Scala assignment comes with a reference implementation in form of
a \texttt{jar}-file. This allows you to run any test cases on your own
-computer. For example you can call Scala on the command line with the
-option \texttt{-cp re.jar} and then query any function from the
-\texttt{re.scala} template file. As usual you have to prefix the calls
-with \texttt{M3} or import this object. Since some tasks
+computer. For example you can call \texttt{scala-cli} on the command
+line with the option \texttt{--extra-jars re.jar} and then query any function
+from the \texttt{re.scala} template file. As usual you have to prefix
+the calls with \texttt{M3} or import this object. Since some tasks
are time sensitive, you can check the reference implementation as
follows: if you want to know, for example, how long it takes to match
strings of $a$'s using the regular expression $(a^*)^*\cdot b$ you can
@@ -155,7 +155,7 @@
\begin{lstlisting}[xleftmargin=1mm,numbers=none,basicstyle=\ttfamily\small]
-$ scala -cp re.jar
+$ scala-cli --extra-jars re.jar
scala> import M3._
scala> for (i <- 0 to 5000000 by 500000) {
| println(f"$i: ${time_needed(2, matcher(EVIL, "a" * i))}%.5f secs.")
@@ -343,7 +343,7 @@
$acc$. In the fourth case we spill out the $rs$ by appending the
$rs$ to the end of the accumulator. Similarly in the last case we
append the single regular expression $r$ to the end of the
- accumulator. I let you think why the ``end'' is needed. \mbox{}\hfill\mbox{[1 Mark]}
+ accumulator. I let you think why you have to add it to the end. \mbox{}\hfill\mbox{[1 Mark]}
\item[(5)] Before we can simplify regular expressions, we need what is often called
\emph{smart constructors} for $\sum$ and $\prod$. While the ``normal'' constructors
@@ -516,7 +516,7 @@
you have implemented. How long can a string of $a$'s be in your
matcher and still stay within the 30 seconds time limit? It should be
mu(uu)$^*$ch better than your off-the-shelf matcher in your
-bog-standard language.
+bog-standard programming language.
\begin{center}
\begin{tabular}{@{}cc@{}}
--- a/main_solution3/re.scala Thu Nov 02 13:53:37 2023 +0000
+++ b/main_solution3/re.scala Thu Nov 02 23:34:53 2023 +0000
@@ -3,7 +3,6 @@
object M3 {
-// Regular Expressions
abstract class Rexp
case object ZERO extends Rexp
case object ONE extends Rexp
@@ -18,30 +17,38 @@
def ALT(r1: Rexp, r2: Rexp) = ALTs(List(r1, r2))
def SEQ(r1: Rexp, r2: Rexp) = SEQs(List(r1, r2))
-// some convenience for typing in regular expressions
-import scala.language.implicitConversions
-import scala.language.reflectiveCalls
+
+// some convenience for typing regular expressions
def charlist2rexp(s: List[Char]): Rexp = s match {
case Nil => ONE
case c::Nil => CHAR(c)
case c::s => SEQ(CHAR(c), charlist2rexp(s))
}
-implicit def string2rexp(s: String): Rexp = charlist2rexp(s.toList)
+
+import scala.language.implicitConversions
-implicit def RexpOps (r: Rexp) = new {
+given Conversion[String, Rexp] = (s => charlist2rexp(s.toList))
+
+extension (r: Rexp) {
def | (s: Rexp) = ALT(r, s)
def % = STAR(r)
def ~ (s: Rexp) = SEQ(r, s)
}
-implicit def stringOps (s: String) = new {
- def | (r: Rexp) = ALT(s, r)
- def | (r: String) = ALT(s, r)
- def % = STAR(s)
- def ~ (r: Rexp) = SEQ(s, r)
- def ~ (r: String) = SEQ(s, r)
-}
+// some examples for the conversion and extension:
+
+// val areg : Rexp = "a" | "b"
+// => ALTs(List(CHAR('a'), CHAR('b')))
+//
+// val sreg : Rexp = "a" ~ "b"
+// => SEQs(List(CHAR('a'), CHAR('b')))
+//
+// val star_reg : Rexp = ("a" ~ "b").%
+// => STAR(SEQs(List(CHAR('a'), CHAR('b'))))
+
+// ADD YOUR CODE BELOW
+//======================
// (1)
def nullable (r: Rexp) : Boolean = r match {
@@ -194,8 +201,9 @@
-/*
-// if nullable(r1)
- ALTs(SEQs(der(c, r1)::rs)::(rs filter what is nullable) .map(der(c,_)))
-*/
+// This template code is subject to copyright
+// by King's College London, 2022. Do not
+// make the template code public in any shape
+// or form, and do not exchange it with other
+// students under any circumstance.
--- a/main_testing2/wordle.scala Thu Nov 02 13:53:37 2023 +0000
+++ b/main_testing2/wordle.scala Thu Nov 02 23:34:53 2023 +0000
@@ -9,45 +9,25 @@
// ADD YOUR CODE BELOW
//======================
-// def main(args: Array[String]): Unit = {
-// val secrets = get_wordle_list("https://nms.kcl.ac.uk/christian.urban/wordle.txt")
-// println(ranked_evil(secrets, "beats")== List("fuzzy"))
-// println(ranked_evil(secrets, "vitae") == List("fuzzy"))
-// println(ranked_evil(secrets, "bento") == List("fuzzy"))
-// println(ranked_evil(secrets, "belts") == List("fuzzy"))
-// println(ranked_evil(secrets, "abbey") == List("whizz"))
-// println(ranked_evil(secrets, "afear") == List("buzzy"))
-// println(ranked_evil(secrets, "zincy") == List("jugum"))
-// println(ranked_evil(secrets, "zippy") == List("chuff"))
-
-
-// }
//(1)
def get_wordle_list(url: String) : List[String] = {
- try {
- Source.fromURL(url).getLines.toList;
- }
- catch {
- case _ : Throwable => List();
- }
+ Try(Source.fromURL(url).getLines.toList).getOrElse(List())
}
+
// val secrets = get_wordle_list("https://nms.kcl.ac.uk/christian.urban/wordle.txt")
// secrets.length // => 12972
// secrets.filter(_.length != 5) // => Nil
-//(2)
-def removeN[A](xs: List[A], elem: A, n: Int) : List[A] = {
- if (xs.isEmpty || n == 0 || !xs.contains(elem)){
- xs
- }
- else{
- val (newLst,newLst2) = xs.splitAt(xs.indexOf(elem))
- removeN(newLst ++ newLst2.tail,elem, n-1)
- }
+//(2)
+def removeN[A](xs: List[A], elem: A, n: Int) : List[A] = xs match {
+ case Nil => Nil
+ case x :: tail if x == elem && n > 0 => removeN(tail, elem, n - 1)
+ case x :: tail => x :: removeN(tail, elem, n)
}
+
// removeN(List(1,2,3,2,1), 3, 1) // => 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), 1, 1) // => List(2, 3, 2, 1)
@@ -61,42 +41,19 @@
def pool(secret: String, word: String) : List[Char] = {
- //print(secret.toList, word.toList)
- val lst= ((0 to 4).map(x => {
- if(!secret(x).equals(word(x))) Some(secret(x)) else None
-
- }).toList)
- lst.flatten
+ (for(index <- (0 to word.length-1); if (word(index) != secret(index))) yield secret(index).toChar).toList
}
-
-
+// t
def aux(secret: List[Char], word: List[Char], pool: List[Char]) : List[Tip] = {
-
- if (secret.length == 1){
- if (secret.head == word.head){
- List(Correct)
- }
- else if (pool.contains(word.head)){
- List(Present)
- }
- else {
- List(Absent)
- }
- }
- else if (secret.head == word.head){
- List(Correct) ++ aux(secret.tail, word.tail, pool)
- }
- else if (pool.contains(word.head)){
- List(Present) ++ aux(secret.tail, word.tail, removeN(pool, word.head, 1))
- }
+ if (secret.isEmpty) List()
else {
- List(Absent) ++ aux(secret.tail, word.tail, pool)
+ if (secret.head == word.head) Correct :: aux(secret.tail, word.tail, pool)
+ else if (pool.contains(word.head)) Present :: aux(secret.tail, word.tail, pool.filterNot(_ == word.head))
+ else Absent :: aux(secret.tail, word.tail, pool)
}
}
-def score(secret: String, word: String) : List[Tip] = {
- aux(secret.toList,word.toList,pool(secret,word))
-}
+def score(secret: String, word: String) : List[Tip] = aux(secret.toList, word.toList, pool(secret, word))
// score("chess", "caves") // => List(Correct, Absent, Absent, Present, Correct)
@@ -105,38 +62,31 @@
// score("chess", "eexss") // => List(Present, Absent, Absent, Correct, Correct)
// (4)
-def eval(t: Tip) : Int = {
- if (t == Correct) 10
- else if (t == Present) 1
- else 0
+def eval(t: Tip) : Int = t match {
+ case Correct => 10
+ case Present => 1
+ case Absent => 0
}
-def iscore(secret: String, word: String) : Int = {
- val scoreList = score(secret,word)
- scoreList.map(x =>(eval(x))).toList.sum
-}
+def iscore(secret: String, word: String) : Int = (for(current <- score(secret, word)) yield eval(current)).sum
+
//iscore("chess", "caves") // => 21
//iscore("chess", "swiss") // => 20
-// (5)
+// (5) t
def lowest(secrets: List[String], word: String, current: Int, acc: List[String]) : List[String] = {
- if(secrets.isEmpty) acc
- else if (iscore(secrets.head,word)<current){
- lowest(secrets.tail, word, iscore(secrets.head,word), List(secrets.head))
+ if (secrets.isEmpty) acc
+ else {
+ val score = iscore(secrets.head, word)
+
+ if (score == current) lowest(secrets.tail, word, current, secrets.head :: acc)
+ else if (score < current) lowest(secrets.tail, word, score, List(secrets.head))
+ else lowest(secrets.tail, word, current, acc)
}
- else if (iscore(secrets.head,word)==current){
- lowest(secrets.tail, word, current, acc :+ secrets.head)
- }
- else {
- lowest(secrets.tail, word, current, acc)
- }
-
}
-def evil(secrets: List[String], word: String) = {
- lowest(secrets, word, 100, List())
-}
+def evil(secrets: List[String], word: String) = lowest(secrets, word, Int.MaxValue ,List())
//evil(secrets, "stent").length
@@ -145,26 +95,23 @@
//evil(secrets, "hoise").length
//evil(secrets, "house").length
-// (6)
+// (6) t
def frequencies(secrets: List[String]) : Map[Char, Double] = {
- val totalChar = secrets.flatMap(_.toList).size.toDouble
- val freqMap = secrets.flatMap(_.toList).groupBy(identity)
- freqMap.map(x => (x._1, (1-(x._2.size.toDouble/ totalChar))))
-
+ val occurrences = secrets.mkString.groupBy(identity).mapValues(_.length)
+ val all_letters = secrets.mkString.length.toDouble
+ occurrences.map{ case (c, n) => c -> (1 - n/all_letters) }.toMap
}
-// (7)
-def rank(frqs: Map[Char, Double], s: String) = {
- s.map(x => (frqs(x))).toList.sum
-}
-
-def ranked_evil(secrets: List[String], word: String) : List[String]= {
- val evilWords = evil(secrets,word)
- val returnVal = evilWords.map(x => (x, rank(frequencies(secrets),x))).toMap.maxBy(_._2)._1
- List(returnVal)
-}
+// (7)
+def rank(frqs: Map[Char, Double], s: String) : Double = s.map(c => frqs(c)).sum
+def ranked_evil(secrets: List[String], word: String): List[String] = {
+ val frqs = frequencies(secrets)
+ val ranked_secrets = evil(secrets, word).map(s => (s, rank(frqs, s)))
+ List((ranked_secrets.sortWith(_._2 > _._2)).map(_._1).head )
+}
+
}
--- a/main_testing2/wordle_test.sh Thu Nov 02 13:53:37 2023 +0000
+++ b/main_testing2/wordle_test.sh Thu Nov 02 23:34:53 2023 +0000
@@ -16,15 +16,15 @@
# compilation tests
function scala_compile {
- (ulimit -t 30; JAVA_OPTS="-Xmx1g" scala -Xprint:parser "$1" 2> c$out 1> c$out)
+ (ulimit -t 30; JAVA_OPTS="-Xmx1g" scala-cli compile "$1" 2> c$out 1> c$out)
}
# functional tests
function scala_assert {
- (ulimit -t 35; JAVA_OPTS="-Xmx1g" scala -nc -i "$1" -- "$2" -e "" 2> /dev/null 1> /dev/null)
+ (ulimit -t 30; JAVA_OPTS="-Xmx1g" scala-cli -i "$1" "$2" -e "urbanmain()" 2> /dev/null 1> /dev/null)
}
-
+
# purity test
function scala_vars {
(sed 's/immutable/ok/g' c$out > cb$out;
@@ -42,6 +42,7 @@
tsts0=$(( 0 ))
else
echo -e " --> SCALA DID NOT RUN wordle.scala\n" >> $out
+ echo -e " --> try running scala-cli compile wordle.scala on your own computer\n" >> $out
tsts0=$(( 1 ))
fi
--- a/main_testing2/wordle_test1.scala Thu Nov 02 13:53:37 2023 +0000
+++ b/main_testing2/wordle_test1.scala Thu Nov 02 23:34:53 2023 +0000
@@ -1,11 +1,12 @@
-import M2._
-
-val urban_wordle_url = """https://nms.kcl.ac.uk/christian.urban/wordle.txt"""
-val urban_secrets = get_wordle_list(urban_wordle_url)
+def urbanmain() = {
+ import M2._
-assert(urban_secrets.length == 12972)
-assert(urban_secrets.filter(_.length != 5) == Nil)
+ val urban_wordle_url = """https://nms.kcl.ac.uk/christian.urban/wordle.txt"""
+ val urban_secrets = get_wordle_list(urban_wordle_url)
-assert(get_wordle_list(urban_wordle_url ++ "2") == Nil)
+ assert(urban_secrets.length == 12972)
+ assert(urban_secrets.filter(_.length != 5) == Nil)
+ assert(get_wordle_list(urban_wordle_url ++ "2") == Nil)
+}
--- a/main_testing2/wordle_test2.scala Thu Nov 02 13:53:37 2023 +0000
+++ b/main_testing2/wordle_test2.scala Thu Nov 02 23:34:53 2023 +0000
@@ -1,17 +1,18 @@
-import M2._
+def urbanmain() = {
+ import M2._
-assert(removeN(List(1,2,3,2,1), 3, 1) == List(1, 2, 2, 1))
-assert(removeN(List(1,2,3,2,1), 2, 1) == List(1, 3, 2, 1))
-assert(removeN(List(1,2,3,2,1), 1, 1) == List(2, 3, 2, 1))
-assert(removeN(List(1,2,3,2,1), 0, 2) == List(1, 2, 3, 2, 1))
-assert(removeN(List("a", "b", "b"), "b", 1) == List("a", "b"))
-assert(removeN(List("b", "a", "b", "b"), "b", 2) == List("a", "b"))
-assert(removeN(List("b", "a", "b"), "a", 2) == List("b", "b"))
+ assert(removeN(List(1,2,3,2,1), 3, 1) == List(1, 2, 2, 1))
+ assert(removeN(List(1,2,3,2,1), 2, 1) == List(1, 3, 2, 1))
+ assert(removeN(List(1,2,3,2,1), 1, 1) == List(2, 3, 2, 1))
+ assert(removeN(List(1,2,3,2,1), 0, 2) == List(1, 2, 3, 2, 1))
+ assert(removeN(List("a", "b", "b"), "b", 1) == List("a", "b"))
+ assert(removeN(List("b", "a", "b", "b"), "b", 2) == List("a", "b"))
+ assert(removeN(List("b", "a", "b"), "a", 2) == List("b", "b"))
-//assert(removeOne(List(1,2,3,2,1), 3) == List(1, 2, 2, 1))
-//assert(removeOne(List(1,2,3,2,1), 2) == List(1, 3, 2, 1))
-//assert(removeOne(List(1,2,3,2,1), 1) == List(2, 3, 2, 1))
-//assert(removeOne(List(1,2,3,2,1), 0) == List(1, 2, 3, 2, 1))
-
+ //assert(removeOne(List(1,2,3,2,1), 3) == List(1, 2, 2, 1))
+ //assert(removeOne(List(1,2,3,2,1), 2) == List(1, 3, 2, 1))
+ //assert(removeOne(List(1,2,3,2,1), 1) == List(2, 3, 2, 1))
+ //assert(removeOne(List(1,2,3,2,1), 0) == List(1, 2, 3, 2, 1))
+}
--- a/main_testing2/wordle_test3a.scala Thu Nov 02 13:53:37 2023 +0000
+++ b/main_testing2/wordle_test3a.scala Thu Nov 02 23:34:53 2023 +0000
@@ -1,7 +1,9 @@
-
-import M2._
-
-assert(pool("chess", "caves").toSet == Set('h', 'e', 's'))
-assert(pool("chess", "swiss").toSet == Set('c', 'h', 'e'))
+def urbanmain() = {
+ import M2._
+
+ assert(pool("chess", "caves").toSet == Set('h', 'e', 's'))
+ assert(pool("chess", "swiss").toSet == Set('c', 'h', 'e'))
+}
+
--- a/main_testing2/wordle_test3b.scala Thu Nov 02 13:53:37 2023 +0000
+++ b/main_testing2/wordle_test3b.scala Thu Nov 02 23:34:53 2023 +0000
@@ -1,12 +1,14 @@
-import M2._
+def urbanmain() = {
+ import M2._
-assert(score("chess", "caves") == List(Correct, Absent, Absent, Present, Correct))
-assert(score("doses", "slide") == List(Present, Absent, Absent, Present, Present))
-assert(score("chess", "swiss") == List(Absent, Absent, Absent, Correct, Correct))
-assert(score("chess", "eexss") == List(Present, Absent, Absent, Correct, Correct))
+ assert(score("chess", "caves") == List(Correct, Absent, Absent, Present, Correct))
+ assert(score("doses", "slide") == List(Present, Absent, Absent, Present, Present))
+ assert(score("chess", "swiss") == List(Absent, Absent, Absent, Correct, Correct))
+ assert(score("chess", "eexss") == List(Present, Absent, Absent, Correct, Correct))
-val urban_p = pool("chess", "caves")
+ val urban_p = pool("chess", "caves")
-assert(aux("chess".toList, "caves".toList, Nil) == List(Correct, Absent, Absent, Absent, Correct))
-assert(aux("chess".toList, "caves".toList, urban_p) == List(Correct, Absent, Absent, Present, Correct))
+ assert(aux("chess".toList, "caves".toList, Nil) == List(Correct, Absent, Absent, Absent, Correct))
+ assert(aux("chess".toList, "caves".toList, urban_p) == List(Correct, Absent, Absent, Present, Correct))
+}
--- a/main_testing2/wordle_test4.scala Thu Nov 02 13:53:37 2023 +0000
+++ b/main_testing2/wordle_test4.scala Thu Nov 02 23:34:53 2023 +0000
@@ -1,5 +1,7 @@
-import M2._
+def urbanmain() = {
+ import M2._
-assert(iscore("chess", "caves") == 21)
-assert(iscore("chess", "swiss") == 20)
+ assert(iscore("chess", "caves") == 21)
+ assert(iscore("chess", "swiss") == 20)
+}
--- a/main_testing2/wordle_test5.scala Thu Nov 02 13:53:37 2023 +0000
+++ b/main_testing2/wordle_test5.scala Thu Nov 02 23:34:53 2023 +0000
@@ -1,20 +1,21 @@
-import M2._
-import io.Source
+def urbanmain() = {
+ import M2._
+ import io.Source
-def urban_get_wordle_list(url: String) : List[String] = {
- Source.fromFile(url)("ISO-8859-1").getLines().toList
-}
-val urban_secrets = urban_get_wordle_list("wordle.txt")
+ def urban_get_wordle_list(url: String) : List[String] = {
+ Source.fromFile(url)("ISO-8859-1").getLines().toList
+ }
+ val urban_secrets = urban_get_wordle_list("wordle.txt")
-//val urban_wordle_url = """https://nms.kcl.ac.uk/christian.urban/wordle.txt"""
-//val urban_secrets = get_wordle_list(urban_wordle_url)
+ //val urban_wordle_url = """https://nms.kcl.ac.uk/christian.urban/wordle.txt"""
+ //val urban_secrets = get_wordle_list(urban_wordle_url)
-assert(evil(urban_secrets, "stent").length == 1907)
-assert(evil(urban_secrets, "hexes").length == 2966)
-assert(evil(urban_secrets, "horse").length == 1203)
-assert(evil(urban_secrets, "hoise").length == 971)
-assert(evil(urban_secrets, "house").length == 1228)
-
+ assert(evil(urban_secrets, "stent").length == 1907)
+ assert(evil(urban_secrets, "hexes").length == 2966)
+ assert(evil(urban_secrets, "horse").length == 1203)
+ assert(evil(urban_secrets, "hoise").length == 971)
+ assert(evil(urban_secrets, "house").length == 1228)
+}
--- a/main_testing2/wordle_test6.scala Thu Nov 02 13:53:37 2023 +0000
+++ b/main_testing2/wordle_test6.scala Thu Nov 02 23:34:53 2023 +0000
@@ -1,18 +1,20 @@
-import M2._
-import io.Source
+def urbanmain() = {
+ import M2._
+
+ import io.Source
-def urban_get_wordle_list(url: String) : List[String] = {
- Source.fromFile(url)("ISO-8859-1").getLines().toList
-}
-val urban_secrets = urban_get_wordle_list("wordle.txt")
+ def urban_get_wordle_list(url: String) : List[String] = {
+ Source.fromFile(url)("ISO-8859-1").getLines().toList
+ }
+ val urban_secrets = urban_get_wordle_list("wordle.txt")
-//val urban_wordle_url = """https://nms.kcl.ac.uk/christian.urban/wordle.txt"""
-//val urban_secrets = get_wordle_list(urban_wordle_url)
+ //val urban_wordle_url = """https://nms.kcl.ac.uk/christian.urban/wordle.txt"""
+ //val urban_secrets = get_wordle_list(urban_wordle_url)
-assert(frequencies(urban_secrets)('y') == 0.9680234350909651)
-assert(frequencies(urban_secrets)('e') == 0.897286463151403)
-assert(frequencies(urban_secrets)('z') == 0.9933086648165279)
-
+ assert(frequencies(urban_secrets)('y') == 0.9680234350909651)
+ assert(frequencies(urban_secrets)('e') == 0.897286463151403)
+ assert(frequencies(urban_secrets)('z') == 0.9933086648165279)
+}
--- a/main_testing2/wordle_test7.scala Thu Nov 02 13:53:37 2023 +0000
+++ b/main_testing2/wordle_test7.scala Thu Nov 02 23:34:53 2023 +0000
@@ -1,25 +1,28 @@
-
-import M2._
-
-import io.Source
-def urban_get_wordle_list(url: String) : List[String] = {
- Source.fromFile(url)("ISO-8859-1").getLines().toList
-}
-val urban_secrets = urban_get_wordle_list("wordle.txt")
+def urbanmain() = {
+ import M2._
+
+ import io.Source
+
+
+ def urban_get_wordle_list(url: String) : List[String] = {
+ Source.fromFile(url)("ISO-8859-1").getLines().toList
+ }
+ val urban_secrets = urban_get_wordle_list("wordle.txt")
-//val urban_wordle_url = """https://nms.kcl.ac.uk/christian.urban/wordle.txt"""
-//val urban_secrets = get_wordle_list(urban_wordle_url)
+ //val urban_wordle_url = """https://nms.kcl.ac.uk/christian.urban/wordle.txt"""
+ //val urban_secrets = get_wordle_list(urban_wordle_url)
-assert(ranked_evil(urban_secrets, "abbey") == List("whizz"))
-assert(ranked_evil(urban_secrets, "afear") == List("buzzy"))
-assert(ranked_evil(urban_secrets, "zincy") == List("jugum"))
-assert(ranked_evil(urban_secrets, "zippy") == List("chuff"))
+ assert(ranked_evil(urban_secrets, "abbey") == List("whizz"))
+ assert(ranked_evil(urban_secrets, "afear") == List("buzzy"))
+ assert(ranked_evil(urban_secrets, "zincy") == List("jugum"))
+ assert(ranked_evil(urban_secrets, "zippy") == List("chuff"))
-assert(ranked_evil(urban_secrets, "beats") == List("fuzzy"))
-assert(ranked_evil(urban_secrets, "vitae") == List("fuzzy"))
-assert(ranked_evil(urban_secrets, "bento") == List("fuzzy"))
-assert(ranked_evil(urban_secrets, "belts") == List("fuzzy"))
+ assert(ranked_evil(urban_secrets, "beats") == List("fuzzy"))
+ assert(ranked_evil(urban_secrets, "vitae") == List("fuzzy"))
+ assert(ranked_evil(urban_secrets, "bento") == List("fuzzy"))
+ assert(ranked_evil(urban_secrets, "belts") == List("fuzzy"))
+}
--- a/main_testing3/re.scala Thu Nov 02 13:53:37 2023 +0000
+++ b/main_testing3/re.scala Thu Nov 02 23:34:53 2023 +0000
@@ -19,240 +19,159 @@
// some convenience for typing regular expressions
-import scala.language.implicitConversions
-import scala.language.reflectiveCalls
def charlist2rexp(s: List[Char]): Rexp = s match {
case Nil => ONE
case c::Nil => CHAR(c)
case c::s => SEQ(CHAR(c), charlist2rexp(s))
}
-implicit def string2rexp(s: String): Rexp = charlist2rexp(s.toList)
+
+import scala.language.implicitConversions
-implicit def RexpOps (r: Rexp) = new {
+given Conversion[String, Rexp] = (s => charlist2rexp(s.toList))
+
+extension (r: Rexp) {
def | (s: Rexp) = ALT(r, s)
def % = STAR(r)
def ~ (s: Rexp) = SEQ(r, s)
}
-implicit def stringOps (s: String) = new {
- def | (r: Rexp) = ALT(s, r)
- def | (r: String) = ALT(s, r)
- def % = STAR(s)
- def ~ (r: Rexp) = SEQ(s, r)
- def ~ (r: String) = SEQ(s, r)
-}
+// some examples for the conversion and extension:
-// examples for the implicits:
-// ALT(CHAR('a'), CHAR('b'))
// val areg : Rexp = "a" | "b"
-
-// SEQ(CHAR('a'), CHAR('b'))
+// => ALTs(List(CHAR('a'), CHAR('b')))
+//
// val sreg : Rexp = "a" ~ "b"
-
+// => SEQs(List(CHAR('a'), CHAR('b')))
+//
+// val star_reg : Rexp = ("a" ~ "b").%
+// => STAR(SEQs(List(CHAR('a'), CHAR('b'))))
// ADD YOUR CODE BELOW
//======================
-// (1)
+// (1)
def nullable (r: Rexp) : Boolean = r match {
- case ZERO => false
- case ONE => true
- case CHAR(_) => false
- case ALTs(rs) => (for(reg <- rs) yield nullable(reg)).exists(_ == true)
- case SEQs(rs) => (for(reg <- rs) yield nullable(reg)).forall(_ == true)
- case STAR(_) => true
+ case ZERO => false
+ case ONE => true
+ case CHAR(_) => false
+ case ALTs(rs) => rs.exists(nullable)
+ case SEQs(rs) => rs.forall(nullable)
+ case STAR(_) => true
}
-/*
-nullable(ZERO) == false
-nullable(ONE) == true
-nullable(CHAR('a')) == false
-nullable(ZERO | ONE) == true
-nullable(ZERO | CHAR('a')) == false
-nullable(ONE ~ ONE) == true
-nullable(ONE ~ CHAR('a')) == false
-nullable(STAR(ZERO)) == true
-nullable(ALTs(List(ONE, CHAR('a'), ZERO))) == true
-nullable(SEQs(List(ONE, ALTs(List(ONE, CHAR('a'), ZERO)), STAR(ZERO)))) == true
-*/
-
// (2)
-def der (c: Char, r: Rexp) : Rexp = r match {
- case ZERO => ZERO
- case ONE => ZERO
- case CHAR(d) => if(c == d) ONE else ZERO
- case ALTs(rs) => ALTs(for(reg <- rs) yield der(c, reg))
- case SEQs(Nil) => ZERO
- case SEQs(r :: rs) => if(nullable(r)) ALT(SEQs(der(c, r) :: rs), der(c, SEQs(rs))) else SEQs(der(c, r) :: rs)
- case STAR(r) => SEQ(der(c,r), STAR(r))
+def der(c: Char, r: Rexp) : Rexp = r match {
+ case ZERO => ZERO
+ case ONE => ZERO
+ case CHAR(d) => if (c == d) ONE else ZERO
+ case ALTs(rs) => ALTs(rs.map(der(c, _)))
+ case SEQs(Nil) => ZERO
+ case SEQs(r1::rs) =>
+ if (nullable(r1)) ALT(SEQs(der(c, r1)::rs), der(c, SEQs(rs)))
+ else SEQs(der(c, r1) :: rs)
+ case STAR(r1) => SEQ(der(c, r1), STAR(r1))
}
-/*
-der('a', ZERO | ONE) == (ZERO | ZERO)
-der('a', (CHAR('a') | ONE) ~ CHAR('a')) == ALT((ONE | ZERO) ~ CHAR('a'), SEQs(List(ONE)))
-der('a', (CHAR('a') | CHAR('a')) ~ CHAR('a')) == (ONE | ONE) ~ CHAR('a')
-der('a', STAR(CHAR('a'))) == (ONE ~ STAR(CHAR('a')))
-der('b', STAR(CHAR('a'))) == (ZERO ~ STAR(CHAR('a')))
-*/
// (3)
def denest(rs: List[Rexp]) : List[Rexp] = rs match {
- case Nil => Nil
- case ZERO :: rest => denest(rest)
- case ALTs(rgs) :: rest => rgs ::: denest(rest)
- case r :: rest => r :: denest(rest)
+ case Nil => Nil
+ case ZERO::tl => denest(tl)
+ case ALTs(rs1)::rs2 => rs1 ::: denest(rs2)
+ case r::rs => r :: denest(rs)
}
-/*
-denest(List(ONE, ZERO, ALTs(List(ONE, CHAR('a'))))) == List(ONE, ONE, CHAR('a'))
-denest(List(ONE ~ ONE, ZERO, ZERO | ONE)) == List(ONE ~ ONE, ZERO, ONE)
-*/
-
// (4)
def flts(rs: List[Rexp], acc: List[Rexp] = Nil) : List[Rexp] = rs match {
- case Nil => acc
- case ZERO :: rest => List(ZERO)
- case ONE :: rest => flts(rest, acc)
- case SEQs(rgs) :: rest => flts(rest, acc ::: rgs)
- case r :: rest => flts(rest, acc ::: List(r))
+ case Nil => acc
+ case ZERO::rs => ZERO::Nil
+ case ONE::rs => flts(rs, acc)
+ case SEQs(rs1)::rs => flts(rs, acc ::: rs1)
+ case r::rs => flts(rs, acc :+ r)
}
-/*
-flts(List(CHAR('a'), ZERO, ONE), Nil) == List(ZERO)
-flts(List(CHAR('a'), ONE, ONE, CHAR('b')), Nil) == List(CHAR('a'), CHAR('b'))
-flts(List(ONE ~ CHAR('a'), CHAR('b') ~ ONE), Nil) == List(ONE, CHAR('a'), CHAR('b'), ONE)
-*/
-
// (5)
def ALTs_smart(rs: List[Rexp]) : Rexp = rs match {
- case Nil => ZERO
- case List(r) => r
- case _ => ALTs(rs)
+ case Nil => ZERO
+ case r::Nil => r
+ case rs => ALTs(rs)
}
def SEQs_smart(rs: List[Rexp]) : Rexp = rs match {
- case Nil => ONE
- case List(r) => r
- case _ => SEQs(rs)
+ case Nil => ONE
+ case ZERO::Nil => ZERO
+ case r::Nil => r
+ case rs => SEQs(rs)
}
-/*
-SEQs_smart(Nil) == ONE
-SEQs_smart(List(ZERO)) == ZERO
-SEQs_smart(List(CHAR('a'))) == CHAR('a')
-SEQs_smart(List(ONE ~ ONE)) == ONE ~ ONE
-SEQs_smart(List(ONE, ONE)) == SEQs(List(ONE, ONE))
-ALTs_smart(Nil) == ZERO
-ALTs_smart(List(ONE ~ ONE)) == ONE ~ ONE
-ALTs_smart(List(ZERO, ZERO)) == ALTs(List(ZERO, ZERO))
-*/
+// (6)
-// (6)
def simp(r: Rexp) : Rexp = r match {
- case ALTs(rs) => ALTs_smart(denest(for(reg <- rs) yield simp(reg)).distinct)
- case SEQs(rs) => SEQs_smart(flts(for(reg <- rs) yield simp(reg)))
- case _ => r
+ case ALTs(rs) =>
+ ALTs_smart(denest(rs.map(simp)).distinct)
+ case SEQs(rs) =>
+ SEQs_smart(flts(rs.map(simp)))
+ case r => r
}
-/*
-simp(ZERO | ONE) == ONE
-simp(STAR(ZERO | ONE)) == STAR(ZERO | ONE)
-simp(ONE ~ (ONE ~ (ONE ~ CHAR('a')))) == CHAR('a')
-simp(((ONE ~ ONE) ~ ONE) ~ CHAR('a')) == CHAR('a')
-simp(((ONE | ONE) ~ ONE) ~ CHAR('a')) == CHAR('a')
-simp(ONE ~ (ONE ~ (ONE ~ ZERO))) == ZERO
-simp(ALT(ONE ~ (ONE ~ (ONE ~ ZERO)), CHAR('a'))) == CHAR('a')
-simp(CHAR('a') | CHAR('a')) == CHAR('a')
-simp(CHAR('a') ~ CHAR('a')) == CHAR('a') ~ CHAR('a')
-simp(ONE | CHAR('a')) == (ONE | CHAR('a'))
-simp(ALT((CHAR('a') | ZERO) ~ ONE,((ONE | CHAR('b')) | CHAR('c')) ~ (CHAR('d') ~ ZERO))) == CHAR('a')
-simp((ZERO | ((ZERO | ZERO) | (ZERO | ZERO))) ~ ((ONE | ZERO) | ONE ) ~ (CHAR('a'))) == ZERO
-simp(ALT(ONE | ONE, ONE | ONE)) == ONE
-simp(ALT(ZERO | CHAR('a'), CHAR('a') | ZERO)) == CHAR('a')
-simp(ALT(ONE | CHAR('a'), CHAR('a') | ONE)) == ALT(ONE, CHAR('a'))
-simp(ALTs(Nil)) == ZERO
-simp(SEQs(List(CHAR('a')))) == CHAR('a')
-*/
+//println("Simp tests")
+//println(simp(ALT(ONE | CHAR('a'), CHAR('a') | ONE)))
+//println(simp(((CHAR('a') | ZERO) ~ ONE) |
+// (((ONE | CHAR('b')) | CHAR('c')) ~ (CHAR('d') ~ ZERO))))
-// (7)
+// (7)
+
def ders (s: List[Char], r: Rexp) : Rexp = s match {
- case Nil => r
- case c :: cs => ders(cs, simp(der(c, r)))
-}
-def matcher(r: Rexp, s: String): Boolean = {
- val derivatives = ders(s.toList, r)
- nullable(derivatives)
+ case Nil => r
+ case c::s => ders(s, simp(der(c, r)))
}
-/*
-val EVIL = SEQ(STAR(STAR(CHAR('a'))), CHAR('b'))
-ders("aaaaa".toList, EVIL) == SEQs(List(STAR(CHAR('a')), STAR(STAR(CHAR('a'))), CHAR('b')))
-ders(List('b'), EVIL) == ONE
-ders("bb".toList, EVIL) == ZERO
-matcher(EVIL, "a" * 5 ++ "b") == true
-matcher(EVIL, "b") == true
-matcher(EVIL, "bb") == false
-matcher("abc", "abc") == true
-matcher(("ab" | "a") ~ (ONE | "bc"), "abc") == true
-matcher(ONE, "") == true
-matcher(ZERO, "") == false
-matcher(ONE | CHAR('a'), "") == true
-matcher(ONE | CHAR('a'), "a") == true
-*/
+// main matcher function
+def matcher(r: Rexp, s: String) = nullable(ders(s.toList, r))
// (8)
+
def size(r: Rexp): Int = r match {
- case ZERO => 1
- case ONE => 1
- case CHAR(_) => 1
- case ALTs(rs) => 1 + (for(reg <- rs) yield size(reg)).sum
- case SEQs(rs) => 1 + (for(reg <- rs) yield size(reg)).sum
- case STAR(r) => 1 + size(r)
+ case ZERO => 1
+ case ONE => 1
+ case CHAR(_) => 1
+ case ALTs(rs) => 1 + rs.map(size).sum
+ case SEQs(rs) => 1 + rs.map(size).sum
+ case STAR(r1) => 1 + size(r1)
}
-/*
-val EVIL = SEQ(STAR(STAR(CHAR('a'))), CHAR('b'))
-size(der('a', der('a', EVIL))) == 36
-size(der('a', der('a', der('a', EVIL)))) == 83
-size(ders("aaaaaa".toList, EVIL)) == 7
-size(ders(("a" * 50).toList, EVIL)) == 7
-*/
-// Some testing data
-//===================
+// some testing data
/*
-
-simp(ALT(ONE | CHAR('a'), CHAR('a') | ONE)) // => ALTs(List(ONE, CHAR(a)))
-simp(((CHAR('a') | ZERO) ~ ONE) | (((ONE | CHAR('b')) | CHAR('c')) ~ (CHAR('d') ~ ZERO))) // => CHAR(a)
-
-matcher(("a" ~ "b") ~ "c", "ab") // => false
-matcher(("a" ~ "b") ~ "c", "abc") // => true
-
+println(matcher(("a" ~ "b") ~ "c", "abc")) // => true
+println(matcher(("a" ~ "b") ~ "c", "ab")) // => false
// the supposedly 'evil' regular expression (a*)* b
val EVIL = SEQ(STAR(STAR(CHAR('a'))), CHAR('b'))
-matcher(EVIL, "a" * 1000) // => false
-matcher(EVIL, "a" * 1000 ++ "b") // => true
-
+println(matcher(EVIL, "a" * 1000 ++ "b")) // => true
+println(matcher(EVIL, "a" * 1000)) // => false
// size without simplifications
-size(der('a', der('a', EVIL))) // => 36
-size(der('a', der('a', der('a', EVIL)))) // => 83
+println(size(der('a', der('a', EVIL)))) // => 36
+println(size(der('a', der('a', der('a', EVIL))))) // => 83
// size with simplification
-size(simp(der('a', der('a', EVIL)))) // => 7
-size(simp(der('a', der('a', der('a', EVIL))))) // => 7
+println(simp(der('a', der('a', EVIL))))
+println(simp(der('a', der('a', der('a', EVIL)))))
+
+println(size(simp(der('a', der('a', EVIL))))) // => 7
+println(size(simp(der('a', der('a', der('a', EVIL)))))) // => 7
// Python needs around 30 seconds for matching 28 a's with EVIL.
// Java 9 and later increase this to an "astonishing" 40000 a's in
-// 30 seconds.
+// around 30 seconds.
//
-// Lets see how long it really takes to match strings with
-// 5 Million a's...it should be in the range of a few
-// of seconds.
+// Lets see how long it takes to match strings with
+// 5 Million a's...it should be in the range of a
+// few seconds.
def time_needed[T](i: Int, code: => T) = {
val start = System.nanoTime()
@@ -266,15 +185,15 @@
}
// another "power" test case
-simp(Iterator.iterate(ONE:Rexp)(r => SEQ(r, ONE | ONE)).drop(50).next()) == ONE
+println(simp(Iterator.iterate(ONE:Rexp)(r => SEQ(r, ONE | ONE)).drop(100).next()) == ONE)
// the Iterator produces the rexp
//
// SEQ(SEQ(SEQ(..., ONE | ONE) , ONE | ONE), ONE | ONE)
//
-// where SEQ is nested 50 times.
+// where SEQ is nested 100 times.
+*/
-*/
}
--- a/main_testing3/re_test.sh Thu Nov 02 13:53:37 2023 +0000
+++ b/main_testing3/re_test.sh Thu Nov 02 23:34:53 2023 +0000
@@ -13,24 +13,22 @@
# compilation tests
function scala_compile {
- (ulimit -t 30; JAVA_OPTS="-Xmx1g" scala -Xprint:parser "$1" 2> c$out 1> c$out)
+ (ulimit -t 30; JAVA_OPTS="-Xmx1g" scala-cli compile "$1" 2> c$out 1> c$out)
}
# functional tests
function scala_assert {
- (ulimit -t 30; JAVA_OPTS="-Xmx1g" scala -nc -i "$1" -- "$2" -e "" 2> /dev/null 1> /dev/null)
+ (ulimit -t 30; JAVA_OPTS="-Xmx1g" scala-cli -i "$1" "$2" -e "urbanmain()" 2> /dev/null 1> /dev/null)
}
# purity test
-
function scala_vars {
- (sed 's/immutable/ok/g' c$out > cb$out;
- egrep '\bvar\b|\breturn\b|\.par\.|\.par |ListBuffer|AtomicInteger|mutable|util.control|new Array' cb$out 2> /dev/null 1> /dev/null)
+ (sed 's/immutable/ok/g' c$out > cb$out;
+ egrep '\bvar\b|\breturn\b|\.par\.|\.par |ListBuffer|AtomicInteger|mutable|util.control|new Array' cb$out 2> /dev/null 1> /dev/null)
}
-
# compilation test
echo -e "re.scala runs?" >> $out
@@ -41,8 +39,6 @@
tsts=$(( 0 ))
else
echo -e " --> SCALA DID NOT RUN RE.SCALA\n" >> $out
- echo -e " !!!! Have you checked that you are using Scala 2.13.XX (preferably with XX == 10)? !!!\n" >> $out
- echo -e " !!!! All help-requests and emails where the problems are due to the use of Scala 3 will be quietly ingnored !!!\n" >> $out
tsts=$(( 1 ))
fi
--- a/main_testing3/re_test0.scala Thu Nov 02 13:53:37 2023 +0000
+++ b/main_testing3/re_test0.scala Thu Nov 02 23:34:53 2023 +0000
@@ -1,6 +1,9 @@
-import M3._
-
-assert(ALTs.getClass == ALTs.getClass)
-assert(SEQs.getClass == SEQs.getClass)
+def urbanmain() = {
+ import M3._
+
+ assert(ALTs.getClass == ALTs.getClass)
+ assert(SEQs.getClass == SEQs.getClass)
+}
+
--- a/main_testing3/re_test1.scala Thu Nov 02 13:53:37 2023 +0000
+++ b/main_testing3/re_test1.scala Thu Nov 02 23:34:53 2023 +0000
@@ -1,13 +1,16 @@
-import M3._
+
+
+def urbanmain() = {
+ import M3._
-assert(nullable(ZERO) == false)
-assert(nullable(ONE) == true)
-assert(nullable(CHAR('a')) == false)
-assert(nullable(ZERO | ONE) == true)
-assert(nullable(ZERO | CHAR('a')) == false)
-assert(nullable(ONE ~ ONE) == true)
-assert(nullable(ONE ~ CHAR('a')) == false)
-assert(nullable(STAR(ZERO)) == true)
-assert(nullable(ALTs(List(ONE, CHAR('a'), ZERO))) == true)
-assert(nullable(SEQs(List(ONE, ALTs(List(ONE, CHAR('a'), ZERO)), STAR(ZERO)))) == true)
-
+ assert(nullable(ZERO) == false)
+ assert(nullable(ONE) == true)
+ assert(nullable(CHAR('a')) == false)
+ assert(nullable(ZERO | ONE) == true)
+ assert(nullable(ZERO | CHAR('a')) == false)
+ assert(nullable(ONE ~ ONE) == true)
+ assert(nullable(ONE ~ CHAR('a')) == false)
+ assert(nullable(STAR(ZERO)) == true)
+ assert(nullable(ALTs(List(ONE, CHAR('a'), ZERO))) == true)
+ assert(nullable(SEQs(List(ONE, ALTs(List(ONE, CHAR('a'), ZERO)), STAR(ZERO)))) == true)
+}
--- a/main_testing3/re_test2.scala Thu Nov 02 13:53:37 2023 +0000
+++ b/main_testing3/re_test2.scala Thu Nov 02 23:34:53 2023 +0000
@@ -1,10 +1,14 @@
-import M3._
+
+def urbanmain() = {
+ import M3._
-assert(der('a', ZERO | ONE) == ALT(ZERO, ZERO))
-assert(der('a', (CHAR('a') | ONE) ~ CHAR('a')) == ALTs(List(SEQ(ALT(ONE, ZERO), CHAR('a')), SEQs(List(ONE)))))
-assert(der('a', (CHAR('a') | CHAR('a')) ~ CHAR('a')) == (ONE | ONE) ~ CHAR('a'))
-assert(der('a', STAR(CHAR('a'))) == (ONE ~ STAR(CHAR('a'))))
-assert(der('b', STAR(CHAR('a'))) == (ZERO ~ STAR(CHAR('a'))))
+ assert(der('a', ZERO | ONE) == ALT(ZERO, ZERO))
+ assert(der('a', (CHAR('a') | ONE) ~ CHAR('a')) == ALTs(List(SEQ(ALT(ONE, ZERO), CHAR('a')), SEQs(List(ONE)))))
+ assert(der('a', (CHAR('a') | CHAR('a')) ~ CHAR('a')) == (ONE | ONE) ~ CHAR('a'))
+ assert(der('a', STAR(CHAR('a'))) == (ONE ~ STAR(CHAR('a'))))
+ assert(der('b', STAR(CHAR('a'))) == (ZERO ~ STAR(CHAR('a'))))
+}
+
/*
val r0_urban = "a" ~ "b" ~ "c"
--- a/main_testing3/re_test3.scala Thu Nov 02 13:53:37 2023 +0000
+++ b/main_testing3/re_test3.scala Thu Nov 02 23:34:53 2023 +0000
@@ -1,22 +1,25 @@
-import M3._
+
+def urbanmain() = {
+
+ import M3._
-assert(simp(ZERO | ONE) == ONE)
-assert(simp(STAR(ZERO | ONE)) == STAR(ZERO | ONE))
-assert(simp(ONE ~ (ONE ~ (ONE ~ CHAR('a')))) == CHAR('a'))
-assert(simp(((ONE ~ ONE) ~ ONE) ~ CHAR('a')) == CHAR('a'))
-assert(simp(((ONE | ONE) ~ ONE) ~ CHAR('a')) == CHAR('a'))
-assert(simp(ONE ~ (ONE ~ (ONE ~ ZERO))) == ZERO)
-assert(simp(ALT(ONE ~ (ONE ~ (ONE ~ ZERO)), CHAR('a'))) == CHAR('a'))
-assert(simp(CHAR('a') | CHAR('a')) == CHAR('a'))
-assert(simp(CHAR('a') ~ CHAR('a')) == CHAR('a') ~ CHAR('a'))
-assert(simp(ONE | CHAR('a')) == (ONE | CHAR('a')))
-assert(simp(ALT((CHAR('a') | ZERO) ~ ONE,
- ((ONE | CHAR('b')) | CHAR('c')) ~ (CHAR('d') ~ ZERO))) == CHAR('a'))
-assert(simp((ZERO | ((ZERO | ZERO) | (ZERO | ZERO))) ~ ((ONE | ZERO) | ONE ) ~ (CHAR('a'))) == ZERO)
-assert(simp(ALT(ONE | ONE, ONE | ONE)) == ONE)
-assert(simp(ALT(ZERO | CHAR('a'), CHAR('a') | ZERO)) == CHAR('a'))
-assert(simp(ALT(ONE | CHAR('a'), CHAR('a') | ONE)) == ALT(ONE, CHAR('a')))
-assert(simp(ALTs(Nil)) == ZERO)
-assert(simp(SEQs(List(CHAR('a')))) == CHAR('a'))
+ assert(simp(ZERO | ONE) == ONE)
+ assert(simp(STAR(ZERO | ONE)) == STAR(ZERO | ONE))
+ assert(simp(ONE ~ (ONE ~ (ONE ~ CHAR('a')))) == CHAR('a'))
+ assert(simp(((ONE ~ ONE) ~ ONE) ~ CHAR('a')) == CHAR('a'))
+ assert(simp(((ONE | ONE) ~ ONE) ~ CHAR('a')) == CHAR('a'))
+ assert(simp(ONE ~ (ONE ~ (ONE ~ ZERO))) == ZERO)
+ assert(simp(ALT(ONE ~ (ONE ~ (ONE ~ ZERO)), CHAR('a'))) == CHAR('a'))
+ assert(simp(CHAR('a') | CHAR('a')) == CHAR('a'))
+ assert(simp(CHAR('a') ~ CHAR('a')) == CHAR('a') ~ CHAR('a'))
+ assert(simp(ONE | CHAR('a')) == (ONE | CHAR('a')))
+ assert(simp(ALT((CHAR('a') | ZERO) ~ ONE, ((ONE | CHAR('b')) | CHAR('c')) ~ (CHAR('d') ~ ZERO))) == CHAR('a'))
+ assert(simp((ZERO | ((ZERO | ZERO) | (ZERO | ZERO))) ~ ((ONE | ZERO) | ONE ) ~ (CHAR('a'))) == ZERO)
+ assert(simp(ALT(ONE | ONE, ONE | ONE)) == ONE)
+ assert(simp(ALT(ZERO | CHAR('a'), CHAR('a') | ZERO)) == CHAR('a'))
+ assert(simp(ALT(ONE | CHAR('a'), CHAR('a') | ONE)) == ALT(ONE, CHAR('a')))
+ assert(simp(ALTs(Nil)) == ZERO)
+ assert(simp(SEQs(List(CHAR('a')))) == CHAR('a'))
+}
--- a/main_testing3/re_test4.scala Thu Nov 02 13:53:37 2023 +0000
+++ b/main_testing3/re_test4.scala Thu Nov 02 23:34:53 2023 +0000
@@ -1,5 +1,10 @@
-import M3._
+
+def urbanmain() = {
+
+ import M3._
-assert(denest(List(ONE, ZERO, ALTs(List(ONE, CHAR('a')))))
- == List(ONE, ONE, CHAR('a')))
-assert(denest(List(ONE ~ ONE, ZERO, ZERO | ONE)) == List(ONE ~ ONE, ZERO, ONE))
+ assert(denest(List(ONE, ZERO, ALTs(List(ONE, CHAR('a'))))) == List(ONE, ONE, CHAR('a')))
+ assert(denest(List(ONE ~ ONE, ZERO, ZERO | ONE)) == List(ONE ~ ONE, ZERO, ONE))
+
+
+}
--- a/main_testing3/re_test5.scala Thu Nov 02 13:53:37 2023 +0000
+++ b/main_testing3/re_test5.scala Thu Nov 02 23:34:53 2023 +0000
@@ -1,6 +1,11 @@
-import M3._
+
+def urbanmain() = {
+
+ import M3._
-assert(flts(List(CHAR('a'), ZERO, ONE), Nil) == List(ZERO))
-assert(flts(List(CHAR('a'), ONE, ONE, CHAR('b')), Nil) == List(CHAR('a'), CHAR('b')))
-assert(flts(List(ONE ~ CHAR('a'), CHAR('b') ~ ONE), Nil) == List(ONE, CHAR('a'), CHAR('b'), ONE))
+ assert(flts(List(CHAR('a'), ZERO, ONE), Nil) == List(ZERO))
+ assert(flts(List(CHAR('a'), ONE, ONE, CHAR('b')), Nil) == List(CHAR('a'), CHAR('b')))
+ assert(flts(List(ONE ~ CHAR('a'), CHAR('b') ~ ONE), Nil) == List(ONE, CHAR('a'), CHAR('b'), ONE))
+}
+
--- a/main_testing3/re_test6.scala Thu Nov 02 13:53:37 2023 +0000
+++ b/main_testing3/re_test6.scala Thu Nov 02 23:34:53 2023 +0000
@@ -1,10 +1,14 @@
-import M3._
+
+def urbanmain() = {
+
+ import M3._
-assert(SEQs_smart(Nil) == ONE)
-assert(SEQs_smart(List(ZERO)) == ZERO)
-assert(SEQs_smart(List(CHAR('a'))) == CHAR('a'))
-assert(SEQs_smart(List(ONE ~ ONE)) == ONE ~ ONE)
-assert(SEQs_smart(List(ONE, ONE)) == SEQs(List(ONE, ONE)))
-assert(ALTs_smart(Nil) == ZERO)
-assert(ALTs_smart(List(ONE ~ ONE)) == ONE ~ ONE)
-assert(ALTs_smart(List(ZERO, ZERO)) == ALTs(List(ZERO, ZERO)))
+ assert(SEQs_smart(Nil) == ONE)
+ assert(SEQs_smart(List(ZERO)) == ZERO)
+ assert(SEQs_smart(List(CHAR('a'))) == CHAR('a'))
+ assert(SEQs_smart(List(ONE ~ ONE)) == ONE ~ ONE)
+ assert(SEQs_smart(List(ONE, ONE)) == SEQs(List(ONE, ONE)))
+ assert(ALTs_smart(Nil) == ZERO)
+ assert(ALTs_smart(List(ONE ~ ONE)) == ONE ~ ONE)
+ assert(ALTs_smart(List(ZERO, ZERO)) == ALTs(List(ZERO, ZERO)))
+}
--- a/main_testing3/re_test7.scala Thu Nov 02 13:53:37 2023 +0000
+++ b/main_testing3/re_test7.scala Thu Nov 02 23:34:53 2023 +0000
@@ -1,19 +1,22 @@
-import M3._
-val EVIL_urban = SEQ(STAR(STAR(CHAR('a'))), CHAR('b'))
+def urbanmain() = {
+ import M3._
+
+ val EVIL_urban = SEQ(STAR(STAR(CHAR('a'))), CHAR('b'))
-assert(ders(("a" * 5).toList, EVIL_urban) == SEQs(List(STAR(CHAR('a')), STAR(STAR(CHAR('a'))), CHAR('b'))))
-assert(ders(List('b'), EVIL_urban) == ONE)
-assert(ders(List('b','b'), EVIL_urban) == ZERO)
-assert(matcher(EVIL_urban, "a" * 5 ++ "b") == true)
-assert(matcher(EVIL_urban, "a" * 50 ++ "b") == true)
-assert(matcher(EVIL_urban, "a" * 50) == false)
-assert(matcher(EVIL_urban, "b") == true)
-assert(matcher(EVIL_urban, "bb") == false)
-assert(matcher("abc", "abc") == true)
-assert(matcher("abc", "ab") == false)
-assert(matcher(("ab" | "a") ~ (ONE | "bc"), "abc") == true)
-assert(matcher(ONE, "") == true)
-assert(matcher(ZERO, "") == false)
-assert(matcher(ONE | CHAR('a'), "") == true)
-assert(matcher(ONE | CHAR('a'), "a") == true)
+ assert(ders(("a" * 5).toList, EVIL_urban) == SEQs(List(STAR(CHAR('a')), STAR(STAR(CHAR('a'))), CHAR('b'))))
+ assert(ders(List('b'), EVIL_urban) == ONE)
+ assert(ders(List('b','b'), EVIL_urban) == ZERO)
+ assert(matcher(EVIL_urban, "a" * 5 ++ "b") == true)
+ assert(matcher(EVIL_urban, "a" * 50 ++ "b") == true)
+ assert(matcher(EVIL_urban, "a" * 50) == false)
+ assert(matcher(EVIL_urban, "b") == true)
+ assert(matcher(EVIL_urban, "bb") == false)
+ assert(matcher("abc", "abc") == true)
+ assert(matcher("abc", "ab") == false)
+ assert(matcher(("ab" | "a") ~ (ONE | "bc"), "abc") == true)
+ assert(matcher(ONE, "") == true)
+ assert(matcher(ZERO, "") == false)
+ assert(matcher(ONE | CHAR('a'), "") == true)
+ assert(matcher(ONE | CHAR('a'), "a") == true)
+}
--- a/main_testing3/re_test8.scala Thu Nov 02 13:53:37 2023 +0000
+++ b/main_testing3/re_test8.scala Thu Nov 02 23:34:53 2023 +0000
@@ -1,8 +1,12 @@
-import M3._
-val EVIL_urban = SEQ(STAR(STAR(CHAR('a'))), CHAR('b'))
+
+def urbanmain() = {
+
+ import M3._
+ val EVIL_urban = SEQ(STAR(STAR(CHAR('a'))), CHAR('b'))
-assert(size(der('a', der('a', EVIL_urban))) == 36)
-assert(size(der('a', der('a', der('a', EVIL_urban)))) == 83)
+ assert(size(der('a', der('a', EVIL_urban))) == 36)
+ assert(size(der('a', der('a', der('a', EVIL_urban)))) == 83)
-assert(size(ders("aaaaaa".toList, EVIL_urban)) == 7)
-assert(size(ders(("a" * 50).toList, EVIL_urban)) == 7)
+ assert(size(ders("aaaaaa".toList, EVIL_urban)) == 7)
+ assert(size(ders(("a" * 50).toList, EVIL_urban)) == 7)
+}
--- a/main_testing3/re_test9.scala Thu Nov 02 13:53:37 2023 +0000
+++ b/main_testing3/re_test9.scala Thu Nov 02 23:34:53 2023 +0000
@@ -1,9 +1,13 @@
-import M3._
+
+def urbanmain() = {
-val EVIL_urban = SEQ(STAR(STAR(CHAR('a'))), CHAR('b'))
+ import M3._
+
+ val EVIL_urban = SEQ(STAR(STAR(CHAR('a'))), CHAR('b'))
-assert(simp(Iterator.iterate(ONE:Rexp)(r => SEQ(r, ONE | ONE)).drop(50).next) == ONE)
-assert(simp(Iterator.iterate(ONE:Rexp)(r => ALT(r, r)).drop(20).next) == ONE)
-assert(matcher(EVIL_urban, "a" * 1000000) == false)
-assert(matcher(EVIL_urban, "a" * 1000000 ++ "b") == true)
+ assert(simp(Iterator.iterate(ONE:Rexp)(r => SEQ(r, ONE | ONE)).drop(50).next) == ONE)
+ assert(simp(Iterator.iterate(ONE:Rexp)(r => ALT(r, r)).drop(20).next) == ONE)
+ assert(matcher(EVIL_urban, "a" * 1000000) == false)
+ assert(matcher(EVIL_urban, "a" * 1000000 ++ "b") == true)
+}
--- a/main_testing5/bf.scala Thu Nov 02 13:53:37 2023 +0000
+++ b/main_testing5/bf.scala Thu Nov 02 23:34:53 2023 +0000
@@ -1,164 +1,166 @@
-// Main Part 5 about an Interpreter for
-// the Brainf*** language
+// Core Part about an Interpreter for
+// the Brainf***++ language
//==============================================
+object M5a {
+
-object M5a {
-
-// representation of BF memory
+// representation of Bf memory
type Mem = Map[Int, Int]
+
+// (1) Write a function that takes a file name as argument and
+// and requests the corresponding file from disk. It Returns the
+// content of the file as a String. If the file does not exists,
+// the function should Return the empty string.
+
import io.Source
import scala.util._
-// ADD YOUR CODE BELOW
-//======================
-
-// (1)
-def load_bff(name: String) : String = {
- Try(Source.fromFile(name)("ISO-8859-1").mkString).getOrElse("")
-}
-
-// (2)
+def load_bff(name: String) : String =
+ Try(Source.fromFile(name)("ISO-8859-1").mkString).getOrElse("")
-def sread(mem: Mem, mp: Int) : Int = {
- Try(mem.apply(mp)).getOrElse(0)
-}
-
-def write(mem: Mem, mp: Int, v: Int) : Mem = {
- mem + (mp -> v)
-}
-
-// sread(Map(), 2) == 0
-// sread(Map(2 -> 1), 2) == 1
-// write(Map(), 1, 2) == Map(1 -> 2)
-// write(Map(1 -> 0), 1, 2) == Map(1 -> 2)
-// val current = sread(Map(2 -> 1), 2)
-// write(Map(2 -> 1), 2, current+1)
-
-// (3)
+// (2) Complete the functions for safely reading
+// and writing brainf***++ memory. Safely read should
+// Return the value stored in the Map for a given memory
+// pointer, provided it exists; otherwise it Returns 0. The
+// writing function generates a new Map with the
+// same data, except at the given memory pointer the
+// value v is stored.
-def jumpRight(prog: String, pc: Int, level: Int) : Int = prog.toList.apply(pc) match{
- case '[' => jumpRight(prog, pc+1, level+1)
- case ']' => level match {
- case 0 => pc+1
- case _ => if (pc+1 >= prog.length) prog.length else jumpRight(prog, pc+1, level-1)
- }
- case _ => if (pc+1 >= prog.length) prog.length else jumpRight(prog, pc+1, level)
-}
-def jumpLeft(prog: String, pc: Int, level: Int) : Int = prog.toList.apply(pc) match{
- case ']' => jumpLeft(prog, pc-1, level+1)
- case '[' => level match {
- case 0 => pc+1
- case _ => if (pc-1 < 0) -1 else jumpLeft(prog, pc-1, level-1)
- }
- case _ => if (pc-1 < 0) -1 else jumpLeft(prog, pc-1, level)
-}
+def sread(mem: Mem, mp: Int) : Int =
+ mem.getOrElse(mp, 0)
+
+def write(mem: Mem, mp: Int, v: Int) : Mem =
+ mem.updated(mp, v)
-// testcases
-// jumpRight("""--[..+>--],>,++""", 3, 0) // => 10
-// jumpLeft("""--[..+>--],>,++""", 8, 0) // => 3
-// jumpRight("""--[..[+>]--],>,++""", 3, 0) // => 12
-// jumpRight("""--[..[[-]+>[.]]--],>,++""", 3, 0) // => 18
-// jumpRight("""--[..[[-]+>[.]]--,>,++""", 3, 0) // => 22 (outside)
-// jumpLeft("""[******]***""", 7, 0) // => -1 (outside)
+// (3) Implement the two jumping instructions in the
+// brainf***++ language. In jumpRight, given a program and
+// a program counter move the program counter to the right
+// until after the *matching* ]-command. Similarly,
+// jumpLeft implements the move to the left to just after
+// the *matching* [-command.
+
+def jumpRight(prog: String, pc: Int, level: Int) : Int = {
+ if (prog.length <= pc) pc
+ else (prog(pc), level) match {
+ case (']', 0) => pc + 1
+ case (']', l) => jumpRight(prog, pc + 1, l - 1)
+ case ('[', l) => jumpRight(prog, pc + 1, l + 1)
+ case (_, l) => jumpRight(prog, pc + 1, l)
+ }
+}
+
+def jumpLeft(prog: String, pc: Int, level: Int) : Int = {
+ if (pc < 0) pc
+ else (prog(pc), level) match {
+ case ('[', 0) => pc + 1
+ case ('[', l) => jumpLeft(prog, pc - 1, l - 1)
+ case (']', l) => jumpLeft(prog, pc - 1, l + 1)
+ case (_, l) => jumpLeft(prog, pc - 1, l)
+ }
+}
+
+// test cases
+//jumpRight("""--[..+>--].>.++""", 3, 0) // => 10
+//jumpLeft("""--[..+>--].>.++""", 8, 0) // => 3
+//jumpRight("""--[..[+>]--].>.++""", 3, 0) // => 12
+//jumpRight("""--[..[[-]+>[.]]--].>.++""", 3, 0) // => 18
+//jumpRight("""--[..[[-]+>[.]]--.>.++""", 3, 0) // => 22 (outside)
+//jumpLeft("""[******]***""", 7, 0) // => -1 (outside)
+// (4) Complete the compute function that interprets (runs) a brainf***++
+// program: the arguments are a program (represented as a string), a program
+// counter, a memory counter and a brainf***++ memory. It Returns the
+// memory at the stage when the execution of the brainf***++ program
+// finishes. The interpretation finishes once the program counter
+// pc is pointing to something outside the program string.
+// If the pc points to a character inside the program, the pc,
+// memory pointer and memory need to be updated according to
+// rules of the brainf***++ language. Then, recursively, the compute
+// function continues with the command at the new program
+// counter.
+//
+// Implement the run function that calls compute with the program
+// counter and memory counter set to 0.
+
+def compute(prog: String, pc: Int, mp: Int, mem: Mem) : Mem = {
+ if (0 <= pc && pc < prog.length) {
+ val (new_pc, new_mp, new_mem) = prog(pc) match {
+ case '>' => (pc + 1, mp + 1, mem)
+ case '<' => (pc + 1, mp - 1, mem)
+ case '+' => (pc + 1, mp, write(mem, mp, sread(mem, mp) + 1))
+ case '-' => (pc + 1, mp, write(mem, mp, sread(mem, mp) - 1))
+ case '.' => { print(sread(mem, mp).toChar); (pc + 1, mp, mem) }
+ case '[' => if (sread(mem, mp) == 0) (jumpRight(prog, pc + 1, 0), mp, mem) else (pc + 1, mp, mem)
+ case ']' => if (sread(mem, mp) != 0) (jumpLeft(prog, pc - 1, 0), mp, mem) else (pc + 1, mp, mem)
+
+ case _ => (pc + 1, mp, mem)
+ }
+ compute(prog, new_pc, new_mp, new_mem)
+ }
+ else mem
+}
+
+def run(prog: String, m: Mem = Map()) = compute(prog, 0, 0, m)
-// (4)
-def compute(prog: String, pc: Int, mp: Int, mem: Mem) : Mem = (pc >= 0 && pc < prog.length) match {
- case false => mem
- case true => prog.toList.apply(pc) match{
- case '>' => compute(prog, pc+1, mp+1, mem)
- case '<' => compute(prog, pc+1, mp-1, mem)
- case '+' => {
- val current = sread(mem, mp)
- compute(prog, pc+1, mp, write(mem, mp, current+1))
- }
- case '-' => {
- val current = sread(mem, mp)
- compute(prog, pc+1, mp, write(mem, mp, current-1))
- }
- case '.' => {
- print(mem.apply(mp).toChar)
- compute(prog, pc+1, mp, mem)
- }
- case '[' => {
- if (mem.apply(mp) == 0) compute(prog, jumpRight(prog, pc+1, 0), mp, mem)
- else compute(prog, pc+1, mp, mem)
- }
- case ']' => {
- if (mem.apply(mp) != 0) compute(prog, jumpLeft(prog, pc-1, 0), mp, mem)
- else compute(prog, pc+1, mp, mem)
- }
- case _ => compute(prog, pc, mp, mem)
- }
+def generate(msg: List[Char]) : String = msg match {
+ case Nil => ""
+ case c::cs => s"${"+" * c.toInt}.[-]" ++ generate(cs)
}
-def run(prog: String, m: Mem = Map()) = {
- compute(prog, 0, 0, m)
-}
+//println(generate("Hello World\n".toList))
-// run("[-]", Map(0 -> 100)) == Map(0 -> 0)
-// run("[->+<]", Map(0 -> 10)) == Map(0 -> 0, 1 -> 10)
-// run("[>>+>>+<<<<-]", Map(0 -> 42)) == Map(0 -> 0, 2 -> 42, 4 -> 42)
-// run("""+++++[->++++++++++<]>--<+++[->>++++++++++<<]>>++<<----------[+>.>.<+<]""") == Map(0 -> 0, 1 -> 58, 2 -> 32)
-// (5)
-def generate(msg: List[Char]) : String = msg match {
- case Nil => ""
- case c => "+"*c.head.toInt + ".[-]" + generate(msg.tail)
-}
-
-// generate("ABC".toList)
-
-// run("+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++.[-]++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++.[-]+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++.[-]", Map())
-
-// some sample bf-programs collected from the Internet
-//=====================================================
+// some sample bf/bf++-programs collected from the Internet
+//==========================================================
// some contrived (small) programs
//---------------------------------
-// // clears the 0-cell
-// run("[-]", Map(0 -> 100)) // Map will be 0 -> 0
+// clears the 0-cell
+//run("[-]", Map(0 -> 100)) // Map will be 0 -> 0
-// // moves content of the 0-cell to 1-cell
-// run("[->+<]", Map(0 -> 10)) // Map will be 0 -> 0, 1 -> 10
+// moves content of the 0-cell to 1-cell
+//run("[->+<]", Map(0 -> 10)) // Map will be 0 -> 0, 1 -> 10
-// // copies content of the 0-cell to 2-cell and 4-cell
-// run("[>>+>>+<<<<-]", Map(0 -> 42)) // Map(0 -> 0, 2 -> 42, 4 -> 42)
+// copies content of the 0-cell to 2-cell and 4-cell
+//run("[>>+>>+<<<<-]", Map(0 -> 42)) // Map(0 -> 0, 2 -> 42, 4 -> 42)
-// // prints out numbers 0 to 9
-// run("""+++++[->++++++++++<]>--<+++[->>++++++++++<<]>>++<<----------[+>.>.<+<]""")
+// prints out numbers 0 to 9
+//run("""+++++[->++++++++++<]>--<+++[->>++++++++++<<]>>++<<----------[+>.>.<+<]""")
-// // some more "useful" programs
-// //-----------------------------
+// some more "useful" programs
+//-----------------------------
-// // hello world program 1
-// run("""++++++++[>++++[>++>+++>+++>+<<<<-]>+>+>->>+[<]<-]>>.>---.+++++++..+++.>>.<-.<.+++.------.--------.>>+.>++.""")
+// hello world program 1
+//run("""++++++++[>++++[>++>+++>+++>+<<<<-]>+>+>->>+[<]<-]>>.>---.+++++++
+// ..+++.>>.<-.<.+++.------.--------.>>+.>++.""")
-// // hello world program 2
-// run("""++++++++++[>+++++++>++++++++++>+++>+<<<<-]>++.>+.+++++++..+++.>++.<<+++++++++++++++.>.+++.------.--------.>+.>.""")
+// hello world program 2
+//run("""++++++++++[>+++++++>++++++++++>+++>+<<<<-]>++.>+.+++++++..+++.>+
+// +.<<+++++++++++++++.>.+++.------.--------.>+.>.""")
-// // hello world program 3
-// run("""+++++++++[>++++++++>+++++++++++>+++++<<<-]>.>++.+++++++..+++.>-.------------.<++++++++.--------.+++.------.--------.>+.""")
+// hello world program 3
+//run("""+++++++++[>++++++++>+++++++++++>+++++<<<-]>.>++.+++++++..
+// +++.>-.------------.<++++++++.--------.+++.------.--------.>+.""")
-// // draws the Sierpinski triangle
-// run(load_bff("sierpinski.bf"))
+// draws the Sierpinski triangle
+//run(load_bff("sierpinski.bf"))
-// //fibonacci numbers below 100
-// run("""+++++++++++
+//fibonacci numbers below 100
+//run("""+++++++++++
// >+>>>>++++++++++++++++++++++++++++++++++++++++++++
// >++++++++++++++++++++++++++++++++<<<<<<[>[>>>>>>+>
// +<<<<<<<-]>>>>>>>[<<<<<<<+>>>>>>>-]<[>++++++++++[-
@@ -170,15 +172,15 @@
// <<<<<<<<<<[>>>+>+<<<<-]>>>>[<<<<+>>>>-]<-[>>.>.<<<
// [-]]<<[>>+>+<<<-]>>>[<<<+>>>-]<<[<+>-]>[<+>-]<<<-]""")
-// //outputs the square numbers up to 10000
-// run("""++++[>+++++<-]>[<+++++>-]+<+[>[>+>+<<-]++>>[<<+>>-]>>>[-]++>[-]+
+//outputs the square numbers up to 10000
+//run("""++++[>+++++<-]>[<+++++>-]+<+[>[>+>+<<-]++>>[<<+>>-]>>>[-]++>[-]+
// >>>+[[-]++++++>>>]<<<[[<++++++++<++>>-]+<.<[>----<-]<]
// <<[>>>>>[>>>[-]+++++++++<[>-<-]+++++++++>[-[<->-]+[<<<]]<[>+<-]>]<<-]<<-]""")
-// // calculates 2 to the power of 6
-// // (example from a C-to-BF compiler at https://github.com/elikaski/BF-it)
-// run(""">>[-]>[-]++>[-]++++++><<<>>>>[-]+><>[-]<<[-]>[>+<<+>-]>[<+>-]
+// calculates 2 to the power of 6
+//(example from a C-to-BF compiler at https://github.com/elikaski/BF-it)
+//run(""">>[-]>[-]++>[-]++++++><<<>>>>[-]+><>[-]<<[-]>[>+<<+>-]>[<+>-]
// <><[-]>[-]<<<[>>+>+<<<-]>>>[<<<+>>>-][-]><<>>[-]>[-]<<<[>>[-]
// <[>+>+<<-]>[<+>-]+>[[-]<-<->>]<<<-]>>[<<+>>-]<<[[-]>[-]<<[>+>
// +<<-]>>[<<+>>-][-]>[-]<<<<<[>>>>+>+<<<<<-]>>>>>[<<<<<+>>>>>-]
@@ -195,28 +197,25 @@
-// // a Mandelbrot set generator in brainf*** written by Erik Bosman
+// a Mandelbrot set generator in brainf*** written by Erik Bosman
// (http://esoteric.sange.fi/brainfuck/utils/mandelbrot/)
-
-// run(load_bff("mandelbrot.bf"))
+//
+//run(load_bff("mandelbrot.bf"))
-// // a benchmark program (counts down from 'Z' to 'A')
-// //
-// run(load_bff("benchmark.bf"))
+// a benchmark program (counts down from 'Z' to 'A')
+//
+//run(load_bff("benchmark.bf"))
-// // calculates the Collatz series for numbers from 1 to 30
-// //
-// run(load_bff("collatz.bf"))
+// calculates the Collatz series for numbers from 1 to 30
+//
+//run(load_bff("collatz.bf"))
}
-
-
+//M5a.run(M5a.load_bff("mandelbrot.bf"))
+//M5a.run(M5a.load_bff("collatz.bf"))
-// This template code is subject to copyright
-// by King's College London, 2022. Do not
-// make the template code public in any shape
-// or form, and do not exchange it with other
-// students under any circumstance.
+//println(M5a.generate("ABC".toList))
+//M5a.run(M5a.generate("Hello World\n".toList))
--- a/main_testing5/bf_test.sh Thu Nov 02 13:53:37 2023 +0000
+++ b/main_testing5/bf_test.sh Thu Nov 02 23:34:53 2023 +0000
@@ -14,20 +14,19 @@
# compilation tests
function scala_compile {
- (ulimit -t 30; JAVA_OPTS="-Xmx1g" scala -Xprint:parser "$1" 2> c$out 1> c$out)
+ (ulimit -t 30; JAVA_OPTS="-Xmx1g" scala-cli compile "$1" 2> c$out 1> c$out)
}
# functional tests
function scala_assert {
- (ulimit -t 30; JAVA_OPTS="-Xmx1g" scala -i "$1" -- "$2" -e "" 2> /dev/null 1> /dev/null)
+ (ulimit -t 30; JAVA_OPTS="-Xmx1g" scala-cli -i "$1" "$2" -e "urbanmain()" 2> /dev/null 1> /dev/null)
}
# purity test
-
function scala_vars {
- (sed 's/immutable/ok/g' c$out > cb$out;
- egrep '\bvar\b|\breturn\b|\.par\.|\.par |ListBuffer|AtomicInteger|mutable|util.control|new Array' cb$out 2> /dev/null 1> /dev/null)
+ (sed 's/immutable/ok/g' c$out > cb$out;
+ egrep '\bvar\b|\breturn\b|\.par\.|\.par |ListBuffer|AtomicInteger|mutable|util.control|new Array' cb$out 2> /dev/null 1> /dev/null)
}
--- a/main_testing5/bf_test1.scala Thu Nov 02 13:53:37 2023 +0000
+++ b/main_testing5/bf_test1.scala Thu Nov 02 23:34:53 2023 +0000
@@ -1,4 +1,9 @@
-import M5a._
+
+def urbanmain() = {
+
+ import M5a._
-assert(load_bff("benchmark.bf").length == 188)
-assert(load_bff("foobar.bf") == "")
+ assert(load_bff("benchmark.bf").length == 188)
+ assert(load_bff("foobar.bf") == "")
+
+}
--- a/main_testing5/bf_test2.scala Thu Nov 02 13:53:37 2023 +0000
+++ b/main_testing5/bf_test2.scala Thu Nov 02 23:34:53 2023 +0000
@@ -1,6 +1,10 @@
-import M5a._
+
+def urbanmain() = {
+
+ import M5a._
-assert(sread(Map(), 2) == 0)
-assert(sread(Map(2 -> 1), 2) == 1)
-assert(write(Map(), 1, 2) == Map(1 -> 2))
-assert(write(Map(1 -> 0), 1, 2) == Map(1 -> 2))
+ assert(sread(Map(), 2) == 0)
+ assert(sread(Map(2 -> 1), 2) == 1)
+ assert(write(Map(), 1, 2) == Map(1 -> 2))
+ assert(write(Map(1 -> 0), 1, 2) == Map(1 -> 2))
+}
--- a/main_testing5/bf_test3.scala Thu Nov 02 13:53:37 2023 +0000
+++ b/main_testing5/bf_test3.scala Thu Nov 02 23:34:53 2023 +0000
@@ -1,10 +1,14 @@
-import M5a._
+
+def urbanmain() = {
+
+ import M5a._
-assert(jumpRight("[xxxxxx]xxx", 1, 0) == 8)
-assert(jumpRight("[xx[x]x]xxx", 1, 0) == 8)
-assert(jumpRight("[xx[x]x]xxx", 1, 0) == 8)
-assert(jumpRight("[xx[xxx]xxx", 1, 0) == 11)
-assert(jumpRight("[x[][]x]xxx", 1, 0) == 8)
-assert(jumpLeft("[xxxxxx]xxx", 6, 0) == 1)
-assert(jumpLeft("[xxxxxx]xxx", 7, 0) == -1)
-assert(jumpLeft("[x[][]x]xxx", 6, 0) == 1)
+ assert(jumpRight("[xxxxxx]xxx", 1, 0) == 8)
+ assert(jumpRight("[xx[x]x]xxx", 1, 0) == 8)
+ assert(jumpRight("[xx[x]x]xxx", 1, 0) == 8)
+ assert(jumpRight("[xx[xxx]xxx", 1, 0) == 11)
+ assert(jumpRight("[x[][]x]xxx", 1, 0) == 8)
+ assert(jumpLeft("[xxxxxx]xxx", 6, 0) == 1)
+ assert(jumpLeft("[xxxxxx]xxx", 7, 0) == -1)
+ assert(jumpLeft("[x[][]x]xxx", 6, 0) == 1)
+}
--- a/main_testing5/bf_test4.scala Thu Nov 02 13:53:37 2023 +0000
+++ b/main_testing5/bf_test4.scala Thu Nov 02 23:34:53 2023 +0000
@@ -1,13 +1,16 @@
-import M5a._
+
+def urbanmain() = {
-assert(run("[-]", Map(0 -> 100)) == Map(0 -> 0))
-assert(run("[->+<]", Map(0 -> 10)) == Map(0 -> 0, 1 -> 10))
-assert(run("[>>+>>+<<<<-]", Map(0 -> 42)) == Map(0 -> 0, 2 -> 42, 4 -> 42))
+ import M5a._
+
+ assert(run("[-]", Map(0 -> 100)) == Map(0 -> 0))
+ assert(run("[->+<]", Map(0 -> 10)) == Map(0 -> 0, 1 -> 10))
+ assert(run("[>>+>>+<<<<-]", Map(0 -> 42)) == Map(0 -> 0, 2 -> 42, 4 -> 42))
-val hw_urban = """+++++[->++++++++++<]>--<+++[->>++++++++++
- <<]>>++<<----------[+>.>.<+<]"""
-assert(run(hw_urban) == Map(0 -> 0, 1 -> 58, 2 -> 32))
-
+ val hw_urban = """+++++[->++++++++++<]>--<+++[->>++++++++++
+ <<]>>++<<----------[+>.>.<+<]"""
+ assert(run(hw_urban) == Map(0 -> 0, 1 -> 58, 2 -> 32))
+}
--- a/main_testing5/bf_test5.scala Thu Nov 02 13:53:37 2023 +0000
+++ b/main_testing5/bf_test5.scala Thu Nov 02 23:34:53 2023 +0000
@@ -1,5 +1,8 @@
-import M5b._
+
+def urbanmain() = {
-assert(jtable("""+++++[->++++++++++<]>--<+++[->>++++++++++<<]>>++<<----------[+>.>.<+<]""") ==
- Map(69 -> 61, 5 -> 20, 60 -> 70, 27 -> 44, 43 -> 28, 19 -> 6))
+ import M5b._
+ assert(jtable("""+++++[->++++++++++<]>--<+++[->>++++++++++<<]>>++<<----------[+>.>.<+<]""") == Map(69 -> 61, 5 -> 20, 60 -> 70, 27 -> 44, 43 -> 28, 19 -> 6))
+
+}
--- a/main_testing5/bf_test6.scala Thu Nov 02 13:53:37 2023 +0000
+++ b/main_testing5/bf_test6.scala Thu Nov 02 23:34:53 2023 +0000
@@ -1,10 +1,14 @@
-import M5b._
-//println(optimise(load_bff("benchmark.bf")).length)
-//println(optimise(load_bff("mandelbrot.bf")).length)
+def urbanmain() = {
+
+ import M5b._
-val urban_l1 = optimise(load_bff("benchmark.bf")).length
-val urban_l2 = optimise(load_bff("mandelbrot.bf")).length
+ //println(optimise(load_bff("benchmark.bf")).length)
+ //println(optimise(load_bff("mandelbrot.bf")).length)
-assert(urban_l1 == 181)
-assert(urban_l2 == 11203)
+ val urban_l1 = optimise(load_bff("benchmark.bf")).length
+ val urban_l2 = optimise(load_bff("mandelbrot.bf")).length
+
+ assert(urban_l1 == 181)
+ assert(urban_l2 == 11203)
+}
--- a/main_testing5/bf_test7.scala Thu Nov 02 13:53:37 2023 +0000
+++ b/main_testing5/bf_test7.scala Thu Nov 02 23:34:53 2023 +0000
@@ -1,7 +1,11 @@
-import M5b._
+
+def urbanmain() = {
+
+ import M5b._
-//println(combine(optimise(load_bff("benchmark.bf"))).length)
-//println(combine(optimise(load_bff("mandelbrot.bf"))).length)
+ //println(combine(optimise(load_bff("benchmark.bf"))).length)
+ //println(combine(optimise(load_bff("mandelbrot.bf"))).length)
-assert(combine(optimise(load_bff("benchmark.bf"))).length == 134)
-assert(combine(optimise(load_bff("mandelbrot.bf"))).length == 6509)
+ assert(combine(optimise(load_bff("benchmark.bf"))).length == 134)
+ assert(combine(optimise(load_bff("mandelbrot.bf"))).length == 6509)
+}
--- a/main_testing5/bfc.scala Thu Nov 02 13:53:37 2023 +0000
+++ b/main_testing5/bfc.scala Thu Nov 02 23:34:53 2023 +0000
@@ -1,6 +1,5 @@
-// Main Part 5 about a "Compiler" for the Brainf*** language
-//============================================================
-
+// Part 2 about a "Compiler" for the Brainf*** language
+//======================================================
object M5b {
@@ -11,15 +10,6 @@
// templates below.
-// DEBUGGING INFORMATION FOR COMPILERS!!!
-//
-// Compiler, even real ones, are fiendishly difficult to get
-// to produce correct code. One way to debug them is to run
-// example programs ``unoptimised''; and then optimised. Does
-// the optimised version still produce the same result?
-
-
-// for timing purposes
def time_needed[T](n: Int, code: => T) = {
val start = System.nanoTime()
for (i <- 0 until n) code
@@ -27,154 +17,296 @@
(end - start)/(n * 1.0e9)
}
+type Mem = Map[Int, Int]
-type Mem = Map[Int, Int]
import io.Source
import scala.util._
-// ADD YOUR CODE BELOW
-//======================
+def load_bff(name: String) : String =
+ Try(Source.fromFile(name)("ISO-8859-1").mkString).getOrElse("")
-// (6)
+def sread(mem: Mem, mp: Int) : Int =
+ mem.getOrElse(mp, 0)
+
+def write(mem: Mem, mp: Int, v: Int) : Mem =
+ mem.updated(mp, v)
+
def jumpRight(prog: String, pc: Int, level: Int) : Int = {
- if (pc >= prog.length) prog.length
- else if (prog(pc) == '[') jumpRight(prog, pc + 1, level + 1)
- else if (prog(pc) == ']' && level == 0) pc + 1
- else if (prog(pc) == ']') jumpRight(prog, pc + 1, level - 1)
- else jumpRight(prog, pc + 1, level)
+ if (prog.length <= pc) pc
+ else (prog(pc), level) match {
+ case (']', 0) => pc + 1
+ case (']', l) => jumpRight(prog, pc + 1, l - 1)
+ case ('[', l) => jumpRight(prog, pc + 1, l + 1)
+ case (_, l) => jumpRight(prog, pc + 1, l)
+ }
}
-def jtable(pg: String) : Map[Int, Int] = {
- val pairs = for {
- i <- 0 until pg.length
- if pg.charAt(i) == '['
- j = jumpRight(pg, i+1, 0)
- } yield (i, j)
- pairs.flatMap { case (i, j) =>
- List((i, j), (j-1, i+1))
- }.toMap
-}
-
-def write(mem: Mem, mp: Int, v: Int) : Mem = mem + (mp -> v)
-
-// testcase
-//
-// jtable("""+++++[->++++++++++<]>--<+++[->>++++++++++<<]>>++<<----------[+>.>.<+<]""")
-// => Map(69 -> 61, 5 -> 20, 60 -> 70, 27 -> 44, 43 -> 28, 19 -> 6)
-
-def compute2(pg: String, tb: Map[Int, Int], pc: Int, mp: Int, mem: Mem) : Mem = {
- if (pc >= pg.length) mem
- else {
- val (npc, nmp, nmem) = pg(pc) match {
- case '>' => (pc + 1, mp + 1, mem)
- case '<' => (pc + 1, mp - 1, mem)
- case '+' => (pc + 1, mp, mem + (mp -> (mem.getOrElse(mp, 0) + 1)))
- case '-' => (pc + 1, mp, mem + (mp -> (mem.getOrElse(mp, 0) - 1)))
- case '.' => {print(mem.getOrElse(mp,0).toChar);(pc + 1, mp, mem)}
- case '[' => if (mem.getOrElse(mp, 0) == 0) (tb(pc), mp, mem) else (pc + 1, mp, mem)
- case ']' => if (mem.getOrElse(mp, 0) != 0) (tb(pc), mp, mem) else (pc + 1, mp, mem)
- case _ => (pc + 1, mp, mem)
- }
- compute2(pg, tb, npc, nmp, nmem)
+def jumpLeft(prog: String, pc: Int, level: Int) : Int = {
+ if (pc < 0) pc
+ else (prog(pc), level) match {
+ case ('[', 0) => pc + 1
+ case ('[', l) => jumpLeft(prog, pc - 1, l - 1)
+ case (']', l) => jumpLeft(prog, pc - 1, l + 1)
+ case (_, l) => jumpLeft(prog, pc - 1, l)
}
}
-def run2(pg: String, m: Mem = Map()) =
- compute2(pg, jtable(pg), 0, 0, m)
-
+def compute(prog: String, pc: Int, mp: Int, mem: Mem) : Mem = {
+ if (0 <= pc && pc < prog.length) {
+ val (new_pc, new_mp, new_mem) = prog(pc) match {
+ case '>' => (pc + 1, mp + 1, mem)
+ case '<' => (pc + 1, mp - 1, mem)
+ case '+' => (pc + 1, mp, write(mem, mp, sread(mem, mp) + 1))
+ case '-' => (pc + 1, mp, write(mem, mp, sread(mem, mp) - 1))
+ case '.' => { print(sread(mem, mp).toChar); (pc + 1, mp, mem) }
+ case '[' => if (sread(mem, mp) == 0) (jumpRight(prog, pc + 1, 0), mp, mem) else (pc + 1, mp, mem)
+ case ']' => if (sread(mem, mp) != 0) (jumpLeft(prog, pc - 1, 0), mp, mem) else (pc + 1, mp, mem)
+ case _ => (pc + 1, mp, mem)
+ }
+ compute(prog, new_pc, new_mp, new_mem)
+ }
+ else mem
+}
-// testcases
-// time_needed(1, run2(load_bff("benchmark.bf")))
-// time_needed(1, run2(load_bff("sierpinski.bf")))
+def run(prog: String, m: Mem = Map()) = compute(prog, 0, 0, m)
+
+
+// The baseline to what we can compare our "compiler"
+// implemented below. It should require something like
+// 60 seconds for the calculation on my laptop
+//
+//time_needed(1, run(load_bff("benchmark.bf")))
+
+
+
+// DEBUGGING INFORMATION!!!
+//
+// Compiler, even real ones, are fiedishly difficult to get
+// to prduce correct code. The point is that for example for
+// the sierpinski program, they need to still generate code
+// that displays such a triangle. If yes, then one usually
+// can take comfort that all is well. If not, then something
+// went wrong during the optimisations.
-// (7)
+// (5) Write a function jtable that precomputes the "jump
+// table" for a bf-program. This function takes a bf-program
+// as an argument and Returns a Map[Int, Int]. The
+// purpose of this map is to record the information
+// that given on the position pc is a '[' or a ']',
+// then to which pc-position do we need to jump next?
+//
+// For example for the program
+//
+// "+++++[->++++++++++<]>--<+++[->>++++++++++<<]>>++<<----------[+>.>.<+<]"
+//
+// we obtain the map
+//
+// Map(69 -> 61, 5 -> 20, 60 -> 70, 27 -> 44, 43 -> 28, 19 -> 6)
+//
+// This states that for the '[' on position 5, we need to
+// jump to position 20, which is just after the corresponding ']'.
+// Similarly, for the ']' on position 19, we need to jump to
+// position 6, which is just after the '[' on position 5, and so
+// on. The idea is to not calculate this information each time
+// we hit a bracket, but just look up this information in the
+// jtable. You can use the jumpLeft and jumpRight functions
+// from Part 1 for calculating the jtable.
+//
+// Then adapt the compute and run functions from Part 1 in order
+// to take advantage of the information stored in the jtable.
+// This means whenever jumpLeft and jumpRight was called previously,
+// you should look up the jump address in the jtable.
+
+
+def jtable(pg: String) : Map[Int, Int] =
+ (0 until pg.length).collect { pc => pg(pc) match {
+ case '[' => (pc -> jumpRight(pg, pc + 1, 0))
+ case ']' => (pc -> jumpLeft(pg, pc - 1, 0))
+ }}.toMap
+
+
+// testcase
+// jtable("""+++++[->++++++++++<]>--<+++[->>++++++++++<<]>>++<<----------[+>.>.<+<]""")
+// => Map(69 -> 61, 5 -> 20, 60 -> 70, 27 -> 44, 43 -> 28, 19 -> 6)
+
-def optimise(s: String) : String =
- s.replaceAll("""[^<>+-.,\[\]]""","").replaceAll("""\[-\]""","0")
+def compute2(pg: String, tb: Map[Int, Int], pc: Int, mp: Int, mem: Mem) : Mem = {
+ if (0 <= pc && pc < pg.length) {
+ val (new_pc, new_mp, new_mem) = pg(pc) match {
+ case '>' => (pc + 1, mp + 1, mem)
+ case '<' => (pc + 1, mp - 1, mem)
+ case '+' => (pc + 1, mp, write(mem, mp, sread(mem, mp) + 1))
+ case '-' => (pc + 1, mp, write(mem, mp, sread(mem, mp) - 1))
+ case '.' => { print(sread(mem, mp).toChar); (pc + 1, mp, mem) }
+ case '[' => if (sread(mem, mp) == 0) (tb(pc), mp, mem) else (pc + 1, mp, mem)
+ case ']' => if (sread(mem, mp) != 0) (tb(pc), mp, mem) else (pc + 1, mp, mem)
+ case _ => (pc + 1, mp, mem)
+ }
+ compute2(pg, tb, new_pc, new_mp, new_mem)
+ }
+ else mem
+}
+
+
+def run2(pg: String, m: Mem = Map()) =
+ compute2(pg, jtable(pg), 0, 0, m)
+
+//time_needed(1, run2(load_bff("benchmark.bf")))
+
+
+
+// (6) Write a function optimise which deletes "dead code" (everything
+// that is not a bf-command) and also replaces substrings of the form
+// [-] by a new command 0. The idea is that the loop [-] just resets the
+// memory at the current location to 0. In the compute3 and run3 functions
+// below you implement this command by writing the number 0 to mem(mp),
+// that is write(mem, mp, 0).
+//
+// The easiest way to modify a string in this way is to use the regular
+// expression """[^<>+-.\[\]""", which recognises everything that is
+// not a bf-command and replace it by the empty string. Similarly the
+// regular expression """\[-\]""" finds all occurences of [-] and
+// by using the Scala method .replaceAll you can repplace it with the
+// string "0" standing for the new bf-command.
+
+def optimise(s: String) : String = {
+ s.replaceAll("""[^<>+-.\[\]]""","")
+ .replaceAll("""\[-\]""", "0")
+}
+
def compute3(pg: String, tb: Map[Int, Int], pc: Int, mp: Int, mem: Mem) : Mem = {
- if (pc >= pg.length) mem
- else {
- val (npc, nmp, nmem) = pg(pc) match {
- case '>' => (pc + 1, mp + 1, mem)
- case '<' => (pc + 1, mp - 1, mem)
- case '+' => (pc + 1, mp, mem + (mp -> (mem.getOrElse(mp, 0) + 1)))
- case '-' => (pc + 1, mp, mem + (mp -> (mem.getOrElse(mp, 0) - 1)))
- case '.' => {print(mem.getOrElse(mp,0).toChar);(pc + 1, mp, mem)}
- case '[' => if (mem.getOrElse(mp, 0) == 0) (tb(pc), mp, mem) else (pc + 1, mp, mem)
- case ']' => if (mem.getOrElse(mp, 0) != 0) (tb(pc), mp, mem) else (pc + 1, mp, mem)
- case _ => (pc + 1, mp, mem)
- }
- compute3(pg, tb, npc, nmp, nmem)
- }
+ if (0 <= pc && pc < pg.length) {
+ val (new_pc, new_mp, new_mem) = pg(pc) match {
+ case '0' => (pc + 1, mp, write(mem, mp, 0))
+ case '>' => (pc + 1, mp + 1, mem)
+ case '<' => (pc + 1, mp - 1, mem)
+ case '+' => (pc + 1, mp, write(mem, mp, sread(mem, mp) + 1))
+ case '-' => (pc + 1, mp, write(mem, mp, sread(mem, mp) - 1))
+ case '.' => { print(sread(mem, mp).toChar); (pc + 1, mp, mem) }
+ case '[' => if (sread(mem, mp) == 0) (tb(pc), mp, mem) else (pc + 1, mp, mem)
+ case ']' => if (sread(mem, mp) != 0) (tb(pc), mp, mem) else (pc + 1, mp, mem)
+ case _ => (pc + 1, mp, mem)
+ }
+ compute3(pg, tb, new_pc, new_mp, new_mem)
+ }
+ else mem
}
-def run3(pg: String, m: Mem = Map()) = {
- val opt_pg = optimise(pg)
- val jt = jtable(opt_pg)
- compute3(opt_pg, jt, 0, 0, m)
+def run3(pg: String, m: Mem = Map()) = {
+ val pg_opt = optimise(pg)
+ compute3(pg_opt, jtable(pg_opt), 0, 0, m)
}
// testcases
-//
-// optimise(load_bff("benchmark.bf")) // should have inserted 0's
-// optimise(load_bff("mandelbrot.bf")).length // => 11203
-// optimise(load_bff("benchmark.bf")).length
-// time_needed(1, run3(load_bff("benchmark.bf")))
+
+//println(optimise(load_bff("collatz.bf")))
+//optimise(load_bff("benchmark.bf")) // should have inserted 0's
+//optimise(load_bff("mandelbrot.bf")).length // => 11203
+
+//time_needed(1, run3(load_bff("benchmark.bf")))
+
-// (8)
-def combine(s: String): String = ???
+// (7) Write a function combine which replaces sequences
+// of repated increment and decrement commands by appropriate
+// two-character commands. For example for sequences of +
+//
+// orig bf-cmds | replacement
+// ------------------------------
+// + | +A
+// ++ | +B
+// +++ | +C
+// |
+// ... |
+// |
+// +++....+++ | +Z
+// (where length = 26)
+//
+// Similar for the bf-command -, > and <. All other commands should
+// be unaffected by this change.
+//
+// Adapt the compute4 and run4 functions such that they can deal
+// appropriately with such two-character commands.
-// testcase
-// combine(load_bff("benchmark.bf"))
+def splice(cs: List[Char], acc: List[(Char, Int)]) : List[(Char, Int)] = (cs, acc) match {
+ case (Nil, acc) => acc
+ case ('[' :: cs, acc) => splice(cs, ('[', 1) :: acc)
+ case (']' :: cs, acc) => splice(cs, (']', 1) :: acc)
+ case ('.' :: cs, acc) => splice(cs, ('.', 1) :: acc)
+ case ('0' :: cs, acc) => splice(cs, ('0', 1) :: acc)
+ case (c :: cs, Nil) => splice(cs, List((c, 1)))
+ case (c :: cs, (d, n) :: acc) =>
+ if (c == d && n < 26) splice(cs, (c, n + 1) :: acc)
+ else splice(cs, (c, 1) :: (d, n) :: acc)
+}
+
+def spl(s: String) = splice(s.toList, Nil).reverse
+
+//spl(load_bff("benchmark.bf"))
+
+def combine(s: String) : String = {
+ (for ((c, n) <- spl(s)) yield c match {
+ case '>' => List('>', (n + '@').toChar)
+ case '<' => List('<', (n + '@').toChar)
+ case '+' => List('+', (n + '@').toChar)
+ case '-' => List('-', (n + '@').toChar)
+ case _ => List(c)
+ }).flatten.mkString
+}
+
+
+//combine(load_bff("benchmark.bf"))
def compute4(pg: String, tb: Map[Int, Int], pc: Int, mp: Int, mem: Mem) : Mem = {
- if (pc >= pg.length) mem
- else {
- val (npc, nmp, nmem) = pg(pc) match {
- case '>' => (pc + 1, mp + 1, mem)
- case '<' => (pc + 1, mp - 1, mem)
- case '+' => (pc + 1, mp, mem + (mp -> (mem.getOrElse(mp, 0) + 1)))
- case '-' => (pc + 1, mp, mem + (mp -> (mem.getOrElse(mp, 0) - 1)))
- case '.' => {print(mem.getOrElse(mp,0).toChar);(pc + 1, mp, mem)}
- case '[' => if (mem.getOrElse(mp, 0) == 0) (tb(pc), mp, mem) else (pc + 1, mp, mem)
- case ']' => if (mem.getOrElse(mp, 0) != 0) (tb(pc), mp, mem) else (pc + 1, mp, mem)
- case _ => (pc + 1, mp, mem)
- }
- compute3(pg, tb, npc, nmp, nmem)
- }
+ if (0 <= pc && pc < pg.length) {
+ val (new_pc, new_mp, new_mem) = pg(pc) match {
+ case '0' => (pc + 1, mp, write(mem, mp, 0))
+ case '>' => (pc + 2, mp + (pg(pc + 1) - '@'), mem)
+ case '<' => (pc + 2, mp - (pg(pc + 1) - '@'), mem)
+ case '+' => (pc + 2, mp, write(mem, mp, sread(mem, mp) + (pg(pc + 1) - '@')))
+ case '-' => (pc + 2, mp, write(mem, mp, sread(mem, mp) - (pg(pc + 1) - '@')))
+ case '.' => { print(sread(mem, mp).toChar); (pc + 1, mp, mem) }
+ case '[' => if (sread(mem, mp) == 0) (tb(pc), mp, mem) else (pc + 1, mp, mem)
+ case ']' => if (sread(mem, mp) != 0) (tb(pc), mp, mem) else (pc + 1, mp, mem)
+ case _ => (pc + 1, mp, mem)
+ }
+ compute4(pg, tb, new_pc, new_mp, new_mem)
+ }
+ else mem
}
-// should call first optimise and then combine on the input string
-//
-def run4(pg: String, m: Mem = Map()) = {
- val co_opt_pg = combine(optimise(pg))
- val jt = jtable(co_opt_pg)
- compute3(co_opt_pg, jt, 0, 0, m)
+def run4(pg: String, m: Mem = Map()) = {
+ val pg_opt = combine(optimise(pg))
+ compute4(pg_opt, jtable(pg_opt), 0, 0, m)
}
// testcases
-// combine(optimise(load_bff("benchmark.bf"))) // => """>A+B[<A+M>A-A]<A[[....."""
+//println(combine(optimise(load_bff("mandelbrot.bf").drop(123))))
+
+//combine(optimise(load_bff("benchmark.bf"))) // => """>A+B[<A+M>A-A]<A[[....."""
-// testcases (they should now run much faster)
-// time_needed(1, run4(load_bff("benchmark.bf")))
-// time_needed(1, run4(load_bff("sierpinski.bf")))
-// time_needed(1, run4(load_bff("mandelbrot.bf")))
+//time_needed(1, run4(load_bff("benchmark.bf")))
+//time_needed(1, run(load_bff("sierpinski.bf")))
+//time_needed(1, run4(load_bff("sierpinski.bf")))
-}
+//println(time_needed(1, run4(load_bff("mandelbrot.bf"))))
-// This template code is subject to copyright
-// by King's College London, 2022. Do not
-// make the template code public in any shape
-// or form, and do not exchange it with other
-// students under any circumstance.
+}
+
+/*
+import CW10b._
+println(time_needed(1, run(load_bff("collatz.bf"))))
+println(time_needed(1, run2(load_bff("collatz.bf"))))
+println(time_needed(1, run3(load_bff("collatz.bf"))))
+println(time_needed(1, run4(load_bff("collatz.bf"))))
+*/
--- a/main_testing5/bfc_test.sh Thu Nov 02 13:53:37 2023 +0000
+++ b/main_testing5/bfc_test.sh Thu Nov 02 23:34:53 2023 +0000
@@ -13,25 +13,23 @@
# compilation tests
function scala_compile {
- (ulimit -t 30; JAVA_OPTS="-Xmx1g" scala -Xprint:parser "$1" 2> c$out 1> c$out)
+ (ulimit -t 30; JAVA_OPTS="-Xmx1g" scala-cli compile "$1" 2> c$out 1> c$out)
}
# functional tests
function scala_assert {
- (ulimit -t 30; JAVA_OPTS="-Xmx1g" scala -i "$1" -- "$2" -e "" 2> /dev/null 1> /dev/null)
+ (ulimit -t 30; JAVA_OPTS="-Xmx1g" scala-cli -i "$1" "$2" -e "urbanmain()" 2> /dev/null 1> /dev/null)
}
# purity test
-
function scala_vars {
- (sed 's/immutable/ok/g' c$out > cb$out;
- egrep '\bvar\b|\breturn\b|\.par\.|\.par |ListBuffer|AtomicInteger|mutable|util.control|new Array' cb$out 2> /dev/null 1> /dev/null)
+ (sed 's/immutable/ok/g' c$out > cb$out;
+ egrep '\bvar\b|\breturn\b|\.par\.|\.par |ListBuffer|AtomicInteger|mutable|util.control|new Array' cb$out 2> /dev/null 1> /dev/null)
}
-
# compilation test
echo -e "bfc.scala runs?" >> $out