De Inca en andere Zuid-Amerikaanse volkeren in de Andesregio maakten gebruik van quipus1 (ook khipus of sprekende knopen genoemd): een registratiesysteem dat bestaat uit een reeks geknoopte touwen. Het woord khipu stamt uit het Cusco-Calloa Quecha-dialect2 (Peru) en betekent knoop of het werkwoord knopen. Een quipu bestaat doorgaans uit gekleurde, gesponnen en gevlochten touwen van katoen of camelidevezel3. Quipus werden gebruikt voor het verzamelen en archiveren van gegevens zoals openstaande belastingen, bevolkingsaantallen, agenda's en militaire structuren. Er zijn maar een beperkt aantal quipus bewaard. Sommige daarvan bestaan slechts uit een handvol touwen, maar er werden ook zeer complexe quipus gevonden die wel 2000 touwen bevatten.
Quipus hebben zeker nog niet al hun geheimen prijsgegeven, maar ondertussen staat wel al vast dat de geregistreerde informatie meestal bestaat uit getallen in het decimaal talstelsel. Na analyse van honderden quipus slaagden Marcia en Robert Ascher erin om de code te ontcijferen die toelaat om de getallen te lezen.
Een touw kan één of meer getallen registreren. Deze getallen worden voorgesteld als een opeenvolging van knopenclusters die moeten gelezen worden vanaf het hoofdtouw: het touw waaraan de andere touwen bevestigd zijn (bovenaan onderstaande figuur). Een cluster van knopen stelt één enkel cijfer voor, waarbij gebruikgemaakt wordt van drie soorten knopen: eenvoudige overhandse knopen4, achtknopen5 en lange knopen (overhandse knopen met één of meer bijkomende omwentelingen).
Opgave
Bij hun analyse van quipus introduceerden de Aschers een eenvoudige notatie voor een cluster van knopen. Ze ontdekten immers dat een natuurlijk getal $$c_{n}c_{n - 1}c_{n - 2}\ldots c_{2}c_{1}c_{0}$$ — waarbij $$c_i (i = 0, 1, \ldots, n)$$ de cijfers $$0, 1, \ldots, 9$$ van een decimaal getal voorstellen — op de volgende manier in knopen vastgelegd wordt. Voor alle cijfers behalve het laatste wordt een nul voorgesteld door een positie zonder knopen (genoteerd als X) en alle andere cijfers door een cluster van $$c_i$$ overhandse knopen (genoteerd als $$c_i$$s). Voor het laatste cijfer wordt een nul voorgesteld door een achtknoop met een extra omwenteling (genoteerd als EE), een één door een gewone achtknoop (genoteerd als E) en alle andere cijfers door een lange knoop met $$c_i$$ omwentelingen (genoteerd als $$c_i$$L). De notaties van de opeenvolgende knopenclusters worden telkens van elkaar gescheiden door een spatie.
Omdat het cijfer van de eenheden (het laatste cijfer van een natuurlijk getal) wordt voorgesteld door karakteristieke knopen, is het meteen ook duidelijk waar een getal eindigt. Daardoor kunnen er op één touw meerdere getallen na elkaar geregistreerd worden. Dit wordt samengevat in onderstaand diagram.
Als bijvoorbeeld 3s staat voor een cluster van drie overhandse knopen, 7L voor een lange knoop met zeven omwentelingen, E voor een achtknoop en X voor een positie zonder knopen, dan
-
wordt het getal 327 genoteerd als 3s 2s 7L
-
wordt het getal 2461 genoteerd als 2s 4s 6s E
-
wordt het getal 107 gevolgd door het getal 51 genoteerd als 1s X 7L 5s E
Deze interpretatie van de knopen wordt bevestigd door een gelukkig toeval: er is immers een systematische manier waarop sommen worden voorgesteld in quipus. Een touw kan bijvoorbeeld de som bevatten van de $$n$$ touwen die erop volgen. Soms worden deze $$n$$ touwen zelfs expliciet aan het touw met de som bevestigd in plaats van aan het hoofdtouw. Er werden ook quipus gevonden waarin de verbindingen van de touwen overeenkomen met sommen van sommen. Dergelijke structuren zouden zeer onwaarschijnlijk zijn als de knopen op een verkeerde manier werden uitgelezen. Gevraagd wordt:
-
Schrijf een functie quipu waaraan een getal $$n \in \mathbb{N}$$ (int) moet doorgegeven worden. De functie moet een string teruggeven met de knopenvoorstelling van $$n$$ op een quipu in de Ashernotatie.
-
Schrijf een functie decimaal2quipu waaraan een reeks (list) natuurlijke getallen (int) moet doorgegeven worden. De functie moet een string teruggeven met de knopenvoorstelling van de gegeven getallen op een quipu in de Ashernotatie.
-
Schrijf een functie quipu2decimaal waaraan een string moet doorgegeven worden met de knopenvoorstelling van één of meer natuurlijke getallen op een quipu in de Ashernotatie. De functie moet de reeks (list) met getallen (int) teruggeven. Indien het argument dat aan de functie wordt doorgegeven geen string is die een geldige knopenvoorstelling in Aschernotatie bevat van één of meer natuurlijke getallen op een quipu, dan moet een AssertionError opgeworpen worden met de boodschap ongeldige knopen.
Voorbeeld
>>> quipu(327)
'3s 2s 7L'
>>> quipu(690)
'6s 9s EE'
>>> quipu(2461)
'2s 4s 6s E'
>>> quipu(107)
'1s X 7L'
>>> quipu(51)
'5s E'
>>> decimaal2quipu([327, 690, 2461])
'3s 2s 7L 6s 9s EE 2s 4s 6s E'
>>> decimaal2quipu([107, 51])
'1s X 7L 5s E'
>>> decimaal2quipu([0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12])
'EE E 2L 3L 4L 5L 6L 7L 8L 9L 1s EE 1s E 1s 2L'
>>> quipu2decimaal('3s 2s 7L 6s 9s EE 2s 4s 6s E')
[327, 690, 2461]
>>> quipu2decimaal('1s X 7L 5s E')
[107, 51]
>>> quipu2decimaal('EE E 2L 3L 4L 5L 6L 7L 8L 9L 1s EE 1s E 1s 2L')
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]
>>> quipu2decimaal('5s 17s 4L')
Traceback (most recent call last):
AssertionError: ongeldige knopen
>>> quipu2decimaal('2s X E 4s 9s')
Traceback (most recent call last):
AssertionError: ongeldige knopen
>>> quipu2decimaal('4s 1L')
Traceback (most recent call last):
AssertionError: ongeldige knopen