PROG0350 - Bus gossip
The bus drivers of a small town are known to be real gossips. When two or more buses are at the same stop at the same time, the drivers quickly get out to exchange all the latest rumors they are aware of. This way, rumors spread like a wildfire throughout the city.
Each stop is labeled with a unique integer. As shown in the illustration above, each bus runs a loop route through the city. The route of a bus can thus be described by the sequence of integers that indicate the successive stops. After the last stop in the sequence, the bus revisits the first stop of the sequence. A bus can also frequent the same stop multiple times throughout a single loop, for example if the bus runs in an eight shaped route. The first stop in the sequence is the stop where the bus leaves in the morning. Drivers that leave at the same stop in the morning also exchange rumors at that stop. A bus having route (3, 6, 9) thus successively visits the stops 3 9 6 3 9 6 3 9 6 …. A bus having route (1, 2, 3, 2) successively visits the stops 1 2 3 2 1 2 3 2 1 2 3 2 ….
Assignment
In the morning, each bus driver has heard of one new rumor that is not known by the other bus drivers. Assume that the time between successive stops is 1 minute, and that exchanging rumors at a stop takes no time. After how many minutes are all bus drivers aware of all new rumors?
In order to answer this question, you write a function busgossip that takes a tuple describing the routes of all buses. Each route is itself described as a tuple containing integers that indicate the labels of the successive stops in a single loop. The function must return an integer that indicates the number of minutes it takes before all bus drivers are aware of all new rumors. If the drivers do not succeed at exchanging all rumors by the end of the day (i.e. after $24 \times 60 = 1440$ minutes), the function must return the value -1.
Example
>>> busgossip(((1, 2, 3, 4, 5), (5, 6, 7, 8), (3, 9, 6))) 12 >>> busgossip(((1, 2, 3), (2, 1, 3), (2, 4, 5, 3))) 4 >>> busgossip(((1, 2), (2, 1))) -1
De buschauffeurs van een klein stadje staan bekend als echte roddeltantes. Wanneer twee of meer bussen op hetzelfde ogenblik aan dezelfde stopplaats halt houden, dan stappen de chauffeurs snel uit om alle nieuwe roddels die ze kennen uit te wisselen. Op die manier verspreiden de nieuwtjes zich als een lopend vuurtje door de stad.
Elke stopplaats wordt genummerd met een uniek natuurlijk getal. Zoals aangegeven in bovenstaande afbeelding, rijdt elke bus een lusvormige route doorheen de stad. De route van een bus kan dus omschreven worden door de reeks getallen die de opeenvolgende stopplaatsen aanduiden. Na de laatste stopplaats in de reeks rijdt de bus verder naar de eerste stopplaats uit de reeks. Eén enkele lus van een busroute kan eenzelfde stopplaats ook verschillende keren aandoen, bijvoorbeeld als de bus een achtvormige route aflegt. De eerste stopplaats uit de reeks is de stopplaats waar de bus 's morgens vertrekt. Chauffeurs die 's morgens aan dezelfde stopplaats vertrekken wisselen daar ook hun roddels uit. Een bus met route (3, 6, 9) doet dus achtereenvolgens de stopplaatsen 3 9 6 3 9 6 3 9 6 … aan. Een bus met stopplaatsen (1, 2, 3, 2) doet achtereenvolgens de stopplaatsen 1 2 3 2 1 2 3 2 1 2 3 2 … aan.
Opgave
's Morgens heeft elke buschauffeur één nieuwe roddel opgevangen die de andere buschauffeurs nog niet kennen. Veronderstel dat de tijd tussen twee opeenvolgende stopplaatsen telkens 1 minuut bedraagt, en dat het uitwisselen van de roddels en het stilstaan geen tijd kost. Na hoeveel minuten zijn alle buschauffeurs dan op de hoogte van alle nieuwe roddels?
Om dit te bepalen, schrijf je een functie busroddels waaraan een tuple moet doorgegeven worden die de route van elke bus bevat. Elke busroute is zelf een tuple van natuurlijke getallen, die de opeenvolgende stopplaatsen van één enkele lus aanduiden. De functie moet een natuurlijk getal teruggeven dat aangeeft na hoeveel minuten alle buschauffeurs op de hoogte zijn van alle nieuwe roddels. Als de chauffeurs er niet in slagen om alle roddels uit te wisselen voor het einde van de dag (dus na $24 \times 60 = 1440$ minuten), dan moet de functie de waarde -1 teruggeven.
Voorbeeld
>>> busroddels(((1, 2, 3, 4, 5), (5, 6, 7, 8), (3, 9, 6))) 12 >>> busroddels(((1, 2, 3), (2, 1, 3), (2, 4, 5, 3))) 4 >>> busroddels(((1, 2), (2, 1))) -1
| Added by: | Peter Dawyndt |
| Date: | 2013-03-30 |
| Time limit: | 10s |
| Source limit: | 50000B |
| Memory limit: | 1536MB |
| Cluster: | Cube (Intel G860) |
| Languages: | PY_NBC |
| Resource: | None |
RSS