最小の空白マスの更新 (KATAMINOを解くプログラムを作成する)

★前回の記事

yucatio.hatenablog.com

今回はminEmptyの更新をします。minEmptyはピースが置かれていないマスのうち、1番上の段の、1番左のマスです。

f:id:yucatio:20190722133606p:plain:w300

実装

フィールドを渡して最小の空白を探すfindMinEmptyを実装します。まずは呼び出し側を書きます。

js/solver.js

const solver = {
    // 中略

  solve : () => {
    while (solver.solverStack.length > 0) {
      const {kataminoField, minEmpty, pieceId, spinId, spin, unPlacedPiece} = solver.solverStack.pop()

      console.log("pieceId", pieceId)
      console.log("spinId", spinId)

      const offset = {x: minEmpty.x, y: minEmpty.y - spin[0].y}
      
      if (! solver.isAllEmpty(kataminoField, spin, offset)) {
        // フィールドの外か、すでにピースが置かれている
        console.log("フィールドの外か、すでにピースが置かれている")
        continue
      }

      console.log("ピースが置ける")

      const nextField = util.copyArrayOfArray(kataminoField)
      solver.placeSpin(nextField, spin, offset, pieceId)
      console.log("nextField", nextField)

      const nextUnPlaced = unPlacedPiece.filter(id => id !== pieceId)
      console.log("nextUnPlaced", nextUnPlaced)

      if (nextUnPlaced.length <= 0) {
        console.log("完成")
        break
      }

      // 追加ここから
      const nextEmpty = solver.findMinEmpty(nextField)
      console.log("nextEmpty", nextEmpty)
      // 追加ここまで
    }
  },
  // 中略
  // 追加ここから
  findMinEmpty : (kataminoField) => {
    // TODO 実装
  },
  // 追加ここまで
}

findMinEmptyを実装していきます。-1が含まれている配列が初めて現れるインデックスを、Array.findIndex ( Array.prototype.findIndex() - JavaScript | MDN ) で見つけ、その中で-1が何番目なのかさらにArray.findIndexで求めます。(コード内では-1かどうかで判定するのではなく、0より小さいかどうかで判定しています。)

  findMinEmpty : (kataminoField) => {
    const x = kataminoField.findIndex(row => 
      row.some((val) => val < 0)
    )
    const y = kataminoField[x].findIndex(val => val < 0)

    return {x, y}
  },

実行結果

動作結果です。nextEmptyが新しいフィールドでピースが置かれていないマスのうち、1番上の段の、1番左のマスを示しています。

f:id:yucatio:20190723085829p:plain

リファクタリング

現在のminEmptyを渡すことによって、最小の空白を探す範囲が少し狭くなります。 minEmpty.xより小さい範囲は探さなくて済むからです。 Array.slice ( Array.prototype.slice() - JavaScript | MDN ) で現在のminEmpty.x以降の配列を作成します。インデックスを調整するため、見つかったxのインデックスにpreviousEmpty.xを足しています。

関数名をfindMinEmptyからfindNextEmptyに変更します。

const solver = {
  // 中略

  solve : () => {
    while (solver.solverStack.length > 0) {
      // 中略
      const nextEmpty = solver.findNextEmpty(nextField, minEmpty)  // 変更
      console.log("nextEmpty", nextEmpty)
    }
  },
  // 中略
  findNextEmpty : (kataminoField, previousEmpty) => {
    const x = previousEmpty.x + kataminoField.slice(previousEmpty.x).findIndex(row => 
      row.some((val) => val < 0)
    )
    const y = kataminoField[x].findIndex(val => val < 0)

    return {x, y}
  },
}