Met 18 960 inwoners per km2 is Monaco het meest dichtbevolkte land van Europa, terwijl IJsland met 3.5 inwoners per km2 het meest dunbevolkt is. Om de beschikbare ruimte beter te verdelen, kunnen we een volksverhuizing organiseren door de Europese landen enerzijds te rangschikken volgens stijgend inwonersaantal en anderzijds volgens stijgende oppervlakte. Het zou dan logisch zijn om de inwoners uit het land met het kleinste inwonersaantal (Vaticaanstad) te laten verhuizen naar het land met de kleinste oppervlakte (Vaticaanstad), de inwoners uit het land met het tweede kleinste inwonersaantal (San Marino) naar het land met de tweede kleinste oppervlakte (Monaco), …, en de inwoners uit het land met het grootste inwonersaantal (Rusland) naar het land met de grootste oppervlakte (Rusland).
Land $$B$$ is de bestemming van land $$A$$ als de inwoners uit land $$A$$ volgens deze strategie moeten verhuizen naar land $$B$$. Op onderstaande kaart kan je de bestemmingen van alle Europese landen aflezen. Enkel de inwoners uit de blauw gemarkeerde landen (Vaticaanstad, Frankrijk en Rusland) mogen in hun eigen land blijven wonen.
Als we elk land verbinden met zijn bestemming, dan ontstaan er cirkels van landen die door de volksverhuizing een ware stoelendans uitvoeren. Bij de volksverhuizing van de Europese landen kunnen we acht dergelijke cirkels identificeren.
Opgave
Een landenbestand is een tekstbestand waarvan elke regel vijf informatievelden bevat over een land: i) de naam van het land, ii) de naam van de hoofdstad, iii) de bevolkingsdichtheid (inwoners/km2), iv) de oppervlakte (km2) en v) het inwonersaantal. De informatievelden worden van elkaar gescheiden door tabs en bevatten zelf geen tabs. De laatste drie velden zijn numerieke velden die natuurlijke getallen bevatten. Dit zijn bijvoorbeeld enkele regels uit een landenbestand (europe.txt1) met informatie over alle Europese landen:
Albania Tirana 100 28748 2870325 Andorra Andorra la Vella 160 468 74794 Austria Vienna 106 83879 8857960 Belarus Minsk 46 207595 9498700 Belgium Brussels 375 30689 11515793 ... Spain Madrid 92 505990 46659302 Sweden Stockholm 23 450295 10215250 Switzerland Bern 206 41285 8508898 Ukraine Kyiv 70 603628 42220824 United Kingdom London 272 242495 66040229 Vatican City Vatican City 1684 0 825
Gevraagd wordt om een bash shell script migration te schrijven waaraan een landenbestand moet doorgegeven worden. Als tweede argument kan aan het script optioneel ook nog de naam doorgegeven worden van een land dat in het landenbestand voorkomt. Het script mag ervan uitgaan dat er enkel geldige argumenten doorgegeven worden, zonder dat dit expliciet moet gecontroleerd worden.
Bestemmingen
Als er enkel een landenbestand wordt doorgegeven, dan moet het script een overzicht uitschrijven naar stdout met de bestemming van elk land uit het landenbestand. Elke regel van het overzicht bestaat uit de naam van een land (van herkomst), gevolgd door een spatie, een pijltje naar rechts (->), nog een spatie en de naam van het land van bestemming. De regels van het overzicht moeten alfabetisch geranschikt worden volgens land van herkomst (zonder onderscheid te maken tussen hoofdletters en kleine letters). Zo moet voor het landenbestand europe.txt2 bijvoorbeeld een overzicht uitgeschreven worden dat er als volgt uitziet:
Albania -> Denmark
Andorra -> Malta
Austria -> Hungary
Belarus -> Serbia
Belgium -> United Kingdom
...
Sweden -> Bulgaria
Switzerland -> Portugal
Ukraine -> Germany
United Kingdom -> Spain
Vatican City -> Vatican City
Dit overzicht geeft aan dat de inwoners van Albanië naar Denemarken moeten verhuizen, de inwoners van Andorra naar Malta, de inwoners van Oostenrijk naar Hongarije, ... en de inwoners van Vaticaanstad mogen in hun eigen land blijven wonen. Deze volksverhuizing kan bepaald worden door de landen eerst te rangschikken volgens stijgend inwonersaantal (vijfde veld):
1 Vatican City 2 San Marino 3 Liechtenstein 4 Monaco 5 Andorra ... 42 Italy 43 United Kingdom 44 France 45 Germany 46 Russia
Daarna worden de landen ook gerangschikt volgens stijgende oppervlakte (vierde veld):
1 Vatican City 2 Monaco 3 San Marino 4 Liechtenstein 5 Malta ... 42 Sweden 43 Spain 44 France 45 Ukraine 46 Russia
Opmerking
Als we in deze opgave landen in stijgende volgorde rangschikken volgens één van hun numerieke eigenschappen (inwonersaantal of oppervlakte), dan worden landen met dezelfde numerieke waarde voor die eigenschap verder in alfabetische volgorde gesorteerd zonder daarbij onderscheid te maken tussen hoofdletters en kleine letters.
We kunnen de bestemmingen van de landen dan bepalen door deze twee rangschikkingen naast elkaar te zetten:
Vatican City -> Vatican City San Marino -> Monaco Liechtenstein -> San Marino Monaco -> Liechtenstein Andorra -> Malta ... Italy -> Sweden United Kingdom -> Spain France -> France Germany -> Ukraine Russia -> Russia
Om het gevraagde overzicht te bekomen, moeten deze bestemming enkel nog alfabetisch gerangschikt worden volgens land van herkomst (zonder onderscheid te maken tussen hoofdletters en kleine letters).
Cirkel
Als naast een landenbestand ook nog de naam $$L$$ van een land wordt doorgegeven, dan moet het script naar stdout een regel uitschrijven met een oplijsting van alle landen in de cirkel waar land $$L$$ deel van uitmaakt. De lijst begint met land $$L$$ en elk land wordt gevolgd door zijn bestemming. Het laatste land uit de lijst heeft als bestemming land $$L$$. Opeenvolgende landen worden van elkaar gescheiden door een spatie, een pijltje naar rechts (->), en nog een spatie.
De cirkel van Rusland is bijvoorbeeld gewoon
Russia
want de inwoners van Rusland moeten niet verhuizen. De cirkel van Belarus is
Belarus -> Serbia -> Czech Republic
want de inwoners van Belarus moeten naar Servië verhuizen, de inwoners van Servië moeten naar Tsjechië verhuizen, en de inwoners van Tsjechië moeten naar Belarus verhuizen.
Voorbeeld
In onderstaande voorbeeldsessie gaan we ervan uit dat het tekstbestand europe.txt3 zich in de huidige directory bevindt.
$ migration europe.txt
Albania -> Denmark
Andorra -> Malta
Austria -> Hungary
Belarus -> Serbia
Belgium -> United Kingdom
...
Sweden -> Bulgaria
Switzerland -> Portugal
Ukraine -> Germany
United Kingdom -> Spain
Vatican City -> Vatican City
$ migration europe.txt Germany
Germany -> Ukraine
$ migration europe.txt Belarus
Belarus -> Serbia -> Czech Republic
$ migration europe.txt Albania
Albania -> Denmark -> Ireland -> Bosnia and Herzegovina -> Estonia -> Slovenia -> Belgium -> United Kingdom -> Spain -> Norway -> Croatia -> Slovakia -> Latvia
$ migration europe.txt Andorra
Andorra -> Malta -> Luxembourg -> Cyprus -> Montenegro -> Kosovo -> North Macedonia -> Moldova -> Switzerland -> Portugal -> Greece -> Romania -> Poland -> Finland -> Lithuania -> Netherlands -> Italy -> Sweden -> Bulgaria -> Austria -> Hungary -> Iceland
$ migration europe.txt France
France
$ migration europe.txt Russia
Russia
$ migration europe.txt "Vatican City"
Vatican City
$ migration europe.txt "San Marino"
San Marino -> Monaco -> Liechtenstein