| Submit | All submissions | Best solutions | Back to list |
PROG0531 - Close neighbours |
Located in Texas' northwest corner, the town of Dalhart is closer to six other state capitals than to Texas' own capital Austin. As the crow flies, Dalhart is 306 kilometers from Santa Fe, 432 kilometers from Denver, 464 kilometers from Oklahoma City, 606 kilometers from Cheyenne, 684 kilometers from Topeka and 738 kilometers from Lincoln, but it is 786 kilometers from Austin.
Assignment
The United States consists of fifty states that have a certain operational autonomy from the US federal government. Each state has its own state capital. In order to avoid confusion due to the fact that some US cities share the same name, place names are usually given in association with the state in which they are located. In this exercise, we will indicate cities always with the name of the city, followed by a comma and the two-letter abbreviation of the state in which the city is located (for example: Austin,TX).
Since some state have more than one occurrence of the same place name, it is even less ambiguous to indicate places with their location. In this exercise, we represent the coordinate where a city is located as a tuple $(b, l)$ ($b, l \in \mathbb{R}, -90 < b \leq 90, -180 < l \leq 180$), where $b$ indicates the latitude and $l$ the longitude, both expressed in decimal degrees.
For a given city, we are looking for the all state capitals of US states that are closer to the city than the state capital of its own state. In order to do so, we proceed as follows:
- Write a function capitals that takes the location of a text file as its argument. This file must contain the list of all capitals, with the name of each city on a separate line, followed by a comma and the two-letter abbreviation of the state in which the city is located. The function must return a dictionary, that maps the two-letter abbreviation of each state onto the name of its state capital.
- Write a function coordinates that takes the location of a text file as its argument. This file must contain a list of cities, with line containing the following information fields on a single city, separated from each other using comma's: i) name, ii) two-letter abbreviation of the state, iii) latitude, en iv) longitude. The function must return a dictionary that maps each city onto its coordinate $(b, l)$.
- Write a function greatCircleDistance
that takes two coordinates $(b_1, l_1)$ en $(b_2, l_2)$ as its
arguments. The function must return the great-circle distance between
the two given coordinates. It represents the distance between two points
on a sphere, and is computed according to the following formula $$d = r
\cdot \arccos(\sin(b_1) \cdot \sin(b_2) + \cos(b_1)\cdot \cos(b_2) \cdot
\cos(l_1 - l_2))$$ Here, $r$ represents the radius of the sphere. The
function must consider Earth as a sphere with radius $r = 6371\mbox{
km}$, which expresses the distance in kilometer.
Note: All trigonometric functions in the math module take angles expressed in radians. Since the original latitudes and longitudes are expresses in decimal degrees, they must be converted into radians. The math module contains a function that computes this conversion. - Use the function greatCircleDistance to write a function closeNeighbours that takes three arguments: i) a city, ii) a dictionary mapping the two-letter abbreviation of each state onto the name of its state capital, and iii) a dictionary that maps each city onto its coordinate $(b, l)$. The function must return a set containing all state capitals that are closer to the given city than its own state capital.
Example
In the following interactive session, we assume that the text files capitals.txt and cities.txt are located in the current directory.
>>> capital = capitals('capitals.txt') >>> capital['TX'] 'Austin' >>> capital['NE'] 'Lincoln' >>> coordinate = coordinates('cities.txt') >>> coordinate['Dalhart,TX'] (36.1173, -102.6024) >>> coordinate['Austin,TX'] (30.352, -97.7151) >>> coordinate['Lincoln,NE'] (40.908, -96.7103) >>> greatCircleDistance((36.1173, -102.6024), (30.352, -97.7151)) # Dalhart,TX <-> Austin,TX 785.5925593169209 >>> greatCircleDistance((36.1173, -102.6024), (40.908, -96.7103)) # Dalhart,TX <-> Lincoln,NE 738.9516485722722 >>> capital = capitals('capitals.txt') >>> coordinate = coordinates('cities.txt') >>> closeNeighbours('Dalhart,TX', capital, coordinate) {'Cheyenne,WY', 'Oklahoma City,OK', 'Topeka,KS', 'Santa Fe,NM', 'Lincoln,NE', 'Denver,CO'}
Epilogue
The small town Green River in the state Wyoming is certainly neighborly: when NASA determined in 1994 that up to six meteors might strike Jupiter, Green River’s city council designated an airstrip south of town as the Greater Green River Intergalactic Spaceport. They asked NASA to broadcast the news to any fleeing Jovians and warned residents to "prepare themselves to make welcome any refugees who might cast themselves upon our mercy."
Mayor George Eckman told the Rock Springs Rocket-Miner, "I feel it is a gesture that could be made and should be made by someone on the planet Earth to fellow citizens of the solar system." The two council members who opposed the resolution pointed out that the region already has a problem with illegal aliens and noted the local housing shortage. But the mile-long runway remains open.
Gelegen in het noordwesten van de Amerikaanse staat Texas ligt het stadje Dalhart. Austin, de hoofdstad van de staat Texas, is verder van dit stadje verwijderd dan de hoofdsteden van zes andere Amerikaanse staten. In vogelvlucht ligt Dalhart 306 kilometer van Santa Fe, 432 kilometer van Denver, 464 kilometer van Oklahoma City, 606 kilometer van Cheyenne, 684 kilometer van Topeka en 738 kilometer van Lincoln, terwijl het 786 kilometer verwijderd is van Austin.
Opgave
De Verenigde Staten bestaan uit vijftig staten die in een zekere mate van onafhankelijkheid van de Amerikaanse federale overheid kunnen opereren. Elke staat heeft een eigen hoofdstad. Om verwarring te voorkomen door het feit dat verschillende Amerikaanse steden dezelfde naam hebben, worden plaatsnamen doorgaans aangeduid samen met de staat waarin ze liggen. In deze opgave zullen we steden steeds aanduiden met de naam van de stad, gevolgd door een komma en de twee-letter afkorting van de staat waarin de stad ligt (bijvoorbeeld Austin,TX).
Aangezien er zelfs dubbele plaatsnamen voorkomen binnen dezelfde staat, is het nog eenduidiger om plaatsen aan te duiden met hun ligging. In deze opgave stellen we de coördinaat van een stad voor als een tuple $(b, l)$ ($b, l \in \mathbb{R}, -90 < b \leq 90, -180 < l \leq 180$), waarbij $b$ de breedtegraad en $l$ de lengtegraad aangeeft (beide uitgedrukt in decimale graden).
Voor een gegeven stad gaan we op zoek naar
alle hoofdsteden van Amerikaanse staten die dichter bij de stad liggen dan
de hoofstad van zijn eigen staat. Hiervoor gaan we als volgt te werk:
- Schrijf een functie hoofdsteden waaraan de locatie van een tekstbestand moet doorgegeven worden. Dit bestand moet een lijst van hoofdsteden bevatten, met voor elke hoofdstad op een afzonderlijke regel de naam van de hoofdstad, gevolgd door een komma en de twee-letter afkorting van de staat waarin de stad ligt. De functie moet een dictionary teruggeven, die de twee-letter afkorting van elke staat afbeeldt op de naam van haar hoofdstad.
- Schrijf een functie coordinaten waaraan de locatie van een tekstbestand moet doorgegeven worden. Dit bestand moet een lijst van steden bevatten, met voor elke stad op een afzonderlijke regel de volgende informatievelden van elkaar gescheiden door een komma: i) naam, ii) twee-letter afkorting van de staat, iii) breedtegraad, en iv) lengtegraad. De functie moet een dictionary teruggeven, die elke stad afbeeldt op zijn coördinaat $(b, l)$.
- Schrijf een functie grootcirkelafstand
waaraan twee coördinaten $(b_1, l_1)$ en $(b_2, l_2)$ moeten
doorgegeven worden. De functie moet de grootcirkelafstand tussen de twee
coördinaten teruggeven. Deze stelt de afstand tussen twee punten op
een bol voor, en kan berekend worden aan de hand van de volgende formule
$$d = r \cdot \arccos(\sin(b_1) \cdot \sin(b_2) + \cos(b_1)\cdot
\cos(b_2) \cdot \cos(l_1 - l_2))$$ Hierbij stelt $r$ de straal van de
bol voor. De functie moet aannemen dat de Aarde bolvormig is met straal
$r = 6371\mbox{ km}$, waardoor de afstand uitgedrukt wordt in kilometer.
Opmerking: Alle goniometrische functies in de math module werken met hoeken die uitgedrukt zijn in radialen. De lengte- en breedtegraden moeten dus omgezet worden naar radialen, maar daarvoor bestaat ook een functie in de math module. - Gebruik de functie grootcirkelafstand om een functie dichteBuren te schrijven waaraan drie argumenten moeten doorgegeven worden: i) een stad, ii) een dictionary die de twee-letter afkorting van elke staat afbeeldt op de naam van haar hoofdstad, en iii) een dictionary die elke stad afbeeldt op zijn coördinaat $(b, l)$. De functie moet een verzameling teruggeven met alle hoofdsteden die dichter bij de gegeven stad liggen dan de hoofstad van zijn eigen staat. Voor de berekening van de afstand tussen steden moet gebruik gemaakt worden van de grootcirkelafstand.
Voorbeeld
Bij onderstaande voorbeeldsessie gaan we ervan uit dat de tekstbestanden hoofdsteden.txt en steden.txt zich in de huidige directory bevinden.
>>> hoofdstad = hoofdsteden('hoofdsteden.txt') >>> hoofdstad['TX'] 'Austin' >>> hoofdstad['NE'] 'Lincoln' >>> coordinaat = coordinaten('steden.txt') >>> coordinaat['Dalhart,TX'] (36.1173, -102.6024) >>> coordinaat['Austin,TX'] (30.352, -97.7151) >>> coordinaat['Lincoln,NE'] (40.908, -96.7103) >>> grootcirkelafstand((36.1173, -102.6024), (30.352, -97.7151)) # Dalhart,TX <-> Austin,TX 785.5925593169209 >>> grootcirkelafstand((36.1173, -102.6024), (40.908, -96.7103)) # Dalhart,TX <-> Lincoln,NE 738.9516485722722 >>> hoofdstad = hoofdsteden('hoofdsteden.txt') >>> coordinaat = coordinaten('steden.txt') >>> dichteBuren('Dalhart,TX', hoofdstad, coordinaat) {'Cheyenne,WY', 'Oklahoma City,OK', 'Topeka,KS', 'Santa Fe,NM', 'Lincoln,NE', 'Denver,CO'}
Epiloog
Het stadje Green River in de staat Wyoming is zeker een goede buur gebleken. Toen NASA in 1994 ontdekte dat Jupiter bedreigd werd door een mogelijk inslag van zes meteoren, besliste de gemeenteraad van Green River om de landingsbaan ten zuiden van de stad beschikbaar te stellen en doopte die meteen ook om tot Greater Green River Intergalactic Spaceport. Ze vroegen NASA om dit nieuws uit te sturen naar alle Jovianen op de vlucht en drongen er bij hun inwoners op aan om "zich voor te bereiden om mogelijke vluchtelingen te verwelkomen die een beroep zouden willen doen op onze barmhartigheid".
Burgemeester George Eckman vertelde aan de krant de Rock Springs Rocket-Miner "Ik zie het als een gebaar dat kon gemaakt worden en moest gemaakt worden door iemand op planeet Aarde aan de medeburgers van ons zonnestelsel". De twee gemeenteraadsleden die zich tegen de resolutie verzet hadden, argumenteerden dat de regio reeds voldoende problemen had met illegale vreemdelingen en wezen ook op de lokale woningnood. Tot op vandaag heeft geen enkel ruimteschip gebruik gemaakt van de luchthaven, maar het aanbod blijft wel gelden.
| Added by: | Peter Dawyndt |
| Date: | 2015-01-16 |
| Time limit: | 10s |
| Source limit: | 50000B |
| Memory limit: | 1536MB |
| Cluster: | Cube (Intel G860) |
| Languages: | PY_NBC |
| Resource: | None |
RSS