# HG changeset patch
# User Christian Urban <urbanc@in.tum.de>
# Date 1572518650 0
# Node ID 12dc251fc47ebb2188504b18172a71f52cbe0410
# Parent  3f34da7a3094d0098461c21cab98d9edf43019ca
updated

diff -r 3f34da7a3094 -r 12dc251fc47e cws/cw03.pdf
Binary file cws/cw03.pdf has changed
diff -r 3f34da7a3094 -r 12dc251fc47e cws/cw03.tex
--- a/cws/cw03.tex	Thu Oct 31 09:49:33 2019 +0000
+++ b/cws/cw03.tex	Thu Oct 31 10:44:10 2019 +0000
@@ -210,7 +210,7 @@
 
 
 
-\subsection*{Part 1 (6 Marks)}
+\subsection*{Preliminary Part (4 Marks)}
 
 You are asked to implement the knight's tour problem such that the
 dimension of the board can be changed.  Therefore most functions will
@@ -296,8 +296,10 @@
   19591828170979904, respectively.}\smallskip
 
 
+\subsection*{Core Part (6 Marks)}
 
-\subsubsection*{Tasks (cont.)}
+
+\subsubsection*{Tasks (file knight1.scala cont.)}
 
 \begin{itemize}
 \item[(4)] Implement a \texttt{first}-function. This function takes a list of
@@ -341,12 +343,10 @@
 sizes of up to $8 \times 8$.
 \bigskip
 
+%%\newpage
 
 
-%%\newpage
-\subsection*{Advanced Part 2 (4 Marks)}
-
-As you should have seen in Part 1, a naive search for tours beyond
+As you should have seen in the earlier parts, 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 \emph{Warnsdorf's
 Rule} that can speed up finding a tour. This heuristic states that a
diff -r 3f34da7a3094 -r 12dc251fc47e mk_jars
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/mk_jars	Thu Oct 31 10:44:10 2019 +0000
@@ -0,0 +1,13 @@
+#!/bin/sh
+set -e
+
+for sd in solutions*; do
+  cd $sd
+  for fl in *.scala; do
+     echo "$fl compiled to ${fl%".scala"}.jar"
+     scalac -d ${fl%".scala"}.jar $fl
+     echo "copied to ../template${sd#"solutions"}"
+     cp ${fl%".scala"}.jar ../template${sd#"solutions"}
+  done
+  cd ..
+done
diff -r 3f34da7a3094 -r 12dc251fc47e solutions1/collatz.jar
Binary file solutions1/collatz.jar has changed
diff -r 3f34da7a3094 -r 12dc251fc47e solutions1/drumb.jar
Binary file solutions1/drumb.jar has changed
diff -r 3f34da7a3094 -r 12dc251fc47e solutions2/danube.jar
Binary file solutions2/danube.jar has changed
diff -r 3f34da7a3094 -r 12dc251fc47e solutions2/docdiff.jar
Binary file solutions2/docdiff.jar has changed
diff -r 3f34da7a3094 -r 12dc251fc47e solutions3/knight1.jar
Binary file solutions3/knight1.jar has changed
diff -r 3f34da7a3094 -r 12dc251fc47e solutions3/knight2.jar
Binary file solutions3/knight2.jar has changed
diff -r 3f34da7a3094 -r 12dc251fc47e solutions3/knight3.jar
Binary file solutions3/knight3.jar has changed
diff -r 3f34da7a3094 -r 12dc251fc47e solutions4/postfix.jar
Binary file solutions4/postfix.jar has changed
diff -r 3f34da7a3094 -r 12dc251fc47e solutions4/postfix2.jar
Binary file solutions4/postfix2.jar has changed
diff -r 3f34da7a3094 -r 12dc251fc47e solutions4/re.jar
Binary file solutions4/re.jar has changed
diff -r 3f34da7a3094 -r 12dc251fc47e solutions5/bf.jar
Binary file solutions5/bf.jar has changed
diff -r 3f34da7a3094 -r 12dc251fc47e solutions5/bfc.jar
Binary file solutions5/bfc.jar has changed
diff -r 3f34da7a3094 -r 12dc251fc47e templates3/knight1.scala
--- a/templates3/knight1.scala	Thu Oct 31 09:49:33 2019 +0000
+++ b/templates3/knight1.scala	Thu Oct 31 10:44:10 2019 +0000
@@ -1,5 +1,8 @@
-// Part 1 about finding Knight's tours
-//=====================================
+// Preliminary Part about finding Knight's tours
+//===============================================
+
+
+object CW8a {
 
 // If you need any auxiliary function, feel free to 
 // implement it, but do not make any changes to the
@@ -26,7 +29,7 @@
 //def legal_moves(dim: Int, path: Path, x: Pos) : List[Pos] = ...
 
 
-//some test cases
+//some testcases
 //
 //assert(legal_moves(8, Nil, (2,2)) == 
 //  List((3,4), (4,3), (4,1), (3,0), (1,0), (0,1), (0,3), (1,4)))
@@ -46,7 +49,7 @@
 //def enum_tours(dim: Int, path: Path) : List[Path] = ...
 
 
-//(5) Implement a first-function that finds the first 
+//(4) Implement a first-function that finds the first 
 //    element, say x, in the list xs where f is not None. 
 //    In that case Return f(x), otherwise None. If possible,
 //    calculate f(x) only once.
@@ -54,16 +57,15 @@
 //def first(xs: List[Pos], f: Pos => Option[Path]) : Option[Path] = ...
 
 
-// test cases
+// testcases
+//
 //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)   // Some(List((4,0)))
 //first(List((1, 0),(2, 0),(3, 0)), foo)          // None
 
 
-
-
-//(6) Implement a function that uses the first-function from (5) for
+//(5) Implement a function that uses the first-function from (5) for
 //    trying out onward moves, and searches recursively for a
 //    knight tour on a dim * dim-board.
 
@@ -92,6 +94,9 @@
 // in order to print out the time that is needed for 
 // running count_tours
 
+
+
+
 // for printing a board
 def print_board(dim: Int, path: Path): Unit = {
   println
@@ -105,3 +110,5 @@
 
 
 */
+
+}
diff -r 3f34da7a3094 -r 12dc251fc47e templates3/knight2.scala
--- a/templates3/knight2.scala	Thu Oct 31 09:49:33 2019 +0000
+++ b/templates3/knight2.scala	Thu Oct 31 10:44:10 2019 +0000
@@ -1,5 +1,9 @@
-// Part 2 about finding a single tour for a board using the Warnsdorf Rule
-//=========================================================================
+// Core Part about finding a single tour for a board using the
+// Warnsdorf Rule
+//==============================================================
+
+object CW8b {
+
 
 // !!! Copy any function you need from file knight1.scala !!!
 //
@@ -34,3 +38,6 @@
 
 //def first_tour_heuristic(dim: Int, path: Path) : Option[Path] = ...
 
+
+
+}
diff -r 3f34da7a3094 -r 12dc251fc47e templates3/knight3.scala
--- a/templates3/knight3.scala	Thu Oct 31 09:49:33 2019 +0000
+++ b/templates3/knight3.scala	Thu Oct 31 10:44:10 2019 +0000
@@ -1,6 +1,7 @@
 // Finding a single tour on a "mega" board
 //=========================================
 
+object CW8c {
 
 // !!! Copy any function you need from file knight1.scala !!!
 // !!! or knight2.scala                                   !!! 
@@ -22,3 +23,4 @@
 
 //def tour_on_mega_board(dim: Int, path: Path) : Option[Path] = ...
 
+}
diff -r 3f34da7a3094 -r 12dc251fc47e testing3/knight2.scala
--- a/testing3/knight2.scala	Thu Oct 31 09:49:33 2019 +0000
+++ b/testing3/knight2.scala	Thu Oct 31 10:44:10 2019 +0000
@@ -1,7 +1,7 @@
 // Part 3 about finding a single tour using the Warnsdorf Rule
 //=============================================================
 
-//object CW8b { // for preparing the jar
+object CW8b {
 
 type Pos = (Int, Int)
 type Path = List[Pos]
@@ -91,4 +91,4 @@
 // will be called with boards up to 30 x 30
 
 
-//}
+}
diff -r 3f34da7a3094 -r 12dc251fc47e testing3/knight2_test.sh
--- a/testing3/knight2_test.sh	Thu Oct 31 09:49:33 2019 +0000
+++ /dev/null	Thu Jan 01 00:00:00 1970 +0000
@@ -1,173 +0,0 @@
-#!/bin/bash
-
-# to make the script fail safely
-set -euo pipefail
-
-
-out=${1:-output}
-
-echo "" > $out
-
-echo -e "Below is the feedback for your submission of CW 8, Core Part." >> $out
-echo -e "" >> $out
-
-
-
-# compilation tests
-
-function scala_compile {
-  (ulimit -t 30; JAVA_OPTS="-Xmx1g" scala "$1" 2>> $out 1>> $out) 
-}
-
-# functional tests
-
-function scala_assert_slow {
-  (ulimit -t 120; JAVA_OPTS="-Xmx1g" scala -i "$1" "-- $2" 2> /dev/null 1> /dev/null)
-}
-
-function scala_assert_thirty {
-  (ulimit -t 30; JAVA_OPTS="-Xmx1g" scala -i "$1" -- "$2" 2> /dev/null 1> /dev/null)
-}
-
-function scala_assert_quick {
-  (ulimit -t 30; JAVA_OPTS="-Xmx1g" scala -i "$1" -- "$2"  2> /dev/null 1> /dev/null)
-}
-
-
-# purity test
-
-function scala_vars {
-   (egrep '\bvar\b|\breturn\b|\.par|ListBuffer|mutable|new Array' "$1" 2> /dev/null 1> /dev/null)
-}
-
-
-
-
-
-
-
-
-# knights2: purity test
-#
-echo -e "knight2.scala does not contain vars, returns, Arrays, ListBuffers etc?" >> $out
-
-
-if (scala_vars knight2.scala)
-then
-  echo -e "  --> fail (make triple-sure your program conforms to the required format)" >> $out    
-  tsts0=$(( 0 ))
-else
-  echo -e "  --> success" >> $out
-  tsts0=$(( 0 )) 
-fi
-
-
-# compilation test
-if  [ $tsts0 -eq 0 ]
-then    
-  echo -e "knight2.scala runs?" >> $out
-
-  if (scala_compile knight2.scala)
-  then
-    echo -e "  --> success" >> $out
-    tsts1=$(( 0 ))
-  else
-    echo -e "  --> SCALA DID NOT RUN KNIGHT2.SCALA\n" >> $out  
-    tsts1=$(( 1 )) 
-  fi
-else
-  tsts1=$(( 1 ))     
-fi
-
-# ordered move test
-
-if [ $tsts1 -eq 0 ]
-then
-  echo -e " ordered_moves(8, List((3,4), (3,2)), (1,3)) == List((0,1), (0,5), (2,1), (2,5))" >> $out
-  echo -e " ordered_moves(8, List((4,0)), (0,0)) == List((2,1), (1,2))" >> $out
-  echo -e " ordered_moves(8, List((0,4)), (0,0)) == List((1,2), (2,1))" >> $out
-  
-  if (scala_assert "knight2.scala" "knight_test6.scala")
-  then
-      echo -e "  --> success" >> $out
-  else
-      echo -e "  --> \n ONE TEST FAILED\n" >> $out  
-  fi
-fi
-
-
-# first-closed-tour test
-
-if [ $tsts1 -eq 0 ]
-then
-  echo -e " first_closed_tour_heuristic(6, List((3,3))) found and correct?" >> $out
-  
-  if (scala_assert "knight2.scala" "knight_test7.scala")
-  then
-      echo -e "  --> success" >> $out
-  else
-      echo -e "  --> \n ONE TEST FAILED\n" >> $out  
-  fi
-fi
-
-
-
-if [ $tsts1 -eq 0 ]
-then
-  echo -e " first_tour_heuristic(8, List((0,0))) found and correct?" >> $out
-  echo -e " first_tour_heuristic(30, List((0,0))) found and correct?" >> $out
-  
-  if (scala_assert "knight2.scala" "knight_test8.scala")
-  then
-      echo -e "  --> success" >> $out
-  else
-      echo -e "  --> \n ONE TEST FAILED\n" >> $out 
-  fi
-fi
-
-
-# knights3: purity test
-#
-echo -e "knight3.scala does not contain vars, returns, Arrays, ListBuffers etc?" >> $out
-
-
-if (scala_vars knight3.scala)
-then
-  echo "  --> test failed" >> $out
-  tsts0=$(( 0 ))
-else
-  echo "  --> success" >> $out
-  tsts0=$(( 0 )) 
-fi
-
-
-# compilation test
-if  [ $tsts0 -eq 0 ]
-then    
-  echo "knight3.scala runs?" >> $out
-
-  if (scala_compile knight3.scala)
-  then
-    echo "  --> success" >> $out
-    tsts1=$(( 0 ))
-  else
-    echo -e "  --> SCALA DID NOT RUN KNIGHT3.SCALA\n" >> $out  
-    tsts1=$(( 1 )) 
-  fi
-else
-  tsts1=$(( 1 ))     
-fi
-
-
-if [ $tsts1 -eq 0 ]
-then
-  echo -e " tour_on_mega_board(70, List((0,0))) found and correct?" >> $out
-  
-  if (scala_assert "knight3.scala" "knight_test9.scala")
-  then
-      echo -e "  --> success" >> $out
-  else
-      echo -e "  --> \n ONE TEST FAILED\n" >> $out 
-  fi
-fi
-
diff -r 3f34da7a3094 -r 12dc251fc47e testing3/knight3.scala
--- a/testing3/knight3.scala	Thu Oct 31 09:49:33 2019 +0000
+++ b/testing3/knight3.scala	Thu Oct 31 10:44:10 2019 +0000
@@ -1,7 +1,7 @@
 // Part 3 about finding a single tour using the Warnsdorf Rule
 //=============================================================
 
-//object CW8c { // for preparing the jar
+object CW8c { 
 
 type Pos = (Int, Int)
 type Path = List[Pos]
@@ -60,4 +60,4 @@
 def tour_on_mega_board(dim: Int, path: Path) =
   time_needed(ttour_on_mega_board(dim: Int, path: Path))
 
-//}
+}
diff -r 3f34da7a3094 -r 12dc251fc47e testing3/knight_test.sh
--- a/testing3/knight_test.sh	Thu Oct 31 09:49:33 2019 +0000
+++ b/testing3/knight_test.sh	Thu Oct 31 10:44:10 2019 +0000
@@ -7,7 +7,13 @@
 
 echo -e "Below is the feedback for your submission of CW 8" >> $out
 echo -e "" >> $out
-
+echo -e "!! Important: !!" >> $out
+echo -e "Because of limitations with our testing infrastructure, we can only" >> $out
+echo -e "let code run for 10 seconds and then have to kill it. This might" >> $out
+echo -e "mean your code is correct, but still marked as Fail. Remember" >> $out
+echo -e "you can test your code on your own machine and benchmark it" >> $out
+echo -e "against the reference implementation." >> $out
+echo -e "" >> $out
 
 # compilation tests
 
@@ -26,7 +32,7 @@
 }
 
 function scala_assert_quick {
-  (ulimit -t 30; JAVA_OPTS="-Xmx1g" scala -i "$1" -- "$2"  2> /dev/null 1> /dev/null)
+  (ulimit -t 30; JAVA_OPTS="-Xmx1g" scala -i "$1" -- "$2" 2> /dev/null 1> /dev/null)
 }
 
 # purity test
@@ -134,7 +140,7 @@
 
 if [ $tsts1 -eq 0 ]
 then
-  echo -e "Takes 10 seconds or less to execute: " >> $out
+  echo -e "For testing needs to take 10 seconds or less to execute: " >> $out
   echo -e " Let f = (x:(Int, Int)) => if (x._1 > 3) Some(List(x)) else None " >> $out
   echo -e "   first(List((1,0),(2,0),(3,0),(4,0)), f) == Some(List((4,0)))" >> $out
   echo -e "   first(List((1,0),(2,0),(3,0)), f) == None" >> $out
@@ -152,7 +158,7 @@
 
 if [ $tsts1 -eq 0 ]
 then
-  echo -e "Takes 10 seconds or less to execute: " >> $out
+  echo -e "For testing needs to take 10 seconds or less to execute: " >> $out
   echo -e " is first_tour(6, List((0, 0))) ok? " >> $out
   echo -e " is first_tour(4, List((0, 0))) == None " >> $out
 
@@ -164,3 +170,139 @@
   fi
 fi
 
+
+echo -e "" >> $out
+echo -e "" >> $out
+
+
+# knights2: purity test
+#
+echo -e "knight2.scala does not contain vars, returns, Arrays, ListBuffers etc?" >> $out
+
+if (scala_vars knight2.scala)
+then
+  echo -e "  --> Fail (make triple-sure your program conforms to the required format)" >> $out    
+  tsts0=$(( 0 ))
+else
+  echo -e "  --> success" >> $out
+  tsts0=$(( 0 )) 
+fi
+
+
+# compilation test
+if  [ $tsts0 -eq 0 ]
+then    
+  echo -e "knight2.scala runs?" >> $out
+
+  if (scala_compile knight2.scala)
+  then
+    echo -e "  --> success" >> $out
+    tsts1=$(( 0 ))
+  else
+    echo -e "  --> SCALA DID NOT RUN KNIGHT2.SCALA\n" >> $out  
+    tsts1=$(( 1 )) 
+  fi
+else
+  tsts1=$(( 1 ))     
+fi
+
+
+# ordered move test
+
+if [ $tsts1 -eq 0 ]
+then
+  echo -e "For testing needs to take 10 seconds or less to execute: " >> $out  
+  echo -e " ordered_moves(8, List((3,4), (3,2)), (1,3)) == List((0,1), (0,5), (2,1), (2,5))" >> $out
+  echo -e " ordered_moves(8, List((4,0)), (0,0)) == List((2,1), (1,2))" >> $out
+  echo -e " ordered_moves(8, List((0,4)), (0,0)) == List((1,2), (2,1))" >> $out
+  
+  if (scala_assert_quick "knight2.scala" "knight_test6.scala")
+  then
+      echo -e "  --> success" >> $out
+  else
+      echo -e "  --> \n ONE TEST FAILED\n" >> $out  
+  fi
+fi
+
+
+# first-closed-tour test
+
+if [ $tsts1 -eq 0 ]
+then
+  echo -e "For testing needs to take 10 seconds or less to execute: " >> $out  
+  echo -e " first_closed_tour_heuristic(6, List((3,3))) found and correct?" >> $out
+  
+  if (scala_assert_quick "knight2.scala" "knight_test7.scala")
+  then
+      echo -e "  --> success" >> $out
+  else
+      echo -e "  --> \n ONE TEST FAILED\n" >> $out  
+  fi
+fi
+
+
+
+if [ $tsts1 -eq 0 ]
+then
+  echo -e "For testing needs to take 10 seconds or less to execute: " >> $out   
+  echo -e " first_tour_heuristic(8, List((0,0))) found and correct?" >> $out
+  echo -e " first_tour_heuristic(30, List((0,0))) found and correct?" >> $out
+  
+  if (scala_assert_quick "knight2.scala" "knight_test8.scala")
+  then
+      echo -e "  --> success" >> $out
+  else
+      echo -e "  --> \n ONE TEST FAILED\n" >> $out 
+  fi
+fi
+
+
+echo -e "" >> $out
+echo -e "" >> $out
+
+# knights3: purity test
+#
+echo -e "knight3.scala does not contain vars, returns, Arrays, ListBuffers etc?" >> $out
+
+
+if (scala_vars knight3.scala)
+then
+  echo "  --> Fail (make triple-sure your program conforms to the required format)xsxs" >> $out
+  tsts0=$(( 0 ))
+else
+  echo "  --> success" >> $out
+  tsts0=$(( 0 )) 
+fi
+
+
+# compilation test
+if  [ $tsts0 -eq 0 ]
+then    
+  echo "knight3.scala runs?" >> $out
+
+  if (scala_compile knight3.scala)
+  then
+    echo "  --> success" >> $out
+    tsts1=$(( 0 ))
+  else
+    echo -e "  --> SCALA DID NOT RUN KNIGHT3.SCALA\n" >> $out  
+    tsts1=$(( 1 )) 
+  fi
+else
+  tsts1=$(( 1 ))     
+fi
+
+
+if [ $tsts1 -eq 0 ]
+then
+  echo -e "For testing needs to take 10 seconds or less to execute: " >> $out  
+  echo -e " tour_on_mega_board(70, List((0,0))) found and correct?" >> $out
+  
+  if (scala_assert_quick "knight3.scala" "knight_test9.scala")
+  then
+      echo -e "  --> success" >> $out
+  else
+      echo -e "  --> \n ONE TEST FAILED\n" >> $out 
+  fi
+fi
+
diff -r 3f34da7a3094 -r 12dc251fc47e testing3/knight_test4.scala
--- a/testing3/knight_test4.scala	Thu Oct 31 09:49:33 2019 +0000
+++ b/testing3/knight_test4.scala	Thu Oct 31 10:44:10 2019 +0000
@@ -1,3 +1,4 @@
+import CW8a._
 
 val f_urban = (x:(Int, Int)) => if (x._1 > 3) Some(List(x)) else None
 
diff -r 3f34da7a3094 -r 12dc251fc47e testing3/knight_test5.scala
--- a/testing3/knight_test5.scala	Thu Oct 31 09:49:33 2019 +0000
+++ b/testing3/knight_test5.scala	Thu Oct 31 10:44:10 2019 +0000
@@ -1,3 +1,5 @@
+import CW8a._
+
 
 //type Pos = (Int, Int)    // a position on a chessboard 
 //type Path = List[Pos]    // a path...a list of positions
diff -r 3f34da7a3094 -r 12dc251fc47e testing3/knight_test6.scala
--- a/testing3/knight_test6.scala	Thu Oct 31 09:49:33 2019 +0000
+++ b/testing3/knight_test6.scala	Thu Oct 31 10:44:10 2019 +0000
@@ -1,4 +1,4 @@
-
+import CW8b._
 
 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)))
diff -r 3f34da7a3094 -r 12dc251fc47e testing3/knight_test7.scala
--- a/testing3/knight_test7.scala	Thu Oct 31 09:49:33 2019 +0000
+++ b/testing3/knight_test7.scala	Thu Oct 31 10:44:10 2019 +0000
@@ -1,3 +1,4 @@
+import CW8b._
 
 //type Pos = (Int, Int)
 //type Path = List[Pos]
diff -r 3f34da7a3094 -r 12dc251fc47e testing3/knight_test8.scala
--- a/testing3/knight_test8.scala	Thu Oct 31 09:49:33 2019 +0000
+++ b/testing3/knight_test8.scala	Thu Oct 31 10:44:10 2019 +0000
@@ -1,3 +1,5 @@
+import CW8b._
+
 
 //type Pos = (Int, Int)
 //type Path = List[Pos]
diff -r 3f34da7a3094 -r 12dc251fc47e testing3/knight_test9.scala
--- a/testing3/knight_test9.scala	Thu Oct 31 09:49:33 2019 +0000
+++ b/testing3/knight_test9.scala	Thu Oct 31 10:44:10 2019 +0000
@@ -1,3 +1,4 @@
+import CW8c._
 
 //type Pos = (Int, Int)
 //type Path = List[Pos]