PROG0158 - Lithological map
To gain historical insight in the geological events that have shaped a particular region into what it is today, geologists must be able to determine the order in which the rocks from that region were formed. Unfortunately, it is usually only possible to determine the age relationship between types of rocks at places where they come into contact with each other. The age relationship at such contact places can be schematically represented for a specific region on a so-called lithological map. The illustration below shows an example of such a map, where areas with the same lithological type - say where the same type of rock is found - are given the same label. In this example, the lithological types are designated by the letters A to L (with the exception of the letter I). Arrows indicate contact points where the relative age of adjacent types of rocks was determined. The arrows point from older rocks to younger specimens. For the area in gray on the lithological map, it can, for example, be deduced that the lithological type L is older than the lithological types A, D and J. All age relationships between the types of rocks from a specific region can thus be listed in a lithological table. For example, the following lithological table includes all age relations from the corresponding lithological map.
| older | younger |
|---|---|
| A | E |
| A | J |
| B | G |
| C | B |
| D | A |
| D | E |
| D | F |
| D | J |
| E | J |
| F | A |
| F | E |
| F | H |
| F | J |
| H | A |
| H | E |
| H | J |
| H | K |
| J | C |
| K | J |
| L | A |
| L | D |
| L | J |
The challenge is to determine the order in which the lithological types were formed based on the information from a lithological table. Such a sequence that is consistent with the data from a lithological table is called a topological order. The determination of all possible topological orders is a complex problem that we're not going to address here. As such your assignment is to determine for a given sequence whether it is a topological order or not, taking into account a given lithological table.
Assignment
- Write a function isChronological to which three arguments should be passed. The first two arguments are lithological types that are represented by a single letter. The third argument is a string that represents a given sequence of lithological types. In this string letters that correspond with older types are before letters that correspond with younger types. The function should return the value True if the first lithological type is older than the second type, or if the two types are the same, otherwise the False value should be returned. Make sure that the function also returns the value False if the character that corresponds to one of the given lithological types is not in the third argument.
- Use the isChronological function to write a function isTopologicalOrder, to which two arguments should be passed. The first argument is a string that represents a given sequence, and which should be interpreted in the same way as the argument described in the isChronological function. The second argument is the location of a text file that contains a topological table. The first row of the file is reserved for column headings; the following rows each contain two letters separated by a tab. As shown in the above example, the first column represents the older lithological type and the second column the younger type. The function should return the value True if the given sequence is a topological order, which means it is consistent with all pairwise age relationships of rocks as defined by the rows of the specified file. Otherwise, the value False must be returned.
Example
In the following example the file topologicalorder1.txt will be used.
>>> isChronological('A', 'B', 'ACEGHLDBFJK') True >>> isChronological('B', 'A', 'ACEGHLDBFJK') False >>> isTopologicalOrder('KLGHABECFJD', 'topologicalorder1.txt') False >>> isTopologicalOrder('LDFHAEKJCBG', 'topologicalorder1.txt') True
Om historisch inzicht te krijgen in de geologische gebeurtenissen die een bepaalde regio gevormd hebben tot wat ze nu is, moeten geologen kunnen achterhalen in welke volgorde de gesteenten uit die regio gevormd werden. Helaas is het meestal enkel mogelijk om de leeftijdsrelatie tussen soorten gesteenten te bepalen op plaatsen waar ze met elkaar in contact komen. De leeftijdsrelatie op dergelijke contactpunten kan voor een bepaalde regio schematisch voorgesteld worden op een zogenaamde lithologische kaart. Onderstaande afbeelding toont een voorbeeld van een dergelijke kaart, waarbij gebieden met eenzelfde lythogisch type — zeg maar waarin hetzelfde soort gesteente aangetroffen wordt — eenzelfde label krijgen. In dit voorbeeld zijn de lythologische types aangeduid met de letters A tot en met L (uitgezonderd de letter I). Pijlen duiden op contactpunten waar de relatieve leeftijd van aangrenzende soorten gesteenten bepaald werd. De pijlen wijzen van oudere naar jongere soorten gesteenten. Voor het gebied dat in het grijs werd aangeduid op de lithologische kaart, kan bijvoorbeeld afgeleid worden dat het lithologisch type L ouder is dan de lithologische types A, D en J. Alle leeftijdsrelaties tussen de soorten gesteenten uit een bepaalde regio kunnen op die manier in een lithologische tabel opgelijst worden. Zo bevat onderstaande lithologische tabel alle leeftijdsrelaties uit de corresponderende lithologische kaart.
| ouder | jonger |
|---|---|
| A | E |
| A | J |
| B | G |
| C | B |
| D | A |
| D | E |
| D | F |
| D | J |
| E | J |
| F | A |
| F | E |
| F | H |
| F | J |
| H | A |
| H | E |
| H | J |
| H | K |
| J | C |
| K | J |
| L | A |
| L | D |
| L | J |
De uitdaging bestaat er in om op basis van de informatie uit een lithologische tabel te bepalen in welke volgorde de lithologische types gevormd werden. Een dergelijke volgorde die consistent is met de gegevens uit een lithologische tabel wordt een topologische orde genoemd. Het bepalen van alle mogelijke topologische ordes is een complex probleem dat we hier niet als dusdanig gaan aanpakken. Je opdracht bestaat er in om voor een gegeven volgorde te bepalen of het een topologische orde is of niet, rekening houdend met een gegeven lithologische tabel.
Opgave
- Schrijf een functie isChronologisch waaraan drie argumenten moeten doorgegeven worden. De eerste twee argumenten zijn lithologische types die worden voorgesteld door één enkele letter. Het derde argument is een string die een gegeven volgorde van lithologische types voorstelt. In deze string staan letters die corresponderen met oudere types voor letters die corresponderen met jongere types. De functie moet de waarde True teruggeven indien het eerste lithologisch type ouder is dan het tweede type of als de twee types hetzelfde zijn, anders moet de waarde False teruggegeven worden. Zorg er voor dat de functie ook de waarde False teruggeeft indien het letterteken dat correspondeert met één van de gegeven lithologische types niet in het derde argument voorkomt.
- Gebruik de functie isChronologisch om een functie isTopologischeOrde te schrijven, waaraan twee argumenten moeten doorgegeven worden. Het eerste argument is een string die een gegeven volgorde voorstelt, en die op dezelfde manier moet geïnterpreteerd worden als het argument omschreven bij de functie isChronologisch. Het tweede argument is de locatie van een tekstbestand waarin een topologische tabel is opgenomen. De eerste rij van dit bestand is voorbehouden voor kolomkoppen; de volgende rijen bevatten telkens twee letters, gescheiden door een tab. Zoals in het voorbeeld hierboven staat de eerste kolom voor het oudere lithologische type en de tweede kolom voor het jongere type. De functie moet de waarde True terug geven indien de gegeven volgorde een topologische orde is, die dus consistent is met alle paarsgewijze leeftijdsrelaties van gesteenten zoals omschreven in de rijen van het opgegeven bestand. Anders moet de waarde False teruggegeven worden.
Voorbeeld
In volgend voorbeeld wordt het bestand topologischeorde1.txt gebruikt.
>>> isChronologisch('A', 'B', 'ACEGHLDBFJK') True >>> isChronologisch('B', 'A', 'ACEGHLDBFJK') False >>> isTopologischeOrde('KLGHABECFJD', 'topologischeorde1.txt') False >>> isTopologischeOrde('LDFHAEKJCBG', 'topologischeorde1.txt') True
| Added by: | Peter Dawyndt |
| Date: | 2011-08-29 |
| Time limit: | 5s |
| Source limit: | 50000B |
| Memory limit: | 1536MB |
| Cluster: | Cube (Intel G860) |
| Languages: | PY_NBC |
| Resource: | None |
RSS