# HG changeset patch # User Christian Urban # Date 1512648271 0 # Node ID 84917f2e16cdb9a913735b096a38442186a55dd4 # Parent 6d25ccbb3cf204f9fa57ee6ce3c7ea06134138cc updated diff -r 6d25ccbb3cf2 -r 84917f2e16cd LINKS --- a/LINKS Tue Dec 05 00:34:14 2017 +0000 +++ b/LINKS Thu Dec 07 12:04:31 2017 +0000 @@ -4,6 +4,7 @@ why functional programming matters http://queue.acm.org/detail.cfm?id=2038036 +============= BufferOverflow diff -r 6d25ccbb3cf2 -r 84917f2e16cd cws/cw02.tex --- a/cws/cw02.tex Tue Dec 05 00:34:14 2017 +0000 +++ b/cws/cw02.tex Thu Dec 07 12:04:31 2017 +0000 @@ -56,7 +56,7 @@ \subsection*{Disclaimer} It should be understood that the work you submit represents -your own effort. You have not copied from anyone else. An +your \textbf{own} effort. You have not copied from anyone else. An exception is the Scala code I showed during the lectures or uploaded to KEATS, which you can freely use. diff -r 6d25ccbb3cf2 -r 84917f2e16cd cws/cw03.pdf Binary file cws/cw03.pdf has changed diff -r 6d25ccbb3cf2 -r 84917f2e16cd cws/cw03.tex --- a/cws/cw03.tex Tue Dec 05 00:34:14 2017 +0000 +++ b/cws/cw03.tex Thu Dec 07 12:04:31 2017 +0000 @@ -45,6 +45,33 @@ 28 29.81185 \end{filecontents} +\begin{filecontents}{re-java9.data} +1000 0.01410 +2000 0.04882 +3000 0.10609 +4000 0.17456 +5000 0.27530 +6000 0.41116 +7000 0.53741 +8000 0.70261 +9000 0.93981 +10000 0.97419 +11000 1.28697 +12000 1.51387 +14000 2.07079 +16000 2.69846 +20000 4.41823 +24000 6.46077 +26000 7.64373 +30000 9.99446 +34000 12.966885 +38000 16.281621 +42000 19.180228 +46000 21.984721 +50000 26.950203 +60000 43.0327746 +\end{filecontents} + \begin{document} @@ -92,7 +119,7 @@ \subsection*{Disclaimer} It should be understood that the work you submit represents -your own effort! You have not copied from anyone else. An +your \textbf{own} effort! You have not copied from anyone else. An exception is the Scala code I showed during the lectures or uploaded to KEATS, which you can freely use.\bigskip @@ -359,28 +386,53 @@ 30 seconds time limit? \begin{center} +\begin{tabular}{@{}cc@{}} +\multicolumn{2}{c}{Graph: $(a^*)^*\cdot b$ and strings + $\underbrace{a\ldots a}_{n}$}\bigskip\\ + \begin{tikzpicture} \begin{axis}[ - title={Graph: $(a^*)^*\cdot b$ and strings - $\underbrace{a\ldots a}_{n}$}, xlabel={$n$}, x label style={at={(1.05,0.0)}}, ylabel={time in secs}, + y label style={at={(0.06,0.5)}}, enlargelimits=false, xtick={0,5,...,30}, xmax=33, - ymax=35, - ytick={0,5,...,30}, + ymax=45, + ytick={0,5,...,40}, scaled ticks=false, axis lines=left, width=6cm, height=5.5cm, legend entries={Python, Java 8}, - legend pos=outer north east] + legend pos=north west] \addplot[blue,mark=*, mark options={fill=white}] table {re-python2.data}; \addplot[cyan,mark=*, mark options={fill=white}] table {re-java.data}; \end{axis} \end{tikzpicture} + & +\begin{tikzpicture} +\begin{axis}[ + xlabel={$n$}, + x label style={at={(1.05,0.0)}}, + ylabel={time in secs}, + y label style={at={(0.06,0.5)}}, + %enlargelimits=false, + %xtick={0,5000,...,30000}, + xmax=65000, + ymax=45, + ytick={0,5,...,40}, + scaled ticks=false, + axis lines=left, + width=6cm, + height=5.5cm, + legend entries={Java 9}, + legend pos=north west] +\addplot[cyan,mark=*, mark options={fill=white}] table {re-java9.data}; +\end{axis} +\end{tikzpicture} +\end{tabular} \end{center} \newpage diff -r 6d25ccbb3cf2 -r 84917f2e16cd progs/catastrophic.java --- a/progs/catastrophic.java Tue Dec 05 00:34:14 2017 +0000 +++ b/progs/catastrophic.java Thu Dec 07 12:04:31 2017 +0000 @@ -9,12 +9,12 @@ public static void main(String[] args) { //we always run all the tests twice -> warmup of the JVM - for (int runs = 0; runs < 2; runs++) { + for (int runs = 0; runs < 3; runs++) { Pattern pattern = Pattern.compile("(a*)*b"); // Run from 5 to 28 characters - for (int length = 5; length < 28; length++) { + for (int length = 70000; length < 70001; length++) { // Build input of specified length String input = ""; @@ -27,7 +27,7 @@ } System.out.println(length + " " + input + ": " - + ((System.nanoTime() - start) / 2000000000d) + + ((System.nanoTime() - start) / 3000000000d) + "s"); } } diff -r 6d25ccbb3cf2 -r 84917f2e16cd template3/bf.scala --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/template3/bf.scala Thu Dec 07 12:04:31 2017 +0000 @@ -0,0 +1,151 @@ +// Part 2 about an Interpreter for the Brainf*** language +//======================================================== + +object CW8b { + +type Mem = Map[Int, Int] + +// (2a) 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, if 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 sread(mem: Mem, mp: Int) : Int = ... + +//def write(mem: Mem, mp: Int, v: Int) : Mem = ... + + +// (2b) Implement the two jumping instructions in the +// brainf*** language. In jumpRight, given a program and +// a program counter move the counter to the right +// until the command after the *matching* ]-command. Similarly, +// jumpLeft implements the move to the left to just after +// the *matching* [-command. The levels are used to find the +// *matching* bracket. + +//def jumpRight(prog: String, pc: Int, level: Int) : Int = ... + +//def jumpLeft(prog: String, pc: Int, level: Int) : Int = ... + + + +// (2c) Complete the run function that interprets (runs) a brainf*** +// program: the arguments are a program, 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 run +// function continues with the command at the new program +// counter. +// +// Implement the start function that calls run with the program +// counter and memory counter set to 0. + +//def run(prog: String, pc: Int, mp: Int, mem: Mem) : Mem = ... + +//def start(prog: String, mem: Mem) = ... + + + + + + +// some sample bf programs collected from the Internet +//================================================== + + +/* +// first some contrived (small) programs + +// clears the 0-cell +start("[-]", Map(0 -> 100)) + +// copies content of the 0-cell to 1-cell +start("[->+<]", Map(0 -> 10)) + +// copies content of the 0-cell to 2-cell and 4-cell +start("[>>+>>+<<<<-]", Map(0 -> 42)) + +start("+++[>+++++<-]", Map(0 -> 10)) + + +// prints out numbers 0 to 9 +start("""+++++[->++++++++++<]>--<+++[->>++++++++++<<]>>++<<----------[+>.>.<+<]""", Map()) + + +// some more "useful" programs + +// hello world program 1 +start("""++++++++[>++++[>++>+++>+++>+<<<<-]>+>+>->>+[<]<-]>>.>---.+++++++ + ..+++.>>.<-.<.+++.------.--------.>>+.>++.""", Map()) + +// hello world program 2 +start("""++++++++++[>+++++++>++++++++++>+++>+<<<<-]>++.>+.+++++++..+++.>+ + +.<<+++++++++++++++.>.+++.------.--------.>+.>.""", Map()) + + +// draws the Sierpinski triangle +start("""++++++++[>+>++++<<-]>++>>+<[-[>>+<<-]+>>]>+[-<<<[ + ->[+[-]+>++>>>-<<]<[<]>>++++++[<<+++++>>-]+<<++.[-]<< + ]>.>+[>>]>+]""", Map()) + +//Fibonacci numbers below 100 +start("""+++++++++++ + >+>>>>++++++++++++++++++++++++++++++++++++++++++++ + >++++++++++++++++++++++++++++++++<<<<<<[>[>>>>>>+> + +<<<<<<<-]>>>>>>>[<<<<<<<+>>>>>>>-]<[>++++++++++[- + <-[>>+>+<<<-]>>>[<<<+>>>-]+<[>[-]<[-]]>[<<[>>>+<<< + -]>>[-]]<<]>>>[>>+>+<<<-]>>>[<<<+>>>-]+<[>[-]<[-]] + >[<<+>>[-]]<<<<<<<]>>>>>[+++++++++++++++++++++++++ + +++++++++++++++++++++++.[-]]++++++++++<[->-<]>++++ + ++++++++++++++++++++++++++++++++++++++++++++.[-]<< + <<<<<<<<<<[>>>+>+<<<<-]>>>>[<<<<+>>>>-]<-[>>.>.<<< + [-]]<<[>>+>+<<<-]>>>[<<<+>>>-]<<[<+>-]>[<+>-]<<<-]""", Map()) + + +//outputs the square numbers up to 10000 +start("""++++[>+++++<-]>[<+++++>-]+<+[ + >[>+>+<<-]++>>[<<+>>-]>>>[-]++>[-]+ + >>>+[[-]++++++>>>]<<<[[<++++++++<++>>-]+<.<[>----<-]<] + <<[>>>>>[>>>[-]+++++++++<[>-<-]+++++++++>[-[<->-]+[<<<]]<[>+<-]>]<<-]<<-]""", Map()) + + +//Collatz numbers (need to be typed in) +start(""">,[[----------[ + >>>[>>>>]+[[-]+<[->>>>++>>>>+[>>>>]++[->+<<<<<]]<<<] + ++++++[>------<-]>--[>>[->>>>]+>+[<<<<]>-],<]>]>>>++>+>>[ + <<[>>>>[-]+++++++++<[>-<-]+++++++++>[-[<->-]+[<<<<]]<[>+<-]>] + >[>[>>>>]+[[-]<[+[->>>>]>+<]>[<+>[<<<<]]+<<<<]>>>[->>>>]+>+[<<<<]] + >[[>+>>[<<<<+>>>>-]>]<<<<[-]>[-<<<<]]>>>>>>> + ]>>+[[-]++++++>>>>]<<<<[[<++++++++>-]<.[-]<[-]<[-]<]<,]""", Map()) + + +// infinite Collatz (never stops) +start(""">>+>+<[[->>[>>]>>>[>>]+[<<]<<<[<<]>[>[>>]>>+>[>>]<+<[<<]<<<[< + <]>-]>[>>]>>[<<<<[<<]>+>[>>]>>-]<<<<[<<]+>>]<<[+++++[>+++++++ + +<-]>.<++++++[>--------<-]+<<]>>[>>]+[>>>>[<<+>+>-]<-[>+<-]+< + [<<->>-[<<+>>[-]]]>>>[<<<+<<+>>>>>-]<<<[>>>+<<<-]<<[[-]>+>>-> + [<+<[<<+>>-]<[>+<-]<[>+<-]>>>>-]<[>+<-]+<[->[>>]<<[->[<+++>-[ + <+++>-[<+++>-[<[-]++>>[-]+>+<<-[<+++>-[<+++>-[<[-]+>>>+<<-[<+ + ++>-[<+++>-]]]]]]]]]<[>+<-]+<<]>>>+<[->[<+>-[<+>-[<+>-[<+>-[< + +>-[<+>-[<+>-[<+>-[<+>-[<[-]>>[-]+>+<<-[<+>-]]]]]]]]]]]<[>+<- + ]+>>]<<[<<]>]<[->>[->+>]<[-[<+>-[<->>+<-[<+>-[<->>+<-[<+>-[<- + >>+<-[<+>-[<->>+<-[<+>-[<->>+<-[<+>-[<->>+<-[<+>-[<->>+<-[<+> + -[<->>+<-[<+>-[<->>+<-[<+>-]]]]]]]]]]]]]]]]]]]>[<+>-]<+<[<+++ + +++++++>-]<]>>[<+>->>]<<[>+>+<<-]>[<+>-]+>[<->[-]]<[-<<-]<<[< + <]]++++++[>+++++++<-]>++.------------.[-]>[>>]<<[+++++[>+++++ + +++<-]>.<++++++[>--------<-]+<<]+<]>[<+>-]<]>>>[>>]<<[>[-]<-< + <]++++++++++.[-]<<<[<<]>>>+<[->[<+>-[<+>-[<+>-[<+>-[<+>-[<+>- + [<+>-[<+>-[<+>-[<[-]>>[-]+>+<<-]]]]]]]]]]<[>+<-]+>>]<<[<<]>>]""", Map()) + + +*/ + +} diff -r 6d25ccbb3cf2 -r 84917f2e16cd template3/re.scala --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/template3/re.scala Thu Dec 07 12:04:31 2017 +0000 @@ -0,0 +1,127 @@ +// Part 1 about Regular Expression Matching +//========================================== + + +object CW8a { + +abstract class Rexp +case object ZERO extends Rexp +case object ONE extends Rexp +case class CHAR(c: Char) extends Rexp +case class ALT(r1: Rexp, r2: Rexp) extends Rexp // alternative +case class SEQ(r1: Rexp, r2: Rexp) extends Rexp // sequence +case class STAR(r: Rexp) extends Rexp // star + + +// some convenience for typing in 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) + +implicit def RexpOps (r: Rexp) = new { + 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) +} + +// (1a) Complete the function nullable according to +// the definition given in the coursework; this +// function checks whether a regular expression +// can match the empty string and Returns a boolean +// accordingly. + +//def nullable (r: Rexp) : Boolean = ... + + +// (1b) Complete the function der according to +// the definition given in the coursework; this +// function calculates the derivative of a +// regular expression w.r.t. a character. + +//def der (c: Char, r: Rexp) : Rexp = ... + + +// (1c) Complete the simp function according to +// the specification given in the coursework; this +// function simplifies a regular expression from +// the inside out, like you would simplify arithmetic +// expressions; however it does not simplify inside +// STAR-regular expressions. + +//def simp(r: Rexp) : Rexp = ... + + +// (1d) Complete the two functions below; the first +// calculates the derivative w.r.t. a string; the second +// is the regular expression matcher taking a regular +// expression and a string and checks whether the +// string matches the regular expression + +//def ders (s: List[Char], r: Rexp) : Rexp = ... + +//def matcher(r: Rexp, s: String): Boolean = ... + + +// (1e) Complete the size function for regular +// expressions according to the specification +// given in the coursework. + +//def size(r: Rexp): Int = ... + + +// some testing data + +/* +matcher(("a" ~ "b") ~ "c", "abc") // => true +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 ++ "b") // => true +matcher(EVIL, "a" * 1000) // => false + +// size without simplifications +size(der('a', der('a', EVIL))) // => 28 +size(der('a', der('a', der('a', EVIL)))) // => 58 + +// size with simplification +size(simp(der('a', der('a', EVIL)))) // => 8 +size(simp(der('a', der('a', der('a', EVIL))))) // => 8 + +// Java needs around 30 seconds for matching 28 a's with EVIL. +// +// Lets see how long it takes to match strings with +// 0.5 Million a's...it should be in the range of some +// seconds. + +def time_needed[T](i: Int, code: => T) = { + val start = System.nanoTime() + for (j <- 1 to i) code + val end = System.nanoTime() + (end - start)/(i * 1.0e9) +} + +for (i <- 0 to 5000000 by 500000) { + println(i + " " + "%.5f".format(time_needed(2, matcher(EVIL, "a" * i)))) +} + +*/ + + +} diff -r 6d25ccbb3cf2 -r 84917f2e16cd testing2/knight1.scala --- a/testing2/knight1.scala Tue Dec 05 00:34:14 2017 +0000 +++ b/testing2/knight1.scala Thu Dec 07 12:04:31 2017 +0000 @@ -1,91 +1,133 @@ + // Part 1 about finding and counting Knight's tours //================================================== -object CW7a { +object CW7a extends App{ type Pos = (Int, Int) // a position on a chessboard type Path = List[Pos] // a path...a list of positions -def print_board(dim: Int, path: Path): Unit = { - println - for (i <- 0 until dim) { - for (j <- 0 until dim) { - print(f"${path.reverse.indexOf((j, dim - i - 1))}%3.0f ") - } - println - } -} +//(1a) Complete the function that tests whether the position +// is inside the board and not yet element in the path. + +//def is_legal(dim: Int, path: Path)(x: Pos) : Boolean = ... -def add_pair(x: Pos)(y: Pos): Pos = - (x._1 + y._1, x._2 + y._2) - -def is_legal(dim: Int, path: Path)(x: Pos): Boolean = - 0 <= x._1 && 0 <= x._2 && x._1 < dim && x._2 < dim && !path.contains(x) - -assert(is_legal(8, Nil)((3,4)) == true) -assert(is_legal(8, List((4,1), (1,0)))((4,1)) == false) -assert(is_legal(2, Nil)((0,0)) == true) +def is_legal(dim: Int, path: Path)(x: Pos) : Boolean = { + +// if ((x._10 || x._2>0)) false else !path.contains(x) + + if (x._1 < 0 || x._2 < 0) false + else if (x._1 < dim && x._2 < dim && !path.contains(x)) true + else false + + +} -def moves(x: Pos): List[Pos] = - List(( 1, 2),( 2, 1),( 2, -1),( 1, -2), - (-1, -2),(-2, -1),(-2, 1),(-1, 2)).map(add_pair(x)) - -def legal_moves(dim: Int, path: Path, x: Pos): List[Pos] = - moves(x).filter(is_legal(dim, path)) - -def count_tours(dim: Int, path: Path): Int = { - if (path.length == dim * dim) 1 - else - (for (x <- legal_moves(dim, path, path.head)) yield count_tours(dim, x::path)).sum -} - -def count_tours(dim: Int, path : Path) : Int = { +def legal_moves(dim: Int, path: Path, x: Pos) : List[Pos] = { + + val allPossibleMoves = List((x._1+1, x._2+2), (x._1+2, x._2+1), (x._1+2, x._2-1), (x._1+1, x._2-2), (x._1-1, x._2-2), (x._1-2, x._2-1), (x._1-2, x._2+1), (x._1-1, x._2+2)); + + //val finalList = allPossibleMoves.filter((a=>a._1= 0 && a._2 >= 0)); - if (path.length == dim * dim) {1} - else - val x = for (m <- legal_moves(dim,path,path.head)) yield { + val finalList = for(pos<-allPossibleMoves if(is_legal(dim,path)(pos))) yield pos; + + // println("Space in board: " + dim*dim + " for dim: " + dim) + + + finalList.toList; - count_tours(dim,m::path) - } - x.sum } -def enum_tours(dim: Int, path: Path): List[Path] = { - if (path.length == dim * dim) List(path) - else - (for (x <- legal_moves(dim, path, path.head)) yield enum_tours(dim, x::path)).flatten -} +println(legal_moves(8, Nil, (2,2))) +println(legal_moves(8, Nil, (7,7))) +println(legal_moves(8, List((4,1), (1,0)), (2,2))) +println(legal_moves(8, List((6,6)), (7,7))) +println(legal_moves(1, Nil, (0,0))) +println(legal_moves(2, Nil, (0,0))) +println(legal_moves(3, Nil, (0,0))) + +println("=================================================================================") +println("================================Comparision output===============================") +println("=================================================================================") + +println(legal_moves(8, Nil, (2,2)) == List((3,4), (4,3), (4,1), (3,0), (1,0), (0,1), (0,3), (1,4))) +println(legal_moves(8, Nil, (7,7)) == List((6,5), (5,6))) +println(legal_moves(8, List((4,1), (1,0)), (2,2)) == List((3,4), (4,3), (3,0), (0,1), (0,3), (1,4))) +println(legal_moves(8, List((6,6)), (7,7)) == List((6,5), (5,6))) +println(legal_moves(1, Nil, (0,0)) == Nil) +println(legal_moves(2, Nil, (0,0)) == Nil) +println(legal_moves(3, Nil, (0,0)) == List((1,2), (2,1))) + -def count_all_tours(dim: Int) = { - for (i <- (0 until dim).toList; - j <- (0 until dim).toList) yield count_tours(dim, List((i, j))) +def count_tours(dim: Int, path: Path) : Int = { + + val allMovesFromCurrentPosition = legal_moves(dim, path, path.head); + + if (path.length == dim*dim) 1 else { + + if (allMovesFromCurrentPosition.size == 0 ) 0 else { + + allMovesFromCurrentPosition.map( element => count_tours(dim, element::path)).sum + + + } + + } + } + + -def enum_all_tours(dim: Int): List[Path] = { - (for (i <- (0 until dim).toList; - j <- (0 until dim).toList) yield enum_tours(dim, List((i, j)))).flatten +println ( count_tours(5, List((0,0))) ) + +def enum_tours(dim: Int, path: Path) : List[Path] = { + + val allMovesFromCurrentPosition = legal_moves(dim, path, path.head); + + if (path.length == dim*dim) List(path) else { + + allMovesFromCurrentPosition.map( element => enum_tours(dim, element::path)).flatten ; + + + } + } + println ( enum_tours(6, List((0,2))).size) } -/* -for (dim <- 1 to 5) { - println(s"${dim} x ${dim} " + count_tours(dim, List((0, 0)))) -} + + + -for (dim <- 1 to 5) { - println(s"${dim} x ${dim} " + count_all_tours(dim)) -} + + +//(1b) Complete the function that calculates for a position +// all legal onward moves that are not already in the path. +// The moves should be ordered in a "clockwise" manner. + +//def legal_moves(dim: Int, path: Path, x: Pos) : List[Pos] = ... + + + -for (dim <- 1 to 5) { - val ts = enum_tours(dim, List((0, 0))) - println(s"${dim} x ${dim} ") - if (ts != Nil) { - print_board(dim, ts.head) - println(ts.head) - } -} -*/ +//some test cases +// +//assert(legal_moves(8, Nil, (2,2)) == +// List((3,4), (4,3), (4,1), (3,0), (1,0), (0,1), (0,3), (1,4))) +//assert(legal_moves(8, Nil, (7,7)) == List((6,5), (5,6))) +//assert(legal_moves(8, List((4,1), (1,0)), (2,2)) == +// List((3,4), (4,3), (3,0), (0,1), (0,3), (1,4))) +//assert(legal_moves(8, List((6,6)), (7,7)) == List((6,5), (5,6))) + -} +//(1c) Complete the two recursive functions below. +// They exhaustively search for knight's tours starting from the +// given path. The first function counts all possible tours, +// and the second collects all tours in a list of paths. + +//def count_tours(dim: Int, path: Path) : Int = ... + + +//def enum_tours(dim: Int, path: Path) : List[Path] = ...