In de roman The Tracer of Lost Persons¹ (1906) van Robert Chalmers probeert meneer Keen een jonge vrouw te vinden waardoor kapitein Harren geobsedeerd geraakt is. Tijdens zijn zoektocht maakt hij een schets van deze vreemde tekens die hij op een mysterieuze foto gevonden heeft.

Meneer Keen zei hierover:

Het is de meest bizarre code die ik ooit ben tegengekomen. De vreemdste waar ik ooit van gehoord heb. Ik heb wel honderden geheime codes gezien — honderden — geheime codes van het Ministerie van Buitenlandse Zaken, geheime militaire codes, ingewikkelde oosterse geheimschriften, symbolen die gebruikt worden bij commerciële transacties, tekens die gebruikt worden door criminelen en andere soorten boosdoeners. Ze kunnen stuk voor stuk opgelost worden met tijd en geduld en een beetje kennis van het onderwerp. Maar deze … deze is te eenvoudig.

Het bericht onthult inderdaad de naam van de jonge vrouw waarnaar kapitein Harren op zoek is. Wie is ze?

Opgave

We duiden acht segmenten aan met de kleine letters a–h en schikken ze op de volgende manier:

Door één of meer segmenten te selecteren, kunnen we in totaal 255 verschillende vormen maken. Zo kunnen we bijvoorbeeld afspreken dat deze vormen de cijfers 0–9 voorstellen:

Het maakt geen verschil in welke volgorde de segmenten (a–h) van een vorm opgelijst worden: chaf, hafc en fahc stellen dezelfde vorm voor. Bovendien kunnen we ook afspreken dat er verschillende vormen zijn die hetzelfde cijfer voorstellen. Zo zouden we het cijfer 9 op de volgende manieren kunnen vormen:

De boxcode is een geheimschrift waarbij in een tekstbestand wordt vastgelegd op welke manieren we de tien cijfers (0–9) kunnen vormen. Elke regel bevat een cijfer, gevolgd door een spatie en een vorm (voorgesteld als een reeks letters (a–h) die corresponderen met de segmenten van de vorm). Er is minstens één regel voor elk cijfer (0–9), maar hetzelfde cijfer kan op meerdere regels voorkomen. Vormen stellen op een ondubbelzinnige manier een cijfer voor, waardoor elke vorm op hoogstens één regel voorkomt. Bijvoorbeeld (code.txt⁴):

0 hde
1 b
1 d
2 fcah
3 gfac
4 bgf
5 eah
6 ghfc
6 chgb
7 afh
7 ab
8 fhcaeg
9 eafh
9 ebfa

Om een bericht te coderen met behulp van deze boxcode, nemen we enkel de letters van het bericht (alle andere karakters worden genegeerd) en maken we geen onderscheid tussen hoofdletters en kleine letters.

Elke letter wordt eerst omgezet naar zijn positie in het alfabet (A=1, B=2, ..., Z=26). Daarna wordt elk cijfer van die positie omgezet naar een corresponderende vorm. Als een cijfer op meerdere manieren kan gevormd worden, dan kiezen we willekeurig één van die vormen. Zo staat de letter H op positie 8 in het alfabet, en dus kan die gecodeerd worden als fecgha op basis van de voorgaande boxcode. Als de positie uit twee cijfers bestaat, dan scheiden we hun corresponderende vormen door een koppelteken (-). Zo staat de letter x op positie 24 in het alfabet, en dus kan die gecodeerd worden als hfac-bfg (waarbij de vorm hfac het cijfer 2 codeert en de vorm bgf het cijfer 4). De gecodeerde letters van een bericht worden telkens van elkaar gescheiden door één spatie.

Gevraagd wordt:

• Schrijf een functie lees_boxcode waaraan de locatie (str) moet doorgegeven worden van een tekstbestand dat vastlegt op welke manieren de tien cijfers (0–9) kunnen gevormd worden. De functie moet een dictionary (dict) teruggeven die elk cijfer (str) afbeeldt op de verzameling (set) van alle vormen (str) voor dat cijfer. Hierbij moeten de letters van elke vorm in alfabetische volgorde opgelijst worden. We noemen dit de dictionary-voorstelling van de boxcode.

• Schrijf een functie letter2code waaraan twee argumenten moeten doorgegeven worden: i) een letter $$l$$ (str) en ii) de dictionary-voorstelling van een boxcode $$\mathcal{B}$$ (dict). De functie moet een codering (str) voor de letter $$l$$ volgens boxcode $$\mathcal{B}$$ teruggeven. Zorg er daarbij voor dat elk cijfer willekeurig door één van zijn mogelijke vormen voorgesteld wordt. Het is niet nodig om er voor te zorgen dat de segmenten van een vorm in een willekeurige volgorde opgelijst worden (maar dat mag wel).

• Schrijf een functie code2letter waaraan twee argumenten moeten doorgegeven worden: i) een gecodeerde letter $$l$$ en ii) de dictionary-voorstelling van de boxcode $$\mathcal{B}$$ (dict) die daarvoor gebruikt werd. Hou daarbij rekening met het feit dat een cijfer door elk van zijn mogelijke vormen kan voorgesteld worden, en dat de segmenten van een vorm in willekeurige volgorde kunnen opgelijst worden. De functie moet de originele letter (str; in hoofdletters) teruggeven.

• Schrijf een functie codeer waaraan twee argumenten moeten doorgegeven worden: i) een bericht (str) en ii) de dictionary-voorstelling van een boxcode $$\mathcal{B}$$ (dict). De functie moet een codering (str) van het bericht volgens boxcode $$\mathcal{B}$$ teruggeven. Zorg er daarbij voor dat elk cijfer willekeurig door één van zijn mogelijke vormen voorgesteld wordt. Het is niet nodig om er voor te zorgen dat de segmenten van een vorm in een willekeurige volgorde opgelijst worden (maar dat mag wel). We onderstrepen ook nog eens dat enkel de letters van het bericht moeten gecodeerd worden. Alle andere karakters moeten genegeerd worden.

• Schrijf een functie decodeer waaraan twee argumenten moeten doorgegeven worden: i) een gecodeerd bericht (str) en ii) de dictionary-voorstelling van de boxcode $$\mathcal{B}$$ (dict) die daarvoor gebruikt werd. Hou daarbij rekening met het feit dat een cijfer door elk van zijn mogelijke vormen kan voorgesteld worden, en dat de segmenten van een vorm in willekeurige volgorde kunnen opgelijst worden. De functie moet de opeenvolgende letters uit het oorspronkelijke bericht (str; in hoofdletters) teruggeven.

Alle functies mogen ervan uitgaan dat er enkel geldige argumenten aan doorgegeven worden, zonder dat dit expliciet moet gecontroleerd worden.

Voorbeeld

In onderstaande voorbeeldsessie gaan we ervan uit dat het tekstbestand code.txt⁵ zich in de huidige directory bevindt.

>>> boxcode = lees_boxcode('code.txt6')
>>> boxcode['0']
{'deh'}
>>> boxcode['1']
{'b', 'd'}
>>> boxcode['9']
{'abef', 'aefh'}

>>> letter2code('H', boxcode)
'fecgha'
>>> letter2code('x', boxcode)
'hfac-bfg'

>>> code2letter('fecgha', boxcode)
'H'
>>> code2letter('hfac-bfg', boxcode)
'X'

>>> codeer('And now for something completely different!', boxcode)
'b b-bgf fbg d-bfg b-hae afhc-fagc bhgc b-eha b-hfceag d-feha d-hae b-agfc hae afhc-edh ghecfa fahe d-fgb ab gcaf b-aeh d-gfca d-gcbh d-chfa eah cahf-hed eah d-acfh hfac-hea fbg fbea ghcb chgb eha b-cahfeg hae b-bgf hcfa-hed'
>>> codeer('And now for something completely different!', boxcode)
'd d-bgf bgf d-fgb d-hea ahcf-cfag cgfh d-ahe d-cgfeha b-fbae b-aeh b-fgac ahe afhc-ehd afghec fhea b-bfg ba cagf b-ahe d-cagf b-hgbc b-chfa aeh afhc-hde hae d-chaf cahf-hea fgb ehaf cgbh chgb hae b-aefcgh aeh d-bfg fach-hed'

>>> decodeer('b b-bgf fbg d-bfg b-hae afhc-fagc bhgc b-eha b-hfceag d-feha d-hae b-agfc hae afhc-edh ghecfa fahe d-fgb ab gcaf b-aeh d-gfca d-gcbh d-chfa eah cahf-hed eah d-acfh hfac-hea fbg fbea ghcb chgb eha b-cahfeg hae b-bgf hcfa-hed', boxcode)
'ANDNOWFORSOMETHINGCOMPLETELYDIFFERENT'
>>> decodeer('d d-bgf bgf d-fgb d-hea ahcf-cfag cgfh d-ahe d-cgfeha b-fbae b-aeh b-fgac ahe afhc-ehd afghec fhea b-bfg ba cagf b-ahe d-cagf b-hgbc b-chfa aeh afhc-hde hae d-chaf cahf-hea fgb ehaf cgbh chgb hae b-aefcgh aeh d-bfg fach-hed', boxcode)
'ANDNOWFORSOMETHINGCOMPLETELYDIFFERENT'