Leonard Gordon noted this interesting pattern. The English names of the first eight positive integers (ONE, TWO, THREE, FOUR, FIVE, SIX, SEVEN, EIGHT) contain altogether 32 letters. The smallest rectangular grid into which they can all be packed, word-search fashion, is $$5 \times 5$$. The 32 letters fit into 25 cells, because some of the cells serve double duty. The ratio of these values is \[ \frac{32}{25} = 1.28 \] This ratio remains remarkably consistent as the list of numbers is extended — here are grids for the first eight, nine, ten, eleven and twelve numbers:
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 numbers 9 numbers 10 numbers 11 numbers 12 numbers 32 letters 36 letters 39 letters 45 letters 51 letters 25 cells 28 cells 30 cells 35 cells 40 cells (1.28) (1.29) (1.30) (1.29) (1.28)
Alas, the last one isn't optimal, Gordon notes. The names ONE through TWELVE will fit into a more compact grid
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
… and that raises the ratio to 1.42 letters per cell.
Assignment
We represent a letter grid as a list of the rows of the grid, listed from top to bottom. Each row is itself represented as a list with the consecutive letters (str) listed from left to right.
In order to refer to the cells of a letter grid, the rows are numbered from top to bottom and the columns from left to right, starting at zero. This way, the position of a cell can be represented as a tuple $$(r, c)$$, where $$r$$ denotes the row number and $$c$$ the column number.
Words can be read horizontally, vertically and diagonally from a letter grid in eight possible directions. Each direction is represented as a string (str) with one or two uppercase letters, corresponding to the cardinal directions. For example, the direction W for words that are read in the western direction (from right to left), and the direction NE for words that are read in the northeasterly direction (from bottom left to top right).
For example, if we read three letters from this grid from cell $$(0, 5)$$ in the western direction (W), we get the letters of the word ONE. If we read three letters from cell $$(4, 1)$$ in the northeasterly direction (NE), we get the letters of the word TEN.
Your task:
-
Write a function pack that takes two arguments: i) a string (str) with the letters in a grid read from left to right and from top to bottom, and ii) the number of rows (int) in the grid. The function must return the letter grid.
-
Write a function letters that takes four arguments: i) a number $$n \in \mathbb{N}$$ (int), ii) the position $$(r, c)$$ of a cell in a grid, iii) a direction $$d$$ (str), and iv) a letter grid $$R$$. The function must return the $$n$$ consecutive letters (str) that can be read in grid $$R$$ from cell $$(r, c)$$ in direction $$d$$. The value None must be returned instead, if it is not possible to read the letters from grid $$R$$ in this way.
-
Write a function occurrences that takes two arguments: i) a word (str) and ii) a letter grid. The function must return a set with all occurrences of the word in the grid. If the word can be read in the grid from cell $$(r, c)$$ in direction $$d$$, this occurrence of the word is represented as a string (str) that consists of the row number $$r$$, a comma (,), the column number $$c$$ and the direction $$d$$.
-
Write a function compactness that takes two arguments: i) a collection (list, tuple or set) of words (str) and ii) a letter grid. If all words occur in the grid at least once, the function must return the ratio (float) of the total number of letters in all words altogether and the number of cells in the grid. Otherwise the function must return the value -1.0 (float).
All functions may assume that only valid arguments are passed, without the need to check this explicitly.
Example
>>> grid = pack('EIGHTFOURWXISMOSEVENTHREE', 5)
>>> grid
[['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), 'S', grid)
'ONE'
>>> letters(3, (0, 4), 'S', grid)
'TWO'
>>> occurrences('ONE', grid)
{'2,4S'}
>>> occurrences('TWO', grid)
{'0,4S'}
>>> occurrences('THREE', grid)
{'4,0E'}
>>> occurrences('FOUR', grid)
{'1,0E'}
>>> occurrences('FIVE', grid)
{'1,0SE'}
>>> occurrences('SIX', grid)
{'2,2W'}
>>> occurrences('SEVEN', grid)
{'3,0E'}
>>> occurrences('EIGHT', grid)
{'0,0E'}
>>> occurrences('NINE', grid)
set()
>>> occurrences('EN', grid)
{'3,3E', '4,3NE', '4,4N'}
>>> compactness(['ONE', 'TWO', 'THREE', 'FOUR', 'FIVE', 'SIX', 'SEVEN', 'EIGHT'], grid)
1.28
>>> compactness(['ONE', 'TWO', 'THREE', 'FOUR', 'FIVE', 'SIX', 'SEVEN', 'EIGHT', 'NINE'], grid)
-1.0