# HG changeset patch # User Christian Urban # Date 1636339048 0 # Node ID 98a5964d49d1ec77d03b1dbc44994461c0c1b976 # Parent f55742af79ef49bc947ac3037020ba20111e2a44 updated diff -r f55742af79ef -r 98a5964d49d1 pre_testing4/knight1.scala --- a/pre_testing4/knight1.scala Mon Nov 08 02:29:24 2021 +0000 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,147 +0,0 @@ -// Preliminary Part about finding Knight's tours -//=============================================== - - -object CW9a { - -// If you need any auxiliary function, feel free to -// implement it, but do not make any changes to the -// templates below. Also have a look whether the functions -// at the end are of any help. - - - -type Pos = (Int, Int) // a position on a chessboard -type Path = List[Pos] // a path...a list of positions - -//(1) Complete the function that tests whether the position x -// is inside the board and not yet element in the path. - -def is_legal(dim: Int, path: Path, x: Pos) : Boolean = { - if ((!(path.contains(x))) && (x._1 >= 0) && (x._2 >= 0) && (x._1 < dim) && (x._2 < dim)) - true - else false -} - -//(2) Complete the function that calculates for a position x -// all legal onward moves that are not already in the path. -// The moves should be ordered in a "clockwise" manner. - - -def legal_moves(dim: Int, path: Path, x: Pos) : List[Pos] = {//List[Pos] - val changes = List((1,2),(2,1),(2,-1),(1,-2),(-1,-2),(-2,-1),(-2,1),(-1,2)) - val returnList = (for ((y,z) <- changes) yield( - //println(y,z)-2,-1 - if ((is_legal(dim,path,((x._1 + y) , (x._2 + z)))) == true) - Some(x._1 + y , x._2 + z) - else - None - )) - returnList.flatten -} - - -//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))) -//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))) - - -//(3) Complete the two recursive functions below. -// They exhaustively search for knight's tours starting from the -// given path. The first function counts all possible tours, -// and the second collects all tours in a list of paths. - -def count_tours(dim: Int, path: Path) : Int = (dim,path) match {//Int - case (_, Nil) => 0 - case (0, path) => 0 - case (dim, path) => { if (legal_moves(dim,path, path.head).size == 0) - if(path.size < dim*dim) - 0 - else - 1 - else (for (j <- legal_moves(dim,path, path.head)) yield count_tours(dim,j::path)).sum - } -} - -def enum_tours(dim: Int, path: Path) : List[Path] = (dim,path) match { - case (_, Nil) => Nil - case (0, path) => Nil - case (dim, path) => { if (legal_moves(dim,path, path.head).size == 0) - if(path.size < dim*dim) - Nil - else - List(path) - else (for (j <- legal_moves(dim,path, path.head)) yield enum_tours(dim,j::path)).flatten - } - -} - - -//(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. - -//def first(xs: List[Pos], f: Pos => Option[Path]) : Option[Path] = ... - - -// 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 - - -//(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. - - -//def first_tour(dim: Int, path: Path) : Option[Path] = ... - - - - - - -/* Helper functions - - -// 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 -} - -// can be called for example with -// time_needed(count_tours(dim, List((0, 0)))) -// 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 - for (i <- 0 until dim) { - for (j <- 0 until dim) { - print(f"${path.reverse.indexOf((j, dim - i - 1))}%3.0f ") - } - println - } -} - - -*/ - -} diff -r f55742af79ef -r 98a5964d49d1 pre_testing4/knight_test.sh --- a/pre_testing4/knight_test.sh Mon Nov 08 02:29:24 2021 +0000 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,148 +0,0 @@ -#!/bin/bash -set -euo pipefail - -out=${1:-output} - -echo -e "" > $out - -echo -e "Below is the feedback for your submission of knight1.scala" >> $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 - -function scala_compile { - (ulimit -t 30; JAVA_OPTS="-Xmx1g" scala -Xprint:parser "$1" 2> c$out 1> c$out) -} - -# functional tests - -function scala_assert { - (ulimit -t 30; JAVA_OPTS="-Xmx1g" scala -i "$1" -- "$2" -e "" 2> /dev/null 1> /dev/null) -} - -# purity test - -function scala_vars { - (egrep '\bvar\b|\breturn\b|\.par\.|\.par |ListBuffer|AtomicInteger|mutable|util.control|new Array' c$out 2> /dev/null 1> /dev/null) -} - - -# compilation test - -echo -e "knight1.scala runs?" >> $out - -if (scala_compile knight1.scala) -then - echo -e " --> passed" >> $out - tsts=$(( 0 )) -else - echo -e " --> SCALA DID NOT RUN knight1.scala\n" >> $out - tsts=$(( 1 )) -fi - - -# knights1: purity test - -echo -e "knight1.scala does not contain vars, returns etc?" >> $out - -if [ $tsts -eq 0 ] -then - if (scala_vars knight1.scala) - then - echo -e " --> FAIL (make triple-sure your program conforms to the required format)" >> $out - tsts=$(( 1 )) - else - echo -e " --> passed" >> $out - tsts=$(( 0 )) - fi -fi - - - -### knight1 test - -if [ $tsts -eq 0 ] -then - #echo -e "For testing needs to take 10 seconds or less to execute: " >> $out - echo -e " is_legal(8, Nil, (3, 4)) == true " >> $out - echo -e " is_legal(8, List((4, 1), (1, 0)), (4, 1)) == false " >> $out - echo -e " is_legal(2, Nil, (0, 0)) == true" >> $out - - if (scala_assert "knight1.scala" "knight_test1.scala") - then - echo -e " --> success" >> $out - else - echo -e " --> \n ONE TEST FAILED\n" >> $out - fi -fi - -### knight2 test - -if [ $tsts -eq 0 ] -then - #echo -e "For testing needs to take 10 seconds or less to execute: " >> $out - echo -e " legal_moves(8, Nil, (2,2)) == List((3,4), (4,3), (4,1), (3,0), (1,0), (0,1), (0,3), (1,4))" >> $out - echo -e " legal_moves(8, Nil, (7,7)) == List((6,5), (5,6))" >> $out - echo -e " legal_moves(8, List((4,1), (1,0)), (2,2)) == List((3,4), (4,3), (3,0), (0,1), (0,3), (1,4))" >> $out - echo -e " legal_moves(8, List((6,6)), (7,7)) == List((6,5), (5,6))" >> $out - echo -e " legal_moves(1, Nil, (0,0)) == Nil" >> $out - echo -e " legal_moves(2, Nil, (0,0)) == Nil" >> $out - echo -e " legal_moves(3, Nil, (0,0)) == List((1,2), (2,1))" >> $out - - if (scala_assert "knight1.scala" "knight_test2.scala") - then - echo -e " --> success" >> $out - else - echo -e " --> \n ONE TEST FAILED\n" >> $out - fi -fi - - -### knight3 test - -if [ $tsts -eq 0 ] -then - #echo -e "For testing needs to take 10 seconds or less to execute: " >> $out - echo -e " count_tours from every position on the board" >> $out - echo -e " dim = 1: 1" >> $out - echo -e " 2: 0,0,0,0" >> $out - echo -e " 3: 0,0,0,0,0,0,0,0,0" >> $out - echo -e " 4: 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0" >> $out - #echo -e " 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" >> $out - echo -e " enum_tours(5, List((0,0)) ) == 304 and all correct?" >> $out - echo -e " enum_tours(5, List((0,1)) ) == 0" >> $out - echo -e " enum_tours(5, List((0,2)) ) == 56 and all correct?" >> $out - - if (scala_assert "knight1.scala" "knight_test3.scala") - then - echo -e " --> success" >> $out - else - echo -e " --> \n ONE TEST FAILED\n" >> $out - fi -fi - -### knight4 test - -#if [ $tsts -eq 0 ] -#then -# #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 -# -# if (scala_assert "knight1.scala" "knight_test4.scala") -# then -# echo -e " --> success" >> $out -# else -# echo -e " --> \n ONE TEST FAILED\n" >> $out -# fi -#fi - -