Coverage for moptipyapps / ttp / game_encoding_2.py: 21%

1""" 

2A permutation-with-repetition-based encoding based on games with rescheduling. 

3 

4This game-based encoding method is an extension of the method presented in 

5:mod:`~moptipyapps.ttp.game_encoding`. The method presented in 

6:mod:`~moptipyapps.ttp.game_encoding` takes a permutation of games and fills 

7these games into a game plan one-by-one. For each game it tries to find the 

8earliest possible slot where it can be scheduled, i.e., the earliest slot 

9where both involved teams do not yet have a game scheduled. 

10 

11During this process, it can happen that a game cannot be added to the game 

12plan, because on each day, at least one of the two teams has already a game 

13scheduled. In such a case, the original encoding will simply drop the game. 

14This results in "byes" in the game plan. 

15 

16This new encoding tries to reduce the number of such byes. It does this as 

17follows: It still processes the game permutations from front to end and 

18adds the games to the schedule. If one game cannot be added to the schedule 

19due to the above reason, it will go through game plan again from beginning 

20to end. This time, it will look for a day on which only *one* of the two teams 

21has a game scheduled already. It will then take this already-scheduled game 

22and try to schedule it on a *later* day. This is a recursive process: If no 

23later slot is found where both teams involved have no game scheduled, we will 

24again look for a day on which only one of the teams have scheduled a game and 

25try to move that to a later slot. Since this will be an even later slot, the 

26recursion will never go too deep. Either way, if a later slot is found, the 

27game can be moved, meaning that the original game blocking our "current" game 

28can be moved as well. Then the new game can be inserted. 

29 

30If no such slot can be found, then we try to insert the game by searching 

31from the back end and moving other games forward in the same recursive 

32fashion. The hope is that, this way, the number of "byes" in the schedule can 

33be reduced. If the number of "byes" is reduced, then there will automatically 

34fewer constraint violations. This makes it more likely that we discover a 

35feasible schedule earlier in the search. 

36 

37Furthermore, the process might even make it easier for a search to move from 

38one feasible schedule to another one. There would hopefully be fewer 

39permutations leading to infeasible schedules and fewer infeasible schedules 

40between two feasible ones. 

41 

42Of course, all of that comes at the cost of increased runtime. 

43""" 

44 

45 

46from typing import Final 

47 

48import numba # type: ignore 

49import numpy as np 

50 

51from moptipyapps.ttp.game_encoding import GameEncoding 

52from moptipyapps.ttp.game_plan_space import GamePlanSpace 

53from moptipyapps.ttp.instance import Instance 

54 

55 

56# Due to the recursion, caching must be disabled or we get a segfault. 

57@numba.njit(cache=False, nogil=True, fastmath=True, boundscheck=True) 

58def _re_schedule(y: np.ndarray, index: int | np.ndarray, 

59 day: int, end: int, direction: int) -> bool: 

60 """ 

61 Try to re-schedule a game at the given index. 

62 

63 This function tries to take the game at the given index and given day and 

64 attempts to move it to a later day. If it succeeds, it returns `True`, if 

65 rescheduling was not possible, it returns `False`. 

66 

67 :param y: the schedule 

68 :param index: the index 

69 :param day: the day 

70 :param end: the end day 

71 :return: `True` if the game was successfully re-scheduled, `False` 

72 otherwise 

73 

74 >>> dest = np.array([ 

75 ... [ 2, -1, 4, -3], 

76 ... [ 3, 4, -1, -2], 

77 ... [ 4, 3, -2, -1], 

78 ... [-2, 1, -4, 3], 

79 ... [-3, -4, 1, 2], 

80 ... [-4, -3, 2, 1]]) 

81 >>> _re_schedule(dest, 0, 2, 6, 1) 

82 False 

83 >>> dest = np.array([ 

84 ... [ 2, -1, 4, -3], 

85 ... [ 3, 4, -1, -2], 

86 ... [ 4, 3, -2, -1], 

87 ... [ 0, 1, -4, 0], 

88 ... [-3, -4, 1, 2], 

89 ... [-4, -3, 2, 1]]) 

90 >>> _re_schedule(dest, 0, 2, 6, 1) 

91 True 

92 >>> print(dest) 

93 [[ 2 -1 4 -3] 

94 [ 3 4 -1 -2] 

95 [ 0 3 -2 0] 

96 [ 4 1 -4 -1] 

97 [-3 -4 1 2] 

98 [-4 -3 2 1]] 

99 >>> dest = np.array([ 

100 ... [ 2, -1, 4, -3], 

101 ... [ 3, 4, -1, -2], 

102 ... [ 0, 3, -2, -1], 

103 ... [-2, 0, 0, 3], 

104 ... [-3, -4, 1, 2], 

105 ... [-4, -3, 2, 1]]) 

106 >>> _re_schedule(dest, 2, 1, 6, 1) 

107 True 

108 >>> print(dest) 

109 [[ 2 -1 4 -3] 

110 [ 0 4 0 -2] 

111 [ 3 0 -1 -1] 

112 [-2 3 -2 3] 

113 [-3 -4 1 2] 

114 [-4 -3 2 1]] 

115 """ 

116 home_idx = int(index) # We first guess that this is the home team 

117 away_idx = int(y[day, index]) # and that this is the away team. 

118 if away_idx < 0: # The home team actually plays away. 

119 away_idx, home_idx = home_idx, (-away_idx) - 1 # Swap. 

120 else: # We were right. 

121 away_idx -= 1 # So the ID of the away team -1 is its index. 

122 if _schedule(y, home_idx, away_idx, day + direction, 

123 end, direction, True): # Try to re-schedule the game. 

124 y[day, home_idx] = 0 # Set first slot to empty. 

125 y[day, away_idx] = 0 # Set last slot to empty. 

126 return True # We successfully rescheduled the game. 

127 return False # We failed to recursively reschedule. 

128 

129 

130# Due to the recursion, caching must be disabled or we get a segfault. 

131@numba.njit(cache=False, nogil=True, fastmath=True, boundscheck=True) 

132def _schedule(y: np.ndarray, home_idx: int, away_idx: int, start: int, 

133 end: int, direction: int, is_recursive: bool) -> bool: 

134 """ 

135 Try to find a slot in the day range where the given game can be placed. 

136 

137 :param y: the destination array 

138 :param home_idx: the home index 

139 :param away_idx: the away index 

140 :param start: the starting day 

141 :param end: the ending day 

142 :return: `True` if the game could be placed, `False` otherwise. 

143 

144 >>> dest = np.array([ 

145 ... [ 2, -1, 4, -3], 

146 ... [ 3, 4, -1, -2], 

147 ... [ 4, 3, -2, -1], 

148 ... [-2, 1, -4, 3], 

149 ... [-3, -4, 1, 2], 

150 ... [-4, -3, 2, 1]]) 

151 >>> _schedule(dest, 1, 2, 0, 6, 1, True) 

152 False 

153 >>> dest = np.array([ 

154 ... [ 2, -1, 4, -3], 

155 ... [ 3, 4, -1, -2], 

156 ... [ 4, 0, 0, -1], 

157 ... [-2, 1, -4, 3], 

158 ... [-3, -4, 1, 2], 

159 ... [-4, -3, 2, 1]]) 

160 >>> _schedule(dest, 1, 2, 0, 6, 1, True) 

161 True 

162 >>> print(dest) 

163 [[ 2 -1 4 -3] 

164 [ 3 4 -1 -2] 

165 [ 4 3 -2 -1] 

166 [-2 1 -4 3] 

167 [-3 -4 1 2] 

168 [-4 -3 2 1]] 

169 >>> dest = np.array([ 

170 ... [ 2, -1, 4, -3], 

171 ... [ 3, 4, -1, -2], 

172 ... [ 0, 3, -2, -1], 

173 ... [-2, 0, 0, 3], 

174 ... [-3, -4, 1, 2], 

175 ... [-4, -3, 2, 1]]) 

176 >>> _schedule(dest, 0, 2, 0, 6, 1, True) 

177 True 

178 >>> print(dest) 

179 [[ 2 -1 4 -3] 

180 [ 3 4 -1 -2] 

181 [ 3 0 -1 -1] 

182 [-2 3 -2 3] 

183 [-3 -4 1 2] 

184 [-4 -3 2 1]] 

185 """ 

186 empty_slots_needed = 2 # Number of required open slots for a game. 

187 while True: 

188 for day in range(start, end, direction): # iterate over all days 

189 can_use_home: bool = y[day, home_idx] == 0 # Check for empty slot 

190 can_use_away: bool = y[day, away_idx] == 0 # Check for empty slot 

191 if can_use_home + can_use_away < empty_slots_needed: 

192 continue # Too few empty slots: Try with next day. 

193 if ((can_use_home or _re_schedule( # At least one empty slot? 

194 y, home_idx, day, end, direction)) and ( 

195 can_use_away or _re_schedule( 

196 y, away_idx, day, end, direction))): 

197 # There either were two empty slots, or one and the other game 

198 # was rescheduled. So we can schedule the game. 

199 y[day, home_idx] = away_idx + 1 

200 y[day, away_idx] = -(home_idx + 1) 

201 return True # Success! 

202 

203 # After we tried finding a perfect slot, we now try with just one slot. 

204 if empty_slots_needed >= 2: 

205 empty_slots_needed = 1 # Try requiring just one slot. 

206 continue # And execute scheduling loop again. 

207 if is_recursive: # Only if this is the root call, we can go one 

208 return False # after the attempt requiring 1 slot failed. 

209 is_recursive = True # But we can only do this once. 

210 # If we got here, we are in the root call. 

211 # We first tried to find two open slots and failed. 

212 # Then we tried to find a single open slot and tried to re-schedule 

213 # the other game to a later point in time ... an failed. 

214 # Now we try rescheduling games towards an early time. 

215 start = end - 1 

216 end = direction = -1 

217 

218 

219# Due to the recursion, caching must be disabled or we get a segfault. 

220@numba.njit(cache=False, fastmath=True, boundscheck=True) 

221def map_games_2(x: np.ndarray, y: np.ndarray) -> None: 

222 """ 

223 Translate a permutation of games to a game plan. 

224 

225 This is a straightforward decoding that places the games into the map one 

226 by one. Each game is placed at the earliest slot in which it can be 

227 placed. If a game cannot be placed, it is ignored. This will lead to many 

228 errors, which can be counted via the :mod:`~moptipyapps.ttp.errors` 

229 objective. 

230 

231 :param x: the source permutation 

232 :param y: the destination game plan 

233 

234 >>> from moptipy.utils.nputils import int_range_to_dtype 

235 >>> from moptipyapps.ttp.game_encoding import ( 

236 ... search_space_for_n_and_rounds) 

237 >>> teams = 2 

238 >>> rounds = 2 

239 >>> perm = search_space_for_n_and_rounds(teams, rounds).blueprint 

240 >>> dest = np.empty((rounds * (teams - 1), teams), 

241 ... int_range_to_dtype(-teams, teams)) 

242 >>> map_games_2(perm, dest) 

243 >>> print(dest) 

244 [[ 2 -1] 

245 [-2 1]] 

246 >>> teams = 4 

247 >>> rounds = 2 

248 >>> perm = search_space_for_n_and_rounds(teams, rounds).blueprint 

249 >>> dest = np.empty((rounds * (teams - 1), teams), 

250 ... int_range_to_dtype(-teams, teams)) 

251 >>> map_games_2(perm, dest) 

252 >>> print(dest) 

253 [[ 2 -1 4 -3] 

254 [ 3 4 -1 -2] 

255 [ 4 3 -2 -1] 

256 [-2 1 -4 3] 

257 [-3 -4 1 2] 

258 [-4 -3 2 1]] 

259 >>> from moptipyapps.ttp.instance import Instance 

260 >>> inst = Instance.from_resource("circ10") 

261 >>> perm = np.array([73,77,55,74,21,20,3,11,63,19,38,8,27,47,88,16,75, 

262 ... 45,89,36,24,80,17,40,0,32,53,82,31,13,12,66,71,6,87,84,2,60,61, 

263 ... 10,30,58,49,57,54,23,26,46,59,42,29,62,22,18,50,78,37,34,65,43, 

264 ... 48,85,86,83,56,41,5,81,52,15,51,9,4,76,7,69,67,33,79,72,35,25, 

265 ... 1,14,70,44,68,64,28,39]) 

266 >>> teams = 10 

267 >>> rounds = 2 

268 >>> dest = np.empty((rounds * (teams - 1), teams), 

269 ... int_range_to_dtype(-teams, teams)) 

270 >>> map_games_2(perm, dest) 

271 >>> print(dest) 

272 [[ -8 -9 5 7 -3 10 -4 1 2 -6] 

273 [ 5 -7 4 -3 -1 -9 2 -10 6 8] 

274 [ 10 4 -9 -2 6 -5 8 -7 3 -1] 

275 [ -4 -3 2 1 -7 8 5 -6 -10 9] 

276 [ -6 9 -5 -8 3 1 -10 4 -2 7] 

277 [ -5 10 -6 -9 1 3 -8 7 4 -2] 

278 [ 2 -1 8 6 7 -4 -5 -3 10 -9] 

279 [ 8 -10 6 5 -4 -3 9 -1 -7 2] 

280 [ 4 6 7 -1 9 -2 -3 10 -5 -8] 

281 [ -7 5 -8 -10 -2 9 1 3 -6 4] 

282 [-10 3 -2 -7 -6 5 4 -9 8 1] 

283 [ 3 -4 -1 2 10 -8 -9 6 7 -5] 

284 [ 9 -8 10 -5 4 -7 6 2 -1 -3] 

285 [ -3 -6 1 9 8 2 10 -5 -4 -7] 

286 [ -2 1 9 8 -10 7 -6 -4 -3 5] 

287 [ 7 8 -10 -6 -9 4 -1 -2 5 3] 

288 [ -9 7 -4 3 -8 -10 -2 5 1 6] 

289 [ 6 -5 -7 10 2 -1 3 9 -8 -4]] 

290 >>> int(dest.shape[0] * dest.shape[1] - np.count_nonzero(dest)) 

291 0 

292 >>> from moptipyapps.ttp.game_encoding import re_encode 

293 >>> re_encode(perm, dest) 

294 >>> print(perm) 

295 [21 32 53 63 73 3 20 55 77 88 8 11 40 60 74 19 27 51 58 89 16 38 45 66 

296 87 17 36 47 69 75 0 24 31 41 80 6 22 30 61 82 2 13 23 43 71 12 52 54 

297 65 84 10 49 57 79 81 1 28 44 68 78 7 26 39 59 64 18 34 42 46 62 9 25 

298 33 50 85 5 15 48 76 83 14 29 67 72 86 4 35 37 56 70] 

299 >>> map_games_2(perm, dest) 

300 >>> print(dest) 

301 [[ -8 -9 5 7 -3 10 -4 1 2 -6] 

302 [ 5 -7 4 -3 -1 -9 2 -10 6 8] 

303 [ 10 4 -9 -2 6 -5 8 -7 3 -1] 

304 [ -4 -3 2 1 -7 8 5 -6 -10 9] 

305 [ -6 9 -5 -8 3 1 -10 4 -2 7] 

306 [ -5 10 -6 -9 1 3 -8 7 4 -2] 

307 [ 2 -1 8 6 7 -4 -5 -3 10 -9] 

308 [ 8 -10 6 5 -4 -3 9 -1 -7 2] 

309 [ 4 6 7 -1 9 -2 -3 10 -5 -8] 

310 [ -7 5 -8 -10 -2 9 1 3 -6 4] 

311 [-10 3 -2 -7 -6 5 4 -9 8 1] 

312 [ 3 -4 -1 2 10 -8 -9 6 7 -5] 

313 [ 9 -8 10 -5 4 -7 6 2 -1 -3] 

314 [ -3 -6 1 9 8 2 10 -5 -4 -7] 

315 [ -2 1 9 8 -10 7 -6 -4 -3 5] 

316 [ 7 8 -10 -6 -9 4 -1 -2 5 3] 

317 [ -9 7 -4 3 -8 -10 -2 5 1 6] 

318 [ 6 -5 -7 10 2 -1 3 9 -8 -4]] 

319 >>> inst = Instance.from_resource("con14") 

320 >>> perm = np.array([70,114,54,51,98,31,49,46,148,169,174,151,155,110, 

321 ... 75,118,128,81,171,19,133,93,5,91,47,1,84,109,142,121,7,40,163, 

322 ... 61,20,96,165,177,160,39,73,37,101,108,119,65,2,117,164,106,60, 

323 ... 145,105,90,170,74,8,26,94,10,22,86,120,154,89,66,77,178,140,48, 

324 ... 0,52,159,25,176,135,63,57,76,161,68,124,162,29,55,80,24,45,85, 

325 ... 115,131,100,17,53,27,38,95,158,104,175,87,123,167,97,79,112, 

326 ... 172,127,136,12,44,50,102,69,144,143,113,4,181,88,166,150,59, 

327 ... 141,72,125,116,132,14,147,153,129,111,92,62,6,32,82,16,179,21, 

328 ... 3,126,134,122,149,146,36,107,34,103,42,41,18,35,78,28,137,43, 

329 ... 33,71,99,139,56,23,138,67,168,130,30,180,152,83,9,13,173,11, 

330 ... 157,156,64,15,58]) 

331 >>> teams = 14 

332 >>> rounds = 2 

333 >>> from moptipy.utils.nputils import int_range_to_dtype 

334 >>> dest = np.empty((rounds * (teams - 1), teams), 

335 ... int_range_to_dtype(-teams, teams)) 

336 >>> from moptipyapps.ttp.game_encoding_2 import map_games_2 

337 >>> map_games_2(perm, dest) 

338 >>> print(dest) 

339 [[ -8 -10 -5 14 3 7 -6 1 12 2 -13 -9 11 -4] 

340 [-14 -6 7 12 11 2 -3 9 -8 13 -5 -4 -10 1] 

341 [ 7 8 -14 9 -10 -12 -1 -2 -4 5 13 6 -11 3] 

342 [ -5 11 -8 -7 1 -14 4 3 -12 -13 -2 9 10 6] 

343 [ 3 -5 -1 -11 2 10 -9 -13 7 -6 4 14 8 -12] 

344 [ 9 -3 2 10 -13 12 8 -7 -1 -4 14 -6 5 -11] 

345 [-10 -4 13 2 -11 -9 14 12 6 1 5 -8 -3 -7] 

346 [ -4 9 -10 1 7 -8 -5 6 -2 3 -14 13 -12 11] 

347 [ -6 -11 -12 -8 10 1 13 4 -14 -5 2 3 -7 9] 

348 [ 4 -14 -13 -1 -9 11 10 -12 5 -7 -6 8 3 2] 

349 [ 10 -7 5 8 -3 14 2 -4 -13 -1 12 -11 9 -6] 

350 [ 12 14 -9 -10 13 -11 -8 7 3 4 6 -1 -5 -2] 

351 [ -3 -9 1 11 -8 13 12 5 2 -14 -4 -7 -6 10] 

352 [ 2 -1 -7 -13 -6 5 3 -14 10 -9 -12 11 4 8] 

353 [-11 -12 14 -5 4 -13 9 -10 -7 8 1 2 6 -3] 

354 [ -9 3 -2 -6 -14 4 -13 11 1 12 -8 -10 7 5] 

355 [-12 13 8 5 -4 -10 -14 -3 11 6 -9 1 -2 7] 

356 [ 8 6 10 -14 -12 -2 11 -1 13 -3 -7 5 -9 4] 

357 [ 14 -8 -11 6 9 -4 -10 2 -5 7 3 -13 12 -1] 

358 [ -2 1 -6 13 12 3 -11 14 -10 9 7 -5 -4 -8] 

359 [ 11 5 12 7 -2 9 -4 13 -6 14 -1 -3 -8 -10] 

360 [ 6 10 11 -12 -7 -1 5 -9 8 -2 -3 4 -14 13] 

361 [ 5 -13 -4 3 -1 8 -12 -6 14 11 -10 7 2 -9] 

362 [-13 7 6 -9 14 -3 -2 -11 4 -12 8 10 1 -5] 

363 [ -7 12 4 -3 6 -5 1 10 -11 -8 9 -2 14 -13] 

364 [ 13 4 9 -2 8 -7 6 -5 -3 -11 10 -14 -1 12]] 

365 """ 

366 y.fill(0) # first zero the output matrix 

367 days, n = y.shape # the number of days and teams to be scheduled 

368 div: Final[int] = n - 1 # the divisor for permutation values -> teams 

369 

370 for game in x: 

371 g = int(game) # make sure that the indices are Python integers 

372 home_idx: int = (g // div) % n # home idx is in 0..n-1 

373 away_idx: int = g % div # away index in 0..n-2 

374 if away_idx >= home_idx: # "A vs. A" games impossible 

375 away_idx += 1 # away index in 0..n-1, but != home_idx 

376 _schedule(y, home_idx, away_idx, 0, days, 1, False) 

377 

378 

379class GameEncoding2(GameEncoding): 

380 """A second encoding that transforms strings of games to game plans.""" 

381 

382 def __init__(self, instance: Instance) -> None: 

383 """ 

384 Create the game-based encoding that can reschedule games. 

385 

386 :param instance: the instance 

387 """ 

388 super().__init__(instance) 

389 self.decode = map_games_2 # type: ignore 

390 

391 # We invoke all the functions in order to enforce proper compilation. 

392 # Numba has some problems with recursive functions. 

393 # Therefore, we try to enforce that all functions used here are 

394 # invoked in an order where their parameters can be fully inferred. 

395 y: np.ndarray = GamePlanSpace(instance).create() 

396 y.fill(1) 

397 _re_schedule(y, 0, 0, 1, 1) 

398 _schedule(y, 0, 1, 0, 1, 1, False) 

399 y[0, 0] = 0 

400 _schedule(y, 0, 1, 0, 1, 1, True) 

401 y.fill(0) 

402 _re_schedule(y, 0, 0, 1, 1) 

403 _schedule(y, 0, 1, 0, 1, 1, False) 

404 x: np.ndarray = self.search_space().blueprint 

405 x.sort() 

406 map_games_2(x, y)