# HG changeset patch # User Christian Urban # Date 1610678457 0 # Node ID 6e12376913071f4a8d8107d6a73c1f24b8bc4ef2 # Parent c02929f2647c923aeb1f8706624207ee0a46033f updated diff -r c02929f2647c -r 6e1237691307 LINKS --- a/LINKS Mon Dec 07 01:25:41 2020 +0000 +++ b/LINKS Fri Jan 15 02:40:57 2021 +0000 @@ -46,6 +46,11 @@ ===================== +Nice video on JSON denial of service attacks + +https://www.youtube.com/watch?v=3Cz6D8JLSSA + +===================== code example (bar code decoder) https://habr.com/en/post/439768/ diff -r c02929f2647c -r 6e1237691307 main_solution1/drumb.scala --- a/main_solution1/drumb.scala Mon Dec 07 01:25:41 2020 +0000 +++ b/main_solution1/drumb.scala Fri Jan 15 02:40:57 2021 +0000 @@ -24,7 +24,7 @@ // strings for each line in the CSV-file. def get_january_data(symbol: String, year: Int) : List[String] = - Source.fromFile(symbol ++ ".csv")("ISO-8859-1").getLines().toList.filter(_.startsWith(year.toString)) + Source.fromFile(symbol ++ ".csv")("ISO-8859-1").getLines.toList.filter(_.startsWith(year.toString)) //test cases diff -r c02929f2647c -r 6e1237691307 main_solution2/danube.scala --- a/main_solution2/danube.scala Mon Dec 07 01:25:41 2020 +0000 +++ b/main_solution2/danube.scala Fri Jan 15 02:40:57 2021 +0000 @@ -42,7 +42,7 @@ def process_ratings(lines: List[String]) : List[(String, String)] = { for (cols <- lines.map(_.split(",").toList); - if (cols(2).toFloat >= 4)) yield (cols(0), cols(1)) + if (cols(2).toInt >= 4)) yield (cols(0), cols(1)) } def process_movies(lines: List[String]) : List[(String, String)] = { diff -r c02929f2647c -r 6e1237691307 main_solution5/bfc.scala --- a/main_solution5/bfc.scala Mon Dec 07 01:25:41 2020 +0000 +++ b/main_solution5/bfc.scala Fri Jan 15 02:40:57 2021 +0000 @@ -294,7 +294,7 @@ } // testcases -//println(combine(optimise(load_bff("collatz.bf")))) +//println(combine(optimise(load_bff("mandelbrot.bf").drop(123)))) //combine(optimise(load_bff("benchmark.bf"))) // => """>A+B[A-A]+-.,\[\]]""", 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 c02929f2647c -r 6e1237691307 main_testing2/danube.scala --- a/main_testing2/danube.scala Mon Dec 07 01:25:41 2020 +0000 +++ b/main_testing2/danube.scala Fri Jan 15 02:40:57 2021 +0000 @@ -1,9 +1,8 @@ -// Core Part about Movie Recommendations +// Core Part about Movie Recommendations // at Danube.co.uk -//======================================== +//=========================================== - -object CW7b { // for purposes of generating a jar +object CW7b { import io.Source import scala.util._ @@ -13,99 +12,182 @@ // as argument and requests the corresponding file. The two urls // of interest are ratings_url and movies_url, which correspond // to CSV-files. -// The function should return the CSV file appropriately broken +// +// The function should ReTurn the CSV-file appropriately broken // up into lines, and the first line should be dropped (that is without -// the header of the CSV file). The result is a list of strings (lines +// the header of the CSV-file). The result is a list of strings (lines // in the file). def get_csv_url(url: String) : List[String] = { - val csv = Source.fromURL(url)("ISO-8859-1") - csv.mkString.split("\n").toList.drop(1) + val site = Source.fromURL(url, "ISO-8859-1") + val site_string = site.mkString + val output = (site_string.split("\n")).toList + output.tail } -val ratings_url = """https://nms.kcl.ac.uk/christian.urban/ratings.csv""" -val movies_url = """https://nms.kcl.ac.uk/christian.urban/movies.csv""" + // get_csv_url("https://nms.kcl.ac.uk/christian.urban/ratings.csv") + +//val ratings_url = """https://nms.kcl.ac.uk/christian.urban/ratings.csv""" +//val movies_url = """https://nms.kcl.ac.uk/christian.urban/movies.csv""" -// test cases - -//val ratings = get_csv_url(ratings_url) +// testcases +//----------- +//: //val movies = get_csv_url(movies_url) + // val ratings = get_csv_url(ratings_url) //ratings.length // 87313 //movies.length // 9742 -// (2) Implement two functions that process the CSV files. The ratings -// function filters out all ratings below 4 and returns a list of -// (userID, movieID) pairs. The movies function just returns a list -// of (movieId, title) pairs. + +// (2) Implement two functions that process the CSV-files from (1). The ratings +// function filters out all ratings below 4 and ReTurns a list of +// (userID, movieID) pairs. The movies function just ReTurns a list +// of (movieID, title) pairs. Note the input to these functions, that is +// the argument lines, will be the output of the function get_csv_url. -//def process_ratings(lines: List[String]) : List[(String, String)] = { -// for (cols <- lines.map(_.split(",").toList); -// if (cols(2).toFloat >= 4)) yield (cols(0), cols(1)) -//} - def process_ratings(lines: List[String]) : List[(String, String)] = { - for (cols <- lines.map(_.split(",").toList); - if (cols(2).toInt >= 4)) yield (cols(0), cols(1)) + val filter = lines.filter(_.last.asDigit >=4) + val output = (for(i <- 0 until filter.length) yield ((filter(i).split(",").toList)(0), (filter(i).split(",").toList)(1))).toList + output } def process_movies(lines: List[String]) : List[(String, String)] = { + val output = (for(i <- 0 until lines.length) yield ((lines(i).split(",").toList)(0), (lines(i).split(",").toList)(1))).toList + output +} + + + +def process_ratings2(lines: List[String]) : List[(String, String)] = { + for (cols <- lines.map(_.split(",").toList); + if (cols(2).toFloat >= 4)) yield (cols(0), cols(1)) +} + +def process_movies2(lines: List[String]) : List[(String, String)] = { for (cols <- lines.map(_.split(",").toList)) yield (cols(0), cols(1)) } -// test cases - +// testcases +//----------- //val good_ratings = process_ratings(ratings) //val movie_names = process_movies(movies) //good_ratings.length //48580 //movie_names.length // 9742 -//============================================== -// Do not change anything below, unless you want -// to submit the file for the advanced part 3! -//============================================== + -// (3) Implement a grouping function that calulates a map -// containing the userIds and all the corresponding recommendations -// (list of movieIds). This should be implemented in a tail -// recursive fashion, using a map m as accumulator. This map -// is set to Map() at the beginning of the claculation. +// (3) Implement a grouping function that calculates a Map +// containing the userIDs and all the corresponding recommendations +// (list of movieIDs). This should be implemented in a tail +// recursive fashion, using a Map m as accumulator. This Map m +// is set to Map() at the beginning of the calculation. + +val ratings_url = """https://nms.kcl.ac.uk/christian.urban/ratings.csv""" +val ratings = get_csv_url(ratings_url) +val good_ratings = process_ratings(ratings) +val v515 = good_ratings.filter(_._1 == "515") +val v515_2 = v515.map(_._2) def groupById(ratings: List[(String, String)], + m: Map[String, List[String]]) : Map[String, List[String]] = { +val users = (for((k,v) <- ratings) yield k).distinct +val movie_ids = (for(i <- 1 to users.length) yield + (for ((k,v) <- ratings if(i.toString == k)) yield v).toList).toList + val out_map = (users zip movie_ids).toMap +out_map +} + +def groupById2(ratings: List[(String, String)], m: Map[String, List[String]]) : Map[String, List[String]] = ratings match { case Nil => m case (id, mov) :: rest => { val old_ratings = m.getOrElse (id, Nil) val new_ratings = m + (id -> (mov :: old_ratings)) - groupById(rest, new_ratings) + groupById2(rest, new_ratings) } } -// test cases +val ls0_urban = + List(("1", "a"), ("1", "c"), ("1", "c")) + +groupById(ls0_urban, Map()) +groupById2(ls0_urban, Map()) + +val ls00_urban = + List(("3", "a"), ("3", "c"), ("3", "c")) + +groupById(ls00_urban, Map()) +groupById2(ls00_urban, Map()) + +groupById(good_ratings, Map()).getOrElse("515", Nil) +groupById2(good_ratings, Map()).getOrElse("515", Nil) + +val ls1_urban = + List(("1", "a"), ("2", "a"), + ("1", "c"), ("2", "a"), ("1", "c")) + +groupById(ls1_urban, Map()) +groupById2(ls1_urban, Map()) + +val ls2_urban = + List(("1", "a"), ("1", "b"), ("2", "x"), + ("3", "a"), ("2", "y"), ("3", "c")) + +groupById(ls2_urban, Map()) +groupById2(ls2_urban, Map()) + +val ls3_urban = (1 to 1000 by 10).map(_.toString).toList +val ls4_urban = ls3_urban zip ls3_urban.tail +val ls5_urban = ls4_urban ::: ls4_urban.reverse + +groupById(ls5_urban, Map()) == groupById2(ls5_urban, Map()) + +groupById(ls5_urban, Map()) +groupById2(ls5_urban, Map()) + +groupById(v515, Map()) +groupById2(v515, Map()) + +groupById(v515.take(1), Map()) +groupById2(v515.take(2), Map()) + +// testcases +//----------- //val ratings_map = groupById(good_ratings, Map()) //val movies_map = movie_names.toMap -//ratings_map.get("414").get.map(movies_map.get(_)) // most prolific recommender with 1227 positive ratings -//ratings_map.get("474").get.map(movies_map.get(_)) // second-most prolific recommender with 787 positive ratings -//ratings_map.get("214").get.map(movies_map.get(_)) // least prolific recommender with only 1 positive rating +//ratings_map.get("414").get.map(movies_map.get(_)).length +// => most prolific recommender with 1227 positive ratings + +//ratings_map.get("475").get.map(movies_map.get(_)).length +// => second-most prolific recommender with 787 positive ratings + +//ratings_map.get("214").get.map(movies_map.get(_)).length +// => least prolific recommender with only 1 positive rating -//(4) Implement a function that takes a ratings map and a movie_name as argument. -// The function calculates all suggestions containing -// the movie mov in its recommendations. It returns a list of all these -// recommendations (each of them is a list and needs to have mov deleted, -// otherwise it might happen we recommend the same movie). +// (4) Implement a function that takes a ratings map and a movie_name as argument. +// The function calculates all suggestions containing +// the movie in its recommendations. It ReTurns a list of all these +// recommendations (each of them is a list and needs to have the movie deleted, +// otherwise it might happen we recommend the same movie). -def favourites(m: Map[String, List[String]], mov: String) : List[List[String]] = + +def favourites(m: Map[String, List[String]], mov: String) : List[List[String]] = { + (for((k,v) <- m if (v.contains(mov))) yield v.filter(_!=mov).toList).toList +} + +def favourites2(m: Map[String, List[String]], mov: String) : List[List[String]] = (for (id <- m.keys.toList; if m(id).contains(mov)) yield m(id).filter(_ != mov)) - -// test cases +// testcases +//----------- // movie ID "912" -> Casablanca (1942) // "858" -> Godfather // "260" -> Star Wars: Episode IV - A New Hope (1977) @@ -117,40 +199,61 @@ // 52 a good rating to movies 260, 318, 593. + // (5) Implement a suggestions function which takes a rating -// map and a movie_name as arguments. It calculates all the recommended -// movies sorted according to the most frequently suggested movie(s) first. +// map and a movie_name as arguments. It calculates all the recommended +// movies sorted according to the most frequently suggested movie(s) first. + def suggestions(recs: Map[String, List[String]], + mov_name: String) : List[String] = { + val flat = favourites(recs, mov_name).flatten.groupMapReduce(identity)(_ => 1)(_ + _) + val sorted = flat.toList.sortWith(_._2 > _._2).map(_._1) + sorted +} + + +def mapValues[S, T, R](m: Map[S, T], f: T => R) = + m.map { case (x, y) => (x, f(y)) } + +def suggestions2(recs: Map[String, List[String]], mov_name: String) : List[String] = { val favs = favourites(recs, mov_name).flatten - val favs_counted = favs.groupBy(identity).view.mapValues(_.size).toList + val favs_counted = mapValues(favs.groupBy(identity), (v:List[String]) => v.size).toList val favs_sorted = favs_counted.sortBy(_._2).reverse favs_sorted.map(_._1) } -// test cases +// testcases +//----------- //suggestions(ratings_map, "912") //suggestions(ratings_map, "912").length // => 4110 suggestions with List(858, 260, 318, 593, ...) // being the most frequently suggested movies -// (6) Implement recommendations functions which generates at most -// *two* of the most frequently suggested movies. It Returns the -// actual movie names, not the movieIDs. + + +// (6) Implement a recommendations function which generates at most +// *two* of the most frequently suggested movies. It ReTurns the +// actual movie names, not the movieIDs. + def recommendations(recs: Map[String, List[String]], - movs: Map[String, String], - mov_name: String) : List[String] = - suggestions(recs, mov_name).take(2).map(movs.get(_).get) + movs: Map[String, String], + mov_name: String) : List[String] = { + val sugg = suggestions(recs, mov_name) + val movies = (for (i <- 0 until 2 if (i < sugg.length)) yield movs(sugg(i))).toList + movies +} + // testcases - +//----------- // recommendations(ratings_map, movies_map, "912") // => List(Godfather, Star Wars: Episode IV - A NewHope (1977)) -// recommendations(ratings_map, movies_map, "260") +//recommendations(ratings_map, movies_map, "260") // => List(Star Wars: Episode V - The Empire Strikes Back (1980), // Star Wars: Episode VI - Return of the Jedi (1983)) @@ -166,51 +269,34 @@ // recommendations(ratings_map, movies_map, "4") // => Nil (there are three ratings for this movie in ratings.csv but they are not positive) + + // (7) Calculate the recommendations for all movies according to // what the recommendations function in (6) produces (this // can take a few seconds). Put all recommendations into a list // (of strings) and count how often the strings occur in // this list. This produces a list of string-int pairs, // where the first component is the movie name and the second -// is the number of how many times they were recommended. +// is the number of how many times the movie was recommended. // Sort all the pairs according to the number // of times they were recommended (most recommended movie name // first). -def occurrences(xs: List[String]): List[(String, Int)] = - for (x <- xs.distinct) yield (x, xs.count(_ == x)) - def most_recommended(recs: Map[String, List[String]], movs: Map[String, String]) : List[(String, Int)] = { - val all = (for (name <- movs.toList.map(_._1)) yield { - recommendations(recs, movs, name) - }).flatten - val occs = occurrences(all) - occs.sortBy(_._2).reverse + val movies = (((for((k,v) <- movs) yield recommendations(recs, movs, k)).toList).flatten).groupMapReduce(identity)(_ => 1)(_ + _) + val sorted = movies.toList.sortWith(_._2 > _._2) + sorted } - +// testcase +// //most_recommended(ratings_map, movies_map).take(3) // => // List((Matrix,698), // (Star Wars: Episode IV - A New Hope (1977),402), // (Jerry Maguire (1996),382)) -} - -//val ratings_url = """https://nms.kcl.ac.uk/christian.urban/ratings.csv""" -//val movies_url = """https://nms.kcl.ac.uk/christian.urban/movies.csv""" - -/* -val ratings = get_csv_url(ratings_url) -val movies = get_csv_url(movies_url) - -val good_ratings = process_ratings(ratings) -val movie_names = process_movies(movies) - -val ratings_map = groupById(good_ratings, Map()) -val movies_map = movie_names.toMap -println(most_recommended(ratings_map, movies_map).take(3)) -*/ +} diff -r c02929f2647c -r 6e1237691307 main_testing2/danube_test.sh --- a/main_testing2/danube_test.sh Mon Dec 07 01:25:41 2020 +0000 +++ b/main_testing2/danube_test.sh Fri Jan 15 02:40:57 2021 +0000 @@ -21,7 +21,7 @@ # 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 -i "$1" -- "$2" -e "") # 2> /dev/null 1> /dev/null) } # purity test @@ -177,11 +177,13 @@ if [ $tsts -eq 0 ] then - echo -e " val ratings_map2 = for ((k, v) <- ratings_map) yield (k, v.take(2)) " >> $out - echo -e " most_recommended(ratings_map2, movies_map).take(3) == " >> $out - echo -e " List((\"M*A*S*H (a.k.a. MASH) (1970)\",15), " >> $out - echo -e " (\"Star Trek: First Contact (1996)\",10), " >> $out - echo -e " (\"Inception (2010)\",9))) " >> $out + echo -e " val rmap = Map(\"1\" -> List(\"b\", \"a\"), " >> $out + echo -e " \"2\" -> List(\"y\", \"x\"), " >> $out + echo -e " \"3\" -> List(\"c\", \"a\")) " >> $out + echo -e " val nmap = Map(\"a\" -> \"A\", \"b\" -> \"B\", \"c\" -> \"C\", " >> $out + echo -e " \"x\" -> \"X\", \"y\" -> \"Y\") " >> $out + echo -e " most_recommended(rmap, nmap).toSet == " >> $out + echo -e " Set((\"A\",2), (\"B\",1), (\"C\",1), (\"X\",1), (\"Y\",1)) " >> $out if (scala_assert "danube.scala" "danube_test7.scala") then diff -r c02929f2647c -r 6e1237691307 main_testing2/danube_test3.scala --- a/main_testing2/danube_test3.scala Mon Dec 07 01:25:41 2020 +0000 +++ b/main_testing2/danube_test3.scala Fri Jan 15 02:40:57 2021 +0000 @@ -35,22 +35,13 @@ assert(urban_ck(ls5_urban)) +// fourth test !!! /* -import io.Source -import scala.util._ - -def urban_get_csv_file(name: String) : List[String] = { - val csv = Source.fromFile(name) - csv.mkString.split("\n").toList.drop(1) -} + +val ls6_urban = (10 to 500 by 10).map(_.toString).toList +val ls7_urban = ls6_urban zip ls6_urban.tail +val ls8_urban = ls7_urban ::: ls7_urban.reverse -def urban_process_ratings(lines: List[String]) : List[(String, String)] = { - for (cols <- lines.map(_.split(",").toList); - if (cols(2).toFloat >= 4)) yield (cols(0), cols(1)) -} - -val urban_ratings = urban_process_ratings(urban_get_csv_file("ratings.csv").take(1000)) - -assert(urban_ck(urban_ratings)) +assert(urban_ck(ls8_urban)) */ diff -r c02929f2647c -r 6e1237691307 main_testing2/danube_test7.scala --- a/main_testing2/danube_test7.scala Mon Dec 07 01:25:41 2020 +0000 +++ b/main_testing2/danube_test7.scala Fri Jan 15 02:40:57 2021 +0000 @@ -1,48 +1,13 @@ import CW7b._ -// first test - -def urban_groupById(ratings: List[(String, String)], - m: Map[String, List[String]]) : Map[String, List[String]] = ratings match { - case Nil => m - case (id, mov) :: rest => { - val old_ratings = m.getOrElse (id, Nil) - val new_ratings = m + (id -> (mov :: old_ratings)) - urban_groupById(rest, new_ratings) - } -} -//def urban_groupById(ratings: List[(String, String)]) = -// ratings.groupBy(_._1).view.mapValues(_.map(_._2)).toMap - -def urban_get_csv_file(name: String) : List[String] = { - import io.Source - import scala.util._ - val csv = Source.fromFile(name)("ISO-8859-1") - csv.mkString.split("\n").toList.drop(1) -} +val urban_recs = + Map("1" -> List("b", "a"), + "2" -> List("y", "x"), + "3" -> List("a", "c")) -def urban_process_ratings(lines: List[String]) : List[(String, String)] = { - for (cols <- lines.map(_.split(",").toList); - if (cols(2).toInt >= 4)) yield (cols(0), cols(1)) -} - -def urban_process_movies(lines: List[String]) : List[(String, String)] = { - for (cols <- lines.map(_.split(",").toList)) yield (cols(0), cols(1)) -} - +val urban_names = Map("a" -> "A", "b" -> "B", "c" -> "C", "x" -> "X", "y" -> "Y") -val urban_good_ratings = urban_process_ratings(urban_get_csv_file("ratings.csv")) -val urban_movie_names = urban_process_movies(urban_get_csv_file("movies.csv")) - -val urban_movie_names_map = urban_movie_names.toMap -val urban_ratings_map = urban_groupById(urban_good_ratings, Map()) -//val urban_ratings_map = groupById(urban_good_ratings, Map()) +assert(most_recommended(urban_recs, urban_names).toSet == + Set(("A",2), ("B",1), ("C",1), ("X",1), ("Y",1))) -val urban_ratings_map2 = for ((k, v) <- urban_ratings_map) yield (k, v.take(2)) - -assert(most_recommended(urban_ratings_map2, urban_movie_names_map).take(3) == - List(("M*A*S*H (a.k.a. MASH) (1970)",15), - ("Star Trek: First Contact (1996)",10), - ("Inception (2010)",9))) - diff -r c02929f2647c -r 6e1237691307 main_testing5/bf.scala --- a/main_testing5/bf.scala Mon Dec 07 01:25:41 2020 +0000 +++ b/main_testing5/bf.scala Fri Jan 15 02:40:57 2021 +0000 @@ -1,227 +1,248 @@ -// Core Part about an Interpreter for -// the Brainf***++ language -//============================================== - -object CW10a { - - -// 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._ - -def load_bff(name: String) : String = - Try(Source.fromFile(name)("ISO-8859-1").mkString).getOrElse("") - - -// (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 sread(mem: Mem, mp: Int) : Int = - mem.getOrElse(mp, 0) - -def write(mem: Mem, mp: Int, v: Int) : Mem = - mem.updated(mp, v) - - -// (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 ',' => (pc + 1, mp, write(mem, mp, Console.in.read().toByte)) - //case ',' => (pc + 1, mp, write(mem, mp, scala.io.StdIn.readByte())) - 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) - - // new commands - case '@' => (pc + 1, mp, write(mem, sread(mem, mp), sread(mem, mp - 1))) - case '*' => (pc + 1, mp, write(mem, mp, sread(mem, mp) * sread(mem, mp -1))) - case '#' => { println(s"${sread(mem, mp)}"); (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) - - - - - -// 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 - -// 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) - - -// 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 -//----------------------------- - -// hello world program 1 -//run("""++++++++[>++++[>++>+++>+++>+<<<<-]>+>+>->>+[<]<-]>>.>---.+++++++ -// ..+++.>>.<-.<.+++.------.--------.>>+.>++.""") - -// hello world program 2 -//run("""++++++++++[>+++++++>++++++++++>+++>+<<<<-]>++.>+.+++++++..+++.>+ -// +.<<+++++++++++++++.>.+++.------.--------.>+.>.""") - -// hello world program 3 -//run("""+++++++++[>++++++++>+++++++++++>+++++<<<-]>.>++.+++++++.. -// +++.>-.------------.<++++++++.--------.+++.------.--------.>+.""") - - -// draws the Sierpinski triangle -//run(load_bff("sierpinski.bf")) - - -//fibonacci numbers below 100 -//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(""">>[-]>[-]++>[-]++++++><<<>>>>[-]+><>[-]<<[-]>[>+<<+>-]>[<+>-] -// <><[-]>[-]<<<[>>+>+<<<-]>>>[<<<+>>>-][-]><<>>[-]>[-]<<<[>>[-] -// <[>+>+<<-]>[<+>-]+>[[-]<-<->>]<<<-]>>[<<+>>-]<<[[-]>[-]<<[>+> -// +<<-]>>[<<+>>-][-]>[-]<<<<<[>>>>+>+<<<<<-]>>>>>[<<<<<+>>>>>-] -// <<>>[-]>[-]<<<[>>>+<<<-]>>>[<<[<+>>+<-]>[<+>-]>-]<<<>[-]<<[-] -// >[>+<<+>-]>[<+>-]<><[-]>[-]<<<[>>+>+<<<-]>>>-[<<<+>>>-]<[-]>[-] -// <<<[>>+>+<<<-]>>>[<<<+>>>-][-]><<>>[-]>[-]<<<[>>[-]<[>+>+<<-]> -// [<+>-]+>[[-]<-<->>]<<<-]>>[<<+>>-]<<][-]>[-]<<[>+>+<<-]>>[<<+> -// >-]<<<<<[-]>>>>[<<<<+>>>>-]<<<<><>[-]<<[-]>[>+<<+>-]>[<+>-]<> -// <[-]>[-]>[-]<<<[>>+>+<<<-]>>>[<<<+>>>-]<<>>[-]>[-]>[-]>[-]>[-]> -// [-]>[-]>[-]>[-]>[-]<<<<<<<<<<>>++++++++++<<[->+>-[>+>>]>[+[-<+ -// >]>+>>]<<<<<<]>>[-]>>>++++++++++<[->-[>+>>]>[+[-<+>]>+>>]<<<<< -// ]>[-]>>[>++++++[-<++++++++>]<.<<+>+>[-]]<[<[->-<]++++++[->++++ -// ++++<]>.[-]]<<++++++[-<++++++++>]<.[-]<<[-<+>]<<><<<""") - - - -// a Mandelbrot set generator in brainf*** written by Erik Bosman -// (http://esoteric.sange.fi/brainfuck/utils/mandelbrot/) -// -//run(load_bff("mandelbrot.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")) - -} +// Core Part about an Interpreter for +// the Brainf***++ language +//============================================== + + +object CW10a { + + +// 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._ +import java.io.FileNotFoundException +import scala.annotation.tailrec + +def load_bff(name: String) : String = { + try { + val bff = io.Source.fromFile(name).getLines().mkString(" ") + bff + } + catch { + case ex: FileNotFoundException => + val bff = "" + bff + } +} + + + +// (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 sread(mem: Mem, mp: Int) : Int = { + mem.getOrElse(mp,0) +} + +def write(mem: Mem, mp: Int, v: Int) : Mem = { + val newMem = mem + (mp -> v) + newMem +} + + + +// (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. +@tailrec +def jumpRight(prog: String, pc: Int, level: Int) : Int = { + if (pc > prog.length-1) pc + else { + prog(pc) match{ + case '[' => jumpRight(prog, pc+1, level+1) + case ']' => if (level == 0) pc+1 + else jumpRight(prog, pc+1, level-1) + case _ => jumpRight(prog, pc+1, level) + } + } +} +@tailrec +def jumpLeft(prog: String, pc: Int, level: Int) : Int = { + if (pc < 0) pc + else { + prog(pc) match{ + case ']' => jumpLeft(prog, pc-1, level+1) + case '[' => if (level == 0) pc+1 + else jumpLeft(prog, pc-1, level-1) + case _ => jumpLeft(prog, pc-1, level) + } + } +} + + +// 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) + + + +// (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. + +@tailrec +def compute(prog: String, pc: Int, mp: Int, mem: Mem) : Mem = { + if (pc > prog.length-1) mem + else { + prog(pc) match{ + case '>' => compute(prog, pc+1, mp+1, mem) + case '<' => compute(prog, pc+1, mp-1, mem) + case '+' => compute(prog, pc+1, mp,write(mem,mp,sread(mem,mp)+1)) + case '-' => compute(prog, pc+1, mp,write(mem,mp,sread(mem,mp)-1)) + case '.' => print(sread(mem,mp).toChar) + compute(prog, pc+1, mp, mem) + case '[' => if (sread(mem,mp) == 0) compute(prog,jumpRight(prog,pc+1,0),mp,mem) + else compute(prog,pc+1,mp,mem) + case ']' => if (sread(mem,mp) != 0) compute(prog,jumpLeft(prog,pc-1,0),mp,mem) + else compute(prog,pc+1,mp,mem) + case '*' => compute(prog, pc+1,mp, write(mem,mp,sread(mem,mp)*sread(mem,mp-1))) + case '@' => compute(prog,pc+1,mp, write(mem,sread(mem,mp),sread(mem,mp-1))) + case '#' => print(sread(mem,mp)) + compute(prog,pc+1, mp, mem) + case _ => compute(prog,pc+1,mp,mem) + } + } +} + +def run(prog: String, m: Mem = Map()) : Mem = { + compute(prog, 0, 0, m) +} + + + +// 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 + +// 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) + + +// 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 +//----------------------------- + +// hello world program 1 +// run("""++++++++[>++++[>++>+++>+++>+<<<<-]>+>+>->>+[<]<-]>>.>---.+++++++ +// ..+++.>>.<-.<.+++.------.--------.>>+.>++.""") + +// hello world program 2 +// run("""++++++++++[>+++++++>++++++++++>+++>+<<<<-]>++.>+.+++++++..+++.>+ +// +.<<+++++++++++++++.>.+++.------.--------.>+.>.""") + +// hello world program 3 +// run("""+++++++++[>++++++++>+++++++++++>+++++<<<-]>.>++.+++++++.. +// +++.>-.------------.<++++++++.--------.+++.------.--------.>+.""") + + +// draws the Sierpinski triangle +//run(load_bff("sierpinski.bf")) + + +//fibonacci numbers below 100 +// 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(""">>[-]>[-]++>[-]++++++><<<>>>>[-]+><>[-]<<[-]>[>+<<+>-]>[<+>-] +// <><[-]>[-]<<<[>>+>+<<<-]>>>[<<<+>>>-][-]><<>>[-]>[-]<<<[>>[-] +// <[>+>+<<-]>[<+>-]+>[[-]<-<->>]<<<-]>>[<<+>>-]<<[[-]>[-]<<[>+> +// +<<-]>>[<<+>>-][-]>[-]<<<<<[>>>>+>+<<<<<-]>>>>>[<<<<<+>>>>>-] +// <<>>[-]>[-]<<<[>>>+<<<-]>>>[<<[<+>>+<-]>[<+>-]>-]<<<>[-]<<[-] +// >[>+<<+>-]>[<+>-]<><[-]>[-]<<<[>>+>+<<<-]>>>-[<<<+>>>-]<[-]>[-] +// <<<[>>+>+<<<-]>>>[<<<+>>>-][-]><<>>[-]>[-]<<<[>>[-]<[>+>+<<-]> +// [<+>-]+>[[-]<-<->>]<<<-]>>[<<+>>-]<<][-]>[-]<<[>+>+<<-]>>[<<+> +// >-]<<<<<[-]>>>>[<<<<+>>>>-]<<<<><>[-]<<[-]>[>+<<+>-]>[<+>-]<> +// <[-]>[-]>[-]<<<[>>+>+<<<-]>>>[<<<+>>>-]<<>>[-]>[-]>[-]>[-]>[-]> +// [-]>[-]>[-]>[-]>[-]<<<<<<<<<<>>++++++++++<<[->+>-[>+>>]>[+[-<+ +// >]>+>>]<<<<<<]>>[-]>>>++++++++++<[->-[>+>>]>[+[-<+>]>+>>]<<<<< +// ]>[-]>>[>++++++[-<++++++++>]<.<<+>+>[-]]<[<[->-<]++++++[->++++ +// ++++<]>.[-]]<<++++++[-<++++++++>]<.[-]<<[-<+>]<<><<<""") + + + +// a Mandelbrot set generator in brainf*** written by Erik Bosman +// (http://esoteric.sange.fi/brainfuck/utils/mandelbrot/) +// +//run(load_bff("mandelbrot.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")) + +} diff -r c02929f2647c -r 6e1237691307 main_testing5/bf_test.sh --- a/main_testing5/bf_test.sh Mon Dec 07 01:25:41 2020 +0000 +++ b/main_testing5/bf_test.sh Fri Jan 15 02:40:57 2021 +0000 @@ -119,7 +119,7 @@ echo -e " run(\"[-]\", Map(0 -> 100)) == Map(0 -> 0)" >> $out echo -e " run(\"[->+<]\", Map(0 -> 10)) == Map(0 -> 0, 1 -> 10)" >> $out echo -e " run(\"[>>+>>+<<<<-]\", Map(0 -> 42)) == Map(0 -> 0, 2 -> 42, 4 -> 42)" >> $out - echo -e " run(\"++++++++++#>+***#\") == Map(0 -> 10, 1 -> 1000))" >> $out + echo -e " run(\"++++++++++#>+***#\") == Map(0 -> 10, 1 -> 1000)" >> $out echo -e " run(\"+++>+@+@+@+@+@\") == Map(0 -> 3, 1 -> 7, 4 -> 3, 5 -> 3, 6 -> 3, 7 -> 3)" >> $out echo -e " run(\"\"\"+++++[->++++++++++<]>--<+++[->>++++++++++" >> $out diff -r c02929f2647c -r 6e1237691307 main_testing5/bf_test6.scala --- a/main_testing5/bf_test6.scala Mon Dec 07 01:25:41 2020 +0000 +++ b/main_testing5/bf_test6.scala Fri Jan 15 02:40:57 2021 +0000 @@ -3,5 +3,8 @@ //println(optimise(load_bff("benchmark.bf")).length) //println(optimise(load_bff("mandelbrot.bf")).length) -assert(optimise(load_bff("benchmark.bf")).length == 181) -assert(optimise(load_bff("mandelbrot.bf")).length == 11205) +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 == 11205) diff -r c02929f2647c -r 6e1237691307 main_testing5/bfc.scala --- a/main_testing5/bfc.scala Mon Dec 07 01:25:41 2020 +0000 +++ b/main_testing5/bfc.scala Fri Jan 15 02:40:57 2021 +0000 @@ -1,15 +1,71 @@ -// Part 2 about a "Compiler" for the Brainf*** language +// Core Part about a "Compiler" for the Brainf*** language //====================================================== + object CW10b { + // !!! Copy any function you need from file bf.scala !!! // // If you need any auxiliary function, feel free to // implement it, but do not make any changes to the // templates below. +type Mem = Map[Int, Int] +import io.Source +import scala.util._ + +def load_bff(name: String) : String = + Try(scala.io.Source.fromFile(name)("ISO-8859-1").mkString).getOrElse("") + +def sread(mem: Mem, mp: Int) : Int = mem.getOrElse(mp, 0) + +def write(mem: Mem, mp: Int, v: Int) : Mem = mem + (mp -> v) + +def jumpRight(prog: String, pc: Int, level: Int) : Int = { + pc match { + case pc: Int if (pc >= 0 && pc < prog.length) => { + prog(pc) match { + case '[' => jumpRight(prog, pc + 1, level + 1) + case ']' => if (level == 0) pc + 1 else jumpRight(prog, pc + 1, level - 1) + case _ => jumpRight(prog, pc + 1, level) + } + } + case _ => pc + } +} + +def jumpLeft(prog: String, pc: Int, level: Int) : Int = { + pc match { + case pc: Int if (pc >= 0 && pc < prog.length) => { + prog(pc) match { + case '[' => if (level == 0) pc + 1 else jumpLeft(prog, pc - 1, level - 1) + case ']' => jumpLeft(prog, pc - 1, level + 1) + case _ => jumpLeft(prog, pc - 1, level) + } + } + case _ => pc + } +} + +def get_position(prog: String, pc: Int, level: Int) : Int = { + prog(pc) match { + case '[' => jumpRight(prog, pc + 1, level) + case ']' => jumpLeft(prog, pc - 1, level) + case _ => println("Something went horrible wrong, I am sorry"); 0 + } +} + +// 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 @@ -17,89 +73,17 @@ (end - start)/(n * 1.0e9) } -type Mem = Map[Int, Int] -import io.Source -import scala.util._ - -def load_bff(name: String) : String = - Try(Source.fromFile(name)("ISO-8859-1").mkString).getOrElse("") - -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 (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) - } -} - -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 ',' => (pc + 1, mp, write(mem, mp, Console.in.read().toByte)) - 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) - - -// 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. - - +// TASKS +//======= // (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? +// purpose of this map is to record the information about +// pc positions where '[' or a ']' are stored. The information +// is to which pc-position do we need to jump next? // // For example for the program // @@ -118,49 +102,54 @@ // 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. +// 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. +// you should immediately look up the jump address in the jtable. +// for ((char, index) <- str.zipWithIndex if (List('[', ']').contains(char))) yield (index, get_position(str, index, 0)) -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 +def jtable(pg: String) : Map[Int, Int] = { + val table = for ((char, index) <- pg.zipWithIndex if (List('[', ']').contains(char))) yield (index, get_position(pg, index, 0)) + table.toMap +} // 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 (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 ',' => (pc + 1, mp, write(mem, mp, Console.in.read().toByte)) - 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) + pc match { + case pc: Int if (pc >= 0 && pc < pg.length) => { + pg(pc) match { + case '>' => compute2(pg, tb, pc + 1, mp + 1, mem) + case '<' => compute2(pg, tb, pc + 1, mp - 1, mem) + case '+' => compute2(pg, tb, pc + 1, mp, write(mem, mp, sread(mem, mp) + 1)) + case '-' => compute2(pg, tb, pc + 1, mp, write(mem, mp, sread(mem, mp) - 1)) + case '.' => print(sread(mem, mp).toChar); compute2(pg, tb, pc + 1, mp, mem) + case '[' => if (sread(mem, mp) == 0) compute2(pg, tb, tb(pc), mp, mem) else compute2(pg, tb, pc + 1, mp, mem) + case ']' => if (sread(mem, mp) != 0) compute2(pg, tb, tb(pc), mp, mem) else compute2(pg, tb, pc + 1, mp, mem) + case '*' => compute2(pg, tb, pc + 1, mp, write(mem, mp, sread(mem, mp) * sread(mem, mp - 1))) + case '@' => compute2(pg, tb, pc + 1, mp, write(mem, mem(mp), sread(mem, mp - 1))) + case '#' => print(sread(mem, mp)); compute2(pg, tb, pc + 1, mp, mem) + case _ => compute2(pg, tb, pc + 1, mp, mem) + } + } + case _ => mem } - else mem +} + +def run2(pg: String, m: Mem = Map()) = { + compute2(pg, jtable(pg), 0, 0, m) } -def run2(pg: String, m: Mem = Map()) = - compute2(pg, jtable(pg), 0, 0, m) - -//time_needed(1, run2(load_bff("benchmark.bf"))) +// testcases +// time_needed(1, run2(load_bff("./main5/benchmark.bf"))) +// time_needed(1, run2(load_bff("./main5/sierpinski.bf"))) @@ -174,53 +163,61 @@ // 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 +// regular expression """\[-\]""" finds all occurrences of [-] and +// by using the Scala method .replaceAll you can replace it with the // string "0" standing for the new bf-command. +// load_bff("./main5/mandelbrot.bf").replaceAll("""[^<>+‐.\[\]@#*]""", "").replaceAll("""\[-\]""", "0") -def optimise(s: String) : String = - s.replaceAll("""[^<>+-.,\[\]]""","").replaceAll("""\[-\]""", "0") +// "Correct" regex +// s.replaceAll("""[^<>+‐.\[\]@#*]""", "").replaceAll("""\[-\]""", "0") +// s.replaceAll("""[^<>+-.,\[\]]""", "").replaceAll("""\[-\]""", "0") +def optimise(s: String) : String = { + //s.replaceAll("""[^<>+-.\[\]@#*]""","") + // .replaceAll("""\[-\]""", "0") + s.replaceAll("""[^<>+-.\[\]]""", "").replaceAll("""\[-\]""", "0") +} def compute3(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 '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 ',' => (pc + 1, mp, write(mem, mp, Console.in.read().toByte)) - 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) + pc match { + case pc: Int if (pc >= 0 && pc < pg.length) => { + pg(pc) match { + case '>' => compute3(pg, tb, pc + 1, mp + 1, mem) + case '<' => compute3(pg, tb, pc + 1, mp - 1, mem) + case '+' => compute3(pg, tb, pc + 1, mp, write(mem, mp, sread(mem, mp) + 1)) + case '-' => compute3(pg, tb, pc + 1, mp, write(mem, mp, sread(mem, mp) - 1)) + case '.' => print(sread(mem, mp).toChar); compute3(pg, tb, pc + 1, mp, mem) + case '[' => if (sread(mem, mp) == 0) compute3(pg, tb, tb(pc), mp, mem) else compute3(pg, tb, pc + 1, mp, mem) + case ']' => if (sread(mem, mp) != 0) compute3(pg, tb, tb(pc), mp, mem) else compute3(pg, tb, pc + 1, mp, mem) + case '*' => compute3(pg, tb, pc + 1, mp, write(mem, mp, sread(mem, mp) * sread(mem, mp - 1))) + case '@' => compute3(pg, tb, pc + 1, mp, write(mem, mem(mp), sread(mem, mp - 1))) + case '#' => print(sread(mem, mp)); compute3(pg, tb, pc + 1, mp, mem) + case '0' => compute3(pg, tb, pc + 1, mp, write(mem, mp, 0)) + case _ => compute3(pg, tb, pc + 1, mp, mem) + } + } + case _ => mem } - else mem } -def run3(pg: String, m: Mem = Map()) = { - val pg_opt = optimise(pg) - compute3(pg_opt, jtable(pg_opt), 0, 0, m) +def run3(pg: String, m: Mem = Map()) = { + val optimised = optimise(pg) + compute3(optimised, jtable(optimised), 0, 0, m) } // testcases - -//optimise(load_bff("benchmark.bf")) // should have inserted 0's -//optimise(load_bff("benchmark.bf")).length // => 181 -//optimise(load_bff("mandelbrot.bf")).length // => 11203 - -//time_needed(1, run3(load_bff("benchmark.bf"))) +// +// optimise(load_bff("./main5/benchmark.bf")) // should have inserted 0's +// optimise(load_bff("./main5/mandelbrot.bf")).length // => 11205 +// +// time_needed(1, run3(load_bff("./main5/benchmark.bf"))) +// time_needed(1, run3(load_bff("./main5/mandelbrot.bf"))) // (7) Write a function combine which replaces sequences -// of repated increment and decrement commands by appropriate +// of repeated increment and decrement commands by appropriate // two-character commands. For example for sequences of + // // orig bf-cmds | replacement @@ -240,73 +237,82 @@ // Adapt the compute4 and run4 functions such that they can deal // appropriately with such two-character commands. -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 (',' :: 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) +// val alphabet = "АБВГДЕЁЖЗИЙКЛМНОПРСТУФХЦЧШЩЪЫЬЭЮЯ" +val alphabet = "ABCDEFGHIJKLMNOPQRSTUVWXYZ" + +// Try any alphabet, it will work as long as the character is recognised and the characters are unique + +def get_number_from_character(char: Char) : Int = { + alphabet.indexOf(char) + 1 +} + +def get_character_from_number(int: Int) : Char = { + alphabet(int - 1) +} + +@annotation.tailrec +def split_by_repetition(string : String, list : List[String] = Nil) : List[String] = { + if(string.size == 0) list.reverse + else { + val (left_substring, right_substring) = string.span(_ == string(0)) + split_by_repetition(right_substring, left_substring :: list) + } } -def spl(s: String) = splice(s.toList, Nil).reverse +def combine(s: String) : String = { + val split_strings = split_by_repetition(s) + val lists = for (string <- split_strings) yield { + if (List("+"(0), "-"(0), "<"(0), ">"(0)).contains(string.head)) { + val long_repeat = s"${string.head}${alphabet.last}" * (string.size / alphabet.length) + val short_repeat = if ((string.size % alphabet.length) != 0) s"${string.head}${get_character_from_number(string.size % alphabet.length)}" else "" + long_repeat + short_repeat + } else string + } + lists.mkString("") +} -//spl(load_bff("benchmark.bf")) +// testcase +// combine(load_bff("./main5/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 +def compute4(pg: String, tb: Map[Int, Int], pc: Int, mp: Int, mem: Mem) : Mem = { + pc match { + case pc: Int if (pc >= 0 && pc < pg.length) => { + pg(pc) match { + case '>' => val number = get_number_from_character(pg(pc + 1)); compute4(pg, tb, pc + 2, mp + number, mem) + case '<' => val number = get_number_from_character(pg(pc + 1)); compute4(pg, tb, pc + 2, mp - number, mem) + case '+' => val number = get_number_from_character(pg(pc + 1)); compute4(pg, tb, pc + 2, mp, write(mem, mp, sread(mem, mp) + number)) + case '-' => val number = get_number_from_character(pg(pc + 1)); compute4(pg, tb, pc + 2, mp, write(mem, mp, sread(mem, mp) - number)) + case '.' => print(sread(mem, mp).toChar); compute4(pg, tb, pc + 1, mp, mem) + case '[' => if (sread(mem, mp) == 0) compute4(pg, tb, tb(pc), mp, mem) else compute4(pg, tb, pc + 1, mp, mem) + case ']' => if (sread(mem, mp) != 0) compute4(pg, tb, tb(pc), mp, mem) else compute4(pg, tb, pc + 1, mp, mem) + case '*' => compute4(pg, tb, pc + 1, mp, write(mem, mp, sread(mem, mp) * sread(mem, mp - 1))) + case '@' => compute4(pg, tb, pc + 1, mp, write(mem, mem(mp), sread(mem, mp - 1))) + case '#' => print(sread(mem, mp)); compute4(pg, tb, pc + 1, mp, mem) + case '0' => compute4(pg, tb, pc + 1, mp, write(mem, mp, 0)) + case _ => compute4(pg, tb, pc + 1, mp, mem) + } + } + case _ => mem + } } -//combine(load_bff("benchmark.bf")) - -def compute4(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 '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 ',' => (pc + 1, mp, write(mem, mp, Console.in.read().toByte)) - 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 processed_prog = combine(optimise(pg)) + compute4(processed_prog, jtable(processed_prog), 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-A] 134 -//combine(optimise(load_bff("mandelbrot.bf"))).length // => 6509 +// combine(optimise(load_bff("./main5/benchmark.bf"))) // => """>A+B[A-A]> $out - echo -e " optimise(load_bff(\"mandelbrot.bf\")).length == 11205" >> $out - + echo -e " optimise(load_bff(\"benchmark.bf\")).length == 181" >> $out + echo -e " optimise(load_bff(\"mandelbrot.bf\")).length == 11205" >> $out if (scala_assert "bfc.scala" "bf_test6.scala") then echo -e " --> success" >> $out diff -r c02929f2647c -r 6e1237691307 marking3/knight1_test.sh --- a/marking3/knight1_test.sh Mon Dec 07 01:25:41 2020 +0000 +++ b/marking3/knight1_test.sh Fri Jan 15 02:40:57 2021 +0000 @@ -20,7 +20,7 @@ function scala_compile { - (ulimit -t 30; JAVA_OPTS="-Xmx1g" scala "$1" 2>> $out 1>> $out) + (ulimit -t 30; JAVA_OPTS="-Xmx1g" scala "$1") # 2>> $out 1>> $out) } # functional tests @@ -140,7 +140,7 @@ echo " 5: 304,0,56,0,304,0,56,0,56,0,56,0,64,0,56,0,56,0,56,0,304,0,56,0,304" | tee -a $out START=$(date +%s) - if (scala_assert_elong "knight1.scala" "knight1_test3a.scala") + if (scala_assert "knight1.scala" "knight1_test3a.scala") then END=$(date +%s) DIFF=$(( $END - $START )) diff -r c02929f2647c -r 6e1237691307 pre_marking3/postfix.scala --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/pre_marking3/postfix.scala Fri Jan 15 02:40:57 2021 +0000 @@ -0,0 +1,103 @@ +// Shunting Yard Algorithm +// by Edsger Dijkstra +// ======================== + +object CW9a { + +type Toks = List[String] + +// the operations in the simple version +val ops = List("+", "-", "*", "/") + +// the precedences of the operators +val precs = Map("+" -> 1, + "-" -> 1, + "*" -> 2, + "/" -> 2) + +// helper function for splitting strings into tokens +def split(s: String) : Toks = s.split(" ").toList + +// (6) Implement below the shunting yard algorithm. The most +// convenient way to this in Scala is to implement a recursive +// function and to heavily use pattern matching. The function syard +// takes some input tokens as first argument. The second and third +// arguments represent the stack and the output of the shunting yard +// algorithm. +// +// In the marking, you can assume the function is called only with +// an empty stack and an empty output list. You can also assume the +// input os only properly formatted (infix) arithmetic expressions +// (all parentheses will be well-nested, the input only contains +// operators and numbers). + +// You can implement any additional helper function you need. I found +// it helpful to implement two auxiliary functions for the pattern matching: +// + +def is_op(op: String) : Boolean = ops.contains(op) + +def prec(op1: String, op2: String) : Boolean = precs(op1) <= precs(op2) + + +def syard(toks: Toks, st: Toks = Nil, out: Toks = Nil) : Toks = (toks, st, out) match { + case (Nil, _, _) => out.reverse ::: st + case (num::in, st, out) if (num.forall(_.isDigit)) => + syard(in, st, num :: out) + case (op1::in, op2::st, out) if (is_op(op1) && is_op(op2) && prec(op1, op2)) => + syard(op1::in, st, op2 :: out) + case (op1::in, st, out) if (is_op(op1)) => syard(in, op1::st, out) + case ("("::in, st, out) => syard(in, "("::st, out) + case (")"::in, op2::st, out) => + if (op2 == "(") syard(in, st, out) else syard(")"::in, st, op2 :: out) + case (in, st, out) => { + println(s"in: ${in} st: ${st} out: ${out.reverse}") + Nil + } +} + + +// test cases +//syard(split("3 + 4 * ( 2 - 1 )")) // 3 4 2 1 - * + +//syard(split("10 + 12 * 33")) // 10 12 33 * + +//syard(split("( 5 + 7 ) * 2")) // 5 7 + 2 * +//syard(split("5 + 7 / 2")) // 5 7 2 / + +//syard(split("5 * 7 / 2")) // 5 7 * 2 / +//syard(split("9 + 24 / ( 7 - 3 )")) // 9 24 7 3 - / + + +//syard(split("3 + 4 + 5")) // 3 4 + 5 + +//syard(split("( ( 3 + 4 ) + 5 )")) // 3 4 + 5 + +//syard(split("( 3 + ( 4 + 5 ) )")) // 3 4 5 + + +//syard(split("( ( ( 3 ) ) + ( ( 4 + ( 5 ) ) ) )")) // 3 4 5 + + + +// (7) Implement a compute function that evaluates an input list +// in postfix notation. This function takes a list of tokens +// and a stack as argumenta. The function should produce the +// result as an integer using the stack. You can assume +// this function will be only called with proper postfix +// expressions. + +def op_comp(s: String, n1: Int, n2: Int) = s match { + case "+" => n2 + n1 + case "-" => n2 - n1 + case "*" => n2 * n1 + case "/" => n2 / n1 +} + +def compute(toks: Toks, st: List[Int] = Nil) : Int = (toks, st) match { + case (Nil, st) => st.head + case (op::in, n1::n2::st) if (is_op(op)) => compute(in, op_comp(op, n1, n2)::st) + case (num::in, st) => compute(in, num.toInt::st) +} + +// test cases +// compute(syard(split("3 + 4 * ( 2 - 1 )"))) // 7 +// compute(syard(split("10 + 12 * 33"))) // 406 +// compute(syard(split("( 5 + 7 ) * 2"))) // 24 +// compute(syard(split("5 + 7 / 2"))) // 8 +// compute(syard(split("5 * 7 / 2"))) // 17 +// compute(syard(split("9 + 24 / ( 7 - 3 )"))) // 15 + +} + + diff -r c02929f2647c -r 6e1237691307 pre_marking3/postfix2.scala --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/pre_marking3/postfix2.scala Fri Jan 15 02:40:57 2021 +0000 @@ -0,0 +1,100 @@ +// Shunting Yard Algorithm +// including Associativity for Operators +// ===================================== + +object CW9b { + +// type of tokens +type Toks = List[String] + +// helper function for splitting strings into tokens +def split(s: String) : Toks = s.split(" ").toList + +// left- and right-associativity +abstract class Assoc +case object LA extends Assoc +case object RA extends Assoc + +// power is right-associative, +// everything else is left-associative +def assoc(s: String) : Assoc = s match { + case "^" => RA + case _ => LA +} + +// the precedences of the operators +val precs = Map("+" -> 1, + "-" -> 1, + "*" -> 2, + "/" -> 2, + "^" -> 4) + +// the operations in the basic version of the algorithm +val ops = List("+", "-", "*", "/", "^") + +// (8) Implement the extended version of the shunting yard algorithm. +// This version should properly account for the fact that the power +// operation is right-associative. Apart from the extension to include +// the power operation, you can make the same assumptions as in +// basic version. + +def is_op(op: String) : Boolean = ops.contains(op) + +def prec(op1: String, op2: String) : Boolean = assoc(op1) match { + case LA => precs(op1) <= precs(op2) + case RA => precs(op1) < precs(op2) +} + +def syard(toks: Toks, st: Toks = Nil, out: Toks = Nil) : Toks = (toks, st, out) match { + case (Nil, _, _) => out.reverse ::: st + case (num::in, st, out) if (num.forall(_.isDigit)) => + syard(in, st, num :: out) + case (op1::in, op2::st, out) if (is_op(op1) && is_op(op2) && prec(op1, op2)) => + syard(op1::in, st, op2 :: out) + case (op1::in, st, out) if (is_op(op1)) => syard(in, op1::st, out) + case ("("::in, st, out) => syard(in, "("::st, out) + case (")"::in, op2::st, out) => + if (op2 == "(") syard(in, st, out) else syard(")"::in, st, op2 :: out) + case (in, st, out) => { + println(s"in: ${in} st: ${st} out: ${out.reverse}") + Nil + } +} + +def op_comp(s: String, n1: Long, n2: Long) = s match { + case "+" => n2 + n1 + case "-" => n2 - n1 + case "*" => n2 * n1 + case "/" => n2 / n1 + case "^" => Math.pow(n2, n1).toLong +} + +def compute(toks: Toks, st: List[Long] = Nil) : Long = (toks, st) match { + case (Nil, st) => st.head + case (op::in, n1::n2::st) if (is_op(op)) => compute(in, op_comp(op, n1, n2)::st) + case (num::in, st) => compute(in, num.toInt::st) +} + + + + +//compute(syard(split("3 + 4 * ( 2 - 1 )"))) // 7 +//compute(syard(split("10 + 12 * 33"))) // 406 +//compute(syard(split("( 5 + 7 ) * 2"))) // 24 +//compute(syard(split("5 + 7 / 2"))) // 8 +//compute(syard(split("5 * 7 / 2"))) // 17 +//compute(syard(split("9 + 24 / ( 7 - 3 )"))) // 15 + +//compute(syard(split("4 ^ 3 ^ 2"))) // 262144 +//compute(syard(split("4 ^ ( 3 ^ 2 )"))) // 262144 +//compute(syard(split("( 4 ^ 3 ) ^ 2"))) // 4096 +//compute(syard(split("( 3 + 1 ) ^ 2 ^ 3"))) // 65536 + +//syard(split("3 + 4 * 8 / ( 5 - 1 ) ^ 2 ^ 3")) // 3 4 8 * 5 1 - 2 3 ^ ^ / + +//compute(syard(split("3 + 4 * 8 / ( 5 - 1 ) ^ 2 ^ 3"))) // 3 + +//compute(syard(split("( 3 + 1 ) ^ 2 ^ 3"))) // 65536 + + + +} diff -r c02929f2647c -r 6e1237691307 pre_marking3/postfix_test.sh --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/pre_marking3/postfix_test.sh Fri Jan 15 02:40:57 2021 +0000 @@ -0,0 +1,200 @@ +#!/bin/zsh +set -euo pipefail + + +out=${1:-output} + +echo -e "" > $out + +echo `date` >> $out +echo -e "Below is the feedback and provisional marks for your submission" >> $out +echo -e "of the Preliminary Part of Part 3 (Scala). Please note all marks are provisional until" >> $out +echo -e "ratified by the assessment board -- this is not an official" >> $out +echo -e "results transcript." >> $out +echo -e "" >> $out + +echo -e "Below is the feedback for your submission docdiff.scala" >> $out +echo -e "" >> $out + + +# marks for CW9 preliminary +marks=$(( 0.0 )) + + +# 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 "postfix.scala runs?" | tee -a $out + +if (scala_compile postfix.scala) +then + echo -e " --> success" | tee -a $out + tsts=$(( 0 )) +else + echo -e " --> SCALA DID NOT RUN postfix.scala\n" | tee -a $out + tsts=$(( 1 )) +fi + + + +# var, return, ListBuffer test +# +if [ $tsts -eq 0 ] + then + echo -e "postfix.scala does not contain VARS, RETURNS etc??" | tee -a $out + + if (scala_vars postfix.scala) + then + echo -e " --> FAIL\n" | tee -a $out + tsts=$(( 1 )) + else + echo -e " --> success" | tee -a $out + tsts=$(( 0 )) + fi +else + tsts=$(( 1 )) +fi + + + +### postfix tests + +if [ $tsts -eq 0 ] +then + echo -e " syard(split(\"3 + 4 * ( 2 - 1 )\")) == List(\"3\", \"4\", \"2\", \"1\", \"-\", \"*\", \"+\")" | tee -a $out + echo -e " syard(split(\"( ( ( 3 ) ) + ( ( 4 + ( 5 ) ) ) )\")) == List(\"3\", \"4\", \"5\", \"+\", \"+\")" | tee -a $out + echo -e " syard(split(\"5 + 7 / 2\")) == List(\"5\", \"7\", \"2\", \"/\", \"+\")" | tee -a $out + echo -e " syard(split(\"5 * 7 / 2\")) == List(\"5\", \"7\", \"*\", \"2\", \"/\")" | tee -a $out + + if (scala_assert "postfix.scala" "postfix_test1.scala") + then + echo -e " --> success" | tee -a $out + marks=$(( marks + 1.0 )) + else + echo -e " --> ONE OF THE TESTS FAILED\n" | tee -a $out + fi +fi + + + +if [ $tsts -eq 0 ] +then + echo -e " compute(syard(split(\"3 + 4 * ( 2 - 1 )\"))) == 7" | tee -a $out + echo -e " compute(syard(split(\"10 + 12 * 33\"))) == 406" | tee -a $out + echo -e " compute(syard(split(\"( 5 + 7 ) * 2\"))) == 24" | tee -a $out + echo -e " compute(syard(split(\"5 + 7 / 2\"))) == 8" | tee -a $out + echo -e " compute(syard(split(\"5 * 7 / 2\"))) == 17" | tee -a $out + echo -e " compute(syard(split(\"9 + 24 / ( 7 - 3 )\"))) == 15" | tee -a $out + + if (scala_assert "postfix.scala" "postfix_test2.scala") + then + echo -e " --> success" | tee -a $out + marks=$(( marks + 1.0 )) + else + echo -e " --> ONE OF THE TESTS FAILED\n" | tee -a $out + fi +fi + + + +### postfix2 tests + +echo -e "Below is the feedback for your submission postfix2.scala" >> $out +echo -e "" >> $out + +# compilation test + +echo -e "postfix2.scala runs?" | tee -a $out + +if (scala_compile postfix2.scala) +then + echo -e " --> success" | tee -a $out + tsts=$(( 0 )) +else + echo -e " --> SCALA DID NOT RUN postfix2.scala\n" | tee -a $out + tsts=$(( 1 )) +fi + + +# var, return, ListBuffer test +# +if [ $tsts -eq 0 ] +then + echo -e "postfix2.scala does not contain VARS, RETURNS etc?" | tee -a $out + + if (scala_vars postfix2.scala) + then + echo -e " --> FAIL\n" | tee -a $out + tsts=$(( 1 )) + else + echo -e " --> success" | tee -a $out + tsts=$(( 0 )) + fi +else + tsts=$(( 1 )) +fi + + + + +if [ $tsts -eq 0 ] +then + echo -e " syard(split(\"3 + 4 * ( 2 - 1 )\")) == List(\"3\", \"4\", \"2\", \"1\", \"-\", \"*\", \"+\")" | tee -a $out + echo -e " syard(split(\"( ( ( 3 ) ) + ( ( 4 + ( 5 ) ) ) )\")) == List(\"3\", \"4\", \"5\", \"+\", \"+\")" | tee -a $out + echo -e " syard(split(\"5 + 7 / 2\")) == List(\"5\", \"7\", \"2\", \"/\", \"+\")" | tee -a $out + echo -e " syard(split(\"5 * 7 / 2\")) == List(\"5\", \"7\", \"*\", \"2\", \"/\")" | tee -a $out + echo -e " syard(split(\"3 + 4 * 8 / ( 5 - 1 ) ^ 2 ^ 3\")) == " | tee -a $out + echo -e " List(\"3\", \"4\", \"8\", \"*\", \"5\", \"1\", \"-\", \"2\", \"3\", \"^\", \"^\", \"/\", \"+\")" | tee -a $out + + if (scala_assert "postfix2.scala" "postfix_test3.scala") + then + echo -e " --> success" | tee -a $out + marks=$(( marks + 0.5 )) + else + echo -e " --> ONE OF THE TESTS FAILED\n" | tee -a $out + fi +fi + +if [ $tsts -eq 0 ] +then + echo -e " compute(syard(split(\"3 + 4 * ( 2 - 1 )\"))) == 7" | tee -a $out + echo -e " compute(syard(split(\"10 + 12 * 33\"))) == 406" | tee -a $out + echo -e " compute(syard(split(\"( 5 + 7 ) * 2\"))) == 24" | tee -a $out + echo -e " compute(syard(split(\"5 + 7 / 2\"))) == 8" | tee -a $out + echo -e " compute(syard(split(\"5 * 7 / 2\"))) == 17" | tee -a $out + echo -e " compute(syard(split(\"9 + 24 / ( 7 - 3 )\"))) == 15" | tee -a $out + echo -e " compute(syard(split(\"4 ^ 3 ^ 2\"))) == 262144" | tee -a $out + echo -e " compute(syard(split(\"4 ^ ( 3 ^ 2 )\"))) == 262144" | tee -a $out + echo -e " compute(syard(split(\"( 4 ^ 3 ) ^ 2\"))) == 4096" | tee -a $out + echo -e " compute(syard(split(\"( 3 + 1 ) ^ 2 ^ 3\"))) == 65536" | tee -a $out + + if (scala_assert "postfix2.scala" "postfix_test10.scala") + then + echo -e " --> success" | tee -a $out + marks=$(( marks + 0.5 )) + else + echo -e " --> ONE OF THE TESTS FAILED\n" | tee -a $out + fi +fi + +## final marks +echo -e "Overall mark for the Preliminary Part 3 (Scala)" | tee -a $out +printf " %0.1f\n" $marks | tee -a $out + diff -r c02929f2647c -r 6e1237691307 pre_marking3/postfix_test1.scala --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/pre_marking3/postfix_test1.scala Fri Jan 15 02:40:57 2021 +0000 @@ -0,0 +1,7 @@ +import CW9a._ + + +assert(syard(split("3 + 4 * ( 2 - 1 )")) == List("3", "4", "2", "1", "-", "*", "+")) +assert(syard(split("( ( ( 3 ) ) + ( ( 4 + ( 5 ) ) ) )")) == List("3", "4", "5", "+", "+")) +assert(syard(split("5 + 7 / 2")) == List("5", "7", "2", "/", "+")) +assert(syard(split("5 * 7 / 2")) == List("5", "7", "*", "2", "/")) diff -r c02929f2647c -r 6e1237691307 pre_marking3/postfix_test2.scala --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/pre_marking3/postfix_test2.scala Fri Jan 15 02:40:57 2021 +0000 @@ -0,0 +1,8 @@ +import CW9a._ + +assert(compute(syard(split("3 + 4 * ( 2 - 1 )"))) == 7) +assert(compute(syard(split("10 + 12 * 33"))) == 406) +assert(compute(syard(split("( 5 + 7 ) * 2"))) == 24) +assert(compute(syard(split("5 + 7 / 2"))) == 8) +assert(compute(syard(split("5 * 7 / 2"))) == 17) +assert(compute(syard(split("9 + 24 / ( 7 - 3 )"))) == 15) diff -r c02929f2647c -r 6e1237691307 pre_marking3/postfix_test3.scala --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/pre_marking3/postfix_test3.scala Fri Jan 15 02:40:57 2021 +0000 @@ -0,0 +1,9 @@ +import CW9b._ + + +assert(syard(split("3 + 4 * ( 2 - 1 )")) == List("3", "4", "2", "1", "-", "*", "+")) +assert(syard(split("( ( ( 3 ) ) + ( ( 4 + ( 5 ) ) ) )")) == List("3", "4", "5", "+", "+")) +assert(syard(split("5 + 7 / 2")) == List("5", "7", "2", "/", "+")) +assert(syard(split("5 * 7 / 2")) == List("5", "7", "*", "2", "/")) +assert(syard(split("3 + 4 * 8 / ( 5 - 1 ) ^ 2 ^ 3")) == List("3", "4", "8", "*", "5", "1", "-", "2", "3", "^", "^", "/", "+")) + diff -r c02929f2647c -r 6e1237691307 pre_marking3/postfix_test4.scala --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/pre_marking3/postfix_test4.scala Fri Jan 15 02:40:57 2021 +0000 @@ -0,0 +1,13 @@ +import CW9b._ + + +assert(compute(syard(split("3 + 4 * ( 2 - 1 )"))) == 7) +assert(compute(syard(split("10 + 12 * 33"))) == 406) +assert(compute(syard(split("( 5 + 7 ) * 2"))) == 24) +assert(compute(syard(split("5 + 7 / 2"))) == 8) +assert(compute(syard(split("5 * 7 / 2"))) == 17) +assert(compute(syard(split("9 + 24 / ( 7 - 3 )"))) == 15) +assert(compute(syard(split("4 ^ 3 ^ 2"))) == 262144) +assert(compute(syard(split("4 ^ ( 3 ^ 2 )"))) == 262144) +assert(compute(syard(split("( 4 ^ 3 ) ^ 2"))) == 4096) +assert(compute(syard(split("( 3 + 1 ) ^ 2 ^ 3"))) == 65536) diff -r c02929f2647c -r 6e1237691307 pre_solution2/docdiff.scala --- a/pre_solution2/docdiff.scala Mon Dec 07 01:25:41 2020 +0000 +++ b/pre_solution2/docdiff.scala Fri Jan 15 02:40:57 2021 +0000 @@ -34,7 +34,7 @@ val occs1 = occurrences(lst1) val occs2 = occurrences(lst2) words.map{ w => occs1.getOrElse(w, 0) * occs2.getOrElse(w, 0) }.sum -} +} //(4) Complete the functions overlap and similarity. The overlap of // two documents is calculated by the formula given in the assignment diff -r c02929f2647c -r 6e1237691307 progs/lecture2.scala --- a/progs/lecture2.scala Mon Dec 07 01:25:41 2020 +0000 +++ b/progs/lecture2.scala Fri Jan 15 02:40:57 2021 +0000 @@ -661,25 +661,3 @@ jumps(List(2,3,1,1,2,4,2,0,1,1)).minBy(_.length) - - - - -/* - * 1 - * / | \ - * / | \ - * / | \ - * 2 3 8 - * / \ / \ / \ - * 4 5 6 7 9 10 - * Preorder: 1,2,4,5,3,6,7,8,9,10 - * InOrder: 4,2,5,1,6,3,7,9,8,10 - * PostOrder: 4,5,2,6,7,3,9,10,8,1 - * - -show inorder, preorder, postorder - - - -*/ diff -r c02929f2647c -r 6e1237691307 progs/lecture4.scala --- a/progs/lecture4.scala Mon Dec 07 01:25:41 2020 +0000 +++ b/progs/lecture4.scala Fri Jan 15 02:40:57 2021 +0000 @@ -249,6 +249,57 @@ // Source.fromFile(name)(encoding) +// Tail recursion +//================ + +@tailrec +def fact(n: BigInt): BigInt = + if (n == 0) 1 else n * fact(n - 1) + + +fact(10) +fact(1000) +fact(100000) + +def factB(n: BigInt): BigInt = + if (n == 0) 1 else n * factB(n - 1) + +def factT(n: BigInt, acc: BigInt): BigInt = + if (n == 0) acc else factT(n - 1, n * acc) + + +factB(1000) + + +factT(10, 1) +println(factT(500000, 1)) + + +// there is a flag for ensuring a function is tail recursive +import scala.annotation.tailrec + +@tailrec +def factT(n: BigInt, acc: BigInt): BigInt = + if (n == 0) acc else factT(n - 1, n * acc) + +factT(100000, 1) + +// for tail-recursive functions the Scala compiler +// generates loop-like code, which does not need +// to allocate stack-space in each recursive +// call; Scala can do this only for tail-recursive +// functions + +// Moral: Whenever a recursive function is resource-critical +// (i.e. works with a large recursion depth), then you need to +// write it in tail-recursive fashion. +// +// Unfortuantely, Scala because of current limitations in +// the JVM is not as clever as other functional languages. It can +// only optimise "self-tail calls". This excludes the cases of +// multiple functions making tail calls to each other. Well, +// nothing is perfect. + @@ -391,66 +442,22 @@ -// Tail recursion -//================ - -@tailrec -def fact(n: BigInt): BigInt = - if (n == 0) 1 else n * fact(n - 1) - - -fact(10) -fact(1000) -fact(100000) - -def factB(n: BigInt): BigInt = - if (n == 0) 1 else n * factB(n - 1) - -def factT(n: BigInt, acc: BigInt): BigInt = - if (n == 0) acc else factT(n - 1, n * acc) - - -factB(1000) - - - - -factT(10, 1) -println(factT(500000, 1)) - - - - - -// there is a flag for ensuring a function is tail recursive +// tail recursive version that searches +// for all Sudoku solutions import scala.annotation.tailrec @tailrec -def factT(n: BigInt, acc: BigInt): BigInt = - if (n == 0) acc else factT(n - 1, n * acc) - -factT(100000, 1) - -// for tail-recursive functions the Scala compiler -// generates loop-like code, which does not need -// to allocate stack-space in each recursive -// call; Scala can do this only for tail-recursive -// functions - -// tail recursive version that searches -// for all Sudoku solutions - -@tailrec -def searchT(games: List[String], sols: List[String]): List[String] = games match { - case Nil => sols - case game::rest => { - if (isDone(game)) searchT(rest, game::sols) - else { - val cs = candidates(game, emptyPosition(game)) - searchT(cs.map(c => update(game, empty(game), c)) ::: rest, sols) - } - } -} +def searchT(games: List[String], sols: List[String]): List[String] = + games match { + case Nil => sols + case game::rest => { + if (isDone(game)) searchT(rest, game::sols) + else { + val cs = candidates(game, emptyPosition(game)) + searchT(cs.map(c => update(game, empty(game), c)) ::: rest, sols) + } + } + } searchT(List(game3), List()).map(pretty) @@ -487,17 +494,6 @@ searchT(List(game3), Nil).map(pretty) search1T(List(game3)).map(pretty) -// Moral: Whenever a recursive function is resource-critical -// (i.e. works with a large recursion depth), then you need to -// write it in tail-recursive fashion. -// -// Unfortuantely, Scala because of current limitations in -// the JVM is not as clever as other functional languages. It can -// only optimise "self-tail calls". This excludes the cases of -// multiple functions making tail calls to each other. Well, -// nothing is perfect. - - diff -r c02929f2647c -r 6e1237691307 progs/lecture5.scala --- a/progs/lecture5.scala Mon Dec 07 01:25:41 2020 +0000 +++ b/progs/lecture5.scala Fri Jan 15 02:40:57 2021 +0000 @@ -3,6 +3,19 @@ + + + + + + + + + + + + + // Laziness with style //===================== @@ -422,6 +435,18 @@ subset(nfa).accepts("aaaaabbbaaa".toList) // false subset(nfa).accepts("ac".toList) // false +import scala.math.pow + + + + + + + + + + + // The End ... Almost Christmas diff -r c02929f2647c -r 6e1237691307 progs/sudoku.scala --- a/progs/sudoku.scala Mon Dec 07 01:25:41 2020 +0000 +++ b/progs/sudoku.scala Fri Jan 15 02:40:57 2021 +0000 @@ -21,8 +21,10 @@ def empty(game: String) = game.indexOf(emptyValue) def isDone(game: String) = empty(game) == -1 + //def emptyPosition(game: String) : Pos = // (empty(game) % maxValue, empty(game) / maxValue) + def emptyPosition(game: String) = { val e = empty(game) (e % maxValue, e / maxValue) @@ -82,8 +84,7 @@ "6.2.5.........3.4..........43...8....1....2........7..5..27...........81...6.....", ".524.........7.1..............8.2...3.....6...9.5.....1.6.3...........897........", "6.2.5.........4.3..........43...8....1....2........7..5..27...........81...6.....", - ".923.........8.1...........1.7.4...........658.........6.5.2...4.....7.....9.....") -/* + ".923.........8.1...........1.7.4...........658.........6.5.2...4.....7.....9.....", "85...24..72......9..4.........1.7..23.5...9...4...........8..7..17..........36.4.", "..53.....8......2..7..1.5..4....53...1..7...6..32...8..6.5....9..4....3......97..", "12..4......5.69.1...9...5.........7.7...52.9..3......2.9.6...5.4..9..8.1..3...9.4", @@ -187,7 +188,7 @@ "3...8.......7....51..............36...2..4....7...........6.13..452...........8..", "....14....3....2...7..........9...3.6.1.............8.2.....1.4....5.6.....7.8...", "4.....8.5.3..........7......2.....6.....8.4......1.......6.3.7.5..2.....1.4......") -*/ + //println("108:\n" ++ pretty(hard_games(108).replaceAll("\\.", " ")) ++ "\n") //println("109:\n" ++ pretty(hard_games(109).replaceAll("\\.", " ")) ++ "\n") diff -r c02929f2647c -r 6e1237691307 slides/slides03.pdf Binary file slides/slides03.pdf has changed diff -r c02929f2647c -r 6e1237691307 slides/slides03.tex --- a/slides/slides03.tex Mon Dec 07 01:25:41 2020 +0000 +++ b/slides/slides03.tex Fri Jan 15 02:40:57 2021 +0000 @@ -369,7 +369,24 @@ \end{frame} +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +\begin{frame}[t] +\frametitle{Preliminary 2 (Scala)} +Raw marks (301 submissions):\bigskip + +\begin{itemize} +\item 3.0\%: \hspace{4mm}236 +\item 2.5\%: \hspace{4mm}5 +\item 2.0\%: \hspace{4mm}7 +\item 1.5\%: \hspace{4mm}13 +\item 1.0\%: \hspace{4mm}1 +\item 0.5\%: \hspace{4mm}2 +\item 0.0\%: \hspace{4mm}37 +\end{itemize} + + +\end{frame} \begin{frame}<1-20> \end{frame}