-
Notifications
You must be signed in to change notification settings - Fork 0
/
invert_distance.go
187 lines (170 loc) · 5.55 KB
/
invert_distance.go
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
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
package main
// TODO: move this function to state.go
// func (search *SearchState) invertDistanceFromMove() t_cell {
// // TODO fix this function
// if search.state.move == nil {
// // panic("can't calculate invert distance from a nil move in state. invertMoveDistance should always be called if the state.move value is set")
// return 0
// }
// var count int = 0
// /**
// When moving a tile vertically, the total number of inversions can change by only -3, -1, +1, and +3 - First note that a vertical move will shift the tile 3 positions forward or backwards in our line of tiles.
// - There are two cases to consider, depending on the relative value of the three tiles we've skipped over:
// - Case 1: the three skipped tiles are all smaller (or larger) than the moved tile.
// - Moving the tile will either add or fix three inversions, one for each skipped tile. So, the total number of inversions changes by +3 or -3.
// - Case 2: two of the tiles are larger and other is smaller (or vice versa).
// - In this case, there's going to be a net change of +1 or -1 inversions
// **/
// board := search.state.board
// move := search.state.move
// switch move.direction {
// case DIRECTION_UP:
// {
// // Case 1: the three skipped tiles are all smaller (or larger) than the moved tile.
// // - Moving the tile will either add or fix three inversions, one for each skipped tile.
// // So, the total number of inversions changes by +3 or -3.
// // board[move.toIndex] is current empty index
// // board[move.emtpyIndex] is the old value of current empty index, aka the value that was moved
// // move.emtpyIndex is the index of old empty location
// idx := move.toIndex + 1
// tile := board[move.emptyIndex]
// for idx < move.emptyIndex {
// if board[idx] > tile {
// count++
// } else {
// count--
// }
// idx++
// }
// }
// case DIRECTION_DOWN:
// {
// idx := move.toIndex - 1 // 11 index 2
// tile := board[move.emptyIndex] // 6
// for idx > move.emptyIndex {
// if board[idx] > tile { // tätä kutsutaan 3 kertaa indexeillä 2,3,4
// count--
// } else {
// count++
// }
// idx--
// }
// }
// case DIRECTION_RIGHT:
// {
// // this has to be tested
// emptyIndex := search.findIndexHorizontal(0)
// toIndex := search.findIndexHorizontal(board[move.emptyIndex])
// idx := toIndex + 1
// tile := memoHorizontalBoard[emptyIndex]
// for idx < emptyIndex {
// if memoHorizontalBoard[idx] > tile { // tätä kutsutaan 3 kertaa indexeillä 2,3,4
// count++
// } else {
// count--
// }
// idx++
// }
// }
// case DIRECTION_LEFT:
// {
// emptyIndex := search.findIndexHorizontal(0)
// toIndex := search.findIndexHorizontal(board[move.emptyIndex])
// idx := toIndex - 1
// tile := memoHorizontalBoard[emptyIndex]
// for idx > emptyIndex {
// if memoHorizontalBoard[idx] > tile { // tätä kutsutaan 3 kertaa indexeillä 2,3,4
// count--
// } else {
// count++
// }
// idx--
// }
// }
// }
// heur := t_cell(0)
// if count < 0 {
// heur += t_cell(abs(count) / 3)
// } else {
// heur -= t_cell(abs(count) / 3)
// }
// return heur
// }
func abs(x int) int {
if x >= 0 {
return x
}
return -x
}
// Evaluate the invert distance of t
func invertDistance(board [16]t_cell) t_cell {
// theory of this heuristic evaluation is based on this article https://web.archive.org/web/20141224035932/http://juropollo.xe0.ru/stp_wd_translation_en.htm
// Calculate the vertical inversions
inv := 0
size := t_cell(BOARD_ROW_SIZE * BOARD_ROW_SIZE)
for i := t_cell(0); i < size; i++ {
if board[i] != 0 {
for j := t_cell(0); j < i; j++ {
if board[i] < board[j] {
inv++
}
}
}
}
vertical := t_cell(inv/3 + 1)
// calculate the horizontal inversions
inv = 0
for i := range board {
// true value of the node so we have to minus one
value := board[i]
if value != -1 {
id := 0
for j := range memoHorizontalBoard {
if memoHorizontalBoard[j] == t_cell(value) {
id = j
break
}
}
inv += abs(id - i)
}
}
horizontal := t_cell(inv/3 + 1)
// sum horizontal and vertical distance to get the sum of invert distance
return vertical + horizontal
}
type MemoizedFunction[T interface{}, R interface{}] func(R) T
// because we are doing alot of expensive or semi expensive calculations. It's prefered that we memoize the values that these calls return rather than we call the operations with same values again and again
func memoizeBoardCalculation[T interface{}, R interface{}](fn MemoizedFunction[T, R]) MemoizedFunction[T, R] {
cache := make(map[interface{}]T)
return func(input R) T {
if val, found := cache[input]; found {
return val
}
val := fn(input)
cache[input] = fn(input)
return val
}
}
// Transition given vertical board to horizontal representation of the given board
func calculateHorizontalBoard(rowSize t_cell) [16]t_cell {
board := startingPoint(rowSize)
// horizontalBoard := make([]t_cell, len(board))
var horizontalBoard [16]t_cell
copy(horizontalBoard[:], board[:])
// make the board list be a horizontal representation of the puzzle board
for i := t_cell(0); i < rowSize; i++ {
for j := t_cell(0); j < rowSize; j++ {
horizontalBoard[i*rowSize+j] = board[i+j*rowSize]
}
}
return horizontalBoard
}
var memoHorizontalBoard = calculateHorizontalBoard(t_cell(BOARD_ROW_SIZE))
func findIndexInHorizontalBoard(num t_cell) t_cell {
for i := range memoHorizontalBoard {
if memoHorizontalBoard[i] == num {
return t_cell(i)
}
}
return -1
}