# HG changeset patch # User Christian Urban # Date 1512335509 0 # Node ID 6ea450e999e212f0007e09955a19435474fa0439 # Parent 863feeb5c760346aafee83cb4a2e5b91c5c09ad5 updated diff -r 863feeb5c760 -r 6ea450e999e2 testing1/alcohol.scala --- a/testing1/alcohol.scala Wed Nov 29 21:22:29 2017 +0000 +++ b/testing1/alcohol.scala Sun Dec 03 21:11:49 2017 +0000 @@ -6,66 +6,93 @@ 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 = +val url_alcohol = "https://raw.githubusercontent.com/fivethirtyeight/data/master/alcohol-consumption/drinks.csv" -val file_population = +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) +//(1) Complete the get_csv_page function below. It takes a URL-string +// as argument and generates a list of strings corresponding to each +// line in the downloaded csv-list. The URL url_alcohol above is one +// possible argument. -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 get_csv_page(url: String) : List[String] = ... +def get_csv_page(url: String) : List[String] = { + val csv = Source.fromURL(url) + val contents = csv.mkString.split("\n") + contents.toList +} +// Complete the get_csv_file function below. It takes a file name +// as argument and reads the content of the given file. Like above, +// it should generate a list of strings corresponding to each +// line in the csv-list. The filename file_population is one possible +// argument. -process_alcs(alcs.drop(1))(1) -process_pops(pops.drop(1))("Albania") - -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 +//def get_csv_file(file: String) : List[String] = ... +def get_csv_file(file: String) : List[String] = { + val csv = Source.fromFile(file) + val contents = csv.mkString.split("\n") + contents.toList } - -sorted_country_consumption().take(10) -sorted_country_consumption().size +//(2) Complete the functions that process the csv-lists. For +// process_alcs extract the country name (as String) and the +// pure alcohol consumption (as Double). For process_pops +// generate a Map of Strings (country names) to Long numbers +// (population sizes). -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) +//def process_alcs(lines: List[String]) : List[(String, Double)] = ... +def process_alcs(lines: List[String]) : List[(String, Double)] = { + val beheaded = lines.drop(1) + val splitEntries = for (n <- beheaded) yield n.split(",").toList + for (n <- splitEntries) yield (n.take(1).mkString, n.drop(4).mkString.toDouble) +} +//def process_pops(lines: List[String]) : Map[String, Long] = ... +def process_pops(lines: List[String]) : Map[String, Long] = { + val beheaded = lines.drop(1); + def toOnePair(line: String) : (String, Long) = { + val splitAsList = line.split(",").toList + (splitAsList.take(1).mkString, splitAsList.drop(1).mkString.toLong) + } + val splitEntries = for (n <- beheaded) yield toOnePair(n) + splitEntries.toMap } -percentage(10) -percentage(164) +//(3) Calculate for each country the overall alcohol_consumption using +// the data from the alcohol list and the population sizes list. You +// should only include countries on the alcohol list that are also +// on the population sizes list with the exact same name. Note that +// the spelling of some names in the alcohol list differs from the +// population sizes list. You can ignore entries where the names differ. +// Sort the resulting list according to the country with the highest alcohol +// consumption to the country with the lowest alcohol consumption. +//def sorted_country_consumption() : List[(String, Long)] = ... +def sorted_country_consumption() : List[(String, Long)] = { + val countryToPop = process_pops(get_csv_file(file_population)) + val countryAndAlc = process_alcs(get_csv_page(url_alcohol)) + val countryAndConsumption = countryAndAlc.collect { + case oneCountryAndAlc + if countryToPop.isDefinedAt(oneCountryAndAlc._1) => + (oneCountryAndAlc._1, (oneCountryAndAlc._2*countryToPop.get(oneCountryAndAlc._1).get).toLong) + } + countryAndConsumption.sortWith(_._2 > _._2) } + +// Calculate the world consumption of pure alcohol of all countries, which +// should be the first element in the tuple below. The second element is +// the overall consumption of the first n countries in the sorted list +// from above; and finally the double should be the percentage of the +// first n countries drinking from the the world consumption of alcohol. + +//def percentage(n: Int) : (Long, Long, Double) = ... +def percentage(n: Int) : (Long, Long, Double) = { + val ctryConsump = sorted_country_consumption() + val totalAlc = ctryConsump.map(_._2).sum + val firstNAlc = ctryConsump.take(n).map(_._2).sum + val pcntage = (firstNAlc*1.0/totalAlc)*100; + (ctryConsump.map(_._2).sum, ctryConsump.take(n).map(_._2).sum, pcntage) +} +} diff -r 863feeb5c760 -r 6ea450e999e2 testing1/drumb.scala --- a/testing1/drumb.scala Wed Nov 29 21:22:29 2017 +0000 +++ b/testing1/drumb.scala Sun Dec 03 21:11:49 2017 +0000 @@ -1,4 +1,4 @@ -// Advanvced Part 3 about a really dumb investment strategy +// Advanced Part 3 about a really dumb investment strategy //========================================================== object CW6c { @@ -7,131 +7,110 @@ //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") +val rstate_portfolio = List("PLD", "PSA", "AMT", "AIV", "AVB", "BXP", "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=<>&a=0&b=1&c=<>&d=1&e=1&f=<> -// -// and extracting the first January Adjusted Close price in a year. - +// (1.a) The function below takes a stock symbol and a year as arguments. +// It should read the corresponding CSV-file and read the January +// data from the given year. The data should be collected in a list of +// strings for each line in the CSV-file. 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_january_data(symbol: String, year: Int) : List[String] = { + val file = symbol + ".csv" + val list = scala.io.Source.fromFile(file).mkString.split("\n").toList + val rx = (year.toString + ".*") + (for(n <- 1 to list.length -1 if(list(n) matches rx)) yield list(n)).toList +} + + +// (1.b) From the output of the get_january_data function, the next function +// should extract the first line (if it exists) and the corresponding +// first trading price in that year as Option[Double]. If no line is +// generated by get_january_data then the result is None 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) + val first_line = get_january_data(symbol, year) + + if(first_line.length == 0 ){ + None + } else { + Option((first_line(0).split(",")(1)).toDouble) + } } -get_first_price("GOOG", 1980) -get_first_price("GOOG", 2010) -get_first_price("FB", 2014) - -// 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]]] = - for (year <- years.toList) yield - for (symbol <- portfolio) yield get_first_price(symbol, year) +// (1.c) Complete the function below that obtains all first prices +// for the stock symbols from a portfolio (list of strings) and +// for the given range of years. The inner lists are for the +// stock symbols and the outer list for the years. -// test case -val p_fb = get_prices(List("FB"), 2012 to 2014) -val p = get_prices(List("GOOG", "AAPL"), 2010 to 2012) +def get_prices(portfolio: List[String], years: Range) : List[List[Option[Double]]] ={ + (for(y <- years) yield (for(n <- 0 to portfolio.length-1) yield get_first_price(portfolio(n), y)).toList).toList +} + -val tt = get_prices(List("BIDU"), 2004 to 2008) -// (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). +// (2) The first function below calculates the change factor (dta) 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). The input to this +// function are the nested lists created by get_prices above. 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 - } + for( x <- price_old; y <- price_new) yield (y-x)/x } -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)) +def get_deltas(data: List[List[Option[Double]]]) : List[List[Option[Double]]] = { + (for( n <- 1 to data.length-1) yield (for(i <- 0 to data(n).length-1) yield get_delta(data(n-1)(i), data(n)(i))).toList).toList +} -// test case using the prices calculated above -val d = get_deltas(p) -val ttd = get_deltas(tt) // (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. +// calculates the yearly yield, i.e. new balance, 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 = { - 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 yearly_yield(data: List[List[Option[Double]]], balance: Long, year: Int) : Long = { + val increments = (for(n <- 0 to data(year).length-1 if(!(data(year)(n) == None))) yield (data(year)(n).getOrElse(0.0))).toList + val sumi = (increments.sum).toDouble + if(increments.length == 0){ + balance + }else{ + val il = (increments.length).toDouble + val averag = sumi/il + val i = (balance + (balance*averag)) + i.toLong + } } -//yearly_yield(d, 100, 0) -//compound_yield(d.take(6), 100, 0) - -//test case -//yearly_yield(d, 100, 0) -//yearly_yield(d, 225, 1) -//yearly_yield(d, 246, 2) -//yearly_yield(d, 466, 3) -//yearly_yield(d, 218, 4) - -//yearly_yield(d, 100, 0) -//yearly_yield(d, 125, 1) - -def investment(portfolio: List[String], years: Range, start_balance: Long): Long = { - compound_yield(get_deltas(get_prices(portfolio, years)), start_balance, 0) +def compound_yield(data: List[List[Option[Double]]], balance: Long, ye: Int) : Long = {//if(year == 0) yearly_yield(data, balance, 0) else compound_yield(data, yearly_yield(data, balance, year), year-1) + val increments_py = (for(year <- 0 to ye) yield { + val increments = (for(n <- 0 to data(year).length-1 if(!(data(year)(n) == None))) yield (data(year)(n).getOrElse(0.0))).toList + val sum_of = (increments.sum).toDouble + val number_of = (increments.length).toDouble + sum_of/number_of + 1.0 + }).toList + val mul_factor = increments_py.reduceLeft(_*_) + (balance*mul_factor).toLong +} +def investment(portfolio: List[String], years: Range, start_balance: Long) : Long = { + val p = get_prices(portfolio, years) + val d = get_deltas(p) + compound_yield(d, start_balance, d.length-1) } -val one = get_deltas(get_prices(rstate_portfolio, 1978 to 1984)) -val two = get_deltas(get_prices(blchip_portfolio, 1978 to 1984)) -val one_full = get_deltas(get_prices(rstate_portfolio, 1978 to 2017)) -val two_full = get_deltas(get_prices(blchip_portfolio, 1978 to 2017)) - -one_full.map(_.flatten).map(_.sum).sum -two_full.map(_.flatten).map(_.sum).sum //test cases for the two portfolios given above -//println("Real data: " + investment(rstate_portfolio, 1978 to 1981, 100)) -//println("Blue data: " + investment(blchip_portfolio, 1978 to 1981, 100)) +investment(rstate_portfolio, 1978 to 2017, 100) +investment(blchip_portfolio, 1978 to 2017, 100) -//for (i <- 1978 to 2017) { -// println("Year " + i) -// println("Real data: " + investment(rstate_portfolio, 1978 to i, 100)) -// println("Blue data: " + investment(blchip_portfolio, 1978 to i, 100)) -//} - -//1984 -//1992 } diff -r 863feeb5c760 -r 6ea450e999e2 testing2/knight3.scala --- a/testing2/knight3.scala Wed Nov 29 21:22:29 2017 +0000 +++ b/testing2/knight3.scala Sun Dec 03 21:11:49 2017 +0000 @@ -1,45 +1,96 @@ -import scala.annotation.tailrec +// Part 3 about finding a single tour using the Warnsdorf Rule +//============================================================= + object CW7c { -type Pos = (Int, Int) // a position on a chessboard -type Path = List[Pos] // a path...a list of positions + +type Pos = (Int, Int) +type Path = List[Pos] -def is_legal(dim: Int, path: Path)(x: Pos) : Boolean = { - if((x._1 >= 0) && (x._2 >= 0) && (x._1 < dim) && (x._2 < dim)){ - !(path.contains(x)) - } else false - } - -def legal_moves(dim: Int, path: Path, x: Pos) : List[Pos] = { - val lst = List( (1,2),(2,1),(2,-1),(1,-2), (-1,-2),(-2,-1),(-2,1),(-1,2) ) - val mapping = lst.map(s => ( s._1 + x._1, s._2 + x._2) ) - for( i <- mapping if ( is_legal(dim,path)(i) )) yield i - } - -def ordered_moves(dim: Int, path: Path, x: Pos) : List[Pos] = { -legal_moves(dim,path,x).sortBy(legal_moves(dim,path,_).length ) +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 first(xs: List[Pos], f: Pos => Option[Path]) : Option[Path] ={ - if(xs.isEmpty) - None - else { - val b = f(xs.head) - if (b!=None) - b - else - first(xs.tail,f) - } +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_closed_tour_heuristic(dim: Int, path: Path) : Option[Path] = { - if (dim < 5) None - else - if(path.length==dim*dim) Some(path) - else - first(ordered_moves(dim,path,path.head),y => first_closed_tour_heuristic(dim, y::path)) - } - } -first_closed_tour_heuristic(6, List((3, 3))) +def first_closed_tour_heuristic(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_heuristic(dim, x::path)) +} + +/* +for (dim <- 1 to 6) { + val t = first_closed_tour_heuristic(dim, List((dim / 2, dim / 2))) + println(s"${dim} x ${dim} closed: " + (if (t == None) "" else { print_board(dim, t.get) ; "" })) +}*/ + + +def first_tour_heuristic(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_heuristic(dim, x::path) + if (r.isDefined) r else aux(dim, path, xs) + } + } + + aux(dim, path, ordered_moves(dim, path, path.head)) +} + +/* +def first_tour_heuristic(dim: Int, path: Path): Option[Path] = { + if (path.length == dim * dim) Some(path) + else + first(ordered_moves(dim, path, path.head), (x: Pos) => first_tour_heuristic(dim, x::path)) +} +*/ + +/* +for (dim <- 1 to 50) { + val t = first_tour_heuristic(dim, List((dim / 2, dim / 2))) + println(s"${dim} x ${dim}: " + (if (t == None) "" else { print_board(dim, t.get) ; "" })) +} +*/ + +} + + +//CW7c.first_tour_heuristic(50, List((0,0))).get diff -r 863feeb5c760 -r 6ea450e999e2 testing3/bf.scala --- a/testing3/bf.scala Wed Nov 29 21:22:29 2017 +0000 +++ b/testing3/bf.scala Sun Dec 03 21:11:49 2017 +0000 @@ -49,6 +49,7 @@ } + // (2c) Complete the run function that interpretes (runs) a brainf*** // program: the arguments are a program, a program counter, // a memory counter and a brainf*** memory. It Returns the