Coverage for moptipyapps / ttp / game_plan.py: 93%

1""" 

2A game plan assigns teams to games. 

3 

4A game plan is a two-dimensional matrix `G`. The rows are the time slots. 

5There is one column for each time. If `G` has value `v` at row `i` and 

6column `j`, then this means: 

7 

8- at the time slot `i` ... 

9- the team with name `j+1` plays 

10 + no team if `v == 0`, 

11 + *at home* against the team `v` if `v > 0`, i.e., team `v` travels 

12 to the home stadium of team `j+1` 

13 + *away* against the team `-v` if `v < 0`, i.e., team `j+1` travels 

14 to the home stadium of team `-v` and plays against them there 

15 

16Indices in matrices are zero-based, i.e., the lowest index for a row `i` is 

17`0` and the lowest index for a column `j` is also `0`. However, team names 

18are one-based, i.e., that with `1`. Therefore, we need to translate the 

19zero-based column index `j` to a team name by adding `1` to it. 

20 

21This is just a numerical variant of the game plan representation given at 

22<https://robinxval.ugent.be/RobinX/travelRepo.php>. Indeed, the `str(...)` 

23representation of a game plan is exactly the table shown there. 

24 

25Of course, if `G[i, j] = v`, then `G[i, v - 1] = -(j + 1)` should hold if 

26`v > 0`, for example. Vice versa, if `v < 0` and `G[i, j] = v`, then 

27`G[i, (-v) - 1] = j + 1` should hold. Such constraints are checked by the 

28:mod:`~moptipyapps.ttp.errors` objective function. 

29 

30The corresponding space implementation, 

31:mod:`~moptipyapps.ttp.game_plan_space`, offers the functionality to convert 

32strings to game plans as well as to instantiate them in a black-box algorithm. 

33""" 

34 

35from io import StringIO 

36from typing import Final 

37 

38import numpy as np 

39from moptipy.api.component import Component 

40from moptipy.utils.logger import CSV_SEPARATOR 

41from pycommons.types import type_error 

42 

43from moptipyapps.ttp.instance import Instance 

44 

45 

46class GamePlan(Component, np.ndarray): 

47 """A game plan, i.e., a solution to the Traveling Tournament Problem.""" 

48 

49 #: the TTP instance 

50 instance: Instance 

51 

52 def __new__(cls, instance: Instance) -> "GamePlan": 

53 """ 

54 Create a solution record for the Traveling Tournament Problem. 

55 

56 :param cls: the class 

57 :param instance: the solution record 

58 """ 

59 if not isinstance(instance, Instance): 

60 raise type_error(instance, "instance", Instance) 

61 

62 n: Final[int] = instance.n_cities # the number of teams 

63 # each team plays every other team 'rounds' times 

64 n_days: Final[int] = (n - 1) * instance.rounds 

65 obj: Final[GamePlan] = super().__new__( 

66 cls, (n_days, n), instance.game_plan_dtype) 

67 #: the TTP instance 

68 obj.instance = instance 

69 return obj 

70 

71 def __str__(self): 

72 """ 

73 Convert the game plan to a compact string. 

74 

75 The first line of the output is a flattened version of this matrix 

76 with the values being separated by `;`. Then we place an empty line. 

77 

78 We then put a more easy-to-read representation and follow the pattern 

79 given at https://robinxval.ugent.be/RobinX/travelRepo.php, which is 

80 based upon the notation by Easton et al. Here, first, a row with the 

81 team names separated by spaces is generated. Then, each row contains 

82 the opponents of these teams, again separated by spaces. If an 

83 opponent plays at their home, this is denoted by an `@`. 

84 If a team has no scheduled opponent, then this is denoted as `-`. 

85 

86 :return: the compact string 

87 """ 

88 csv: Final[str] = CSV_SEPARATOR 

89 sep: str = "" 

90 teams: Final[tuple[str, ...]] = self.instance.teams 

91 len(teams) 

92 

93 with StringIO() as sio: 

94 for k in self.flatten(): 

95 sio.write(sep) 

96 sio.write(str(k)) 

97 sep = csv 

98 

99 sio.write("\n\n") 

100 

101 sep = "" 

102 for t in teams: 

103 sio.write(sep) 

104 sio.write(t) 

105 sep = " " 

106 

107 for row in self: 

108 sio.write("\n") 

109 sep = "" 

110 for d in row: 

111 sio.write(sep) 

112 if d < 0: 

113 sio.write(f"@{teams[-d - 1]}") 

114 elif d > 0: 

115 sio.write(teams[d - 1]) 

116 else: 

117 sio.write("-") 

118 sep = " " 

119 

120 return sio.getvalue()