Radio Frequency Assignment X57157


Statement
 

optilog

pdf   zip

html

Write a program in Python that, using the optilog library, finds a radio frequency for each radio station.

In order to use the optilog library, the program has to include something like:

from optilog.solvers.sat import *
...
solver = Glucose41()
solver.add_clauses(...)
solver.solve()
solver.model()

Input

The input is a text (in the stdin) with lists of radio stations, and for each one (in a distinct line) the list of places where they operate, like:

RAC105 bergueda baixllobregat barcelones
SER barcelones baixllobregat
40principals barcelones bages
radiodesvern baixllobregat
radioberga bergueda bages

Output

The output is also a text (in the stdout) where in every line there is a list of radio stations that can share the same frequency because they do not overlap in the same place. In this example:

{RAC105}
{radiodesvern, 40principals}
{SER, radioberga}

Notice that the order of the lines and the order inside each line is not relevant. In this example, there are three lines because this is the minimum number of distinct frequencies we need in order to get an assignment such that two radio stations that operate in the same area do not get the same frequency.

Scoring

Samples have been selected in order to ensure that there exist a unique solution up to permutations.

Public test cases
  • Input

    RAC105 bergueda baixllobregat barcelones
    SER barcelones baixllobregat
    40principals barcelones bages
    radiodesvern baixllobregat
    radioberga bergueda bages
    

    Output

    {SER, radioberga}
    {RAC105}
    {40principals, radiodesvern}
    
  • Information
    Author
    Jordi Levy
    Language
    English
    Official solutions
    Python
    User solutions
    Python