Railsで腹ぺこカバ問題を解いてみた時の気付き

INDEX

1. 最初に問題のルールと回答。
2. 最後に俺の最初の考えとやるべきだったこと

やること

あなたの仕事は、Gameという単純なクラスを作成することです。
このクラスは、カバが何回アリーナの中央に飛び込んで食べ物を集める必要があるかをチェックします。
すべての食べ物を見つけることができる場所を定義する、ボードと呼ばれる整数配列が与えられます。カバがすべての餌を食べるために必要な飛躍の量を表す整数を返す必要があります。

条件

1.ボード配列には、スペース用の0と食品用の1が含まれています。
2.ボードのサイズは n*n で、n は5～50です。
3. 1 つの跳躍は、互いに水平または垂直に接続された
食品で構成されます。それらが接続されていない場合は、別の飛躍が必要です。

初期状態

board = [[1,1,0,0,0],
         [1,1,0,0,0],
         [0,0,0,0,0],
         [0,0,0,1,1],
         [0,0,0,1,1]]

game = Game.new(board)
game.play()

結果

水平または垂直に接続された ２つの食品ブロックがあるため、 ２を返す必要がある。

ソースコード

class Game
  DIRECTIONS = [[1, 0], [0, 1], [-1, 0], [0, -1]].freeze

  def initialize(board)
    @board = board
  end

  def play
    # food_locationsは数える対象の[x,y]を生成する
    food_pile = food_locations(@board)
    result = 0
    # 格納した[x,y]の座標がなくなるまでループ処理,present?の方が良さげ
    until food_pile.empty? do
      result += 1
      #seedは集合に格納した座標[x,y]の先頭
      seed = food_pile.first
      # 集合から座標[x,y]を消す
      food_pile.delete(seed)
      consume_cluster(seed, food_pile)
    end

    result
  end

  private

  def food_locations(board)
    # ここで集合を作る.
    coordinates = Set.new

    # boardは[[1,1,0,0,0]...]
    board.each_with_index do |row, y|
      # rowは0or1
      row.each_with_index do |field, x|
        # row==fieldが1。今回の数える対象。その座標[x,y]を集合に格納していく
        coordinates << [x, y] if field == 1
      end
    end

    coordinates
  end

  # pointはseed, pileはfood_pile(集合)
  def consume_cluster(point, pile)
    # pointの上下左右の座標がneighbour
    each_neighbour(point) do |neighbour|
      # カウント対象をpileに格納していて、そこに上下左右の座標が含まれてるか見てる。
      # neighbourがカウント対象(=boardの0なら)じゃなければ次のneighbourをチェック
      next unless pile.include?(neighbour)
      # カウント対象が上下左右の座標なら集合から削除する。
      pile.delete(neighbour)
      # 上下左右の計算を最後までroopで行う
      consume_cluster(neighbour, pile)
    end
  end

  def each_neighbour(point)
    # pointはseed.seedは今回求める1の座標
    x, y = point
    # DIRECTIONSは上下左右の座標
    DIRECTIONS.each do |dx, dy|
      # yieldは今回はputsぐらいの感覚で抑えよう。
      # seedを基準に上下左右の座標を定数をeachすることで生成。
      yield [x + dx, y + dy]
    end
  end
end

自分でソースコードを考えてる時の流れ

与えられたボードをeachで回して、配列１つずつにkeyで数字を割り振って、配列の各要素にもkeyを割り振り参照できるようにしようとしたのが下記

board = 
[[1,1,0,0,0], => 1
 [1,1,0,0,0], => 2
 [0,0,0,0,0], => 3
 [0,0,0,1,1], => 4
 [0,0,0,1,1]] => 5
↓を作った
[{1=>{1=>1, 2=>0, 3=>1, 4=>0, 5=>1}},
{2=>{1=>0, 2=>1, 3=>0, 4=>1, 5=>0}}, 
{3=>{1=>1, 2=>0, 3=>1, 4=>0, 5=>1}}, 
{4=>{1=>0, 2=>1, 3=>0, 4=>1, 5=>0}}, 
{5=>{1=>1, 2=>0, 3=>1, 4=>0, 5=>1}}]

自分的には{1=>{1=>1, 2=>0, 3=>1, 4=>0, 5=>1}のkeyである1=>{はy列を示していて、valueの{1=>1, 2=>0, 3=>1, 4=>0, 5=>1}はx列を示してる。
その上で0,1までジャンプしてジャンプカウンターを+1。ジャンプした場所が1且つ、上下左右に1があったらジャンプカウンターを-1。
のようなロジックを作りたかったが、そもそもここに記載してる時点で日本語をうまくまとめ切れてない。
おそらく今回の敗因はこれ。うまくロジックを頭の中で作れてないのに手を動かしてしまった。

回答のソースコードでは、僕のところでいうジャンプカウンターを毎回計測して、1つずつboardを元につくったhashを参照する方法ではなく、
boardから計測すべき対象だけまとめてそこから条件をつけて再度対象を減らすようなロジックの流れを構築していた。

つまり、僕の場合は0~100のなかで1,2,3,4,5...と1つずつ対象かどうかをチェックする流れだったが、
回答は0~100のうち対象を最初に抽出して、そこからさらに条件に当てはまるものを抽出してる流れであった。

この最初の頭の使い方で問題を難解に解釈してしまっていた。仮にできたとしても難解なソースコード+処理がすごい遅いものができていただろう。

当時の途中までのソースコード

class Game
  attr_accessor :borad, :jump_counter

  def initialize(board)
    @borad = board
    @jump_counter = 0
  end

  def play
    list =[]

    # 配列を整形する処理. eachにeachを重ねるのは処理速度的によくないが一旦
    board.each_with_index do |board_ary, i| 
      hash = {}
      board_ary.each_with_index do |element, ii|
        ii += 1
        hash[ii] = element
      end
      list << {"#{i + 1}".to_i => hash}
    end

    list.each do |arr|
      # この辺りで積んだ
      if arr.keys.first == 1
      end
    end

  end
end