Misschien was dit wel onvermijdelijk: een team van wiskundigen en informatici heeft de meest efficiënte kroegentocht voor het Verenigd Koninkrijk uitgestippeld. Ze berekenden de kortst mogelijke gesloten lus1 die alle 49 687 pubs van het land met elkaar verbindt. Om de tocht te vervolledigen, moet je in totaal wel nog altijd 63 739 687 meter afleggen — ongeveer een zesde van de afstand van de Aarde tot de maan. Maar omdat het een lus is, kan je overal aan je kroegentocht beginnen, om uiteindelijk toch weer veilig thuis te komen.

UK49687
De kortst mogelijke gesloten lus (63�� meter) die alle 49.687 pubs van het Verenigd Koninkrijk met elkaar verbindt.

Ondanks de mondaine toepassing is dit een absolute topprestatie op het vlak van de computationele complexiteitstheorie — een doorbraak in het oplossen van het zogenaamde handelsreizigersprobleem2 (travelling salesman problem3; TSP) dat vraagt om de kortste route die één keer langs elk van een reeks punten passeert. De UK49687 kroegentocht4 omvat meer dan 100 keer het vorige recordaantal punten op een wegenkaart waarvoor het handelsreizigersprobleem werd opgelost. Hoofdonderzoeker William Cook van de Universiteit van Waterloo5 schreef hierover:

We hadden uiteraard niet voor ogen om alles wat de wiskunde en de informatica te bieden hebben in te zetten om het lot van een rondtrekkende caféganger te verbeteren. De wereld heeft maar een beperkt aantal grondstoffen en het doel van de toegepaste wiskunde en informatica — in het bijzonder wiskundige optimalisatie en operationeel onderzoek — is om manieren te vinden om deze grondstoffen zo efficiënt mogelijk te gebruiken.

Opgave

Het tekstbestand pubs.csv6 bevat een dataset met informatie over 51 566 pubs in het Verenigd Koninkrijk. De eerste regel bevat een hoofding. Elke volgende regel bevat gegevens over één pub, bestaande uit negen velden die telkens van elkaar gescheiden worden door een puntkomma (;):

  1. fas_id (int): unieke ID (natuurlijk getal) waaronder de pub geregistreerd werd bij de Food Standard Agency7

  2. name (string): naam van de pub

  3. address (string): adres van de pub

  4. postcode (string): postcode van de pub

  5. easting (int): eerste coördinaat waarop de pub gelegen is in een geprojecteerd coördinatensysteem

  6. northing (int): tweede coördinaat waarop de pub gelegen is in een geprojecteerd coördinatensysteem

  7. latitude (float): breedtegraad waarop de pub gelegen is (reëel getal in het interval $$\left[-90, 90\right]$$)

  8. longitude (float): lengtegraad waarop de pub gelegen is (reëel getal in het interval $$\left]-180, 180\right]$$)

  9. local_authority (string): lokale authoriteit waaronder de pub valt

De velden bevatten zelf geen puntkomma's (;). De hoofding bevat de namen van de velden.

Gevraagd wordt om — gebruikmakend van de teksteditors vi of vim — een reeks commando's op te stellen die achtereenvolgens de volgende opdrachten uitvoeren. Probeer voor elke opdracht zo weinig mogelijk commando's te gebruiken en zorg er voor dat elk van deze commando's uit zo weinig mogelijk tekens bestaat. De commando's mogen geen programmeerbare filters (bv. awk) gebruiken. Alle opdrachten moeten na elkaar uitgevoerd worden. De opdrachten mogen de eerste regel (hoofding) niet wijzigen, tenzij dit expliciet anders vermeld staat. Ter controle kan je gebruikmaken van de meegeleverde bestanden pubs.i.csv (ZIP8), die telkens de inhoud van het bestand bevatten nadat de $$i$$-de opdracht werd uitgevoerd.

  1. Verwijder de eerste (easting) en de tweede (northing) coördinaat waarop de pub gelegen is in een geprojecteerd coördinatensysteem. Ook de hoofding moet mee aangepast worden. Zo moet

    fas_id;name;address;postcode;easting;northing;latitude;longitude;local_authority
24;Anchor Inn;Upper Street, Stratford St Mary, Colchester, Essex;CO7 6LW;604748;234405;51.97039;0.979328;Babergh
30;Angel Inn;Egremont Street, Glemsford, Sudbury, Suffolk;CO10 7SA;582888;247368;52.094427;0.668408;Babergh
63;Black Boy Hotel;7 Market Hill, Sudbury, Suffolk;CO10 2EA;587356;241327;52.038683;0.730226;Babergh
64;Black Horse;Lower Street, Stratford St Mary, Colchester, Essex;CO7 6JS;604270;233920;51.966211;0.972091;Babergh
65;Black Lion;Lion Road, Glemsford, Sudbury, Suffolk;CO10 7RF;582750;248298;52.102815;0.666893;Babergh
85;Bristol Arms;Bristol Hill, Shotley, Ipswich, Suffolk;IP9 1PU;624667;233744;51.956771;1.268376;Babergh
101;Butt and Oyster Inn;Pin Mill Road, Chelmondiston, Ipswich, Suffolk;IP9 1JW;620709;237978;51.996361;1.213605;Babergh
…

    omgezet worden naar (pubs.1.csv9)

    fas_id;name;address;postcode;latitude;longitude;local_authority
24;Anchor Inn;Upper Street, Stratford St Mary, Colchester, Essex;CO7 6LW;51.97039;0.979328;Babergh
30;Angel Inn;Egremont Street, Glemsford, Sudbury, Suffolk;CO10 7SA;52.094427;0.668408;Babergh
63;Black Boy Hotel;7 Market Hill, Sudbury, Suffolk;CO10 2EA;52.038683;0.730226;Babergh
64;Black Horse;Lower Street, Stratford St Mary, Colchester, Essex;CO7 6JS;51.966211;0.972091;Babergh
65;Black Lion;Lion Road, Glemsford, Sudbury, Suffolk;CO10 7RF;52.102815;0.666893;Babergh
85;Bristol Arms;Bristol Hill, Shotley, Ipswich, Suffolk;IP9 1PU;51.956771;1.268376;Babergh
101;Butt and Oyster Inn;Pin Mill Road, Chelmondiston, Ipswich, Suffolk;IP9 1JW;51.996361;1.213605;Babergh
…

  2. De naam van de pub (name) kan één deel bevatten dat tussen ronde haakjes staat. Als dat het geval is, verwijder dan het deel tussen ronde haakjes, samen met alle spaties die vlak voor het openende ronde haakje (() staan. Je mag ervan uitgaan dat het deel tussen ronde haakjes zelf geen ronde haakjes bevat. Zo moet

    fas_id;name;address;postcode;latitude;longitude;local_authority
24;Anchor Inn;Upper Street, Stratford St Mary, Colchester, Essex;CO7 6LW;51.97039;0.979328;Babergh
30;Angel Inn;Egremont Street, Glemsford, Sudbury, Suffolk;CO10 7SA;52.094427;0.668408;Babergh
63;Black Boy Hotel;7 Market Hill, Sudbury, Suffolk;CO10 2EA;52.038683;0.730226;Babergh
64;Black Horse;Lower Street, Stratford St Mary, Colchester, Essex;CO7 6JS;51.966211;0.972091;Babergh
…
294;Grover And Allen (J D Wetherspoon);The Grover and Allen, 67-70 North Street, Sudbury, Suffolk;CO10 1RF;52.040323;0.73088;Babergh
…
2123;Bedford Rugby (Ground, Bar & Marquee);Bedford Rugby Union F C, Goldington Road, Bedford;MK40 3NF;52.140104;-0.46053;Bedford
…
4596;Breckland Lodge (The Stag);Breckland Stag, London Road, Attleborough, Norfolk;NR17 1AY;52.496684;0.983533;Breckland
…

    omgezet worden naar (pubs.2.csv10)

    fas_id;name;address;postcode;latitude;longitude;local_authority
24;Anchor Inn;Upper Street, Stratford St Mary, Colchester, Essex;CO7 6LW;51.97039;0.979328;Babergh
30;Angel Inn;Egremont Street, Glemsford, Sudbury, Suffolk;CO10 7SA;52.094427;0.668408;Babergh
63;Black Boy Hotel;7 Market Hill, Sudbury, Suffolk;CO10 2EA;52.038683;0.730226;Babergh
64;Black Horse;Lower Street, Stratford St Mary, Colchester, Essex;CO7 6JS;51.966211;0.972091;Babergh
…
294;Grover And Allen;The Grover and Allen, 67-70 North Street, Sudbury, Suffolk;CO10 1RF;52.040323;0.73088;Babergh
…
2123;Bedford Rugby;Bedford Rugby Union F C, Goldington Road, Bedford;MK40 3NF;52.140104;-0.46053;Bedford
…
4596;Breckland Lodge;Breckland Stag, London Road, Attleborough, Norfolk;NR17 1AY;52.496684;0.983533;Breckland
…

  3. Hou enkel de pubs over waarvan de naam (name) de term Snooker bevat. We krijgen dan (pubs.3.csv11)

    fas_id;name;address;postcode;latitude;longitude;local_authority
958;Basildon Snooker Centre;5 High Pavement, Basildon, Essex;SS14 1EA;51.570643;0.457173;Basildon
1642;Q Ball Snooker and Sports Bar;Time Square, Basildon, Essex;SS14 1DJ;51.568428;0.453013;Basildon
2445;Executive Snooker Club;3a Lurke Street, Bedford;MK40 3HZ;52.137924;-0.465047;Bedford
2543;Greyfriars Snooker Centre;Greyfriars Snooker Centre, Greyfriars, Bedford;MK40 1HP;52.13647;-0.472155;Bedford
4162;Stepfield Snooker Club;2 Stepfield, Witham, Essex;CM8 3TH;51.802809;0.648042;Braintree
4534;Attleborough Snooker Centre;Attleborough Snooker Centre, A, London Road, Attleborough, Norfolk;NR17 2BX;52.514593;1.009998;Breckland
4720;Dereham Snooker Club;19 Bertie Ward Way, Dereham, Norfolk;NR19 1TE;52.664995;0.951283;Breckland
…

  4. Zorg er voor dat de coördinaat $$c$$ voor de breedtegraad (latitude) en de lengtegraad (longitude) weergegeven wordt in het formaat $$|c|$$° $$W$$. Hierbij staat $$|c|$$ voor de absolute waarde van de coördinaat $$c$$ en is $$W$$ een hoofdletter die de windrichting van coördinaat aangeeft.

    coördinaat ($$c$$) interval windrichting ($$W$$)
    breedtegraad (latitude) $$c \in \left[-90, 0\right[$$ S
    breedtegraad (latitude) $$c \in \left[0, 90\right]$$ N
    lengtegraad (longitude) $$c \in \left]-180, 0\right[$$ W
    lengtegraad (longitude) $$c \in \left[0, 180\right]$$ E

    Zo moet

    fas_id;name;address;postcode;latitude;longitude;local_authority
958;Basildon Snooker Centre;5 High Pavement, Basildon, Essex;SS14 1EA;51.570643;0.457173;Basildon
1642;Q Ball Snooker and Sports Bar;Time Square, Basildon, Essex;SS14 1DJ;51.568428;0.453013;Basildon
2445;Executive Snooker Club;3a Lurke Street, Bedford;MK40 3HZ;52.137924;-0.465047;Bedford
2543;Greyfriars Snooker Centre;Greyfriars Snooker Centre, Greyfriars, Bedford;MK40 1HP;52.13647;-0.472155;Bedford
4162;Stepfield Snooker Club;2 Stepfield, Witham, Essex;CM8 3TH;51.802809;0.648042;Braintree
4534;Attleborough Snooker Centre;Attleborough Snooker Centre, A, London Road, Attleborough, Norfolk;NR17 2BX;52.514593;1.009998;Breckland
4720;Dereham Snooker Club;19 Bertie Ward Way, Dereham, Norfolk;NR19 1TE;52.664995;0.951283;Breckland
…

    omgezet worden naar (pubs.4.csv12)

    fas_id;name;address;postcode;latitude;longitude;local_authority
958;Basildon Snooker Centre;5 High Pavement, Basildon, Essex;SS14 1EA;51.570643° N;0.457173° E;Basildon
1642;Q Ball Snooker and Sports Bar;Time Square, Basildon, Essex;SS14 1DJ;51.568428° N;0.453013° E;Basildon
2445;Executive Snooker Club;3a Lurke Street, Bedford;MK40 3HZ;52.137924° N;0.465047° W;Bedford
2543;Greyfriars Snooker Centre;Greyfriars Snooker Centre, Greyfriars, Bedford;MK40 1HP;52.13647° N;0.472155° W;Bedford
4162;Stepfield Snooker Club;2 Stepfield, Witham, Essex;CM8 3TH;51.802809° N;0.648042° E;Braintree
4534;Attleborough Snooker Centre;Attleborough Snooker Centre, A, London Road, Attleborough, Norfolk;NR17 2BX;52.514593° N;1.009998° E;Breckland
4720;Dereham Snooker Club;19 Bertie Ward Way, Dereham, Norfolk;NR19 1TE;52.664995° N;0.951283° E;Breckland
…

  5. Sorteer de pubs eerst lexicografisch volgens naam (naam) en daarna volgens lokale authoriteit (local_authority). Maak daarbij geen onderscheid tussen hoofdletters en kleine letters. Vervang het eerste veld (fas_id) door een nieuw veld (id) waarin de pubs (in hun nieuwe volgorde) oplopend genummerd worden vanaf 1. Ook de naam in de hoofding moet mee aangepast worden. We krijgen dan (pubs.5.csv13)

    id;name;address;postcode;latitude;longitude;local_authority
1;147 Snooker Club;157b Queensferry Road, Rosyth, Dunfermline, Fife;KY11 2PP;56.040196° N;3.421767° W;Fife
2;147 Snooker Club;Unit 3, A Shop Great Western Business Centr, Access Road Great Western Business, Swindon;SN1 5DE;51.56307° N;1.790569° W;Swindon
3;147 Snooker Club;Evans House, Norman Street, Warrington;WA2 7HW;53.395357° N;2.591142° W;Warrington
4;ABC Snooker and Social Club;24 Leys Avenue, Letchworth Garden City;SG6 3EW;51.979192° N;0.22641° W;North Hertfordshire
5;Academy Snooker Club;704-708 Christchurch Road, Bournemouth;BH7 6BY;50.727954° N;1.83534° W;Bournemouth
6;Accrington Pool and Snooker;39-43 Abbey Street, Accrington, Lancashire;BB5 1EN;53.753172° N;2.361739° W;Hyndburn
7;Alfreton Snooker Hall;55-57 High Street, Alfreton, Derbyshire;DE55 7DR;53.097655° N;1.389241° W;Amber Valley
8;Ambassadeur Snooker Club;North Street, Leven, Fife;KY8 4LY;56.195358° N;2.997587° W;Fife
9;Ambassador and Greenbaize Snooker Club;256 Wallisdown Road, Bournemouth;BH10 4HZ;50.746027° N;1.907221° W;Bournemouth
…