スポンサーサイト

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

[Scala]水差し問題を幅優先探索と深さ優先探索で

大学の授業で水差し問題をプログラムで解くという話が出てきたので、Scalaの勉強がてら書いてみました。
まずはメインクラス
// Main.scala
object Main {
  def main(args: Array[String]): Unit = {
    // WaterClassに、ゴールの状態と探索の種類("wide" or "deep")を引数で与えて初期化
    val water = new WaterClass((2, 0), "wide")
    // 探索開始
    water.search_start
    water.load_of_goal
    println("Goal!!")
  }
}

次に、水差し問題を解く本体のWater.scala。

// Water.scala
import scala.collection.mutable.HashMap // HashMapを使用するのに必要

class WaterClass(goal: (Int, Int), category: String)
{
  val cup_goal = goal            // ゴールの状態
  val left_max = 4               // 左側の壷に入る水の最大量
  val right_max = 3              // 右側の壷に入る水の最大量
  val search_category = category // 探索方法の種類
  val start = (0, 0)             // スタート時のコップの状態
  var goal_in = false            // ゴールしたかどうかのフラグ
  var stayList = List(start)    // コップの状態。現在左右ともに0
  var opendMap = new HashMap[(Int, Int), (Int, Int)]
  opendMap += start -> start

  // 探索開始
  def search_start(): Unit = {
    // ゴールが見つかるまで無限ループ
    while(true){
      println(stayList)
      var now = stayList.head    // コップの状態候補のリストから、先頭の要素を取り出す
      stayList = stayList.tail   // リストの中から、先頭の要素以外のものを新しいリストとする
      var left  = now._1         // Tuple形式で保存されているコップの左側の状態を入力
      var right = now._2         // Tuple形式で保存されているコップの右側の状態を入力
      r1(left, right)            // 手順R1へ、コップの状態を渡し判定
      r2(left, right)            // 手順R2へ、(以下略)
      r3(left, right)
      r4(left, right)
      r5(left, right)
      r6(left, right)
      r7(left, right)
      r8(left, right)
      if(goal_in){
        println("ゴールを発見しました")
        return
      }
    }
  }

  // 探索が幅優先か深さ優先かにより、リストの結合順を切り替える関数
  def setting_cup(set: (Int, Int)): Unit = {
    if(search_category == "wide") stayList = stayList:::List(set)
    if(search_category == "deep") stayList = List(set):::stayList
    if(set == cup_goal)
      goal_in = true
  }

  // カップの状態が、過去になったことがあるかどうかをチェックする関数
  def cheak_opened(set: (Int, Int)): Boolean = {
    for(key <- opendMap.keySet){
      if(key == set)
        return true
    }
    return false
  }

  // R1:左の水差しが満杯(4リットル)ではないなら、それを満杯にする
  def r1(left: Int, right: Int): Unit ={
    if(left < left_max){
      val set = (left_max, right)
      if(cheak_opened(set))
        return
      opendMap += set -> (left, right)
      setting_cup(set)
    }
  }

  // R2:右の水差しが満杯(3リットル)ではないなら、それを満杯にする
  def r2(left: Int, right: Int): Unit ={
    if(right < right_max){
      val set = (left, right_max)
      if(cheak_opened(set))
        return
      opendMap += set -> (left, right)
      setting_cup(set)
    }
  }

  // R3:左の水差しに少しでも水が入っているならそれを空にする
  def r3(left: Int, right: Int): Unit ={
    if(left > 0){
      val set = (0, right)
      if(cheak_opened(set))
        return
      opendMap += set -> (left, right)
      setting_cup(set)
    }
  }

  // R4:右の水差しに少しでも水が入っているならそれを空にする
  def r4(left: Int, right: Int): Unit ={
    if(right > 0){
      val set = (left, 0)
      if(cheak_opened(set))
        return
      opendMap += set -> (left, right)
      setting_cup(set)
    }
  }

  // R5:左右の水の合計が左の水差しの上限以上、かつ左の水差しが満杯でないとき、
  //    右の水差しの水を左の水差しに入れて満杯にする。
  def r5(left: Int, right: Int): Unit ={
    if((left + right) >= left_max && left < left_max){
      val set = (left_max, left + right - left_max)
      if(cheak_opened(set))
        return
      opendMap += set -> (left, right)
      setting_cup(set)
    }
  }

  // R6:左右の水の合計が右の水差しの上限以上、かつ右の水差しが満杯でないとき、
  //    左の水差しの水を右の水差しに入れて満杯にする
  def r6(left: Int, right: Int): Unit ={
    if((left + right) >= right_max && right < right_max){
      val set = (left + right - right_max, right_max)
      if(cheak_opened(set))
        return
      opendMap += set -> (left, right)
      setting_cup(set)
    }
  }

  // R7:左右の水の合計が左の水差しの上限以下、かつ右の水差しが空でないとき、
  //    右の水差しの水をすべて左の水差しに入れる
  def r7(left: Int, right: Int): Unit ={
    if((left + right) <= left_max && right > 0){
      val set = (left + right, 0)
      if(cheak_opened(set))
        return
      opendMap += set -> (left, right)
      setting_cup(set)
    }
  }

  // R8:左右の水の合計が右の水差しの上限以下、かつ左の水差しが空でないとき、
  //    左の水差しの水をすべて右の水差しに入れる
  def r8(left: Int, right: Int): Unit ={
    if((left + right) <= right_max && left > 0){
      val set = (0, left + right)
      if(cheak_opened(set))
        return
      opendMap += set -> (left, right)
      setting_cup(set)
    }
  }

  // ゴールから逆算して、ゴールまでの過程を表示する
  def load_of_goal(): Unit = {
    var gList = List(cup_goal)
    while(true){
      gList = List(opendMap(gList.head)):::gList
      if(gList.head == start){
        for(stay <- gList)
          println(stay + "\n ↓ ")
        return
      }
    }
  }
}

うーん、なんか汚いソースですね。修行せねば。
スポンサーサイト

テーマ : プログラミング - ジャンル : コンピュータ

上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。