yucatio@システムエンジニア

趣味で作ったものいろいろ

JavaScriptで値を指定して削除する(置かれていないピースの更新) (KATAMINOを解くプログラムを作成する)

KATAMINOを解くプログラム JavaScript

★前回の記事

yucatio.hatenablog.com

続いてunPlacedPieceの更新をします。unPlacedPieceはまだ置かれていないピースの番号を格納しています。置かれたピースの番号をここから削除します。

実装

JavaScriptでは、引数に渡された値と同じ値を削除する関数は用意されていませんので、自分で用意する必要があります。また、フィールドを更新したときと同様に、unPlacedPiece自体を更新しないように気をつける必要があります。調べたところ、Array.filterを使用するのが良さそうなので、今回はこちらを使用します。

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)
      // 追加ここまで
    }
  },
  // 中略
}

ここで、nextUnPlacedが空の場合はすべてのピースが置けたということなので、処理を中断します。コードを追加します。

const solver = {
    // 中略

  solve : () => {
    while (solver.solverStack.length > 0) {
      // 中略

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

      // 追加ここから
      if (nextUnPlaced.length <= 0) {
        console.log("完成")
        break
      }
      // 追加ここまで
    }
  },
  // 中略
}

動作確認

動作結果です。nextUnPlacedは置かれたピースの番号(pieceId)が含まれていません。

f:id:yucatio:20190722215416p:plain

以上でunPlacedPieceから置かれた置かれたピースの番号を削除することができました。


★次回の記事

yucatio.hatenablog.com

★目次

yucatio.hatenablog.com

フィールドの更新 (KATAMINOを解くプログラムを作成する)

KATAMINOを解くプログラム

★前回の記事

yucatio.hatenablog.com

フィールドにピースが置かれているかどうか判定できたので、今回はフィールドにピースを置く処理を実装します。

実装

ピースが置かれた場所を、pieceIdで更新します。kataminoFieldの値を更新してしまうとスタック内の他のデータにも影響が出てしまうので、コピーを作成してから変更します。

配列の配列をコピーする関数を先に書いておきます。

js/util.js

const util = {
  copyArrayOfArray : (arrayOfArray) => {
    return arrayOfArray.map(array => ([...array]))
  },
}

フィールドを更新するplaceSpin関数とそれを呼び出す部分を実装します。placeSpin関数の中でフィールドのマスの値を置かれたピースの番号(pieceId)で更新します。

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)
      // 追加ここまで
    }
  },

  // 中略

  // 追加ここから
  placeSpin: (kataminoField, places, offset, pieceId) => {
    places.forEach((place) => {
      kataminoField[place.x + offset.x][place.y + offset.y] = pieceId
    })
  },
  // 追加ここまで
}

動作確認

動作結果です。フィールドが置かれたピースの番号で更新されています。

f:id:yucatio:20190722214005p:plain

以上でフィールドのマスを、置かれたピースの番号で更新することができました。


★次回の記事

yucatio.hatenablog.com

★目次

yucatio.hatenablog.com

フィールドにピースが置けるかどうかの判定 (KATAMINOを解くプログラムを作成する)

KATAMINOを解くプログラム

★前回の記事

yucatio.hatenablog.com

前回まででスピンをどこに移動するか求めることができたので、今回はその位置に置けるかどうかを判定する関数を作成します。

ピースがフィールドに置ける条件は、以下の2点を満たすことです。

  • ピースがフィールドの外に出ていないこと
  • 置こうとする場所にすでに他のピースが置かれていないこと

置ける例↓

f:id:yucatio:20190722133633p:plain:w300

置けない例↓

f:id:yucatio:20190722133621p:plain:w300

実装

フィールドにスピンが置けるかを判定する、isAllEmpty関数とisEmpty関数を定義します。isAllEmptyは、スピンが置かれるすべてのマスが、フィールドの範囲内でまだピースが置かれていないときにtrueを返す関数です。 isEmptyは、placeの位置がフィールドの外でなく、かつまだピースが置かれていないときにtrueを返す関数です。

はじめに呼び出し側の実装をします。isAllEmptyでスピンが置けるか判定し、置けなかった場合には処理を中断し、ループの先頭に戻ります。

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("ピースが置ける")
      // 追加ここまで
    }
  },

  // 追加ここから
  isAllEmpty: (kataminoField, places, offset) => {
    // TODO 実装
    return false
  },

  isEmpty: (kataminoField, place) => {
    // TODO 実装
    return false
  },
  // 追加ここまで
}

isAllEmptyからisEmptyを呼び出しましょう。Array.every ( Array.prototype.every() - JavaScript | MDN ) はコールバックに渡された関数が、配列のすべての要素に対して、true相当を返すかどうかを判定します。 isEmptyの引数には、スピンが実際に置かれるマスを渡すので、offsetをそれぞれ加算した値を渡しています。

  isAllEmpty: (kataminoField, places, offset) => {
    return places.every((place) => (
      solver.isEmpty(kataminoField, {x: place.x + offset.x, y: place.y + offset.y})
    ))
  },

次に、isEmpty関数を実装します。まずはplaceの位置がフィールドの内のときにtrueを返すようにします。JavaScriptの場合は、配列の定義外の範囲を参照するとundefinedが返ってくるので、それで判定します。place.xもplace.yもundefinedでなければフィールドの範囲内です。

  isEmpty: (kataminoField, place) => {
    return (
      kataminoField[place.x] !== undefined &&
      kataminoField[place.x][place.y] !== undefined
    )
  },

次に、置こうとする場所にすでに他のピースが置かれていないことを判定します。フィールドにピースが置かれているときはそのピースの番号、置かれていないときは-1なので、ピースが置かれているかどうかは0より小さいかどうかで判定します。

  isEmpty: (kataminoField, place) => {
    return (
      kataminoField[place.x] !== undefined &&
      kataminoField[place.x][place.y] !== undefined &&
      kataminoField[place.x][place.y] < 0
    )
  },

動作確認

動作結果です。コンソールの出力はこのようになっています。

f:id:yucatio:20190722162554p:plain

下記の図と対応させてみると、

f:id:yucatio:20190722141550p:plain

(pieceId, spinId) = (9, 1), (9, 0), (2, 7), (2, 1), (1, 7), (1, 3), (1, 1)

が初期状態で置けることが分かり、コンソールの出力結果と一致していることが分かります。


★次回の記事

yucatio.hatenablog.com

★目次

yucatio.hatenablog.com

ピースを置く場所の算出 (KATAMINOを解くプログラムを作成する)

KATAMINOを解くプログラム

★前回の記事

yucatio.hatenablog.com

スタックからフィールドとスピン情報を取得することができたので、ピースが置けるか判定していきます。 minEmptyのマスに重なるようにピースを置くのでした。 minEmptyは、フィールドのピースが置かれていないマスのうち、1番上の行で1番左にあるマスです。 置くスピンの一番上の左端とminEmptyを重ねます。これ以外のマスを重ねようとしてもすでにあるピースと重なってしまったり枠の外に出たりしてしまいます。(ただしスピンの1番上の左端を重ねたからと言って必ずしも他のピースと重ならないわけではないです)

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

minEmptyと重なるようにピースを置いた例↓フィールドからはみ出していて、他のピースとも重なっている

f:id:yucatio:20190722133621p:plain:w280

minEmptyと重なるようにピースを置いた例↓フィールド内に収まっていて、他のピースとも重なっていない

f:id:yucatio:20190722133633p:plain:w250

幸いな事に、spinの1番上の1番左にあたる場所はspin[0]です。これは2次元配列からリストを作成した時に、1番上の列の左からリストにしていったためです。 スピンをminEmptyと重なるように移動します。

x方向(下方向)にはminEmpty.xぶん移動します。y方向(右方向)にはminEmpty.y - spin[0].yぶん移動します。

f:id:yucatio:20190722135720p:plain

実装

コードにしていきます。spinの移動量をoffsetという変数に格納します。

js/solver.js

const solver = {
  solverStack : [], 

  // 中略

  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} // 追加

      console.log("offset", offset)
    }
  },
}

pieceの各値にoffsetを足したものが実際のピースが置かれる場所になります。

例えば、以下のスピンは、

f:id:yucatio:20190722133926p:plain

リストの表現は

[
  {x: 0, y: 1},
  {x: 1, y: 1},
  {x: 2, y: 0},
  {x: 2, y: 1},
  {x: 2, y: 2}
}

です。

nextEmptyが{x: 2, y: 1}のとき、offsetは{x: 2, y: 0}なので、 実際にピースが置かれる場所は、各配列の要素に{x: 2, y: 0}を足して、

[
  {x: 2, y: 1},
  {x: 3, y: 1},
  {x: 4, y: 0},
  {x: 4, y: 1},
  {x: 4, y: 2}
}

となります。

動作確認

実行結果です。以下のようになっていれば成功です。offsetの値が表示されました。

f:id:yucatio:20190722094926p:plain

以上でピースを置く場所の算出ができました。


★次回の記事

yucatio.hatenablog.com

★目次

yucatio.hatenablog.com

スタックからの情報の取り出し (KATAMINOを解くプログラムを作成する)

KATAMINOを解くプログラム

★前回の記事

yucatio.hatenablog.com

solve関数を実装していきます。 この関数内では、スタックからフィールドとピースの組み合わせを1つ取り出し、すべてのピースがフィールドに置けるまで(もしくはすべての組み合わせを試して、解けないことが確定するまで)フィールドにピースを置くということを繰り返します。

実装

前回スタックに投入したデータを1つずつ取り出してみましょう。while (solver.solverStack.length > 0)で配列にデータがあるあいだ、ブロックを実行します。solver.solverStack.pop()でスタックからデータを取り出します。

js/solver.js

const solver = {
  solverStack : [], 

  // 中略

  solve : () => {
    while (solver.solverStack.length > 0) {
      const popped = solver.solverStack.pop()
      console.log("popped", popped)
    }
  },
}

実行結果

以下のように表示されていれば成功です。 スタックにpushしたのと逆順に表示されます。

f:id:yucatio:20190722092737p:plain

リファクタリング

今後の実装のために、取り出したデータの各プロパティをローカル変数に代入して置くと便利です。 分割代入を使用すると簡潔に書けます。

const solver = {
  solverStack : [], 

  // 中略

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

以上でスタックから情報を取り出すことができました。


★次回の記事

yucatio.hatenablog.com

★目次

yucatio.hatenablog.com

スタックへの初期データの投入 (KATAMINOを解くプログラムを作成する)

KATAMINOを解くプログラム

★前回の記事

yucatio.hatenablog.com

スタックへデータを投入します。

スタックを使用するアルゴリズムについては以下の記事を参照してください。

yucatio.hatenablog.com

実装

フィールドと次に置くことができるピースをスタックへ投入します。 スタックsolverStackを定義します。解く対象のピースtargetPieceの各スピンをスタックに投入します。

js/solver.js

const solver = {
  solverStack : [],  // 追加

  init : (targetPiece) => {
    let kataminoField = new Array(5).fill().map(() => (
      new Array(targetPiece.length).fill(-1)
    }

    // 追加ここから
    solver.solverStack  = []
    targetPiece.forEach((pieceId) => {
      KATAMINO_ARR[pieceId].forEach((spin) => {
        solver.solverStack.push({kataminoField, spin})
      })
    })
    // 追加ここまで
  },
}

ここまでで、スタックの内容は以下のようになっています。

f:id:yucatio:20190722090944p:plain

ここのままでも解けそうですが、1つ問題点があります。例えば1番のピースの1番のスピンがフィールドに置けたとき、1番のピースはもうこれ以上置くことはできません。しかしピース番号が分からないため、1番のピース以外を次に置く候補としてスタックに入れることができません。

そこでピース番号pieceIdとまだ置かれていないピースの配列unPlacedPieceをスタックに入れる情報に追加します。ピースをフィールドに置いた時に、置いたピースの番号をunPlacedPieceから削除することで同じピースを重複して置くことを防ぎます。また、デバッグのために、spinIdもスタックに入れます(STEP2でspinIdも使用します)。

js/solver.js

const solver = {
  solverStack : [], 

  init : (targetPiece) => {
    let kataminoField = new Array(5).fill().map(() => (
      new Array(targetPiece.length).fill(-1)
    }

    solver.solverStack  = []
    targetPiece.forEach((pieceId) => {
      KATAMINO_ARR[pieceId].forEach((spin, spinId) => {  // 変更
        solver.solverStack.push({kataminoField, pieceId, spinId, spin, unPlacedPiece: targetPiece})  // 変更
      })
    })
  },
}

ところで、スタックから取り出した後に、1番番号が小さい(左上の)空白を埋めるようにピースを置いてみるのでした。 毎回スタックから取り出すごとに計算するのも面倒なので、フィールドの状態ごとに計算してスタックに入れておくことにしましょう。

const solver = {
  solverStack : [], 

  init : (targetPiece) => {
    let kataminoField = new Array(5).fill().map(() => (
      new Array(targetPiece.length).fill(-1)
    }

    solver.solverStack  = []
    const minEmpty = {x:0, y:0}  // 追加

    targetPiece.forEach((pieceId) => {
      KATAMINO_ARR[pieceId].forEach((spin, spinId) => {
        solver.solverStack.push({kataminoField, minEmpty, pieceId, spinId, spin, unPlacedPiece: targetPiece})  // 変更
      })
    })
  },
}

以上でスタックへの初期データの投入が完了しました。


★次回の記事

yucatio.hatenablog.com

★目次

yucatio.hatenablog.com

フィールドの初期化 (KATAMINOを解くプログラムを作成する)

KATAMINOを解くプログラム

★前回の記事

yucatio.hatenablog.com

KATAMINOのピースを置くフィールドを初期化します。 フィールドのサイズは、5 × (置くピースの数)です。

f:id:yucatio:20190619224647p:plain

詳しくは以下の記事を参照してください。

yucatio.hatenablog.com

実装

フィールドの各値を-1で初期化します。配列を引数で与えられた値で埋めるArray.fill ( Array.prototype.fill() - JavaScript | MDN ) という関数を使用しています。

js/solver.js

const solver = {
  init : (targetPiece) => {
    const kataminoField = []
    for(let i=0; i < 5; i++) {
      kataminoField.push((new Array(targetPiece.length)).fill(-1))
    }
    console.log("kataminoField", kataminoField)
  },
  // 中略
}

動作確認

以下のようになっていれば成功です。今回は引数で渡されたピースが3つなので、5×3の配列が作成されています。

f:id:yucatio:20190721223754p:plain

リファクタリング

長さ5の配列を定義し、mapを使用することで以下のように書き換えることもできます。

const solver = {
  init : (targetPiece) => {
    const kataminoField = new Array(5).fill().map(() => (
      new Array(targetPiece.length).fill(-1)
    ))
    console.log("kataminoField", kataminoField)
  },
}

new Array(5)とmapの間にfillを挟む理由は以下の記事を参照してください。

yucatio.hatenablog.com

以上でフィールドの初期化を行うことができました。


★次回の記事

yucatio.hatenablog.com

★目次

yucatio.hatenablog.com