Het oog van Leonard Gordon viel op een interessant patroon. De Engelse namen van de eerste acht strikt positieve natuurlijke getallen (ONE, TWO, THREE, FOUR, FIVE, SIX, SEVEN, EIGHT) bevatten in totaal 32 letters. Het kleinste rechthoekig rooster waarin ze woordzoeker-gewijs kunnen verpakt worden, is een $$5 \times 5$$ rooster. De 32 letters passen in de 25 cellen van het rooster omdat sommige cellen dubbel gebruikt worden. De verhouding van deze waarden is \[ \frac{32}{25} = 1.28 \] Deze verhouding blijft nagenoeg dezelfde naarmate de lijst met getallen uitgebreid wordt. Hier zijn de roosters voor de eerste acht, negen, tien, elf en twaalf getallen:
E I G H T O N E E R H T E I G H T F E L E V E N S S E V E N O W T F O U R W S E V E N I N F X W O I F S O I E F I V E E R H T X I S O E I G H T W O N I N E O U G O I T N V O G X N E N I N S E V E N F O U R X I S S E V E N R H W U X V E E U H E V L E W T T H R E E T H R E E T H R E E E N R T N E V E L E 8 getallen 9 getallen 10 getallen 11 getallen 12 getallen 32 letters 36 letters 39 letters 45 letters 51 letters 25 cellen 28 cellen 30 cellen 35 cellen 40 cellen (1.28) (1.29) (1.30) (1.29) (1.28)
Helaas is het laatste rooster niet optimaal, merkt Gordon op. De getallen ONE tot en met TWELVE passen in een kleiner rooster
T W E L V E F N E X S L O F I V E E U S G N V V R T H R E E O W T E N N
… en dat drijft de compactheid op naar 1.42 letters per cel.
Opgave
We stellen een rooster met letters voor als een lijst (list) met de rijen van het rooster, opgelijst van boven naar onder. Elke rij wordt zelf voorgesteld als een lijst (list) met de opeenvolgende letters (str) opgelijst van links naar rechts.
Om naar de cellen van een rooster met letters te kunnen verwijzen, worden de rijen van boven naar onder genummerd en de kolommen van links naar rechts, telkens vanaf nul. Op die manier kan de positie van een cel voorgesteld worden als een tuple $$(r, k)$$, waarbij $$r$$ het rijnummer aanduidt en $$k$$ het kolomnummer.
In het rooster kunnen woorden horizontaal, verticaal en diagonaal in acht mogelijk richtingen uitgelezen worden. Elke richting wordt voorgesteld als een string (str) met één of twee hoofdletters, overeenkomstig de windrichtingen. Bijvoorbeeld de richting W voor woorden die naar het westen uitgelezen worden (van rechts naar links), of de richting NO voor woorden die naar het noordoosten uitgelezen worden (van linksonder naar rechtsboven).
Als we in onderstaand rooster bijvoorbeeld drie letters uitlezen vanaf cel $$(0, 5)$$ in westelijke richting (W), dan krijgen we de letters van het woord ONE. Als we drie letters uitlezen vanaf cel $$(4, 1)$$ in noordoostelijke richting (NO), dan krijgen we de letters van het woord TEN.
Gevraagd wordt:
-
Schrijf een functie verpak waaraan twee argumenten moeten doorgegeven worden: i) een string (str) met de letters van een rooster uitgelezen van links naar rechts en van boven naar onder, en ii) het aantal rijen (int) van het rooster. De functie moet het rooster van letters teruggeven.
-
Schrijf een functie letters waaraan vier argumenten moeten doorgegeven worden: i) een getal $$n \in \mathbb{N}$$ (int), ii) de positie $$(r, k)$$ van een cel in een rooster, iii) een richting $$d$$ (str) en iv) een rooster van letters $$R$$. De functie moet de $$n$$ opeenvolgende letters (str) teruggeven die in rooster $$R$$ uitgelezen worden vanaf cel $$(r, k)$$ in richting $$d$$. Als het niet mogelijk is om op deze manier de letters uit rooster $$R$$ te lezen, dan moet de waarde None teruggegeven worden.
-
Schrijf een functie voorkomens waaraan twee argumenten moeten doorgegeven worden: i) een woord (str) en ii) een rooster van letters. De functie moet een verzameling (set) teruggeven met alle voorkomens van het woord in het rooster. Als het woord uit het rooster kan uitgelezen worden vanaf cel $$(r, k)$$ in richting $$d$$, dan wordt dit voorkomen voorgesteld als de string (str) die bestaat uit het rijnummer $$r$$, een komma (,), het kolomnummer $$k$$ en de richting $$d$$.
-
Schrijf een functie compactheid waaraan twee argumenten moeten doorgegeven worden: i) een collectie (list, tuple of set) van woorden (str) en ii) een rooster van letters. Als alle woorden minstens één keer in het rooster voorkomen, dan moet de functie de verhouding (float) teruggeven van het totaal aantal letters in alle woorden samen en het aantal cellen in het rooster. Anders moet de functie de waarde -1.0 (float) teruggeven.
Alle functies mogen ervan uitgaan dat er enkel geldige argumenten aan doorgegeven worden, zonder dat dit expliciet moet gecontroleerd worden.
Voorbeeld
>>> rooster = verpak('EIGHTFOURWXISMOSEVENTHREE', 5)
>>> rooster
[['E', 'I', 'G', 'H', 'T'], ['F', 'O', 'U', 'R', 'W'], ['X', 'I', 'S', 'M', 'O'], ['S', 'E', 'V', 'E', 'N'], ['T', 'H', 'R', 'E', 'E']]
>>> letters(3, (2, 4), 'Z', rooster)
'ONE'
>>> letters(3, (0, 4), 'Z', rooster)
'TWO'
>>> voorkomens('ONE', rooster)
{'2,4Z'}
>>> voorkomens('TWO', rooster)
{'0,4Z'}
>>> voorkomens('THREE', rooster)
{'4,0O'}
>>> voorkomens('FOUR', rooster)
{'1,0O'}
>>> voorkomens('FIVE', rooster)
{'1,0ZO'}
>>> voorkomens('SIX', rooster)
{'2,2W'}
>>> voorkomens('SEVEN', rooster)
{'3,0O'}
>>> voorkomens('EIGHT', rooster)
{'0,0O'}
>>> voorkomens('NINE', rooster)
set()
>>> voorkomens('EN', rooster)
{'3,3O', '4,3NO', '4,4N'}
>>> compactheid(['ONE', 'TWO', 'THREE', 'FOUR', 'FIVE', 'SIX', 'SEVEN', 'EIGHT'], rooster)
1.28
>>> compactheid(['ONE', 'TWO', 'THREE', 'FOUR', 'FIVE', 'SIX', 'SEVEN', 'EIGHT', 'NINE'], rooster)
-1.0