Dit is een bekend raadsel dat doorgaans op de volgende manier wordt omschreven:
We hebben 12 muntstukken een uniek label gegeven, maar voor rest zien ze er exact hetzelfde uit. Alle muntstukken hebben hetzelfde gewicht, behalve één dat lichter of zwaarder is dan de rest. Dat noemen we het vervalste muntstuk, maar uiteraard zeggen we niet over welk muntstuk het gaat.
Je krijgt een weegschaal die je mag gebruiken om het gewicht te vergelijken van een gelijk aantal muntstukken (tot maximaal de helft van het totaal aantal muntstukken) die aan de linker- en rechterkant van de weegschaal gelegd worden. De weegschaal is voldoende nauwkeurig om het onevenwicht te bepalen dat optreedt als het vervalste muntstuk bij de gewogen muntstukken zit.
Je opdracht bestaat erin om het vervalste muntstuk te vinden, en ook om te bepalen of het lichter of zwaarder is dan de rest van de muntstukken, door maximaal drie wegingen uit te voeren.
Er kan echter algemeen aangetoond worden dat $$n \in \mathbb{N}_0$$ wegingen volstaan om een vervalst muntstuk te identificeren uit een reeks van maximaal $$\frac{3^n - 3}{2}$$ muntstukken.
De uitkomsten van een reeks van $$n$$ wegingen kunnen voorgesteld worden als een string (str) van $$n$$ cijfers: 0, 1 of 2. Daarbij stellen de opeenvolgende cijfers (van links naar rechts) de uitkomsten van de opeenvolgende wegingen voor, waarbij de cijfers de volgende betekenis hebben:
0: weegschaal is in evenwicht (vervalste muntstuk zit niet bij de gewogen muntstukken)
1: linkerkant van de weegschaal weegt zwaarder
2: rechterkant van de weegschaal weegt zwaarder
We noemen zo'n string een weegpatroon, of kortweg een patroon. Omdat het vervalste muntstuk niet noodzakelijk bij de gewogen muntstukken van de eerste weging zit, hebben voorloopnullen wel degelijk betekenis en mogen dus niet weggelaten worden.
Een weegplan geeft aan welke $$n$$ wegingen we moeten uitvoeren om het vervalste muntstuk te vinden uit een reeks van $$m$$ muntstukken (met $$m \leq \frac{3^n - 3}{2}$$). Dit gebeurt door aan elk muntstuk een uniek patroon van $$n$$ wegingen toe te kennen (hoe is voor deze opgave niet belangrijk). Als we elk van de 12 muntstukken uit het originele raadsel labelen met een unieke letter, dan ziet een weegplan voor 12 muntstukken er bijvoorbeeld als volgt uit:
| label | patroon |
|---|---|
| A | 112 |
| B | 120 |
| C | 121 |
| D | 122 |
| E | 220 |
| F | 201 |
| G | 202 |
| H | 200 |
| I | 001 |
| J | 012 |
| K | 010 |
| L | 011 |
Voor de $$i$$-de weging ($$i = 0, 1, \ldots, n - 1$$) geeft het $$i$$-de cijfer van elk patroon (geteld vanaf links) als volgt aan hoe het muntstuk deelneemt in de weging:
0: muntstuk wordt niet op de weegschaal geplaatst (neemt niet deel aan de weging)
1: muntstuk wordt aan linkerkant van de weegschaal geplaatst
2: muntstuk wordt aan rechterkant van de weegschaal geplaatst
Hierbij geldt dat er altijd evenveel muntstukken aan beide kanten van de weegschaal liggen, en dat elk muntstuk minstens één keer gewogen wordt (met andere woorden, het patroon 00…0 komt niet in het weegplan voor). Het weegplan voor 12 muntstukken geeft bijvoorbeeld aan dat de volgende wegingen moeten uitgevoerd worden:
| weging | linkerkant (1) | rechterkant (2) |
|---|---|---|
| 0 | A, B, C, D | E, F, G, H |
| 1 | A, J, K, L | B, C, D, E |
| 2 | C, F, I, L | A, D, G, J |
Om het vervalste muntstuk te vinden, moet je de uitkomsten van de opeenvolgende wegingen oplijsten in de vorm van een "patroon": het eerste cijfer correspondeert met de uitkomst van de eerste weging, het tweede cijfer met de uitkomst van de tweede weging, enzoverder. Daarbij hebben de cijfers de volgende betekenis:
0: weegschaal is in evenwicht (vervalste muntstuk zit niet bij de gewogen muntstukken)
1: linkerkant van de weegschaal weegt zwaarder
2: rechterkant van de weegschaal weegt zwaarder
Nu zijn er twee mogelijkheden:
het bekomen patroon komt in het weegplan overeen met één muntstuk: dat is het vervalste muntstuk dat zwaarder is dan de rest van de muntstukken
het omgekeerde van het bekomen patroon komt in het weegplan overeen met één muntstuk: dat is het vervalste muntstuk dat lichter is dan de rest van de muntstukken
Hierbij is het omgekeerde van een patroon $$p$$ gedefinieerd als het patroon dat men bekomt door in $$p$$ elk voorkomen van het cijfer 2 te vervangen door het cijfer 1, en elk voorkomen van het cijfer 1 te vervangen door het cijfer 2.
Gevraagd wordt:
Schrijf een functie omgekeerd waaraan een patroon (str) moet doorgegeven worden. De functie moet het omgekeerde (str) van het gegeven patroon teruggeven.
Schrijf een functie weegschaal waaraan drie argumenten moeten doorgegeven worden: i) een collectie (list, tuple of set) met labels (str) van de muntstukken die aan de linkerkant van de weegschaal gelegd worden, ii) een collectie (list, tuple of set) met labels (str) van de muntstukken die aan de rechterkant van de weegschaal gelegd worden, en iii) het label (str) van het vervalste muntstuk. Daarbij mag de functie ervan uitgaan dat de twee collecties evenveel labels bevatten, en dat elk label in hoogstens één collectie voorkomt. De functie heeft ook nog een optionele parameter zwaarder waaraan een Booleaanse waarde (bool) kan doorgegeven worden die aangeeft of het vervalste muntstuk lichter (False) of zwaarder (True) is dan de rest van de muntstukken (standaardwaarde: False). De functie moet het cijfer (int; 0, 1 of 2) teruggeven dat de toestand van de weegschaal beschrijft bij de weging van de twee collecties muntstukken.
Schrijf een functie labels waaraan de locatie (str) van een tekstbestand moet doorgegeven worden. Het bestand moet de omschrijving van een weegplan bevatten. Daarbij bestaat elke regel uit het unieke label van een muntstuk, gevolgd door een komma (,) en het patroon dat in het weegplan aan het muntstuk toegekend wordt. De functie moet een dictionary (dict) teruggeven waarvan de sleutels gevormd worden door de patronen (str) in het gegeven bestand. De dictionary moet elk patroon afbeelden op het label (str) van het corresponderende muntstuk.
Schrijf een functie weegplan waaraan een dictionary (dict) moet doorgegeven worden, zoals die wordt teruggegeven door de functie labels. De functie moet een lijst (list) teruggeven met de opeenvolgende wegingen ($$i = 0, 1, \ldots, n - 1$$) die volgens het gegeven weegplan moeten uitgevoerd worden. Hierbij wordt elke weging voorgesteld als een tuple met twee elementen: i) de verzameling (set) met de labels (str) van alle muntstukken die bij de $$i$$-de weging aan de linkerkant van de weegschaal gelegd worden en ii) de verzameling (set) met de labels (str) van alle muntstukken die bij de $$i$$-de weging aan de rechterkant van de weegschaal gelegd worden.
Schrijf een functie weegpatroon waaraan twee argumenten moeten doorgegeven worden: i) een dictionary (dict) met een weegplan zoals die wordt teruggegeven door de functie labels en ii) het label (str) van het vervalste muntstuk. De functie heeft ook nog een optionele parameter zwaarder waaraan een Booleaanse waarde (bool) kan doorgegeven worden die aangeeft of het vervalste muntstuk lichter (False) of zwaarder (True) is dan de rest van de muntstukken (standaardwaarde: False). De functie moet de string (str) teruggeven die de uitkomsten van de opeenvolgende wegingen oplijst in de vorm van een "patroon", als het gegeven weegplan gevolgd wordt met het gegeven vervalste muntstuk.
Schrijf een functie vervalsing waaraan twee argumenten moeten doorgegeven worden: i) een dictionary (dict) met een weegplan zoals die wordt teruggegeven door de functie labels en ii) een string (str) die de uitkomsten van de opeenvolgende wegingen oplijst in de vorm van een "patroon", als het gegeven weegplan gevolgd wordt. De functie moet een tuple met twee elementen teruggegeven: i) het label (str) van het vervalste muntstuk en ii) een Booleaanse waarde (bool) die aangeeft of het vervalste muntstuk lichter (False) of zwaarder (True) is dan de rest van de muntstukken.
In onderstaande voorbeeldsessie gaan we ervan uit dat het tekstbestand plan.txt1 zich in de huidige directory bevindt.
>>> omgekeerd('102')
'201'
>>> omgekeerd('200')
'100'
>>> weegschaal({'A', 'B', 'C', 'D'}, {'E', 'F', 'G', 'H'}, 'F')
1
>>> weegschaal({'A', 'B', 'C', 'D'}, {'E', 'F', 'G', 'H'}, 'F', True)
2
>>> weegschaal({'A', 'J', 'K', 'L'}, {'B', 'C', 'D', 'E'}, 'F')
0
>>> weegschaal({'A', 'J', 'K', 'L'}, {'B', 'C', 'D', 'E'}, 'F', True)
0
>>> weegschaal({'C', 'F', 'I', 'L'}, {'A', 'D', 'G', 'J'}, 'F')
2
>>> weegschaal({'C', 'F', 'I', 'L'}, {'A', 'D', 'G', 'J'}, 'F', zwaarder=True)
1
>>> plan = labels('plan.txt2')
>>> plan['121']
'C'
>>> plan['202']
'G'
>>> plan['011']
'L'
>>> weging = weegplan(plan)
>>> weging[0]
({'A', 'B', 'C', 'D'}, {'E', 'F', 'G', 'H'})
>>> weging[1]
({'A', 'J', 'K', 'L'}, {'B', 'C', 'D', 'E'})
>>> weging[2]
({'C', 'F', 'I', 'L'}, {'A', 'D', 'G', 'J'})
>>> weegpatroon(plan, 'F')
'102'
>>> weegpatroon(plan, 'F', True)
'201'
>>> weegpatroon(plan, 'H', zwaarder=False)
'100'
>>> weegpatroon(plan, 'H', zwaarder=True)
'200'
>>> vervalsing(plan, '102')
('F', False)
>>> vervalsing(plan, '200')
('H', True)