Binary file core_solution1/collatz.jar has changed
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/core_solution1/collatz.scala Sat Nov 06 00:06:39 2021 +0000
@@ -0,0 +1,52 @@
+// Core Part 1 about the 3n+1 conjecture
+//==================================
+
+// generate jar with
+// > scala -d collatz.jar collatz.scala
+
+object C1 { // for purposes of generating a jar
+
+def collatz(n: Long): Long =
+ if (n == 1) 0 else
+ if (n % 2 == 0) 1 + collatz(n / 2) else
+ 1 + collatz(3 * n + 1)
+
+
+def collatz_max(bnd: Long): (Long, Long) = {
+ val all = for (i <- (1L to bnd)) yield (collatz(i), i)
+ all.maxBy(_._1)
+}
+
+//collatz_max(1000000)
+//collatz_max(10000000)
+//collatz_max(100000000)
+
+/* some test cases
+val bnds = List(10, 100, 1000, 10000, 100000, 1000000)
+
+for (bnd <- bnds) {
+ val (steps, max) = collatz_max(bnd)
+ println(s"In the range of 1 - ${bnd} the number ${max} needs the maximum steps of ${steps}")
+}
+
+*/
+
+
+def is_pow(n: Long) : Boolean = (n & (n - 1)) == 0
+
+def is_hard(n: Long) : Boolean = is_pow(3 * n + 1)
+
+def last_odd(n: Long) : Long =
+ if (is_hard(n)) n else
+ if (n % 2 == 0) last_odd(n / 2) else
+ last_odd(3 * n + 1)
+
+
+
+//for (i <- 130 to 10000) println(s"$i: ${last_odd(i)}")
+//for (i <- 1 to 100) println(s"$i: ${collatz(i)}")
+
+}
+
+
+
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/core_testing1/collatz.scala Sat Nov 06 00:06:39 2021 +0000
@@ -0,0 +1,50 @@
+// Basic Part about the 3n+1 conjecture
+//==================================
+
+// generate jar with
+// > scala -d collatz.jar collatz.scala
+
+object C1 { // for purposes of generating a jar
+
+def collatz(n: Long): Long =
+ if (n == 1) 0 else
+ if (n % 2 == 0) 1 + collatz(n / 2) else
+ 1 + collatz(3 * n + 1)
+
+
+def collatz_max(bnd: Long): (Long, Long) = {
+ val all = for (i <- (1L to bnd)) yield (collatz(i), i)
+ all.maxBy(_._1)
+}
+
+//collatz_max(1000000)
+//collatz_max(10000000)
+//collatz_max(100000000)
+
+/* some test cases
+val bnds = List(10, 100, 1000, 10000, 100000, 1000000)
+
+for (bnd <- bnds) {
+ val (steps, max) = collatz_max(bnd)
+ println(s"In the range of 1 - ${bnd} the number ${max} needs the maximum steps of ${steps}")
+}
+
+*/
+
+def is_pow(n: Long) : Boolean = (n & (n - 1)) == 0
+
+def is_hard(n: Long) : Boolean = is_pow(3 * n + 1)
+
+def last_odd(n: Long) : Long =
+ if (is_hard(n)) n else
+ if (n % 2 == 0) last_odd(n / 2) else
+ last_odd(3 * n + 1)
+
+
+//for (i <- 130 to 10000) println(s"$i: ${last_odd(i)}")
+//for (i <- 1 to 100) println(s"$i: ${collatz(i)}")
+
+}
+
+
+
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/core_testing1/collatz_test.sh Sat Nov 06 00:06:39 2021 +0000
@@ -0,0 +1,118 @@
+#!/bin/bash
+
+# to make the script fail safely
+set -euo pipefail
+
+
+out=${1:-output}
+
+echo -e "" > $out
+
+echo -e "Below is the feedback for your submission collatz.scala" >> $out
+echo -e "" >> $out
+
+
+# compilation tests
+
+function scala_compile {
+ (ulimit -t 30; JAVA_OPTS="-Xmx1g" scala -Xprint:parser "$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)
+}
+
+# purity test
+
+function scala_vars {
+ (egrep '\bvar\b|\breturn\b|\.par\.|\.par |ListBuffer|AtomicInteger|mutable|util.control|new Array' c$out 2> /dev/null 1> /dev/null)
+}
+
+
+### compilation test
+
+echo -e "collatz.scala runs?" >> $out
+
+if (scala_compile collatz.scala)
+then
+ echo -e " --> success" >> $out
+ tsts=$(( 0 ))
+else
+ echo -e " --> SCALA DID NOT RUN collatz.scala\n" >> $out
+ tsts=$(( 1 ))
+fi
+
+
+
+# var, .par return, ListBuffer test
+#
+
+if [ $tsts -eq 0 ]
+then
+ echo -e "collatz.scala does not contain VARS, RETURNS etc?" >> $out
+
+ if (scala_vars collatz.scala)
+ then
+ echo -e " --> FAIL (make triple-sure your program conforms to the required format)\n" >> $out
+ tsts=$(( 1 ))
+ else
+ echo -e " --> success" >> $out
+ tsts=$(( 0 ))
+ fi
+fi
+
+
+### collatz tests
+
+if [ $tsts -eq 0 ]
+then
+ echo -e "collatz.scala tests:" >> $out
+ echo -e " collatz(1) == 0" >> $out
+ echo -e " collatz(6) == 8" >> $out
+ echo -e " collatz(9) == 19" >> $out
+
+ if (scala_assert "collatz.scala" "collatz_test1.scala")
+ then
+ echo -e " --> success" >> $out
+ else
+ echo -e " --> ONE OF THE TESTS FAILED\n" >> $out
+ fi
+fi
+
+### collatz-max tests
+
+if [ $tsts -eq 0 ]
+then
+ echo -e " collatz_max(10) == (19, 9)" >> $out
+ echo -e " collatz_max(100) == (118, 97)" >> $out
+ echo -e " collatz_max(1000) == (178, 871)" >> $out
+ echo -e " collatz_max(10000) == (261, 6171)" >> $out
+ echo -e " collatz_max(100000) == (350, 77031)" >> $out
+ echo -e " collatz_max(1000000) == (524, 837799)" >> $out
+
+ if (scala_assert "collatz.scala" "collatz_test2.scala")
+ then
+ echo -e " --> success" >> $out
+ else
+ echo -e " --> ONE OF THE TESTS FAILED\n" >> $out
+ fi
+fi
+
+
+### last-odd tests
+
+if [ $tsts -eq 0 ]
+then
+ echo -e " last_odd(113) == 85" >> $out
+ echo -e " last_odd(84) == 21" >> $out
+ echo -e " last_odd(605) == 341" >> $out
+
+ if (scala_assert "collatz.scala" "collatz_test3.scala")
+ then
+ echo -e " --> success" >> $out
+ else
+ echo -e " --> ONE OF THE TESTS FAILED\n" >> $out
+ fi
+fi
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/core_testing1/collatz_test1.scala Sat Nov 06 00:06:39 2021 +0000
@@ -0,0 +1,8 @@
+
+import C1._
+
+assert(collatz(1) == 0)
+assert(collatz(6) == 8)
+assert(collatz(9) == 19)
+
+
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/core_testing1/collatz_test2.scala Sat Nov 06 00:06:39 2021 +0000
@@ -0,0 +1,8 @@
+import C1._
+
+assert(collatz_max(10) == (19, 9))
+assert(collatz_max(100) == (118, 97))
+assert(collatz_max(1000) == (178, 871))
+assert(collatz_max(10000) == (261, 6171))
+assert(collatz_max(100000) == (350, 77031))
+assert(collatz_max(1000000) == (524, 837799))
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/core_testing1/collatz_test3.scala Sat Nov 06 00:06:39 2021 +0000
@@ -0,0 +1,4 @@
+
+assert(C1.last_odd(113) == 85)
+assert(C1.last_odd(84) == 21)
+assert(C1.last_odd(605) == 341)
Binary file cws/main_cw01.pdf has changed
--- a/cws/main_cw01.tex Fri Nov 05 17:20:53 2021 +0000
+++ b/cws/main_cw01.tex Sat Nov 06 00:06:39 2021 +0000
@@ -8,9 +8,9 @@
\begin{document}
-\section*{Main Part 1 (Scala, 7 Marks)}
+\section*{Main Part 1 (Scala, 6 Marks)}
-\IMPORTANT{This part is about Scala. It is due on \cwSIXa{} at 5pm and worth 7\%.}
+\IMPORTANT{This part is about Scala. It is due on \cwSIXa{} at 5pm and worth 6\%.}
\noindent
Also note that the running time of each part will be restricted to a
@@ -64,7 +64,7 @@
\texttt{100.0 / 3}!
\newpage
-\subsection*{Main Part 1 (7 Marks, file drumb.scala)}
+\subsection*{Main Part 1 (6 Marks, file drumb.scala)}
A purely fictional character named Mr T.~Drumb inherited in 1978
approximately 200 Million Dollar from his father. Mr Drumb prides
@@ -119,7 +119,7 @@
stock symbol and a year as arguments. The function reads the
corresponding CSV-file and returns the list of strings that start
with the given year (each line in the CSV-list is of the form
- \texttt{someyear-01-someday,someprice}).\hfill[1 Mark]
+ \texttt{someyear-01-someday,someprice}).\hfill[0.5 Marks]
\item[(2)] Write a function \texttt{get\_first\_price} that takes
again a stock symbol and a year as arguments. It should return the
@@ -212,7 +212,7 @@
for a range of years where each year the yearly profit is compounded to
the new balances and then re-invested into our portfolio.
For this use the function and results generated under (6).\\
- \mbox{}\hfill\mbox{[1 Mark]}
+ \mbox{}\hfill\mbox{[0.5 Marks]}
\end{itemize}\medskip
Binary file cws/main_cw05.pdf has changed
--- a/cws/main_cw05.tex Fri Nov 05 17:20:53 2021 +0000
+++ b/cws/main_cw05.tex Sat Nov 06 00:06:39 2021 +0000
@@ -15,7 +15,7 @@
\begin{document}
-\section*{Part 5 (Scala, 10 Marks)}
+\section*{Main Part 5 (Scala, 9 Marks)}
\mbox{}\hfill\textit{``If there's one feature that makes Scala, `Scala',}\\
\mbox{}\hfill\textit{ I would pick implicits.''}\smallskip\\
@@ -24,8 +24,8 @@
\noindent
This part is about a small (esoteric) programming language called
-brainf***. Actually, we will implement an interpreter for our own version
-of this language called brainf*ck++.\bigskip
+brainf***. We will implement an interpreter and compiler for
+this language.\bigskip
\IMPORTANT{This part is worth 10\% and you need to submit it on \cwTEN{} at 5pm.
Any 1\% you achieve counts as your ``weekly engagement''.}
@@ -44,13 +44,13 @@
allow 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 bf.jar}
and then query any function from the \texttt{bf.scala} template file.
-You have to prefix the calls with \texttt{CW10a} and \texttt{CW10b},
+You have to prefix the calls with \texttt{M5a} and \texttt{M5b},
respectively. For example
\begin{lstlisting}[language={},xleftmargin=1mm,numbers=none,basicstyle=\ttfamily\small]
$ scala -cp bf.jar
-scala> import CW10a._
+scala> import M5a._
scala> run(load_bff("sierpinski.bf")) ; ()
*
* *
@@ -88,7 +88,7 @@
\newpage
-\subsection*{Part A (6 Marks)}
+\subsection*{Part A (5 Marks)}
Coming from Java or C++, you might think Scala is a rather esoteric
programming language. But remember, some serious companies have built
@@ -124,13 +124,12 @@
\noindent
As mentioned above, the original brainf*** has 8 single-character
-commands. Our version of bf++ will contain the commands \texttt{'>'},
+commands. Our version of bf will contain the commands \texttt{'>'},
\texttt{'<'}, \texttt{'+'}, \texttt{'-'}, \texttt{'.'}, \texttt{'['}
-and \texttt{']'} from the original, and in addition the commands
-\texttt{'@'}, \texttt{'*'} and \texttt{'\#'}. Every other character
+and \texttt{']'}. Every other character
is considered a comment.
-Our interpreter for bf++ operates on memory cells containing
+Our interpreter for bf operates on memory cells containing
integers. For this it uses a single memory pointer, called
\texttt{mp}, that points at each stage to one memory cell.
@@ -161,7 +160,7 @@
command \texttt{'>'}, and backward by using \texttt{'<'}. The commands
\texttt{'+'} and \texttt{'-'} increase, respectively decrease, by 1
the content of the memory cell to which the memory pointer currently
-points to. The command for output in bf++ is \texttt{'.'} whereby output works
+points to. The command for output in bf is \texttt{'.'} whereby output works
by reading the content of the memory cell to which the memory pointer
points to and printing it out as an ASCII character.\footnote{In the
original version of bf, there is also a command for input, but we
@@ -179,9 +178,7 @@
\end{center}
\noindent
-This one prints out Hello World\ldots{}obviously \texttt{;o)} We also
-add 3 new commands in the bf++-version of the bf-language. The purpose
-of these commands we explain later.
+This one prints out Hello World\ldots{}obviously \texttt{;o)}
\subsubsection*{Tasks (file bf.scala)}
@@ -191,9 +188,9 @@
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.
- \mbox{}\hfill[1 Mark]
+ \mbox{}\hfill[0.5 Marks]
-\item[(2)] Brainf**k++ memory is represented by a \texttt{Map} from
+\item[(2)] Brainf**k memory is represented by a \texttt{Map} from
integers to integers. The empty memory is represented by
\texttt{Map()}, that is nothing is stored in the
memory; \texttt{Map(0 -> 1, 2 -> 3)} stores \texttt{1} at
@@ -210,11 +207,11 @@
\texttt{Map} with the value at the given memory location. As usual,
the \texttt{Map} is not updated `in-place' but a new map is created
with the same data, except the new value is stored at the given memory
- pointer.\hfill[1 Mark]
+ pointer.\hfill[0.5 Marks]
\item[(3)] Write two functions, \texttt{jumpRight} and
\texttt{jumpLeft}, that are needed to implement the loop constructs
- in brainf**k++. They take a program (a \texttt{String}) and a program
+ in brainf**k. They take a program (a \texttt{String}) and a program
counter (an \texttt{Int}) as arguments and move right (respectively
left) in the string in order to find the \textbf{matching}
opening/closing bracket. For example, given the following program
@@ -243,7 +240,7 @@
Unfortunately we have to take into account that there might be
other opening and closing brackets on the `way' to find the
- matching bracket. For example in the brain*ck++ program
+ matching bracket. For example in the brain*ck program
\begin{center}
\texttt{--[\barbelow{.}.[+>]--].>.++}
@@ -283,7 +280,7 @@
\item[(4)] Write a recursive function \texttt{compute} that runs a
- brain*u*k++ program. It takes a program, a program counter, a memory
+ brain*u*k program. It takes a program, a program counter, a memory
pointer and a memory as arguments. If the program counter is outside
the program string, the execution stops and \texttt{compute} returns the
memory. If the program counter is inside the string, it reads the
@@ -291,14 +288,14 @@
memory pointer \texttt{mp} and memory \texttt{mem} according to the
rules shown in Figure~\ref{comms}. It then calls recursively
\texttt{compute} with the updated data. The most convenient way to
- implement the brainf**k++ rules in Scala is to use pattern-matching
+ implement the brainf**k rules in Scala is to use pattern-matching
and to calculate a triple consisting of the updated \texttt{pc},
\texttt{mp} and \texttt{mem}.
Write another function \texttt{run} that calls \texttt{compute} with a
- given brainfu*k++ program and memory, and the program counter and memory pointer
+ given brainfu*k program and memory, and the program counter and memory pointer
set to~$0$. Like \texttt{compute}, it returns the memory after the execution
- of the program finishes. You can test your brainf**k++ interpreter with the
+ of the program finishes. You can test your brainf**k interpreter with the
Sierpinski triangle or the Hello world programs (they seem to be particularly
useful for debugging purposes), or have a look at
@@ -306,7 +303,7 @@
\url{https://esolangs.org/wiki/Brainfuck}
\end{center}
- \noindent for more bf/bf++-programs and the test cases given in \texttt{bf.scala}.\\
+ \noindent for more bf-programs and the test cases given in \texttt{bf.scala}.\\
\mbox{}\hfill[2 Marks]
\begin{figure}[p]
@@ -361,36 +358,36 @@
$\bullet$ & $\texttt{pc} + 1$\\
$\bullet$ & $\texttt{mp}$ and \texttt{mem} unchanged\\
\end{tabular}\\\hline
- \hfill\texttt{'*'} & \begin{tabular}[t]{@{}l@{\hspace{2mm}}l@{}}
- $\bullet$ & $\texttt{pc} + 1$\\
- $\bullet$ & $\texttt{mp}$ unchanged\\
- $\bullet$ & \texttt{mem} updated with \texttt{mp -> mem(mp) * mem(mp - 1)}\\
- \multicolumn{2}{@{}l}{this multiplies the content of the memory cells at
- \texttt{mp} and \texttt{mp - 1}}\\
- \multicolumn{2}{@{}l}{and stores the result at \texttt{mp}}
- \end{tabular}\\\hline
- \hfill\texttt{'@'} & \begin{tabular}[t]{@{}l@{\hspace{2mm}}l@{}}
- $\bullet$ & $\texttt{pc} + 1$\\
- $\bullet$ & $\texttt{mp}$ unchanged\\
- $\bullet$ & \texttt{mem} updated with
- \texttt{mem(mp) -> mem(mp - 1)}\\
- \multicolumn{2}{@{}l}{this updates the memory cell having the index stored at \texttt{mem(mp)},}\\
- \multicolumn{2}{@{}l}{with the value stored at \texttt{mem(mp - 1)},}
- \end{tabular}\\\hline
- \hfill\texttt{'\#'} & \begin{tabular}[t]{@{}l@{\hspace{2mm}}l@{}}
- $\bullet$ & $\texttt{pc} + 1$\\
- $\bullet$ & $\texttt{mp}$ and \texttt{mem} unchanged\\
- $\bullet$ & print out \,\texttt{mem(mp)} as a number\\
- \end{tabular}\\\hline
+ %\hfill\texttt{'*'} & \begin{tabular}[t]{@{}l@{\hspace{2mm}}l@{}}
+ % $\bullet$ & $\texttt{pc} + 1$\\
+ % $\bullet$ & $\texttt{mp}$ unchanged\\
+ % $\bullet$ & \texttt{mem} updated with \texttt{mp -> mem(mp) * mem(mp - 1)}\\
+ % \multicolumn{2}{@{}l}{this multiplies the content of the memory cells at
+ % \texttt{mp} and \texttt{mp - 1}}\\
+ % \multicolumn{2}{@{}l}{and stores the result at \texttt{mp}}
+ % \end{tabular}\\\hline
+ %\hfill\texttt{'@'} & \begin{tabular}[t]{@{}l@{\hspace{2mm}}l@{}}
+ % $\bullet$ & $\texttt{pc} + 1$\\
+ % $\bullet$ & $\texttt{mp}$ unchanged\\
+ % $\bullet$ & \texttt{mem} updated with
+ % \texttt{mem(mp) -> mem(mp - 1)}\\
+ % \multicolumn{2}{@{}l}{this updates the memory cell having the index stored at \texttt{mem(mp)},}\\
+ % \multicolumn{2}{@{}l}{with the value stored at \texttt{mem(mp - 1)},}
+ % \end{tabular}\\\hline
+ %\hfill\texttt{'\#'} & \begin{tabular}[t]{@{}l@{\hspace{2mm}}l@{}}
+ % $\bullet$ & $\texttt{pc} + 1$\\
+ % $\bullet$ & $\texttt{mp}$ and \texttt{mem} unchanged\\
+ % $\bullet$ & print out \,\texttt{mem(mp)} as a number\\
+ % \end{tabular}\\\hline
any other char & \begin{tabular}[t]{@{}l@{\hspace{2mm}}l@{}}
- $\bullet$ & $\texttt{pc} + 1$\\
+ % $\bullet$ & $\texttt{pc} + 1$\\
$\bullet$ & \texttt{mp} and \texttt{mem} unchanged
\end{tabular}\\
\hline
\end{tabular}
\\\mbox{}\\[-10mm]\mbox{}
\end{center}
- \caption{The rules for how commands in the brainf***++ language update the
+ \caption{The rules for how commands in the brainf*** language update the
program counter \texttt{pc},
the memory pointer \texttt{mp} and the memory \texttt{mem}.\label{comms}}
\end{figure}
@@ -400,9 +397,9 @@
\subsection*{Part B (4 Marks)}
-I am sure you agree while it is fun to marvel at bf++-programs, like the
+I am sure you agree while it is fun to marvel at bf-programs, like the
Sierpinski triangle or the Mandelbrot program, being interpreted, it
-is much more fun to write a compiler for the bf++-language.
+is much more fun to write a compiler for the bf-language.
\subsubsection*{Tasks (file bfc.scala)}
@@ -415,7 +412,7 @@
loops.
For this write a function \texttt{jtable} that precomputes the ``jump
- table'' for a bf++-program. This function takes a bf++-program
+ table'' for a bf-program. This function takes a bf-program
as an argument and returns a \texttt{Map[Int, Int]}. The
purpose of this Map is to record the information, in cases
a pc-position points to a '\texttt{[}' or a '\texttt{]}',
@@ -460,21 +457,21 @@
at finding out what small snippets of code do, and then try to
generate faster code for such snippets.
- In our case, dead code is everything that is not a bf++-command.
+ In our case, dead code is everything that is not a bf-command.
Therefore write a function \texttt{optimise} which deletes such
- dead code from a bf++-program. Moreover this function should replace every substring
+ dead code from a bf-program. Moreover this function should replace every substring
of the form \pcode{[-]} by a new command \texttt{0}.
The idea is that the loop \pcode{[-]} just resets the
memory at the current location to 0. It is more efficient
to do this in a single step, rather than stepwise in a loop as in
- the original bf++-programs.
+ the original bf-programs.
In the extended \texttt{compute3} and \texttt{run3} functions you should
implement this command by writing 0 to \pcode{mem(mp)}, that is use
\pcode{write(mem, mp, 0)} as the rule for the command \texttt{0}.
The easiest way to modify a string in this way is to use the regular
- expression \pcode{"""[^<>+-.\\[\\]@\#*]"""}, which recognises everything that is
- not a bf++-command. Similarly, the
+ expression \pcode{"""[^<>+-.\\[\\]]"""}, which recognises everything that is
+ not a bf-command. Similarly, the
regular expression \pcode{"""\\[-\\]"""} finds all occurrences of \pcode{[-]}. By using the Scala method \pcode{.replaceAll} you can replace substrings
with new strings.\\
\mbox{}\hfill{[1 Mark]}
@@ -490,7 +487,7 @@
for the bf-commands \pcode{-}, \pcode{<} and
\pcode{>}, which can all be replaced by extended versions that take
the amount of the increment (decrement) into account. We will do
- this by introducing two-character bf++-commands. For example
+ this by introducing two-character bf-commands. For example
\begin{center}
\begin{tabular}{l|l}
@@ -509,17 +506,17 @@
If there are more
than 26 \pcode{+}'s in a row, then more than one ``two-character''
bf-commands need to be generated (the idea is that more than
- 26 copies of a single bf++-command in a row is a rare occurrence in
- actual bf++-programs). Similar replacements apply
+ 26 copies of a single bf-command in a row is a rare occurrence in
+ actual bf-programs). Similar replacements apply
for \pcode{-}, \pcode{<} and \pcode{>}, but
- all other bf++-commands should be unaffected by this
+ all other bf-commands should be unaffected by this
change.
For this write a function \texttt{combine} which replaces sequences
of repeated increment and decrement commands by appropriate
two-character commands. In the functions \pcode{compute4} and
\pcode{run4}, the ``combine'' and the optimisation from (6) should
- be performed. Make sure that when a two-character bf++-command is
+ be performed. Make sure that when a two-character bf-command is
encountered you need to increase the \pcode{pc}-counter by two in
order to progress to the next command. For example
--- a/main_solution5/bfc.scala Fri Nov 05 17:20:53 2021 +0000
+++ b/main_solution5/bfc.scala Sat Nov 06 00:06:39 2021 +0000
@@ -170,14 +170,14 @@
// 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
+// 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("""[^<>+-.\[\]@*#]""","")
+ s.replaceAll("""[^<>+-.\[\]]""","")
.replaceAll("""\[-\]""", "0")
}
Binary file main_templates4/knight2.jar has changed
Binary file main_templates4/knight3.jar has changed
Binary file main_templates5/bf.jar has changed
--- a/main_templates5/bf.scala Fri Nov 05 17:20:53 2021 +0000
+++ b/main_templates5/bf.scala Sat Nov 06 00:06:39 2021 +0000
@@ -1,12 +1,12 @@
-// Core Part about an Interpreter for
-// the Brainf***++ language
+// Main Part 5 about an Interpreter for
+// the Brainf*** language
//==============================================
-object CW10a {
+object M5a {
-// representation of Bf memory
+// representation of BF memory
type Mem = Map[Int, Int]
@@ -24,7 +24,7 @@
// (2) Complete the functions for safely reading
-// and writing brainf***++ memory. Safely read should
+// 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
@@ -39,7 +39,7 @@
// (3) Implement the two jumping instructions in the
-// brainf***++ language. In jumpRight, given a program and
+// 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
@@ -60,15 +60,15 @@
-// (4) Complete the compute function that interprets (runs) a brainf***++
+// (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
+// 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
+// rules of the brainf*** language. Then, recursively, the compute
// function continues with the command at the new program
// counter.
//
@@ -82,8 +82,8 @@
-// some sample bf/bf++-programs collected from the Internet
-//==========================================================
+// some sample bf-programs collected from the Internet
+//=====================================================
// some contrived (small) programs
@@ -103,15 +103,6 @@
// prints out numbers 0 to 9
//run("""+++++[->++++++++++<]>--<+++[->>++++++++++<<]>>++<<----------[+>.>.<+<]""")
-// bf++ program calculating the cube-function, 10 * 10 * 10 = 1000
-//run("""++++++++++#>+***#""") // Map(0 -> 10, 1 -> 1000)
-
-
-// bf++ program copies 3 from 0-cell to to cells 1, 4, 5, 6 and 7
-// (note that because of how the program wprks cell 1 will contain 7)
-//run("""+++>+@+@+@+@+@""") // Map(0 -> 3, 1 -> 7, 4 -> 3, 5 -> 3, 6 -> 3, 7 -> 3)
-
-
// some more "useful" programs
//-----------------------------
Binary file main_templates5/bfc.jar has changed
--- a/main_templates5/bfc.scala Fri Nov 05 17:20:53 2021 +0000
+++ b/main_templates5/bfc.scala Sat Nov 06 00:06:39 2021 +0000
@@ -1,8 +1,8 @@
-// Core Part about a "Compiler" for the Brainf*** language
-//======================================================
+// Main Part 5 about a "Compiler" for the Brainf*** language
+//============================================================
-object CW10b {
+object M5b {
// !!! Copy any function you need from file bf.scala !!!
@@ -95,7 +95,7 @@
// 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
+// expression """[^<>+-,\[\]]""", which recognises everything that is
// not a bf-command and replace it by the empty string. Similarly the
// regular expression """\[-\]""" finds all occurrences of [-] and
// by using the Scala method .replaceAll you can replace it with the
Binary file pre_solution1/collatz.jar has changed
--- a/pre_solution1/collatz.scala Fri Nov 05 17:20:53 2021 +0000
+++ /dev/null Thu Jan 01 00:00:00 1970 +0000
@@ -1,52 +0,0 @@
-// Basic Part about the 3n+1 conjecture
-//==================================
-
-// generate jar with
-// > scala -d collatz.jar collatz.scala
-
-object CW6a { // for purposes of generating a jar
-
-def collatz(n: Long): Long =
- if (n == 1) 0 else
- if (n % 2 == 0) 1 + collatz(n / 2) else
- 1 + collatz(3 * n + 1)
-
-
-def collatz_max(bnd: Long): (Long, Long) = {
- val all = for (i <- (1L to bnd)) yield (collatz(i), i)
- all.maxBy(_._1)
-}
-
-//collatz_max(1000000)
-//collatz_max(10000000)
-//collatz_max(100000000)
-
-/* some test cases
-val bnds = List(10, 100, 1000, 10000, 100000, 1000000)
-
-for (bnd <- bnds) {
- val (steps, max) = collatz_max(bnd)
- println(s"In the range of 1 - ${bnd} the number ${max} needs the maximum steps of ${steps}")
-}
-
-*/
-
-
-def is_pow(n: Long) : Boolean = (n & (n - 1)) == 0
-
-def is_hard(n: Long) : Boolean = is_pow(3 * n + 1)
-
-def last_odd(n: Long) : Long =
- if (is_hard(n)) n else
- if (n % 2 == 0) last_odd(n / 2) else
- last_odd(3 * n + 1)
-
-
-
-//for (i <- 130 to 10000) println(s"$i: ${last_odd(i)}")
-//for (i <- 1 to 100) println(s"$i: ${collatz(i)}")
-
-}
-
-
-
--- a/pre_testing1/collatz.scala Fri Nov 05 17:20:53 2021 +0000
+++ /dev/null Thu Jan 01 00:00:00 1970 +0000
@@ -1,50 +0,0 @@
-// Basic Part about the 3n+1 conjecture
-//==================================
-
-// generate jar with
-// > scala -d collatz.jar collatz.scala
-
-object CW6a { // for purposes of generating a jar
-
-def collatz(n: Long): Long =
- if (n == 1) 0 else
- if (n % 2 == 0) 1 + collatz(n / 2) else
- 1 + collatz(3 * n + 1)
-
-
-def collatz_max(bnd: Long): (Long, Long) = {
- val all = for (i <- (1L to bnd)) yield (collatz(i), i)
- all.maxBy(_._1)
-}
-
-//collatz_max(1000000)
-//collatz_max(10000000)
-//collatz_max(100000000)
-
-/* some test cases
-val bnds = List(10, 100, 1000, 10000, 100000, 1000000)
-
-for (bnd <- bnds) {
- val (steps, max) = collatz_max(bnd)
- println(s"In the range of 1 - ${bnd} the number ${max} needs the maximum steps of ${steps}")
-}
-
-*/
-
-def is_pow(n: Long) : Boolean = (n & (n - 1)) == 0
-
-def is_hard(n: Long) : Boolean = is_pow(3 * n + 1)
-
-def last_odd(n: Long) : Long =
- if (is_hard(n)) n else
- if (n % 2 == 0) last_odd(n / 2) else
- last_odd(3 * n + 1)
-
-
-//for (i <- 130 to 10000) println(s"$i: ${last_odd(i)}")
-//for (i <- 1 to 100) println(s"$i: ${collatz(i)}")
-
-}
-
-
-
--- a/pre_testing1/collatz_test.sh Fri Nov 05 17:20:53 2021 +0000
+++ /dev/null Thu Jan 01 00:00:00 1970 +0000
@@ -1,118 +0,0 @@
-#!/bin/bash
-
-# to make the script fail safely
-set -euo pipefail
-
-
-out=${1:-output}
-
-echo -e "" > $out
-
-echo -e "Below is the feedback for your submission collatz.scala" >> $out
-echo -e "" >> $out
-
-
-# compilation tests
-
-function scala_compile {
- (ulimit -t 30; JAVA_OPTS="-Xmx1g" scala -Xprint:parser "$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)
-}
-
-# purity test
-
-function scala_vars {
- (egrep '\bvar\b|\breturn\b|\.par\.|\.par |ListBuffer|AtomicInteger|mutable|util.control|new Array' c$out 2> /dev/null 1> /dev/null)
-}
-
-
-### compilation test
-
-echo -e "collatz.scala runs?" >> $out
-
-if (scala_compile collatz.scala)
-then
- echo -e " --> success" >> $out
- tsts=$(( 0 ))
-else
- echo -e " --> SCALA DID NOT RUN collatz.scala\n" >> $out
- tsts=$(( 1 ))
-fi
-
-
-
-# var, .par return, ListBuffer test
-#
-
-if [ $tsts -eq 0 ]
-then
- echo -e "collatz.scala does not contain VARS, RETURNS etc?" >> $out
-
- if (scala_vars collatz.scala)
- then
- echo -e " --> FAIL (make triple-sure your program conforms to the required format)\n" >> $out
- tsts=$(( 1 ))
- else
- echo -e " --> success" >> $out
- tsts=$(( 0 ))
- fi
-fi
-
-
-### collatz tests
-
-if [ $tsts -eq 0 ]
-then
- echo -e "collatz.scala tests:" >> $out
- echo -e " collatz(1) == 0" >> $out
- echo -e " collatz(6) == 8" >> $out
- echo -e " collatz(9) == 19" >> $out
-
- if (scala_assert "collatz.scala" "collatz_test1.scala")
- then
- echo -e " --> success" >> $out
- else
- echo -e " --> ONE OF THE TESTS FAILED\n" >> $out
- fi
-fi
-
-### collatz-max tests
-
-if [ $tsts -eq 0 ]
-then
- echo -e " collatz_max(10) == (19, 9)" >> $out
- echo -e " collatz_max(100) == (118, 97)" >> $out
- echo -e " collatz_max(1000) == (178, 871)" >> $out
- echo -e " collatz_max(10000) == (261, 6171)" >> $out
- echo -e " collatz_max(100000) == (350, 77031)" >> $out
- echo -e " collatz_max(1000000) == (524, 837799)" >> $out
-
- if (scala_assert "collatz.scala" "collatz_test2.scala")
- then
- echo -e " --> success" >> $out
- else
- echo -e " --> ONE OF THE TESTS FAILED\n" >> $out
- fi
-fi
-
-
-### last-odd tests
-
-if [ $tsts -eq 0 ]
-then
- echo -e " last_odd(113) == 85" >> $out
- echo -e " last_odd(84) == 21" >> $out
- echo -e " last_odd(605) == 341" >> $out
-
- if (scala_assert "collatz.scala" "collatz_test3.scala")
- then
- echo -e " --> success" >> $out
- else
- echo -e " --> ONE OF THE TESTS FAILED\n" >> $out
- fi
-fi
--- a/pre_testing1/collatz_test1.scala Fri Nov 05 17:20:53 2021 +0000
+++ /dev/null Thu Jan 01 00:00:00 1970 +0000
@@ -1,8 +0,0 @@
-
-import CW6a._
-
-assert(collatz(1) == 0)
-assert(collatz(6) == 8)
-assert(collatz(9) == 19)
-
-
--- a/pre_testing1/collatz_test2.scala Fri Nov 05 17:20:53 2021 +0000
+++ /dev/null Thu Jan 01 00:00:00 1970 +0000
@@ -1,8 +0,0 @@
-import CW6a._
-
-assert(collatz_max(10) == (19, 9))
-assert(collatz_max(100) == (118, 97))
-assert(collatz_max(1000) == (178, 871))
-assert(collatz_max(10000) == (261, 6171))
-assert(collatz_max(100000) == (350, 77031))
-assert(collatz_max(1000000) == (524, 837799))
--- a/pre_testing1/collatz_test3.scala Fri Nov 05 17:20:53 2021 +0000
+++ /dev/null Thu Jan 01 00:00:00 1970 +0000
@@ -1,4 +0,0 @@
-
-assert(CW6a.last_odd(113) == 85)
-assert(CW6a.last_odd(84) == 21)
-assert(CW6a.last_odd(605) == 341)