--- 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/
--- 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
--- 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)] = {
--- 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+M>A-A]<A[[....."""
@@ -306,6 +306,9 @@
//println(time_needed(1, run4(load_bff("mandelbrot.bf"))))
+
+
+
}
/*
--- a/main_templates5/bfc.scala Mon Dec 07 01:25:41 2020 +0000
+++ b/main_templates5/bfc.scala Fri Jan 15 02:40:57 2021 +0000
@@ -95,7 +95,7 @@
// that is write(mem, mp, 0).
//
// The easiest way to modify a string in this way is to use the regular
-// expression """[^<>+-.,\[\]]""", which recognises everything that is
+// expression """[^<>+-,\[\]@#*]""", which recognises everything that is
// not a bf-command and replace it by the empty string. Similarly the
// regular expression """\[-\]""" finds all occurrences of [-] and
// by using the Scala method .replaceAll you can replace it with the
--- 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))
-*/
+}
--- 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
--- 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))
*/
--- 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)))
-
--- 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"))
+
+}
--- 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
--- 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)
--- 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+M>A-A]<A[[....."""
-//combine(optimise(load_bff("benchmark.bf"))).length // => 134
-//combine(optimise(load_bff("mandelbrot.bf"))).length // => 6509
+// combine(optimise(load_bff("./main5/benchmark.bf"))) // => """>A+B[<A+M>A-A]<A[[....."""
-//time_needed(1, run4(load_bff("benchmark.bf")))
-
-//time_needed(1, run(load_bff("sierpinski.bf")))
-//time_needed(1, run4(load_bff("sierpinski.bf")))
-
-//time_needed(1, run4(load_bff("mandelbrot.bf")))
+// testcases (they should now run much faster)
+// time_needed(1, run4(load_bff("./main5/benchmark.bf")))
+// time_needed(1, run4(load_bff("./main5/sierpinski.bf")))
+// time_needed(1, run4(load_bff("./main5/mandelbrot.bf")))
}
--- a/main_testing5/bfc_test.sh Mon Dec 07 01:25:41 2020 +0000
+++ b/main_testing5/bfc_test.sh Fri Jan 15 02:40:57 2021 +0000
@@ -77,9 +77,8 @@
if [ $tsts1 -eq 0 ]
then
- echo -e " optimise(load_bff(\"benchmark.bf\")).length == 181" >> $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
--- 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 ))
--- /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
+
+}
+
+
--- /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
+
+
+
+}
--- /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
+
--- /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", "/"))
--- /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)
--- /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", "^", "^", "/", "+"))
+
--- /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)
--- 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
--- 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
-
-
-
-*/
--- 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.
-
-
--- 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
--- 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")
Binary file slides/slides03.pdf has changed
--- 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}