All files / src/games SlidingBlockPuzzle.js

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
 
 
1x
 
 
 
 
 
 
 
2x
2x
 
 
 
 
1x
 
1x
 
1x
 
50x
50x
50x
 
 
1x
 
 
 
 
6x
 
 
 
 
6x
 
44x
 
6x
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
13310x
 
15321x
 
13307x
 
 
3x
 
 
 
 
13356x
13356x
13356x
13356x
 
13356x
 
8940x
 
 
13356x
 
8918x
 
 
13356x
 
8912x
 
 
13356x
 
8949x
 
 
13356x
 
 
 
 
35646x
 
35646x
 
35646x
35646x
 
35646x
 
 
 
 
35583x
 
 
 
 
"use strict";
 
module.exports.SlidingBlockPuzzle = class
{
  /**
   * @param {number} width
   * @param {number} height
   */
  constructor(width, height)
  {
    this.width = width;
    this.height = height;
  }
 
  createRandomInitialState()
  {
    let state = this.createGoalState();
 
    let steps = 50;
 
    while (steps-- > 0)
    {
      let actions = this.getActions(state);
      let action = actions[Math.floor(actions.length * Math.random())];
      state = this.performAction(state, action);
    }
 
    return state;
  }
 
  createGoalState()
  {
    let state = {
      width: this.width,
      height: this.height,
      length: this.width * this.height
    };
    for (let index = 0; index < state.length; index++)
    {
      state[index] = index;
    }
    return state;
  }
 
  print(state)
  {
    let output = [];
    for (let yIndex = 0; yIndex < state.height; yIndex++)
    {
      let line = [];
      for (let xIndex = 0; xIndex < state.width; xIndex++)
      {
        line.push(state[yIndex * state.width + xIndex]);
      }
      output.push(line.join(' '))
    }
    return output.join('\n')
  }
 
  isGoalState(state, goal)
  {
    for (let index = 0; index < state.length; index++)
    {
      if (state[index] !== goal[index])
      {
        return false;
      }
    }
    return true;
  }
 
  getActions(state)
  {
    const actions = [];
    const emptyIndex = Array.prototype.indexOf.call(state, 0)
    const emptyX = emptyIndex % state.width;
    const emptyY = (emptyIndex - emptyX) / state.width;
 
    if (emptyX > 0)
    {
      actions.push(emptyIndex - 1)
    }
 
    if (emptyX + 1 < state.width)
    {
      actions.push(emptyIndex + 1)
    }
 
    if (emptyY > 0)
    {
      actions.push(emptyIndex - state.width)
    }
 
    if (emptyY + 1 < state.height)
    {
      actions.push(emptyIndex + state.width)
    }
 
    return actions;
  }
 
  performAction(state, action)
  {
    state = Object.assign({}, state);
 
    const emptyIndex = Array.prototype.indexOf.call(state, 0)
 
    state[emptyIndex] = state[action];
    state[action] = 0;
 
    return state;
  }
 
  stateSerialise(state)
  {
    return Array.prototype.join.call(state, ',');
  }
 
}