PROG0369 - Doodle
Doodle is an online tool for scheduling activities (meetings, parties, …) that need to be attended by several people. All participants are polled to indicate on a calendar when they are available, so that the coordinator of the activity can fix a time and date for the activity that meets everyone's availabilities.
Assignment
A text file contains the information of a doodle where $m$ people have indicates their availabilities for $n$ successive days. The file contains $m$ lines, where each line describes the availabilities of a single person. Each line contains $n$ letters that indicate whether (letter V) or not (letter X) that person $n$ is available on each of the successive days. The doodle that is graphically represented above is thus stored in a text format using the following format:
VVVXVVXXXXXXVV
XVVXVVXXXXXXVV
VVXXVVXXXXXXVV
Write a function activity that can be used to schedule an activity based on a filled up doodle. The location of the text file containing the information of the doodle must be passed as the first argument to the function. The function also has a second optional parameter days, that indicates how many days the activity lasts. If no explicit value is passed for this parameter, a one-day activity is assumed.
Based on the provided information, the function must look for the first period (spanning the given number of successive days) where all participants of the activity are available. If such a period has been found, the function must return the index of the first day of the period (doodle columns represent successive days, indexed from 1). If no such period was found, the function must return the value -1.
Example
In the following interactive session we assume that the text files doodle1.txt and doodle2.txt are located in the current directory.
>>> activity('doodle1.txt') 2 >>> activity('doodle1.txt', 2) 5 >>> activity('doodle2.txt', 3) -1
Doodle is een online toepassing voor het inplannen van activiteiten (vergaderingen, feestjes, …) waaraan verschillende personen moeten deelnemen. Aan de deelnemers wordt gevraagd om op een kalender aan te geven wanneer ze vrij zijn, zodat de coördinator van de activiteit de datum en het uur kan vastleggen waarop iedereen zich kan vrijmaken.
Opgave
Een tekstbestand bevat de informatie van een doodle waarop $m$ personen hun beschikbaarheid hebben opgegeven voor $n$ opeenvolgende dagen. Het bestand bevat $m$ regels, waarbij elke regel de beschikbaarheid van één persoon aangeeft. Elke regel bevat $n$ letters die aangeven of de persoon op elk van de $n$ opeenvolgende dagen beschikbaar is (letter V) of niet (letter X). De doodle die hierboven grafisch wordt weergegeven, wordt als volgt opgeslagen in een tekstbestand:
VVVXVVXXXXXXVV
XVVXVVXXXXXXVV
VVXXVVXXXXXXVV
Schrijf een functie activiteit waarmee op basis van een ingevulde doodle een activiteit kan ingepland worden. De locatie van een tekstbestand dat de informatie van de doodle bevat, moet als eerste argument aan de functie doorgegeven worden. De functie heeft ook nog een tweede optionele parameter dagen, die aangeeft over hoeveel opeenvolgende dagen de activiteit loopt. Indien geen expliciete waarde wordt doorgegeven voor deze parameter, dan wordt een activiteit van één dag verondersteld.
Op basis van de gegeven informatie moet de functie op zoek gaan naar de eerste periode (bestaande uit het opgegeven aantal opeenvolgende dagen) waarbinnen alle deelnemers aan de activiteit zich vrij kunnen maken. Indien een dergelijk periode gevonden wordt, dan moet de functie de index van de eerste dag van die periode teruggeven (de kolommen van de doodle corresponderen met opeenvolgende dagen, en deze worden geïndexeerd vanaf 1). Indien geen geschikte periode gevonden wordt, dan moet de functie de waarde -1 teruggeven.
Voorbeeld
Bij onderstaande voorbeeldsessie gaan we ervan uit dat de tekstbestanden doodle1.txt en doodle2.txt zich in de huidige directory bevinden.
>>> activiteit('doodle1.txt') 2 >>> activiteit('doodle1.txt', 2) 5 >>> activiteit('doodle2.txt', 3) -1
| Added by: | Peter Dawyndt |
| Date: | 2013-04-04 |
| Time limit: | 10s |
| Source limit: | 50000B |
| Memory limit: | 1536MB |
| Cluster: | Cube (Intel G860) |
| Languages: | PY_NBC |
| Resource: | None |
RSS