kairo-gokko (15-1) 通電 5



前回はエッジ 4本の場合の中でも限定的な配線パターンを対象に、それだけをなんとかする通電判定処理を作ってみました。 しかし、あのやり方ではすぐに行き詰まるでしょう。

エッジが 5本でも 100本でも解決できる汎用的な方法はないのでしょうか。


ふわふわしたことを言っていると話が進まないので、 適当な具体例を挙げて考えます。

f:id:sonota88:20200306051812p:plain

×印を付けたエッジではスイッチが OFF になっています。 また、線が交わっている箇所はすべてノードとします。

描いてみたはいいけど、どうすんのこれ。


えっと……これをまるごと扱おうとすると手に負えないので、 ぐちゃぐちゃした部分の真ん中あたりにある色を付けたエッジに着目します。

f:id:sonota88:20200306052046p:plain

たとえばこのエッジが通電するか、どうすれば分かるのか……?


こう考えてみました。

(1) まず着目しているエッジの片方の端点から出発してプラス極を目指す。 スイッチが OFF になっているエッジは通れないので迂回する。 プラス極まで辿りつければ OK。

f:id:sonota88:20200306052213p:plain

(2) 同じように、 着目しているエッジのもう片方の端点から出発してマイナス極を目指す。 マイナス極まで辿りつければ OK。

f:id:sonota88:20200306052333p:plain

(3) (1)(2) が両方とも OK なら着目しているエッジは通電すると判定する。

f:id:sonota88:20200306052538p:plain

緑の点線の経路が通れるのであれば、 端から端までずっとつながっているのですから、 たしかに着目しているエッジにも通電するだろう、 物理的にこの回路を作っても通電しそうだ、 と思えます。 直観としてはおかしくはない。

そうして1本のエッジについて判定できるようになったら、 あとはすべてのエッジについて繰り返せばよいのでは。

# こういうイメージ。この形に持っていきたい。

def edge_tuden_hantei(edge)
  is_tuden_plus  = ... # ここをどうにかして作る
  is_tuden_minus = ... # ここをどうにかして作る
  is_tuden_plus && is_tuden_minus
end

edges.each { |edge|
  is_tuden = edge_tuden_hantei(edge)
  edge.update_state(is_tuden)
}

通電しないパターンも挙げておきます。

たとえば、次の図のエッジ e1 やエッジ e2 にあるスイッチが OFF になっていると、プラス極に辿りつくことができず通電しません。

f:id:sonota88:20200306052834p:plain


ふーむ……ほんとにこのアイデアでなんとかなるんでしょうか?