--- a/cws/cw02.tex Thu Dec 07 12:09:06 2017 +0000
+++ b/cws/cw02.tex Sat Dec 16 23:53:28 2017 +0000
@@ -3,6 +3,7 @@
\usepackage[LSBC4,T1]{fontenc}
\let\clipbox\relax
\usepackage{../style}
+\usepackage{disclaimer}
\begin{document}
@@ -25,40 +26,14 @@
might include material you have not yet seen in the first two
lectures. \bigskip
-\noindent
-\textbf{Important:}
-
-\begin{itemize}
-\item Make sure the files you submit can be processed by just calling\\
-\mbox{\texttt{scala <<filename.scala>>}} on the commandline.
-
-\item Do not use any mutable data structures in your
-submissions! They are not needed. This means you cannot create new
-\texttt{Array}s or \texttt{ListBuffer}s, for example.
-
-\item Do not use \texttt{return} in your code! It has a different
- meaning in Scala, than in Java.
-
-\item Do not use \texttt{var}! This declares a mutable variable. Only
- use \texttt{val}!
-
-\item Do not use any parallel collections! No \texttt{.par} therefore!
- Our testing and marking infrastructure is not set up for it.
-\end{itemize}
-
-\noindent
+\IMPORTANT{}
Also note that the running time of each part will be restricted to a
maximum of 360 seconds on my laptop: If you calculate a result once,
try to avoid to calculate the result again. Feel free to copy any code
you need from files \texttt{knight1.scala}, \texttt{knight2.scala} and
\texttt{knight3.scala}.
-
-\subsection*{Disclaimer}
-It should be understood that the work you submit represents
-your \textbf{own} effort. You have not copied from anyone else. An
-exception is the Scala code I showed during the lectures or
-uploaded to KEATS, which you can freely use.
+\DISCLAIMER{}
\subsection*{Background}
@@ -212,16 +187,16 @@
\subsubsection*{Tasks (file knight1.scala)}
\begin{itemize}
-\item[(1a)] Implement an \texttt{is-legal-move} function that takes a
- dimension, a path and a position as argument and tests whether the
+\item[(1a)] Implement an \texttt{is\_legal\_move} function that takes a
+ dimension, a path and a position as arguments and tests whether the
position is inside the board and not yet element in the
path. \hfill[1 Mark]
-\item[(1b)] Implement a \texttt{legal-moves} function that calculates for a
+\item[(1b)] Implement a \texttt{legal\_moves} function that calculates for a
position all legal onward moves. If the onward moves are
placed on a circle, you should produce them starting from
``12-o'clock'' following in clockwise order. For example on an
- $8\times 8$ board for a knight on position $(2, 2)$ and otherwise
+ $8\times 8$ board for a knight at position $(2, 2)$ and otherwise
empty board, the legal-moves function should produce the onward
positions in this order:
@@ -238,8 +213,8 @@
\end{center}
\mbox{}\hfill[1 Mark]
-\item[(1c)] Implement two recursive functions (count-tours and
- enum-tours). They each take a dimension and a path as
+\item[(1c)] Implement two recursive functions (\texttt{count\_tours} and
+ \texttt{enum\_tours}). They each take a dimension and a path as
arguments. They exhaustively search for tours starting
from the given path. The first function counts all possible
tours (there can be none for certain board sizes) and the second
@@ -266,11 +241,11 @@
\subsubsection*{Tasks (file knight2.scala)}
\begin{itemize}
-\item[(2a)] Implement a first-function. This function takes a list of
- positions and a function $f$ as arguments. The function $f$ takes a
- position as argument and produces an optional path. So $f$'s type is
- \texttt{Pos => Option[Path]}. The idea behind the first-function is
- as follows:
+\item[(2a)] Implement a \texttt{first}-function. This function takes a list of
+ positions and a function $f$ as arguments; $f$ is the name we give to
+ this argument). The function $f$ takes a position as argument and
+ produces an optional path. So $f$'s type is \texttt{Pos =>
+ Option[Path]}. The idea behind the \texttt{first}-function is as follows:
\[
\begin{array}{lcl}
@@ -283,21 +258,25 @@
\]
\noindent That is, we want to find the first position where the
- result of $f$ is not \texttt{None}, if there is one. Note that you
- do not (need to) know anything about the function $f$ except its
- type, namely \texttt{Pos => Option[Path]}. There is one additional
- point however you should take into account when implementing
- \textit{first}: you will need to calculate what the result of $f(x)$
- is; your code should do this only \textbf{once}!\\\mbox{}\hfill[1 Mark]
+ result of $f$ is not \texttt{None}, if there is one. Note that
+ `inside' \texttt{first}, you do not (need to) know anything about
+ the argument $f$ except its type, namely \texttt{Pos =>
+ Option[Path]}. There is one additional point however you should
+ take into account when implementing \texttt{first}: you will need to
+ calculate what the result of $f(x)$ is; your code should do this
+ only \textbf{once} and for as \textbf{few} elements in the list as
+ possible! Do not calculate $f(x)$ for all elements and then see which
+ is the first \texttt{Some}.\\\mbox{}\hfill[1 Mark]
-\item[(2b)] Implement a first-tour function that uses the
- first-function from (2a), and searches recursively for a tour.
- As there might not be such a tour at all, the first-tour function
- needs to return an \texttt{Option[Path]}.\\\mbox{}\hfill[2 Marks]
+\item[(2b)] Implement a \texttt{first\_tour} function that uses the
+ \texttt{first}-function from (2a), and searches recursively for a tour.
+ As there might not be such a tour at all, the \texttt{first\_tour} function
+ needs to return a value of type
+ \texttt{Option[Path]}.\\\mbox{}\hfill[2 Marks]
\end{itemize}
\noindent
-\textbf{Testing:} The first tour function will be called with board
+\textbf{Testing:} The \texttt{first\_tour} function will be called with board
sizes of up to $8 \times 8$.
\bigskip
@@ -309,13 +288,13 @@
this functions takes an \texttt{Int} as an argument.
-\newpage
+%%\newpage
\subsection*{Part 2 (3 Marks)}
As you should have seen in Part 1, a naive search for tours beyond
$8 \times 8$ boards and also searching for closed tours even on small
-boards takes too much time. There is a heuristic, called Warnsdorf's
-rule that can speed up finding a tour. This heuristic states that a
+boards takes too much time. There is a heuristic, called \emph{Warnsdorf's
+Rule} that can speed up finding a tour. This heuristic states that a
knight is moved so that it always proceeds to the field from which the
knight will have the \underline{fewest} onward moves. For example for
a knight on field $(1, 3)$, the field $(0, 1)$ has the fewest possible
@@ -332,7 +311,7 @@
setpieces={Na3}]
\noindent
-Warnsdorf's rule states that the moves on the board above should be
+Warnsdorf's Rule states that the moves on the board above should be
tried in the order
\[
@@ -347,22 +326,24 @@
\subsubsection*{Tasks (file knight3.scala)}
\begin{itemize}
-\item[(3a)] Write a function ordered-moves that calculates a list of
+\item[(3a)] Write a function \texttt{ordered\_moves} that calculates a list of
onward moves like in (1b) but orders them according to the
- Warnsdorf’s rule. That means moves with the fewest legal onward moves
+ Warnsdorf’s Rule. That means moves with the fewest legal onward moves
should come first (in order to be tried out first). \hfill[1 Mark]
-\item[(3b)] Implement a first-closed-tour-heuristic function that searches for a
+\item[(3b)] Implement a \texttt{first\_closed-tour\_heuristic}
+ function that searches for a
\textbf{closed} tour on a $6\times 6$ board. It should use the
- first-function from (2a) and tries out onward moves according to
- the ordered-moves function from (3a). It is more likely to find
+ \texttt{first}-function from (2a) and tries out onward moves according to
+ the \texttt{ordered\_moves} function from (3a). It is more likely to find
a solution when started in the middle of the board (that is
position $(dimension / 2, dimension / 2)$). \hfill[1 Mark]
-\item[(3c)] Implement a first-tour-heuristic function for boards up to
+\item[(3c)] Implement a \texttt{first\_tour\_heuristic} function
+ for boards up to
$40\times 40$. It is the same function as in (3b) but searches for
tours (not just closed tours). You have to be careful to write a
- tail-recursive version of the first-tour-heuristic function
+ tail-recursive function of the \texttt{first\_tour\_heuristic} function
otherwise you will get problems with stack-overflows.\\
\mbox{}\hfill[1 Mark]
\end{itemize}
--- a/testing1/drumb.scala Thu Dec 07 12:09:06 2017 +0000
+++ b/testing1/drumb.scala Sat Dec 16 23:53:28 2017 +0000
@@ -1,4 +1,4 @@
-// Advanced Part 3 about a really dumb investment strategy
+// Advanvced Part 3 about a really dumb investment strategy
//==========================================================
object CW6c {
@@ -7,110 +7,228 @@
//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.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.
+// (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.
+
import io.Source
import scala.util._
-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_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 first_line = get_january_data(symbol, year)
-
- if(first_line.length == 0 ){
- None
- } else {
- Option((first_line(0).split(",")(1)).toDouble)
- }
+ 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)
-// (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.
+
+// 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)
-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
+// test case
+val prices_fb = get_prices(List("FB"), 2012 to 2014)
+val prices_goap = get_prices(List("GOOG", "AAPL"), 2010 to 2014)
+val prices_bidu = get_prices(List("BIDU"), 2004 to 2008)
+val prices_goapfb = get_prices(List("GOOG", "AAPL", "FB"), 2010 to 2016)
+
+// (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] = {
+ (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))
-// (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] = {
- for( x <- price_old; y <- price_new) yield (y-x)/x
-}
-
-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 deltas_fb = get_deltas(prices_fb)
+val deltas_goap = get_deltas(prices_goap)
+val deltas_bidu = get_deltas(prices_bidu)
+val deltas_goapfb = get_deltas(prices_goapfb)
// (3) Write a function that given change factors, a starting balance and a year
-// 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.
+// 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 = {
- 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
- }
+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
+ (for (x <- somes) yield ((1.0 + x) * portion)).sum.toLong
+ //balance + (for (x <- somes) yield (x * portion)).sum.toLong
+ }
+}
+
+def yearly_yield_double(data: List[List[Option[Double]]], balance: Double, year: Int): Double = {
+ val somes = data(year).flatten
+ val somes_length = somes.length
+ if (somes_length == 0) balance
+ else {
+ val portion: Double = balance / somes_length.toDouble
+ balance + (for (x <- somes) yield (x * portion)).sum
+ }
+}
+
+def compound_yield(data: List[List[Option[Double]]], balance: Long, year: Int): Long = {
+ println(balance)
+ if (year >= data.length) balance else {
+ val new_balance = yearly_yield(data, balance, year)
+ compound_yield(data, new_balance, year + 1)
+ }
+}
+
+def compound_yield_double(data: List[List[Option[Double]]], balance: Double, year: Int): Long = {
+ if (year >= data.length) balance.toLong else {
+ val new_balance = yearly_yield_double(data, balance.toDouble, year)
+ compound_yield_double(data, new_balance, year + 1)
+ }
}
-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 prices_fb = get_prices(List("FB"), 2012 to 2014)
+val prices_goap = get_prices(List("GOOG", "AAPL"), 2010 to 2014)
+val prices_bidu = get_prices(List("BIDU"), 2004 to 2008)
+val prices_goapfb = get_prices(List("GOOG", "AAPL", "FB"), 2010 to 2016)
+
+val deltas_fb = get_deltas(prices_fb)
+val deltas_goap = get_deltas(prices_goap)
+val deltas_bidu = get_deltas(prices_bidu)
+val deltas_goapfb = get_deltas(prices_goapfb)
+
+
+yearly_yield(deltas_bidu, 100, 0)
+yearly_yield(deltas_bidu, 100, 1)
+yearly_yield(deltas_bidu, 100, 2)
+yearly_yield(deltas_bidu, 192, 3)
+//598
+
+yearly_yield(deltas_fb, 100, 0)
+yearly_yield(deltas_fb, 100, 1)
+//yearly_yield(deltas_fb, 195, 2)
+
+yearly_yield(deltas_goap, 100, 0)
+yearly_yield(deltas_goap, 125, 1)
+yearly_yield(deltas_goap, 146, 2)
+yearly_yield(deltas_goap, 177, 3)
+//yearly_yield(deltas_goap, 227, 4)
+
+yearly_yield(deltas_goapfb, 100, 0)
+yearly_yield(deltas_goapfb, 125, 1)
+yearly_yield(deltas_goapfb, 146, 2)
+yearly_yield(deltas_goapfb, 177, 3)
+yearly_yield(deltas_goapfb, 267, 4)
+yearly_yield(deltas_goapfb, 337, 5)
+//416
+
+compound_yield(deltas_goapfb.take(1), 100, 0)
+compound_yield(deltas_goapfb.take(2), 100, 0)
+compound_yield(deltas_goapfb.take(3), 100, 0)
+compound_yield(deltas_goapfb.take(4), 100, 0)
+compound_yield(deltas_goapfb.take(5), 100, 0)
+compound_yield(deltas_goapfb.take(6), 100, 0)
+
+compound_yield_double(deltas_goapfb.take(1), 100.0, 0)
+compound_yield_double(deltas_goapfb.take(2), 100.0, 0)
+compound_yield_double(deltas_goapfb.take(3), 100.0, 0)
+compound_yield_double(deltas_goapfb.take(4), 100.0, 0)
+compound_yield_double(deltas_goapfb.take(5), 100.0, 0)
+compound_yield_double(deltas_goapfb.take(6), 100.0, 0)
+
+//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 investment_double(portfolio: List[String], years: Range, start_balance: Long): Long = {
+ compound_yield_double(get_deltas(get_prices(portfolio, years)), start_balance.toDouble, 0)
+}
-//test cases for the two portfolios given above
investment(rstate_portfolio, 1978 to 2017, 100)
investment(blchip_portfolio, 1978 to 2017, 100)
+investment_double(rstate_portfolio, 1978 to 2017, 100)
+investment_double(blchip_portfolio, 1978 to 2017, 100)
+
+
+/*
+val q1 = get_deltas(get_prices(List("GOOG", "AAPL", "BIDU"), 2000 to 2017))
+yearly_yield(q1, 100, 0)
+yearly_yield(q1, 100, 1)
+yearly_yield(q1, 100, 2)
+yearly_yield(q1, 100, 3)
+yearly_yield(q1, 100, 4)
+yearly_yield(q1, 100, 5)
+yearly_yield(q1, 100, 6)
+
+investment(List("GOOG", "AAPL", "BIDU"), 2004 to 2017, 100)
+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 2017, 100))
+//println("Blue data: " + investment(blchip_portfolio, 1978 to 2017, 100))
+
+for (i <- 2000 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))
+ println("test: " + investment(List("GOOG", "AAPL", "BIDU"), 2000 to i, 100))
}
+
+
+*/
+//1984
+//1992
+}