Éric Angelini ontdekte deze reeks die zichzelf progressief beschrijft:
10 71 32 23 14 15 16 27 18 19
20 81 72 53 44 35 26 47 38 29
40 101 82 73 64 65 56 77 58 39
60 131 92 93 74 75 86 107 88 69
80 201 122 113 84 85 96 117 138 89
De eerste regel beschrijft zichzelf: ze bevat één keer het cijfer 0, zeven keer het cijfer 1, drie keer het cijfer 2, twee keer het cijfer 3, enzoverder.
Op een analoge manier beschrijft de tweede regel de gezamelijke inhoud van de eerste twee regels: ze bevatten samen twee keer het cijfer 0, acht keer het cijfer 1, zeven keer het cijfer 2, vijf keer het cijfer 3, enzoverder.
Ook de volgende regels beschrijven hun eigen inhoud en die van alle voorgaande regels. De vijfde regel beschrijft de gezamelijke inhoud van alle regels: ze bevatten samen acht keer het cijfer 0, twintig keer het cijfer 1, twaalf keer het cijfer 2, elf keer het cijfer 3, enzoverder.
Hij vermoedt dat een zelfbeschrijvende reeks met zes regels er misschien ook wel moet inzitten, maar tot nu toe heeft hij er nog geen gevonden.
De cijferfrequentie van een string $$s$$ (str) is een tuple van tien getallen $$(a_0, a_1, \ldots, a_9)$$, waarbij $$a_i \in \mathbb{N}$$ (int) aangeeft hoeveel keer het cijfer $$i$$ voorkomt in $$s$$ ($$i = 0, 1, \ldots, 9$$).
De beschrijving van een cijferfrequentie $$(a_0, a_1, \ldots, a_9)$$ is een string (str) die wordt opgemaakt als
$$a_0$$0 $$a_1$$1 $$\ldots$$ $$a_9$$9
Daarbij worden voorloopnullen in de weergave van $$a_i$$i ($$i = 0, 1, \ldots, 9$$) weggelaten: als het cijfer 3 niet voorkomt in de string $$s$$ dan schrijven we in de beschrijving van de cijferfrequentie gewoon 3 en niet 03. Gevraagd wordt:
Schrijf een functie cijferfrequentie waaraan een string (str) moet doorgegeven worden. De functie moet de cijferfrequentie van de gegeven string teruggeven.
Schrijf een functie beschrijving waaraan de cijferfrequentie van een string moet doorgegeven worden. De functie moet de beschrijving van de gegeven cijferfrequentie teruggeven.
Schrijf een functie iszelfbeschrijvend waaraan een reeks (list of tuple) van $$n \in \mathbb{N}$$ strings (str) moet doorgegeven worden. De functie moet een Booleaanse waarde (bool) teruggeven, die aangeeft of de $$n$$ strings een reeks vormen die zichzelf progressief beschrijft. Dat is het geval als elke $$i$$-de string de beschrijving is van de gezamelijke inhoud van de eerste $$i$$ strings ($$i = 1, 2, \ldots, n$$).
Een lege reeks is per definitie zelfbeschrijvend.
Schrijf een functie iszelfbeschrijvend_2 waaraan een variabel aantal van $$n \in \mathbb{N}$$ strings (str) kunnen doorgegeven worden. De functie moet een Booleaanse waarde (bool) teruggeven, die aangeeft of de $$n$$ strings een reeks vormen die zichzelf progressief beschrijft. Dat is het geval als elke $$i$$-de string de beschrijving is van de gezamelijke inhoud van de eerste $$i$$ strings ($$i = 1, 2, \ldots, n$$).
>>> cijferfrequentie('10 71 32 23 14 15 16 27 18 19')
(1, 7, 3, 2, 1, 1, 1, 2, 1, 1)
>>> cijferfrequentie('F1gur471v3ly 5p34k1ng?')
(0, 3, 0, 2, 2, 1, 0, 1, 0, 0)
>>> beschrijving((1, 7, 3, 2, 1, 1, 1, 2, 1, 1))
'10 71 32 23 14 15 16 27 18 19'
>>> beschrijving((0, 3, 0, 2, 2, 1, 0, 1, 0, 0))
'0 31 2 23 24 15 6 17 8 9'
>>> iszelfbeschrijvend(['10 71 32 23 14 15 16 27 18 19'])
True
>>> iszelfbeschrijvend(['F1gur471v3ly 5p34k1ng?'])
False
>>> iszelfbeschrijvend([
... '10 71 32 23 14 15 16 27 18 19',
... '20 81 72 53 44 35 26 47 38 29'
... ])
True
>>> iszelfbeschrijvend((
... '10 71 32 23 14 15 16 27 18 19',
... '20 81 72 53 44 35 26 47 38 29',
... '40 101 82 73 64 65 56 77 58 39',
... '60 131 92 93 74 75 86 107 88 69',
... '80 201 122 113 84 85 96 117 138 89'
... ))
True
>>> iszelfbeschrijvend_2('10 71 32 23 14 15 16 27 18 19')
True
>>> iszelfbeschrijvend_2('F1gur471v3ly 5p34k1ng?')
False
>>> iszelfbeschrijvend_2(
... '10 71 32 23 14 15 16 27 18 19',
... '20 81 72 53 44 35 26 47 38 29'
... )
True
>>> iszelfbeschrijvend_2(
... '10 71 32 23 14 15 16 27 18 19',
... '20 81 72 53 44 35 26 47 38 29',
... '40 101 82 73 64 65 56 77 58 39',
... '60 131 92 93 74 75 86 107 88 69',
... '80 201 122 113 84 85 96 117 138 89'
... )
True
Éric Angelini mag zijn droom opbergen om een zelfbeschrijvende reeks met 6 regels te vinden. Toon Baeyens van de Universiteit Gent kon aantonen dat een dergelijke reeks niet bestaat. Bovendien toonde hij ook aan dat behalve de zelfbeschrijvende reeks met 5 regels uit de inleiding, er nog maar één andere zelfbeschrijvende reeks met 5 regels bestaat:
10 71 32 23 14 15 16 27 18 19
20 81 72 53 44 35 26 47 38 29
30 111 82 83 74 45 46 77 68 39
40 151 92 93 94 75 56 117 78 79
60 241 112 113 114 85 76 137 108 89
Althans als we ons beperken tot het decimaal talstelsel.