続: 『続: Rubyでかの有名な水の移し替えパズルを解く』(再帰使わない書き方とか諸々)

# はじめに
まさか[「Rubyでかの有名な水の移し替えパズルを解く」](https://qiita.com/jerrywdlee/items/c7bbcbb6c68e37e7ef71)シリーズの続々編まで書けると思いませんでした。

先日[続編の方](https://qiita.com/jerrywdlee/items/35d93bba3224e48da039)で、**深さ優先探索**は再帰で書きましたが、再帰の深さによってパフォーマンスが心配で、連休を乗じてイテレーション(繰り返し処理、ループ)での書き方も投稿いたします。

# 前回までのあらすじ
https://qiita.com/jerrywdlee/items/c7bbcbb6c68e37e7ef71

https://qiita.com/jerrywdlee/items/35d93bba3224e48da039


# 方法
## (単純の)深さ優先探索

```rb
require "./jug" # 容器クラス
require "./print_result" # 結果印字用メソッド

# 深さ優先探索(イテレーション)
# @param [Int] s_max 容器(小)の最大容量
# @param [Int] l_max 容器(大)の最大容量
# @param [Int] t_vol 取りたい水の量
# @return [Hash] 結果のノード: `{ steps: 操作ステップ, vols: 途中の容量変化 }`
# @return [nil] 結果見つからない際は `nil` を返す
def dfs(s_max, l_max, t_vol, &block)
  stack = [{ steps: [], vols: [[0, 0]] }] # スタックにルートノードをセットアップ

  loop do
    return nil if stack.empty? # 結果が見つからない(処理するノードがもうない)時

    curr_node = stack.pop # 処理したいノードを取り出す
    s_vol, l_vol = curr_node[:vols].last # それぞれの容器の現在の容量を取得
    return curr_node if s_vol == t_vol || l_vol == t_vol # 結果見つかった時は結果ノードを返す

    yield curr_node if block_given? # カウンターや途中の処理状況を確認するためのHook

    # 6種類の操作をラベリングし、それぞれ処理を行う
    # 無効な操作が発生した場合は結果次第排除する
    %w[SE LE SF LF S2L L2S].each do |o_label|
      jug_s = Jug.new(s_max, s_vol); jug_l = Jug.new(l_max, l_vol) # 2つの容器の初期化
      pour_vol = nil # もし該当操作は「注ぐ」の場合、注いだ量の初期化
      case o_label
      when 'SE' then jug_s.empty
      when 'LE' then jug_l.empty
      when 'SF' then jug_s.fill
      when 'LF' then jug_l.fill
      when 'S2L' then pour_vol = jug_s.pour jug_l
      when 'L2S' then pour_vol = jug_l.pour jug_s
      end

      # 2つの容器に入った水の量の組み合わせは既に存在した場合、
      # 無限ループに入ったと判断し、このノードを切り捨てる
      next if curr_node[:vols].include? [jug_s.vol, jug_l.vol]

      # 処理結果を新しいノードとして追加
      stack << {
        steps: curr_node[:steps] + [o_label + pour_vol.to_s],
        vols: curr_node[:vols] + [[jug_s.vol, jug_l.vol]],
      }
    end
  end

  nil # 見つからない時はnilを返す
end
```

深さ優先探索で再帰を使わない場合は、手書きでスタックを管理する必要があります。
[「幅優先探索」](https://qiita.com/jerrywdlee/items/35d93bba3224e48da039#%E5%B9%85%E5%84%AA%E5%85%88%E6%8E%A2%E7%B4%A2)に似たような書き方となりますが、幅優先探索方は`Queue`(FIFO)で探索中のノードを保持し、深さ優先探索は`Stack`(LIFO)でノードを保持します。

ちなみに、`print_result`の中身は **[こちら](https://qiita.com/jerrywdlee/items/35d93bba3224e48da039#%E5%AE%9F%E8%A1%8C%E7%B5%90%E6%9E%9C%E3%81%AE%E6%95%B4%E5%BD%A2)** です。

## 結果確認

```rb
s_max, l_max, t_vol = [3, 5, 4]; cnt = 0
res = dfs(s_max, l_max, t_vol) { cnt += 1 }
print_result(res, s_max, l_max)
puts "cnt = #{cnt}"
```

実行してみると、当たり前ですが、最適解ではないものが返されました。
面白いことで、[再帰の方で書いたメソッドと違う結果](https://qiita.com/jerrywdlee/items/35d93bba3224e48da039#%E5%AE%9F%E8%A1%8C%E7%B5%90%E6%9E%9C-1)になりました。

見た感じ、再帰で書いた方とイテレーションで書いた方、逆サイドから処理を行うようです。

```
Step1: 5L容器を満タンにした (3L容器: 0L, 5L容器: 5L)
Step2: 5L容器から3L容器へ3Lを注いだ (3L容器: 3L, 5L容器: 2L)
Step3: 5L容器を満タンにした (3L容器: 3L, 5L容器: 5L)
Step4: 5L容器を空っぽにした (3L容器: 3L, 5L容器: 0L)
Step5: 3L容器から5L容器へ3Lを注いだ (3L容器: 0L, 5L容器: 3L)
Step6: 3L容器を満タンにした (3L容器: 3L, 5L容器: 3L)
Step7: 3L容器から5L容器へ2Lを注いだ (3L容器: 1L, 5L容器: 5L)
Step8: 5L容器を空っぽにした (3L容器: 1L, 5L容器: 0L)
Step9: 3L容器から5L容器へ1Lを注いだ (3L容器: 0L, 5L容器: 1L)
Step10: 3L容器を満タンにした (3L容器: 3L, 5L容器: 1L)
Step11: 3L容器から5L容器へ3Lを注いだ (3L容器: 0L, 5L容器: 4L)

cnt = 11
```

ちなみに答えの出ない組み合わせ(3, 6, 4)で探索すると、同じ結果になります。

```rb
s_max, l_max, t_vol = [3, 6, 4]; cnt = 0
res = dfs(s_max, l_max, t_vol) { cnt += 1 }
print_result(res, s_max, l_max)
puts "cnt = #{cnt}"
```

```
結果見つかりませんでした
cnt = 31
```

## 反復深化深さ優先探索

```rb
require "./jug" # 容器クラス
require "./print_result" # 結果印字用メソッド

# 反復深化深さ優先探索
# @param [Int] s_max 容器(小)の最大容量
# @param [Int] l_max 容器(大)の最大容量
# @param [Int] t_vol 取りたい水の量
# @return [Hash] 結果のノード: `{ steps: 操作ステップ, vols: 途中の容量変化 }`
# @return [nil] 結果見つからない際は `nil` を返す
def iddfs_v2(s_max, l_max, t_vol, &block)
  root = { steps: [], vols: [[0, 0]] } # ルートノードを初期化
  stack = []
  9999.times do |depth| # 無限ループ対策
    res = dls(s_max, l_max, t_vol, depth, root, &block)
    return res if res
  end

  nil # 結果見つからない時はnilを返す
end

# 深さ制限探索(イテレーション)
# @param [Int] s_max 容器(小)の最大容量
# @param [Int] l_max 容器(大)の最大容量
# @param [Int] t_vol 取りたい水の量
# @param [Int] depth 制限深さ
# @param [Hash] root ルートノード: `{ steps: 操作ステップ, vols: 途中の容量変化 }`
# @return [Hash] 結果ノード: `{ steps: 操作ステップ, vols: 途中の容量変化 }`
# @return [nil] 結果見つからない際は `nil` を返す
def dls(s_max, l_max, t_vol, depth, root , &block)
  stack = [root] # スタックにルートノードをセットアップ

  loop do
    return nil if stack.empty? # 結果が見つからない(処理するノードがもうない)時

    curr_node = stack.pop # 処理したいノードを取り出す
    s_vol, l_vol = curr_node[:vols].last # それぞれの容器の現在の容量を取得
    return curr_node if s_vol == t_vol || l_vol == t_vol # 結果見つかった時は結果ノードを返す

    curr_depth = curr_node[:vols].size - 1 # 処理対象のノードの深さを今までの処理結果より算出
    next if curr_depth >= depth # 深度達した際は処理しない

    yield curr_node if block_given? # カウンターや途中の処理状況を確認するためのHook

    # 6種類の操作をラベリングし、それぞれ処理を行う
    # 無効な操作が発生した場合は結果次第排除する
    %w[SE LE SF LF S2L L2S].each do |o_label|
      jug_s = Jug.new(s_max, s_vol); jug_l = Jug.new(l_max, l_vol) # 2つの容器の初期化
      pour_vol = nil # もし該当操作は「注ぐ」の場合、注いだ量の初期化
      case o_label
      when 'SE' then jug_s.empty
      when 'LE' then jug_l.empty
      when 'SF' then jug_s.fill
      when 'LF' then jug_l.fill
      when 'S2L' then pour_vol = jug_s.pour jug_l
      when 'L2S' then pour_vol = jug_l.pour jug_s
      end

      # 2つの容器に入った水の量の組み合わせは既に存在した場合、
      # 無限ループに入ったと判断し、このノードを切り捨てる
      next if curr_node[:vols].include? [jug_s.vol, jug_l.vol]

      # 処理結果を新しいノードとして追加
      stack << {
        steps: curr_node[:steps] + [o_label + pour_vol.to_s],
        vols: curr_node[:vols] + [[jug_s.vol, jug_l.vol]],
      }
    end
  end

  nil # 見つからない時はnilを返す
end
```

## 結果確認

```rb
s_max, l_max, t_vol = [3, 5, 4]; cnt = 0
res = iddfs_v2(s_max, l_max, t_vol) { |r| cnt += 1; }
print_result(res, s_max, l_max)
puts "cnt = #{cnt}"
```

実行してみると、ちゃんと最適解を見つかりました。こちらも面白いことに、処理回数は[再帰の方](https://qiita.com/jerrywdlee/items/35d93bba3224e48da039#%E5%AE%9F%E8%A1%8C%E7%B5%90%E6%9E%9C-2)よりやや少なくなりましたが、[幅優先探索](https://qiita.com/jerrywdlee/items/35d93bba3224e48da039#%E5%AE%9F%E8%A1%8C%E7%B5%90%E6%9E%9C)の47回よりは多いです。


```
Step1: 5L容器を満タンにした (3L容器: 0L, 5L容器: 5L)
Step2: 5L容器から3L容器へ3Lを注いだ (3L容器: 3L, 5L容器: 2L)
Step3: 3L容器を空っぽにした (3L容器: 0L, 5L容器: 2L)
Step4: 5L容器から3L容器へ2Lを注いだ (3L容器: 2L, 5L容器: 0L)
Step5: 5L容器を満タンにした (3L容器: 2L, 5L容器: 5L)
Step6: 5L容器から3L容器へ1Lを注いだ (3L容器: 3L, 5L容器: 4L)

cnt = 62
```

## 参考

- [[アルゴリズム(Ruby)]深さ優先探索・幅優先探索の解説](https://jaigotec.com/algorithm_dfs-bfs/)
- [アルゴリズム初心者向けの基礎と入門(C#, Pythonとか)](https://algoful.com/Archive/Algorithm/DFS)