SPOJ.com - Problem PROG0475

PROG0475 - Districts

no tags

In Belgium a borough is the territory of a former municipality that was independent before the big municipal reorganizations in the 1960s-70s. A merged municipality (abbreviated municipality) therefore counts as many boroughs as there were once communities before the merger. A former municipality may call itself a borough if it was an independent municipality on January 1, 1961, the official start date of the great reorganization.

Borough sign on the border of the Vladslo borough in the municipality of Diksmuide.

The name borough has no legal or governing consequences. However, on the basis of the area of the former municipalities it is possible to set up municipal departments. There a local administrative office can be established in a borough hall, often in the former town hall, which offers a limited service for administrative formalities (population, marital status), of which the documents will be sent to the central administration for processing.The police may have a department or commissioner's office on the same premises. Cultural activities (library, meeting rooms) can also be present.

Assignment

Given is a file with all names of the boroughs from a specific region. Each line of the file contains the name of a borough, followed by a tab and the name of the (merger) municipality to which the borough now belongs. Asked:

Write a function readMunicipalities to which the name of a text file must be passed. This text file contains a listing of all the boroughs in a particular region. The function must return a dictionary, that shows the names of all the (merger) municipalities in that region on the collection of all the boroughs of which the (merger) municipality exists.
Write a function searchMunicipalities to which two arguments should be passed: the name of a borough and a dictionary that shows the names of the(merger) municipalities on a collection of all boroughs of which the municipality exists. The function must return a collection of the names of all the (merger) municipalities that have a borough with the specified name.
Write a function compounds to which a dictionary must be passed that shows the names of (merger) municipalities on a set of all the boroughs of which the (merger) municipality exists. The function must return a collection of the names of all the (merger) municipalities in the dictionary, of which the name of the municipality contains at least one hyphen (-), and if you split the name at the hyphens, all parts also form the name of a borough. Thus, the Flemish municipality of Knokke-Heist, for example, has two names: Knokke and Heist.

Example

In the following interactive example session we assume that the file vlaams_gewest.txt is in the current directory.

>>> boroughs = readMunicipalities('vlaams_gewest.txt')
>>> boroughs['Anzegem']
{'Anzegem', 'Gijzelbrechtegem', 'Tiegem', 'Kaster', 'Vichte', 'Ingooigem'}
>>> boroughs['Oostende']
{'Stene', 'Zandvoorde', 'Oostende'}
>>> boroughs['Zonnebeke']
{'Zandvoorde', 'Zonnebeke', 'Geluveld', 'Passendale', 'Beselare'}

>>> searchMunicipalities('Tiegem', boroughs)
{'Anzegem'}
>>> searchMunicipalities('Vladslo', boroughs)
{'Diksmuide'}
>>> searchMunicipalities('Zandvoorde', boroughs)
{'Zonnebeke', 'Oostende'}
>>> searchMunicipalities('Heusden', boroughs)
{'Destelbergen', 'Heusden-Zolder'}
>>> searchMunicipalities('Berchem', boroughs)
{'Antwerpen', 'Kluisbergen'}
>>> searchMunicipalities('Meldert', boroughs)
{'Hoegaarden', 'Lummen', 'Aalst'}
>>> searchMunicipalities('Beveren', boroughs)
{'Beveren', 'Waregem', 'Roeselare', 'Alveringem'}

>>> compounds(boroughs)
{'Knokke-Heist', 'Langemark-Poelkapelle', 'Scherpenheuvel-Zichem', 'Hamont-Achel', 'Houthalen-Helchteren', 'Lo-Reninge', 'Erpe-Mere', 'Spiere-Helkijn', 'Meeuwen-Gruitrode', 'Dilsen-Stokkem', 'Heusden-Zolder', 'Hechtel-Eksel'}

In België is een deelgemeente het grondgebied van een voormalige gemeente die vóór de grote gemeentelijke herindelingen in de jaren 1960-'70 nog zelfstandig was. Binnen een fusiegemeente (kortweg gemeente) liggen dus net zoveel deelgemeenten als gemeenten waaruit de fusiegemeente ooit is ontstaan. Een voormalige gemeente mag zich deelgemeente noemen als het een onafhankelijke gemeente was op 1 januari 1961, de officiële startdatum van de grote herindelingsoperatie.

Plaatsnaambord op de grens van deelgemeente Vladslo in de gemeente Diksmuide.

De naam deelgemeente heeft geen enkele juridische of bestuurlijke consequentie. Men kan wel, al dan niet op basis van de gebiedsomschrijving van de vroegere gemeenten, gemeenteafdelingen oprichten. Daar kan men plaatselijk een administratief bureau vestigen in een deelgemeentehuis, vaak in het vroegere gemeentehuis, dat een beperkte dienst aanbiedt voor administratieve formaliteiten (bevolking, burgerlijke stand) waarvan de documenten dan naar de centrale administratie worden doorgestuurd voor afhandeling. De politie kan in dezelfde lokalen een afdeling of commissariaat hebben. Culturele activiteiten (bibliotheek, vergaderzalen) kunnen er eveneens bij aansluiten.

Opgave

Gegeven is een bestand dat de namen alle deelgemeenten oplijst uit een bepaalde regio. Elke regel van het bestand bevat de naam van een deelgemeente, gevolgd door een tab en de naam van de (fusie)gemeente waartoe de deelgemeente nu behoort. Gevraagd wordt:

Schrijf een functie leesGemeenten waaraan de naam van een tekstbestand moet doorgegeven worden. Dit tekstbestand bevat een oplijsting van alle deelgemeenten uit een bepaalde regio. De functie moet een dictionary teruggeven, die de namen van alle (fusie)gemeenten uit die regio afbeeldt op de verzameling namen van alle deelgemeenten waaruit de (fusie)gemeente bestaat.
Schrijf een functie zoekGemeenten waaraan twee argumenten moeten doorgegeven worden: de naam van een deelgemeente en een dictionary die namen van (fusie)gemeenten afbeeldt op een verzameling van alle deelgemeenten waaruit de (fusie)gemeente bestaat. De functie moet een verzameling teruggeven die de namen van alle (fusie)gemeenten bevat die een deelgemeente hebben met de opgegeven naam.
Schrijf een functie samenstellingen waaraan een dictionary moet doorgegeven worden die namen van (fusie)gemeenten afbeeldt op een verzameling van alle deelgemeenten waaruit de (fusie)gemeente bestaat. De functie moet een verzameling met de namen van alle (fusie)gemeenten uit de dictionary teruggeven, waarvoor de naam van de gemeente minstens één koppelteken (-) bevat en als je de naam opsplitst volgens de koppeltekens, alle onderdelen ook de naam van een deelgemeente vormen. Zo heeft de Vlaamse gemeente Knokke-Heist bijvoorbeeld twee deelgemeenten met namen Knokke en Heist.

Voorbeeld

Bij onderstaande voorbeeldsessie gaan we ervan uit dat het bestand vlaams_gewest.txt zich in de huidige directory bevindt.

>>> deelgemeenten = leesGemeenten('vlaams_gewest.txt')
>>> deelgemeenten['Anzegem']
{'Anzegem', 'Gijzelbrechtegem', 'Tiegem', 'Kaster', 'Vichte', 'Ingooigem'}
>>> deelgemeenten['Oostende']
{'Stene', 'Zandvoorde', 'Oostende'}
>>> deelgemeenten['Zonnebeke']
{'Zandvoorde', 'Zonnebeke', 'Geluveld', 'Passendale', 'Beselare'}

>>> zoekGemeenten('Tiegem', deelgemeenten)
{'Anzegem'}
>>> zoekGemeenten('Vladslo', deelgemeenten)
{'Diksmuide'}
>>> zoekGemeenten('Zandvoorde', deelgemeenten)
{'Zonnebeke', 'Oostende'}
>>> zoekGemeenten('Heusden', deelgemeenten)
{'Destelbergen', 'Heusden-Zolder'}
>>> zoekGemeenten('Berchem', deelgemeenten)
{'Antwerpen', 'Kluisbergen'}
>>> zoekGemeenten('Meldert', deelgemeenten)
{'Hoegaarden', 'Lummen', 'Aalst'}
>>> zoekGemeenten('Beveren', deelgemeenten)
{'Beveren', 'Waregem', 'Roeselare', 'Alveringem'}

>>> samenstellingen(deelgemeenten)
{'Knokke-Heist', 'Langemark-Poelkapelle', 'Scherpenheuvel-Zichem', 'Hamont-Achel', 'Houthalen-Helchteren', 'Lo-Reninge', 'Erpe-Mere', 'Spiere-Helkijn', 'Meeuwen-Gruitrode', 'Dilsen-Stokkem', 'Heusden-Zolder', 'Hechtel-Eksel'}

Submit solution!

Added by:	Peter Dawyndt
Date:	2014-04-15
Time limit:	10s
Source limit:	50000B
Memory limit:	1536MB
Cluster:	Cube (Intel G860)
Languages:	PY_NBC
Resource:	None