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:

  1. 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.
  2. The clásico Real Madrid vs Barcelona (or vice versa) cannot occur in the first three rounds of the competition.
  3. 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.
  4. 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.
Maintained by Pedro Cabalar. Last update 22/2/2017