5/21/09
My take on 99 problems in Scala (23 to 26)
Note: in all this and the previous solutions, I've left out (most of the time) boundary conditions checks, to keep the code simple and as elegant as possible.
P23: Random select. We reuse P20 (removeAt) and remove a random element of the list recursively.
//P23 def randomSelect[A](n: Int, xs: List[A]): List[A] = (n, xs) match {
case (_, Nil) => Nil
case (0, _) => Nil
case (_, _) => {
val x = removeAt(new Random().nextInt(xs.size), xs)
x._2 :: randomSelect(n - 1, x._1)
}
}P24: lotto. we create a list (well, actually is a range converted to a list) of the numbers and use P23 to select a random draw.
//P24
def lotto(n:Int,max:Int):List[Int] =randomSelect(n,(1 to max).toList)
P25: random permute. That's easy: we use P23 to do a randomSelect on the whole list
//P25
def randomPermute[A](xs:List[A]):List[A] =randomSelect(xs.size,xs)
P26: combinations. That one wasn't straightforward, I actually had to think! :)
But the solution can be defined recursively:
to get the combinations of size n, take one element of the set and append it to all the combinations of sets of size n-1 of the remaining elements, union the combinations of size n of the remaining elements.
I had to create an auxiliary function that "lift" a list into a list of lists, (kind of the opposite of flatten).
//P26 def combinations[A](n: Int, xs: List[A]): List[List[A]] = {
def lift[A](xs: List[A]): List[List[A]] = xs.foldLeft(List[List[A]]())((ys, y) => (List(y) :: ys))
(n, xs) match {
case (1, ys) => lift(ys)
case (i, xs) if (i == xs.size) => xs :: Nil
case (i, ys) => combinations(i - 1, ys.tail).map(zs => ys.head :: zs) ::: combinations(i, ys.tail)
}
}4/28/09
My take on 99 problems in Scala (first 22)
Nice stuff to get your skills up to shape. It helped me to improve my understanding of folds, maps, flatMaps, zips, etc. Also I learned new pattern matching techniques (tuples and guards).
You must really give the exercises a shot!
Here are my solutions:
package exercises
object NinetyNine {
//P01
def last[A](xs: List[A]): A = xs match {
case x :: Nil => x
case x :: xs => last(xs)
case Nil => throw new NoSuchElementException
}
//P02
def penultimate[A](xs: List[A]): A = xs match {
case x :: y :: Nil => x
case x :: xs => penultimate(xs)
case _ => throw new NoSuchElementException
}
//P03
def nth[A](i: Int, xs: List[A]): A = xs match {
case x :: xs => if (i == 0) x else nth(i - 1, xs)
case _ => throw new NoSuchElementException
}
def nth2[A](i: Int, xs: List[A]): A = xs match {
case x :: xs if (i == 0) => x
case x :: xs if (i > 0) => nth(i - 1, xs)
case _ => throw new NoSuchElementException
}
//P04
def length[A](xs: List[A]): Int = xs match {
case x :: xs => 1 + length(xs)
case Nil => 0
}
//Although straight recursion is fun, using folds is more effective
// folds are abstractions for recursion over data structures
//P04
def length1[A](xs: List[A]): Int = xs.foldLeft(0)((a, b) => a + 1)
//P05
def reverse[A](xs: List[A]): List[A] = xs.foldLeft(Nil: List[A])((a, b) => b :: a)
//P06
def isPalindrome[A](xs: List[A]): Boolean = reverse(xs) == xs
//P07
def flatten[A](xs: List[List[A]]): List[A] = xs.foldRight(Nil: List[A])(
(xs, acc) => xs match {
case ys: List[A] => ys ::: acc
case y: A => y :: acc
})
//P08
def compress[A](xs: List[A]): List[A] =
xs.foldRight(List[A]())((y, ys) =>
if (ys != Nil && ys.head == y) ys else y :: ys)
//P09
def pack[A](xs: List[A]): List[List[A]] = xs match {
case Nil => Nil
case _ => xs.takeWhile(_ == xs.head) :: pack(xs.dropWhile(_ == xs.head)) //can use span too, see P13
}
//P10
def encode[A](xs: List[A]): List[(Int, A)] =
pack(xs).map(y => (y.length, y.head))
//P11
def encodeModified[A](xs: List[A]): List[Any] =
pack(xs).map(
y => if (y.length == 1) y.head else (y.length, y.head))
//Type safe version
def encodeModifiedTypSafe[A](xs: List[A]): List[Either[A, (Int, A)]] =
pack(xs).map(
y =>
if (y.length == 1) Left(y.head)
else Right(y.length, y.head))
//P12
def decode[A](xs: List[(Int, A)]): List[A] = {
def expand(i: Int, a: A): List[A] = if (i == 0) Nil else a :: expand(i - 1, a)
flatten(xs.foldRight(List[List[A]]())((y, ys) => expand(y._1, y._2) :: ys))
}
//is better with flatMap
def decode1[A](xs: List[(Int, A)]): List[A] =
xs.flatMap(ny => List.make(ny._1, ny._2))
//P13
def encodeDirect[A](xs: List[A]): List[(Int, A)] = xs match {
case Nil => Nil
case _ => {
val ys = xs.span(_ == xs.head)
(ys._1.length, xs.head) :: encodeDirect(ys._2)
}
}
//P14
def duplicate[A](xs: List[A]): List[A] =
xs.foldRight(Nil: List[A])((y, ys) => y :: y :: ys)
//is better with flatMap
def duplicate1[A](xs: List[A]): List[A] = xs.flatMap(y => y :: y :: Nil)
//P15
def duplicateN[A](n: Int, xs: List[A]): List[A] =
xs.foldRight(Nil: List[A])((y, ys) => (1 to n).toList.map(_ => y) ::: ys)
//is better with flatMap
def duplicateN1[A](n: Int, xs: List[A]): List[A] =
xs.flatMap(y => List.make(n, y))
//P16
def drop[A](n: Int, xs: List[A]): List[A] =
xs.zipWithIndex.filter(_._2 % n != 0).map(_._1)
//P17
def split[A](n: Int, xs: List[A]): (List[A], List[A]) =
xs.splitAt(n) // or (xs.take(n),xs.drop(n))
//ok, that was too easy, let's try recursion
def splitRec[A](n: Int, xs: List[A]): (List[A], List[A]) =
(n, xs) match {
case (0, _) => (Nil, xs)
case (_, y :: ys) => {
val rec = splitRec(n - 1, ys)
(y :: rec._1, rec._2)
}
case (_, Nil) => (xs, Nil)
}
//P18
def slice[A](s: Int, e: Int, xs: List[A]): List[A] =
xs.slice(s, e) // or xs.drop(s).take(e-s)
//with recursion
def sliceRec[A](s: Int, e: Int, xs: List[A]): List[A] =
(s, e, xs) match {
case (0, 0, xs) => Nil
case (0, _, y :: ys) => y :: sliceRec(0, e - 1, ys)
case (_, _, y :: ys) => sliceRec(s - 1, e - 1, ys)
}
//P19
def rotate[A](n: Int, xs: List[A]): List[A] = {
val s = split((if (n > 0) n else n + xs.length), xs)
s._2 ::: s._1
}
//P20
def removeAt[A](n: Int, xs: List[A]): (List[A], A) = {
val (heads, tails) = split(n, xs)
(heads ::: tails.tail, tails.head)
}
//P21
def insertAt[A](e: A, n: Int, xs: List[A]): List[A] = {
val (heads, tails) = split(n, xs)
heads ::: e :: tails
}
//with recursion
def insertRecAt[A](e: A, n: Int, xs: List[A]): List[A] =
(n, xs) match {
case (0, ys) => e :: ys
case (_, y :: ys) => y :: insertRecAt(e, n - 1, ys)
}
//P22
def range[A](s: Int, e: Int): List[Int] = (s to e).toList
//I don't think is the purpose of the exercise! Again, let's try recursion
def rangeRec(s: Int, e: Int): List[Int] = if (e - s == 0) e :: Nil else s :: rangeRec(s + 1, e)
//recursion and pattern matching with guards
//a little more readable
def rangeRecPm(s: Int, e: Int): List[Int] = (e - s) match {
case x if (x > 0) => s :: rangeRecPm(s + 1, e)
case x if (x == 0) => e :: Nil
case _ => error("Invalid range")
} }
12/18/08
Playing with Scala 5 ½: More variations
As James pointed out, the implicit conversion creates a new object every time we convert the Node to Ordered[Node], and although the JVM and the GC can deal pretty well with that kind of scenario, it will be better if we can avoid the creation of the object (BTW, the fact that Scala can leverage years of work on JIT optimizations is something that shouldn't be taken lightly... I still want tail call optimization, though)
We need to add the Ordered trait for Node somewhere in the hierarchy. The reasonable place is when we add the Weight trait (once we have weight we can compare the nodes):
classDfsNodeextendsNodeImplwithWeightwithOrdered[DfsNode]{
...
defcompare(y: Node): Int = this.weight.compare(y.weight)
}
Now we can compare the nodes by their weight: “lighter” nodes are before “heavier” nodes, but the comparation is not what we need for the priority queue, we need to reverse the the ordering.
The most immediate way is just reverse DfsNode's comparation function:
defcompare(y: Node): Int = -this.weight.compare(y.weight)
but this has the undesirable effect of reversing all the node comparations, and most of the time I'll bet we want to have the lighter nodes before the heavier ones, the reverse is counter-intuitive (and the potential source of nightmares). The solution? Let's create our particular flavor of DfsNode with the comparation reversed to use it in the PriorityQeue:
classPQNodeextendsDfsNode {
overridedefcompare(y: Node): Int = -super.compare(y)
}
And we just need to change our newNode method to return PQNodes instead of DfsNodes:
protecteddefnewNode: Node = newPQNode
For extra points on modularization, we can extract those changes and the code related to the algorithm in a subclass of DfsGraph.
Here is the complete code:
package dfs2;
abstract class Graph {
type Edge
type Node <: NodeIntf
abstract class NodeIntf {
def connectWith(node: Node): Edge
}
def nodes: Set[Node]
def edges: Set[Edge]
def addNode: Node
}
abstract class DirectedGraph extends Graph {
type Edge <: EdgeImpl
class EdgeImpl(origin: Node, dest: Node) {
def from = origin
def to = dest
}
class NodeImpl extends NodeIntf {
self: Node =>
def connectWith(node: Node): Edge = {
val edge = newEdge(this, node)
edges = edges + edge
edge
}
}
protected def newNode: Node
protected def newEdge(from: Node, to: Node): Edge
var nodes: Set[Node] =Set()
var edges: Set[Edge] =Set()
def addNode: Node = {
val node = newNode
nodes = nodes + node
node
}
}
trait Weight {
var weight= Float.PositiveInfinity
}
import scala.collection.mutable.PriorityQueue;
class DfsGraph extends DirectedGraph {
class DfsNode extends NodeImpl with Weight with Ordered[DfsNode]{
var previous: DfsNode = _
var label:String = _
var nodeEdges: Set[Edge] = Set()
override def connectWith(node: Node): Edge = {
val newEdge=super.connectWith(node)
nodeEdges = nodeEdges + newEdge
newEdge
}
def -->(n2:Node):DfsEdge =connectWith(n2)
override def toString()= label+ " w:"+weight
def compare(y: Node): Int = this.weight.compare(y.weight)
}
class DfsEdge(origin:Node, dest:Node) extends EdgeImpl(origin, dest) with Weight {
override def toString()= from.label+"-->"+to.label+" w:"+weight
}
def addNewNode(l:String):Node={
val newNode=super.addNode
newNode.label=l
newNode
}
type Node= DfsNode
type Edge= DfsEdge
protected def newEdge(from: Node, to: Node): Edge = new DfsEdge(from,to)
protected def newNode: Node = new DfsNode
}
class DijkstraSPGraph extends DfsGraph {
class PQNode extends DfsNode {
override def compare(y: Node): Int = -super.compare(y)
}
override protected def newNode: Node = new PQNode
def shortestPath(start: DfsNode, end: DfsNode) = {
val unvisited=new PriorityQueue[Node]()
unvisited++=(nodes)
start.weight=0
while (!unvisited.isEmpty) {
val vertx=unvisited.dequeue
for (v <- vertx.nodeEdges if canImprove(v)){
unvisited+improveDistance(v)
}
}
}
def canImprove(a:Edge)=(a.from.weight+a.weight< a.to.weight)
def improveDistance(a:Edge) ={
val v=a.to
v.weight=a.from.weight+a.weight
v.previous=a.from
v
}
def pathToStart(end:DfsNode):List[DfsNode] = {
if (end == null)
Nil
else
end :: pathToStart(end.previous)
}
}
object Example extends Application {
val graph = new DijkstraSPGraph
val n1=graph addNewNode "start"
val n2=graph addNewNode "n2"
val n3=graph addNewNode "n3"
val n4=graph addNewNode "n4"
val n5=graph addNewNode "n5"
val n6=graph addNewNode "end"
graph addNewNode "alone"
n1-->n2 weight=2
n1-->n3 weight=1
n2-->n4 weight=1
n3-->n4 weight=3
n2-->n5 weight=1
n4-->n6 weight=1
n5-->n6 weight=3
n1-->n6 weight=7
n1-->n4 weight=10
graph.shortestPath(n1,n6)
println("Path")
graph.pathToStart(n6).reverse.map(println(_))
}
12/14/08
Playing with Scala 5: improving code, use of views and comprehensions
The first change is replace the set with Scala's priority queue:
valunvisited=newPriorityQueue[Node]()
But as it is, it will not compile: the priority queue's signature is
class PriorityQueue[A](implicit view1ドル : (A) => Ordered[A])extends ResizableArray[A] with CloneableCollection
You need to provide an implicit conversion from the parameter type A to the type Ordered[A]. But nothing to worry about: is as easy as
implicitdefnode2ordered(n: Node): Ordered[Node] = newOrdered[Node] {
//reverse the comparation so highest priority = lower cost
defcompare(y: Node): Int = -(n.weight.compare(y.weight))
}
Look at the improveDistance function, it does two things: filters the nodes and updates the distance if we can improve it. I think is better if we split into two different functions, separating the filtering from the updating, so instead of:
defimproveDistance(a:Edge) ={
if(a.from.weight+a.weight<a.to.weight) {
a.to.weight=a.from.weight+a.weight
a.to.previous=a.from
}
}
we get:
defcanImprove(a:Edge)=(a.from.weight+a.weight<a.to.weight)
and
defimproveDistance(a:Edge) ={
a.to.weight=a.from.weight+a.weight
a.to.previous=a.from
a.to
}
Then, instead of a function map over the nodeEdges, we have to filter and then map:
vertx.nodeEdges.map(improveDistance(_))
is replaced by
vertx.nodeEdges.filter(canImprove(_))).map(improveDistance(_)
that gives a better picture of the steps involved.
As we need to add the updated nodes to the priority queue so they can “float” to the top, the line would look like:
unvisited++ (vertx.nodeEdges.filter(canImprove(_))).map(improveDistance(_))
But I don't really think the explicit use of map and filter helps readability.
Enter Scala's for comprehensions: we can replace the map/filter with a comprehension:
for (v <- vertx.nodeEdges if canImprove(v)){
unvisited+improveDistance(v)
}
Nothing fantastic, but an improvement, isn't it?
For future posts, I'm planning on generalizing the algorithm into a A* pathfinding with different heuristic functions... stay tuned!
2/3/08
Playing with Scala 4: Abstract types and Self-types
(well, there already was a generic graph and directed graph written in Scala... talking about reinventing the wheel!. The solution in Eric's comment works great too... is almost the same, but he was faster than me on coming up with it :D )
http://www.scala-lang.org/intro/abstracttypes.html
http://www.scala-lang.org/intro/selfrefs.html
I just used the same code, and changed the nodes and edges to use sets instead of lists (really, we don't care about the order)
The Scala example of Graph uses abstract types: it declares type Node and type Edge as type "parameters" to be defined by concrete implementation. Even more, by declaring type Node <: NodeIntf, we're restricting Node to be subtypes of NodeIntf. The declaration "self: Node =>" tells "I'll use self as Node type"
Then I declared the trait Weighted and extended the class DirectedGraph adding my extensions to NodeImpl and EdgeImpl to use weighted trait and add the node label and the previous property. I had to add a collection of the adjacent arcs, because they weren't in the original Graph and is easier for the algorithm. I overrode the connectWith method to keep track of the adjacent arcs as they're added, also I defined our --> operator to call the connectWith method.
class DfsNode extends NodeImpl with Weighted {
var label:String = _
var nodeEdges: Set[Edge] = Set()
override def connectWith(node: Node): Edge = {
val newEdge=super.connectWith(node)
nodeEdges = nodeEdges + newEdge
newEdge
}
def -->(n2:Node):DfsEdge =connectWith(n2)
override def toString()= label+ " w:"+weight
Edges are simpler, just add the weight and override toString:
class DfsEdge(origin:Node, dest:Node) extends EdgeImpl(origin, dest) with Weighted {
override def toString()= from.label+"-->"+to.label+" w:"+weight
}
All are enclosed in the DfsGraph class extending the DirectedGraph class, now I can assign the concrete types for Node and Edge:
type Node= DfsNode
type Edge= DfsEdge
The DirectedGraph class has a addNode method. To keep the DSL-ish quality of the construction of the graph, I added the method addNewNode to take the node label as parameter
def addNewNode(l:String):Node={
val newNode=super.addNode
newNode.label=l
newNode
}
So we can write: graph addNewNode "nodeLabel".
The example looks like this:
objectExampleextendsApplication {
valgraph = newDfsGraph
valn1=graphaddNewNode"start"
valn2=graphaddNewNode"n2"
valn3=graphaddNewNode"n3"
valn4=graphaddNewNode"n4"
valn5=graphaddNewNode"n5"
valn6=graphaddNewNode"end"
n1-->n2weight=2
n1-->n3weight=1
n2-->n4weight=1
n3-->n4weight=3
n2-->n5weight=1
n4-->n6weight=1
n5-->n6weight=3
graph.shortestPath(n1,n6)
println("Path")
graph.pathToStart(n6).reverse.map(println(_))
}
Pretty easy to read, don't you think?In the next post, I'll show you how we can use this algorithm to solve the "Abbott's revenge" type of maze. Ideally, I want to create an interpreter for the input, exploring Scala's features for creating language interpreters.
Here is the complete code:
package dfs2;
abstractclassGraph {
typeEdge
typeNode <: NodeIntf
abstractclassNodeIntf {
defconnectWith(node: Node): Edge
}
defnodes: Set[Node]
defedges: Set[Edge]
defaddNode: Node
}
abstractclassDirectedGraphextendsGraph {
typeEdge <: EdgeImpl
classEdgeImpl(origin: Node, dest: Node) {
deffrom = origin
defto = dest
}
classNodeImplextendsNodeIntf {
self: Node =>
defconnectWith(node: Node): Edge = {
valedge = newEdge(this, node)
edges = edges+edge
edge
}
}
protecteddefnewNode: Node
protecteddefnewEdge(from: Node, to: Node): Edge
varnodes: Set[Node] =Set()
varedges: Set[Edge] =Set()
defaddNode: Node = {
valnode = newNode
nodes = nodes+node
node
}
}
traitWeighted {
varweight= Float.PositiveInfinity
}
classDfsGraphextendsDirectedGraph{
classDfsNodeextendsNodeImplwithWeighted {
varprevious: DfsNode = _
varlabel:String = _
varnodeEdges: Set[Edge] = Set()
overridedefconnectWith(node: Node): Edge = {
valnewEdge=super.connectWith(node)
nodeEdges = nodeEdges+newEdge
newEdge
}
def-->(n2:Node):DfsEdge =connectWith(n2)
overridedeftoString()= label+" w:"+weight
}
classDfsEdge(origin:Node, dest:Node) extendsEdgeImpl(origin, dest) withWeighted {
overridedeftoString()= from.label+"-->"+to.label+" w:"+weight
}
defaddNewNode(l:String):Node={
valnewNode=super.addNode
newNode.label=l
newNode
}
typeNode= DfsNode
typeEdge= DfsEdge
protecteddefnewEdge(from: Node, to: Node): Edge =newDfsEdge(from,to)
protecteddefnewNode: Node = newDfsNode
defshortestPath(start: DfsNode, end: DfsNode) = {
varunvisited=nodes
start.weight=0
while (!unvisited.isEmpty){
valvertx=min(unvisited)
vertx.nodeEdges.map(improveDistance(_))
unvisited=unvisited-vertx
}
}
defimproveDistance(a:Edge) ={
if (a.from.weight+a.weight<a.to.weight) {
a.to.weight=a.from.weight+a.weight
a.to.previous=a.from
}
}
defmin(nodes: Set[DfsNode]): DfsNode = {
nodes.reduceLeft((a:DfsNode,b:DfsNode)=>if (a.weight<b.weight) aelseb )
}
defpathToStart(end:DfsNode):List[DfsNode] = {
if (end==null)
Nil
else
end::pathToStart(end.previous)
}
}