--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/Attic/alcohol.scala Sat Mar 11 23:22:05 2023 +0000
@@ -0,0 +1,72 @@
+// Part 2 about Alcohol-Consumption Worldwide
+//============================================
+
+object CW6b {
+
+import io.Source
+import scala.util._
+
+def get_csv_page(url: String) : List[String] =
+ Source.fromURL(url)("ISO-8859-1").getLines.toList
+
+def get_csv_file(file: String) : List[String] =
+ Source.fromFile(file)("ISO-8859-1").getLines.toList
+
+
+val url_alcohol =
+ "https://raw.githubusercontent.com/fivethirtyeight/data/master/alcohol-consumption/drinks.csv"
+
+val file_population =
+ "population.csv"
+
+get_csv_page(url_alcohol)
+get_csv_file(file_population)
+
+get_csv_page(url_alcohol).size
+get_csv_file(file_population).size
+
+val alcs = get_csv_page(url_alcohol)
+val pops = get_csv_file(file_population)
+
+
+def process_alcs(lines: List[String]) : List[(String, Double)] =
+ for (l <- lines) yield {
+ val entries = l.split(",").toList
+ (entries(0), entries(4).toDouble)
+ }
+
+def process_pops(lines: List[String]) : Map[String, Long] =
+ (for (l <- lines) yield {
+ val entries = l.split(",").toList
+ (entries(0), entries(1).toLong)
+ }).toMap
+
+
+def sorted_country_consumption() : List[(String, Long)] = {
+ val alcs2 = process_alcs(alcs.drop(1))
+ val pops2 = process_pops(pops.drop(1))
+ val cons_list =
+ for ((cname, cons) <- alcs2;
+ if pops2.isDefinedAt(cname)) yield (cname, (cons * pops2(cname)).toLong)
+ cons_list.sortBy(_._2).reverse
+}
+
+sorted_country_consumption()(9)
+sorted_country_consumption().size
+
+def percentage(n: Int) : (Long, Long, Double) = {
+ val cons_list = sorted_country_consumption()
+ val sum_n = cons_list.take(n).map(_._2).sum
+ val sum_all = cons_list.map(_._2).sum
+ val perc = (sum_n.toDouble / sum_all.toDouble) * 100.0
+ (sum_all, sum_n, perc)
+}
+
+
+percentage(10)
+percentage(164)
+
+assert(percentage(164) == (28771558364L, 28771558364L, 100.0))
+
+}
+
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/Attic/drumb.scala Sat Mar 11 23:22:05 2023 +0000
@@ -0,0 +1,62 @@
+// Advanvced Part 3 about really dumb investing strategy
+//=======================================================
+
+//two test portfolios
+
+val blchip_portfolio = List("GOOG", "AAPL", "MSFT", "IBM", "FB", "YHOO", "AMZN", "BIDU")
+val rstate_portfolio = List("PLD", "PSA", "AMT", "AIV", "AVB", "BXP", "CBG", "CCI",
+ "DLR", "EQIX", "EQR", "ESS", "EXR", "FRT", "GGP", "HCP")
+
+
+// (1) The function below should obtain the first trading price
+// for a stock symbol by using the query
+//
+// http://ichart.yahoo.com/table.csv?s=<<symbol>>&a=0&b=1&c=<<year>>&d=1&e=1&f=<<year>>
+//
+// and extracting the first January Adjusted Close price in a year.
+
+def get_first_price(symbol: String, year: Int): Option[Double] = ...
+
+// Complete the function below that obtains all first prices
+// for the stock symbols from a portfolio for the given
+// range of years
+
+def get_prices(portfolio: List[String], years: Range): List[List[Option[Double]]] = ...
+
+// test case
+//val p = get_prices(List("GOOG", "AAPL"), 2010 to 2012)
+
+
+// (2) The first function below calculates the change factor (delta) between
+// a price in year n and a price in year n+1. The second function calculates
+// all change factors for all prices (from a portfolio).
+
+def get_delta(price_old: Option[Double], price_new: Option[Double]): Option[Double] = ...
+
+def get_deltas(data: List[List[Option[Double]]]): List[List[Option[Double]]] = ...
+
+// test case using the prices calculated above
+//val d = get_deltas(p)
+
+
+// (3) Write a function that given change factors, a starting balance and a year
+// calculates the yearly yield, i.e. new balanace, according to our dump investment
+// strategy. Another function calculates given the same data calculates the
+// compound yield up to a given year. Finally a function combines all
+// calculations by taking a portfolio, a range of years and a start balance
+// as arguments.
+
+def yearly_yield(data: List[List[Option[Double]]], balance: Long, year: Int): Long = ...
+
+//test case
+//yearly_yield(d, 100, 0)
+
+def compound_yield(data: List[List[Option[Double]]], balance: Long, year: Int): Long = ...
+
+def investment(portfolio: List[String], years: Range, start_balance: Long): Long = ...
+
+
+//test cases for the two portfolios given above
+//investment(rstate_portfolio, 1978 to 2016, 100)
+//investment(blchip_portfolio, 1978 to 2016, 100)
+
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/Attic/drumb_sol.scala Sat Mar 11 23:22:05 2023 +0000
@@ -0,0 +1,88 @@
+// Advanvced Part 3 about a really dumb investment strategy
+//==========================================================
+
+object CW6c {
+
+
+//two test portfolios
+
+val blchip_portfolio = List("GOOG", "AAPL", "MSFT", "IBM", "FB", "AMZN", "BIDU")
+val rstate_portfolio = List("PLD", "PSA", "AMT", "AIV", "AVB", "BXP", "CCI",
+ "DLR", "EQIX", "EQR", "ESS", "EXR", "FRT", "GGP", "HCP")
+
+import io.Source
+import scala.util._
+
+def get_january_data(symbol: String, year: Int) : List[String] =
+ Source.fromFile(symbol ++ ".csv")("ISO-8859-1").getLines.toList.filter(_.startsWith(year.toString))
+
+
+def get_first_price(symbol: String, year: Int) : Option[Double] = {
+ val data = Try(Some(get_january_data(symbol, year).head)) getOrElse None
+ data.map(_.split(",").toList(1).toDouble)
+}
+
+get_first_price("GOOG", 1980)
+get_first_price("GOOG", 2010)
+get_first_price("FB", 2014)
+
+
+def get_prices(portfolio: List[String], years: Range): List[List[Option[Double]]] =
+ for (year <- years.toList) yield
+ for (symbol <- portfolio) yield get_first_price(symbol, year)
+
+
+// test case
+val p_fb = get_prices(List("FB"), 2012 to 2014)
+val p = get_prices(List("GOOG", "AAPL"), 2010 to 2012)
+
+val tt = get_prices(List("BIDU"), 2004 to 2008)
+
+
+def get_delta(price_old: Option[Double], price_new: Option[Double]) : Option[Double] = {
+ (price_old, price_new) match {
+ case (Some(x), Some(y)) => Some((y - x) / x)
+ case _ => None
+ }
+}
+
+def get_deltas(data: List[List[Option[Double]]]): List[List[Option[Double]]] =
+ for (i <- (0 until (data.length - 1)).toList) yield
+ for (j <- (0 until (data(0).length)).toList) yield get_delta(data(i)(j), data(i + 1)(j))
+
+
+// test case using the prices calculated above
+val d = get_deltas(p)
+val ttd = get_deltas(tt)
+
+
+def yearly_yield(data: List[List[Option[Double]]], balance: Long, year: Int): Long = {
+ val somes = data(year).flatten
+ val somes_length = somes.length
+ if (somes_length == 0) balance
+ else {
+ val portion: Double = balance.toDouble / somes_length.toDouble
+ balance + (for (x <- somes) yield (x * portion)).sum.toLong
+ }
+}
+
+def compound_yield(data: List[List[Option[Double]]], balance: Long, year: Int): Long = {
+ if (year >= data.length) balance else {
+ val new_balance = yearly_yield(data, balance, year)
+ compound_yield(data, new_balance, year + 1)
+ }
+}
+
+def investment(portfolio: List[String], years: Range, start_balance: Long): Long = {
+ compound_yield(get_deltas(get_prices(portfolio, years)), start_balance, 0)
+}
+
+
+
+//test cases for the two portfolios given above
+
+println("Real data: " + investment(rstate_portfolio, 1978 to 2017, 100))
+println("Blue data: " + investment(blchip_portfolio, 1978 to 2017, 100))
+
+
+}
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/Attic/knight.scala Sat Mar 11 23:22:05 2023 +0000
@@ -0,0 +1,87 @@
+import scala.util._
+
+def print_board(n: Int)(steps: List[(Int, Int)]): Unit = {
+ for (i <- 0 until n) {
+ for (j <- 0 until n) {
+ print(f"${steps.indexOf((i, j))}%3.0f ")
+ }
+ println
+ }
+ //readLine()
+ //System.exit(0)
+ throw new Exception("\n")
+}
+
+def add_pair(x: (Int, Int))(y: (Int, Int)) =
+ (x._1 + y._1, x._2 + y._2)
+
+def is_legal(n: Int)(x: (Int, Int)) =
+ 0 <= x._1 && 0 <= x._2 && x._1 < n && x._2 < n
+
+def moves(n: Int)(x: (Int, Int)): List[(Int, Int)] = {
+ List((1, 2),(2, 1),(2, -1),(1, -2),
+ (-1, -2),(-2, -1),(-2, 1),(-1, 2)).map(add_pair(x)).filter(is_legal(n))
+}
+
+def ordered_moves(n: Int)(steps: List[(Int, Int)])(x : (Int, Int)): List[(Int, Int)] =
+ moves(n)(x).sortBy((x: (Int, Int)) => moves(n)(x).filterNot(steps.contains(_)).length)
+
+moves(8)(1,3)
+ordered_moves(8)(Nil)(1,3)
+ordered_moves(8)(List((2, 4), (2, 6)))(1,3)
+
+// non-circle tour parallel
+def tour(n: Int)(steps: List[(Int, Int)]): Unit = {
+ if (steps.length == n * n)
+ print_board(n)(steps)
+ else
+ for (x <- moves(n)(steps.head); if (!steps.contains(x))) tour(n)(x :: steps)
+}
+
+// non-circle tour
+def ctour(n: Int)(steps: List[(Int, Int)]): Unit = {
+ if (steps.length == n * n && moves(n)(steps.head).contains(steps.last))
+ print_board(n)(steps)
+ else
+ for (x <- moves(n)(steps.head); if (!steps.contains(x))) ctour(n)(x :: steps)
+}
+
+
+def faster_tour(n: Int)(steps: List[(Int, Int)]): Unit = {
+ if (steps.length == n * n && moves(n)(steps.head).contains(steps.last))
+ print_board(n)(steps)
+ else
+ for (x <- ordered_moves(n)(steps)(steps.head); if (!steps.contains(x))) faster_tour(n)(x :: steps)
+}
+
+
+val n1 = 5
+println(s"simple tour: n = $n1")
+
+Try {
+ for (i <- 0 until n1; j <- 0 until n1) {
+ tour(n1)(List((i, j)))
+ }
+}
+
+
+val n2 = 6
+println(s"circle tour: n = $n2")
+
+Try {
+ for (i <- 0 until n2; j <- 0 until n2) {
+ ctour(n2)(List((i, j)))
+ }
+}
+
+
+val n3 = 8
+println(s"fast circle tour: n = $n3")
+
+Try {
+ for (i <- 0 until n3; j <- 0 until n3) {
+ faster_tour(n3)(List((i, j)))
+ }
+}
+
+println("finished")
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/Attic/knight1.scala Sat Mar 11 23:22:05 2023 +0000
@@ -0,0 +1,157 @@
+// Part 1 about finding Knight's tours
+//=====================================
+
+type Pos = (Int, Int) // a position on a chessboard
+type Path = List[Pos] // a path...a list of positions
+
+// for measuring time
+def time_needed[T](code: => T) : T = {
+ val start = System.nanoTime()
+ val result = code
+ val end = System.nanoTime()
+ println(f"Time needed: ${(end - start) / 1.0e9}%3.3f secs.")
+ result
+}
+
+// for printing a board
+def print_board(dim: Int, path: Path): Unit = {
+ println
+ for (i <- 0 until dim) {
+ for (j <- 0 until dim) {
+ print(f"${path.reverse.indexOf((j, dim - i - 1))}%3.0f ")
+ }
+ println
+ }
+}
+
+
+// 1 mark
+
+def is_legal(dim: Int, path: Path, x: Pos): Boolean =
+ 0 <= x._1 && 0 <= x._2 && x._1 < dim && x._2 < dim && !path.contains(x)
+
+assert(is_legal(8, Nil, (3, 4)) == true)
+assert(is_legal(8, List((4, 1), (1, 0)), (4, 1)) == false)
+assert(is_legal(2, Nil, (0, 0)) == true)
+
+
+def add_pair(x: Pos, y: Pos): Pos =
+ (x._1 + y._1, x._2 + y._2)
+
+def moves(x: Pos): List[Pos] =
+ List(( 1, 2),( 2, 1),( 2, -1),( 1, -2),
+ (-1, -2),(-2, -1),(-2, 1),(-1, 2)).map(add_pair(x, _))
+
+// 1 mark
+
+def legal_moves(dim: Int, path: Path, x: Pos): List[Pos] =
+ moves(x).filter(is_legal(dim, path, _))
+
+assert(legal_moves(8, Nil, (2,2)) ==
+ List((3,4), (4,3), (4,1), (3,0), (1,0), (0,1), (0,3), (1,4)))
+assert(legal_moves(8, Nil, (7,7)) == List((6,5), (5,6)))
+assert(legal_moves(8, List((4,1), (1,0)), (2,2)) ==
+ List((3,4), (4,3), (3,0), (0,1), (0,3), (1,4)))
+assert(legal_moves(8, List((6,6)), (7,7)) == List((6,5), (5,6)))
+assert(legal_moves(1, Nil, (0,0)) == List())
+assert(legal_moves(2, Nil, (0,0)) == List())
+assert(legal_moves(3, Nil, (0,0)) == List((1,2), (2,1)))
+
+// 2 marks
+
+def count_tours(dim: Int, path: Path): Int = {
+ if (path.length == dim * dim) 1
+ else
+ (for (x <- legal_moves(dim, path, path.head)) yield count_tours(dim, x::path)).sum
+}
+
+def enum_tours(dim: Int, path: Path): List[Path] = {
+ if (path.length == dim * dim) List(path)
+ else
+ (for (x <- legal_moves(dim, path, path.head)) yield enum_tours(dim, x::path)).flatten
+}
+
+// as far as tasks go
+// test cases for CW
+
+
+
+def count_all_tours(dim: Int) = {
+ for (i <- (0 until dim).toList;
+ j <- (0 until dim).toList) yield count_tours(dim, List((i, j)))
+}
+
+def enum_all_tours(dim: Int): List[Path] = {
+ (for (i <- (0 until dim).toList;
+ j <- (0 until dim).toList) yield enum_tours(dim, List((i, j)))).flatten
+}
+
+
+println("Number of tours starting from (0, 0)")
+
+for (dim <- 1 to 5) {
+ println(s"${dim} x ${dim} " + time_needed(0, count_tours(dim, List((0, 0)))))
+}
+
+println("Number of tours starting from all fields")
+
+for (dim <- 1 to 5) {
+ println(s"${dim} x ${dim} " + time_needed(0, count_all_tours(dim)))
+}
+
+for (dim <- 1 to 5) {
+ val ts = enum_tours(dim, List((0, 0)))
+ println(s"${dim} x ${dim} ")
+ if (ts != Nil) {
+ print_board(dim, ts.head)
+ println(ts.head)
+ }
+}
+
+
+// 1 mark
+
+def first(xs: List[Pos], f: Pos => Option[Path]): Option[Path] = xs match {
+ case Nil => None
+ case x::xs => {
+ val result = f(x)
+ if (result.isDefined) result else first(xs, f)
+ }
+}
+
+// test cases
+def foo(x: (Int, Int)) = if (x._1 > 3) Some(List(x)) else None
+
+first(List((1, 0),(2, 0),(3, 0),(4, 0)), foo)
+first(List((1, 0),(2, 0),(3, 0)), foo)
+
+
+// 1 mark
+
+def first_tour(dim: Int, path: Path): Option[Path] = {
+ if (path.length == dim * dim) Some(path)
+ else
+ first(legal_moves(dim, path, path.head), (x: Pos) => first_tour(dim, x::path))
+}
+
+
+
+/*
+for (dim <- 1 to 8) {
+ val t = first_tour(dim, List((0, 0)))
+ println(s"${dim} x ${dim} " + (if (t == None) "" else { print_board(dim, t.get) ; "" }))
+}
+*/
+
+// 15 secs for 8 x 8
+val ts1 = time_needed(0,first_tour(8, List((0, 0))).get)
+
+// no result for 4 x 4
+val ts2 = time_needed(0, first_tour(4, List((0, 0))))
+
+// 0.3 secs for 6 x 6
+val ts3 = time_needed(0, first_tour(6, List((0, 0))))
+
+// 15 secs for 8 x 8
+time_needed(0, print_board(8, first_tour(8, List((0, 0))).get))
+
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/Attic/knight1_sol.scala Sat Mar 11 23:22:05 2023 +0000
@@ -0,0 +1,107 @@
+// Part 1 about finding and counting Knight's tours
+//==================================================
+
+type Pos = (Int, Int) // a position on a chessboard
+type Path = List[Pos] // a path...a list of positions
+
+def print_board(dim: Int, path: Path): Unit = {
+ println
+ for (i <- 0 until dim) {
+ for (j <- 0 until dim) {
+ print(f"${path.reverse.indexOf((j, dim - i - 1))}%3.0f ")
+ }
+ println
+ }
+}
+
+def add_pair(x: Pos)(y: Pos): Pos =
+ (x._1 + y._1, x._2 + y._2)
+
+def is_legal(dim: Int, path: Path)(x: Pos): Boolean =
+ 0 <= x._1 && 0 <= x._2 && x._1 < dim && x._2 < dim && !path.contains(x)
+
+assert(is_legal(8, Nil)((3,4)) == true)
+assert(is_legal(8, List((4,1), (1,0)))((4,1)) == false)
+assert(is_legal(2, Nil)((0,0)) == true)
+
+def moves(x: Pos): List[Pos] =
+ List(( 1, 2),( 2, 1),( 2, -1),( 1, -2),
+ (-1, -2),(-2, -1),(-2, 1),(-1, 2)).map(add_pair(x))
+
+def legal_moves(dim: Int, path: Path, x: Pos): List[Pos] =
+ moves(x).filter(is_legal(dim, path))
+
+assert(legal_moves(8, Nil, (2,2)) ==
+ List((3,4), (4,3), (4,1), (3,0), (1,0), (0,1), (0,3), (1,4)))
+assert(legal_moves(8, Nil, (7,7)) == List((6,5), (5,6)))
+assert(legal_moves(8, List((4,1), (1,0)), (2,2)) ==
+ List((3,4), (4,3), (3,0), (0,1), (0,3), (1,4)))
+assert(legal_moves(8, List((6,6)), (7,7)) == List((6,5), (5,6)))
+assert(legal_moves(1, Nil, (0,0)) == List())
+assert(legal_moves(2, Nil, (0,0)) == List())
+assert(legal_moves(3, Nil, (0,0)) == List((1,2), (2,1)))
+
+
+def count_tours(dim: Int, path: Path): Int = {
+ if (path.length == dim * dim) 1
+ else
+ (for (x <- legal_moves(dim, path, path.head)) yield count_tours(dim, x::path)).sum
+}
+
+def enum_tours(dim: Int, path: Path): List[Path] = {
+ if (path.length == dim * dim) List(path)
+ else
+ (for (x <- legal_moves(dim, path, path.head)) yield enum_tours(dim, x::path)).flatten
+}
+
+def count_all_tours(dim: Int) = {
+ for (i <- (0 until dim).toList;
+ j <- (0 until dim).toList) yield count_tours(dim, List((i, j)))
+}
+
+def enum_all_tours(dim: Int): List[Path] = {
+ (for (i <- (0 until dim).toList;
+ j <- (0 until dim).toList) yield enum_tours(dim, List((i, j)))).flatten
+}
+
+
+def add_pair_urban(x: Pos)(y: Pos): Pos =
+ (x._1 + y._1, x._2 + y._2)
+
+def is_legal_urban(dim: Int, path: Path)(x: Pos): Boolean =
+ 0 <= x._1 && 0 <= x._2 && x._1 < dim && x._2 < dim && !path.contains(x)
+
+def moves_urban(x: Pos): List[Pos] =
+ List(( 1, 2),( 2, 1),( 2, -1),( 1, -2),
+ (-1, -2),(-2, -1),(-2, 1),(-1, 2)).map(add_pair_urban(x))
+
+def legal_moves_urban(dim: Int, path: Path, x: Pos): List[Pos] =
+ moves_urban(x).filter(is_legal_urban(dim, path))
+
+def correct_urban(dim: Int)(p: Path): Boolean = p match {
+ case Nil => true
+ case x::Nil => true
+ case x::y::p => if (legal_moves_urban(dim, p, y).contains(x)) correct_urban(dim)(y::p) else false
+}
+
+enum_tours(5, List((0, 2))).map(correct_urban(5)).forall(_ == true)
+
+
+for (dim <- 1 to 5) {
+ println(s"${dim} x ${dim} " + count_tours(dim, List((0, 0))))
+}
+
+for (dim <- 1 to 5) {
+ println(s"${dim} x ${dim} " + count_all_tours(dim))
+}
+
+for (dim <- 1 to 5) {
+ val ts = enum_tours(dim, List((0, 0)))
+ println(s"${dim} x ${dim} ")
+ if (ts != Nil) {
+ print_board(dim, ts.head)
+ println(ts.head)
+ }
+}
+
+
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/Attic/knight2.scala Sat Mar 11 23:22:05 2023 +0000
@@ -0,0 +1,81 @@
+// Part 2 about finding a single tour for a board
+//================================================
+
+type Pos = (Int, Int) // a position on a chessboard
+type Path = List[Pos] // a path...a list of positions
+
+
+// for measuring time
+def time_needed[T](n: Int, code: => T) : T = {
+ val start = System.nanoTime()
+ for (i <- 0 until n) code
+ val result = code
+ val end = System.nanoTime()
+ println("Time needed: " + (end - start) / 1.0e9 + " secs.")
+ result
+}
+
+
+def print_board(dim: Int, path: Path): Unit = {
+ println
+ for (i <- 0 until dim) {
+ for (j <- 0 until dim) {
+ print(f"${path.reverse.indexOf((i, j))}%3.0f ")
+ }
+ println
+ }
+}
+
+def add_pair(x: Pos)(y: Pos): Pos =
+ (x._1 + y._1, x._2 + y._2)
+
+def is_legal(dim: Int, path: Path)(x: Pos): Boolean =
+ 0 <= x._1 && 0 <= x._2 && x._1 < dim && x._2 < dim && !path.contains(x)
+
+def moves(x: Pos): List[Pos] =
+ List(( 1, 2),( 2, 1),( 2, -1),( 1, -2),
+ (-1, -2),(-2, -1),(-2, 1),(-1, 2)).map(add_pair(x))
+
+def legal_moves(dim: Int, path: Path, x: Pos): List[Pos] =
+ moves(x).filter(is_legal(dim, path))
+
+
+def first(xs: List[Pos], f: Pos => Option[Path]): Option[Path] = xs match {
+ case Nil => None
+ case x::xs => {
+ val result = f(x)
+ if (result.isDefined) result else first(xs, f)
+ }
+}
+
+first(List((1, 0),(2, 0),(3, 0),(4, 0)), (x => if (x._1 > 3) Some(List(x)) else None))
+first(List((1, 0),(2, 0),(3, 0)), (x => if (x._1 > 3) Some(List(x)) else None))
+
+
+
+def first_tour(dim: Int, path: Path): Option[Path] = {
+ if (path.length == dim * dim) Some(path)
+ else
+ first(legal_moves(dim, path, path.head), (x: Pos) => first_tour(dim, x::path))
+}
+
+/*
+for (dim <- 1 to 8) {
+ val t = first_tour(dim, List((0, 0)))
+ println(s"${dim} x ${dim} " + (if (t == None) "" else { print_board(dim, t.get) ; "" }))
+}
+*/
+
+// 15 secs for 8 x 8
+val ts1 = time_needed(0,first_tour(8, List((0, 0))).get)
+
+// no result for 4 x 4
+val ts2 = time_needed(0, first_tour(4, List((0, 0))))
+
+// 0.3 secs for 6 x 6
+val ts3 = time_needed(0, first_tour(6, List((0, 0))))
+
+// 15 secs for 8 x 8
+time_needed(0, print_board(8, first_tour(8, List((0, 0))).get))
+
+
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/Attic/knight2_sol.scala Sat Mar 11 23:22:05 2023 +0000
@@ -0,0 +1,88 @@
+// Part 2 about finding a single tour for a board
+//================================================
+
+type Pos = (Int, Int) // a position on a chessboard
+type Path = List[Pos] // a path...a list of positions
+
+def print_board(dim: Int, path: Path): Unit = {
+ println
+ for (i <- 0 until dim) {
+ for (j <- 0 until dim) {
+ print(f"${path.reverse.indexOf((i, j))}%3.0f ")
+ }
+ println
+ }
+}
+
+def add_pair(x: Pos)(y: Pos): Pos =
+ (x._1 + y._1, x._2 + y._2)
+
+def is_legal(dim: Int, path: Path)(x: Pos): Boolean =
+ 0 <= x._1 && 0 <= x._2 && x._1 < dim && x._2 < dim && !path.contains(x)
+
+def moves(x: Pos): List[Pos] =
+ List(( 1, 2),( 2, 1),( 2, -1),( 1, -2),
+ (-1, -2),(-2, -1),(-2, 1),(-1, 2)).map(add_pair(x))
+
+def legal_moves(dim: Int, path: Path, x: Pos): List[Pos] =
+ moves(x).filter(is_legal(dim, path))
+
+
+def first(xs: List[Pos], f: Pos => Option[Path]): Option[Path] = xs match {
+ case Nil => None
+ case x::xs => {
+ val result = f(x)
+ if (result.isDefined) result else first(xs, f)
+ }
+}
+
+first(List((1, 0),(2, 0),(3, 0),(4, 0)), (x => if (x._1 > 3) Some(List(x)) else None))
+first(List((1, 0),(2, 0),(3, 0)), (x => if (x._1 > 3) Some(List(x)) else None))
+
+
+
+def first_tour(dim: Int, path: Path): Option[Path] = {
+ if (path.length == dim * dim) Some(path)
+ else
+ first(legal_moves(dim, path, path.head), (x: Pos) => first_tour(dim, x::path))
+}
+
+/*
+for (dim <- 1 to 8) {
+ val t = first_tour(dim, List((0, 0)))
+ println(s"${dim} x ${dim} " + (if (t == None) "" else { print_board(dim, t.get) ; "" }))
+}
+*/
+
+def add_pair_urban(x: Pos)(y: Pos): Pos =
+ (x._1 + y._1, x._2 + y._2)
+
+def is_legal_urban(dim: Int, path: Path)(x: Pos): Boolean =
+ 0 <= x._1 && 0 <= x._2 && x._1 < dim && x._2 < dim && !path.contains(x)
+
+def moves_urban(x: Pos): List[Pos] =
+ List(( 1, 2),( 2, 1),( 2, -1),( 1, -2),
+ (-1, -2),(-2, -1),(-2, 1),(-1, 2)).map(add_pair_urban(x))
+
+def legal_moves_urban(dim: Int, path: Path, x: Pos): List[Pos] =
+ moves_urban(x).filter(is_legal_urban(dim, path))
+
+def correct_urban(dim: Int)(p: Path): Boolean = p match {
+ case Nil => true
+ case x::Nil => true
+ case x::y::p =>
+ if (legal_moves_urban(dim, p, y).contains(x)) correct_urban(dim)(y::p) else false
+}
+
+
+
+
+val ts1 = first_tour(8, List((0, 0))).get
+ assert(correct_urban(8)(ts1) == true)
+
+val ts2 = first_tour(4, List((0, 0)))
+assert(ts2 == None)
+
+print_board(8, first_tour(8, List((0, 0))).get)
+
+
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/Attic/knight3.scala Sat Mar 11 23:22:05 2023 +0000
@@ -0,0 +1,124 @@
+// Part 3 about finding a single tour using the Warnsdorf Rule
+//=============================================================
+
+
+type Pos = (Int, Int)
+type Path = List[Pos]
+
+// for measuring time
+def time_needed[T](n: Int, code: => T) : T = {
+ val start = System.nanoTime()
+ for (i <- 0 until n) code
+ val result = code
+ val end = System.nanoTime()
+ println(f"Time needed: ${(end - start) / 1.0e9}%3.3f secs.")
+ result
+}
+
+def print_board(dim: Int, path: Path): Unit = {
+ println
+ for (i <- 0 until dim) {
+ for (j <- 0 until dim) {
+ print(f"${path.reverse.indexOf((i, j))}%4.0f ")
+ }
+ println
+ }
+}
+
+def add_pair(x: Pos, y: Pos): Pos =
+ (x._1 + y._1, x._2 + y._2)
+
+def is_legal(dim: Int, path: Path, x: Pos): Boolean =
+ 0 <= x._1 && 0 <= x._2 && x._1 < dim && x._2 < dim && !path.contains(x)
+
+def moves(x: Pos): List[Pos] =
+ List(( 1, 2),( 2, 1),( 2, -1),( 1, -2),
+ (-1, -2),(-2, -1),(-2, 1),(-1, 2)).map(add_pair(x, _))
+
+def legal_moves(dim: Int, path: Path, x: Pos): List[Pos] =
+ moves(x).filter(is_legal(dim, path, _))
+
+def ordered_moves(dim: Int, path: Path, x: Pos): List[Pos] =
+ legal_moves(dim, path, x).sortBy((x) => legal_moves(dim, path, x).length)
+
+import scala.annotation.tailrec
+
+@tailrec
+def first(xs: List[Pos], f: Pos => Option[Path]): Option[Path] = xs match {
+ case Nil => None
+ case x::xs => {
+ val result = f(x)
+ if (result.isDefined) result else first(xs, f)
+ }
+}
+
+
+//def first[A, B](xs: List[A], f: A => Option[B]): Option[B] =
+// xs.flatMap(f(_)).headOption
+
+
+def first_closed_tour_heuristics(dim: Int, path: Path): Option[Path] = {
+ if (path.length == dim * dim && moves(path.head).contains(path.last)) Some(path)
+ else
+ first(ordered_moves(dim, path, path.head), (x: Pos) => first_closed_tour_heuristics(dim, x::path))
+}
+
+// heuristic cannot be used to search for closed tours on 7 x 7
+for (dim <- 1 to 6) {
+ val t = time_needed(0, first_closed_tour_heuristics(dim, List((dim / 2, dim / 2))))
+ println(s"${dim} x ${dim} closed: " + (if (t == None) "" else { print_board(dim, t.get) ; "" }))
+}
+
+
+//@tailrec
+/*
+def first_tour_heuristics(dim: Int, path: Path): Option[Path] = {
+
+ @tailrec
+ def aux(dim: Int, path: Path, moves: List[Pos]): Option[Path] =
+ if (path.length == dim * dim) Some(path)
+ else
+ moves match {
+ case Nil => None
+ case x::xs => {
+ val r = first_tour_heuristics(dim, x::path)
+ if (r.isDefined) r else aux(dim, path, xs)
+ }
+ }
+
+ aux(dim, path, ordered_moves(dim, path, path.head))
+}
+*/
+
+@tailrec
+def tour_on_mega_board(dim: Int, paths: List[Path]): Option[Path] = paths match {
+ case Nil => None
+ case (path::rest) =>
+ if (path.length == dim * dim) Some(path)
+ else tour_on_mega_board(dim, ordered_moves(dim, path, path.head).map(_::path) ::: rest)
+}
+
+
+
+/*
+def first_tour_heuristics(dim: Int, path: Path): Option[Path] = {
+ if (path.length == dim * dim) Some(path)
+ else
+ for (p <- ordered_moves(dim, path, path.head))
+ val r = first_tour_heuristics(dim, x::path)
+ //first(ordered_moves(dim, path, path.head), (x: Pos) => first_tour_heuristics(dim, x::path))
+ ordered_moves(dim, path, path.head).view.flatMap((x: Pos) => first_tour_heuristics(dim, x::path)).headOption
+}
+*/
+
+/*
+for (dim <- 1 to 50) {
+ val t = first_tour_heuristics(dim, List((dim / 2, dim / 2)))
+ println(s"${dim} x ${dim}: " + (if (t == None) "" else { print_board(dim, t.get) ; "" }))
+}
+*/
+
+val dim = 70
+println(s"${dim} x ${dim}:")
+print_board(dim, time_needed(0, tour_on_mega_board(dim, List(List((0, 0)))).get))
+
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/Attic/knight3_sol.scala Sat Mar 11 23:22:05 2023 +0000
@@ -0,0 +1,99 @@
+// Part 3 about finding a single tour using the Warnsdorf Rule
+//=============================================================
+
+
+type Pos = (Int, Int)
+type Path = List[Pos]
+
+def print_board(dim: Int, path: Path): Unit = {
+ println
+ for (i <- 0 until dim) {
+ for (j <- 0 until dim) {
+ print(f"${path.reverse.indexOf((i, j))}%3.0f ")
+ }
+ println
+ }
+}
+
+def add_pair(x: Pos)(y: Pos): Pos =
+ (x._1 + y._1, x._2 + y._2)
+
+def is_legal(dim: Int, path: Path)(x: Pos): Boolean =
+ 0 <= x._1 && 0 <= x._2 && x._1 < dim && x._2 < dim && !path.contains(x)
+
+def moves(x: Pos): List[Pos] =
+ List(( 1, 2),( 2, 1),( 2, -1),( 1, -2),
+ (-1, -2),(-2, -1),(-2, 1),(-1, 2)).map(add_pair(x))
+
+def legal_moves(dim: Int, path: Path, x: Pos): List[Pos] =
+ moves(x).filter(is_legal(dim, path))
+
+def ordered_moves(dim: Int, path: Path, x: Pos): List[Pos] =
+ legal_moves(dim, path, x).sortBy((x) => legal_moves(dim, path, x).length)
+
+import scala.annotation.tailrec
+
+/*
+@tailrec
+def first(xs: List[Pos], f: Pos => Option[Path]): Option[Path] = xs match {
+ case Nil => None
+ case x::xs => {
+ val result = f(x)
+ if (result.isDefined) result else first(xs, f)
+ }
+}
+*/
+
+def first[A, B](xs: List[A], f: A => Option[B]): Option[B] =
+ xs.flatMap(f(_)).headOption
+
+
+def first_closed_tour_heuristics(dim: Int, path: Path): Option[Path] = {
+ if (path.length == dim * dim && moves(path.head).contains(path.last)) Some(path)
+ else
+ first(ordered_moves(dim, path, path.head), (x: Pos) => first_closed_tour_heuristics(dim, x::path))
+}
+
+/*
+for (dim <- 1 to 6) {
+ val t = first_closed_tour_heuristics(dim, List((dim / 2, dim / 2)))
+ println(s"${dim} x ${dim} closed: " + (if (t == None) "" else { print_board(dim, t.get) ; "" }))
+}
+*/
+
+//@tailrec
+def first_tour_heuristics(dim: Int, path: Path): Option[Path] = {
+
+ @tailrec
+ def aux(dim: Int, path: Path, moves: List[Position]): Option[Path
+ if (path.length == dim * dim) Some(path)
+ else
+ moves match {
+ case Nil => None
+ case x::xs => {
+ val r = first_tour_heuristics(dim, x::path)
+ if (r.isDefined) Some(r) else aux(dim, path, xs)
+ }
+ aux(dim, path, ordered_moves(dim, path, path.head))
+}
+
+
+/*
+def first_tour_heuristics(dim: Int, path: Path): Option[Path] = {
+ if (path.length == dim * dim) Some(path)
+ else
+ for (p <- ordered_moves(dim, path, path.head))
+ val r = first_tour_heuristics(dim, x::path)
+ //first(ordered_moves(dim, path, path.head), (x: Pos) => first_tour_heuristics(dim, x::path))
+ ordered_moves(dim, path, path.head).view.flatMap((x: Pos) => first_tour_heuristics(dim, x::path)).headOption
+}
+*/
+
+/*
+for (dim <- 1 to 50) {
+ val t = first_tour_heuristics(dim, List((dim / 2, dim / 2)))
+ println(s"${dim} x ${dim}: " + (if (t == None) "" else { print_board(dim, t.get) ; "" }))
+}
+*/
+
+print_board(50, first_tour_heuristics(50, (25,25)::Nil).get)
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/Attic/knight4.scala Sat Mar 11 23:22:05 2023 +0000
@@ -0,0 +1,48 @@
+import scala.util._
+
+def print_board(n: Int)(steps: List[(Int, Int)]): Unit = synchronized {
+ for (i <- 0 until n) {
+ for (j <- 0 until n) {
+ print(f"${steps.indexOf((i, j))}%3.0f ")
+ }
+ println
+ }
+ //readLine()
+ System.exit(0)
+}
+
+def add_pair(x: (Int, Int))(y: (Int, Int)) =
+ (x._1 + y._1, x._2 + y._2)
+
+def is_legal(n: Int)(x: (Int, Int)) =
+ 0 <= x._1 && 0 <= x._2 && x._1 < n && x._2 < n
+
+def moves(n: Int)(x: (Int, Int)): List[(Int, Int)] = {
+ List((1, 2),(2, 1),(2, -1),(1, -2),
+ (-1, -2),(-2, -1),(-2, 1),(-1, 2)).map(add_pair(x)).filter(is_legal(n))
+}
+
+def ordered_moves(n: Int)(steps: List[(Int, Int)])(x : (Int, Int)): List[(Int, Int)] =
+ moves(n)(x).sortBy((x: (Int, Int)) => moves(n)(x).filterNot(steps.contains(_)).length)
+
+moves(8)(1,3)
+ordered_moves(8)(Nil)(1,3)
+ordered_moves(8)(List((2, 4), (2, 6)))(1,3)
+
+// non-circle tour parallel
+def tour(n: Int)(steps: List[(Int, Int)]): Unit = {
+ if (steps.length == n * n && moves(n)(steps.head).contains(steps.last))
+ print_board(n)(steps)
+ else
+ for (x <- ordered_moves(n)(steps)(steps.head).par; if (!steps.contains(x))) tour(n)(x :: steps)
+}
+
+val n = 7
+println(s"circle tour parallel fast: n = $n")
+
+val starts = for (i <- 0 until n; j <- 0 until n) yield (i, j)
+
+starts.par.foreach((x:(Int, Int)) => tour(n)(List(x)))
+
+
+
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/Attic/knight5.scala Sat Mar 11 23:22:05 2023 +0000
@@ -0,0 +1,45 @@
+import scala.util._
+
+def print_board(n: Int)(steps: List[(Int, Int)]): Unit = synchronized {
+ for (i <- 0 until n) {
+ for (j <- 0 until n) {
+ print(f"${steps.indexOf((i, j))}%3.0f ")
+ }
+ println
+ }
+ //readLine()
+ System.exit(0)
+}
+
+def add_pair(x: (Int, Int))(y: (Int, Int)) =
+ (x._1 + y._1, x._2 + y._2)
+
+def is_legal(n: Int)(x: (Int, Int)) =
+ 0 <= x._1 && 0 <= x._2 && x._1 < n && x._2 < n
+
+def moves(n: Int)(x: (Int, Int)): List[(Int, Int)] = {
+ List((1, 2),(2, 1),(2, -1),(1, -2),
+ (-1, -2),(-2, -1),(-2, 1),(-1, 2)).map(add_pair(x)).filter(is_legal(n))
+}
+
+def ordered_moves(n: Int)(steps: List[(Int, Int)])(x : (Int, Int)): List[(Int, Int)] =
+ moves(n)(x).sortBy((x: (Int, Int)) => moves(n)(x).filterNot(steps.contains(_)).length)
+
+moves(8)(1,3)
+ordered_moves(8)(Nil)(1,3)
+ordered_moves(8)(List((2, 4), (2, 6)))(1,3)
+
+// non-circle tour parallel
+def tour(n: Int)(steps: List[(Int, Int)]): Unit = {
+ if (steps.length == n * n) // && moves(n)(steps.head).contains(steps.last))
+ print_board(n)(steps)
+ else
+ for (x <- ordered_moves(n)(steps)(steps.head); if (!steps.contains(x))) tour(n)(x :: steps)
+}
+
+val n = 21
+println(s"circle tour parallel fast: n = $n")
+
+val starts = for (i <- 0 until n; j <- 0 until n) yield (i, j)
+
+starts.par.foreach((x:(Int, Int)) => tour(n)(List(x)))
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/Attic/knight6.scala Sat Mar 11 23:22:05 2023 +0000
@@ -0,0 +1,72 @@
+import scala.util._
+
+type Pos = (Int, Int)
+
+
+def print_board(n: Int)(steps: List[Pos]): Unit = {
+ for (i <- 0 until n) {
+ for (j <- 0 until n) {
+ print(f"${steps.reverse.indexOf((i, j))}%3.0f ")
+ }
+ println
+ }
+}
+
+def add_pair(x: Pos)(y: Pos) =
+ (x._1 + y._1, x._2 + y._2)
+
+def dist(n: Int)(y: Pos) =
+ (n / 2 - y._1).abs + (n / 2 - y._2).abs
+
+def is_legal(n: Int)(x: Pos) =
+ 0 <= x._1 && 0 <= x._2 && x._1 < n && x._2 < n
+
+def moves(n: Int)(x: Pos): List[Pos] = {
+ List(( 1, 2),( 2, 1),( 2, -1),( 1, -2),
+ (-1, -2),(-2, -1),(-2, 1),(-1, 2)).map(add_pair(x)).filter(is_legal(n))
+}
+
+def moves_filtered(n: Int)(steps: List[Pos])(x: Pos): List[Pos] = {
+ moves(n)(x).filterNot(steps.contains(_))
+}
+
+def ordered_moves(n: Int)(steps: List[Pos])(x: Pos): List[Pos] =
+ moves_filtered(n)(steps)(x).sortBy((x: Pos) => (moves_filtered(n)(steps)(x).length, dist(n)(x)))
+
+/*def first[A, B](xs: List[A], f: A => Option[B]): Option[B] = xs match {
+ case Nil => None
+ case x::xs => {
+ val result = f(x)
+ if (result.isDefined) result else first(xs, f)
+ }
+}*/
+
+def first[A, B](xs: List[A], f: A => Option[B]): Option[B] =
+ xs.par.flatMap(f(_)).headOption
+
+// non-circle tours, including distance
+def tour(n: Int)(steps: List[Pos]): Option[List[Pos]] = {
+ if (steps.length == n * n) //&& moves(n)(steps.head).contains(steps.last))
+ Some(steps)
+ else first(ordered_moves(n)(steps)(steps.head), (x: Pos) => tour(n)(x::steps))
+}
+
+//val n = 8
+val n = 6
+println(s"number simple tours: n = $n")
+
+println(print_board(n)((tour(n)(List((0, 0)))).get))
+//println((for (i <- 0 until n; j <- 0 until n) yield tour(n)(List((i, j)))).flatten.distinct.size)
+
+
+
+
+
+/*
+def first[A, B](xs: List[A], f: A => Option[B]): Option[B] =
+ xs.view.flatMap(f(_)).headOption
+*/
+
+/*
+
+*/
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/Attic/population.csv Sat Mar 11 23:22:05 2023 +0000
@@ -0,0 +1,216 @@
+country,population_size
+Afghanistan,32758020
+Albania,2889104
+Algeria,39113313
+American Samoa,55437
+Andorra,79223
+Angola,26920466
+Antigua and Barbuda,98875
+Argentina,42981515
+Armenia,2906220
+Aruba,103795
+Australia,23460694
+Austria,8541575
+Azerbaijan,9535079
+Bahamas,382169
+Bahrain,1336397
+Bangladesh,159405279
+Barbados,283385
+Belarus,9474511
+Belgium,11209057
+Belize,351694
+Benin,10286712
+Bermuda,65139
+Bhutan,776448
+Bolivia,10562159
+Bosnia and Herzegovina,3566002
+Botswana,2168573
+Brazil,204213133
+British Virgin Islands,29588
+Brunei Darussalam,411704
+Bulgaria,7223938
+Burkina Faso,17585977
+Burundi,9891790
+Cabo Verde,526437
+Cambodia,15270790
+Cameroon,22239904
+Canada,35544564
+Cayman Islands,59172
+Central African Republic,4515392
+Chad,13569438
+Channel Islands,162969
+Chile,17613798
+China,1364270000
+Colombia,47791911
+Comoros,759385
+Congo,73722860
+Costa Rica,4757575
+Cote d'Ivoire,22531350
+Croatia,4238389
+Cuba,11439767
+Curacao,155909
+Cyprus,1152309
+Czech Republic,10525347
+Denmark,5643475
+Djibouti,912164
+Dominica,72778
+Dominican Republic,10405844
+Ecuador,15903112
+Egypt,91812566
+El Salvador,6281189
+Equatorial Guinea,1129424
+Estonia,1314545
+Ethiopia,97366774
+Faroe Islands,48842
+Fiji,885806
+Finland,5461512
+France,66331957
+French Polynesia,275484
+Gabon,1875713
+Gambia,1917852
+Georgia,3727000
+Germany,80982500
+Ghana,26962563
+Gibraltar,34038
+Greece,10892413
+Greenland,56295
+Grenada,106360
+Guam,160967
+Guatemala,15923559
+Guinea,11805509
+Guinea-Bissau,1725744
+Guyana,763393
+Haiti,10572466
+Honduras,8809216
+Hong Kong SAR,7241700
+Hungary,9866468
+Iceland,327386
+India,1293859294
+Indonesia,255131116
+Iran,78411092
+Iraq,35006080
+Ireland,4617225
+Isle of Man,82590
+Israel,8215700
+Italy,60789140
+Jamaica,2862087
+Japan,127276000
+Jordan,8809306
+Kazakhstan,17289224
+Kenya,46024250
+Kiribati,110458
+North Korea,25116363
+South Korea,50746659
+Kosovo,1821800
+Kuwait,3782450
+Kyrgyz Republic,5835500
+Lao PDR,6576397
+Latvia,1993782
+Lebanon,5603279
+Lesotho,2145785
+Liberia,4390737
+Libya,6204108
+Liechtenstein,37127
+Lithuania,2932367
+Luxembourg,556319
+Macao SAR,588781
+Macedonia,2077495
+Madagascar,23589801
+Malawi,17068838
+Malaysia,30228017
+Maldives,401000
+Mali,16962846
+Malta,427364
+Marshall Islands,52898
+Mauritania,4063920
+Mauritius,1260934
+Mexico,124221600
+Micronesia,104015
+Moldova,3556397
+Monaco,38132
+Mongolia,2923896
+Montenegro,621810
+Morocco,34318082
+Mozambique,27212382
+Myanmar,51924182
+Namibia,2370992
+Nauru,11853
+Nepal,28323241
+Netherlands,16865008
+New Caledonia,268000
+New Zealand,4509700
+Nicaragua,6013997
+Niger,19148219
+Nigeria,176460502
+Northern Mariana Islands,54468
+Norway,5137232
+Oman,3960925
+Pakistan,185546257
+Palau,21094
+Panama,3903986
+Papua New Guinea,7755785
+Paraguay,6552584
+Peru,30973354
+Philippines,100102249
+Poland,38011735
+Portugal,10401062
+Puerto Rico,3534874
+Qatar,2374419
+Romania,19908979
+Russian Federation,143819666
+Rwanda,11345357
+Samoa,192290
+San Marino,32657
+Sao Tome and Principe,191266
+Saudi Arabia,30776722
+Senegal,14546111
+Serbia,7130576
+Seychelles,91359
+Sierra Leone,7079162
+Singapore,5469724
+Sint Maarten (Dutch part),37685
+Slovak Republic,5418649
+Slovenia,2061980
+Solomon Islands,575504
+Somalia,13513125
+South Africa,54146734
+South Sudan,11530971
+Spain,46480882
+Sri Lanka,20771000
+St. Kitts and Nevis,53739
+St. Lucia,176421
+St. Martin (French part),31530
+St. Vincent and the Grenadines,109357
+Sudan,37737913
+Suriname,547928
+Swaziland,1295097
+Sweden,9696110
+Switzerland,8188649
+Syrian Arab Republic,19203090
+Tajikistan,8362745
+Tanzania,52234869
+Thailand,68416772
+Timor-Leste,1212814
+Togo,7228915
+Tonga,105782
+Trinidad and Tobago,1354493
+Tunisia,11143908
+Turkey,77030628
+Turkmenistan,5466241
+Turks and Caicos Islands,33739
+Tuvalu,10908
+Uganda,38833338
+Ukraine,45271947
+United Arab Emirates,9070867
+United Kingdom,64613160
+United States,318563456
+Uruguay,3419546
+Uzbekistan,30757700
+Vanuatu,258850
+Venezuela,30738378
+Vietnam,90728900
+Virgin Islands (U.S.),104170
+West Bank and Gaza,4294682
+Yemen,26246327
+Zambia,15620974
+Zimbabwe,15411675
--- a/progs/alcohol.scala Sat Mar 11 23:12:49 2023 +0000
+++ /dev/null Thu Jan 01 00:00:00 1970 +0000
@@ -1,72 +0,0 @@
-// Part 2 about Alcohol-Consumption Worldwide
-//============================================
-
-object CW6b {
-
-import io.Source
-import scala.util._
-
-def get_csv_page(url: String) : List[String] =
- Source.fromURL(url)("ISO-8859-1").getLines.toList
-
-def get_csv_file(file: String) : List[String] =
- Source.fromFile(file)("ISO-8859-1").getLines.toList
-
-
-val url_alcohol =
- "https://raw.githubusercontent.com/fivethirtyeight/data/master/alcohol-consumption/drinks.csv"
-
-val file_population =
- "population.csv"
-
-get_csv_page(url_alcohol)
-get_csv_file(file_population)
-
-get_csv_page(url_alcohol).size
-get_csv_file(file_population).size
-
-val alcs = get_csv_page(url_alcohol)
-val pops = get_csv_file(file_population)
-
-
-def process_alcs(lines: List[String]) : List[(String, Double)] =
- for (l <- lines) yield {
- val entries = l.split(",").toList
- (entries(0), entries(4).toDouble)
- }
-
-def process_pops(lines: List[String]) : Map[String, Long] =
- (for (l <- lines) yield {
- val entries = l.split(",").toList
- (entries(0), entries(1).toLong)
- }).toMap
-
-
-def sorted_country_consumption() : List[(String, Long)] = {
- val alcs2 = process_alcs(alcs.drop(1))
- val pops2 = process_pops(pops.drop(1))
- val cons_list =
- for ((cname, cons) <- alcs2;
- if pops2.isDefinedAt(cname)) yield (cname, (cons * pops2(cname)).toLong)
- cons_list.sortBy(_._2).reverse
-}
-
-sorted_country_consumption()(9)
-sorted_country_consumption().size
-
-def percentage(n: Int) : (Long, Long, Double) = {
- val cons_list = sorted_country_consumption()
- val sum_n = cons_list.take(n).map(_._2).sum
- val sum_all = cons_list.map(_._2).sum
- val perc = (sum_n.toDouble / sum_all.toDouble) * 100.0
- (sum_all, sum_n, perc)
-}
-
-
-percentage(10)
-percentage(164)
-
-assert(percentage(164) == (28771558364L, 28771558364L, 100.0))
-
-}
-
--- a/progs/cube.sc Sat Mar 11 23:12:49 2023 +0000
+++ /dev/null Thu Jan 01 00:00:00 1970 +0000
@@ -1,215 +0,0 @@
-
-// for measuring time
-def time_needed[T](i: Int, code: => T) = {
- val start = System.nanoTime()
- for (j <- 1 to i) code
- val end = System.nanoTime()
- (end - start) / (i * 1.0e9)
-}
-
-// for measuring memory usage
-val mb = 1024*1024
-val runtime = Runtime.getRuntime
-
-def memory() = {
- println(s" ** Used Memory: ${(runtime.totalMemory - runtime.freeMemory) / mb}")
- println(s" ** Free Memory: ${runtime.freeMemory / mb}")
- println(s" ** Total Memory: ${runtime.totalMemory / mb}")
- println(s" ** Max Memory: ${runtime.maxMemory / mb}")
-}
-
-
-abstract class Colour
-case object White extends Colour
-case object Yellow extends Colour
-case object Orange extends Colour
-case object Red extends Colour
-case object Green extends Colour
-case object Blue extends Colour
-
-// -------
-// |c11 c12|
-// |c21 c22|
-// -------
-case class Face(c11: Colour, c12: Colour,
- c21: Colour, c22: Colour)
-
-// +--+
-// |f2|
-// +--+ +--+
-// |f5 f1 f6|
-// +--+ +--+
-// |f3|
-// |f4|
-// +--+
-case class Cube(f1: Face, f2: Face, f3: Face,
- f4: Face, f5: Face, f6: Face)
-
-// pretty printing
-def pp_col(c: Colour) : String = c match {
- case White => "W"
- case Yellow => "Y"
- case Orange => "O"
- case Red => "R"
- case Green => "G"
- case Blue => "B"
-}
-
-def pp_face(f: Face) : String =
- s"${pp_col(f.c11)} ${pp_col(f.c12)}\n${pp_col(f.c21)} ${pp_col(f.c22)}"
-
-def pp_cube(c: Cube) : String =
- s"${pp_face(c.f1)}\n${pp_face(c.f2)}\n${pp_face(c.f3)}\n${pp_face(c.f4)}\n${pp_face(c.f5)}\n${pp_face(c.f6)}"
-
-
-val init =
- Cube(Face(White, Green, White, White),
- Face(Blue, Yellow, Orange, Red),
- Face(Red, Blue, Red, Blue),
- Face(White, Yellow, Red, Orange),
- Face(Yellow, Green, Blue, Green),
- Face(Yellow, Green, Orange, Orange))
-
-val solved =
- Cube(Face(Yellow, Yellow, Yellow, Yellow),
- Face(Orange, Orange, Orange, Orange),
- Face(Red, Red, Red, Red),
- Face(White, White, White, White),
- Face(Blue, Blue, Blue, Blue),
- Face(Green, Green, Green, Green))
-
-//println(pp_cube(init))
-
-// actions
-
-
-def up(c: Cube) : Cube =
- Cube(Face(c.f1.c11, c.f3.c12, c.f1.c21, c.f3.c22),
- Face(c.f2.c11, c.f1.c12, c.f2.c21, c.f1.c22),
- Face(c.f3.c11, c.f4.c12, c.f3.c21, c.f4.c22),
- Face(c.f4.c11, c.f2.c12, c.f4.c21, c.f2.c22),
- Face(c.f5.c11, c.f5.c12, c.f5.c21, c.f5.c22),
- Face(c.f6.c21, c.f6.c11, c.f6.c22, c.f6.c12))
-
-def clock(c: Cube) : Cube =
- Cube(Face(c.f1.c21, c.f1.c11, c.f1.c22, c.f1.c12),
- Face(c.f2.c11, c.f2.c12, c.f5.c22, c.f5.c12),
- Face(c.f6.c21, c.f6.c11, c.f3.c21, c.f3.c22),
- Face(c.f4.c11, c.f4.c12, c.f4.c21, c.f4.c22),
- Face(c.f5.c11, c.f3.c11, c.f5.c21, c.f3.c12),
- Face(c.f2.c21, c.f6.c12, c.f2.c22, c.f6.c22))
-
-def right(c: Cube) : Cube =
- Cube(Face(c.f5.c11, c.f5.c12, c.f1.c21, c.f1.c22),
- Face(c.f2.c12, c.f2.c22, c.f2.c11, c.f2.c21),
- Face(c.f3.c11, c.f3.c12, c.f3.c21, c.f3.c22),
- Face(c.f4.c11, c.f4.c12, c.f6.c12, c.f6.c11),
- Face(c.f4.c22, c.f4.c21, c.f5.c21, c.f5.c22),
- Face(c.f1.c11, c.f1.c12, c.f6.c21, c.f6.c22))
-
-
-//println("\n" ++ pp_cube(up(init)))
-//println("\n" ++ pp_cube(clock(init)))
-//println("\n" ++ pp_cube(right(init)))
-
-//println(List(init, up(init), clock(init), right(init)).map(solved))
-
-
-// simple bf-search without solution
-
-def actions(c: Cube) : List[Cube] =
- List(up(c), clock(c), right(c))
-
-def search(cs: List[Cube], d: Int) : Boolean = {
- println(s"Depth: $d Cands: ${cs.length}")
- //memory()
- if (cs.exists(solved == _)) true
- else search(cs.flatMap(actions), d + 1)
-}
-
-//println("List Version")
-//println(search(List(init), 0))
-//println(s"${time_needed(1, search(List(init), 0))} secs")
-
-
-def actionsS(c: Cube) : Set[Cube] =
- Set(up(c), clock(c), right(c))
-
-def searchS(cs: Set[Cube], d: Int) : Boolean = {
- println(s"Depth: $d Cands: ${cs.size}")
- memory()
- if (cs.exists(solved == _)) true
- else searchS(cs.flatMap(actionsS), d + 1)
-}
-
-//println("Set Version")
-//println(searchS(Set(init), 0))
-//println(s"${time_needed(1, searchS(Set(init), 0))} secs")
-
-// bf-search generating a list of "actions""
-
-abstract class Action
-case object Up extends Action
-case object Right extends Action
-case object Clock extends Action
-
-type Actions = List[Action]
-
-def actions2(c: Cube, act: Actions) : List[(Cube, Actions)] =
- List((up(c), Up::act),
- (clock(c), Clock::act),
- (right(c), Right::act))
-
-
-def search2(cs: List[(Cube, Actions)], d: Int) : (Cube, Actions) = {
- println(s"Depth: $d Cands: ${cs.length}")
- val res = cs.find(init == _._1)
- if (res.isDefined) res.get
- else search2(cs.flatMap((actions2 _).tupled), d + 1)
-}
-
-//println("List Version with Actions")
-//println(search2(List((solved, Nil)), 0)._2.mkString("\n"))
-//println(s"${time_needed(1, search2(List((init, Nil)), 0))} secs")
-
-// using Maps for recording the moves
-def actionsM(c: Cube, act: Actions) : Map[Cube, Actions] =
- Map(up(c) -> (Up::act),
- clock(c) -> (Clock::act),
- right(c) -> (Right::act))
-
-
-def searchM(cs: Map[Cube, Actions], d: Int) : Actions = {
- println(s"Depth: $d Cands: ${cs.keySet.size}")
- val res = cs.keySet.find(init == _)
- if (res.isDefined) cs(res.get)
- else searchM(cs.flatMap((actionsM _).tupled), d + 1)
-}
-
-println("Map Version with actions")
-println(searchM(Map(solved -> Nil), 0).mkString("\n"))
-println(s"${time_needed(1, searchM(Map(init -> Nil), 0))} secs")
-
-
-
-// bi-directional search
-def bsearch(cs: Map[Cube, Actions],
- bs: Map[Cube, Actions], d: Int) : (Actions, Actions) = {
- println(s"Depth: $d Cands: ${cs.keySet.size}/${bs.keySet.size}")
- val res = cs.keySet intersect bs.keySet
- if (!res.isEmpty) (cs(res.head), bs(res.head))
- else bsearch(cs.flatMap((actions2 _).tupled),
- bs.flatMap((actions2 _).tupled), d + 1)
-}
-
-println("Bidirectional Version with actions")
-println(bsearch(Map(init -> Nil), Map(solved -> Nil), 0))
-println(s"${time_needed(1, bsearch(Map(init -> Nil), Map(solved -> Nil), 0))}")
-
-
-
-
-
-
-// more memory
-// JAVA_OPTS="-Xmx2g"
\ No newline at end of file
--- a/progs/drumb.scala Sat Mar 11 23:12:49 2023 +0000
+++ /dev/null Thu Jan 01 00:00:00 1970 +0000
@@ -1,62 +0,0 @@
-// Advanvced Part 3 about really dumb investing strategy
-//=======================================================
-
-//two test portfolios
-
-val blchip_portfolio = List("GOOG", "AAPL", "MSFT", "IBM", "FB", "YHOO", "AMZN", "BIDU")
-val rstate_portfolio = List("PLD", "PSA", "AMT", "AIV", "AVB", "BXP", "CBG", "CCI",
- "DLR", "EQIX", "EQR", "ESS", "EXR", "FRT", "GGP", "HCP")
-
-
-// (1) The function below should obtain the first trading price
-// for a stock symbol by using the query
-//
-// http://ichart.yahoo.com/table.csv?s=<<symbol>>&a=0&b=1&c=<<year>>&d=1&e=1&f=<<year>>
-//
-// and extracting the first January Adjusted Close price in a year.
-
-def get_first_price(symbol: String, year: Int): Option[Double] = ...
-
-// Complete the function below that obtains all first prices
-// for the stock symbols from a portfolio for the given
-// range of years
-
-def get_prices(portfolio: List[String], years: Range): List[List[Option[Double]]] = ...
-
-// test case
-//val p = get_prices(List("GOOG", "AAPL"), 2010 to 2012)
-
-
-// (2) The first function below calculates the change factor (delta) between
-// a price in year n and a price in year n+1. The second function calculates
-// all change factors for all prices (from a portfolio).
-
-def get_delta(price_old: Option[Double], price_new: Option[Double]): Option[Double] = ...
-
-def get_deltas(data: List[List[Option[Double]]]): List[List[Option[Double]]] = ...
-
-// test case using the prices calculated above
-//val d = get_deltas(p)
-
-
-// (3) Write a function that given change factors, a starting balance and a year
-// calculates the yearly yield, i.e. new balanace, according to our dump investment
-// strategy. Another function calculates given the same data calculates the
-// compound yield up to a given year. Finally a function combines all
-// calculations by taking a portfolio, a range of years and a start balance
-// as arguments.
-
-def yearly_yield(data: List[List[Option[Double]]], balance: Long, year: Int): Long = ...
-
-//test case
-//yearly_yield(d, 100, 0)
-
-def compound_yield(data: List[List[Option[Double]]], balance: Long, year: Int): Long = ...
-
-def investment(portfolio: List[String], years: Range, start_balance: Long): Long = ...
-
-
-//test cases for the two portfolios given above
-//investment(rstate_portfolio, 1978 to 2016, 100)
-//investment(blchip_portfolio, 1978 to 2016, 100)
-
--- a/progs/drumb_sol.scala Sat Mar 11 23:12:49 2023 +0000
+++ /dev/null Thu Jan 01 00:00:00 1970 +0000
@@ -1,88 +0,0 @@
-// Advanvced Part 3 about a really dumb investment strategy
-//==========================================================
-
-object CW6c {
-
-
-//two test portfolios
-
-val blchip_portfolio = List("GOOG", "AAPL", "MSFT", "IBM", "FB", "AMZN", "BIDU")
-val rstate_portfolio = List("PLD", "PSA", "AMT", "AIV", "AVB", "BXP", "CCI",
- "DLR", "EQIX", "EQR", "ESS", "EXR", "FRT", "GGP", "HCP")
-
-import io.Source
-import scala.util._
-
-def get_january_data(symbol: String, year: Int) : List[String] =
- Source.fromFile(symbol ++ ".csv")("ISO-8859-1").getLines.toList.filter(_.startsWith(year.toString))
-
-
-def get_first_price(symbol: String, year: Int) : Option[Double] = {
- val data = Try(Some(get_january_data(symbol, year).head)) getOrElse None
- data.map(_.split(",").toList(1).toDouble)
-}
-
-get_first_price("GOOG", 1980)
-get_first_price("GOOG", 2010)
-get_first_price("FB", 2014)
-
-
-def get_prices(portfolio: List[String], years: Range): List[List[Option[Double]]] =
- for (year <- years.toList) yield
- for (symbol <- portfolio) yield get_first_price(symbol, year)
-
-
-// test case
-val p_fb = get_prices(List("FB"), 2012 to 2014)
-val p = get_prices(List("GOOG", "AAPL"), 2010 to 2012)
-
-val tt = get_prices(List("BIDU"), 2004 to 2008)
-
-
-def get_delta(price_old: Option[Double], price_new: Option[Double]) : Option[Double] = {
- (price_old, price_new) match {
- case (Some(x), Some(y)) => Some((y - x) / x)
- case _ => None
- }
-}
-
-def get_deltas(data: List[List[Option[Double]]]): List[List[Option[Double]]] =
- for (i <- (0 until (data.length - 1)).toList) yield
- for (j <- (0 until (data(0).length)).toList) yield get_delta(data(i)(j), data(i + 1)(j))
-
-
-// test case using the prices calculated above
-val d = get_deltas(p)
-val ttd = get_deltas(tt)
-
-
-def yearly_yield(data: List[List[Option[Double]]], balance: Long, year: Int): Long = {
- val somes = data(year).flatten
- val somes_length = somes.length
- if (somes_length == 0) balance
- else {
- val portion: Double = balance.toDouble / somes_length.toDouble
- balance + (for (x <- somes) yield (x * portion)).sum.toLong
- }
-}
-
-def compound_yield(data: List[List[Option[Double]]], balance: Long, year: Int): Long = {
- if (year >= data.length) balance else {
- val new_balance = yearly_yield(data, balance, year)
- compound_yield(data, new_balance, year + 1)
- }
-}
-
-def investment(portfolio: List[String], years: Range, start_balance: Long): Long = {
- compound_yield(get_deltas(get_prices(portfolio, years)), start_balance, 0)
-}
-
-
-
-//test cases for the two portfolios given above
-
-println("Real data: " + investment(rstate_portfolio, 1978 to 2017, 100))
-println("Blue data: " + investment(blchip_portfolio, 1978 to 2017, 100))
-
-
-}
--- a/progs/knight.scala Sat Mar 11 23:12:49 2023 +0000
+++ /dev/null Thu Jan 01 00:00:00 1970 +0000
@@ -1,87 +0,0 @@
-import scala.util._
-
-def print_board(n: Int)(steps: List[(Int, Int)]): Unit = {
- for (i <- 0 until n) {
- for (j <- 0 until n) {
- print(f"${steps.indexOf((i, j))}%3.0f ")
- }
- println
- }
- //readLine()
- //System.exit(0)
- throw new Exception("\n")
-}
-
-def add_pair(x: (Int, Int))(y: (Int, Int)) =
- (x._1 + y._1, x._2 + y._2)
-
-def is_legal(n: Int)(x: (Int, Int)) =
- 0 <= x._1 && 0 <= x._2 && x._1 < n && x._2 < n
-
-def moves(n: Int)(x: (Int, Int)): List[(Int, Int)] = {
- List((1, 2),(2, 1),(2, -1),(1, -2),
- (-1, -2),(-2, -1),(-2, 1),(-1, 2)).map(add_pair(x)).filter(is_legal(n))
-}
-
-def ordered_moves(n: Int)(steps: List[(Int, Int)])(x : (Int, Int)): List[(Int, Int)] =
- moves(n)(x).sortBy((x: (Int, Int)) => moves(n)(x).filterNot(steps.contains(_)).length)
-
-moves(8)(1,3)
-ordered_moves(8)(Nil)(1,3)
-ordered_moves(8)(List((2, 4), (2, 6)))(1,3)
-
-// non-circle tour parallel
-def tour(n: Int)(steps: List[(Int, Int)]): Unit = {
- if (steps.length == n * n)
- print_board(n)(steps)
- else
- for (x <- moves(n)(steps.head); if (!steps.contains(x))) tour(n)(x :: steps)
-}
-
-// non-circle tour
-def ctour(n: Int)(steps: List[(Int, Int)]): Unit = {
- if (steps.length == n * n && moves(n)(steps.head).contains(steps.last))
- print_board(n)(steps)
- else
- for (x <- moves(n)(steps.head); if (!steps.contains(x))) ctour(n)(x :: steps)
-}
-
-
-def faster_tour(n: Int)(steps: List[(Int, Int)]): Unit = {
- if (steps.length == n * n && moves(n)(steps.head).contains(steps.last))
- print_board(n)(steps)
- else
- for (x <- ordered_moves(n)(steps)(steps.head); if (!steps.contains(x))) faster_tour(n)(x :: steps)
-}
-
-
-val n1 = 5
-println(s"simple tour: n = $n1")
-
-Try {
- for (i <- 0 until n1; j <- 0 until n1) {
- tour(n1)(List((i, j)))
- }
-}
-
-
-val n2 = 6
-println(s"circle tour: n = $n2")
-
-Try {
- for (i <- 0 until n2; j <- 0 until n2) {
- ctour(n2)(List((i, j)))
- }
-}
-
-
-val n3 = 8
-println(s"fast circle tour: n = $n3")
-
-Try {
- for (i <- 0 until n3; j <- 0 until n3) {
- faster_tour(n3)(List((i, j)))
- }
-}
-
-println("finished")
--- a/progs/knight1.scala Sat Mar 11 23:12:49 2023 +0000
+++ /dev/null Thu Jan 01 00:00:00 1970 +0000
@@ -1,157 +0,0 @@
-// Part 1 about finding Knight's tours
-//=====================================
-
-type Pos = (Int, Int) // a position on a chessboard
-type Path = List[Pos] // a path...a list of positions
-
-// for measuring time
-def time_needed[T](code: => T) : T = {
- val start = System.nanoTime()
- val result = code
- val end = System.nanoTime()
- println(f"Time needed: ${(end - start) / 1.0e9}%3.3f secs.")
- result
-}
-
-// for printing a board
-def print_board(dim: Int, path: Path): Unit = {
- println
- for (i <- 0 until dim) {
- for (j <- 0 until dim) {
- print(f"${path.reverse.indexOf((j, dim - i - 1))}%3.0f ")
- }
- println
- }
-}
-
-
-// 1 mark
-
-def is_legal(dim: Int, path: Path, x: Pos): Boolean =
- 0 <= x._1 && 0 <= x._2 && x._1 < dim && x._2 < dim && !path.contains(x)
-
-assert(is_legal(8, Nil, (3, 4)) == true)
-assert(is_legal(8, List((4, 1), (1, 0)), (4, 1)) == false)
-assert(is_legal(2, Nil, (0, 0)) == true)
-
-
-def add_pair(x: Pos, y: Pos): Pos =
- (x._1 + y._1, x._2 + y._2)
-
-def moves(x: Pos): List[Pos] =
- List(( 1, 2),( 2, 1),( 2, -1),( 1, -2),
- (-1, -2),(-2, -1),(-2, 1),(-1, 2)).map(add_pair(x, _))
-
-// 1 mark
-
-def legal_moves(dim: Int, path: Path, x: Pos): List[Pos] =
- moves(x).filter(is_legal(dim, path, _))
-
-assert(legal_moves(8, Nil, (2,2)) ==
- List((3,4), (4,3), (4,1), (3,0), (1,0), (0,1), (0,3), (1,4)))
-assert(legal_moves(8, Nil, (7,7)) == List((6,5), (5,6)))
-assert(legal_moves(8, List((4,1), (1,0)), (2,2)) ==
- List((3,4), (4,3), (3,0), (0,1), (0,3), (1,4)))
-assert(legal_moves(8, List((6,6)), (7,7)) == List((6,5), (5,6)))
-assert(legal_moves(1, Nil, (0,0)) == List())
-assert(legal_moves(2, Nil, (0,0)) == List())
-assert(legal_moves(3, Nil, (0,0)) == List((1,2), (2,1)))
-
-// 2 marks
-
-def count_tours(dim: Int, path: Path): Int = {
- if (path.length == dim * dim) 1
- else
- (for (x <- legal_moves(dim, path, path.head)) yield count_tours(dim, x::path)).sum
-}
-
-def enum_tours(dim: Int, path: Path): List[Path] = {
- if (path.length == dim * dim) List(path)
- else
- (for (x <- legal_moves(dim, path, path.head)) yield enum_tours(dim, x::path)).flatten
-}
-
-// as far as tasks go
-// test cases for CW
-
-
-
-def count_all_tours(dim: Int) = {
- for (i <- (0 until dim).toList;
- j <- (0 until dim).toList) yield count_tours(dim, List((i, j)))
-}
-
-def enum_all_tours(dim: Int): List[Path] = {
- (for (i <- (0 until dim).toList;
- j <- (0 until dim).toList) yield enum_tours(dim, List((i, j)))).flatten
-}
-
-
-println("Number of tours starting from (0, 0)")
-
-for (dim <- 1 to 5) {
- println(s"${dim} x ${dim} " + time_needed(0, count_tours(dim, List((0, 0)))))
-}
-
-println("Number of tours starting from all fields")
-
-for (dim <- 1 to 5) {
- println(s"${dim} x ${dim} " + time_needed(0, count_all_tours(dim)))
-}
-
-for (dim <- 1 to 5) {
- val ts = enum_tours(dim, List((0, 0)))
- println(s"${dim} x ${dim} ")
- if (ts != Nil) {
- print_board(dim, ts.head)
- println(ts.head)
- }
-}
-
-
-// 1 mark
-
-def first(xs: List[Pos], f: Pos => Option[Path]): Option[Path] = xs match {
- case Nil => None
- case x::xs => {
- val result = f(x)
- if (result.isDefined) result else first(xs, f)
- }
-}
-
-// test cases
-def foo(x: (Int, Int)) = if (x._1 > 3) Some(List(x)) else None
-
-first(List((1, 0),(2, 0),(3, 0),(4, 0)), foo)
-first(List((1, 0),(2, 0),(3, 0)), foo)
-
-
-// 1 mark
-
-def first_tour(dim: Int, path: Path): Option[Path] = {
- if (path.length == dim * dim) Some(path)
- else
- first(legal_moves(dim, path, path.head), (x: Pos) => first_tour(dim, x::path))
-}
-
-
-
-/*
-for (dim <- 1 to 8) {
- val t = first_tour(dim, List((0, 0)))
- println(s"${dim} x ${dim} " + (if (t == None) "" else { print_board(dim, t.get) ; "" }))
-}
-*/
-
-// 15 secs for 8 x 8
-val ts1 = time_needed(0,first_tour(8, List((0, 0))).get)
-
-// no result for 4 x 4
-val ts2 = time_needed(0, first_tour(4, List((0, 0))))
-
-// 0.3 secs for 6 x 6
-val ts3 = time_needed(0, first_tour(6, List((0, 0))))
-
-// 15 secs for 8 x 8
-time_needed(0, print_board(8, first_tour(8, List((0, 0))).get))
-
--- a/progs/knight1_sol.scala Sat Mar 11 23:12:49 2023 +0000
+++ /dev/null Thu Jan 01 00:00:00 1970 +0000
@@ -1,107 +0,0 @@
-// Part 1 about finding and counting Knight's tours
-//==================================================
-
-type Pos = (Int, Int) // a position on a chessboard
-type Path = List[Pos] // a path...a list of positions
-
-def print_board(dim: Int, path: Path): Unit = {
- println
- for (i <- 0 until dim) {
- for (j <- 0 until dim) {
- print(f"${path.reverse.indexOf((j, dim - i - 1))}%3.0f ")
- }
- println
- }
-}
-
-def add_pair(x: Pos)(y: Pos): Pos =
- (x._1 + y._1, x._2 + y._2)
-
-def is_legal(dim: Int, path: Path)(x: Pos): Boolean =
- 0 <= x._1 && 0 <= x._2 && x._1 < dim && x._2 < dim && !path.contains(x)
-
-assert(is_legal(8, Nil)((3,4)) == true)
-assert(is_legal(8, List((4,1), (1,0)))((4,1)) == false)
-assert(is_legal(2, Nil)((0,0)) == true)
-
-def moves(x: Pos): List[Pos] =
- List(( 1, 2),( 2, 1),( 2, -1),( 1, -2),
- (-1, -2),(-2, -1),(-2, 1),(-1, 2)).map(add_pair(x))
-
-def legal_moves(dim: Int, path: Path, x: Pos): List[Pos] =
- moves(x).filter(is_legal(dim, path))
-
-assert(legal_moves(8, Nil, (2,2)) ==
- List((3,4), (4,3), (4,1), (3,0), (1,0), (0,1), (0,3), (1,4)))
-assert(legal_moves(8, Nil, (7,7)) == List((6,5), (5,6)))
-assert(legal_moves(8, List((4,1), (1,0)), (2,2)) ==
- List((3,4), (4,3), (3,0), (0,1), (0,3), (1,4)))
-assert(legal_moves(8, List((6,6)), (7,7)) == List((6,5), (5,6)))
-assert(legal_moves(1, Nil, (0,0)) == List())
-assert(legal_moves(2, Nil, (0,0)) == List())
-assert(legal_moves(3, Nil, (0,0)) == List((1,2), (2,1)))
-
-
-def count_tours(dim: Int, path: Path): Int = {
- if (path.length == dim * dim) 1
- else
- (for (x <- legal_moves(dim, path, path.head)) yield count_tours(dim, x::path)).sum
-}
-
-def enum_tours(dim: Int, path: Path): List[Path] = {
- if (path.length == dim * dim) List(path)
- else
- (for (x <- legal_moves(dim, path, path.head)) yield enum_tours(dim, x::path)).flatten
-}
-
-def count_all_tours(dim: Int) = {
- for (i <- (0 until dim).toList;
- j <- (0 until dim).toList) yield count_tours(dim, List((i, j)))
-}
-
-def enum_all_tours(dim: Int): List[Path] = {
- (for (i <- (0 until dim).toList;
- j <- (0 until dim).toList) yield enum_tours(dim, List((i, j)))).flatten
-}
-
-
-def add_pair_urban(x: Pos)(y: Pos): Pos =
- (x._1 + y._1, x._2 + y._2)
-
-def is_legal_urban(dim: Int, path: Path)(x: Pos): Boolean =
- 0 <= x._1 && 0 <= x._2 && x._1 < dim && x._2 < dim && !path.contains(x)
-
-def moves_urban(x: Pos): List[Pos] =
- List(( 1, 2),( 2, 1),( 2, -1),( 1, -2),
- (-1, -2),(-2, -1),(-2, 1),(-1, 2)).map(add_pair_urban(x))
-
-def legal_moves_urban(dim: Int, path: Path, x: Pos): List[Pos] =
- moves_urban(x).filter(is_legal_urban(dim, path))
-
-def correct_urban(dim: Int)(p: Path): Boolean = p match {
- case Nil => true
- case x::Nil => true
- case x::y::p => if (legal_moves_urban(dim, p, y).contains(x)) correct_urban(dim)(y::p) else false
-}
-
-enum_tours(5, List((0, 2))).map(correct_urban(5)).forall(_ == true)
-
-
-for (dim <- 1 to 5) {
- println(s"${dim} x ${dim} " + count_tours(dim, List((0, 0))))
-}
-
-for (dim <- 1 to 5) {
- println(s"${dim} x ${dim} " + count_all_tours(dim))
-}
-
-for (dim <- 1 to 5) {
- val ts = enum_tours(dim, List((0, 0)))
- println(s"${dim} x ${dim} ")
- if (ts != Nil) {
- print_board(dim, ts.head)
- println(ts.head)
- }
-}
-
-
--- a/progs/knight2.scala Sat Mar 11 23:12:49 2023 +0000
+++ /dev/null Thu Jan 01 00:00:00 1970 +0000
@@ -1,81 +0,0 @@
-// Part 2 about finding a single tour for a board
-//================================================
-
-type Pos = (Int, Int) // a position on a chessboard
-type Path = List[Pos] // a path...a list of positions
-
-
-// for measuring time
-def time_needed[T](n: Int, code: => T) : T = {
- val start = System.nanoTime()
- for (i <- 0 until n) code
- val result = code
- val end = System.nanoTime()
- println("Time needed: " + (end - start) / 1.0e9 + " secs.")
- result
-}
-
-
-def print_board(dim: Int, path: Path): Unit = {
- println
- for (i <- 0 until dim) {
- for (j <- 0 until dim) {
- print(f"${path.reverse.indexOf((i, j))}%3.0f ")
- }
- println
- }
-}
-
-def add_pair(x: Pos)(y: Pos): Pos =
- (x._1 + y._1, x._2 + y._2)
-
-def is_legal(dim: Int, path: Path)(x: Pos): Boolean =
- 0 <= x._1 && 0 <= x._2 && x._1 < dim && x._2 < dim && !path.contains(x)
-
-def moves(x: Pos): List[Pos] =
- List(( 1, 2),( 2, 1),( 2, -1),( 1, -2),
- (-1, -2),(-2, -1),(-2, 1),(-1, 2)).map(add_pair(x))
-
-def legal_moves(dim: Int, path: Path, x: Pos): List[Pos] =
- moves(x).filter(is_legal(dim, path))
-
-
-def first(xs: List[Pos], f: Pos => Option[Path]): Option[Path] = xs match {
- case Nil => None
- case x::xs => {
- val result = f(x)
- if (result.isDefined) result else first(xs, f)
- }
-}
-
-first(List((1, 0),(2, 0),(3, 0),(4, 0)), (x => if (x._1 > 3) Some(List(x)) else None))
-first(List((1, 0),(2, 0),(3, 0)), (x => if (x._1 > 3) Some(List(x)) else None))
-
-
-
-def first_tour(dim: Int, path: Path): Option[Path] = {
- if (path.length == dim * dim) Some(path)
- else
- first(legal_moves(dim, path, path.head), (x: Pos) => first_tour(dim, x::path))
-}
-
-/*
-for (dim <- 1 to 8) {
- val t = first_tour(dim, List((0, 0)))
- println(s"${dim} x ${dim} " + (if (t == None) "" else { print_board(dim, t.get) ; "" }))
-}
-*/
-
-// 15 secs for 8 x 8
-val ts1 = time_needed(0,first_tour(8, List((0, 0))).get)
-
-// no result for 4 x 4
-val ts2 = time_needed(0, first_tour(4, List((0, 0))))
-
-// 0.3 secs for 6 x 6
-val ts3 = time_needed(0, first_tour(6, List((0, 0))))
-
-// 15 secs for 8 x 8
-time_needed(0, print_board(8, first_tour(8, List((0, 0))).get))
-
-
--- a/progs/knight2_sol.scala Sat Mar 11 23:12:49 2023 +0000
+++ /dev/null Thu Jan 01 00:00:00 1970 +0000
@@ -1,88 +0,0 @@
-// Part 2 about finding a single tour for a board
-//================================================
-
-type Pos = (Int, Int) // a position on a chessboard
-type Path = List[Pos] // a path...a list of positions
-
-def print_board(dim: Int, path: Path): Unit = {
- println
- for (i <- 0 until dim) {
- for (j <- 0 until dim) {
- print(f"${path.reverse.indexOf((i, j))}%3.0f ")
- }
- println
- }
-}
-
-def add_pair(x: Pos)(y: Pos): Pos =
- (x._1 + y._1, x._2 + y._2)
-
-def is_legal(dim: Int, path: Path)(x: Pos): Boolean =
- 0 <= x._1 && 0 <= x._2 && x._1 < dim && x._2 < dim && !path.contains(x)
-
-def moves(x: Pos): List[Pos] =
- List(( 1, 2),( 2, 1),( 2, -1),( 1, -2),
- (-1, -2),(-2, -1),(-2, 1),(-1, 2)).map(add_pair(x))
-
-def legal_moves(dim: Int, path: Path, x: Pos): List[Pos] =
- moves(x).filter(is_legal(dim, path))
-
-
-def first(xs: List[Pos], f: Pos => Option[Path]): Option[Path] = xs match {
- case Nil => None
- case x::xs => {
- val result = f(x)
- if (result.isDefined) result else first(xs, f)
- }
-}
-
-first(List((1, 0),(2, 0),(3, 0),(4, 0)), (x => if (x._1 > 3) Some(List(x)) else None))
-first(List((1, 0),(2, 0),(3, 0)), (x => if (x._1 > 3) Some(List(x)) else None))
-
-
-
-def first_tour(dim: Int, path: Path): Option[Path] = {
- if (path.length == dim * dim) Some(path)
- else
- first(legal_moves(dim, path, path.head), (x: Pos) => first_tour(dim, x::path))
-}
-
-/*
-for (dim <- 1 to 8) {
- val t = first_tour(dim, List((0, 0)))
- println(s"${dim} x ${dim} " + (if (t == None) "" else { print_board(dim, t.get) ; "" }))
-}
-*/
-
-def add_pair_urban(x: Pos)(y: Pos): Pos =
- (x._1 + y._1, x._2 + y._2)
-
-def is_legal_urban(dim: Int, path: Path)(x: Pos): Boolean =
- 0 <= x._1 && 0 <= x._2 && x._1 < dim && x._2 < dim && !path.contains(x)
-
-def moves_urban(x: Pos): List[Pos] =
- List(( 1, 2),( 2, 1),( 2, -1),( 1, -2),
- (-1, -2),(-2, -1),(-2, 1),(-1, 2)).map(add_pair_urban(x))
-
-def legal_moves_urban(dim: Int, path: Path, x: Pos): List[Pos] =
- moves_urban(x).filter(is_legal_urban(dim, path))
-
-def correct_urban(dim: Int)(p: Path): Boolean = p match {
- case Nil => true
- case x::Nil => true
- case x::y::p =>
- if (legal_moves_urban(dim, p, y).contains(x)) correct_urban(dim)(y::p) else false
-}
-
-
-
-
-val ts1 = first_tour(8, List((0, 0))).get
- assert(correct_urban(8)(ts1) == true)
-
-val ts2 = first_tour(4, List((0, 0)))
-assert(ts2 == None)
-
-print_board(8, first_tour(8, List((0, 0))).get)
-
-
--- a/progs/knight3.scala Sat Mar 11 23:12:49 2023 +0000
+++ /dev/null Thu Jan 01 00:00:00 1970 +0000
@@ -1,124 +0,0 @@
-// Part 3 about finding a single tour using the Warnsdorf Rule
-//=============================================================
-
-
-type Pos = (Int, Int)
-type Path = List[Pos]
-
-// for measuring time
-def time_needed[T](n: Int, code: => T) : T = {
- val start = System.nanoTime()
- for (i <- 0 until n) code
- val result = code
- val end = System.nanoTime()
- println(f"Time needed: ${(end - start) / 1.0e9}%3.3f secs.")
- result
-}
-
-def print_board(dim: Int, path: Path): Unit = {
- println
- for (i <- 0 until dim) {
- for (j <- 0 until dim) {
- print(f"${path.reverse.indexOf((i, j))}%4.0f ")
- }
- println
- }
-}
-
-def add_pair(x: Pos, y: Pos): Pos =
- (x._1 + y._1, x._2 + y._2)
-
-def is_legal(dim: Int, path: Path, x: Pos): Boolean =
- 0 <= x._1 && 0 <= x._2 && x._1 < dim && x._2 < dim && !path.contains(x)
-
-def moves(x: Pos): List[Pos] =
- List(( 1, 2),( 2, 1),( 2, -1),( 1, -2),
- (-1, -2),(-2, -1),(-2, 1),(-1, 2)).map(add_pair(x, _))
-
-def legal_moves(dim: Int, path: Path, x: Pos): List[Pos] =
- moves(x).filter(is_legal(dim, path, _))
-
-def ordered_moves(dim: Int, path: Path, x: Pos): List[Pos] =
- legal_moves(dim, path, x).sortBy((x) => legal_moves(dim, path, x).length)
-
-import scala.annotation.tailrec
-
-@tailrec
-def first(xs: List[Pos], f: Pos => Option[Path]): Option[Path] = xs match {
- case Nil => None
- case x::xs => {
- val result = f(x)
- if (result.isDefined) result else first(xs, f)
- }
-}
-
-
-//def first[A, B](xs: List[A], f: A => Option[B]): Option[B] =
-// xs.flatMap(f(_)).headOption
-
-
-def first_closed_tour_heuristics(dim: Int, path: Path): Option[Path] = {
- if (path.length == dim * dim && moves(path.head).contains(path.last)) Some(path)
- else
- first(ordered_moves(dim, path, path.head), (x: Pos) => first_closed_tour_heuristics(dim, x::path))
-}
-
-// heuristic cannot be used to search for closed tours on 7 x 7
-for (dim <- 1 to 6) {
- val t = time_needed(0, first_closed_tour_heuristics(dim, List((dim / 2, dim / 2))))
- println(s"${dim} x ${dim} closed: " + (if (t == None) "" else { print_board(dim, t.get) ; "" }))
-}
-
-
-//@tailrec
-/*
-def first_tour_heuristics(dim: Int, path: Path): Option[Path] = {
-
- @tailrec
- def aux(dim: Int, path: Path, moves: List[Pos]): Option[Path] =
- if (path.length == dim * dim) Some(path)
- else
- moves match {
- case Nil => None
- case x::xs => {
- val r = first_tour_heuristics(dim, x::path)
- if (r.isDefined) r else aux(dim, path, xs)
- }
- }
-
- aux(dim, path, ordered_moves(dim, path, path.head))
-}
-*/
-
-@tailrec
-def tour_on_mega_board(dim: Int, paths: List[Path]): Option[Path] = paths match {
- case Nil => None
- case (path::rest) =>
- if (path.length == dim * dim) Some(path)
- else tour_on_mega_board(dim, ordered_moves(dim, path, path.head).map(_::path) ::: rest)
-}
-
-
-
-/*
-def first_tour_heuristics(dim: Int, path: Path): Option[Path] = {
- if (path.length == dim * dim) Some(path)
- else
- for (p <- ordered_moves(dim, path, path.head))
- val r = first_tour_heuristics(dim, x::path)
- //first(ordered_moves(dim, path, path.head), (x: Pos) => first_tour_heuristics(dim, x::path))
- ordered_moves(dim, path, path.head).view.flatMap((x: Pos) => first_tour_heuristics(dim, x::path)).headOption
-}
-*/
-
-/*
-for (dim <- 1 to 50) {
- val t = first_tour_heuristics(dim, List((dim / 2, dim / 2)))
- println(s"${dim} x ${dim}: " + (if (t == None) "" else { print_board(dim, t.get) ; "" }))
-}
-*/
-
-val dim = 70
-println(s"${dim} x ${dim}:")
-print_board(dim, time_needed(0, tour_on_mega_board(dim, List(List((0, 0)))).get))
-
--- a/progs/knight3_sol.scala Sat Mar 11 23:12:49 2023 +0000
+++ /dev/null Thu Jan 01 00:00:00 1970 +0000
@@ -1,99 +0,0 @@
-// Part 3 about finding a single tour using the Warnsdorf Rule
-//=============================================================
-
-
-type Pos = (Int, Int)
-type Path = List[Pos]
-
-def print_board(dim: Int, path: Path): Unit = {
- println
- for (i <- 0 until dim) {
- for (j <- 0 until dim) {
- print(f"${path.reverse.indexOf((i, j))}%3.0f ")
- }
- println
- }
-}
-
-def add_pair(x: Pos)(y: Pos): Pos =
- (x._1 + y._1, x._2 + y._2)
-
-def is_legal(dim: Int, path: Path)(x: Pos): Boolean =
- 0 <= x._1 && 0 <= x._2 && x._1 < dim && x._2 < dim && !path.contains(x)
-
-def moves(x: Pos): List[Pos] =
- List(( 1, 2),( 2, 1),( 2, -1),( 1, -2),
- (-1, -2),(-2, -1),(-2, 1),(-1, 2)).map(add_pair(x))
-
-def legal_moves(dim: Int, path: Path, x: Pos): List[Pos] =
- moves(x).filter(is_legal(dim, path))
-
-def ordered_moves(dim: Int, path: Path, x: Pos): List[Pos] =
- legal_moves(dim, path, x).sortBy((x) => legal_moves(dim, path, x).length)
-
-import scala.annotation.tailrec
-
-/*
-@tailrec
-def first(xs: List[Pos], f: Pos => Option[Path]): Option[Path] = xs match {
- case Nil => None
- case x::xs => {
- val result = f(x)
- if (result.isDefined) result else first(xs, f)
- }
-}
-*/
-
-def first[A, B](xs: List[A], f: A => Option[B]): Option[B] =
- xs.flatMap(f(_)).headOption
-
-
-def first_closed_tour_heuristics(dim: Int, path: Path): Option[Path] = {
- if (path.length == dim * dim && moves(path.head).contains(path.last)) Some(path)
- else
- first(ordered_moves(dim, path, path.head), (x: Pos) => first_closed_tour_heuristics(dim, x::path))
-}
-
-/*
-for (dim <- 1 to 6) {
- val t = first_closed_tour_heuristics(dim, List((dim / 2, dim / 2)))
- println(s"${dim} x ${dim} closed: " + (if (t == None) "" else { print_board(dim, t.get) ; "" }))
-}
-*/
-
-//@tailrec
-def first_tour_heuristics(dim: Int, path: Path): Option[Path] = {
-
- @tailrec
- def aux(dim: Int, path: Path, moves: List[Position]): Option[Path
- if (path.length == dim * dim) Some(path)
- else
- moves match {
- case Nil => None
- case x::xs => {
- val r = first_tour_heuristics(dim, x::path)
- if (r.isDefined) Some(r) else aux(dim, path, xs)
- }
- aux(dim, path, ordered_moves(dim, path, path.head))
-}
-
-
-/*
-def first_tour_heuristics(dim: Int, path: Path): Option[Path] = {
- if (path.length == dim * dim) Some(path)
- else
- for (p <- ordered_moves(dim, path, path.head))
- val r = first_tour_heuristics(dim, x::path)
- //first(ordered_moves(dim, path, path.head), (x: Pos) => first_tour_heuristics(dim, x::path))
- ordered_moves(dim, path, path.head).view.flatMap((x: Pos) => first_tour_heuristics(dim, x::path)).headOption
-}
-*/
-
-/*
-for (dim <- 1 to 50) {
- val t = first_tour_heuristics(dim, List((dim / 2, dim / 2)))
- println(s"${dim} x ${dim}: " + (if (t == None) "" else { print_board(dim, t.get) ; "" }))
-}
-*/
-
-print_board(50, first_tour_heuristics(50, (25,25)::Nil).get)
--- a/progs/knight4.scala Sat Mar 11 23:12:49 2023 +0000
+++ /dev/null Thu Jan 01 00:00:00 1970 +0000
@@ -1,48 +0,0 @@
-import scala.util._
-
-def print_board(n: Int)(steps: List[(Int, Int)]): Unit = synchronized {
- for (i <- 0 until n) {
- for (j <- 0 until n) {
- print(f"${steps.indexOf((i, j))}%3.0f ")
- }
- println
- }
- //readLine()
- System.exit(0)
-}
-
-def add_pair(x: (Int, Int))(y: (Int, Int)) =
- (x._1 + y._1, x._2 + y._2)
-
-def is_legal(n: Int)(x: (Int, Int)) =
- 0 <= x._1 && 0 <= x._2 && x._1 < n && x._2 < n
-
-def moves(n: Int)(x: (Int, Int)): List[(Int, Int)] = {
- List((1, 2),(2, 1),(2, -1),(1, -2),
- (-1, -2),(-2, -1),(-2, 1),(-1, 2)).map(add_pair(x)).filter(is_legal(n))
-}
-
-def ordered_moves(n: Int)(steps: List[(Int, Int)])(x : (Int, Int)): List[(Int, Int)] =
- moves(n)(x).sortBy((x: (Int, Int)) => moves(n)(x).filterNot(steps.contains(_)).length)
-
-moves(8)(1,3)
-ordered_moves(8)(Nil)(1,3)
-ordered_moves(8)(List((2, 4), (2, 6)))(1,3)
-
-// non-circle tour parallel
-def tour(n: Int)(steps: List[(Int, Int)]): Unit = {
- if (steps.length == n * n && moves(n)(steps.head).contains(steps.last))
- print_board(n)(steps)
- else
- for (x <- ordered_moves(n)(steps)(steps.head).par; if (!steps.contains(x))) tour(n)(x :: steps)
-}
-
-val n = 7
-println(s"circle tour parallel fast: n = $n")
-
-val starts = for (i <- 0 until n; j <- 0 until n) yield (i, j)
-
-starts.par.foreach((x:(Int, Int)) => tour(n)(List(x)))
-
-
-
--- a/progs/knight5.scala Sat Mar 11 23:12:49 2023 +0000
+++ /dev/null Thu Jan 01 00:00:00 1970 +0000
@@ -1,45 +0,0 @@
-import scala.util._
-
-def print_board(n: Int)(steps: List[(Int, Int)]): Unit = synchronized {
- for (i <- 0 until n) {
- for (j <- 0 until n) {
- print(f"${steps.indexOf((i, j))}%3.0f ")
- }
- println
- }
- //readLine()
- System.exit(0)
-}
-
-def add_pair(x: (Int, Int))(y: (Int, Int)) =
- (x._1 + y._1, x._2 + y._2)
-
-def is_legal(n: Int)(x: (Int, Int)) =
- 0 <= x._1 && 0 <= x._2 && x._1 < n && x._2 < n
-
-def moves(n: Int)(x: (Int, Int)): List[(Int, Int)] = {
- List((1, 2),(2, 1),(2, -1),(1, -2),
- (-1, -2),(-2, -1),(-2, 1),(-1, 2)).map(add_pair(x)).filter(is_legal(n))
-}
-
-def ordered_moves(n: Int)(steps: List[(Int, Int)])(x : (Int, Int)): List[(Int, Int)] =
- moves(n)(x).sortBy((x: (Int, Int)) => moves(n)(x).filterNot(steps.contains(_)).length)
-
-moves(8)(1,3)
-ordered_moves(8)(Nil)(1,3)
-ordered_moves(8)(List((2, 4), (2, 6)))(1,3)
-
-// non-circle tour parallel
-def tour(n: Int)(steps: List[(Int, Int)]): Unit = {
- if (steps.length == n * n) // && moves(n)(steps.head).contains(steps.last))
- print_board(n)(steps)
- else
- for (x <- ordered_moves(n)(steps)(steps.head); if (!steps.contains(x))) tour(n)(x :: steps)
-}
-
-val n = 21
-println(s"circle tour parallel fast: n = $n")
-
-val starts = for (i <- 0 until n; j <- 0 until n) yield (i, j)
-
-starts.par.foreach((x:(Int, Int)) => tour(n)(List(x)))
--- a/progs/knight6.scala Sat Mar 11 23:12:49 2023 +0000
+++ /dev/null Thu Jan 01 00:00:00 1970 +0000
@@ -1,72 +0,0 @@
-import scala.util._
-
-type Pos = (Int, Int)
-
-
-def print_board(n: Int)(steps: List[Pos]): Unit = {
- for (i <- 0 until n) {
- for (j <- 0 until n) {
- print(f"${steps.reverse.indexOf((i, j))}%3.0f ")
- }
- println
- }
-}
-
-def add_pair(x: Pos)(y: Pos) =
- (x._1 + y._1, x._2 + y._2)
-
-def dist(n: Int)(y: Pos) =
- (n / 2 - y._1).abs + (n / 2 - y._2).abs
-
-def is_legal(n: Int)(x: Pos) =
- 0 <= x._1 && 0 <= x._2 && x._1 < n && x._2 < n
-
-def moves(n: Int)(x: Pos): List[Pos] = {
- List(( 1, 2),( 2, 1),( 2, -1),( 1, -2),
- (-1, -2),(-2, -1),(-2, 1),(-1, 2)).map(add_pair(x)).filter(is_legal(n))
-}
-
-def moves_filtered(n: Int)(steps: List[Pos])(x: Pos): List[Pos] = {
- moves(n)(x).filterNot(steps.contains(_))
-}
-
-def ordered_moves(n: Int)(steps: List[Pos])(x: Pos): List[Pos] =
- moves_filtered(n)(steps)(x).sortBy((x: Pos) => (moves_filtered(n)(steps)(x).length, dist(n)(x)))
-
-/*def first[A, B](xs: List[A], f: A => Option[B]): Option[B] = xs match {
- case Nil => None
- case x::xs => {
- val result = f(x)
- if (result.isDefined) result else first(xs, f)
- }
-}*/
-
-def first[A, B](xs: List[A], f: A => Option[B]): Option[B] =
- xs.par.flatMap(f(_)).headOption
-
-// non-circle tours, including distance
-def tour(n: Int)(steps: List[Pos]): Option[List[Pos]] = {
- if (steps.length == n * n) //&& moves(n)(steps.head).contains(steps.last))
- Some(steps)
- else first(ordered_moves(n)(steps)(steps.head), (x: Pos) => tour(n)(x::steps))
-}
-
-//val n = 8
-val n = 6
-println(s"number simple tours: n = $n")
-
-println(print_board(n)((tour(n)(List((0, 0)))).get))
-//println((for (i <- 0 until n; j <- 0 until n) yield tour(n)(List((i, j)))).flatten.distinct.size)
-
-
-
-
-
-/*
-def first[A, B](xs: List[A], f: A => Option[B]): Option[B] =
- xs.view.flatMap(f(_)).headOption
-*/
-
-/*
-
-*/
--- a/progs/population.csv Sat Mar 11 23:12:49 2023 +0000
+++ /dev/null Thu Jan 01 00:00:00 1970 +0000
@@ -1,216 +0,0 @@
-country,population_size
-Afghanistan,32758020
-Albania,2889104
-Algeria,39113313
-American Samoa,55437
-Andorra,79223
-Angola,26920466
-Antigua and Barbuda,98875
-Argentina,42981515
-Armenia,2906220
-Aruba,103795
-Australia,23460694
-Austria,8541575
-Azerbaijan,9535079
-Bahamas,382169
-Bahrain,1336397
-Bangladesh,159405279
-Barbados,283385
-Belarus,9474511
-Belgium,11209057
-Belize,351694
-Benin,10286712
-Bermuda,65139
-Bhutan,776448
-Bolivia,10562159
-Bosnia and Herzegovina,3566002
-Botswana,2168573
-Brazil,204213133
-British Virgin Islands,29588
-Brunei Darussalam,411704
-Bulgaria,7223938
-Burkina Faso,17585977
-Burundi,9891790
-Cabo Verde,526437
-Cambodia,15270790
-Cameroon,22239904
-Canada,35544564
-Cayman Islands,59172
-Central African Republic,4515392
-Chad,13569438
-Channel Islands,162969
-Chile,17613798
-China,1364270000
-Colombia,47791911
-Comoros,759385
-Congo,73722860
-Costa Rica,4757575
-Cote d'Ivoire,22531350
-Croatia,4238389
-Cuba,11439767
-Curacao,155909
-Cyprus,1152309
-Czech Republic,10525347
-Denmark,5643475
-Djibouti,912164
-Dominica,72778
-Dominican Republic,10405844
-Ecuador,15903112
-Egypt,91812566
-El Salvador,6281189
-Equatorial Guinea,1129424
-Estonia,1314545
-Ethiopia,97366774
-Faroe Islands,48842
-Fiji,885806
-Finland,5461512
-France,66331957
-French Polynesia,275484
-Gabon,1875713
-Gambia,1917852
-Georgia,3727000
-Germany,80982500
-Ghana,26962563
-Gibraltar,34038
-Greece,10892413
-Greenland,56295
-Grenada,106360
-Guam,160967
-Guatemala,15923559
-Guinea,11805509
-Guinea-Bissau,1725744
-Guyana,763393
-Haiti,10572466
-Honduras,8809216
-Hong Kong SAR,7241700
-Hungary,9866468
-Iceland,327386
-India,1293859294
-Indonesia,255131116
-Iran,78411092
-Iraq,35006080
-Ireland,4617225
-Isle of Man,82590
-Israel,8215700
-Italy,60789140
-Jamaica,2862087
-Japan,127276000
-Jordan,8809306
-Kazakhstan,17289224
-Kenya,46024250
-Kiribati,110458
-North Korea,25116363
-South Korea,50746659
-Kosovo,1821800
-Kuwait,3782450
-Kyrgyz Republic,5835500
-Lao PDR,6576397
-Latvia,1993782
-Lebanon,5603279
-Lesotho,2145785
-Liberia,4390737
-Libya,6204108
-Liechtenstein,37127
-Lithuania,2932367
-Luxembourg,556319
-Macao SAR,588781
-Macedonia,2077495
-Madagascar,23589801
-Malawi,17068838
-Malaysia,30228017
-Maldives,401000
-Mali,16962846
-Malta,427364
-Marshall Islands,52898
-Mauritania,4063920
-Mauritius,1260934
-Mexico,124221600
-Micronesia,104015
-Moldova,3556397
-Monaco,38132
-Mongolia,2923896
-Montenegro,621810
-Morocco,34318082
-Mozambique,27212382
-Myanmar,51924182
-Namibia,2370992
-Nauru,11853
-Nepal,28323241
-Netherlands,16865008
-New Caledonia,268000
-New Zealand,4509700
-Nicaragua,6013997
-Niger,19148219
-Nigeria,176460502
-Northern Mariana Islands,54468
-Norway,5137232
-Oman,3960925
-Pakistan,185546257
-Palau,21094
-Panama,3903986
-Papua New Guinea,7755785
-Paraguay,6552584
-Peru,30973354
-Philippines,100102249
-Poland,38011735
-Portugal,10401062
-Puerto Rico,3534874
-Qatar,2374419
-Romania,19908979
-Russian Federation,143819666
-Rwanda,11345357
-Samoa,192290
-San Marino,32657
-Sao Tome and Principe,191266
-Saudi Arabia,30776722
-Senegal,14546111
-Serbia,7130576
-Seychelles,91359
-Sierra Leone,7079162
-Singapore,5469724
-Sint Maarten (Dutch part),37685
-Slovak Republic,5418649
-Slovenia,2061980
-Solomon Islands,575504
-Somalia,13513125
-South Africa,54146734
-South Sudan,11530971
-Spain,46480882
-Sri Lanka,20771000
-St. Kitts and Nevis,53739
-St. Lucia,176421
-St. Martin (French part),31530
-St. Vincent and the Grenadines,109357
-Sudan,37737913
-Suriname,547928
-Swaziland,1295097
-Sweden,9696110
-Switzerland,8188649
-Syrian Arab Republic,19203090
-Tajikistan,8362745
-Tanzania,52234869
-Thailand,68416772
-Timor-Leste,1212814
-Togo,7228915
-Tonga,105782
-Trinidad and Tobago,1354493
-Tunisia,11143908
-Turkey,77030628
-Turkmenistan,5466241
-Turks and Caicos Islands,33739
-Tuvalu,10908
-Uganda,38833338
-Ukraine,45271947
-United Arab Emirates,9070867
-United Kingdom,64613160
-United States,318563456
-Uruguay,3419546
-Uzbekistan,30757700
-Vanuatu,258850
-Venezuela,30738378
-Vietnam,90728900
-Virgin Islands (U.S.),104170
-West Bank and Gaza,4294682
-Yemen,26246327
-Zambia,15620974
-Zimbabwe,15411675