Binary file cws/cw02.pdf has changed
--- a/cws/cw02.tex Wed Jul 24 15:18:44 2019 +0100
+++ b/cws/cw02.tex Thu Aug 01 09:48:34 2019 +0100
@@ -1,3 +1,4 @@
+% !TEX program = xelatex
\documentclass{article}
\usepackage{../style}
\usepackage{disclaimer}
@@ -13,8 +14,8 @@
\mbox{}\hfill\textit{ --- Frederick P.~Brooks (author of The Mythical Man-Month)}\bigskip
\noindent
-This coursework is worth 10\%. The first and second part are due
-on 22 November at 11pm; the third, more advanced part, is due on 20
+This coursework is worth 10\%. The basic part is due
+on 22 November at 11pm; the main part is due on 20
December at 11pm. You are asked to implement Scala programs for
measuring similarity in texts, and for recommending movies
according to a ratings list. Note the second part might include
@@ -34,8 +35,9 @@
Like the C++ assignments, the Scala assignments will work like this: you
push your files to GitHub and receive (after sometimes a long delay) some
automated feedback. In the end we take a snapshot of the submitted files and
-apply an automated marking script to them.
+apply an automated marking script to them.\medskip
+\noindent
In addition, the Scala assignments come with a reference
implementation in form of a \texttt{jar}-file. This allows you to run
any test cases on your own computer. For example you can call Scala on
@@ -82,7 +84,7 @@
\newpage
-\subsection*{Part 1 (4 Marks, file docdiff.scala)}
+\subsection*{Basic Part (4 Marks, file docdiff.scala)}
It seems source code plagiarism---stealing and submitting someone
else's code---is a serious problem at other
@@ -167,7 +169,7 @@
\end{itemize}\bigskip
-\subsection*{Part 2 (2 Marks, file danube.scala)}
+\subsection*{Main Part (2 Marks, file danube.scala)}
You are creating Danube.co.uk which you hope will be the next big thing
in online movie renting. You know that you can save money by
@@ -229,14 +231,14 @@
ratings below 4 and returns a list of (userID, movieID) pairs. The
\pcode{process_movies} function returns a list of (movieID, title) pairs.\\
\mbox{}\hfill [1 Mark]
-\end{itemize}
-
-
-\subsection*{Part 3 (4 Marks, file danube.scala)}
-
-\subsection*{Tasks}
-
-\begin{itemize}
+%\end{itemize}
+%
+%
+%\subsection*{Part 3 (4 Marks, file danube.scala)}
+%
+%\subsection*{Tasks}
+%
+%\begin{itemize}
\item[(3)] Implement a kind of grouping function that calculates a Map
containing the userIDs and all the corresponding recommendations for
this user (list of movieIDs). This should be implemented in a
@@ -285,7 +287,7 @@
\mbox{}\hfill [1 Mark]
\end{itemize}
-\end{document}
+\end{document}
%%% Local Variables:
%%% mode: latex
Binary file cws/cw05.pdf has changed
--- a/cws/cw05.tex Wed Jul 24 15:18:44 2019 +0100
+++ b/cws/cw05.tex Thu Aug 01 09:48:34 2019 +0100
@@ -27,15 +27,17 @@
maximum of 30 seconds on my laptop.
\DISCLAIMER{}
+\newpage
\subsection*{Reference Implementation}
-As usual, this Scala assignment comes with a reference implementation in form of
-two \texttt{jar}-files. You can download them from KEATS. They allow you to run any
-test cases on your own computer. For example you can call Scala on the command line with the
-option \texttt{-cp bf.jar} and then query any function from the
-\texttt{bf.scala} template file. You have to
-prefix the calls with \texttt{CW10a} and \texttt{CW10b}, respectively. For example
+As usual, this Scala assignment comes with a reference implementation in
+form of two \texttt{jar}-files. You can download them from KEATS. They
+allow you to run any test cases on your own computer. For example you
+can call Scala on the command line with the option \texttt{-cp bf.jar}
+and then query any function from the \texttt{bf.scala} template file.
+You have to prefix the calls with \texttt{CW10a} and \texttt{CW10b},
+respectively. For example
\begin{lstlisting}[language={},xleftmargin=1mm,numbers=none,basicstyle=\ttfamily\small]
@@ -76,7 +78,7 @@
* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *
\end{lstlisting}%$
-
+\newpage
\subsection*{Part 1 (6 Marks)}
@@ -106,7 +108,7 @@
\begin{center}
\url{https://www.microsoft.com/en-us/p/brainf-ck/9nblgggzhvq5}
-\end{center}
+\end{center} \bigskip
\noindent
@@ -155,7 +157,7 @@
memory location \texttt{0}, and at \texttt{2} it stores \texttt{3}. The
convention is that if we query the memory at a location that is
\emph{not} defined in the \texttt{Map}, we return \texttt{0}. Write
- a function, \texttt{sread}, that takes a memory (a \texttt{Map}) and
+ a `safe-read' function, \texttt{sread}, that takes a memory (a \texttt{Map}) and
a memory pointer (an \texttt{Int}) as arguments, and `safely' reads the
corresponding memory location. If the \texttt{Map} is not defined at
the memory pointer, \texttt{sread} returns \texttt{0}.
@@ -325,7 +327,7 @@
\end{figure}
\end{itemize}\bigskip
-\newpage
+%%\newpage
\subsection*{Part 2 (4 Marks)}
--- a/marking1/drumb_test.sh Wed Jul 24 15:18:44 2019 +0100
+++ b/marking1/drumb_test.sh Thu Aug 01 09:48:34 2019 +0100
@@ -98,7 +98,7 @@
if [ $tsts -eq 0 ]
then
echo " get_first_price(\"GOOG\", 1980) == None" | tee -a $out
- echo " get_first_price(\"GOOG\", 2010) == Some(311.349976)" | tee -a $out
+ echo " get_first_price(\"GOOG\", 2010) == Some(312.204773)" | tee -a $out
if (scala_assert "drumb.scala" "drumb_test2.scala")
then
@@ -118,9 +118,9 @@
echo " List(Some(12.241)), List(Some(38.188)))" | tee -a $out
echo " " | tee -a $out
echo " get_prices(List(\"GOOG\", \"AAPL\"), 2010 to 2012) ==" | tee -a $out
- echo " List(List(Some(311.349976), Some(20.544939))," | tee -a $out
- echo " List(Some(300.222351), Some(31.638695))," | tee -a $out
- echo " List(Some(330.555054), Some(39.478039)))" | tee -a $out
+ echo " List(List(Some(312.204773), Some(26.782711))," | tee -a $out
+ echo " List(Some(301.0466), Some(41.244694))," | tee -a $out
+ echo " List(Some(331.462585), Some(51.464207)))" | tee -a $out
if (scala_assert "drumb.scala" "drumb_test3.scala")
then
@@ -155,8 +155,8 @@
if [ $tsts -eq 0 ]
then
echo -e " get_deltas(get_prices(List(\"GOOG\", \"AAPL\"), 2010 to 2012)) == " | tee -a $out
- echo -e " List(List(Some(-0.03573992567129673), Some(0.539975124774038)), " | tee -a $out
- echo -e " List(Some(0.10103412653643493), Some(0.24777709700099845)))" | tee -a $out
+ echo -e " List(List(Some(-0.03573991804411003), Some(0.539974575389325)), " | tee -a $out
+ echo -e " List(Some(0.10103414222249969), Some(0.24777764141006836)))" | tee -a $out
echo -e "" | tee -a $out
echo -e " get_deltas(get_prices(List(\"BIDU\"), 2004 to 2008)) == " | tee -a $out
echo -e " List(List(None), List(None), " | tee -a $out
@@ -203,7 +203,7 @@
echo -e " investment(List(\"GOOG\", \"AAPL\", \"BIDU\"), 2000 to 2005, 100) == 113" | tee -a $out
echo -e " investment(List(\"GOOG\", \"AAPL\", \"BIDU\"), 2000 to 2006, 100) == 254" | tee -a $out
echo -e " investment(List(\"GOOG\", \"AAPL\", \"BIDU\"), 2000 to 2007, 100) == 349" | tee -a $out
- echo -e " investment(List(\"GOOG\", \"AAPL\", \"BIDU\"), 1990 to 2017, 100) == 83061" | tee -a $out
+ echo -e " investment(List(\"GOOG\", \"AAPL\", \"BIDU\"), 1990 to 2017, 100) == 11504" | tee -a $out
if (scala_assert "drumb.scala" "drumb_test7.scala")
--- a/marking1/drumb_test2.scala Wed Jul 24 15:18:44 2019 +0100
+++ b/marking1/drumb_test2.scala Thu Aug 01 09:48:34 2019 +0100
@@ -1,5 +1,12 @@
-
-assert(get_first_price("GOOG", 1980) == None)
+def myassert(cond : => Boolean) = {
+ try {
+ assert(cond)
+ } catch {
+ case _ : Throwable => System.exit(1)
+ }
+}
-assert(get_first_price("GOOG", 2010) == Some(311.349976))
+myassert(get_first_price("GOOG", 1980) == None)
+myassert(get_first_price("GOOG", 2010) == Some(312.204773))
+
--- a/marking1/drumb_test3.scala Wed Jul 24 15:18:44 2019 +0100
+++ b/marking1/drumb_test3.scala Thu Aug 01 09:48:34 2019 +0100
@@ -1,4 +1,17 @@
-assert(get_prices(List("GOOG", "AAPL"), 2010 to 2012) ==
- List(List(Some(311.349976), Some(20.544939)),
- List(Some(300.222351), Some(31.638695)),
- List(Some(330.555054), Some(39.478039))))
+def myassert(cond : => Boolean) = {
+ try {
+ assert(cond)
+ } catch {
+ case _ : Throwable => System.exit(1)
+ }
+}
+
+myassert(get_prices(List("BIDU"), 2004 to 2008) ==
+ List(List(None), List(None), List(Some(6.35)),
+ List(Some(12.241)), List(Some(38.188))))
+
+
+myassert(get_prices(List("GOOG", "AAPL"), 2010 to 2012) ==
+ List(List(Some(312.204773), Some(26.782711)),
+ List(Some(301.0466), Some(41.244694)),
+ List(Some(331.462585), Some(51.464207))))
--- a/marking1/drumb_test4.scala Wed Jul 24 15:18:44 2019 +0100
+++ b/marking1/drumb_test4.scala Thu Aug 01 09:48:34 2019 +0100
@@ -1,6 +1,12 @@
-
+def myassert(cond : => Boolean) = {
+ try {
+ assert(cond)
+ } catch {
+ case _ : Throwable => System.exit(1)
+ }
+}
-assert(get_delta(None, None) == None)
-assert(get_delta(Some(50.0), None) == None)
-assert(get_delta(None, Some(100.0)) == None)
-assert(get_delta(Some(50.0), Some(100.0)) == Some(1.0))
+myassert(get_delta(None, None) == None)
+myassert(get_delta(Some(50.0), None) == None)
+myassert(get_delta(None, Some(100.0)) == None)
+myassert(get_delta(Some(50.0), Some(100.0)) == Some(1.0))
--- a/marking1/drumb_test5.scala Wed Jul 24 15:18:44 2019 +0100
+++ b/marking1/drumb_test5.scala Thu Aug 01 09:48:34 2019 +0100
@@ -1,12 +1,19 @@
+def myassert(cond : => Boolean) = {
+ try {
+ assert(cond)
+ } catch {
+ case _ : Throwable => System.exit(1)
+ }
+}
// get_prices(List("GOOG", "AAPL"), 2010 to 2012)
-val urban_prices = List(List(Some(311.349976), Some(20.544939)),
- List(Some(300.222351), Some(31.638695)),
- List(Some(330.555054), Some(39.478039)))
+val urban_prices = List(List(Some(312.204773), Some(26.782711)),
+ List(Some(301.0466), Some(41.244694)),
+ List(Some(331.462585), Some(51.464207)))
-assert(get_deltas(urban_prices) == List(List(Some(-0.03573992567129673), Some(0.539975124774038)),
- List(Some(0.10103412653643493), Some(0.24777709700099845))))
+myassert(get_deltas(urban_prices) == List(List(Some(-0.03573991804411003), Some(0.539974575389325)),
+ List(Some(0.10103414222249969), Some(0.24777764141006836))))
//get_prices(List("BIDU"), 2004 to 2008)
@@ -15,6 +22,6 @@
List(Some(38.188)))
-assert(get_deltas(urban_prices2) == List(List(None), List(None),
+myassert(get_deltas(urban_prices2) == List(List(None), List(None),
List(Some(0.9277165354330709)),
List(Some(2.119679764725104))))
--- a/marking1/drumb_test6.scala Wed Jul 24 15:18:44 2019 +0100
+++ b/marking1/drumb_test6.scala Thu Aug 01 09:48:34 2019 +0100
@@ -1,9 +1,18 @@
//val urban_deltas = get_deltas(get_prices(List("GOOG", "AAPL"), 2010 to 2012))
-val ds_urban = List(List(Some(-0.03573992567129673), Some(0.539975124774038)),
- List(Some(0.10103412653643493), Some(0.24777709700099845)))
+def myassert(cond : => Boolean) = {
+ try {
+ assert(cond)
+ } catch {
+ case _ : Throwable => System.exit(1)
+ }
+}
+
+
+val ds_urban = List(List(Some(-0.03573991804411003), Some(0.539974575389325)),
+ List(Some(0.10103414222249969), Some(0.24777764141006836)))
-assert(yearly_yield(ds_urban, 100, 0) == 125)
-assert(yearly_yield(ds_urban, 100, 1) == 117)
+myassert(yearly_yield(ds_urban, 100, 0) == 125)
+myassert(yearly_yield(ds_urban, 100, 1) == 117)
--- a/marking1/drumb_test7.scala Wed Jul 24 15:18:44 2019 +0100
+++ b/marking1/drumb_test7.scala Thu Aug 01 09:48:34 2019 +0100
@@ -1,10 +1,18 @@
+def myassert(cond : => Boolean) = {
+ try {
+ assert(cond)
+ } catch {
+ case _ : Throwable => System.exit(1)
+ }
+}
-assert(investment(List("GOOG", "AAPL", "BIDU"), 2000 to 2000, 100) == 100)
-assert(investment(List("GOOG", "AAPL", "BIDU"), 2000 to 2001, 100) == 27)
-assert(investment(List("GOOG", "AAPL", "BIDU"), 2000 to 2002, 100) == 42)
-assert(investment(List("GOOG", "AAPL", "BIDU"), 2000 to 2003, 100) == 27)
-assert(investment(List("GOOG", "AAPL", "BIDU"), 2000 to 2004, 100) == 38)
-assert(investment(List("GOOG", "AAPL", "BIDU"), 2000 to 2005, 100) == 113)
-assert(investment(List("GOOG", "AAPL", "BIDU"), 2000 to 2006, 100) == 254)
-assert(investment(List("GOOG", "AAPL", "BIDU"), 2000 to 2007, 100) == 349)
-assert(investment(List("GOOG", "AAPL", "BIDU"), 1990 to 2017, 100) == 83061)
+
+myassert(investment(List("GOOG", "AAPL", "BIDU"), 2000 to 2000, 100) == 100)
+myassert(investment(List("GOOG", "AAPL", "BIDU"), 2000 to 2001, 100) == 27)
+myassert(investment(List("GOOG", "AAPL", "BIDU"), 2000 to 2002, 100) == 42)
+myassert(investment(List("GOOG", "AAPL", "BIDU"), 2000 to 2003, 100) == 27)
+myassert(investment(List("GOOG", "AAPL", "BIDU"), 2000 to 2004, 100) == 38)
+myassert(investment(List("GOOG", "AAPL", "BIDU"), 2000 to 2005, 100) == 113)
+myassert(investment(List("GOOG", "AAPL", "BIDU"), 2000 to 2006, 100) == 254)
+myassert(investment(List("GOOG", "AAPL", "BIDU"), 2000 to 2007, 100) == 349)
+myassert(investment(List("GOOG", "AAPL", "BIDU"), 1990 to 2017, 100) == 11504)
--- a/progs/lecture1.scala Wed Jul 24 15:18:44 2019 +0100
+++ b/progs/lecture1.scala Thu Aug 01 09:48:34 2019 +0100
@@ -37,12 +37,13 @@
List(1,2,3,1)
Set(1,2,3,1)
+// ranges
1 to 10
(1 to 10).toList
(1 until 10).toList
-// an element in a list
+// picking an element in a list
val lst = List(1, 2, 3, 1)
lst(0)
lst(2)
@@ -52,8 +53,8 @@
1 :: 2 :: 3 :: Nil
List(1, 2, 3) ::: List(4, 5, 6)
-// Equality is structural
-//========================
+// Equality in Scala is structural
+//=================================
val a = "Dave"
val b = "Dave"
@@ -76,13 +77,16 @@
println("test")
-val tst = "This is a " + "test\n"
+val tst = "This is a " ++ "test"
+print(tst)
println(tst)
val lst = List(1,2,3,1)
println(lst.toString)
+
+println(lst.mkString)
println(lst.mkString(","))
println(lst.mkString(", "))
@@ -90,6 +94,9 @@
// some methods take more than one argument
println(lst.mkString("{", ",", "}"))
+// (in this case .mkString can take no, one,
+// or three arguments...this has to do with
+// default arguments)
// Conversion methods
@@ -97,6 +104,7 @@
List(1,2,3,1).toString
List(1,2,3,1).toSet
+
"hello".toList.tail
1.toDouble
@@ -119,27 +127,31 @@
"abcdefg".startsWith("abc")
-// Types (slide)
-//===============
+// Types (see slide)
+//===================
/* Scala is a strongly typed language
- * some base types
+ * base types
Int, Long, BigInt, Float, Double
String, Char
- Boolean
+ Boolean...
- * some compound types
+ * compound types
- List[Int],
+ List[Int]
Set[Double]
Pairs: (Int, String)
List[(BigInt, String)]
Option[Int]
+
+ * user-defined types (later)
+
*/
+// you can make the type of a value explicit
val name: String = "leo"
@@ -153,6 +165,7 @@
// required: Double
// math.sqrt("64")
+
// Pairs/Tuples
//==============
@@ -174,7 +187,11 @@
def square(x: Int) : Int = x * x
def str(x: Int) : String = x.toString
+
+incr(3)
+double(4)
square(6)
+str(3)
// The general scheme for a function: you have to give a type
@@ -195,12 +212,21 @@
else n + n
}
+def another_silly(x: Int, y: String) : String = {
+ if (x <= 12) y
+ else x.toString
+}
+
+another_silly(2, "two")
+another_silly(12, "twelf")
+another_silly(20, "twenty")
+
// If-Conditionals
//=================
// - Scala does not have a then-keyword
-// - both if-else branches need to be present
+// - !both if-else branches need to be present!
def fact(n: Int) : Int =
if (n == 0) 1 else n * fact(n - 1)
@@ -250,7 +276,7 @@
// Option type
//=============
-//in Java if something unusually happens, you return null
+//in Java if something unusually happens, you return null or something
//
//in Scala you use Options instead
// - if the value is present, you use Some(value)
@@ -269,7 +295,7 @@
import scala.util._
import io.Source
-val my_url = "https://nms.imperial.ac.uk/christian.urban/"
+val my_url = "https://nms.kcl.ac.uk/christian.urban/"
Source.fromURL(my_url).mkString
@@ -299,7 +325,7 @@
Try(Some(Source.fromFile(name).getLines.toList)).getOrElse(None)
get_contents("text.txt")
-
+get_contents("test.txt")
// String Interpolations
@@ -346,6 +372,8 @@
m <- (1 to 10).toList) yield m * n
+// you can assign the result of a for-comprehension
+// to a value
val mult_table =
for (n <- (1 to 10).toList;
m <- (1 to 10).toList) yield m * n
@@ -426,10 +454,11 @@
for (c <- lst) println(c)
// Aside: concurrency
-// (ONLY WORKS OUT-OF-THE-BOX IN SCALA 2.11.8, not in SCALA 2.12)
-// (would need to have this wrapped into a function, or
-// REPL called with scala -Yrepl-class-based)
+// (scala <<..parallel_collections...>> -Yrepl-class-based)
for (n <- (1 to 10)) println(n)
+
+import scala.collection.parallel.CollectionConverters._
+
for (n <- (1 to 10).par) println(n)
@@ -456,6 +485,7 @@
// Q: Count how many elements are in the intersections of two sets?
+// A; IMPROPER WAY (mutable counter)
def count_intersection(A: Set[Int], B: Set[Int]) : Int = {
var count = 0
--- a/progs/lecture2.scala Wed Jul 24 15:18:44 2019 +0100
+++ b/progs/lecture2.scala Thu Aug 01 09:48:34 2019 +0100
@@ -18,9 +18,7 @@
time_needed(10, for (n <- list) yield n + 42)
time_needed(10, for (n <- list.par) yield n + 42)
-// (ONLY WORKS OUT-OF-THE-BOX IN SCALA 2.11.8, not in SCALA 2.12)
-// (would need to have this wrapped into a function, or
-// REPL called with scala -Yrepl-class-based)
+// (needs a library and 'magic' option -Yrepl-class-based)
// Just for Fun: Mutable vs Immutable
@@ -124,7 +122,8 @@
lst.map(square)
-// this is actually what for is defined at in Scala
+// this is actually how for-comprehensions
+// defined as in Scala
lst.map(n => square(n))
for (n <- lst) yield square(n)
@@ -227,12 +226,13 @@
-// Option type
-//=============
+// Option type (again)
+//=====================
-//in Java if something unusually happens, you return null;
+// remember, in Java if something unusually happens,
+// you return null;
//
-//in Scala you use Option
+// in Scala you use Option
// - if the value is present, you use Some(value)
// - if no value is present, you use None
@@ -295,7 +295,7 @@
val lst = List("12345", "foo", "5432", "bar", "x21", "456")
for (x <- lst) yield get_me_an_int(x)
-// summing all the numbers
+// summing up all the numbers
lst.map(get_me_an_int).flatten.sum
lst.map(get_me_an_int).flatten.sum
@@ -419,7 +419,7 @@
fav_colour(Green)
-// ... a bit more useful: Roman Numerals
+// ... a tiny bit more useful: Roman Numerals
abstract class RomanDigit
case object I extends RomanDigit
@@ -434,6 +434,7 @@
List(X,I)
+/*
I -> 1
II -> 2
III -> 3
@@ -444,6 +445,7 @@
VIII -> 8
IX -> 9
X -> X
+*/
def RomanNumeral2Int(rs: RomanNumeral): Int = rs match {
case Nil => 0
@@ -510,10 +512,8 @@
println(people.sortWith(superior).mkString("\n"))
-print("123\\n456")
-
-// Tail recursion
+// Tail Recursion
//================
@@ -565,6 +565,7 @@
val http_pattern = """"https?://[^"]*"""".r
val email_pattern = """([a-z0-9_\.-]+)@([\da-z\.-]+)\.([a-z\.]{2,6})""".r
+//test case:
//email_pattern.findAllIn
// ("foo bla christian@kcl.ac.uk 1234567").toList
@@ -617,54 +618,57 @@
|..7.9.41.""".stripMargin.replaceAll("\\n", "")
type Pos = (Int, Int)
-val EmptyValue = '.'
-val MaxValue = 9
+val emptyValue = '.'
+val maxValue = 9
val allValues = "123456789".toList
val indexes = (0 to 8).toList
+def empty(game: String) = game.indexOf(emptyValue)
+def isDone(game: String) = empty(game) == -1
+def emptyPosition(game: String) : Pos =
+ (empty(game) % maxValue, empty(game) / maxValue)
-def empty(game: String) = game.indexOf(EmptyValue)
-def isDone(game: String) = empty(game) == -1
-def emptyPosition(game: String) = (empty(game) % MaxValue, empty(game) / MaxValue)
-
-
-def get_row(game: String, y: Int) = indexes.map(col => game(y * MaxValue + col))
-def get_col(game: String, x: Int) = indexes.map(row => game(x + row * MaxValue))
+def get_row(game: String, y: Int) = indexes.map(col => game(y * maxValue + col))
+def get_col(game: String, x: Int) = indexes.map(row => game(x + row * maxValue))
def get_box(game: String, pos: Pos): List[Char] = {
def base(p: Int): Int = (p / 3) * 3
val x0 = base(pos._1)
val y0 = base(pos._2)
- val ys = (y0 until y0 + 3).toList
- (x0 until x0 + 3).toList.flatMap(x => ys.map(y => game(x + y * MaxValue)))
-}
+ for (x <- (x0 until x0 + 3).toList;
+ y <- (y0 until y0 + 3).toList) yield game(x + y * maxValue)
+}
//get_row(game0, 0)
//get_row(game0, 1)
//get_box(game0, (3,1))
-def update(game: String, pos: Int, value: Char): String = game.updated(pos, value)
+def update(game: String, pos: Int, value: Char): String =
+ game.updated(pos, value)
def toAvoid(game: String, pos: Pos): List[Char] =
(get_col(game, pos._1) ++ get_row(game, pos._2) ++ get_box(game, pos))
-def candidates(game: String, pos: Pos): List[Char] = allValues diff toAvoid(game,pos)
+def candidates(game: String, pos: Pos): List[Char] =
+ allValues.diff(toAvoid(game, pos))
-//candidates(game0, (0,0))
+//candidates(game0, (0, 0))
-def pretty(game: String): String = "\n" + (game sliding (MaxValue, MaxValue) mkString "\n")
+def pretty(game: String): String =
+ "\n" ++ (game.sliding(maxValue, maxValue).mkString("\n"))
def search(game: String): List[String] = {
if (isDone(game)) List(game)
else
- candidates(game, emptyPosition(game)).map(c => search(update(game, empty(game), c))).toList.flatten
+ candidates(game, emptyPosition(game)).
+ map(c => search(update(game, empty(game), c))).flatten
}
-
+// an easy game
val game1 = """23.915...
|...2..54.
|6.7......
@@ -676,7 +680,7 @@
|...329..1""".stripMargin.replaceAll("\\n", "")
-// game that is in the hard category
+// a game that is in the sligtly harder category
val game2 = """8........
|..36.....
|.7..9.2..
@@ -687,7 +691,7 @@
|..85...1.
|.9....4..""".stripMargin.replaceAll("\\n", "")
-// game with multiple solutions
+// a game with multiple solutions
val game3 = """.8...9743
|.5...8.1.
|.1.......
@@ -707,7 +711,7 @@
val start = System.nanoTime()
for (j <- 1 to i) code
val end = System.nanoTime()
- ((end - start) / i / 1.0e9) + " secs"
+ s"${(end - start) / i / 1.0e9} secs"
}
search(game2).map(pretty)
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/progs/sudoku.scala Thu Aug 01 09:48:34 2019 +0100
@@ -0,0 +1,236 @@
+// Sudoku
+//========
+
+object Sudoku extends App {
+
+import scala.collection.parallel.CollectionConverters._
+
+type Pos = (Int, Int)
+val emptyValue = '.'
+val maxValue = 9
+
+val allValues = "123456789".toList
+val indexes = (0 to 8).toList
+
+
+def empty(game: String) = game.indexOf(emptyValue)
+def isDone(game: String) = empty(game) == -1
+def emptyPosition(game: String) : Pos =
+ (empty(game) % maxValue, empty(game) / maxValue)
+
+
+def get_row(game: String, y: Int) = indexes.map(col => game(y * maxValue + col))
+def get_col(game: String, x: Int) = indexes.map(row => game(x + row * maxValue))
+
+def get_box(game: String, pos: Pos): List[Char] = {
+ def base(p: Int): Int = (p / 3) * 3
+ val x0 = base(pos._1)
+ val y0 = base(pos._2)
+ for (x <- (x0 until x0 + 3).toList;
+ y <- (y0 until y0 + 3).toList) yield game(x + y * maxValue)
+}
+
+
+//get_row(game0, 0)
+//get_row(game0, 1)
+//get_box(game0, (3,1))
+
+def update(game: String, pos: Int, value: Char): String =
+ game.updated(pos, value)
+
+def toAvoid(game: String, pos: Pos): List[Char] =
+ (get_col(game, pos._1) ++ get_row(game, pos._2) ++ get_box(game, pos))
+
+def candidates(game: String, pos: Pos): List[Char] =
+ allValues.diff(toAvoid(game, pos))
+
+//candidates(game0, (0, 0))
+
+//def pretty(game: String): String =
+// "\n" ++ (game.sliding(maxValue, maxValue).mkString("\n"))
+
+def search(game: String): List[String] = {
+ if (isDone(game)) List(game)
+ else
+ candidates(game, emptyPosition(game)).par.
+ map(c => search(update(game, empty(game), c))).toList.flatten
+}
+
+// two easy games
+val game0 = """.14.6.3..
+ |62...4..9
+ |.8..5.6..
+ |.6.2....3
+ |.7..1..5.
+ |5....9.6.
+ |..6.2..3.
+ |1..5...92
+ |..7.9.41.""".stripMargin.replaceAll("\\n", "")
+
+val game1 = """23.915...
+ |...2..54.
+ |6.7......
+ |..1.....9
+ |89.5.3.17
+ |5.....6..
+ |......9.5
+ |.16..7...
+ |...329..1""".stripMargin.replaceAll("\\n", "")
+
+
+// a game that is in the sligtly harder category
+val game2 = """8........
+ |..36.....
+ |.7..9.2..
+ |.5...7...
+ |....457..
+ |...1...3.
+ |..1....68
+ |..85...1.
+ |.9....4..""".stripMargin.replaceAll("\\n", "")
+
+// a game with multiple solutions
+val game3 = """.8...9743
+ |.5...8.1.
+ |.1.......
+ |8....5...
+ |...8.4...
+ |...3....6
+ |.......7.
+ |.3.5...8.
+ |9724...5.""".stripMargin.replaceAll("\\n", "")
+
+val hard_games =
+ List("85...24..72......9..4.........1.7..23.5...9...4...........8..7..17..........36.4.",
+ "..53.....8......2..7..1.5..4....53...1..7...6..32...8..6.5....9..4....3......97..",
+ "12..4......5.69.1...9...5.........7.7...52.9..3......2.9.6...5.4..9..8.1..3...9.4",
+ "...57..3.1......2.7...234......8...4..7..4...49....6.5.42...3.....7..9....18.....",
+ "7..1523........92....3.....1....47.8.......6............9...5.6.4.9.7...8....6.1.",
+ "1....7.9..3..2...8..96..5....53..9...1..8...26....4...3......1..4......7..7...3..",
+ "1...34.8....8..5....4.6..21.18......3..1.2..6......81.52..7.9....6..9....9.64...2",
+ "...92......68.3...19..7...623..4.1....1...7....8.3..297...8..91...5.72......64...",
+ ".6.5.4.3.1...9...8.........9...5...6.4.6.2.7.7...4...5.........4...8...1.5.2.3.4.",
+ "7.....4...2..7..8...3..8.799..5..3...6..2..9...1.97..6...3..9...3..4..6...9..1.35",
+ "....7..2.8.......6.1.2.5...9.54....8.........3....85.1...3.2.8.4.......9.7..6....",
+// "4.....8.5.3..........7......2.....6.....8.4......1.......6.3.7.5..2.....1.4......",
+ "52...6.........7.13...........4..8..6......5...........418.........3..2...87.....",
+ "6.....8.3.4.7.................5.4.7.3..2.....1.6.......2.....5.....8.6......1....",
+ "48.3............71.2.......7.5....6....2..8.............1.76...3.....4......5....",
+// "....14....3....2...7..........9...3.6.1.............8.2.....1.4....5.6.....7.8...",
+ "......52..8.4......3...9...5.1...6..2..7........3.....6...1..........7.4.......3.",
+ "6.2.5.........3.4..........43...8....1....2........7..5..27...........81...6.....",
+ ".524.........7.1..............8.2...3.....6...9.5.....1.6.3...........897........",
+ "6.2.5.........4.3..........43...8....1....2........7..5..27...........81...6.....",
+ ".923.........8.1...........1.7.4...........658.........6.5.2...4.....7.....9.....",
+ "6..3.2....5.....1..........7.26............543.........8.15........4.2........7..",
+ ".6.5.1.9.1...9..539....7....4.8...7.......5.8.817.5.3.....5.2............76..8...",
+ "..5...987.4..5...1..7......2...48....9.1.....6..2.....3..6..2.......9.7.......5..",
+ "3.6.7...........518.........1.4.5...7.....6.....2......2.....4.....8.3.....5.....",
+ "1.....3.8.7.4..............2.3.1...........958.........5.6...7.....8.2...4.......",
+ "6..3.2....4.....1..........7.26............543.........8.15........4.2........7..",
+ "....3..9....2....1.5.9..............1.2.8.4.6.8.5...2..75......4.1..6..3.....4.6.",
+ "45.....3....8.1....9...........5..9.2..7.....8.........1..4..........7.2...6..8..",
+ ".237....68...6.59.9.....7......4.97.3.7.96..2.........5..47.........2....8.......",
+ "..84...3....3.....9....157479...8........7..514.....2...9.6...2.5....4......9..56",
+ ".98.1....2......6.............3.2.5..84.........6.........4.8.93..5...........1..",
+ "..247..58..............1.4.....2...9528.9.4....9...1.........3.3....75..685..2...",
+// "4.....8.5.3..........7......2.....6.....5.4......1.......6.3.7.5..2.....1.9......",
+ ".2.3......63.....58.......15....9.3....7........1....8.879..26......6.7...6..7..4",
+ "1.....7.9.4...72..8.........7..1..6.3.......5.6..4..2.........8..53...7.7.2....46",
+ "4.....3.....8.2......7........1...8734.......6........5...6........1.4...82......",
+ ".......71.2.8........4.3...7...6..5....2..3..9........6...7.....8....4......5....",
+ "6..3.2....4.....8..........7.26............543.........8.15........8.2........7..",
+ ".47.8...1............6..7..6....357......5....1..6....28..4.....9.1...4.....2.69.",
+ "......8.17..2........5.6......7...5..1....3...8.......5......2..4..8....6...3....",
+ "38.6.......9.......2..3.51......5....3..1..6....4......17.5..8.......9.......7.32",
+ "...5...........5.697.....2...48.2...25.1...3..8..3.........4.7..13.5..9..2...31..",
+ ".2.......3.5.62..9.68...3...5..........64.8.2..47..9....3.....1.....6...17.43....",
+ ".8..4....3......1........2...5...4.69..1..8..2...........3.9....6....5.....2.....",
+ "..8.9.1...6.5...2......6....3.1.7.5.........9..4...3...5....2...7...3.8.2..7....4",
+// "4.....5.8.3..........7......2.....6.....5.8......1.......6.3.7.5..2.....1.8......",
+ "1.....3.8.6.4..............2.3.1...........958.........5.6...7.....8.2...4.......",
+ "1....6.8..64..........4...7....9.6...7.4..5..5...7.1...5....32.3....8...4........",
+ "249.6...3.3....2..8.......5.....6......2......1..4.82..9.5..7....4.....1.7...3...",
+ "...8....9.873...4.6..7.......85..97...........43..75.......3....3...145.4....2..1",
+// "...5.1....9....8...6.......4.1..........7..9........3.8.....1.5...2..4.....36....",
+ "......8.16..2........7.5......6...2..1....3...8.......2......7..3..8....5...4....",
+ ".476...5.8.3.....2.....9......8.5..6...1.....6.24......78...51...6....4..9...4..7",
+ ".....7.95.....1...86..2.....2..73..85......6...3..49..3.5...41724................",
+ ".4.5.....8...9..3..76.2.....146..........9..7.....36....1..4.5..6......3..71..2..",
+ ".834.........7..5...........4.1.8..........27...3.....2.6.5....5.....8........1..",
+ "..9.....3.....9...7.....5.6..65..4.....3......28......3..75.6..6...........12.3.8",
+ ".26.39......6....19.....7.......4..9.5....2....85.....3..2..9..4....762.........4",
+ "2.3.8....8..7...........1...6.5.7...4......3....1............82.5....6...1.......",
+ "6..3.2....1.....5..........7.26............843.........8.15........8.2........7..",
+ "1.....9...64..1.7..7..4.......3.....3.89..5....7....2.....6.7.9.....4.1....129.3.",
+ ".........9......84.623...5....6...453...1...6...9...7....1.....4.5..2....3.8....9",
+ ".2....5938..5..46.94..6...8..2.3.....6..8.73.7..2.........4.38..7....6..........5",
+ "9.4..5...25.6..1..31......8.7...9...4..26......147....7.......2...3..8.6.4.....9.",
+ "...52.....9...3..4......7...1.....4..8..453..6...1...87.2........8....32.4..8..1.",
+ "53..2.9...24.3..5...9..........1.827...7.........981.............64....91.2.5.43.",
+ "1....786...7..8.1.8..2....9........24...1......9..5...6.8..........5.9.......93.4",
+ "....5...11......7..6.....8......4.....9.1.3.....596.2..8..62..7..7......3.5.7.2..",
+ ".47.2....8....1....3....9.2.....5...6..81..5.....4.....7....3.4...9...1.4..27.8..",
+ "......94.....9...53....5.7..8.4..1..463...........7.8.8..7.....7......28.5.26....",
+ ".2......6....41.....78....1......7....37.....6..412....1..74..5..8.5..7......39..",
+ "1.....3.8.6.4..............2.3.1...........758.........7.5...6.....8.2...4.......",
+ "2....1.9..1..3.7..9..8...2.......85..6.4.........7...3.2.3...6....5.....1.9...2.5",
+ "..7..8.....6.2.3...3......9.1..5..6.....1.....7.9....2........4.83..4...26....51.",
+ "...36....85.......9.4..8........68.........17..9..45...1.5...6.4....9..2.....3...",
+ "34.6.......7.......2..8.57......5....7..1..2....4......36.2..1.......9.......7.82",
+ "......4.18..2........6.7......8...6..4....3...1.......6......2..5..1....7...3....",
+ ".4..5..67...1...4....2.....1..8..3........2...6...........4..5.3.....8..2........",
+ ".......4...2..4..1.7..5..9...3..7....4..6....6..1..8...2....1..85.9...6.....8...3",
+ "8..7....4.5....6............3.97...8....43..5....2.9....6......2...6...7.71..83.2",
+ ".8...4.5....7..3............1..85...6.....2......4....3.26............417........",
+ "....7..8...6...5...2...3.61.1...7..2..8..534.2..9.......2......58...6.3.4...1....",
+ "......8.16..2........7.5......6...2..1....3...8.......2......7..4..8....5...3....",
+ ".2..........6....3.74.8.........3..2.8..4..1.6..5.........1.78.5....9..........4.",
+ ".52..68.......7.2.......6....48..9..2..41......1.....8..61..38.....9...63..6..1.9",
+ "....1.78.5....9..........4..2..........6....3.74.8.........3..2.8..4..1.6..5.....",
+ "1.......3.6.3..7...7...5..121.7...9...7........8.1..2....8.64....9.2..6....4.....",
+ "4...7.1....19.46.5.....1......7....2..2.3....847..6....14...8.6.2....3..6...9....",
+ "......8.17..2........5.6......7...5..1....3...8.......5......2..3..8....6...4....",
+ "963......1....8......2.5....4.8......1....7......3..257......3...9.2.4.7......9..",
+ "15.3......7..4.2....4.72.....8.........9..1.8.1..8.79......38...........6....7423",
+ "..........5724...98....947...9..3...5..9..12...3.1.9...6....25....56.....7......6",
+ "....75....1..2.....4...3...5.....3.2...8...1.......6.....1..48.2........7........",
+ "6.....7.3.4.8.................5.4.8.7..2.....1.3.......2.....5.....7.9......1....",
+ "....6...4..6.3....1..4..5.77.....8.5...8.....6.8....9...2.9....4....32....97..1..",
+ ".32.....58..3.....9.428...1...4...39...6...5.....1.....2...67.8.....4....95....6.",
+ "...5.3.......6.7..5.8....1636..2.......4.1.......3...567....2.8..4.7.......2..5..",
+ ".5.3.7.4.1.........3.......5.8.3.61....8..5.9.6..1........4...6...6927....2...9..",
+ "..5..8..18......9.......78....4.....64....9......53..2.6.........138..5....9.714.",
+ "..........72.6.1....51...82.8...13..4.........37.9..1.....238..5.4..9.........79.",
+ "...658.....4......12............96.7...3..5....2.8...3..19..8..3.6.....4....473..",
+ ".2.3.......6..8.9.83.5........2...8.7.9..5........6..4.......1...1...4.22..7..8.9",
+ ".5..9....1.....6.....3.8.....8.4...9514.......3....2..........4.8...6..77..15..6.",
+ ".....2.......7...17..3...9.8..7......2.89.6...13..6....9..5.824.....891..........",
+ "3...8.......7....51..............36...2..4....7...........6.13..452...........8..")
+
+
+
+//search(game0).map(pretty)
+//search(game1).map(pretty)
+
+// for measuring time
+def time_needed[T](i: Int, code: => T) = {
+ val start = System.nanoTime()
+ for (j <- 1 to i) code
+ val end = System.nanoTime()
+ s"${(end - start) / i / 1.0e9} secs"
+}
+
+//search(game2).map(pretty)
+//search(game3).distinct.length
+println(time_needed(10, search(game0)))
+println(time_needed(10, search(game1)))
+println(time_needed(4, search(game2)))
+println(time_needed(8, search(game3)))
+
+for (i <- 0 until hard_games.length) {
+ println(" " ++ hard_games(i))
+ println(s"$i: ${time_needed(1, search(hard_games(i)))}")
+}
+
+}
\ No newline at end of file