Een leuk wist-je-datje dat voor de rest niets met deze opgave te maken heeft. In 2004 verscheen op verschillende plaatsen in de Verenigde Staten een mysterieus reclamebord:

De meeste mensen weten wel dat de wiskundige constante $$e$$ (2.718281828…) het grondtal is van de natuurlijke logaritme¹, maar zoeken naar priemgetallen van 10 cijfers is geen eenvoudige opdracht. Gelukkig is het eerste priemgetal van 10 cijfers (7427466391) in $$e$$ al te vinden vanaf positie 101:

2.718281828459045235360287471352662497757247093699959574966967627724076630353
  547594571382178525166427427466391932003059921817413596629043572900334295260
  595630738132328627943490763233829880753195251019011573834187930702154089149
  934884167509244761460668082264800168477411853742345442437107539077744992069
  551702761838606261331384583000752044933826560297606737113200709328709127443

Wie het mysterie had opgelost en de website 7427466391.com² bezocht, vond er een nog moeilijker probleem om op te lossen. De oplossing van dat probleem leidde naar een pagina bij Google Labs … waarop een uitnodiging stond om een CV in te dienen.

Opgave

Een interval $$[o, b]$$ met $$o \leq b$$ is een afkorting voor de collectie van alle gehele getallen $$n$$ waarvoor geldt dat $$o \leq n \leq b$$. Zo stelt het interval $$[19, 25]$$ de collectie $$\{19, 20, 21, 22, 23, 24, 25\}$$ voor. We stellen een interval voor als een lijst (list) of een tuple (tuple) met twee getallen $$o, b \in \mathbb{Z}$$ (int), waarbij geldt dat $$o \leq b$$.

Een collectie gehele getallen stellen we voor als een lijst (list), een tuple (tuple) of een verzameling (set) van gehele getallen (int) en/of intervallen. Het is toegelaten dat een integer meerdere keren voorkomt in een collectie, dat een integer uit een collectie behoort tot een interval uit de collectie, en dat een interval uit een collectie overlapt met een ander interval uit de collectie. Zo stellen

$$\{33, [27, 30], 32, 25, [20, 24], 31, 19\}$$

en

$$\{19, 20, 21, 22, 23, 24, 25, 27, 28, 29, 30, 31, 32, 33\}$$

dezelfde collecties gehele getallen voor.

De normaalvorm van een collectie gehele getallen wordt voorgesteld als een lijst (list) met gehele getallen (int) en/of intervallen, en voldoet aan de volgende voorwaarden:

• er worden zoveel mogelijk getallen opgenomen in een interval

• intervallen groeperen zoveel mogelijk getallen

• getallen en intervallen worden in stijgende volgorde opgelijst

• intervallen worden voorgesteld als een lijst (list) van twee getallen (int)

• intervallen met één getal ($$[n, n]$$) worden voorgesteld als het getal $$n$$ (int)

Deze voorwaarden op de normaalvorm zorgen voor een unieke voorstelling van de collectie gehele getallen. De normaalvorm van de twee collecties die we hierboven als voorbeeld gebruikt hebben, is

$$[[19, 25], [27, 33]]$$

Definieer een klasse Collectie waarmee collecties gehele getallen kunnen voorgesteld worden. Bij het aanmaken van een collectie (Collectie) moet een collectie gehele getallen doorgegeven worden. Als het argument dat wordt doorgegeven geen geldige voorstelling is van een collectie gehele getallen, dan moet een AssertionError opgeworpen worden met de boodschap ongeldige collectie. Voorts moet de klasse minstens de volgende methoden ondersteunen, waaraan geen argumenten moeten doorgegeven worden:

• De methode getallen moet een verzameling (set) teruggeven met alle gehele getallen (int) in de collectie.

• De methode normaalvorm moet de normaalvorm (list) van de collectie gehele getallen teruggeven.

Als er een collectie $$c$$ (Collectie) wordt doorgegeven aan de ingebouwde functie len dan moet die het aantal (int) getallen in collectie $$c$$ teruggeven. Als er een collectie $$c$$ (Collectie) wordt doorgegeven aan de ingebouwde functie str dan moet die een string (str) teruggeven die bestaat uit de normaalvorm van collectie $$c$$. Als er een collectie $$c$$ (Collectie) wordt doorgegeven aan de ingebouwde functie repr dan moet die een string (str) teruggeven met een Python expressie die een nieuwe collectie (Collectie) aanmaakt op basis van de normaalvorm van collectie $$c$$.

Zorg ervoor dat de volgende bewerkingen telkens een nieuwe collectie (Collectie) opleveren als ze uitgevoerd worden op twee collecties (Collectie):

Zorg er ook voor dat de volgende Booleaanse bewerkingen de gegeven betekenis krijgen als ze uitgevoerd worden op twee collecties (Collectie):

Voorbeeld

>>> A = Collectie([33, [27, 30], 32, 25, [20, 24], 31, 19])
>>> A.getallen()
{19, 20, 21, 22, 23, 24, 25, 27, 28, 29, 30, 31, 32, 33}
>>> len(A)
14
>>> A.normaalvorm()
[[19, 25], [27, 33]]
>>> print(A)
[[19, 25], [27, 33]]
>>> A
Collectie([[19, 25], [27, 33]])

>>> B = Collectie([22, 26, 30])
>>> A - B
Collectie([[19, 21], [23, 25], [27, 29], [31, 33]])
>>> B - A
Collectie([26])
>>> A | B
Collectie([[19, 33]])
>>> A & B
Collectie([22, 30])
>>> A ^ B
Collectie([[19, 21], [23, 29], [31, 33]])

>>> C = Collectie([[1, 5], [7, 7]])
>>> D = Collectie([[1, 5], [7, 8]])
>>> C == Collectie([1, 2, 3, 4, 5, 7])
True
>>> C == D
False
>>> C != D
True
>>> C < D
True
>>> C <= D
True
>>> C > D
False
>>> C >= D
False
>>> D > C
True
>>> D >= C
True