I won't guess when shovel (attached to board) could be useful :(
This problem is brought to us by our colleague Christian Gjedrem who encountered it at technical interview for Palantir Technologies. Our version may have non-important differences.
Some travellers need to travel through the network of cities. By coincidence there is an outbreak of some contagious (but not very dangerous) disease. So the travellers may become sick and share virus between them when they visit the same city. However recovering is fast and no fatalities occur.
This is a very good model for studying statistics of epidemy spreading. One can slightly manipulate input data and see that, depending on relation between amount of cities and travellers, the disease can either dissolve fast or on contrary plague the whole population endlessly. But before anything could be studied, we need an implementation of this model :)
So here are the rules:
- Every person can be in either of 3 conditions: healthy, sick or recovering
- If person is sick this day, he/she becomes recovering next day and healthy the day after.
- If healthy person is in contact (in the same city) with sick or recovering, he/she becomes sick the next day.
- For every traveller we have a route consisting of several cities. Every day the next city is visited and when the route ends, traveller restart from beginning (i.e. route is cyclic).
We want to monitor the process either till everyone becomes healthy, or 100 days pass (then emergency is
declared and all travellers are put to hospital).
Input data: will have number of travellers in the first line.
The following lines describe one traveller each.
For each traveller description gives initial state and route. Route consists of city codes (like IATA airport
codes).
There would be about 40 travellers and route for everyone includes less than dosen cities.
Output data: should give the names of people who were last to recover (in other words - who were
not healthy the day before all become healthy). If day 99 is reached without total recovery, stop here and
output names of sick and recovering travellers on that day.
Also please add (at the end) the number of day for which this output is provided.
In both cases names should be sorted alphabetically and separated with space.
Example:
input:
8
Pat sick XPU-JBK-TNU-BEN-HEM-ZJY-IMY-WFA-PPT
Xan sick KSB-TRV-XPU-JBK-TNU-BEN-HEM-IMY-WFA-NND
Mel sick KSB-TRV-XPU-TNU-BEN-HEM-ZJY-IMY-WFA-PPT-NND
Nick healthy KSB-TRV-JBK-HEM-IMY-WFA
Alf recovering KSB-TRV-XPU-JBK-TNU-BEN-IMY-WFA-NND
Tim healthy TRV-XPU-TNU-HEM-ZJY-PPT-NND
Irv recovering KSB-TRV-XPU-JBK-BEN-HEM-ZJY-IMY-PPT
Andy recovering XPU-JBK-TNU-BEN-HEM-ZJY-IMY-PPT-NND
answer:
Andy Pat 10
In this example we have only 2 healthy persons on day 0. One of them (Nick) is in the same city (KSB) with
Xan, Mel, Alf and Irv so he gets infection and becomes sick on day 1. The other (Tim) is in TRV so he remains
in good health. Moreover he remains healthy on the day after (2) as he was in XPU on day 1 and there were
no one at all. He only got virus when he arrives in TNU, probably, from Andy, who recovered on day 1 but got
infected again from Pat whom he met in JBK while she was recovering.