5-card poker probabilities

(I do this as a warm up exercise when I need to think about combinatorics, weird as that may sound)

The total number of choices for 5 cards is

$$ 52 * 51 * 50 * 49 * 48 = 311875200 $$

One pair: 

$$ {13 \choose 1} * { 4 \choose 2} * { 12 \choose 3 } * { 4 \choose 1}^3 = 1098240 $$

Two pair:

$$ {13 \choose 2 } * { 4 \choose 2}^2 * { 11 \choose 1} * {4 \choose 1} = 123552 $$

Three of a kind: 

$$ {13 \choose 1} * {4 \choose 3} * { 12 \choose 2 } * { 4 \choose 1}^2 = 54912 $$

Straight: 

$$  {10 \choose 1} * { 4 \choose 1} ^ 5 - (straight flush,royal flush) =   {10 \choose 1} * { 4 \choose 1} ^ 5 - {10 \choose 1}* {4 \choose 1} = 10200 $$

Flush:

$$ {13 \choose 5} * {12 \choose 1} - (royal flush,straight flush) = {13 \choose 5} * {12 \choose 1} - {10 \choose 1}* {4 \choose 1} = 5108 $$

Full House: 

$$ {13 \choose 1} {4 \choose 3} * { 12 \choose 1} * { 4 \choose 2} = 3744 $$

Four of a kind:

$$ {13 \choose 1} * { 12 \choose 1} * { 4 \choose 1} = 624$$

Straight flush (not including royal flush):

Per suit there are 10 choices of straight (A - 5, 2 - 6, 3 - 7, 4 - 8, 5 - 9, 6 - 10, 7 - J, 8 - Q, 9 - K, 10 - A)

$$ {10 \choose 1} * {4 \choose 1} - {4 \choose 1} = 36 $$

Royal flush: 

$$ {4 \choose 1} = 4 $$

Least Squares Regression

If you have a scatter graph of n points, how can you find a 'line of best fit' for the data?

There exists some line $l_i$ that we need to find:

$$l_i = m (x_i) + c$$

However, the y-intercept of this line (c) is the y-value when x = 0. This may not be the most useful results so one neat adjustment we can make is redefined the line so that it crosses the y axis when $x$ = $\bar{x}$.

$$l_i = m (x_i - \bar{x}) + c $$

For a least squares regression we want to find m and c such that the following sum is minimised:

$$ \sum_{i=1}^{n}(y_i - l_i)^2 = \sum_{i=1}^{n}(y_i - (m(x_i - \bar{x}) + c))^2 \equiv Q $$

Solution: 

Minimising $Q$ involves differentiating Q by $c$ and $m$, setting each result to zero and solving for $c$ and $m$.

Firstly differentiate wrt $c$: 

$$Q = \sum_{i=1}^{n}(y_i - (m(x_i - \bar{x}) + c))^2 $$

$$\frac{dQ}{dc} = 2 \sum_{i=1}^{n}(y_i - (m(x_i - \bar{x}) + c)) * (-1) = 0 $$

$$ =>  - \sum _{i=1}^{n} y_i + m  \sum _{i=1}^{n} (x_i - \bar{x}) + \sum _{i=1}^{n}c = 0 $$

Note that $  \sum _{i=1}^{n} (x_i - \bar{x}) = 0 $

Therefore:

$$  - \sum _{i=1}^{n} y_i  + n c = 0 $$

$$ => c = \frac{\sum _{i=1}^{n} y_i } { n } = \bar{y} $$

Now let's differentiate wrt $m$:

$$Q = \sum_{i=1}^{n}(y_i - (m(x_i - \bar{x}) + \bar{y}))^2 $$

$$ \frac{dQ}{dm} = 2 \sum_{i=1}^{n}(y_i - (m(x_i - \bar{x}) + \bar{y}))(\bar{x}-x_i) = 0 $$

$$ => \sum_{i=1}^{n} (y_i - (m x_i - m \bar{x} + \bar{y}))(\bar{x} - x_1) = 0 $$

$$ => \sum_{i=1}^{n} (y_i - m x_i + m \bar{x} - \bar{y}))(\bar{x} - x_1) = 0 $$

$$ => \sum_{i=1}^{n} [(y_i \bar{x}- m x_i \bar{x} + m \bar{x}^2 - \bar{y}\bar{x}) - (y_i x_i - m x_i^2 + m \bar{x} x_i - \bar{y} x_i)] = 0 $$

$$ => m \sum_{i=1}^{n} ( \bar{x}^2 + x_i^2 - 2 \bar{x} x_i) + \sum_{i=1}^{n} (y_i \bar{x} - \bar{y} \bar{x} - y_i x_i - \bar{y} x_i) = 0 $$ 

$$ => m  \sum_{i=1}^{n} (x_i - \bar{x})^2 -  \sum_{i=1}^{n} (y_i - \bar{y})(x_i - \bar{x}) = 0 $$

$$ => m = \frac{\sum_{i=1}^{n} (y_i - \bar{y})(x_i - \bar{x})}{\sum_{i=1}^{n} (x_i - \bar{x})^2 }$$

Voila. Now to find the line, we can easily calculate $c$ and $m$. 

Formal definition of a Monad

A monad it a parametric type with two functions defined, $flatMap$ and $unit$.

trait Monad[T] {
  def flatMap[U](f: T => Monad[U]): Monad[U]
}

def unit[T](t: T): Monad[T]

Monads must satisfy the following three laws:

Associativity law: $$ m.flatMap(f).flatMap(g) = m.flatMap ( x => f(x).flatmap(g)) $$

Left unit law:  $$ unit(x).flatMap(f) = f(x) $$

Right unit law: $$ m.flatMap(unit) = m $$

Dijkstra in scala

The easiest way to understand dijkstra is by watching a youtube video.

Step 1: Mark all distance to start node as 0 and distance to all other nodes as infinity.
Step 2: Take current node and update distance to all its linked nodes that are unvisited
Step 3: Choose the next node which is the closest unvisited node.
Repeat steps 2 and 3 until target nodes is marked visited.

The following gist shows the code. Full code on github.

How to implement a graph

Let's take the edit distance example graph from an earlier post.

This is our example graph:


An edge exists between two nodes if they differ by only one letter.

There are two main ways of representing graphs in memory:

1. Adjacency Matrix

This is a 2x2 matrix with a bit set if there is an edge between two vertices. Note that because this is a undirected graph this matrix will be symmetrical.

       cat    cab    car    bar    tar    tat
cat             1       1
cab   1                1
car    1       1                1  
bar                      1                1
tar                                1              1
tat                                          1

2. Adjacency List

For each Vertex maintain a list containing all linked vertices.

cat      [cab, car]
cab     [cat, car]
car      [cat, bar, cab]
bar      [car, tar]
tar       [bar, tat]
tat       [tar]

(Note that to solve the problem, it's a simple matter of building a graph and executing dijkstra's algorithm to find the shortest path between two nodes.)

Computing edit distance between strings in Scala

Question: Assuming you have a set of n letter dictionary words ($S$), a start word ($s_0 \in S$) and a target word ($s_t \in S$) find the shortest chain of words ($C$) where one letter differs between consecutive words in the chain and the first and last words in the chain are $s_0$ and $s_t$ respectively.

Eg $S = [cat, cab, car, tat, tar, bar], s_0 = cat, s_t = tar $
                      $ => C = [cat -> car -> bar -> tar]$

Top level solution

To solve this programatically, we can see that this is a graph programming problem - we can build a graph representing the data then find the shortest path within the graph from $s_0$ to $s_t$.


Scala has no graph implementation in the standard collections, but there is a neat little project called scala-graph which you can use.

def computeEditDistance(start: String, end: String, dictionary: Set[String]): Option[Int] = {
  val graph = Graph.from(dictionary, computeEdges(dictionary))
  val path = graph.get(start).shortestPathTo(graph.get(end))
  path.map(_.edges.size)
}

How to compute the edges

The interesting part is the computeEdges function. Here is a naive implementation:

private def computeEdgesSlowly(dictionary: Set[String]): List[UnDiEdge[String]] = {
  val (_, edges) 
     = dictionary.foldLeft (dictionary.drop(1), List.empty[UnDiEdge[String]]) {
        case (acc, word) =>
          val (unvisitedWords, edgeList) = acc
          val edgesForThisWord = unvisitedWords.collect { 
            case (w) if differsByOneLetter(w, word) 
               => word ~ w 
          }
          (unvisitedWords.drop(1), edgeList ++ edgesForThisWord)
      }
  edges
}

For every word in the list we check it against every other unvisisted word in the list meaning that this algorithm is O(n^2) where n = the number of words in the dictionary.

Eg

cat is compared to  [ cab, car, tat, tar, bar ]
cab is compared to [ car, tat, tar, bar ]
car is compared to  [ tat, tar, bar ]
tat is compared to   [ tar, bar ]
tar is compared to   [ bar ]

Cleverer algorithm for computing edges

It is possible to compute the edges in O(n) which is a huge improvement on the implementation above. :D :D

Example:  [ cat, cab, car, tat, tar, bar ]

Step 1: 

Firstly we compute 'subs' for each word in the dictionary

    'cat' ->  [ '?at'  , 'c?t' ,  'ca?' ]
    'cab' -> [ '?ab' , 'c?b' ,  'ca?' ]
    etc...

val mapOfSubs = dictionary.map { word =>
  val subs = (0 until word.length) map { case i =>
    word.patch(i, Seq('?'), 1)
  }
  word -> subs
}.toMap

Step 2:

We build a hashmap from the subs

    '?at' ->  [ 'cat', 'tat' ]
    'c?t' ->  [ 'cat' ]
    'ca?' -> [ 'cat', 'cab', 'car' ]
    '?ab' -> [ 'cab' ]
    'c?b' -> [ 'cab' ]
    etc...

val cachedMap = mutable.HashMap.empty[String, Set[String]]
dictionary.foreach { word =>
  val subs = mapOfSubs.get(word)
  subs.foreach(o => o.foreach {
    sub => 
      cachedMap(sub) 
        = Set(word) ++ cachedMap.getOrElse(sub, Set.empty[String])
  })
}

Step 3:

Now we build up the list of edges. For each word, we get 3 subs for each word. Then we look up each of these 3 subs in the above hashmap to get all the nodes for which the current words has an edge with. We keep a list of nodes we have visited so that we don't add each node twice (the edges are undirected).

val visited = mutable.Seq.empty[String]
dictionary.flatMap { word =>
  word :+ visited
  val subs = mapOfSubs(word)
  subs.flatMap { s =>
    val links = cachedMap(s)
    links.collect { 
      case l if !visited.contains(l) 
        => word ~ l // ~ = undirected edge    }
  }
}.toSeq

Full code is here.

Tree algorithms in Scala: DFS, BFS and Height of binary tree

Tree:

         3
   5          2
1   4      6

Preorder Traversal

root -> left subtree -> right subtree
3 ->  5 -> 1 -> 4 -> 2 -> 6

def preOrder(node: Node): Unit = {
  if (node != null){
    print(node.value + " ")
    preOrder(node.left)
    preOrder(node.right)
  }
}

def iterativePreOrder(root: Node): Unit = {
  val stack = new mutable.Stack[Node]()
  var node = root
  while (stack.nonEmpty || node != null) {
    if (node != null) {
      print(node.value + " ")
      if (node.right != null) stack.push(node.right)
      node = node.left
    }
    else {
      node = stack.pop()
    }
  }
}

InOrder Traversal

left subtree -> root -> right subtree
1 -> 5 -> 4 -> 3 -> 6 -> 2

def inOrder(node: Node): Unit = {
  if (node != null){
    inOrder(node.left)
    print(node.value + " ")
    inOrder(node.right)
  }
}

def iterativeInOrder(root: Node): Unit = {
  val stack = new mutable.Stack[Node]()
  var node = root
  while (stack.nonEmpty || node != null) {    if (node != null) {      stack.push(node)      node = node.left    }    else {      node = stack.pop()      print(node.value + " ")      node = node.right    }  }
}

PostOrder Traversal

left subtree -> right subtree -> root
1 -> 4 -> 5 -> 6 -> 2 -> 3

def postOrder(node: Node): Unit = {
  if (node != null) {
    postOrder(node.left)
    postOrder(node.right)
    print(node.value + " ")
  }
}

def iterativePostOrder(root: Node): Unit = {
  val stack = new mutable.Stack[Node]()
  var node = root
  var prev: Node = null  while (stack.nonEmpty || node != null) {
    if (node != null) {
      stack.push(node)
      node = node.left
    }
    else {
      node = stack.pop()
      if (node.right != null && prev != node.right) {
        stack.push(node)
        node = node.right
      }
      else {
        print(node.value + " ")
        prev = node
        node = null      }
    }
  }
}

Breadth first search

3 -> 5 -> 2 -> 1 -> 4 -> 6 

def bfs(root: Node): Unit = {
  val q = new mutable.Queue[Node]()
  var node = root

  q.enqueue(node)
  while (q.nonEmpty) {
    node = q.dequeue()
    print(node.value + " ")
    if (node.left != null) q.enqueue(node.left)
    if (node.right != null) q.enqueue(node.right)
  }
}

Height of a binary tree

def height(root: Node): Int = {
  val q = new mutable.Queue[(Node, Int)]()
  var node = root

  q.enqueue((node, 1))
  var max = 1  while (q.nonEmpty) {
    val d = q.dequeue()
    node = d._1

    if (node.left != null) {
      max = d._2 +1      q.enqueue((node.left, max))
    }
    if (node.right != null) {
      max = d._2 +1      q.enqueue((node.right, max))
    }
  }
  max
}