PROG0238 - Settlers of Catan
In the game Settlers of Catan two dice are thrown at every turn to determine which areas of the island (represented by hexagonal tiles) will yield raw materials. In every area, a number is written. That number lays between 2 and 12 (boundaries included), but that differs from 7. Only the areas of which the number is equal to the sum of the dots of the dice thrown, will yield raw materials. There are five raw materials: wood, wool, grain, ore and stone. If the sum thrown equals 7, the area won't yield raw materials.
Given is a sequence of land tiles (areas) of the isle Catan (each with their own number and raw material) that form the board of a game of Settlers of Catan. Your assignment is to determine the most scarce raw material on this board, this is the material that will be yielded the least. For example: a board that contains three tiles with the material grass that are labeled with the numbers, 2, 8 and 8 will statistically yield more grass than a board with only two tiles of grass that are labeled with the numbers 2 and 8. If two or more materials have the smallest chance to be yielded, choose the material with the least amount of tiles on the board. In this last case, we guarantee that a unique kind of material occurs less than the rest.
Background calculation of probability: The chance you throw 2 with two dice is 1/36 (this is only possible if both dots are 1, with a chance 1/6 + 1/6). The chance you throw a 3 is 2/36 (1 + 2 or 2 + 1, each with a chance of 1/6 + 1/6, for a total of 2/36), and so on. The chance you throw a 12 is equal to the chance you throw a 2.
Assignment
Write a function leastChance that determines for a given game board of the Settlers of Catan which raw material has the least chance of yielding something. To this function a string must be given that describes the tiles of a game board. Every tile is described by a letter that describes the raw material on the tile (for example H for wood, W for wool, G for grain, E for ore and S for stone), folowed by an integer between 2 and 12 (boundaries included). The different descriptions of the tiles on the game board are always separated by a single space. In contrast with the real game, the board in this assignment can consist of an arbitrary amount of tiles (at least 1) and more than 2 tiles can contain the same number or the same material. Moreover, more or less letters for materials may occur in contrast with the original game. The function must print the letter of the raw material that has the smallest chance to yield anything. If multiple materials have a minimal chance, the function should print the material with the least amount of tiles.
Voorbeeld
>>> leastChance('W2 H12 W4 E5 S4 G2 H5 W8') 'G' >>> leastChance('S4 E6 W8 H9 G12 E3 W4 S2 G5 H5') 'S' >>> leastChance('E2 H6') 'E' >>> leastChance('W4 H4 W4') 'H'
Bij het spel Kolonisten van Catan worden elke beurt twee dobbelstenen geworpen om te bepalen welke gebieden van het eiland (voorgesteld door zeshoekige tegels) grondstoffen zullen opleveren. In elk gebied staat een getal geschreven. Dat getal ligt tussen 2 en 12 (grenzen inbegrepen) maar is verschillend van 7. Alleen gebieden waarvan het ingeschreven getal gelijk is aan de som van de ogen van de geworpen dobbelstenen, leveren die beurt grondstoffen op. Er zijn 5 grondstoffen: hout, wol, graan, erts en steen. Een geworpen som van 7 ogen levert geen grondstoffen op.
Gegeven is een reeks landtegels (gebieden) van het eiland Catan (elk met hun eigen getal en grondstoffensoort) die samen het bord van een spel Kolonisten van Catan vormen. Je opdracht bestaat erin om de meest schaarse grondstof te bepalen op dit bord, zijnde de grondstof die statistisch gezien het minst zal opgeleverd worden. Een voorbeeld: een bord dat drie tegels met de grondstof gras bevat die gelabeld zijn met de getallen 2, 8 en 8 zal statistisch gezien meer gras opleveren dan een bord met slechts twee tegels met gras die gelabeld zijn met de getallen 2 en 8. Indien twee of meer grondstoffen allebei het minst kans hebben om opgeleverd te worden, verkies dan van die grondstoffen de grondstof met het minste tegels op het bord. In dit laatste geval garanderen we dat er een unieke grondstoffensoort is die minder voorkomt dan de rest.
Achtergrond kansrekenen: De kans dat je met twee dobbelstenen een 2 werpt is 1/36 (dit kan alleen als beide ogen 1 zijn, met kans 1/6 + 1/6). De kans dat je een 3 werpt is 2/36 (1 + 2 of 2 + 1, elk met een kans van 1/6 + 1/6, voor een totaal van 2/36), enzovoort. De kans dat je een 12 werpt is gelijk aan de kans dat je een 2 werpt.
Opgave
Schrijf een functie minsteKans die voor een gegeven spelbord van de Kolonisten van Catan bepaalt welke grondstof het minste kans heeft om iets op te leveren. Aan deze functie moet een string doorgegeven worden die de tegels van het spelbord omschrijft. Elke tegel wordt omschreven door een letter die de grondstof op de tegel omschrijft (bijvoorbeeld H voor hout, W voor wol, G voor graan, E voor erts en S voor steen), gevolgd door een natuurlijk getal tussen 2 en 12 (grenzen ingrepen). De verschillende omschrijvingen van de tegels van het spelbord worden telkens van elkaar gescheiden door één enkele spatie. In tegenstelling tot het echte spel, kan in deze opgave een bord bestaan uit een willekeurig aantal tegels (minstens 1) en kunnen er meer dan 2 tegels zijn met hetzelfde getal of dezelfde grondstof. Er kunnen ook meer of minder letters voor grondstoffen voorkomen ten opzichte van het originele spel. De functie moet de letter van de grondstof teruggeven die het minste kans maakt om iets op te leveren. Indien er meerdere grondstoffen zijn met een minimale kans, dan moet de functie die grondstof teruggeven waarvoor het aantal tegels minimaal is.
Voorbeeld
>>> minsteKans('W2 H12 W4 E5 S4 G2 H5 W8') 'G' >>> minsteKans('S4 E6 W8 H9 G12 E3 W4 S2 G5 H5') 'S' >>> minsteKans('E2 H6') 'E' >>> minsteKans('W4 H4 W4') 'H'
| Added by: | Peter Dawyndt |
| Date: | 2012-03-30 |
| Time limit: | 10s |
| Source limit: | 50000B |
| Memory limit: | 1536MB |
| Cluster: | Cube (Intel G860) |
| Languages: | PY_NBC |
| Resource: | None |
RSS