# HG changeset patch # User Christian Urban # Date 1636157199 0 # Node ID b17a98b0c52fac0b18f1733adc8ccf3dda420f40 # Parent 7d9b765d40121b99b036d3425d9505e16aaf15af updated diff -r 7d9b765d4012 -r b17a98b0c52f core_solution1/collatz.jar Binary file core_solution1/collatz.jar has changed diff -r 7d9b765d4012 -r b17a98b0c52f core_solution1/collatz.scala --- /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)}") + +} + + + diff -r 7d9b765d4012 -r b17a98b0c52f core_testing1/collatz.scala --- /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)}") + +} + + + diff -r 7d9b765d4012 -r b17a98b0c52f core_testing1/collatz_test.sh --- /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 diff -r 7d9b765d4012 -r b17a98b0c52f core_testing1/collatz_test1.scala --- /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) + + diff -r 7d9b765d4012 -r b17a98b0c52f core_testing1/collatz_test2.scala --- /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)) diff -r 7d9b765d4012 -r b17a98b0c52f core_testing1/collatz_test3.scala --- /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) diff -r 7d9b765d4012 -r b17a98b0c52f cws/main_cw01.pdf Binary file cws/main_cw01.pdf has changed diff -r 7d9b765d4012 -r b17a98b0c52f cws/main_cw01.tex --- 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 diff -r 7d9b765d4012 -r b17a98b0c52f cws/main_cw05.pdf Binary file cws/main_cw05.pdf has changed diff -r 7d9b765d4012 -r b17a98b0c52f cws/main_cw05.tex --- 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 diff -r 7d9b765d4012 -r b17a98b0c52f main_solution5/bfc.scala --- 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") } diff -r 7d9b765d4012 -r b17a98b0c52f main_templates4/knight2.jar Binary file main_templates4/knight2.jar has changed diff -r 7d9b765d4012 -r b17a98b0c52f main_templates4/knight3.jar Binary file main_templates4/knight3.jar has changed diff -r 7d9b765d4012 -r b17a98b0c52f main_templates5/bf.jar Binary file main_templates5/bf.jar has changed diff -r 7d9b765d4012 -r b17a98b0c52f main_templates5/bf.scala --- 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 //----------------------------- diff -r 7d9b765d4012 -r b17a98b0c52f main_templates5/bfc.jar Binary file main_templates5/bfc.jar has changed diff -r 7d9b765d4012 -r b17a98b0c52f main_templates5/bfc.scala --- 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 diff -r 7d9b765d4012 -r b17a98b0c52f pre_solution1/collatz.jar Binary file pre_solution1/collatz.jar has changed diff -r 7d9b765d4012 -r b17a98b0c52f pre_solution1/collatz.scala --- 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)}") - -} - - - diff -r 7d9b765d4012 -r b17a98b0c52f pre_testing1/collatz.scala --- 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)}") - -} - - - diff -r 7d9b765d4012 -r b17a98b0c52f pre_testing1/collatz_test.sh --- 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 diff -r 7d9b765d4012 -r b17a98b0c52f pre_testing1/collatz_test1.scala --- 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) - - diff -r 7d9b765d4012 -r b17a98b0c52f pre_testing1/collatz_test2.scala --- 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)) diff -r 7d9b765d4012 -r b17a98b0c52f pre_testing1/collatz_test3.scala --- 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)