Статьи

Решение проблемы «ведра с водой» с помощью Scala

Февраль 8, 2019

Недавно я натолкнулся на загадку, которая в этой книге называлась проблемой «ведра с водой», и это меня совершенно озадачило.

У вас есть 12-галлонное ведро, 8-галлонное ведро и 5-галлонное ведро. 12-литровое ведро заполнено водой, а два других пусты. Не используя дополнительную воду, как вы можете разделить двенадцать галлонов воды поровну, чтобы в двух из трех ведер было ровно 6 галлонов воды?

Я и мой племянник потратили немало времени, пытаясь ее решить, и в конечном итоге сдались.

Тогда я вспомнил, что видел программное решение для аналогичной головоломки, разрабатываемой в курсе «Принципы функционального программирования в Scala» Мартина Одерского.

Это суть решения, полностью скопированного с курса:

01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
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
  }
}
01
02
03
04
05
06
07
08
09
10
11
12
13
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)))
  }
}

и запуск этой программы выплевывает следующее 7-шаговое решение! (индекс 0 — ведро на 12 галлонов, 1 — ведро на 8 галлонов и 2 — ведро на 5 галлонов)

1
2
3
4
5
6
7
Pour(0,1)
Pour(1,2)
Pour(2,0)
Pour(1,2)
Pour(0,1)
Pour(1,2)
Pour(2,0)

Если вы заинтересованы в том, чтобы узнать больше о коде этого решения, лучше всего следовать 7-й неделе курса Coursera, который я связал выше, Мартин Одерски проделывает фантастическую работу, казалось бы, находя решение на лету! ,

Ссылка: Решение проблемы «ведер с водой» с использованием Scala от нашего партнера по JCG Биджу Кунджуммен в блоге » все и вся» .
35
Share: