Lab Assignment #2
La Liga
Spanish Soccer League Schedule
Introduction
In this exercise we will encode in ASP
the schedule generation method for the Spanish Soccer
League and impose different constraints to restrict the
number of possible assignments. The Spanish Soccer League
for the first division follows a fixed round robin method
to determine the schedule for all matches in a given
season. This method guarantees that each team eventually
matches the rest of teams twice: once as local and once as
visitor. Starting from a given initial assignment (by
draw), the method establishes all the rounds in a fixed
way, so that, knowing the initial round, all the rest can
be easily decided afterwards.
This lab assignment will consist in
encoding the round robin method and adding several
constraints on the resulting matches that will act
restricting the possible solutions for the initial round.
The round robin method
The soccer league first division
consists of n=20
teams. This means that each team must play against the
other 19 teams both as local and as visitor. As a result,
we will have 19 x 2 = 38
rounds. These rounds are actually divided into a first lap
comprising rounds 1..19 and
a second lap 20..38 which
is a repetition of the first lap, but switching the roles
of local and visitor in each match. For simplicity, we
will strictly concentrate on the first lap, that is, match
rounds 1..19.
The round robin method deals with a table of 10 rows x 2
columns and locates each team in one position of the table.
Each table row is a match where the team on the left is
local and the team on the right is visitor. The method fixes
two different types of shifts from the current round R
to the next one R+1,
depending on whether R is odd or even:
-
Odd rounds: for rounds 1, 3,
5, ... the next round is computed by switching first
the columns and then making a complete rotation
downwards on the right column. If we enumerate the
table cells from 0 to 19, in columns from up to down,
the following diagram shows where each original
position ends up after the rotation:
0
|
10
|
1
|
11
|
2
|
12
|
3
|
13
|
4
|
14
|
5
|
15
|
6
|
16
|
7
|
17
|
8
|
18
|
9
|
19
|
round 1
|
===>
|
10
|
9
|
11
|
0
|
12
|
1
|
13
|
2
|
14
|
3
|
15
|
4
|
16
|
5
|
17
|
6
|
18
|
7
|
19
|
8
|
round 2
|
-
Even rounds: for rounds 2,
4, 6, ... the next round is computed by, again,
switching first the columns and then making a rotation
upwards in the right column, but using the first and
last elements of the left column in the rotation too.
This is shown in the diagram:
0
|
10
|
1
|
11
|
2
|
12
|
3
|
13
|
4
|
14
|
5
|
15
|
6
|
16
|
7
|
17
|
8
|
18
|
9
|
19
|
round 2
|
===>
|
0
|
1
|
11
|
2
|
12
|
3
|
13
|
4
|
14
|
5
|
15
|
6
|
16
|
7
|
17
|
8
|
18
|
9
|
10
|
19
|
round 3
|
-
The joker team: if
we repeat these two shifts alternatively, it is not
difficult to see that there is one team (we will call
the joker) that is always placed in the same
positions: the last row as local (odd rounds) and the
first row as visitor (even rows). In the diagrams
above, we have coloured the joker team positions in
red.
-
Exceptions: by default, the
final match assignment is the one fixed by the
rotations above. However, in the last two rounds, an exception
is made: the joker team exchanges its role
(local/visitor) with its opponent. This is made to
avoid that a team repeats as local in more than two
consecutive matches.
The file rounds.txt
contains the complete pattern for the 19 rounds, assuming
we enumerate all teams using their table cell position at
the initial round. Warning: the ASP
encoding must generate this pattern using
generic rules rather than storing it as an
extensional table. For instance, the code must allow
varying the number n=20
of teams in a parametric way for any number n of teams. For
simplicity, we will always assume that n is an even number
greater than 2 (when n is
odd, one team would rest in each round).
Generate and test
In the current season 2016/2017, the 20
teams are described below:
team(ala,"Deportivo Alavés
S.A.D").
team(ath,"Athlétic Club de Bilbao").
team(atl,"Atlético de Madrid").
team(cel,"RC Celta de Vigo").
team(dep,"RC Deportivo de La Coruña
S.A.D").
team(eib,"SD Eibar").
team(esp,"RCD Espanyol").
team(fcb,"FC Barcelona").
team(gra,"Granada CF").
team(pal,"UD Las Palmas").
team(leg,"CD Leganés").
team(mal,"Málaga CF").
team(osa,"CA Osasuna").
team(bet,"Real Betis").
team(rma,"Real Madrid CF").
team(rso,"Real Sociedad SAD").
team(sev,"Sevilla FC").
team(spo,"Real Sporting de Gijón").
team(val,"Valencia CF").
team(vil,"Villarreal CF").
|
You can use the team abreviation to
encode the matches. Once the round robin method is
encoded, our program must choose an arbitrary assignment
for the table cells for the initial round among teams from
the table above. Using the first round assignment,
we want to additionally check the following constraints on
the resulting schedule:
- Two neighbour teams will never repeat location (local
or visitor) in the same round. The pairs of neighbour
teams are: Espanyol and Barcelona; Atlético and Real
Madrid; Sevilla and Betis.
- The clásico Real Madrid vs Barcelona (or vice
versa) cannot occur in the first three rounds of the
competition.
- Check that no team plays more than 2 times
consecutively as local or as visitor. Use a predicate to
find out which teams repeat their travel type (local or
visitor) 2 consecutive times, and in which rounds.
- Weak constraint: try to avoid two derbis in the
same round. A derbi is any match between two neighbours
plus the matches: Real Madrid vs Barcelona; Celta vs
Deportivo; Athletic vs Real Sociedad.
Assessment & delivery
The maximum grade for this exercise (1a)
is 1 point = 10% of the course. The deadline for
delivery is Friday, April 28th,
2017 using the MOODLE assignment. Exercises
can be made by groups of 2 students at most. If so, only
one student is required to deliver the files in moodle,
but all source files must contain the names of the two
group members.
Delivery: submit all files as a .zip and
include a file README.txt explaining how to use them,
especially if you write different ASP source files or you
use command line defined constants.
|