Over a million developers have joined DZone.
{{announcement.body}}
{{announcement.title}}

Solving "Water buckets" Problem Using Scala

DZone's Guide to

Solving "Water buckets" Problem Using Scala

· Java Zone ·
Free Resource

Download Microservices for Java Developers: A hands-on introduction to frameworks and containers. Brought to you in partnership with Red Hat.

I recently came across a puzzle called the "Water Buckets" problem in  book, which totally stumped me. 

You have a 12-gallon bucket, an 8-gallon bucket and a 5-gallon bucket. The 12-gallon bucket is full of water and the other two are empty. Without using any additional water how can you divide the twelve gallons of water equally so that two of the three buckets have exactly 6 gallons of water in them?


I and my nephew spent a good deal of time trying to solve it and ultimately gave up.

I remembered then that I have seen a programmatic solution to a similar puzzle being worked out in the "Functional Programming Principles in Scala" Coursera course by Martin Odersky.

This is the gist to the solution completely copied from the course:

package bucket
 
case class Pouring(capacity: Vector[Int], initialState: Vector[Int]){
  type State = Vector[Int]
		  
  trait Move {
    def change(state: State): State
  }
  
  case class Pour(from: Int, to: Int) extends Move {
    def change(state: State) = {
      val amount = state(from) min (capacity(to) - state(to))
      state updated (from, state(from) - amount) updated (to, state(to) + amount)
    }
  }
  
  class Path(history: List[Move], val endState: State) {
    def extend(move: Move) = new Path(move :: history, move change endState)
    override def toString = (history.reverse mkString " ") + "-->" + endState
  }
  
  val glasses = 0 until capacity.length
  
  val moves = for {
    from <- glasses
    to <- glasses
    if (from != to)
  } yield Pour(from, to)
  
  val initialPath = new Path(Nil, initialState )
 
  def from(paths: Set[Path], explored: Set[State]): Stream[Set[Path]] = {
    if (paths.isEmpty) Stream.empty
    else {
      val more = for {
        path <- paths
        next <- moves map path.extend
        if !(explored contains next.endState)
      } yield next
      
      paths #:: from(more, explored ++ (more map (_.endState)))
    }
  }
  
  val pathSets = from(Set(initialPath), Set(initialState))
  
  def solution(target: State): Stream[Path] = {
    for {
      pathSet <- pathSets
      path <- pathSet
      if (path.endState == target)
    } yield path
  }
}
package bucket
 
import org.scalatest.FunSuite
import org.junit.runner.RunWith
import org.scalatest.junit.JUnitRunner
 
@RunWith(classOf[JUnitRunner])
class PouringTest extends FunSuite {
  test("Solution to the 12-gallon, 8-gallon, 5-gallon problem") {
    val p = Pouring(Vector(12, 8, 5), Vector(12, 0, 0))
    println(p.solution(Vector(6, 6, 0)))
  }
}

and running this program spits out the following 7 step solution! (index 0 is the 12-gallon bucket, 1 is the 8-gallon bucket and 2 is the 5-gallon bucket)

Pour(0,1)
Pour(1,2)
Pour(2,0)
Pour(1,2)
Pour(0,1)
Pour(1,2)
Pour(2,0)

If you are interested in learning more about the code behind this solution, the best way is to follow the week 7 of the Coursera course that I have linked above, Martin Odersky does a fantastic job of seemingly coming up with a solution on the fly!.

Download Building Reactive Microservices in Java: Asynchronous and Event-Based Application Design. Brought to you in partnership with Red Hat

Topics:

Published at DZone with permission of

Opinions expressed by DZone contributors are their own.

{{ parent.title || parent.header.title}}

{{ parent.tldr }}

{{ parent.urlSource.name }}