# HG changeset patch # User Christian Urban # Date 1481634172 0 # Node ID f8a781322499dfb2f967fa25bd8003dc9c984598 # Parent fd3f8581ce857467a2d8d4f17930c14c288527a4 updated diff -r fd3f8581ce85 -r f8a781322499 cws/cw01.pdf Binary file cws/cw01.pdf has changed diff -r fd3f8581ce85 -r f8a781322499 cws/cw01.tex --- a/cws/cw01.tex Thu Dec 08 12:50:54 2016 +0000 +++ b/cws/cw01.tex Tue Dec 13 13:02:52 2016 +0000 @@ -21,7 +21,8 @@ code! It has a different meaning in Scala, than in Java. Do not use \texttt{var}! This declares a mutable variable. Make sure the functions you submit are defined on the ``top-level'' of Scala, not -inside a class or object. +inside a class or object. Also note that the running time of +each part will be restricted to a maximum of 360 seconds. \subsection*{Disclaimer} diff -r fd3f8581ce85 -r f8a781322499 cws/cw02.pdf Binary file cws/cw02.pdf has changed diff -r fd3f8581ce85 -r f8a781322499 cws/cw02.tex --- a/cws/cw02.tex Thu Dec 08 12:50:54 2016 +0000 +++ b/cws/cw02.tex Tue Dec 13 13:02:52 2016 +0000 @@ -34,7 +34,9 @@ copy any code you need from files \texttt{knight1.scala}, \texttt{knight2.scala} and \texttt{knight3.scala}. Make sure the functions you submit are defined on the ``top-level'' of Scala, not -inside a class or object. +inside a class or object. Also note that the running time of +each part will be restricted to a maximum of 360 seconds. + \subsection*{Disclaimer} @@ -319,19 +321,19 @@ \item[(3a)] Write a function 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 - should come first (in order to be tried out first). + 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 \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 a solution when started in the middle of the board (that is - position $(dimension / 2, dimension / 2)$). + position $(dimension / 2, dimension / 2)$). \hfill[1 Mark] \item[(3c)] Implement a first-tour-heuristic function for boards up to $50\times 50$. It is the same function as in (3b) but searches for \textbf{open} tours. You have to be careful to write a tail-recursive version of the first-tour-heuristic - function otherwise you will get problems with stack-overflows. + function otherwise you will get problems with stack-overflows. \hfill[1 Mark] \end{itemize} \end{document} diff -r fd3f8581ce85 -r f8a781322499 cws/cw03.pdf Binary file cws/cw03.pdf has changed diff -r fd3f8581ce85 -r f8a781322499 cws/cw03.tex --- a/cws/cw03.tex Thu Dec 08 12:50:54 2016 +0000 +++ b/cws/cw03.tex Tue Dec 13 13:02:52 2016 +0000 @@ -20,7 +20,9 @@ code! It has a different meaning in Scala, than in Java. Do not use \texttt{var}! This declares a mutable variable. Make sure the functions you submit are defined on the ``top-level'' of Scala, not -inside a class or object. +inside a class or object. Also note that the running time of +each part will be restricted to a maximum of 360 seconds. + \subsection*{Disclaimer!!!!!!!!} diff -r fd3f8581ce85 -r f8a781322499 marking/knight1b_test.scala --- a/marking/knight1b_test.scala Thu Dec 08 12:50:54 2016 +0000 +++ b/marking/knight1b_test.scala Tue Dec 13 13:02:52 2016 +0000 @@ -4,16 +4,42 @@ import ExecutionContext.Implicits.global import scala.language.postfixOps -lazy val f = Future { - 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_all_tours(dim: Int) = { + for (i <- (0 until dim).toList; + j <- (0 until dim).toList) yield count_tours(dim, List((i, j))) } -Await.result(f, 120 second) +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 +} + + +lazy val f = Future { + assert(count_all_tours(1) == List(1)) + assert(count_all_tours(2) == List(0, 0, 0, 0)) + assert(count_all_tours(3) == List(0, 0, 0, 0, 0, 0, 0, 0, 0)) + assert(count_all_tours(4) == List(0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0)) + assert(count_all_tours(5) == List(304, 0, 56, 0, 304, 0, 56, 0, 56, 0, 56, 0, 64, 0, 56, 0, 56, 0, 56, 0, 304, 0, 56, 0, 304)) + + val ts = enum_tours(5, List((0, 2))) + assert(ts.map(correct_urban(5)).forall(_ == true) == true) + assert(ts.length == 56) +} + +Await.result(f, 360 second) diff -r fd3f8581ce85 -r f8a781322499 marking/knight2b_test.scala --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/marking/knight2b_test.scala Tue Dec 13 13:02:52 2016 +0000 @@ -0,0 +1,38 @@ + +import scala.concurrent._ +import scala.concurrent.duration._ +import ExecutionContext.Implicits.global +import scala.language.postfixOps + + +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 +} + + +lazy val f = Future { + + 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) +} + +Await.result(f, 300 second) diff -r fd3f8581ce85 -r f8a781322499 marking/knight3a_test.scala --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/marking/knight3a_test.scala Tue Dec 13 13:02:52 2016 +0000 @@ -0,0 +1,15 @@ + +import scala.concurrent._ +import scala.concurrent.duration._ +import ExecutionContext.Implicits.global +import scala.language.postfixOps + +lazy val f = Future { + +assert( ordered_moves(8, List((3,4), (3,2)), (1, 3)) == List((0,1), (0,5), (2,1), (2,5))) +assert( ordered_moves(8, List((4,0)), (0,0)) == List((2,1), (1,2))) +assert( ordered_moves(8, List((0,4)), (0,0)) == List((1,2), (2,1))) + +} + +Await.result(f, 120 second) diff -r fd3f8581ce85 -r f8a781322499 marking/mark01b --- a/marking/mark01b Thu Dec 08 12:50:54 2016 +0000 +++ b/marking/mark01b Tue Dec 13 13:02:52 2016 +0000 @@ -39,7 +39,7 @@ if (scala_compile drumb.scala) then - echo " --> success" | tee -a $out + echo " --> yes" | tee -a $out tsts=$(( 0 )) else echo " --> scala did not run drumb.scala" | tee -a $out diff -r fd3f8581ce85 -r f8a781322499 marking/mark02 --- a/marking/mark02 Thu Dec 08 12:50:54 2016 +0000 +++ b/marking/mark02 Tue Dec 13 13:02:52 2016 +0000 @@ -6,7 +6,7 @@ echo "" > $out echo "Below is the feedback and provisional mark for your submission" >> $out -echo "for CW 7. Please note all marks are provisional until" >> $out +echo "for CW 7, Part 1. Please note all marks are provisional until" >> $out echo "ratified by the assessment board -- this is not an official" >> $out echo "results transcript." >> $out echo "" >> $out @@ -33,38 +33,57 @@ # marks for CW2 marks=$(( 0 )) -# var, comments test -echo "knight1.scala contains any vars, returns etc?" | tee -a $out +# knights1: var, comments test + +echo "knight1.scala does not contain vars, returns etc?" | tee -a $out if (scala_vars knight1.scala) then echo " --> fail" | tee -a $out tsts0=$(( 1 )) else - echo " --> success" | tee -a $out + echo " --> yes" | tee -a $out tsts0=$(( 0 )) fi # compilation test -if [ $tsts0 -eq 0 ] + +if [ $tsts0 -eq 0 ] then echo "knight1.scala runs?" | tee -a $out if (scala_compile knight1.scala.bak) then - echo " --> success" | tee -a $out + echo " --> yes" | tee -a $out tsts1=$(( 0 )) else echo " --> scala did not run knight1.scala" | tee -a $out tsts1=$(( 1 )) fi +else + tsts1=$(( 1 )) fi ### knight1a test if [ $tsts1 -eq 0 ] then + echo " is_legal(8, Nil) (3,4) == true " | tee -a $out + echo " is_legal(8, (4,1) (1,0)) (4,1) == false " | tee -a $out + echo " is_legal(2, Nil) (0,0) == true" | tee -a $out + + if (scala_assert "knight1.scala.bak" "../../../marking/knight1c_test.scala") + then + echo " --> success" | tee -a $out + marks=$(( marks + 1 )) + else + echo " --> test failed" | tee -a $out + fi +fi + +if [ $tsts1 -eq 0 ] +then echo " legal_moves(8, Nil, (2,2)) = (3,4), (4,3), (4,1), (3,0), (1,0), (0,1), (0,3), (1,4)" | tee -a $out echo " legal_moves(8, Nil, (7,7)) = (6,5), (5,6)" | tee -a $out echo " legal_moves(8, (4,1), (1,0), (2,2)) = (3,4), (4,3), (3,0), (0,1), (0,3), (1,4)" | tee -a $out @@ -73,7 +92,7 @@ echo " legal_moves(2, Nil, (0,0)) = Nil" | tee -a $out echo " legal_moves(3, Nil, (0,0)) = (1,2), (2,1)" | tee -a $out - if (scala_assert "knight1.scala" "../../../marking/knight1_test.scala") + if (scala_assert "knight1.scala.bak" "../../../marking/knight1_test.scala") then echo " --> success" | tee -a $out marks=$(( marks + 1 )) @@ -82,44 +101,126 @@ fi fi +### knight1b test + +if [ $tsts1 -eq 0 ] +then + echo " all_tours from every position on the board" | tee -a $out + echo " dim = 1: 1" | tee -a $out + echo " 2: 0,0,0,0" | tee -a $out + echo " 3: 0,0,0,0,0,0,0,0,0" | tee -a $out + echo " 4: 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0" | tee -a $out + echo " 5: 304,0,56,0,304,0,56,0,56,0,56,0,64,0,56,0,56,0,56,0,304,0,56,0,304" | tee -a $out + echo " enum_tours(5, (0,2) ) = 56 and all correct?" | tee -a $out + + if (scala_assert "knight1.scala.bak" "../../../marking/knight1b_test.scala") + then + echo " --> success" | tee -a $out + marks=$(( marks + 2 )) + else + echo " --> test failed" | tee -a $out + fi +fi + + + +# knights2: var, comments test + +echo "knight2.scala does not contain vars, returns etc?" | tee -a $out + +if (scala_vars knight2.scala) +then + echo " --> fail" | tee -a $out + tsts0=$(( 1 )) +else + echo " --> yes" | tee -a $out + tsts0=$(( 0 )) +fi + + +# compilation test +if [ $tsts0 -eq 0 ] +then + echo "knight2.scala runs?" | tee -a $out + + if (scala_compile knight2.scala.bak) + then + echo " --> yes" | tee -a $out + tsts1=$(( 0 )) + else + echo " --> scala did not run knight2.scala" | tee -a $out + tsts1=$(( 1 )) + fi +else + tsts1=$(( 1 )) +fi + ### knight2 test -#if [ $tsts -eq 0 ] +if [ $tsts1 -eq 0 ] +then + echo " Let f = (x:(Int, Int)) => if (x._1 > 3) Some(List(x)) else None " | tee -a $out + echo " first((1,0),(2,0),(3,0),(4,0), f) == Some(List((4,0)))" | tee -a $out + echo " first((1,0),(2,0),(3,0), f) == None" | tee -a $out + + if (scala_assert "knight2.scala.bak" "../../../marking/knight2_test.scala") + then + echo " --> success" | tee -a $out + marks=$(( marks + 1 )) + else + echo " --> test failed" | tee -a $out + fi +fi + +### knight2b test + +if [ $tsts1 -eq 0 ] +then + echo " is first_tour(8, (0, 0)) ok? " | tee -a $out + echo " is first_tour(4, (0, 0)) == None " | tee -a $out + + if (scala_assert "knight2.scala.bak" "../../../marking/knight2b_test.scala") + then + echo " --> success" | tee -a $out + marks=$(( marks + 2 )) + else + echo " --> test failed" | tee -a $out + fi +fi + + +# knights3: var, comments test +# +#echo "knight3.scala does not contain vars, returns etc?" | tee -a $out + +#if (scala_vars knight3.scala) #then -# echo " legal_moves(8, Nil, (2,2) = (3,4), (4,3), (4,1), (3,0), (1,0), (0,1), (0,3), (1,4)" | tee -a $out -# echo " List(List(Some(0.07596697626574789), None), " | tee -a $out -# echo " List(Some(-0.152620823795232), None)," | tee -a $out -# echo " List(Some(0.20126676681483952), Some(0.9277165354330709))," | tee -a $out -# echo " List(Some(0.09141762603007778), Some(2.119679764725104)))" | tee -a $out -# -# if (scala_assert "drumb.scala" "../drumb_test2.scala") -# then -# echo " --> success" | tee -a $out -# marks=$(( marks + 1 )) -# else -# echo " --> test failed" | tee -a $out -# fi +# echo " --> fail" | tee -a $out +# tsts0=$(( 1 )) +#else +# echo " --> success" | tee -a $out +# tsts0=$(( 0 )) #fi -### knight3 test -#if [ $tsts -eq 0 ] -#then -# echo " yearly_yield(IBM + BIDU, 04 - 08, 100, 0) - 107).abs <= 2 " | tee -a $out -# echo " yearly_yield(IBM + BIDU, 04 - 08, 100, 1) - 85).abs <= 2 " | tee -a $out -# echo " yearly_yield(IBM + BIDU, 04 - 08, 100, 2) - 156).abs <= 2 " | tee -a $out -# echo " yearly_yield(IBM + BIDU, 04 - 08, 100, 3) - 210).abs <= 2 " | tee -a $out -# echo " investment(List(\"IBM\", \"BIDU\"), 2004 to 2008, 100) - 298).abs <= 10" | tee -a $out -# -# if (scala_assert "drumb.scala" "../drumb_test3.scala") +# compilation test +#if [ $tsts0 -eq 0 ] +#then +# echo "knight3.scala runs?" | tee -a $out +# +# if (scala_compile knight3.scala.bak) # then # echo " --> success" | tee -a $out -# marks=$(( marks + 1 )) +# tsts1=$(( 0 )) # else -# echo " --> test failed" | tee -a $out +# echo " --> scala did not run knight3.scala" | tee -a $out +# tsts1=$(( 1 )) # fi +#else +# tsts1=$(( 1 )) #fi + ## final marks -echo "Overall mark for CW 2" | tee -a $out +echo "Overall mark for CW 2, Part 1 " | tee -a $out echo "$marks" | tee -a $out diff -r fd3f8581ce85 -r f8a781322499 marking/mark02b --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/marking/mark02b Tue Dec 13 13:02:52 2016 +0000 @@ -0,0 +1,74 @@ +#!/bin/bash +set -e + +out=${1:-output} + +echo "" > $out + +echo "Below is the feedback and provisional mark for your submission" >> $out +echo "for CW 7, Part 2. Please note all marks are provisional until" >> $out +echo "ratified by the assessment board -- this is not an official" >> $out +echo "results transcript." >> $out +echo "" >> $out + +function scala_vars { + (egrep 'var|return|ListBuffer|mutable' "$1" 2> /dev/null 1> /dev/null) +} + + +# compilation tests + +function scala_compile { + (scala "$1" 2> /dev/null 1> /dev/null) +} + + +# functional tests + +function scala_assert { + (scala -i "$1" "$2" -e "" 2> /dev/null 1> /dev/null) +} + + +# marks for CW2b +marks=$(( 0 )) + + +# knights3: var, comments test +# +echo "knight3.scala does not contain vars, returns etc?" | tee -a $out + +if (scala_vars knight3.scala) +then + echo " --> fail" | tee -a $out + tsts0=$(( 1 )) +else + echo " --> yes" | tee -a $out + tsts0=$(( 0 )) +fi + + +# compilation test +if [ $tsts0 -eq 0 ] +then + echo "knight3.scala runs?" | tee -a $out + + if (scala_compile knight3.scala.bak) + then + echo " --> yes" | tee -a $out + tsts1=$(( 0 )) + else + echo " --> scala knight3.scala did not run successfully" | tee -a $out + tsts1=$(( 1 )) + fi +else + tsts1=$(( 1 )) +fi + + + + + +## final marks +echo "Overall mark for CW 7, Part 2" | tee -a $out +echo "$marks" | tee -a $out diff -r fd3f8581ce85 -r f8a781322499 progs/knight1_sol.scala --- a/progs/knight1_sol.scala Thu Dec 08 12:50:54 2016 +0000 +++ b/progs/knight1_sol.scala Tue Dec 13 13:02:52 2016 +0000 @@ -20,6 +20,10 @@ 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)) @@ -50,9 +54,9 @@ (for (x <- legal_moves(dim, path, path.head)) yield enum_tours(dim, x::path)).flatten } -def count_all_tours(dim: Int): Int = { - (for (i <- (0 until dim).toList; - j <- (0 until dim).toList) yield count_tours(dim, List((i, j)))).sum +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] = { @@ -60,6 +64,29 @@ 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)))) } diff -r fd3f8581ce85 -r f8a781322499 progs/knight2_sol.scala --- a/progs/knight2_sol.scala Thu Dec 08 12:50:54 2016 +0000 +++ b/progs/knight2_sol.scala Tue Dec 13 13:02:52 2016 +0000 @@ -36,6 +36,10 @@ } } +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) @@ -49,7 +53,36 @@ 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)