CSE 130: Spring 2016

Recap: Scala Basics

Today

Compiling and Running

Compiling and Running

To make an executable, put the functions in a file

e.g. lec-iterators.scala

object Freq { ... }

compile with

$ scalac lec-iterators.scala

and run with

$ scala Freq lec-iterators.markdown
$ scala Freq foo.txt
...

Compiling and Running

Or run in the REPL

scala> import Freq._
scala> val m = Freq("caterpillar")
scala> Freq.show(m, 1)
c : #
a : ##
e : #
i : #
r : ##
t : #
l : ##
p : #

Today: Iteration AND Recursion

Today: Iteration AND Recursion

Elegant way to systematically

  1. Generate Combinations
  1. Search Combinations
  1. Generate + Search Combinations

Warm-up: A Polymorphic Frequency Finder

Lets write a Polymorphic Frequency Finder

Lets write a polymorphic frequency finder.

def freq[A](xs: Iterable[A]): HashMap[A, Int] = {
  val freqMap = new HashMap[A, Int]
  for (x <- xs) {
    freqMap(x) = 1 + freqMap.getOrElse(x, 0)
  }
  freqMap
}

Iterable[A] describes objects that can be iterated over...

Lets write a Polymorphic Frequency Finder

Can run it on Strings

scala> freq("caterillar")
res: scala.collection.mutable.HashMap[Char,Int]
  = Map(c -> 1, a -> 2, e -> 1, i -> 1, r -> 2, t -> 1, l -> 2)

or List

scala> freq(List(1,2,1,13,1,2,1,3,31,12,1))
res: scala.collection.mutable.HashMap[Int,Int]
     = Map(12 -> 1, 3 -> 1, 13 -> 1, 1 -> 5, 2 -> 2, 31 -> 1)

or ...

Today: Iteration AND Recursion

Elegant way to systematically

  1. Generate Combinations

  2. Search Combinations

  3. Generate & Search Combinations

QUIZ: Nested for-loops

Of course, you can nest for-loops too:

val res = for (xs <- Array("cat", "dog");
               x  <- xs)
          yield x

What is the type of res?

A. String

B. List[String]

C. Iterator[String]

D. List[Char]

E. Iterator[Char]

Nested for-loops

Of course, you can nest for-loops too:

val res = for (xs <- Iterator("cat", "dog", "mouse");
               x  <- xs)
          yield x

What is the type of res?

Type Of Output Collection

QUIZ: Nested for-loops

val res = for ( i <- List(1, 2)
              ; j <- Iterator("a", "b"))
          yield (i, j)

What is the value of res ?

A. Nothing (Type Error)

B. List(1, 2, "a", "b")

C. List(1, "a", 2, "b")

D. List((1, "a"), (2, "b"))

E. List((1,"a"), (1,"b"), (2,"a"), (2,"b"))

Nested for Loops

val res = for ( i <- List(1, 2)
              ; j <- List("a", "b"))
          yield (i, j)

Here is how it goes down:

PSA: Why choose Iterator vs. List

PSA: Why choose Iterator vs. List

We chose Iterator and not List for password crack

Why?

Not to make you write

words.toList.filter(...).toIterator     // yuck

PSA: Why choose Iterator vs. List

We chose Iterator and not List for password crack

Not to make you write

words.toList.filter(...).toIterator     // yuck

which is almost the same as

words.filter(...)                       // sweet!

PSA: Why choose Iterator vs. List

We chose Iterator and not List for password crack

Because Iterator lazily computes one element at a time

At each .next call

PSA: Why choose Iterator vs. List

We chose Iterator and not List for password crack

Because Iterator lazily computes one element at a time

At each .next call

So Iterator good for operating on big data streams

PSA: Why choose Iterator vs. List

Iterator is lazy, good for operating on big data streams

def allVowels(megaDictionary: Iterator[String]): Iterator[String] =
  for { w <- megaDictionary
      ; if hasAllVowels(w)  }
  yield w
def allVowels(megaDictionary: List[String]): List[String] =
  for (w <- megaDictionary
       if hasAllVowels(w))
  yield w

PSA: Why choose Iterator vs. List

We chose Iterator and not List for password crack

Iterator is lazy, good for operating on big data streams

def txReverse(megaDictionary: Iterator[String]): Iterator[String] =
  for (w <- megaDictionary
       c <- Iterator(w, reverse(w))
  yield c
def txReverse(megaDictionary: List[String]): List[String] =
  for (w <- megaDictionary
       c <- Iterator(w, reverse(w))
  yield c

Note: Only difference is in the type

PSA: Why choose Iterator vs. List

We chose Iterator and not List for password crack

Iterator is lazy, good for operating on big data streams

So why not always use Iterator ?

PSA: Bottom-line

For PA5

QUIZ: Combining Iteration & Recursion

def bitStrings(n:Int) : List[String] =
  if (n <= 0) {
    List("")
  } else {
    for (c <- List("0", "1");
         s <- bitStrings(n-1))
    yield(c + s)
  }

What does bitStrings(2) return?

A. Nothing (Type Error)

B. Nothing (Infinite Loop)

C. List()

D. List("0", "1")

E. List("00", "01", "10", "11")

Combining Iteration & Recursion

Consider the following function:

def bitStrings(n: Int) : List[String] =
  if (n <= 0) { List() } else {
   for (c <- List("0", "1");
        s <- bitStrings(n-1))
   yield(c + s)
  }

Here is what happens (lets work backwards)

bitStrings(0) ==> List()

Combining Iteration & Recursion

Consider the following function:

def bitStrings(n: Int) : List[String] =
  if (n <= 0) { List() } else {
   for (c <- List("0", "1");
        s <- bitStrings(n-1))
   yield(c + s)
  }

Here is what happens (lets work backwards)

bitStrings(1) ==> ?

Combining Iteration & Recursion

Consider the following function:

def bitStrings(n: Int) : List[String] =
  if (n <= 0) { List() } else {
   for (c <- List("0", "1");
        s <- bitStrings(n-1))
   yield(c + s)
  }

Here is what happens (lets work backwards)

bitStrings(1) ==> List()

Recap: Nested Loops

Nested loops are like cartesian products

scala> for ( i <- List(1, 2)
           ; j <- List("a", "b"))
       yield (i, j)
res0: List[(Int, String)] = List((1,a), (1,b), (2,a), (2,b))

Result is empty if either the first sequence is empty

scala> for ( i <- List(1,2)
           ; j <- List())
       yield (i, j)
res1: List[(Int, String)] = List()

or the second sequence is empty

scala> for ( i <- List()
           ; j <- List("a", "b"))
       yield (i, j)
res2: List[(Nothing, String)] = List()

Combining Iteration & Recursion

def bitStrs(n: Int) : List[String] =
  if (n <= 0) { List() } else {
   for (c <- List("0", "1");
        s <- bitStrs(n-1))
   yield(c + s)
  }

How can we fix this function so that:

bitStrs(1) ==> List("0","1")

bitStrs(2) ==> List("00","01","10","11")

bitStrs(3) ==> List("000","001","010","011","100","101","110","111")

etc. ?

Combining Iteration & Recursion

Base Case

def bitStrings(n: Int) : List[String] =
  if (n <= 0) { List("") } else {
   for (c <- List("0", "1");
        s <- bitStrings(n-1))
   yield(c + s)
  }

QUIZ: What is the value of res ?

def foo(w: String) : List[String] =
  if (w == "")  { List("") } else
    for (c <- List("", w.substring(0, 1));
         s <- foo(w.substring(1)))
    yield(c + s)

val res = foo("go")

Hint "sunday".substring(0, 1) ==> "s" and "sunday".substring(1) ==> "unday"

A. Nothing (Infinite Loop)

B. List()

C. List("", "o", "g", "go")

D. List("")

E. List("o", "g", "go")

Combining Iteration & Recursion

def subStrings(w: String) : List[String] =
  if (w == "")  { List(w) } else
    for (c <- List("", w.substring(0, 1));
         s <- subStrings(w.substring(1)))
    yield(c + s)

Again, lets work backwards

subStrings("") ==> List("")

Combining Iteration & Recursion

def subStrings(w: String) : List[String] =
  if (w == "")  { List(w) } else
    for (c <- List("", w.substring(0, 1));
         s <- foo(w.substring(1)))
    yield(c + s)

Lets work backwards . subStrings("o") ==> ?

Combining Iteration & Recursion

def subStrings(w: String) : List[String] =
  if (w == "")  { List(w) } else
    for (c <- List("", w.substring(0, 1));
         s <- foo(w.substring(1)))
    yield(c + s)

Lets work backwards . subStrings("o") ==> List("", "o")

Combining Iteration & Recursion

def subStrings(w: String) : List[String] =
  if (w == "")  { List(w) } else
    for (c <- List("", w.substring(0, 1));
         s <- foo(w.substring(1)))
    yield(c + s)

Lets work backwards . subStrings("go") ==> ?

Combining Iteration & Recursion

def subStrings(w: String) : List[String] =
  if (w == "")  { List(w) } else
    for (c <- List("", w.substring(0, 1));
         s <- foo(w.substring(1)))
    yield(c + s)

Lets work backwards . subStrings("go") ==> List("", "o", "g", "go")

Combining Iteration & Recursion

Mega Hint for PA5

substrings is almost identical to transformCapitalize

subStrings

Replace each character "c" by either "c" or ""

transformCapitalize

Replace each character "c" by either "c" or "C"

Today: Iteration AND Recursion

Elegant way to systematically

  1. Generate Combinations

  2. Search Combinations

  3. Generate & Search Combinations

QUIZ: Systematic Search/Query

val res = for (i <- 1 to 10;
               j <- 1 to 10;
               k <- 1 to 10
               if i*i + j*j == k*k)
          yield (i, j, k)

What is the value of res ?

A. Vector()

B. Vector((3,4,5), (6,8,10))

C. Vector((6,8,10), (3,4,5))

D. Vector((3,4,5), (4,3,5), (6,8,10), (8,6,10))

E. Vector((8,6,10), (6,8,10), (4,3,5), (3,4,5))

Systematic Search/Query

val res = for (i <- 1 to 10;
               j <- 1 to 10;
               k <- 1 to 10
               if i*i + j*j == k*k)
          yield (i, j, k)

Is equivalent to:

val res = (for (i <- 1 to 10;j <- 1 to 10; k <- 1 to 10)
           yield (i, j, k)
          ).filter { case (i, j, k) => i*i + j*j == k*k}

which is equivalent to:

Vector( (1,1,1), (1,1,2), ..., (1,1,10),  (1,2,1),..., (1,10,10)
      , (2,1,1), (2,1,2), ..., (2,1,10),  (2,2,1),..., (2,10,10)
      , ...,
      ,(10,1,1), (10,1,2),...,(10,1,10), (10,2,1),...,(10,10,10)
      ).filter { case (i, j, k) => i*i + j*j == k*k}

Systematic Search/Query

Note: filter Preserves Sequence Order

Hence, the expression

Vector( (1,1,1), (1,1,2), ..., (1,1,10),  (1,2,1),..., (1,10,10)
      , (2,1,1), (2,1,2), ..., (2,1,10),  (2,2,1),..., (2,10,10)
      , ...,
      ,(10,1,1), (10,1,2),...,(10,1,10), (10,2,1),...,(10,10,10)
      ).filter { case (i, j, k) => i*i + j*j == k*k}

evaluates to ...

D. Vector((3,4,5), (4,3,5), (6,8,10), (8,6,10))

Systematic Search/Query

Systematic Search/Query

val res = for (i <- 1 to 10;
               j <- 1 to 10;
               k <- 1 to 10
               if i*i + j*j == k*k && i <= j)
          yield (i, j, k)

Can Query More Interesting Objects

Brief Digression: Case Classes

Case Classes

case class Name(x1: T1, x2: T2, ..., xn: TN)

Creates a class Name with

  1. Immutable fields x1 of type T1 ... xn of type Tn
  1. Constructor method for object creation
  1. Extractor method for pattern matching (later...)

Case Classes: Example Novel

Here is a case class (just fancy records for now...)

case class Novel(title: String, author: String)

You can create instances thus (no need for new because Scala generates an apply for us)

scala> val n1 = Novel("A Feast For Crows", "George R. R. Martin")
n1: Novel = Novel(A Feast For Crows,George R. R. Martin)

// which is equivalent from Scala's view to...

scala> val n2 = Novel.apply("A Feast For Crows", "George R. R. Martin")
n2: Novel = Novel(A Feast For Crows,George R. R. Martin)

and access fields like so

scala> n1.author
n1: String = George R. R. Martin

Case Classes: Example Album

Here is another case class (just fancy records for now...)

case class Album(title: String, artist: String)

You can create instances thus (no need for new again)

scala> val a = Album("We are glitter", "Goldfrapp")
a: Album = Album(We are glitter,Goldfrapp)

Back to Querying More Interesting Objects

Database Style Queries

Suppose we have a "database" of novels

val novels =
  List( Novel ( "Skinny Legs and All"
              , "Tom Robbins")

      , Novel ( "Breakfast of Champions"
              , "Kurt Vonnegut")

      , Novel ( "An Object of Beauty"
              , "Steve Martin")

      , Novel ( "Sophie's Choice"
              , "William Styron")

      , Novel ( "The Other"
              , "Tom Tryon")
      )

Database Style Queries

... and a "database" of albums

val albums =
  List( Album ( "Rare Bird Alert"
              , "Steve Martin")

      , Album ( "Paper Airplane"
              , "Alison Krauss and Union Station")

      , Album ( "Earl Scruggs and Friends"
              , "Earl Scruggs")
      )

Database Style Queries

... and a "database" of movies

val movies =
  List( Movie ("Airplane",
               List ( "Leslie Nielsen", "Robert Stack"))

      , Movie ("Young Frankenstein",
               List ("Gene Wilder", "Madeline Kahn"))

      , Movie ("The Pink Panther",
               List ("Steve Martin", "Jean Reno"))
      )

Query: Is there tripleThreat ?

A person who has

  1. written a book,
  2. acted in a movie,
  3. performed in an album ?

Query: Is there a tripleThreat ?

A person who has

  1. written a book,
  2. acted in a movie,
  3. performed in an album ?

Cue, nested loop query...

for (n <- novels;
     a <- albums;
     m <- movies;
     if (n.author == a.artist && m.actors.contains (n.author)))
yield (n.author)

Query: Is there a tripleThreat ?

A person who has

  1. written a book,
  2. acted in a movie,
  3. performed in an album ?

Cue, nested loop query...

for (n <- novels;
     a <- albums;
     m <- movies;
     if (n.author == a.artist && m.actors.contains (n.author)))
yield (n.author)

Which evaluates to

tripleThreats: List[String] = List(Steve Martin)

Even more magical: From Loops-to-SQL

You can define a special collection type such that the expression

for (n <- novels;
     a <- albums;
     m <- movies;
     if (n.author == a.artist && m.actors.contains (n.author)))
yield (n.author)

is automatically converted into an SQL (DataBase) query ...!

Today: Iteration AND Recursion

Elegant way to systematically

  1. Generate Combinations

  2. Search Combinations

  3. Generate & Search Combinations

Iteration + Recursion + Filter = Fun Ensues

Generate and Search: The N-Queens Puzzle

Given a chess board of size n rows and n columns

Find a placement of n queens so none can kill each other!


Generate and Search: The N-Queens Puzzle

Given a chess board of size n rows and columns

Find a placement of n queens so none can kill each other!


First: What is a Solution?

Generate and Search: The N-Queens Puzzle

The first question: what is a solution ?

Generate and Search: The N-Queens Puzzle

The first question: what is a solution ?

We represent each queen by its position XY: a pair of (row, col)

type XY = (Int, Int)

Generate and Search: The N-Queens Puzzle

The first question: what is a solution ?

We represent each queen by its position XY: a pair of (row, col)

type XY = (Int, Int)

One queen q1 can kill another q2 if

def canKill(q1: XY, q2: XY) =
  q1._1 == q2._1 ||                          // same row
  q1._2 == q2._2 ||                          // same column
  (q1._1 - q2._1).abs == (q1._2 - q2._2).abs // same diagonal

QUIZ: When is a board safe?

canKill(q1, q2) is true if a queen at q1 can kill another q2

queens : List[XY] is a list of occupied positions

q : XY is a new queen position.

Which expression evaluates to true exactly when none of queens can kill q ?

A. for (qo <- queens) yield !canKill(qo, q)

B. for (qo <- queens) yield canKill(qo, q)

C. queens.exists(!canKill(_,q))

D. queens.forall(!canKill(_,q))

E. queens.map(!canKill(_,q)).foldLeft(true)(_ && _)

When is a board safe?

canKill(q1, q2) is true if a queen at q1 can kill another q2

queens : List[XY] is a list of occupied positions

q : XY is a new queen position.

Board is Safe

Generate and Search: The N-Queens Puzzle

The first question: what is a solution ?

We represent each queen by its position XY: a pair of (row, col)

type XY = (Int, Int)

One queen q1 can kill another q2 if

def canKill(q1: XY, q2: XY) =
  eqRow(q1, q2) || eqCol(q1, q2) || eqDia(q1, q2)

A queen at q is safe w.r.t. other queens if:

def isSafe(queen: XY, others: List[XY]) =
  others forall (!canKill(_, queen))

Generate and Search: The N-Queens Puzzle

Given a chess board of size n rows and columns

Find a placement of n queens so none can kill each other!

def placeQueens(columns: Int, row: Int) : List[XY]

To place queens on row r ... 0

Generate and Search: The N-Queens Puzzle

Given a chess board of size n rows and columns

Find a placement of n queens so none can kill each other!

Problem

Solution

Generate and Search: The N-Queens Puzzle

Given a chess board of size n rows and columns

Find a placement of n queens so none can kill each other!

def placeQueens(columns: Int, row: Int) : List[List[XY]]

Strategy: Recursive Search

To place queens on row r ... 0

  1. (recursively) place queens on rows r-1 ... 0
  1. for each (recursive) solution
  1. for each column in row r
  1. yield position which isSafe w.r.t. recursive solution

Generate and Search: The N-Queens Puzzle

Given a chess board of size n rows and columns

Find a placement of n queens so none can kill each other!

Strategy: Recursive Search

def placeQueens(columns: Int, row: Int) : List[List[XY]] =
  if (row == 0)
    List(List())
  else
    for { queens <- placeQueens(columns, row - 1)
          column <- 1 to columns
          queen   = (row, column)
          if isSafe(queen, queens) }
    yield (queen :: queens)

Generate and Search: The N-Queens Puzzle

Given a chess board of size n rows and columns

Find a placement of n queens so none can kill each other!

Lets run it: 4 Queens

Just printing the 1 solution (of several)

scala> Queens(4, 1)
OOXO
XOOO
OOOX
OXOO

Generate and Search: The N-Queens Puzzle

Given a chess board of size n rows and columns

Find a placement of n queens so none can kill each other!

Lets run it: 8 Queens

Just printing the 1 solution (there are many)

scala> Queens(8, 1)
OOOXOOOO
OXOOOOOO
OOOOOOXO
OOXOOOOO
OOOOOXOO
OOOOOOOX
OOOOXOOO
XOOOOOOO

Generate and Search: The N-Queens Puzzle

Given a chess board of size n rows and columns

Find a placement of n queens so none can kill each other!

Lets run it: 2 or 3 Queens

scala> Queens(2, 1)

scala> Queens(3, 1)

scala>

Iteration + Recursion + Filter = Fun Continues

Generate and Search: A Sudoku Solver

Generate and Search: A Sudoku Solver

Given A sudoku puzzle

5, 3,  ,  , 7,  ,  ,  ,
6,  ,  , 1, 0, 5,  ,  ,
 , 0, 8,  ,  ,  ,  , 6,
8,  ,  ,  , 6,  ,  ,  , 3
4,  ,  , 8,  , 3,  ,  , 1
7,  ,  ,  , 2,  ,  ,  , 6
 , 6,  ,  ,  ,  , 2, 8,
 ,  ,  , 4, 1, 0,  ,  , 5
 ,  ,  ,  , 8,  ,  , 7, 0

Generate and Search: A Sudoku Solver

Find A solution

5, 3, 4, 6, 7, 8, 0, 1, 2
6, 7, 2, 1, 0, 5, 3, 4, 8
1, 0, 8, 3, 4, 2, 5, 6, 7
8, 5, 0, 7, 6, 1, 4, 2, 3
4, 2, 6, 8, 5, 3, 7, 0, 1
7, 1, 3, 0, 2, 4, 8, 5, 6
0, 6, 1, 5, 3, 7, 2, 8, 4
2, 8, 7, 4, 1, 0, 6, 3, 5
3, 4, 5, 2, 8, 6, 1, 7, 0

First: What is a Board & Solution?

Generate and Search: Sudoku Solver

The first question: what is a sudoku board ?

Generate and Search: Sudoku Solver

The first question: what is a sudoku board ?

Representing Squares

We represent each square by its position XY: a pair of (row, col)

type XY = (Int, Int)

Generate and Search: Sudoku Solver

The first question: what is a sudoku board ?

Representing Squares

We represent each square by its position XY: a pair of (row, col)

type XY = (Int, Int)

Representing Boards

We represent the board by a (partial) map from XY to Int

type Board = Map[XY, Int]

Representing Sudoku Boards

5, 3,  ,  , 7,  ,  ,  ,
6,  ,  , 1, 0, 5,  ,  ,
 , 0, 8,  ,  ,  ,  , 6,
8,  ,  ,  , 6,  ,  ,  , 3
4,  ,  , 8,  , 3,  ,  , 1
7,  ,  ,  , 2,  ,  ,  , 6
 , 6,  ,  ,  ,  , 2, 8,
 ,  ,  , 4, 1, 0,  ,  , 5
 ,  ,  ,  , 8,  ,  , 7, 0

is represented by

Map ((0, 0) -> 5, (0, 1) -> 3, (0, 4) -> 7,
     (1, 0) -> 6, (1, 3) -> 1, (1, 4) -> 0, (1, 5) -> 5,
     (2, 1) -> 0, (2, 2) -> 8, (2, 7) -> 6,
     (3, 0) -> 8, (3, 4) -> 6, (3, 8) -> 3,
     (4, 0) -> 4, (4, 3) -> 8, (4, 5) -> 3, (4, 8) -> 1,
     (5, 0) -> 7, (5, 4) -> 2, (5, 8) -> 6,
     (6, 1) -> 6, (6, 6) -> 2, (6, 7) -> 8,
     (7, 3) -> 4, (7, 4) -> 1, (7, 5) -> 0, (7, 8) -> 5,
     (8, 4) -> 8, (8, 7) -> 7, (8, 8) -> 0)

Generate and Search: Sudoku Solver

Given a partially filled Sudoku Board

Find a way to fill in all squares

Strategy: Recursive Search

Generate and Search: Sudoku Solver

Given a partially filled Sudoku Board

Find a way to fill in all squares

Strategy: Recursive Search

def solve(b: Board) : Iterator[Board] = {
  val blanks = candidates(b)
  if (blanks.isEmpty) Iterator(b)
  else {
    val (xy, choices) = blanks minBy (_._2.length)
    for (choice <- choices.toIterator;
         bFull  <- solve(b + (xy -> choice)))
    yield bFull
  }
}

Generate and Search: Sudoku Solver

def solve(b: Board) : Iterator[Board] = {
  val blanks = candidates(b)
  if (blanks.isEmpty) Iterator(b)
  else {
    val (xy, choices) = blanks minBy (_._2.length)
    for (choice <- choices.toIterator;
         bFull  <- solve(b + (xy -> choice)))
    yield bFull
  }
}

Questions

Generate and Search: Sudoku Solver

Details: Computing candidates for a board

def candidates (b: Board) =
  for { x <- 0 until 9 ;
        y <- 0 until 9 ;
        if (!b.isDefinedAt((x,y))) ;
        xy   = (x, y) ;
        vals = (0 until 9) diff (alreadyTaken(x,y,b)) }
  yield (xy, vals)

Generate and Search: Sudoku Solver

Details: Computing alreadyTaken values for a square

def alreadyTaken(x: Int, y: Int, b: Board) =
  for (p <- pointsOfCol(x) ++
            pointsOfRow(y) ++
            pointsOfGrid(x, y)
       if b.isDefinedAt(p))
  yield b(p)

Generate and Search: Sudoku Solver

Details: Points in Same Grid

def pointsOfGrid(x: Int, y: Int) = {
  val (x0, y0) = ((x/3) * 3,  (y/3) * 3)
  for (px <- x0 until x0 + 3 ;
       py <- y0 until y0 + 3 )
  yield (px, py)
}

Details: Points in Same Row/Column

def pointsOfCol(x: Int) =
  for (y <- 0 until 9) yield (x, y)

def pointsOfRow(y: Int) =
  for (x <- 0 until 9) yield (x, y)

Lets run the solver!

Today: Iteration AND Recursion

Elegant way to systematically

  1. Generate Combinations

  2. Search Combinations

  3. Generate & Search Combinations

How ?