1

scalaを使用してcodechefから注ぐ水の問題を解決しようとしています。問題文は次のとおりです。

2 つの容器があり、一方は 1 リットルの水を収容でき、もう一方は b リットルの水を収容できる場合、一方の容器で正確に c リットルの水を得るために必要なステップ数を決定します。

最初は両方の容器が空です。次の操作は「ステップ」としてカウントされます。

emptying a vessel,
filling a vessel,
pouring water from one vessel to the other, without spilling, until one of the vessels is either full or empty.

入力

整数 t、1<=t<=100 はテスト ケースの数を示し、その後に t セットの入力データが続き、それぞれが 3 つの正の整数 a (最初のコンテナーが保持できるリットル数)、b (数2 番目のコンテナが保持できる水のリットル数)、および c (1 つの容器に収容できる最終的な水のリットル数)、40000 を超えない、別々の行で指定します。

出力

入力データの各セットについて、c リットルを取得するために必要な最小ステップ数を出力するか、それが不可能な場合は -1 を出力します。

例 入力例:

2 5 2 3 2 3 4

出力例:

2 -1

私はグラフ理論の問題としてこの問題に取り組んでいます。コンテナーの初期構成が であるとすると(0, 0)、次の操作を適用してコンテナーの次の状態を取得します。

FillA、FillB、PourAtoB、PourBtoA、EmptyA、EmptyBターゲットに到達するまで再帰的に。

私のコードは次のとおりです。

import scala.collection.mutable.Queue

def pour(initA:Int, initB:Int, targetCapacity:Int) {
    var pourCombinations = new scala.collection.mutable.HashMap[(Int, Int),Int]
    val capacityA = initA
    val capacityB = initB

    val processingQueue = new Queue[(Int, Int, Int, Int)]

    def FillA(a:Int, b:Int) = {
      (capacityA, b)                    
    }
    def FillB(b:Int, a:Int) = {
      (a, capacityB)
    }   
    def PourAtoB(a:Int, b:Int): (Int, Int) = {
      if((a == 0) || (b == capacityB)) (a, b) 
      else PourAtoB(a - 1, b + 1) 
    }
    def PourBtoA(b:Int, a:Int): (Int, Int) = { 
      if((b == 0) || (a == capacityA)) (a, b) 
      else PourBtoA(b - 1, a + 1)
    }
    def EmptyA(a:Int, b:Int) = {
      (0, b)
    }
    def EmptyB(a:Int, b:Int) = {
      (a, 0)
    }

    processingQueue.enqueue((0, 0, targetCapacity, 0))
    pourCombinations((0, 0)) = 0


    def pourwater(a:Int, b:Int, c:Int, numSteps:Int): Int = {
        println(a + ":" + b + ":" + c + ":" + numSteps)

        if((a == c) || (b == c)) {return numSteps}

        if(processingQueue.isEmpty && (pourCombinations((a,b)) == 1)) {return -1}

        //Put all the vals in a List of tuples
        val pStateList = scala.List(FillA(a, b), FillB(a, b), PourAtoB(a, b), PourBtoA(b, a), EmptyA(a, b), EmptyB(a, b))       

        pStateList.foreach{e =>
          {
            if(!pourCombinations.contains(e)) {
              pourCombinations(e) = 0
              processingQueue.enqueue((e._1, e._2, c, numSteps + 1))
            }
          }
        }   
        pourCombinations((a, b)) = 1
        val processingTuple = processingQueue.dequeue()
        pourwater(processingTuple._1, processingTuple._2, processingTuple._3, processingTuple._4)

     }
     val intialvalue = processingQueue.dequeue()
     pourwater(intialvalue._1, intialvalue._2, intialvalue._3, intialvalue._4)
}

これにはいくつかの問題があります。まず、再帰ステップの基本ケースが適切に設定されているかどうかがわかりません。また、この問題を解決するために適切な Scala 規則を使用していない可能性もあります。numStepsまた、実行が終了したら、 pour 関数が を返すようにします。現時点ではそれを行っていません。

誰かが私のコードを調べて、私のアプローチの間違いを指摘できれば素晴らしいことです。

ありがとう

4

0 に答える 0