Like good magic tricks, clever puzzles can inspire awe, reveal mathematical truths and prompt important questions. At least that is what Martin Gardner thought. His name is synonymous with the legendary Mathematical Games column he wrote for a quarter of a century in Scientific American. The column that began in January 1957 has become a legend in publishing, even though it's been almost 40 years since the last one appeared. Thanks to his own mathemagical skills, Gardner presented noteworthy mathematics every month with all the wonder of legerdemain and — in so doing — captivated a huge readership worldwide. The columns are still considered models of clarity and elegance for introducing fresh and engaging ideas in mathematics in non-technical ways.
While many articles of the ever-prolific Martin Gardner fall under the umbrella of "recreational mathematics", others touched on cutting-edge concepts involving contributions from some of the world's most creative minds. Even the articles that seemed to be purely for entertainment sometimes inspired important research, some of which led to developments with real impact on science, technology and society. This success is all the more remarkable considering that Gardner had no formal training in mathematics. In his memoirs Undiluted Hocus-Pocus (Princeton, 2013), Gardner recalls:
One of the pleasures in writing the column was that it introduced me to so many top mathematicians, which of course I was not. Their contributions to my column were far superior to anything I could write, and were a major reason for the column's growing popularity. The secret of its success was a direct result of my ignorance. Even today my knowledge of math extends only through calculus, and even calculus I only dimly comprehend. As a result, I had to struggle to understand what I wrote, and this helped me write in ways that others could understand.
We focus on a nice trick that appeared in one of the Mathematical Games columns that Martin Gardner wrote together with the mathematician Ross Honsberger. Deal cards into any rectangular array.
Put the cards on each row of the array such that they are sorted in increasing order. In doing so, you only need to take into account the numerical value of the cards.
Now you do the same with the cards in each column of the array.
Surprisingly, that last step hasn't disturbed the preceding one — the cards in each row are still sorted in increasing order. Any idea how this is possible?
Assignment
The above trick works with all objects that can be sorted. We keep it simple by considering only integers. An example: \[ \begin{array}{rrrrrr} 2 & 12 & 2 & 4 & 6 & 12\\ 9 & 11 & 3 & 4 & 1 & 6\\ 13 & 2 & 5 & 9 & 1 & 1\\ 13 & 2 & 5 & 10 & 11 & 9 \end{array} \,\, \stackrel{\text{sort rows}}{\longrightarrow} \,\, \begin{array}{rrrrrr} 2& 2& 4& 6& 12& 12\\ 1& 3& 4& 6& 9& 11 \\ 1& 1& 2& 5& 9& 13\\ 2& 5& 9& 10& 11& 13 \end{array} \,\, \stackrel{\text{sort columns}}{\longrightarrow} \,\, \begin{array}{rrrrrr} 1& 1& 2& 5& 9& 11 \\ 1& 2& 4& 6& 9& 12 \\ 2& 3& 4& 6& 11& 13 \\ 2& 5& 9& 10& 12& 13 \end{array} \]
Define a class Grid that can be used to represent rectangular arrays of integers. One argument must be passed when creating a new grid (Grid). It the argument is a string (str), it specifies the location of a text file containing a description of the grid. Each row of the grid is described on a separate line. Each line contains the numbers in the corresponding row, separated by one or more spaces or tabs. If the argument is a sequence (list or tuple), it contains the rows of the grid, with each row represented as a sequence (list or tuple) containing the integers (int) in that row. In both cases, the grid must have at least one row and at least one column, and each row must contain the same number of integers. If this is not the case, an AssertionError must be raised with the message invalid grid.
Each grid (Grid) must have a getter (or property) smallest that returns the smallest number in the grid, and a getter (or property) largest that returns the largest integer in the grid.
If a grid $$g$$ (Grid) is passed to the built-in function str, a string representation of grid $$g$$ must be returned. Each integer in this string representation must be right aligned over $$p$$ positions, where $$p$$ is the number of characters needed to represent the widest integer in the grid. The columns of the grid must be separated by a single space in the string representation.
A grid $$g$$ (Grid) must support at least the following methods:
-
A method issorted with two optional parameters decreasing and columns that may take a Boolean value (bool; default value: False). The method must return a Boolean value (bool) that indicates whether all rows (columns = False) or all columns (columns = True) of grid $$g$$ are sorted in increasing (decreasing = False) or decreasing (decreasing = True) order.
-
A method sort with two optional parameters decreasing and columns that may take a Boolean value (bool; default value: False). The method must sort the integers on each row (columns = False) or each column (columns = True) of grid $$g$$ in increasing (decreasing = False) or decreasing (decreasing = True) order, and return a reference to grid $$g$$.
If two grids $$r$$ and $$s$$ (Grid) do not have the same number of rows, the sum $$r + s$$ must raise an AssertionError with message different number of rows. Otherwise, the sum $$r + s$$ must yield a new grid (Grid) formed by putting the columns of grid $$s$$ after the columns of grid $$r$$.
If two grids $$r$$ and $$s$$ (Grid) do not have the same number of columns, the difference $$r - s$$ must raise an AssertionError with message different number of columns. Otherwise, the difference $$r - s$$ must yield a new grid (Grid) formed by putting the columns of grid $$s$$ underneath the columns of grid $$r$$.
Example
In this interactive session, we assume the text file grid.txt is located in the current directory.
>>> grid = Grid('grid.txt')
>>> grid.largest
16
>>> grid.smallest
1
>>> print(grid)
16 3 2 13
5 10 11 8
9 6 7 12
4 15 14 1
>>> grid.issorted()
False
>>> grid.issorted(columns=True)
False
>>> print(grid.sort())
2 3 13 16
5 8 10 11
6 7 9 12
1 4 14 15
>>> grid.issorted()
True
>>> grid.issorted(columns=True)
False
>>> print(grid.sort(columns=True))
1 3 9 11
2 4 10 12
5 7 13 15
6 8 14 16
>>> grid.issorted()
True
>>> grid.issorted(columns=True)
True
>>> print(grid.sort(decreasing=True))
11 9 3 1
12 10 4 2
15 13 7 5
16 14 8 6
>>> grid.issorted()
False
>>> grid.issorted(decreasing=True)
True
>>> print(grid.sort(columns=True, decreasing=True))
16 14 8 6
15 13 7 5
12 10 4 2
11 9 3 1
>>> grid.issorted(columns=True)
False
>>> grid.issorted(columns=True, decreasing=True)
True
>>> row = Grid([[17, 18, 19, 20]])
>>> print(grid - row)
16 14 8 6
15 13 7 5
12 10 4 2
11 9 3 1
17 18 19 20
>>> col = Grid([[-21], [-22], [-23], [-24]])
>>> print(col + grid)
-21 16 14 8 6
-22 15 13 7 5
-23 12 10 4 2
-24 11 9 3 1
>>> print(grid - row)
16 14 8 6
15 13 7 5
12 10 4 2
11 9 3 1
17 18 19 20
>>> print(col + grid)
-21 16 14 8 6
-22 15 13 7 5
-23 12 10 4 2
-24 11 9 3 1
>>> Grid([[1], [2, 3], [4, 5, 6]])
Traceback (most recent call last):
AssertionError: invalid grid
>>> Grid([])
Traceback (most recent call last):
AssertionError: invalid grid
>>> Grid([[]])
Traceback (most recent call last):
AssertionError: invalid grid
>>> grid - col
Traceback (most recent call last):
AssertionError: different number of columns
>>> grid + row
Traceback (most recent call last):
AssertionError: different number of rows