Radio Frequency Assignment X57157

optilog

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.