© The Author(s), under exclusive license to APress Media, LLC, part of Springer Nature 2022
M. IndenPython Challengeshttps://doi.org/10.1007/978-1-4842-7398-2_6

6. Arrays

Michael Inden1  
(1)
Zurich, Switzerland
 

Arrays are data structures that store values of the same data type in a contiguous memory area. Thus, arrays are more memory-optimal and perform better than lists but are not supported natively in Python. However, they are supported by the array and numpy modules. In the following, you will look at the processing of data with the help of additional modules and deepen it with the help of exercises.

6.1 Introduction

While arrays are basic building blocks in many other programming languages, they exist in Python only as extensions, such as in the array and numpy modules. Because the former has only one-dimensional arrays and a cryptic syntax like
>>> import array
>>> ints = array.array('i', [2, 4, 6, 8])
>>> ints
array('i', [2, 4, 6, 8])
the choice for the following descriptions falls on numpy,1 whose array implementation is more elegant and more pleasant to handle. In particular, arrays can be created quite easily from lists, even multidimensional ones:
import numpy as np
numbers = np.array([1, 2, 3, 4, 5, 6, 7])
primes = np.array([2, 3, 5, 7, 11, 13, 17])
twodim = np.array([["A1", "A2"],
                   ["B1", "B2"],
                   ["C1", "C2"]])

NumPy almost feels like a built-in data type since many operations like slicing and index accesses or the standard function len() are possible. You’ll look at what to consider for multidimensional arrays later.

By providing arrays as a stand-alone module, an import is necessary. But arrays, unlike many built-in data types in other languages, are not just simple data containers but can do much more in terms of functionality than in Java or C++, for example.

NumPy offers various mathematical functionalities. I will go into more detail about NumPy specialties later. Upfront you will investigate one-dimensional and multidimensional arrays in this introduction and build a basic understanding of arrays.

6.1.1 One-Dimensional Arrays

As an introduction to processing data with arrays and to build knowledge of possible interview questions, let’s look at some examples.

Textual Output

Arrays provide an appealing textual output, which is greatly beneficial for following the upcoming examples, especially the two-dimensional ones.
>>> grades = np.array(["A1", "A2", "B1", "B2", "C1", "C2"])
>>> grades
array(['A1', 'A2', 'B1', 'B2', 'C1', 'C2'], dtype='<U2')

Example 1: Swapping Elements

A common functionality is swapping elements at two positions. This can be achieved in a simple and readable way by providing function swap(values, first, second) as follows:
def swap(values, first, second):
    value1 = values[first]
    value2 = values[second]
    values[first] = value2
    values[second] = value1
Of course, you can also solve this with only three assignments and a temporary variable. Still, I think the previous version is a bit more comprehensible.
def swap(values, first, second):
    tmp = values[first]
    values[first] = values[second]
    values[second] = tmp
In Python, there is the following variant based on a tuple assignment:
def swap_with_tuple(values, first, second):
    values[second], values[first] = values[first], values[second]
HINT: PREFER READABILITY AND COMPREHENSIBILITY

Please keep in mind that readability and understandability are the keys to correctness and maintainability. Besides, this often facilitates testability.

While the helper variable to save one assignment is pretty catchy here, there are definitely more elaborate traceable low-level optimizations in other use cases. They are usually more difficult to read and less comprehensible.

Example 2: Basic Functionality for Arrays

Now let’s write the function find(values, search_for) to search for a value in a one-dimensional array or a list and return the position or -1 for not found:
def find(values, search_for):
    for i, current_value in enumerate(values):
        if current_value == search_for:
            return i
    return -1
This can be solved as a typical search problem with a while loop where the condition is given as a comment at the end of the loop:
def find(values, search_for):
    pos = 0
    while pos < len(values) and not values[pos] == search_for:
        pos += 1
    # i >= len(values) or values[i] == search_for
    return -1 if pos >= len(values) else pos

Please note the following: The Python built-in function len() returns the length of a list, so also for arrays, as long as they are one-dimensional. Alternatively, NumPy provides the attribute size on the array. For two-dimensional arrays, the values differ, but more about this later.

Pythonic variant with enumerate() Indexed accesses can hardly be avoided when working on array elements and are often quite intuitive. However, such accesses via the index in combination with range(len(values)) do not necessarily correspond to good style in Python. Sometimes there are more elegant ways, like the following one with enumerate():
def find_with_enumerate(values, search_for):
    for i, value in enumerate(values):
        if value == search_for:
            return i
    return -1

Example 3: Remove Duplicates

The following shows a sorted array of positive numbers, but with duplicate values. Removing the duplicates should provide the following result:
 [1, 2, 2, 3, 3, 3, 4, 4, 4, 4] => [1, 2, 3, 4]
JOB INTERVIEW TIPS: PROBLEM-SOLVING STRATEGIES
For assignments like this, you should always ask a few questions to clarify the context and gain a better understanding. For this example, possible questions include the following:
  1. 1.

    Is it necessary to keep the order/sorting of the numbers?

     
  2. 2.

    May a new array be created or must the actions be processed inplace—within the original array?

     
  3. 3.
    For inplace there are further questions:
    1. a.

      What exactly should happen when removing/deleting?

       
    2. b.

      What value represents no entry?

       
     

Solution 1 for Example 3: New array and sorted input Suppose you are to return a new array as a result when eliminating duplicates.

Maybe when you implement it you get the idea to remove the duplicates simply by refilling in a set. However, this does not guarantee that the original order is preserved. To be on the safe side, it is recommended to use a dictionary to ensure that the insertion order of the keys is preserved. Using fromkeys(), a dictionary is created based on the passed list and duplicate keys are automatically removed. As a second step, you prepare a new array based on the keys. This procedure can be implemented as follows:
def remove_duplicates_new_array(sorted_numbers):
    # order may change
    # unique_values = list(set(sorted_numbers))
    # stable order
    unique_values = list(dict.fromkeys(sorted_numbers))
    return np.array(unique_values)
Solution 2 for Example 3: Unsorted/arbitrary numbers The previous task of removing duplicates in sorted numbers was easy to solve with Python on-board facilities. But how should you proceed with non-sorted data, assuming that the original order has to be maintained? Specifically, the result shown on the right should then result from the left sequence of values.
[1, 4, 4, 2, 2, 3, 4, 3, 4] => [1, 4, 2, 3]
Interestingly, a set would not make sense as a result data structure in this case because it would mess up the original order. If you think for a moment, ask an experienced colleague, or browse through a good book, you might discover that you can use a set as an auxiliary data structure for already discovered numbers. To store the result, you use a list. This variant (combination) works just as well with already sorted data.
def remove_duplicates_stable(numbers):
    return np.array(collect_unique_values_stable(numbers))
def collect_unique_values_stable(numbers):
    result = []
    unique_values = set()
    for value in numbers:
        if value not in unique_values:
            unique_values.add(value)
            result.append(value)
    return result

This example illustrates the advantages of programming small functionalities that are self-contained and follow the SRP (Single Responsibility Principle). Even more: Keeping public methods understandable and moving details to (preferably private) helper methods often allows you to keep subsequent changes as local as possible. By the way, I discuss the SRP in detail in my book Der Weg zum Java-Profi [Ind20].

As a special feature since Python 3.6, the order of the keys when creating a dictionary with fromkeys() corresponds to the later iteration order, so the collection can be written even shorter as follows:
def collect_unique_values_stable_shorter(numbers):
    return list(dict.fromkeys(numbers))
Solution 3 for Example 3: Inplace Given this sorted array again
sortedNumbers = [1, 2, 2, 3, 3, 3, 4, 4, 4, 4]
all duplicates are to be removed, but this time you’re not allowed to create a new array. This implementation is a little bit more difficult. The algorithm is as follows: Run through the array, check for each element, whether it already exists, and whether it is a duplicate. This check can be performed by comparing the current element with its predecessor. This simplification is possible because sorting exists; without it, it would be much more complicated to solve. You start the processing at the frontmost position and proceed step by step. Thereby you collect all numbers without duplicates on the left side of the array. To know where to read or write in the array, you use position pointers named read_pos and write_pos, respectively. If you find a duplicate number, the read pointer moves on and the write pointer stays in place.
def remove_duplicates_inplace_first_try(sorted_numbers):
    prev_value = sorted_numbers[0]
    write_pos = 1
    read_pos = 1
    while read_pos < len(sorted_numbers):
        current_value = sorted_numbers[read_pos]
        if prev_value != current_value:
            sorted_numbers[write_pos] = current_value
            write_pos += 1
            prev_value = current_value
        read_pos += 1
Let’s call this function once:
>>> sorted_numbers = np.array([1, 2, 2, 3, 3, 3, 4, 4, 4, 4])
>>> remove_duplicates_inplace_first_try(sorted_numbers)
>>> print(sorted_numbers)
This variant is functionally correct, but the result is confusing:
[1 2 3 4 3 3 4 4 4 4]
This is because you are working inplace here. There is no hint how the result can be separated, up to where the values are valid and where the invalid, removed values start. Accordingly, two things are recommended:
  1. 1.

    You should return the length of the valid range.

     
  2. 2.

    You should delete the following positions with a special value, like -1 for primitive number types or for reference types often None. This value must not be part of the value set. Otherwise, irritations and inconsistencies are inevitable.

     
The following modification solves both issues and also uses a for loop, which makes everything a bit more elegant and shorter:
def remove_duplicates_inplace_improved(sorted_numbers):
    write_index = 1
    for i in range(1, len(sorted_numbers)):
        current_value = sorted_numbers[i]
        prev_value = sorted_numbers[write_index - 1]
        if prev_value != current_value:
            sorted_numbers[write_index] = current_value
            write_index += 1
    # delete the positions that are no longer needed
    for i in range(write_index, len(sorted_numbers)):
        sorted_numbers[i] = -1
    return write_index
An invocation of this function returns the length of the valid range (additionally, after the last valid index in the modified array, all values are set to -1). Let’s check this by running the following lines:
>>> sorted_numbers = np.array([1, 2, 2, 3, 3, 3, 4, 4, 4, 4])
>>> pos = remove_duplicates_inplace_improved(sorted_numbers)
>>> print("pos:", pos, " / values:", sorted_numbers)
pos: 4 / values: [ 1 2 3 4 -1 -1 -1 -1 -1 -1]

Interim conclusion The example illustrates several problematic issues. First, that it is often more complex to work inplace—that is, without creating new arrays, but directly within the original array. Second, to handle changes when values remain in the array but are no longer part of the result, you can either return a counter or erase the values with a neutral, special value. However, it is often more understandable and therefore recommended to use the variants shown, which create a new array.

JOB INTERVIEW TIPS: ALTERNATIVE WAYS OF LOOKING AT THINGS
As simple as the assignment may have sounded at first, it does hold some potential for different approaches and solution strategies. When removing duplicates, you could also come up with the idea of replacing elements by no entry—for object references the value None:
["Tim", "Tim", "Jim", "Tom", "Jim", "Tom"]
=>
["Tim", None, "Jim", "Tom", None, None]
For a non-sorted array, it is also possible to retain the values in the order of their original occurrence:
[1, 2, 2, 4, 4, 3, 3, 3, 2, 2, 3, 1] => [1, 2, 4, 3]
Alternatively, it is possible to remove only consecutive duplicates at a time:
[1, 2, 2, 4, 4, 3, 3, 3, 2, 2, 3, 1] => [1, 2, 4, 3, 2, 3, 1]

As you can see, there is more to consider, even for apparently simple tasks. This is why requirements engineering and the correct coverage of requirements are a real challenge.

Example 4: Rotation by One or More Positions

Let’s look at another problem, namely rotating an array by n positions to the left or to the right, where the elements are then to be shifted cyclically at the beginning or the end, respectively, as visualized below, where the middle array is the starting point:

The algorithm for a rotation by one element to the right is simple: Remember the last element and then repeatedly copy the element that is one ahead in the direction of rotation to the one behind it. Finally, the cached last element is inserted at the foremost position.

Please note that the following two functions work inplace (on the passed array) so they do not return a value:
def rotate_right(values):
    if len(values) < 2:
        return
    end_pos = len(values) - 1
    temp = values[end_pos]
    for i in range(end_pos, 0, -1):
        values[i] = values[i - 1]
    values[0] = temp
The rotation to the left works analogously:
def rotate_left(values):
    if len(values) < 2:
        return
    end_pos = len(values) - 1
    temp = values[0]
    for i in range(end_pos):
        values[i] = values[i + 1]
    values[end_pos] = temp
Let’s try the whole thing out in the Python command line:
>>> numbers = np.array([1, 2, 3, 4])
>>> rotate_right(numbers)
>>> numbers
array([4, 1, 2, 3])
>>>
>>> numbers = np.array([1, 2, 3, 4])
>>> rotate_left(numbers)
>>> print(numbers)
[2 3 4 1]

In case you are wondering about the different console outputs, it should be noted that there is a difference between the formatting with __repr__() and __str__(). In the first case, you get the type info and then the values are comma-separated as output. In the second case, the output is the same as the standard of lists.

Rotation around n positions (simple) An obvious extension is to rotate by a certain number of positions. This can be solved using brute force by calling the just-developed functionality n times:
def rotate_right_by_n_simple(values, n):
    for i in range(n):
        rotate_right(values)

This solution is acceptable in principle, although not performant due to the frequent copy actions. How can it be more efficient?

HINT: OPTIMIZATION OF LARGE VALUES FOR n

There is one more small feature to consider. Namely, if n is larger than the length of the array, you don’t have to rotate all the time; you can limit this to what is actually needed by using the modulo operation i < n % len(values).

Rotation around n positions (tricky) Alternatively, imagine that n positions are added to the original array. This is accomplished by using an independent buffer that caches the last n elements. It is implemented in the function fill_temp_with_last_n(). This first creates a suitably sized array and puts the last n values there. Then you copy the values as before, but with an offset of n. Finally, you just need to copy the values back from the buffer using copy_temp_buffer_to_start().
def rotate_right_by_n(values, n):
    adjusted_n = n % len(values)
    temp_buffer = fill_temp_with_last_n(values, adjusted_n)
    # copy n positions to the right
    for i in range(len(values) - 1, adjusted_n - 1, -1):
        values[i] = values[i - adjusted_n]
    copy_temp_buffer_to_start(temp_buffer, values)
    return values
def fill_temp_with_last_n(values, n):
    temp_buffer = np.arange(n)
    for i in range (n):
        temp_buffer[i] = values[len(values) - n + i]
    return temp_buffer
def copy_temp_buffer_to_start(temp_buffer, values):
    for i in range(len(temp_buffer)):
        values[i] = temp_buffer[i]

Here’s another hint: The function just presented for rotation can be suboptimal in terms of memory, especially if the value of n is very large and the array itself is also huge, but for our examples, this does not matter. Interestingly, the simple version would then be better in terms of memory, although probably rather slow due to the frequent copy actions.

6.1.2 Multidimensional Arrays

In this section, I will briefly discuss multidimensional arrays . Because it is more common in practice and easy to imagine visually, I will just discuss two-dimensional arrays.2

Using a two-dimensional rectangular array, you can model a playfield, such as a Sudoku puzzle or a landscape represented by characters. For a better understanding and an introduction, let’s consider an example. Suppose # represents a boundary wall, $ stands for an item to be collected, P stands for the player, and X stands for the exit from a level. These characters are used to describe a playfield as follows:
################
##  P         ##
####   $ X  ####
###### $  ######
################

In Python, a two-dimensional array can be used for processing, which you can construct based on strings converted to lists as follows:

def main():
    world = np.array([list("################"),
                      list("##  P         ##"),
                      list("####   $ X  ####"),
                      list("###### $  ######"),
                      list("################")])
    print_array(world)
def print_array(values):
    max_y, max_x = get_dimension(values)
    for y in range(max_y):
        for x in range(max_x):
            value = values[y][x]
            print(value, end=" ")
        print()
def get_dimension(values):
    if isinstance(values, list):
        return len(values), len(values[0])
    if isinstance(values, np.ndarray):
        return values.shape
    raise ValueError("unsupported type", type(values))

In the code above, you can see the helper function get_dimension(values) to determine the dimensions for both lists and NumPy arrays. This allows using one or the other without worrying. See subsection 6.1.4 for a broader explanation.

Let’s run the module TWO_DIM_ARRAY_WORLD_EXAMPLE.PY to see the output functionality in action. In the following, I will refer to similar things from time to time. Besides debugging, the console output is quite helpful, especially for multidimensional arrays.
# # # # # # # # # # # # # # # #
# #     P                   # #
# # # #       $ X       # # # #
# # # # # #   $     # # # # # #
# # # # # # # # # # # # # # # #
Accessing values There are two variants of how to specify the coordinates when accessing: one is [x][y] and the other is [y][x] if you think in a more line-oriented way. Between different developers, this can lead to misunderstandings and discussions. A small remedy can be achieved if you write an access function, like get_at(values, x, y), and consider the respective preference there. I will use this access function in the introduction and later switch over to direct array accesses:
def get_at(values, x, y) :
    return values[y][x];

Introductory Example

Your task is to rotate an array by 90 degrees to the left or right. Let’s take a look at this for two rotations to the right:
1111       4321       4444
2222  =>   4321  =>   3333
3333       4321       2222
4444       4321       1111
Let’s try to formalize the procedure a bit. The easiest way to implement the rotation is to create a new array and then populate it appropriately. For the determination of the formulas, let’s use concrete example data, which facilitates the understanding (xn and yn stand for the new coordinates; in the following, the rotation to the left and the rotation to the right is shown on the left/right):
            x  0123
           y   ----
           0   ABCD
           1   EFGH
  xn  01                 xn  01
yn    --               yn    --
 0    DH                0    EA
 1    CG                1    FB
 2    BF                2    GC
 3    AE                3    HD

You see that a 4 × 2 array turns into a 2 × 4 array.

The rotation is based on the following calculation rules, where max_x and max_y are the respective maximum coordinates:
                Orig  ->  new_x      new_y
-----------------------------------------------------
rotate_left:    (x,y) ->  y          max_x - x
rotate_right:   (x,y) ->  max_y - y  x
You proceed to the implementation with this knowledge: You first create a suitably large array by calling np.empty() and traverse the original array line by line and then position by position. Based on the formulas above, the rotation can be implemented as follows:
class RotationDirection(Enum):
    LEFT_90 = auto()
    RIGHT_90 = auto()
def rotate(values, dir):
    orig_length_y, orig_length_x = values.shape
    rotated_array = np.empty((orig_length_x, orig_length_y), values.dtype)
    for y in range(orig_length_y):
        for x in range(orig_length_x):
            max_x = orig_length_x - 1
            max_y = orig_length_y - 1
            orig_value = values[y][x]
            if dir == RotationDirection.LEFT_90:
                new_x = y
                new_y = max_x - x
                rotated_array[new_y][new_x] = orig_value
            if dir == RotationDirection.RIGHT_90:
                new_x = max_y - y
                new_y = x
                rotated_array[new_y][new_x] = orig_value
    return rotated_array
Let’s take a look at the operations in the Python command line:
def main():
    letters = np.array([["A", "B", "C", "D"],
                        ["E", "F", "G", "H"]])
    left_rotated = rotate(letters, RotationDirection.LEFT_90)
    print(left_rotated)
    right_rotated = rotate(letters, RotationDirection.RIGHT_90)
    print(right_rotated)
Finally, the call to print() shows the arrays rotated by 90 degrees to the left and to the right:
[['D' 'H']
 ['C' 'G']
 ['B' 'F']
 ['A' 'E']]
[['E' 'A']
 ['F' 'B']
 ['G' 'C']
 ['H' 'D']]

Modeling Directions

You will encounter directions in a variety of use cases. They can, of course, be modeled simply using an enumeration. In the context of two-dimensional arrays, it is extremely convenient and contributes significantly to readability and comprehensibility to define all essential cardinal directions in the enumeration and, moreover, offsets in x- and y- directions. For better manageability of the delta values, I offer a to_dx_dy() function:
class Direction(Enum):
    N = (0, -1)
    NE = (1, -1)
    E = (1, 0)
    SE = (1, 1)
    S = (0, 1)
    SW = (-1, 1)
    W = (-1, 0)
    NW = (-1, -1)
    def to_dx_dy(self):
        return self.value
    @classmethod
    def provide_random_direction(cls):
        random_index = randrange(len(list(Direction)))
        return list(Direction)[random_index]
HINT: RANDOM NUMBERS
In the example, you see the function randrange(), which generates random numbers in the range 0 to the specified boundary exclusive. An alternative is random.randint(). To get a random number greater than or equal to 0.0 and less than 1.0, use the call random.random(). For example, if you want to simulate the numbers of a dice, you could implement this as follows:
dice_eyes = random.randint(1, 6)

Example: Random traversal To go a little deeper on processing with directions, let’s develop a traversal for a playfield. Whenever you hit array boundaries, you randomly choose a new direction not equal to the old one:

def main():
    world = np.array([list("ABCDEF"),
                      list("GHIJKL"),
                      list("MNOPQR"),
                      list("abcdef"),
                      list("ghijkl")])
    dir = Direction.provide_random_direction()
    print("Direction:", dir.name)
    pos_x = 0
    pos_y = 0
    steps = 0
    while steps < 25:
        print(world[pos_y][pos_x], " ", end="")
        dx, dy = dir.to_dx_dy()
        if not is_on_board(world, pos_x + dx, pos_y + dy):
            dir = select_new_dir(world, dir, pos_x, pos_y)
            dx, dy = dir.to_dx_dy()
            print(" New Direction:", dir.name)
        pos_x += dx
        pos_y += dy
        steps += 1
def select_new_dir(world, dir, pos_x, pos_y):
    old_dir = dir
    while True:
        dir = Direction.provide_random_direction()
        dx, dy = dir.to_dx_dy()
        if old_dir != dir and is_on_board(world, pos_x + dx, pos_y + dy):
            break
    return dir
In this assignment, you immediately get in touch with another useful function named is_on_board(). Its task is to check whether a passed x-y value is valid for the array, here assuming that the array is rectangular.3
def is_on_board(values, next_pos_x, next_pos_y):
    max_y, max_x = values.shape
    return 0 <= next_pos_x < max_x and 0 <= next_pos_y < max_y
If you start the module RANDOM_TRAVERSAL_DIRECTION_EXAMPLE.PY, you will get output like the following, which shows the direction changes very well. The output is limited by the maximum number of 25 steps. Therefore, only 3 letters are found at the end.
Direction: SE
A H O d k
New Direction: N
e Q K E
New Direction: SW
J O b g
New Direction: N
a M G A
New Direction: E
B C D E F
New Direction: SW
K P c
HINT: VARIATION WITH BUFFER FIELDS AT THE BORDER
Especially for two-dimensional arrays and accesses to adjacent cells, it may be useful to add an unused element at each border field to avoid special cases, indicated below with a X:
XXXXXXXXX
X       X
X       X
X       X
XXXXXXXXX

Using this trick, you always have eight adjacent cells. This helps to avoid special treatments in your programs. This is also true, for example, when walking through the array. Instead of checking for the array boundaries, you can restrict yourself to checking if you reach a boundary field. Sometimes it is handy to use a neutral element, such as the value 0, since this does not affect computations.

6.1.3 Typical Errors

Not only when accessing arrays, but especially there, you find a multiplicity of potential sources of errors, in particular, the following:

  • Off-by-one: Sometimes you are off by one element when accessing because, for example, the index calculation contains an error, such as adding or subtracting 1 to correct the index or comparing positions with <, <=, >, or >=.

  • Array bounds: Similarly, the bounds of the array are sometimes inadvertently disregarded, for example, by incorrect use of <, <= or >, >= when comparing length or lower or upper bounds.4

  • Dimensions: As mentioned, how x and y are represented depends on the chosen flavor. This quickly causes x and y to be interchanged for two-dimensional arrays.

  • Rectangular property: Although an n × m array is assumed to be rectangular, this need not be the case in Python when using nested lists. You can specify a different length for each new row, but many of the examples below use rectangular arrays,5 especially because they are only supported by NumPy. The reason lies in the arrangement in memory for maximum performance.

  • Neutral element: What represents no value. Is it -1 or None? How do you deal with this if these are possible values?

6.1.4 Special Features

I would like to point out something extraordinary. Practically, almost all of our developed program modules can be used for NumPy arrays and lists without changing much in the algorithmic part of the functions. Often, all that is needed is the determination of the sizes shown below. This is a significant advantage in contrast to algorithms in, say, Java and C++, which must be developed specifically for lists and other types.

For many algorithms for two-dimensional arrays, you can use the function get_dimension(values) to determine the dimensions for both lists and NumPy arrays. A few examples require some manual work but rarely a completely new implementation.
def get_dimension(values):
    if isinstance(values, list):
        return len(values), len(values[0])
    if isinstance(values, np.ndarray):
        return values.shape
    raise ValueError("unsupported type", type(values))
For nested lists, it returns the number of lines and the length of the first line. This corresponds exactly to the dimensions that can be obtained from NumPy via the shape attribute as a tuple:
nested_lists = [[0, 1, 2, 3],
                [4, 5, 6, 7],
                [8, 9, 10, 10]]
nested_lists_array = np.array(nested_lists)
print(get_dimension(nested_lists))
print(get_dimension(nested_lists_array))
This results in the following output:
(3, 4)
(3, 4)

Special Treatment for Generalizations

Sometimes you want to apply functionalities not only for special types but in general. In doing so, you occasionally need to initialize arrays with an empty value or query whether an array is empty. You will look at this in more detail in the solution part of exercise 6, where you want to be able to use arrays with letters in addition to arrays with numbers to model a playfield. An empty field is then indicated by, for example, the numerical value 0, a single space character, or an empty string. You could formulate this general-purpose check as function is_empty_cell(values2dim, x, y) as follows:
def is_empty_cell(values2dim, x, y):
    return is_empty(values2dim[y][x])
def is_empty(value):
    if type(value) is str:
        return value == " " or len(value) == 0
    return value == 0

6.1.5 Recapitulation: NumPy

So far, you have used NumPy in various examples without it being remarkably different in handling than lists. This is a big plus. Nevertheless, I would like to introduce a few things explicitly and point out others.

What is NumPy? NumPy stands for Numerical Python and is a module for processing arrays. Besides basic functionalities, there are mathematical extensions for linear algebra and matrices.

Creating NumPy Arrays Based on Lists

Let’s take a quick look at how easy it is to create a corresponding NumPy array from a list:
numbers = [1, 2, 3, 4, 5, 6, 7]
numbers_array = np.array(numbers)
firstprimes = [2, 3, 5, 7, 11, 13, 17]
firstprimes_array = np.array(firstprimes)
print(numbers_array)
print(firstprimes_array)
You receive the following output:
[1 2 3 4 5 6 7]
[ 2  3  5  7 11 13 17]
The whole thing also works without problems with two-dimensional nested lists:
twodim = np.array([["A1", "A2"],
                   ["B1", "B2"],
                   ["C1", "C2"]])
print(twodim)
print(len(twodim))   # 3
print(twodim.size)   # 6
print(twodim.shape)  # (3, 2)
You get the following output of the array (lengths are not shown here):
[['A1' 'A2']
 ['B1' 'B2']
 ['C1' 'C2']]

Creating NumPy Arrays with Particular Values

Sometimes you want to preinitialize arrays with a special value; for numbers this is often the value 0 or the 1. NumPy offers specific functions for this purpose:

  • zeros()

  • ones()

  • empty()

Let’s call these functions to create arrays. Note that the first value corresponds to the number of rows and the second one corresponds to the number of columns. Additionally, you can optionally specify a data type.
array_with_zeros = np.zeros((2, 4), dtype='int')
print(array_with_zeros)
array_with_ones = np.ones((5, 10))
print(array_with_ones)
empty_strings_array = np.empty((3, 3), dtype="str")
print(empty_strings_array)
This leads to the following output, which illustrates that by default (here for the ones) float is chosen as the data type:
[[0 0 0 0]
 [0 0 0 0]]
[[1. 1. 1. 1. 1. 1. 1. 1. 1. 1.]
 [1. 1. 1. 1. 1. 1. 1. 1. 1. 1.]
 [1. 1. 1. 1. 1. 1. 1. 1. 1. 1.]
 [1. 1. 1. 1. 1. 1. 1. 1. 1. 1.]
 [1. 1. 1. 1. 1. 1. 1. 1. 1. 1.]]
[['' '' '']
 ['' '' '']
 ['' '' '']]
Such initializations can also be achieved with Python on-board tools as follows but the NumPy variant feels more comprehensible for me:
zeros_with_lists = [[0 for x in range(4)] for y in range(2)]
print(zeros_with_lists)
ones_with_lists = [[1 for x in range(10)] for y in range(5)]
print(ones_with_lists)
empty_string_with_list = [["" for x in range(3)] for y in range(3)]
print(empty_string_with_list)
ATTENTION: FAULTY VARIANT WITH LIST COMPREHENSION
Please note the following pitfall: You might like to create something similar to the above using list comprehensions:
width = 10
height = 5
# generates non-independent references board = [[0] * width] * height print(board)
# Attention: modification happens in all lines! board[1][1] = 1
print(board)

The lists created in this way are not independent of each other, and changes have effects on the other lines.

Other Functionalities of NumPy Arrays

Previously I indicated that NumPy offers some mathematical functionalities out of the box. But not only that. There are various others, which you can explore in detail in https://numpy.org/doc/stable/reference/routines.array-manipulation.html. As an example, I’ll demonstrate the vertical and horizontal flipping of the contents of an array, which you are supposed to rebuild by hand in exercise 2.

Let’s look at how this works using two arrays, where the 1 stands for horizontal and 0 for vertical:
import numpy as np
numbers = np.array([[1, 2, 3, 4],
                    [1, 2, 3, 4],
                    [1, 2, 3, 4]])
print(np.flip(numbers, 1))
numbers2 = np.array([[1, 1, 1, 1],
                     [2, 2, 2, 2],
                     [3, 3, 3, 3]])
print(np.flip(numbers2, 0))
This results in the following output:
[[4 3 2 1]
 [4 3 2 1]
 [4 3 2 1]]
 [[3 3 3 3]
 [2 2 2 2]
 [1 1 1 1]]

Advantages of NumPy

As is well known, lists in Python are very convenient and provide an ordered and changeable sequence of values. The values stored can be of different types (heterogeneous) or contain only the same types (homogeneous). Multidimensional structures are possible by nesting lists. NumPy allows only homogeneous value assignments, which is often an advantage rather than a disadvantage.

What are the indisputable advantages of using NumPy instead of the built-in lists?

  • NumPy arrays fit seamlessly and are easy to use.

  • NumPy arrays use (slightly) less memory.

  • NumPy arrays are (much) faster than lists for various use cases.

However, the last point only applies when processing enormous amounts of data, especially when performing mathematical operations such as matrix multiplication. Normal array accesses are sometimes even slower than indexed list accesses. I will show this with an example later.

Memory Consumption

To compare the memory consumption of lists and NumPy arrays, I created a list and an array with 100,000 elements each. To determine the used memory, I used the getsizeof() functionality from the sys module.
import numpy as np
import sys
numbers = [i for i in range(100_000)]
print("Size of each element:", sys.getsizeof(numbers[0]))
print("Size of the list:", sys.getsizeof(numbers))
numbers_array = np.arange(100_000)
print("Size of each element:", numbers_array.itemsize)
print("Size of the Numpy array:", sys.getsizeof(numbers_array))
The following output occurred:
Size of each element: 24
Size of the list: 824456
Size of each element: 8
Size of the Numpy array: 800096

You can see that (on my machine6) each element in a list occupied 24 bytes, but in NumPy, only 8 bytes. With NumPy the total size resulted from the number of elements, their size in bytes, and the number of bytes for the NumPy array as management:

100.000 ∗ 8 + 96 = 800.096

With lists, the output confused me. According to the number for a single element

100.000 ∗ 24 + x = 2.400.000

should be occupied, but surprisingly I got around 824.000.

Performance Comparison

Finally, let’s compare lists and arrays concerning their performance. I started with the basic functionality of indexed access to recognize that lists have a slight advantage here. However, when it comes to actions on all elements of an array, particularly complex mathematical operations like matrix multiplication, the picture reversed massively. NumPy clearly showed its strengths. Let’s have a closer look at this through examples in more detail.

Index based accesses For indexed accesses, NumPy was a bit slower than the built-in lists. This can be observed in the first example, the flipping of the content by single assignments:
for size in (100, 1000, 10000, 100000, 1_000_000):
    print("performing idx assign for ", size, "elements")
    orig_values = range(size)
    array = np.asarray(orig_values)
    result_list = list(orig_values)
    result_array = array[:]
    start = time.process_time()
    for i in range(size):
        result_list[i] = orig_values[size - 1 - i]
    end = time.process_time()
    print("list idx assign took %.2f ms" % ((end - start) * 1000))
    start = time.process_time()
    for i in range(size):
        result_array[i] = array[size - 1 - i]
    end = time.process_time()
    print("array idx assign took %.2f ms" % ((end - start) * 1000))
Here, indexed reads and writes are especially in demand. I looked at the outputs and saw that in this case, the lists were about 20% faster on my iMac:
performing idx assign for all 100 elements
list idx assign took 0.02 ms
array idx assign took 0.03 ms
performing idx assign for all 1000 elements
list idx assign took 0.26 ms
array idx assign took 0.33 ms
performing idx assign for all 10000 elements
list idx assign took 2.75 ms
array idx assign took 3.44 ms
performing idx assign for all 100000 elements
list idx assign took 27.81 ms
array idx assign took 35.23 ms
performing idx assign for all 1000000 elements
list idx assign took 273.67 ms
array idx assign took 354.75 ms
I modified it slightly and added a constant value to each element in the data container as an action. In that case, NumPy provided a nice shorthand and was a bit faster from about 1.000 elements. The more elements I managed, the clearer the differences for these actions.
result_list = [i + 5 for i in range(size)]
result_array = array1 + 5
Matrix multiplication Let’s look at one example where performance improvements are noticeable (more accurately, drastic) when using NumPy: the common matrix multiplication. This consists of row-by-row and then element-by-element multiplication (the mathematical details are not relevant here, as I only want to compare performance here):
def python_implementation(arr1, arr2):
    result = [[0 for _ in range(len(arr1))] for _ in range(len(arr2[0]))]
    for row in range(len(arr1)):
        for x1_y2 in range(len(arr2[0])):
            for y2 in range(len(arr2)):
                result[row][x1_y2] += arr1[row][y2] * arr2[y2][x1_y2]
    return result
def numpy_implementation(arr1, arr2):
    return np.array(arr1).dot(arr2)
I ran the two variants with the following source code snippet once:
max_x = 100
max_y = 50
arr1 = [[random.randrange(1, 100) for _ in range(max_x)] for _ in range(max_y)]
arr2 = [[random.randrange(1, 100) for _ in range(max_y)] for _ in range(max_x)]
start = time.process_time()
python_implementation(arr1, arr2)
end = time.process_time()
print("list perform dot product took %.2f ms" % ((end - start) * 1000))
start = time.process_time()
numpy_implementation(arr1, arr2)
end = time.process_time()
print("array perform dot product took %.2f ms" % ((end - start) * 1000))
Thus, I obtained the following output, which shows the clear speed advantages of NumPy by a factor of about 50–60%:
list perform dot product took 86.52 ms
array perform dot product took 1.85 ms

6.2 Exercises

6.2.1 Exercise 1: Even Before Odd Numbers (★★✩✩✩)

Write function order_even_before_odd(numbers). This is supposed to rearrange a given array or a list of int values so that the even numbers appear first, followed by the odd numbers. The order within the even and odd numbers is not of relevance.

Examples

Input

Result

[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

[2, 4, 6, 8, 10, 3, 7, 1, 9, 5]

[2, 4, 6, 1, 8]

[2, 4, 6, 8, 1]

[2, 4, 6, 8, 1]

[2, 4, 6, 8, 1]

6.2.2 Exercise 2: Flip (★★✩✩✩)

Write generic functions for flipping a two-dimensional array horizontally with flip_horizontally(values2dim) and vertically with flip_vertically(values2dim). The array should be rectangular, so no line should be longer than another.

Examples

The following illustrates how this functionality should work:
flip_horizontally()     flip_vertically()
-------------------     -----------------
123      321           1144      3366
456  =>  654           2255  =>  2255
789      987           3366      1144

6.2.3 Exercise 3: Palindrome (★★✩✩✩)

Write function is_palindrome(values) that checks an array of strings for whether its values form a palindrome.

Examples

Input

Result

[“One”, “Test”, “ – ”, “Test”, “One”]

True

[“Max”, “Mike”, “Mike”, “Max”]

True

[“Tim”, “Tom”, “Mike”, “Max”]

False

6.2.4 Exercise 4: Inplace Rotate (★★★✩✩)

Exercise 4a: Iterative (★★★✩✩)

In the introductory section, I showed how to rotate arrays. Now try this inplace without creating a new array. Your task is to rotate a two-dimensional, square-shaped array by 90 degrees clockwise. Write generic function rotate_inplace(values2dim) that iteratively implements this.

Example

For a 6 × 6 array, this is visualized below:
1 2 3 4 5 6      F G H I J 1
J K L M N 7      E T U V K 2
I V W X O 8  =>  D S Z W L 3
H U Z Y P 9      C R Y X M 4
G T S R Q 0      B Q P O N 5
F E D C B A      A 0 9 8 7 6

Exercise 4b: Recursive (★★★✩✩)

Write recursive function rotate_inplace_recursive(values2dim) that implements the desired 90-degree clockwise rotation.

6.2.5 Exercise 5: Jewels Board Init (★★★✩✩)

Exercise 5a: Initialize (★★★✩✩)

Initialize a two-dimensional rectangular array with random-based numbers representing various types of diamonds or jewels as numerical values. The constraint is that initially there must not be three diamonds of the same type placed horizontally or vertically in direct sequence. Write function init_jewels_board(width, height, num_of_colors) to generate a valid array of the given size and quantity of different types of diamonds.

Example

A random distribution of diamonds represented by digits may look like this for four different colors and shapes:
2 3 3 4 4 3 2
1 3 3 1 3 4 4
4 1 4 3 3 1 3
2 2 1 1 2 3 2
3 2 4 4 3 3 4
To illustrate this, Figure 6-1 shows another example.
Figure 6-1

Graphical representation of a Jewels board

Bonus: Diagonal Check (★★★✩✩) Add a check for diagonals. This should make the constellation from the example invalid, among other things, because of the diagonals marked in bold with the number 3 at the bottom right.

Exercise 5b: Validity Check (★★★✩✩)

In this subtask, you want to validate an existing playfield. As a challenge, a list of violations must be returned. Implement function check_board_validity(board2dim) for a rectangular array.

Example

To try out the validity check, use the playfield from the introduction, specially marked here:
values_with_errors = [[2, 3, 3, 4, 4, 3, 2],
                      [1, 3, 3, 1, 3, 4, 4],
                      [4, 1, 4, 3, 3, 1, 3],
                      [2, 2, 1, 1, 2, 3, 2],
                      [3, 2, 4, 4, 3, 3, 4]]
This should produce the following errors due to its diagonals:
['Invalid at x=3 y=2 hor=False, ver=False, dia=True',
 'Invalid at x=2 y=3 hor=False, ver=False, dia=True',
 'Invalid at x=4 y=4 hor=False, ver=False, dia=True']

6.2.6 Exercise 6: Jewels Board Erase Diamonds (★★★★✩)

The challenge is to delete all chains of three or more horizontally, vertically, or diagonally connected diamonds from the rectangular playfield and subsequently to fill the resulting empty spaces with the diamonds lying above them, (i.e., roughly in the same way gravity works in nature). The following is an example of how the erasing and then dropping is repeated several times until no more change occurs (spaces are shown as _ for better visibility):
Iteration 1:
1 1 1 2 4 4 3  erase  _ _ _ _ 4 4 _  fall down  _ _ _ _ _ _ _
1 2 3 4 2 4 3   =>    1 2 3 4 _ 4 _      =>     1 2 3 4 4 4 _
2 3 3 1 2 2 3         2 3 3 1 2 _ _             2 3 3 1 2 4 _
Iteration 2:
_ _ _ _ _ _ _  erase  _ _ _ _ _ _ _  fall down  _ _ _ _ _ _ _
1 2 3 4 4 4 _   =>    1 2 3 _ _ _ _      =>     1 2 3 _ _ _ _
2 3 3 1 2 4 _         2 3 3 1 2 4 _             2 3 3 1 2 4 _

Exercise 6a: Erase (★★★★✩)

Write function erase_chains(values2dim) that erases all rows of three or more contiguous diamonds in horizontal, vertical, and diagonal orientations from a rectangular playfield array.

Examples

An invocation of the method transforms the output array given on the left into the result shown on the right:
All chains without overlap        Special case: overlaps
1 2 3 3 3 4      0 0 0 0 0 0      1 1 1 2      0 0 0 2
1 3 2 4 2 4      0 3 0 4 2 0      1 1 3 4  =>  0 0 3 4
1 2 4 2 4 4  =>  0 0 4 0 4 0      1 2 1 3      0 2 0 3
1 2 3 5 5 5      0 0 3 0 0 0
1 2 1 3 4 4      0 0 1 3 4 4

Exercise 6b: Falling Down (★★★✩✩)

Write function fall_down(values2dim) working inplace that drops the diamonds from top to bottom, provided there is a space below their position.

Example

An invocation of the method transforms the output array given on the left into the result shown on the right:
0 1 3 3 0 0      0 0 0 0 0 0
0 1 0 0 0 0      0 0 0 0 0 0
0 0 3 3 0 0  =>  0 0 3 3 0 0
0 0 0 3 3 4      0 1 3 3 0 0
0 0 3 0 0 0      0 1 3 3 3 4

6.2.7 Exercise 7: Spiral Traversal (★★★★✩)

Write generic method spiral_traversal(values2dim) that traverses a two-dimensional rectangular array (or a nested list) in the form of a spiral and prepares it as a list. The start is in the upper left corner. First the outer layer is traversed and then the next inner layer.

Example

An example is shown in Figure 6-2.
Figure 6-2

Basic procedure for the spiral traversal

For the following two arrays, the number or letter sequences listed below should be the results of a spiral traversal:
numbers = [[1, 2, 3, 4],
           [12, 13, 14, 5],
           [11, 16, 15, 6],
           [10, 9, 8, 7]]
letterPairs = [["AB", "BC", "CD", "DE"],
               ["JK", "KL", "LM", "EF"],
               ["IJ", "HI", "GH", "FG"]]
=>
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16]
[AB, BC, CD, DE, EF, FG, GH, HI, IJ, JK, KL, LM]

6.2.8 Exercise 8: Add One to an Array as a Number (★★✩✩✩)

Consider an array or a list of numbers representing the digits of a decimal number. Write function add_one(digits) that performs an addition by the value 1 and is only allowed to use arrays as a data structure for the solution.

Examples

Input

Result

[1, 3, 2, 4]

[1, 3, 2, 5]

[1, 4, 8, 9]

[1, 4, 9, 0]

[9, 9, 9, 9]

[1, 0, 0, 0, 0]

6.2.9 Exercise 9: Sudoku Checker (★★★✩✩)

In this challenge, a Sudoku puzzle is examined to see if it is a valid solution. Let’s assume a 9 × 9 array with int values. According to the Sudoku rules, each row and each column must contain all numbers from 1 to 9. Besides, all numbers from 1 to 9 must, in turn, occur in each 3 × 3 subarray. Write function is_sudoku_valid(board)for checking.

Example

The following is a valid solution:

Bonus While it is nice to be able to check a Sudoku board that is completely filled with digits for its validity, it is even better to be able to predict for a board with gaps (i.e., missing digits) whether a valid solution can emerge from it. This is of particular interest if you want to develop an algorithm for solving a Sudoku puzzle.

Example

Based on the example of the valid Sudoku playfield given above, I deleted the digits in random places. This surely results in a valid solution.

6.2.10 Exercise 10: Flood Fill (★★✩✩✩)

Exercise 10a (★★✩✩✩)

Write function flood_fill(values2dim, start_x, start_y) that fills all free fields in an array or a two-dimensional nested list with a specified value.

Example

The following shows the filling process for the character *. The filling starts at a given position, such as the upper left corner. It then continues in all four compass directions until the boundaries of the array or a boundary represented by another character are found.
"     # "      "***# "      "    #    # "      "   #******# "
"      #"      "****#"      "     #    #"      "    #******#"
"#     #"  =>  "#***#"      "#    #   # "  =>  "#   #*****# "
"  # #  "      " #*# "      " # #    #  "      " # #*****#  "
"   #   "      "  #  "      "  #   #    "      "  #*****#   "

Exercise 10b (★★✩✩✩)

Extend the function to fill any pattern passed as a rectangular array. However, spaces are not allowed in the pattern specification.

Example

The following is an impression of how a flood fill with a pattern could look. The pattern consists of several lines with characters:
.|.
-*-
.|.
If the filling starts at the bottom center, you get the following result:
     x        .|..|.x
    # #       -*--#--#
   ### #      .|.###.|#
#  ### #  =>  #|.###.|#
#   #  #      #*--#--*#
 # #  #        #.#|..#
  #  #          #.|.#

6.2.11 Exercise 11: Array Min and Max (★★✩✩✩)

Exercise 11a: Min and Max (★✩✩✩✩)

Write two functions find_min(values) and find_max(values) that search for the minimum and maximum, respectively, of a given non-empty array using a self-implemented search, thus eliminating the usage of built-ins like min() and sort(). :-)

Example

Input

Minimum

Maximum

[2, 3, 4, 5, 6, 7, 8, 9, 1, 10]

1

10

Exercise 11b: Min und Max Pos (★★✩✩✩)

Implement two helper functions find_min_pos(values, start, end) and find-_max_pos(values, start, end) that seek and return the position of the minimum and maximum, respectively. Again, assume a non-empty array and additionally an index range of left and right boundaries. In the case of several identical values for minimum or maximum, the first occurrence should be returned.

To find the minimum and maximum values, respectively, write two functions find_min_by_pos(values, start, end) and find_max_by_pos(values, start, end) that use the helper function.

Examples

Method

Input

Range

Result

Position

find_min_xyz()

[5, 3, 4, 2, 6, 7, 8, 9, 1, 10]

0, 10

1

8

find_min_xyz()

[5, 3, 4, 2, 6, 7, 8, 9, 1, 10]

0, 7

2

3

find_min_xyz()

[5, 3, 4, 2, 6, 7, 8, 9, 1, 10]

2, 7

2

3

find_max_xyz()

[1, 22, 3, 4, 5, 10, 7, 8, 9, 49]

0, 10

49

9

find_max_xyz()

[1, 22, 3, 4, 5, 10, 7, 8, 9, 49]

0, 7

22

1

find_max_xyz()

[1, 22, 3, 4, 5, 10, 7, 8, 9, 49]

2, 7

10

5

6.2.12 Exercise 12: Array Split (★★★✩✩)

Say you have an array (or list) of arbitrary integers. For this task, the data structure is to be reordered so that all values less than a special reference value are placed on the left. All values greater than or equal to the reference value are placed on the right. The ordering within the subranges is not relevant and may vary.

Examples

Input

Reference element

Sample result

[4, 7, 1, 20]

9

[1, 4, 7, 9, 20]

[3, 5, 2]

7

[2, 3, 5, 7]

[2, 14, 10, 1, 11, 12, 3, 4]

7

[2, 1, 3, 4, 7, 14, 10, 11, 12]

[3, 5, 7, 1, 11, 13, 17, 19]

11

[1, 3, 5, 7, 11, 11, 13, 17, 19]

Exercise 12a: Array Split (★★✩✩✩)

Write function array_split(values, reference_element) to implement the functionality described above. In this first part of the exercise, it is allowed to create new data structures, such as lists.

Exercise 12b: Array Split Inplace (★★★✩✩)

Write function array_split_inplace(values, reference_element) that implements the functionality described inside the source array (i.e., inplace). It is explicitly not desirable to create new data structures. To be able to include the reference element in the result, the creation of an array is allowed once for the result. Because this has to be returned, it is permitted to return a value for an inplace function; indeed, it operates only partially inplace here.

Exercise 12c: Array Split Quick Sort Partition (★★★✩✩)

For sorting according to Quick Sort, you need a partitioning functionality similar to the one just developed. However, often the foremost element of the array is used as the reference element.

Based on the two previously developed implementations that use an explicit reference element, your task is to create corresponding alternatives such as the functions array_split_qs(values) and array_split_qs_inplace(values).

Examples

Input

Reference element

Sample result

[9, 4, 7, 1, 20]

9

[1, 4, 7, 9, 20]

[7, 3, 5, 2]

7

[2, 3, 5, 7]

[7, 2, 14, 10, 1, 11, 12, 3, 4]

7

[2, 1, 3, 4, 7, 14, 10, 11, 12]

[11, 3, 5, 7, 1, 11, 13, 17, 19]

11

[1, 3, 5, 7, 11, 11, 13, 17, 19]

6.2.13 Exercise 13: Minesweeper Board (★★★✩✩)

The chances are high that you’ve played Minesweeper in the past. To remind you, it’s a nice little quiz game with a bit of puzzling. What is it about? Bombs are placed face down on a playfield. The player can choose any field on the board. If a field is uncovered, it shows a number. This indicates how many bombs are hidden in the neighboring fields. However, if you are unlucky, you hit a bomb field and you lose. Your task is about initializing such a field and preparing it for a subsequent game.

Solution 13a (★★✩✩✩)

Write function place_bombs_randomly(width, height, probability) that creates a playfield specified in size via the first two parameters, randomly filled with bombs, respecting the probability from 0.0 to 1.0 passed in.

Example

The following is a playfield of size 16 × 7 with bombs placed randomly. Bombs are represented by asterisks (*) and spaces by dots (.):
* * * . * * . * . * * . * . . .
. * * . * . . * . * * . . . . .
. . * . . . . . . . . . * * * *
. . . * . * * . * * . * * . . .
* * . . . . * . * . . * . . . *
. . * . . * . * * . . * . * * *
. * . * * . * . * * * . . * * .

Exercise 13b (★★★✩✩)

Write function calc_bomb_count(bombs) that computes the number of adjacent fields based on the bomb fields passed in and returns a corresponding array.

Examples

A calculation for playfields of size 3 × 3 as well as size 5 × 5, including randomly distributed bombs results, is the following:
* . .      B 2 1      . * * . .      2 B B 3 1
. . *  =>  1 3 B      * . * * .      B 6 B B 1
. . *      0 2 B      * * . . .  =>  B B 4 3 2
                      * . . * .      B 6 4 B 1
                      * * * . .      B B B 2 1

Exercise 13c (★★✩✩✩)

Write function print_board(bombs, bomb_symbol, bomb_counts) that allows you to display a board as points and stars as well as numbers and B.

Example

The following is the above playfield of size 16 × 7 with all the calculated values for bomb neighbors:
B B B 4 B B 3 B 4 B B 3 B 1 0 0
3 B B 5 B 3 3 B 4 B B 4 3 4 3 2
1 3 B 4 3 3 3 3 4 4 4 4 B B B B
2 3 3 B 2 B B 4 B B 3 B B 4 4 3
B B 3 2 3 4 B 6 B 4 4 B 5 3 4 B
3 4 B 3 3 B 4 B B 5 4 B 4 B B B
1 B 3 B B 3 B 4 B B B 2 3 B B 3

6.3 Solutions

6.3.1 Solution 1: Even Before Odd Numbers (★★✩✩✩)

Write function order_even_before_odd(numbers). This is supposed to rearrange a given array or a list of int values so that the even numbers appear first, followed by the odd numbers. The order within the even and odd numbers is not of relevance.

Examples

Input

Result

[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

[2, 4, 6, 8, 10, 3, 7, 1, 9, 5]

[2, 4, 6, 1, 8]

[2, 4, 6, 8, 1]

[2, 4, 6, 8, 1]

[2, 4, 6, 8, 1]

Algorithm Traverse the array from the beginning. Skip even numbers. As soon as an odd number is found, search for an even number in the part of the array that follows. If such a number is found, swap it with the current odd number. The procedure is repeated until you reach the end of the array.
def order_even_before_odd(numbers):
    i = 0
    while i < len(numbers):
        value = numbers[i]
        if is_even(value):
            # even number, so continue with next number
            i += 1
        else:
            # odd number, jump over all odd ones, until the first even
            j = i + 1
            while j < len(numbers) and not is_even(numbers[j]):
                 j += 1
            if j < len(numbers):
                swap(numbers, i, j)
            else:
                # no further numbers
                break
            i += 1
The helper functions for checking and swapping elements have already been implemented in earlier chapters or sections. They are shown here again to make it easier to try out the examples in the Python command line:
def is_even(n):
    return n % 2 == 0
def is_odd(n):
    return n % 2 != 0
def swap(values, first, second):
    tmp = values[first]
    values[first] = values[second]
    values[second] = tmp
NOTE: VARIATION OF ODD BEFORE EVEN

A variation is to arrange all odd numbers before the even ones. Therefore, it is possible to write function order_odd_before_even(numbers) where again the ordering within the odd and even numbers is not important.

The algorithm is identical to that shown except for minimal differences in an inverted test. This modification is so simple that the function is not shown again here.

Optimized Algorithm: Improved Running Time

You recognize that your checks have quadratic running time, here O(n · m), because you should aim to reduce the running time of an algorithm to O(1) in the best case, preferably O(n) or at least O(n · log(n)), ideally without reducing readability, so nested loops are used. This is not quite so dramatic for pure computations and comprehensibility. For an introduction to the O-notation, please consult Appendix C.

In this case, reducing the running time to O(n) is actually fairly straightforward. As in many solutions to other problems, two position markers are used, here next_even and next_odd. In the beginning, it is assumed that the first element is even and the last odd. Now it is checked if the front number is really even, and the position marker is moved to the right. If the first odd number is encountered, it is swapped with the last element. Even if the last element were odd, it would be swapped again in the next step.

In contrast to the previous solution, this solution does not preserve the order of the even numbers; it also potentially shuffles the odd numbers to a greater extent.
def order_even_before_odd_optimized(numbers):
    next_even = 0
    next_odd = len(numbers) - 1
    while next_even < next_odd:
        current_value = numbers[next_even]
        if is_even(current_value):
            next_even += 1
        else:
            swap(numbers, next_even, next_odd)
            next_odd -= 1
Let’s take a look at the algorithm for the following unsorted numbers (2, 4, 3, 6, 1). Here e and o represent the position pointers for next_even and next_odd, respectively.
2 4 3 6 1
^       ^
e       o
  ^     ^
  e     o
   ^    ^
   e    o
--------- swap
   1 6 3
   ^ ^
   e o
--------- swap
   6 1 3
   ^
   eo
Finally, let’s have a look at what happens for already sorted numbers. Let’s use 1, 2, 3, 4 as examples.
1 2 3 4
^     ^
e     o
-------- swap
4 2 3 1
^   ^
E   o
  ^ ^
  e o
    ^
    eo

Optimized Algorithm: Less Copying

The previous optimization can be taken a little further. Instead of just skipping the even numbers from the left until you encounter an odd number, you can skip values starting two additional while loops. However, you still preserve a O(n) running time from both sides as long as they are even in the front and odd in the back. This is required since you are traversing the same elements and not performing steps more than once (this insight requires some experience).

The following implementation applies what has been said and swaps elements only when it is unavoidable:
def order_even_before_odd_optimized_v2(numbers):
    left = 0
    right = len(numbers) - 1
    while left < right:
        # run to the first odd number or to the end of the array
        while left < len(numbers) and is_even(numbers[left]):
            left += 1
        # run to the first even number or to the beginning of the array
        while right >= 0 and is_odd(numbers[right]):
            right -= 1
        if left < right:
            swap(numbers, left, right)
            left += 1
            right -= 1

Verification

To try it out, use the following inputs that show how it works:
>>> import numpy as np
>>> values = np.array([1, 2, 3, 4, 5, 6, 7])
... order_even_before_odd(values)
... print(values)
[2 4 6 1 5 3 7]
>>> values = np.array([1, 2, 3, 4, 5, 6, 7])
... order_even_before_odd_optimized(values)
... print(values)
[6 2 4 5 3 7 1]
>>> values = np.array([1, 2, 3, 4, 5, 6, 7])
... order_even_before_odd_optimized_v2(values)
... print(values)
[6 2 4 3 5 1 7]

6.3.2 Solution 2: Flip (★★✩✩✩)

Write generic functions for flipping a two-dimensional array horizontally with flip_horizontally(values2dim) and vertically with flip_vertically(values2dim). The array should be rectangular (i.e., no line should be longer than another).

Examples

The following illustrates how this functionality should work:
flip_horizontally()   flip_vertically()
-------------------   -----------------
123      321          1144      3366
456  =>  654          2255  =>  2255
789      987          3366      1144

Horizontal flipping algorithm Traverse inwards from the left and right side of the array. To do this, use two position markers leftIdx and rightIdx. At each step, swap the values referenced by these positions and move inward until the positions overlap. The termination occurs at leftIdx >= rightIdx. Repeat the procedure for all lines.

The following sequence shows the described actions for one line, where l represents leftIdx and r represents rightIdx:
Step      Array values
---------------------
1         1 2 3 4
          ^     ^
          l     r
2         4 2 3 1
          ^     ^
          L     r
3         4 3 2 1
          ^     ^
          R     l

Algorithm for vertical flipping Move from the top and bottom towards the center until both positions overlap. Swap the values and repeat this for all columns. The implementation traverses the array in the x-direction and operates with two position markers on the vertical. After each swap, these position markers are moved towards each other until they cross. You then proceed with the next x-position.

The implementation uses two position pointers and swaps the respective values until the position pointers cross:
def flip_horizontally(values2dim):
    max_y, max_x = get_dimension(values2dim)
    for y in range(max_y):
        left_idx = 0
        right_idx = max_x - 1
        while left_idx < right_idx:
            left_value = values2dim[y][left_idx]
            right_value = values2dim[y][right_idx]
            # swap
            values2dim[y][left_idx] = right_value
            values2dim[y][right_idx] = left_value
             left_idx += 1
             right_idx -= 1
Let’s now take a look at the corresponding implementation of vertical flipping:
def flip_vertically(values2dim):
    max_y, max_x = get_dimension(values2dim)
    for x in range(max_x):
        top_idx = 0
        bottom_idx = max_y - 1
        while top_idx < bottom_idx:
            top_value = values2dim[top_idx][x]
            bottom_value = values2dim[bottom_idx][x]
            # swap
            values2dim[top_idx][x] = bottom_value
            values2dim[bottom_idx][x] = top_value
            top_idx += 1
            bottom_idx -= 1
Here is the function for determining the dimensions of the two-dimensional array that returns the correct data for both nested lists and NumPy arrays, listed once again as a reminder:
def get_dimension(values2dim):
    if isinstance(values2dim, list):
        return (len(values2dim), len(values2dim[0]))
    if isinstance(values2dim, np.ndarray):
        return values2dim.shape
    raise ValueError("unsupported type", type(values2dim))

Modified algorithm In fact, the implementation for flipping may be simplified a little bit. The number of steps can be directly computed in both cases: it is width/2 or height/2. For odd lengths, the middle element is not taken into account, resulting in a correct flip.

With these preliminary considerations, here’s the implementation for horizontal flipping with a for loop as an example. In doing so, you make use of the auxiliary method developed in the introduction, swap(), for swapping two elements.
def flip_horizontally_v2(values2dim):
    max_y, max_x = get_dimension(values2dim)
    for y in range(max_y):
        row = values2dim[y]
        for x in range(max_x // 2):
            swap(row, x, max_x - x - 1)
Optimized algorithm (only for lists) While the solutions shown so far have each made the swaps at the level of individual elements, you can benefit from reassigning entire lines for vertical flipping. This is significantly simpler both in terms of complexity and effort as well as in terms of the amount of source code and it also increases comprehensibility enormously.
def flip_vertically_just_for_lists(values2dim):
    max_y, _ = get_dimension(values2dim)
    for y in range(max_y // 2):
        swap(values2dim, y, max_y - y - 1)
HINT: LIMITATION

This optimization is not possible for NumPy arrays since they operate purely on a contiguous piece of memory. You can read therein row by row, but you can’t swap the references to these rows with each other. On the other hand, you can quickly turn a 4 × 4 array into a 2 × 8 array or 8 × 2 array with reshape().

Verification

To test the functionality, use the inputs from the introductory example, which show the correct operation:
def test_flip_horizontally():
    hori_values = [[1, 2, 3],
                   [4, 5, 6],
                   [7, 8, 9]]
    flip_horizontally(hori_values)
    expected = [[3, 2, 1],
                [6, 5, 4],
                [9, 8, 7]]
    assert hori_values == expected
def test_flip_vertically():
    vert_values = [[1, 1, 4, 4],
                   [2, 2, 5, 5],
                   [3, 3, 6, 6]]
    flip_vertically(vert_values)
    expected = [[3, 3, 6, 6],
                [2, 2, 5, 5],
                [1, 1, 4, 4]]
    assert vert_values == expected

Both other functions are tested in exactly the same way as the previous ones so the associated test functions are not shown here again.

6.3.3 Solution 3: Palindrome (★★✩✩✩)

Write function is_palindrome(values) that checks an array of strings for whether its values form a palindrome.

Examples

Input

Result

[“One”, “Test”, “ – ”, “Test”, “One”]

True

[“Max”, “Mike”, “Mike”, “Max”]

True

[“Tim”, “Tom”, “Mike”, “Max”]

False

Algorithm The palindrome check can easily be expressed recursively. Again, two position pointers are used, which are initially located at the beginning and end of the array. It is checked whether the two values referenced by them are the same. If so, you continue to check recursively and move one position further to the middle on both sides with each recursion step until the positions overlap.
def is_palindrome_rec(values):
    return is_palindrome_rec_in_range(values, 0, len(values) - 1)
def is_palindrome_rec_in_range(values, left, right):
    # recursive termination
    if left >= right:
        return True
    # check if left == right
    if values[left] == values[right]:
        # recursive descent
        return is_palindrome_rec_in_range(values, left + 1, right - 1)
    return False
Optimized algorithm The palindrome check can be converted to an iterative variant based on the recursive solution without much effort:
def is_palindrome_iterative(values):
    left = 0
    right = len(values) - 1
    same_value = True
    while left <= right and same_value:
        # check left == right and repeat until difference occurs
        same_value = values[left] == values[right]
        left += 1
        right -= 1
    return same_value
Besides this variant, you can also take advantage of the fact that the maximum number of steps is known, and you can terminate the loop directly in case of a violation of the palindrome property:
def is_palindrome_short(values):
    for i in range(len(values) // 2):
        if values[i] != values[len(values) - 1 - i]:
            return False
    return True
Python shortcut Of course, the whole thing can be achieved a lot easier by calling the built-in functionality [::-1]:
def is_palindrome_shorter(values):
    return values == values[::-1]

Please keep in mind that for this approach in the presumably rare case of very large amounts of data, an inverse variant of the original data is generated here and thus the memory is required twice.

Verification

For unit testing (again, shown only in excerpts for the recursive variant), use the inputs from the above example. The input and expected values are extracted as a function because they also serve as parameterization for the other two variants.
def values_and_expected():
    return [(["A", "Test", " -- ", "Test", "A"], True),
             (["Max", "Mike", "Mike", "Max"], True),
             (["Tim", "Tom", "Mike", "Max"], False)]
@pytest.mark.parametrize("values, expected", values_and_expected())
def test_is_palindrome_rec(values, expected):
    result = is_palindrome_rec(values)
    assert result == expected

6.3.4 Solution 4: Inplace Rotate (★★★✩✩)

Solution 4a: Iterative (★★★✩✩)

In the introductory section, I showed how to rotate arrays. Now try this inplace (i.e., without creating a new array). Your task is to rotate a two-dimensional square shaped array by 90 degrees clockwise. Write generic function rotate_inplace(values2dim) that iteratively implements this.

Example

For a 6 × 6 array, this is visualized as follows:
1 2 3 4 5 6      F G H I J 1
J K L M N 7      E T U V K 2
I V W X O 8  =>  D S Z W L 3
H U Z Y P 9      C R Y X M 4
G T S R Q 0      B Q P O N 5
F E D C B A      A 0 9 8 7 6
Algorithm Define four corner positions TL, TR, BL, and BR corresponding to the respective corners. Move from left to right and from top to bottom and copy logically as shown in Figure 6-3.
Figure 6-3

Procedure for inplace rotation

Repeat the procedure layer by layer for all neighbors of TL until TR is reached (analogously for the neighbors of the other corners). Then move one position inwards at a time until BL and BR intersect. Let’s clarify the procedure again step by step.

Starting point Given the following array:
1 2 3 4 5 6
J K L M N 7
I V W X O 8
H U Z Y P 9
G T S R Q 0
F E D C B A
Step 1: First, the outer layer is rotated by copying all values to the respective target position as shown here:
F G H I J 1
E K L M N 2
D V W X O 3
C U Z Y P 4
B T S R Q 5
A 0 9 8 7 6
Step 2: Continue with one layer further inwards:
F G H I J 1
E T U V K 2
D S W X L 3
C R Z Y M 4
B Q P O N 5
A 0 9 8 7 6
Step 3: This continues until the innermost level is reached:
F G H I J 1
E T U V K 2
D S Z W L 3
C R Y X M 4
B Q P O N 5
A 0 9 8 7 6
For the processing steps shown, variable offset determines which layer you are in, so width/2 steps are required. Based on the layer, the number of positions to copy is obtained, for which an inner loop is used. The corresponding positions in the array are calculated based on their location, as indicated in the figure. Copying is also made easy by the use of helper variables.
def rotate_inplace(values2dim):
    max_y, max_x = get_dimension(values2dim)
    height = max_y - 1
    width = max_x - 1
    offset = 0
    while offset <= width // 2:
        current_width = width - offset * 2
        for idx in range(current_width):
            # top, right, bottom, left
            lo_x = offset + idx
            lo_y = offset
            ro_x = width - offset
            ro_y = offset + idx
            ru_x = width - offset - idx
            ru_y = height – offset
            lu_x = offset
            lu_y = height - offset – idx
            lo = values2dim[lo_y][lo_x]
            ro = values2dim[ro_y][ro_x]
            ru = values2dim[ru_y][ru_x]
            lu = values2dim[lu_y][lu_x]
            # copy over
            values2dim[ro_y][ro_x] = lo
            values2dim[ru_y][ru_x] = ro
            values2dim[lu_y][lu_x] = ru
            values2dim[lo_y][lo_x] = lu
    offset += 1
Alternatively, you can omit helper variables and only cache the value of the upper left position. However, copying then becomes somewhat tricky because the order in the implementation must be exactly the other way around. This variant of the ring-shaped swap is implemented by the function rotate_elements(). To my taste, the previous variant is more understandable.
def rotate_inplace_v2(values2dim):
    side_length, _ = get_dimension(values2dim)
    start = 0
    while side_length > 0:
        for i in range(side_length):
            rotate_elements(values2dim, start, side_length, i)
        side_length = side_length - 2
        start += 1
def rotate_elements(values2dim, start, len, i):
    end = start + len - 1
    tmp = values2dim[start][start + i]
    values2dim[start][start + i] = values2dim[end - i][start]
    values2dim[end - i][start] = values2dim[end][end - i]
    values2dim[end][end - i] = values2dim[start + i][end]
    values2dim[start + i][end] = tmp

Solution 4b: Recursive (★★★✩✩)

Write recursive function rotate_inplace_recursive(values2dim) that implements the desired 90-degree clockwise rotation.

Algorithm You have already seen that you rotate layer by layer, going from the outer layer further to the inner layer. This literally screams for a recursive solution:
def rotate_inplace_recursive(values2dim):
    _, max_x = get_dimension(values2dim)
    __rotate_inplace_recursive_helper(values2dim, 0, max_x - 1)
The component layer copy is identical as before. Recursive calls replace only the while loop.
def __rotate_inplace_recursive_helper(values2dim, left, right):
    if left >= right:
        return
    current_width = right - left
    for i in range(current_width):
        lo = values2dim[left + i][left]
        ro = values2dim[right][left + i]
        ru = values2dim[right - i][right]
        lu = values2dim[left][right - i]
        values2dim[left + i][left] = ro
        values2dim[right][left + i] = ru
        values2dim[right - i][right] = lu
        values2dim[left][right - i] = lo
    __rotate_inplace_recursive_helper(values2dim, left + 1, right - 1)

Verification

You define the two-dimensional array shown at the beginning. Then you perform the rotation and compare the result with the expectation.
def test_rotation():
    values = [['1', '2', '3', '4', '5', '6'],
              ['J', 'K', 'L', 'M', 'N', '7'],
              ['I', 'V', 'W', 'X', 'O', '8'],
              ['H', 'U', 'Z', 'Y', 'P', '9'],
              ['G', 'T', 'S', 'R', 'Q', '0'],
              ['F', 'E', 'D', 'C', 'B', 'A']]
    rotate_inplace(values)
    expected = [to_list("F G H I J 1"),
                to_list("E T U V K 2"),
                to_list("D S Z W L 3"),
                to_list("C R Y X M 4"),
                to_list("B Q P O N 5"),
                # this is how it would look by hand
                list("A 0 9 8 7 6".replace(" ", ""))]
    assert values == expected
def to_list(text):
    return list(text.replace(" ", ""))

I deliberately show several variants of how to convert a textual representation into a two-dimensional array. I prefer the second variant, especially if using the function to_list(text), which removes the spaces and then formats the string as a list.

6.3.5 Solution 5: Jewels Board Init (★★★✩✩)

Solution 5a: Initialize (★★★✩✩)

Initialize a two-dimensional rectangular array with random-based numbers representing various types of diamonds or jewels as numerical values. The constraint is that initially there must not be three diamonds of the same type placed horizontally or vertically in direct sequence. Write function init_jewels_board(width, height, num_of_colors), which will generate a valid array of the given size and quantity of different types of diamonds.

Example

A random distribution of diamonds represented by digits may look like this for four different colors and shapes:
2 3 3 4 4 3 2
1 3 3 1 3 4 4
4 1 4 3 3 1 3
2 2 1 1 2 3 2
3 2 4 4 3 3 4
To illustrate this, Figure 6-4 shows another example.
Figure 6-4

Graphical representation of a Jewels board

Algorithm First, you create a suitably sized array. Then you fill it row by row and position by position with random-based values using function select_valid_jewel(), which returns the numerical value for the type of diamond. In this method, you have to make sure that the random number just selected does not create a row of three horizontally or vertically.
def init_jewels_board(width, height, num_of_colors):
    board = [[0 for x in range(width)] for y in range(height)]
    for y in range(height):
        for x in range(width):
            board[y][x] = select_valid_jewel(board, x, y, num_of_colors)
    return board
def select_valid_jewel(board, x, y, num_of_colors):
    next_jewel_nr = -1
    is_valid = False
    while not is_valid:
        next_jewel_nr = random.randint(1, num_of_colors)
        is_valid = not check_horizontally(board, x, y, next_jewel_nr) and
                  not check_vertically(board, x, y, next_jewel_nr)
    return next_jewel_nr
ATTENTION: THINGS TO KNOW ABOUT INITIALIZATION
The function select_valid_jewel() still needs optimization. At the moment, you can’t determine that a valid number can be found for a position, for example, for the following constellation with only two types and the position *, for which neither 1 nor 2 is valid as a value, because both would lead to a row of three:
1221
2122
11*

However, the fact that a valid distribution is also available even for only two values gets obvious by the alternating distribution of the white and black squares of a chessboard. One way to fix the just-mentioned weakness is to choose a more powerful algorithm, such as one that uses backtracking.

There is another weak point: The generation of random numbers out of a small range of values often produces the same number several times, but this number has probably already been checked. This must be avoided. For this purpose, all previously selected random numbers can be stored in a set. Besides, you would have to check whether all expected and possible numbers have already been tried. This short list shows that it is much more complex than you might initially expect.

Now let’s move on to checking the horizontal and vertical. At first, you could assume that starting from the current position, you would have to check to the left and right as well as up and down. However, if you reread the assignment more carefully, it says that no chains of length three or longer are allowed. Because you fill the playfield from top to bottom and from left to right, no diamonds to be checked can exist on the right and below the current position. Thus, you can limit yourself to checking to the left and to the top. Furthermore, you do not need to check for longer chains since they cannot occur if you have identified a chain of three.

With these preliminary considerations, you can use the two helper functions to check the respective neighboring fields horizontally and vertically by simply verifying that all of them have the same value as the initial field.
def check_horizontally(board, x, y, jewel_nr):
    top1 = get_at(board, x, y - 1)
    top2 = get_at(board, x, y - 2)
    return top1 == jewel_nr and top2 == jewel_nr
def check_vertically(board, x, y, jewel_nr):
    left1 = get_at(board, x - 1, y)
    left2 = get_at(board, x - 2, y)
    return left1 == jewel_nr and left2 == jewel_nr
When accessing the array, the negative offsets may result in invalid array indices. Therefore, you implement function get_at(), which is mainly responsible for checking the boundaries and returns the value -1 for no longer being on the playfield. This value can never occur on the playfield, and thus it is counted as no chain when comparing. Furthermore, you use the function get_dimension() again.
def get_at(values, x, y):
    max_y, max_x = get_dimension(values)
    if x < 0 or y < 0 or y >= max_y or x >= max_x:
        return -1
    return values[y][x]
def get_dimension(values2dim):
    if isinstance(values2dim, list):
        return (len(values2dim), len(values2dim[0]))
    if isinstance(values2dim, np.ndarray):
        return values2dim.shape
    raise ValueError("unsupported type", type(values2dim))
ATTENTION: LITTLE SOURCE CODE VS. SMALL BUT MANY METHODS

In this example, I follow the strategy of defining small helper functions, which on the one hand increases the amount of source code. On the other hand, functionalities can be described and tested very well in isolation. Moreover, this approach often allows expressing the source code on a comprehensible and conceptual level. In many cases, this allows extensions to be easily integrated.

Solution to the Bonus Task: Checking Diagonals (★★★✩✩)

Add a check for diagonals. This should make the constellation from the example invalid, among other things, because of the diagonals marked in bold with the number 3 at the bottom right.

Algorithm Checking the four diagonals from one position seems much more time-consuming than checking the horizontal and the vertical. Theoretically, there would be four directions for each position. As (almost) always, it is a good idea to think about a problem a little longer. If you follow this advice, you may come to the solution where in this case, starting from one position, it is sufficient to check only diagonally to the top left and right because, from the point of view of the positions above, this one corresponds to a check diagonally left and right below, as is indicated in the following:
X      X
 X   X
  X X
Thus, the diagonal check with two helper variables each for the positions of the compass directions northwest and northeast can be implemented as follows and invoked in the function select_valid_jewel():
def check_diagonally(board, x, y, jewel_nr):
    up_left1 = get_at(board, x - 1, y - 1)
    up_left2 = get_at(board, x - 2, y - 2)
    up_right1 = get_at(board, x + 1, y - 1)
    up_right2 = get_at(board, x + 2, y - 2)
    return (up_left1 == jewel_nr and up_left2 == jewel_nr) or
           (up_right1 == jewel_nr and up_right2 == jewel_nr)
def select_valid_jewel(board, x, y, num_of_colors):
    next_jewel_nr = -1
    is_valid = False
    while not is_valid:
        next_jewel_nr = random.randint(1, num_of_colors)
        is_valid = not check_horizontally(board, x, y, next_jewel_nr) and
                  not check_vertically(board, x, y, next_jewel_nr) and
                  not check_diagonally(board, x, y, next_jewel_nr)
    return next_jewel_nr

Verification

To verify that the correct playfields are being created now, let’s generate and output one of size 5 × 3 with four types of diamonds as follows:
>>> import random
>>> import numpy as np
>>> board = init_jewels_board(5, 3, 4)
>>> np.array(board)
array([[3, 4, 3, 3, 2],
       [4, 4, 1, 2, 3],
       [1, 1, 3, 3, 2]])

Solution 5b: Validity Check (★★★✩✩)

In this subtask, you want to validate an existing playfield. As a challenge, a list of violations must be returned. Implement function check_board_validity(board2dim) for a rectangular array.

Example

To try out the validity check, use the playfield from the introduction, specially marked here:
values_with_errors = [[2, 3, 3, 4, 4, 3, 2],
                      [1, 3, 3, 1, 3, 4, 4],
                      [4, 1, 4, 3, 3, 1, 3],
                      [2, 2, 1, 1, 2, 3, 2],
                      [3, 2, 4, 4, 3, 3, 4]]
This should produce the following errors due to its diagonals:
['Invalid at x=3 y=2 hor=False, ver=False, dia=True',
 'Invalid at x=2 y=3 hor=False, ver=False, dia=True',
 'Invalid at x=4 y=4 hor=False, ver=False, dia=True']
Algorithm The validity check can be easily developed based on your previously implemented functions. You check for horizontal, vertical, and diagonal rows of three for each playfield position. If such a violation is found, you generate an appropriate error message.
def check_board_validity(board2dim):
    errors = []
    max_y, max_x = get_dimension(board2dim)
    for y in range(max_y):
        for x in range(max_x):
        current_jewel = board2dim[y][x]
        has_chain_hor = check_horizontally(board2dim, x, y, current_jewel)
        has_chain_ver = check_vertically(board2dim, x, y, current_jewel)
        has_chain_dia = check_diagonally(board2dim, x, y, current_jewel)
        if has_chain_hor or has_chain_ver or has_chain_dia:
            error_msg = "Invalid at x={} y={} hor={}, ver={}, dia={}".
                format(x, y, has_chain_hor, has_chain_ver, has_chain_dia)
            errors.append(error_msg)
    return errors

Verification

To try out the validity check, you first use the playfield from the introduction and create a NumPy array from it:
>>> values_with_errors = [[2, 3, 3, 4, 4, 3, 2],
                          [1, 3, 3, 1, 3, 4, 4],
                          [4, 1, 4, 3, 3, 1, 3],
                          [2, 2, 1, 1, 2, 3, 2],
                          [3, 2, 4, 4, 3, 3, 4]]
>>> array_with_errors = np.array(values_with_errors)
Your functionality should produce the following error messages due to the three faulty diagonals. This is the case for both calls.
>>> check_board_validity(values_with_errors)
['Invalid at x=3 y=2 hor=False, ver=False, dia=True',
'Invalid at x=2 y=3 hor=False, ver=False, dia=True',
'Invalid at x=4 y=4 hor=False, ver=False, dia=True']
>>> check_board_validity(array_with_errors)
['Invalid at x=3 y=2 hor=False, ver=False, dia=True',
'Invalid at x=2 y=3 hor=False, ver=False, dia=True',
'Invalid at x=4 y=4 hor=False, ver=False, dia=True']
Subsequently, you replace the problematic digits with a yet unused digit, such as number 5, and retest the function, expecting no conflicts:
def test_check_board_validity_no_conflicts():
    values = [[2, 3, 3, 4, 4, 3, 2],
              [1, 3, 3, 1, 3, 4, 4],
              [4, 1, 4, 5, 3, 1, 3],
              [2, 2, 5, 1, 2, 3, 2],
              [3, 2, 4, 4, 5, 3, 4]]
    errors = check_board_validity(values)
    assert errors == []

6.3.6 Solution 6: Jewels Board Erase Diamonds (★★★★✩)

The challenge is to delete all chains of three or more horizontally, vertically, or diagonally connected diamonds from the rectangular playfield and subsequently to fill the resulting empty spaces with the diamonds lying above them (i.e., roughly in the same way as gravity works in nature). The following is an example of how the erasing and then dropping is repeated several times until no more change occurs. Spaces are shown as _ for better visibility.
Iteration 1:
1 1 1 2 4 4 3  erase  _ _ _ _ 4 4 _  fall down  _ _ _ _ _ _ _
1 2 3 4 2 4 3   =>    1 2 3 4 _ 4 _      =>     1 2 3 4 4 4 _
2 3 3 1 2 2 3         2 3 3 1 2 _ _             2 3 3 1 2 4 _
Iteration 2:
_ _ _ _ _ _ _  erase  _ _ _ _ _ _ _  fall down  _ _ _ _ _ _ _
1 2 3 4 4 4 _    =>   1 2 3 _ _ _ _      =>     1 2 3 _ _ _ _
2 3 3 1 2 4 _         2 3 3 1 2 4 _             2 3 3 1 2 4 _

Solution 6a: Erase (★★★★✩)

Write function erase_chains(values2dim) that erases all rows of three or more contiguous diamonds in horizontal, vertical, and diagonal orientations from a rectangular playfield array.

Examples

An invocation of the method transforms the output array given on the left into the result shown on the right:
All chains without overlap          Special case: overlaps
1 2 3 3 3 4      0 0 0 0 0 0        1 1 1 2      0 0 0 2
1 3 2 4 2 4      0 3 0 4 2 0        1 1 3 4  =>  0 0 3 4
1 2 4 2 4 4  =>  0 0 4 0 4 0        1 2 1 3      0 2 0 3
1 2 3 5 5 5      0 0 3 0 0 0
1 2 1 3 4 4      0 0 1 3 4 4
Algorithm: Preliminary considerations As a first brute force variant, you could erase the values directly when finding them. In this case, you search for a chain of length 3 or more and then directly erase these fields. However, this has a crucial weakness: Single diamonds can be part of several chains, as shown in the example above. If you delete immediately, not all occurrences may be found; depending on which of the checks is done first, the other two fail in the following constellation.
XXX
XX
X X

A second idea is to modify the algorithm minimally by choosing an intermediate representation that symbolizes the deletion request, such as negative numbers, instead of deletion. After all entries in the array have been processed, the deletion takes place in a separate pass. Specifically, you remove all negative values from the array by replacing them with the numerical value 0.

Algorithm The second idea is implemented by function erase_chains(values2dim). It starts with marking all the fields to be deleted using the function mark_elements_for_removal(values2dim). Then they are deleted using the function erase_all_marked(values2dim). For both methods you work position by position. First you have to detect chains of length 3 or more. Function find_chains(values2dim, x, y) is responsible for this. Once a chain has been found, it is marked by calling mark_chains_for_removal(values2dim, x, y, dirs_with_chains). The next action is to determine whether each field is marked for deletion. In this case, the stored value is replaced with the value 0 (here by calling the function blank_value(values2dim); details about this seemingly superfluous indirection will be considered later).
def erase_chains(values2dim):
    mark_elements_for_removal(values2dim)
    return erase_all_marked(values2dim)
def mark_elements_for_removal(values2dim):
    max_y, max_x = get_dimension(values2dim)
    for y in range(max_y):
        for x in range(max_x):
            dirs_with_chains = find_chains(values2dim, x, y)
            mark_chains_for_removal(values2dim, x, y, dirs_with_chains)
def erase_all_marked(values2dim):
    erased_something = False
    max_y, max_x = get_dimension(values2dim)
    for y in range(max_y):
        for x in range(max_x):
            if is_element_marked_for_removal(values2dim[y][x]):
                values2dim[y][x] = blank_value(values2dim)
                erased_something = True
    return erased_something
def is_element_marked_for_removal(value):
    return value < 0
def blank_value(values2dim):
    return 0
Now let’s move on to the two trickier implementations and start picking up and recognizing chains of three or more similar diamonds. For this, you check for all relevant directions if there is a chain (again with the optimization that you must check diagonally only to the lower right and left). For this, you traverse the fields, count the similar elements, and stop at a deviation. If you find three or more equal values, then that direction is included in the list dirs_with_chains. As a special feature, you check at the beginning of the function if the current field is empty; you don’t want to collect chains of blanks.
def find_chains(values2dim, start_x, start_y):
    orig_value = values2dim[start_y][start_x]
    if orig_value == 0: # ATTENTION to think of such special cases
        return []
    dirs_with_chains = []
    relevant_dirs = (Direction.S, Direction.SW, Direction.E, Direction.SE)
    for current_dir in relevant_dirs:
        length = 1
    dx, dy = current_dir.value
    next_pos_x = start_x + dx
    next_pos_y = start_y + dy
    while is_on_board(values2dim, next_pos_x, next_pos_y) and
          is_same(orig_value, values2dim[next_pos_y][next_pos_x]):
        length += 1
        next_pos_x += dx
        next_pos_y += dy
        if length >= 3:
            dirs_with_chains.append(current_dir)
    return dirs_with_chains
def is_on_board(values2dim, next_pos_x, next_pos_y):
    max_y, max_x = get_dimension(values2dim)
    return 0 <= next_pos_x < max_x and 0 <= next_pos_y < max_y
def is_same(val1, val2):
    return abs(val1) == abs(val2)
In fact, you are almost there. The only thing missing is the function for marking for deletion. Did you think at the beginning that this assignment is so complex? Probably not :-) Let’s get to work. You now traverse all chains and convert the original values into one marked for deletion. To accomplish this, you rely on helper function mark_element_for_removal(orig_value), which for the sake of simplicity converts the value to a negative value (with type str, for example, you can use a conversion to lowercase).
def mark_chains_for_removal(values, start_x, start_y, dirs_with_chains):
    orig_value = values[start_y][start_x]
    for current_dir in dirs_with_chains:
        dx, dy = current_dir.value
        next_x = start_x
        next_y = start_y
        while is_on_board(values, next_x, next_y) and
               is_same(orig_value, values[next_y][next_x]):
            values[next_y][next_x] = mark_element_for_removal(orig_value)
            next_x += dx
            next_y += dy
def mark_element_for_removal(value):
    return -value if value > 0 else value

I want to point out that the functionalities are solved using side effects. Here, you are operating directly on the passed data, so this is not bad because the data is not passed further out. Instead, it is all internal functionalities.

Verification

After this exhausting implementation, let’s test the deletion as well:
def test_erase_chains():
    values2dim = [[1, 1, 1, 2, 4, 4, 3],
                  [1, 1, 3, 4, 2, 4, 3],
                  [1, 3, 1, 1, 2, 2, 3]]
    deleted = erase_chains(values2dim)
    expected_board = [[0, 0, 0, 0, 4, 4, 0],
                      [0, 0, 3, 4, 0, 4, 0],
                      [0, 3, 0, 1, 2, 0, 0]]
    assert deleted is True
    assert values2dim == expected_board
def test_erase_chains_example_1():
    values2dim = [[1, 2, 3, 3, 3, 4],
                  [1, 3, 2, 4, 2, 4],
                  [1, 2, 4, 2, 4, 4],
                  [1, 2, 3, 5, 5, 5],
                  [1, 2, 1, 3, 4, 4]]
    deleted = erase_chains(values2dim)
    expected_board = [[0, 0, 0, 0, 0, 0],
                      [0, 3, 0, 4, 2, 0],
                      [0, 0, 4, 0, 4, 0],
                      [0, 0, 3, 0, 0, 0],
                      [0, 0, 1, 3, 4, 4]]
    assert deleted is True
    assert values2dim == expected_board

Solution 6b: Falling Down (★★★✩✩)

Write function fall_down(values2dim) working inplace that drops the diamonds from top to bottom, provided there is a space below their position.

Example

An invocation of the function transforms the output array given on the left into the result shown on the right:
0 1 3 3 0 0      0 0 0 0 0 0
0 1 0 0 0 0      0 0 0 0 0 0
0 0 3 3 0 0  =>  0 0 3 3 0 0
0 0 0 3 3 4      0 1 3 3 0 0
0 0 3 0 0 0      0 1 3 3 3 4

Algorithm At first, the task seems to be relatively easy to solve. However, the complexity increases due to a few special characteristics.

As one possible implementation, let’s begin with a brute force solution. From left to right, the following is checked for all x-positions in the vertical: Starting from the lowest row to the second highest one, you test whether they represent a blank in each case. If this is the case, the value from the line above is used. In this case, the value from the line above is exchanged with the blank (symbolized here as _, represented in the model with the value 0).
1      1      _
2  =>  _  =>  1
_      2      2
The procedure can be implemented as follows:
def fall_down_first_try(values2dim):
    max_y, max_x = get_dimension(values2dim)
    for x in range(max_x):
        for y in range(max_y - 1, 0, -1):
            value = values2dim[y][x]
            if is_blank(value):
                # fall down
                values2dim[y][x] = values2dim[y - 1][x]
                values2dim[y - 1][x] = blank_value(values2dim)
def is_blank(value):
    return value == 0
This works pretty passably, but unfortunately not quite for the following special case:
1      _
_  =>  1
_      _

You recognize that propagation is missing, and thus the numbers do not continue to fall all the way down, even if there is an empty place below.

As a next idea, you could start falling from the top, but this doesn’t work in every case either! While with this procedure the previously problematic case
1      _
_  =>  _
_      1
is solved, problems occur now for the first constellation. These problems do not occur with the variant before.
1      1
2  =>  _
_      2

You now know that both of the variants discussed do not yet work quite correctly. Moreover, it was crucial to use the right set of test data to uncover just these specific problems.

To correct this, you need to implement continuous falling of stones to always move all values per column. The while loop is used for this:
def fall_down(values2dim):
    max_y, max_x = get_dimension(values2dim)
    for x in range(max_x):
        for y in range(max_y - 1, 0, -1):
            current_y = y
            # fall down until there is no more empty space under it
            while current_y < len(values2dim) and
                is_blank(values2dim[current_y][x]):
            # fall down
            values2dim[current_y][x] = values2dim[current_y - 1][x]
            values2dim[current_y - 1][x] = blank_value(values2dim)
            current_y += 1

Verification

Let’ take the previously obtained result of the deletion as the starting point for the falling:
def test_fall_down():
    values2dim = [[0, 1, 3, 3, 0, 0],
                  [0, 1, 0, 0, 0, 0],
                  [0, 0, 3, 3, 0, 0],
                  [0, 0, 0, 3, 3, 4],
                  [0, 0, 3, 0, 0, 0]]
    fall_down(values2dim)
    expected_board = [[0, 0, 0, 0, 0, 0],
                      [0, 0, 0, 0, 0, 0],
                      [0, 0, 3, 3, 0, 0],
                      [0, 1, 3, 3, 0, 0],
                      [0, 1, 3, 3, 3, 4]]
    assert values2dim == expected_board

Overall Verification

To experience your functions all together in action, use the example you used for deleting:
def main():
    example_board = [[1, 1, 1, 2, 4, 4, 3],
                  [1, 1, 3, 4, 2, 4, 3],
                  [1, 3, 1, 1, 2, 2, 3]]
    print_array(example_board)
    while erase_chains(example_board):
        print("---------------------------------")
        fall_down(example_board)
        print_array(example_board)
Using the following helper function print_array(values) developed in the introduction
def print_array(values2dim):
    max_y, max_x = get_dimension(values2dim)
    for y in range(max_y):
        for x in range(max_x):
            value = values2dim[y][x]
            print(str(value) + " ", end='')
        print()
gives the expected output:
1 1 1 2 4 4 3
1 1 3 4 2 4 3
1 3 1 1 2 2 3
---------------------------------
0 0 0 0 0 0 0
0 0 0 4 4 4 0
0 3 3 1 2 4 0
---------------------------------
0 0 0 0 0 0 0
0 0 0 0 0 0 0
0 3 3 1 2 4 0
---------------------------------
Modification to characters Now let’s go one step further and use letters as an alternative to digits for modeling. You perform the actions on a prepared array of letters, which allows you to see different deletions and iterations very nicely. However, you must adapt some of the functions for the type str appropriately (see the following practical tip). Add the following lines to the above main() function as indicated by the comment:
# main as before
    jewels_test_deletion = [list("AACCDE"),
                            list("AA DE"),
                            list("ABCCDE"),
                            list("AB CCD"),
                            list("ABCDDD")]
    print_array(jewels_test_deletion)
    while erase_chains(jewels_test_deletion):
        print("---------------------------------")
        fall_down(jewels_test_deletion)
        print_array(jewels_test_deletion)
The desired and expected result should then look like this:
A A C C D E
A A     D E
A B C C D E
A B   C C D
A B C D D D
---------------------------------
   C C
 A C C
 A C C C D
---------------------------------
 A
 A       D

Implementing the supplementary processing based on characters is the subject of the following practical tip. You will probably also suddenly realize why a few seemingly unimportant auxiliary functions were created in the previous implementation.

HINT: VARIANTS WITH TYPE STR
Some readers may have wondered why I implement various helper functions when the functionality seems very simple. The reason is that this way it gets easier to use the algorithms almost unchanged for other types instead just by redefining the corresponding helper functions, for example these:
def blank_value(values2dim):
    if type(values2dim[0][0]) is str:
        return " "
    return 0
def is_blank(value):
    if type(value) is str:
        return value == " " or value == "_" or len(value) == 0
    return value == 0
 def is_same(val1, val2):
    if type(val1) is str:
        return val1.lower() == val2.lower()
    return abs(val1) == abs(val2)
def mark_element_for_removal(value):
    if type(value) is str:
        return value.lower()
    return -value if value > 0 else value
def is_element_marked_for_removal(value):
    if type(value) is str:
        return value.islower()
    return value < 0

Using the approach described ensures that the higher-level functions for determining which chains to delete, the actual deletion, and the falling of the diamonds don’t even need to be adjusted.

6.3.7 Solution 7: Spiral Traversal (★★★★✩)

Write generic method spiral_traversal(values2dim) that traverses a two-dimensional rectangular array (or a nested list) in the form of a spiral and prepare it as a list. The start is in the upper left corner. First, the outer layer is traversed, and then the next inner layer.

Example

An example is shown in Figure 6-5.
Figure 6-5

Basic procedure for the spiral traversal

For the following two nested lists of number and letter sequences, the results of a spiral traversal are shown:
numbers = [[1, 2, 3, 4],
           [12, 13, 14, 5],
           [11, 16, 15, 6],
           [10, 9, 8, 7]]
letter_pairs = [["AB", "BC", "CD", "DE"],
                ["JK", "KL", "LM", "EF"],
                ["IJ", "HI", "GH", "FG"]]
=>
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16]
[AB, BC, CD, DE, EF, FG, GH, HI, IJ, JK, KL, LM]
JOB INTERVIEW TIPS: CLARIFY ASSUMPTIONS

Before proceeding with a solution, be sure to clarify any constraints or special requirements by asking questions. In this case, ask if the original data should be a rectangular. Assume that to be the case here.

Algorithm Let’s start with an idea. For a spiral movement, you start going to the right until you reach the boundary, then change direction downward, and advance again until you reach the boundary. Then turn to the left and finally up to the boundary. For the spiral to narrow, the respective limits must be suitably reduced at each change of direction. Formulating the termination condition correctly is not quite easy when operating. The following observation helps: The total number of steps is given by width ∗ height − 1 for a 4 × 3 sized data set, thus 4 ∗ 3 − 1 = 12 − 1 = 11. With these preliminary considerations, we implement the spiral traversal as follows:
class Direction(Enum):
    RIGHT = (1, 0)
    DOWN = (0, 1)
    LEFT = (-1, 0)
    UP = (0, -1)
def spiral_traversal(values2dim):
    pos_x = 0
    pos_y = 0
    min_x = 0
    min_y = 1
    max_y, max_x = get_dimension(values2dim)
    results = []
    dir = Direction.RIGHT
    steps = 0
    all_steps = max_y * max_x
    while steps < all_steps:
        # action
        results.append(values2dim[pos_y][pos_x])
        if dir == Direction.RIGHT:
            if pos_x < max_x - 1:
                pos_x += 1
            else:
                dir = Direction.DOWN
                max_x -= 1
        if dir == Direction.DOWN:
            if pos_y < max_y - 1:
                 pos_y += 1
            else:
                dir = Direction.LEFT
                max_y -= 1
        if dir == Direction.LEFT:
            if pos_x > min_x:
                pos_x -= 1
            else:
                dir = Direction.UP
                min_x += 1
        if dir == Direction.UP:
            if pos_y > min_y:
                pos_y -= 1
            else:
                dir = Direction.RIGHT
                min_y += 1
                # possible mistake: You now have to start one
                # position further to the right!
                pos_x += 1
        steps += 1
    return results

After a complete traversal of one layer, you have to move the position pointer one position towards the center. This gets easily forgotten.

The algorithm presented works, but it requires quite a few special treatments.

Optimized algorithm Look at the figure again and then think a bit. You know that initially the whole array is a valid movement area. At each iteration, the outer layer is processed and you continues inwards. Now you can specify the valid range by four position markers as before. However, you proceed more cleverly when updating.

You notice that after moving to the right, the top line is processed so that you can increase the counter min_y by one. If you move down, then the rightmost side is traversed, and the counter max_x is decreased by one. Moving to the left, the bottom row is processed, and the counter max_y is decreased by one. Finally, when moving upwards, the counter min_x is increased by one. To detect when to increment, you implement utility function is_outside() or range checking.

Additionally, you can still take advantage of defining the direction constants according to the order in the spiral traversal and then implementing function next() in the enum that specifies the subsequent direction in each case. Likewise, you define there the offset values dx and dy as a tuple.
class Direction(Enum):
    RIGHT = (1, 0)
    DOWN = (0, 1)
    LEFT = (-1, 0)
    UP = (0, -1)
    def next(self):
        keys = list(Direction.__members__.keys())
        pos = keys.index(self.name)
        return list(Direction)[(pos + 1) % len(keys)]
With these thoughts and preliminaries, you are now able to implement the spiral traversal in a readable and understandable way as follows:
def spiral_traversal_optimized(values2dim):
    pos_x = 0
    pos_y = 0
    min_x = 0
    min_y = 0
    max_y, max_x = get_dimension(values2dim)
    results = []
    dir = Direction.RIGHT
    steps = 0
    all_steps = max_y * max_x
    while steps < all_steps:
        # action
        results.append(values2dim[pos_y][pos_x])
        dx, dy = dir.value
        if is_outside(pos_x + dx, pos_y + dy, min_x, max_x, min_y, max_y):
            if dir == Direction.RIGHT:
                min_y += 1
            if dir == Direction.DOWN:
                max_x -= 1
            if dir == Direction.LEFT:
                max_y -= 1
            if dir == Direction.UP:
                min_x += 1
            dir = dir.next()
            dx, dy = dir.value
        pos_x += dx
        pos_y += dy
        steps += 1
    return results
def is_outside(x, y, min_x, max_x, min_y, max_y):
    return x < min_x or x >= max_x or y < min_y or y >= max_y

Verification

Check if your algorithm as well as its optimized variant and really performs the expected traversal through the array or nested list for the inputs from the above example:
def values_and_expected():
    return [([["A", "B", "C", "D"],
               ["J", "K", "L", "E"],
               ["I", "H", "G", "F"]],
              list("ABCDEFGHIJKL")),
             ([[1, 2, 3, 4],
               [12, 13, 14, 5],
               [11, 16, 15, 6],
               [10, 9, 8, 7]],
              [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16])]
@pytest.mark.parametrize("values, expected", values_and_expected())
def test_spiral_traversal(values, expected):
    result = spiral_traversal(values)
    assert result == expected
@pytest.mark.parametrize("values, expected", values_and_expected())
def test_spiral_traversal_optimized(values, expected):
    result = spiral_traversal_optimized(values)
    assert result == expected

6.3.8 Solution 8: Add One to an Array as a Number (★★✩✩✩)

Consider an array or a list of numbers representing the digits of a decimal number. Write function add_one(digits) that performs an addition by the value 1 and is only allowed to use arrays as data structure for the solution.

Examples

Input

Result

[1, 3, 2, 4]

[1, 3, 2, 5]

[1, 4, 8, 9]

[1, 4, 9, 0]

[9, 9, 9, 9]

[1, 0, 0, 0, 0]

Algorithm You may remember back to your school days and use digit-oriented processing: traverse the values from back to front and then add the overflow value of the last addition to the respective digit value. Initially, you start with the assumption that there is an overflow. If the value 10 is reached again, the overflow must be propagated further. In the special case that the overflow propagates to the very front, the array must be increased by one position to accommodate the new leading 1.
def add_one(digits):
    if len(digits) == 0:
        raise ValueError("must be a valid non empty array / list")
    result = []
    # run from back to front and add, check for overflow
    overflow = 1
    for current_digit in reversed(digits):
        current_digit += overflow
        overflow = 1 if current_digit >= 10 else 0
        result.insert(0, current_digit % 10)
    if overflow == 1:
        result.insert(0, 1)
    return result

In the special case that the carry propagates all the way to the front, the array must be enlarged by one position to accommodate the new leading 1.

Verification

To check your implementation, use the three combinations of values from the introductory examples, which cover the three main cases of no propagation, propagation by one digit, and propagation over all digits. Additionally, add a test case for the propagation for two digits.
def values_and_expected():
    return [([1, 3, 2, 4], [1, 3, 2, 5]),
             ([1, 4, 8, 9], [1, 4, 9, 0]),
             ([1, 3, 9, 9], [1, 4, 0, 0]),
             ([9, 9, 9, 9], [1, 0, 0, 0, 0])]
@pytest.mark.parametrize("values, expected", values_and_expected())
def test_add_one(values, expected):
    result = add_one(values)
    assert result == expected

6.3.9 Solution 9: Sudoku Checker (★★★✩✩)

In this challenge, a Sudoku puzzle is examined to see if it is a valid solution. Let’s assume a 9 × 9 array with int values. According to the Sudoku rules, each row and each column must contain all numbers from 1 to 9. Besides, all numbers from 1 to 9 must, in turn, occur in each 3 × 3 subarray. Write function is_sudoku_valid(board)for checking.

Example

The following is a valid solution:
Algorithm In Sudoku, three different types of checks have to be performed. They can be divided into three corresponding functions very well. First are the functions check_horizontally() and check_vertically(), which ensure horizontally and vertically that all digits from 1 to 9 always occur exactly once in a row or column, respectively. To check this, you collect all digits stored in the respective alignment in a list and compare them in the function all_desired_numbers() to see if they contain the desired numbers.
def check_horizontally(board):
    for row in range(9):
        # collect all values of a row in a list
        row_values = [board[row][x] for x in range(9)]
    if not all_desired_numbers(row_values):
        return False
    return True
def check_vertically(board):
    for x in range(9):
        # collect all values of a column in a list
        column_values = [board[row][x] for row in range(9)]
        if not all_desired_numbers(column_values):
            return False
    return True

You might wonder whether it’s preferable to collect the values in a set. Although this is obvious and works well for fully filled Sudoku puzzles, collecting data in a set complicates subsequent checking if you permit empty fields as well.

Regardless, both checks rely on the following helper function:
def all_desired_numbers(all_collected_values):
    if len(all_collected_values) != 9:
        raise ValueError("not 9 values to process")
    one_to_nine = {1, 2, 3, 4, 5, 6, 7, 8, 9}
    values_set = set(all_collected_values)
    return one_to_nine == values_set

I would like to explicitly point out the elegance of the helper function all_desired-_numbers(). It unifies various things in its brevity: actually, you need to check that the collected values do not contain duplicates and that there are exactly nine different digits. Due to your implementation, you don’t need to check the length. Still, you do it anyway to guard against careless errors with an exception. By converting the values into a set and comparing it to the set from the expected values, the process is nice and short.

Next, you need to check each of the nine subfields of size 3 × 3. This doesn’t sound easy at first. But think a bit: You can use two nested loops to run off the 3 × 3 boxes. Two more nested loops run the respective x and y values for the boxes. Simple multiplications and additions are used to derive the corresponding index values in the original array. By following the previously presented idea of collecting the values into a list, which is finally checked against the expected target set of digits 1 to 9, the implementation loses its initial horror.
def check_boxes(board):
    # 3 x 3 box
    for y_box in range(3):
        for x_box in range(3):
            # values per box
            box_values = collect_box_values(board, y_box, x_box)
            if not all_desired_numbers(box_values):
                return False
    return True
The picking up of digits within a 3 x 3 box is implemented as follows:
def collect_box_values(board, y_box, x_box):
    box_values = []
    # inside the boxes each 3 x 3
    for y in range(3):
        for x in range(3):
            # actual index values
            real_y = y_box * 3 + y
            real_x = x_box * 3 + x
           box_values.append(board[real_y][real_x])
    return box_values
For a complete Sudoku check, you then need to combine these values all together by and:
def is_sudoku_valid(board):
    return check_horizontally(board) and
        check_vertically(board) and
        check_boxes(board)

Verification

You first define the Sudoku playfield as shown in the introduction and then you test all three variants.
def main():
    board = [[1, 2, 3, 4, 5, 6, 7, 8, 9],
             [4, 5, 6, 7, 8, 9, 1, 2, 3],
             [7, 8, 9, 1, 2, 3, 4, 5, 6],
             [2, 1, 4, 3, 6, 5, 8, 9, 7],
             [3, 6, 5, 8, 9, 7, 2, 1, 4],
             [8, 9, 7, 2, 1, 4, 3, 6, 5],
             [5, 3, 1, 6, 4, 2, 9, 7, 8],
             [6, 4, 2, 9, 7, 8, 5, 3, 1],
             [9, 7, 8, 5, 3, 1, 6, 4, 2], ]
    print("H: ", check_horizontally(board))
    print("V: ", check_vertically(board))
    print("B: ", check_boxes(board))
    print("S: ", is_sudoku_valid(board))

As expected, you get four times the value True as a result.

Bonus

While it is nice to be able to check a Sudoku board that is completely filled with digits for its validity, it is even better to be able to predict for a board with gaps (i.e., still missing digits) whether a valid solution can emerge from it. This is of particular interest if you want to develop an algorithm for solving a Sudoku puzzle.

Example

Based on the example of the valid Sudoku playfield given above, I deleted the digits in random places. This surely results in a valid solution.
Algorithm A partially filled playfield can be checked for validity fairly easily if you take the previous implementation as a basis. First, you need modeling for the blank fields. In this case, the value 0 is a good choice. Based on this, you can leave the implementation for collecting the values horizontally, vertically, and in the boxes as it is. You only have to slightly modify the final check whether all values from 1 to 9 are included. First, you remove the value 0 from the collected values, if any. Then you make sure that there are no duplicates. Finally, you check whether the collected values are a subset of 1 to 9.
def all_desired_numbers(all_collected_values):
    # remove irrelevant empty fields
    relevant_values = remove_all_occurences(all_collected_values, 0)
    # no duplicates?
    values_set = set(relevant_values)
    if len(relevant_values) != len(values_set):
        return False
    # only 1 to 9?
    one_to_nine = {1, 2, 3, 4, 5, 6, 7, 8, 9}
    return one_to_nine.issuperset(values_set)
def remove_all_occurences(values, item):
    return list(filter(lambda x: x != item, values))

The very best comes at the end. This function works for completely filled Sudoku puzzles and those containing blanks!

Verification

Again you define the Sudoku playfield with blanks, as shown before. After that, you check a slightly modified playfield, where the value 2 is inserted in the first line at position 3. Due to this, the playfield becomes invalid.
def create_initialized_board():
    return [[1, 2, 0, 4, 5, 0, 7, 8, 9],
             [0, 5, 6, 7, 0, 9, 0, 2, 3],
             [7, 8, 0, 1, 2, 3, 4, 5, 6],
             [2, 1, 4, 0, 6, 0, 8, 0, 7],
             [3, 6, 0, 8, 9, 7, 2, 1, 4],
             [0, 9, 7, 0, 1, 4, 3, 6, 0],
             [5, 3, 1, 6, 0, 2, 9, 0, 8],
             [6, 0, 2, 9, 7, 8, 5, 3, 1],
             [9, 7, 0, 0, 3, 1, 6, 4, 2]]
def test_is_sudoku_valid():
    board = create_initialized_board()
    is_valid_sudoku = is_sudoku_valid(board)
    assert is_valid_sudoku is True
def test_is_sudoku_valid_for_invalid_board():
    board = create_initialized_board()
    # change it and make it invalid
    board[0][2] = 2
    is_valid_sudoku = is_sudoku_valid(board)
    assert is_valid_sudoku is False
The faulty playfield of the second test case looks like this and the problematic value is marked in bold:
1 2 2 4 5 0 7 8 9
0 5 6 7 0 9 0 2 3
7 8 0 1 2 3 4 5 6
2 1 4 0 6 0 8 0 7
3 6 0 8 9 7 2 1 4
0 9 7 0 1 4 3 6 0
5 3 1 6 0 2 9 0 8
6 0 2 9 7 8 5 3 1
9 7 0 0 3 1 6 4 2

6.3.10 Solution 10: Flood Fill (★★✩✩✩)

Exercise 10a (★★✩✩✩)

Write function flood_fill(values2dim, start_x, start_y) that fills all free fields in an array or a two-dimensional nested list with a specified value.

Example

The following shows the filling process for the character *. The filling starts at a given position, such as the upper left corner. It continues in all four compass directions until the boundaries of the array or a boundary represented by another character are found.
"   # "      "***# "   "   #     # "      "   #******# "
"    #"      "****#"   "    #     #"      "    #******#"
"#   #"  =>  "#***#"   "#   #    # "  =>  "#   #*****# "
" # # "      " #*# "   " # #    #  "      " # #*****#  "
"  #  "      "  #  "   "  #   #    "      "  #*****#   "
Algorithm Recursively check the neighboring cells in the four cardinal directions. If a field is empty, it gets filled and the check it repeated. If you reach the array boundaries or a filled cell, you stop. This can be expressed recursively in an elegant way.
def flood_fill(values2dim, x, y):
    max_y, max_x = get_dimension(values2dim)
    # recursive termination
    if x < 0 or y < 0 or x >= max_x or y >= max_y:
        return
    if values2dim[y][x] == ' ':
        values2dim[y][x] = '*'
    # recursive descent: fill all 4 directions
    flood_fill(values2dim, x, y - 1)
    flood_fill(values2dim, x + 1, y)
    flood_fill(values2dim, x, y + 1)
    flood_fill(values2dim, x - 1, y)

Verification

Now let’s define the array shown in the introduction as a starting point and then perform a flood fill with different starting locations.
def create_world_and_expected_fills():
    first_world = [list("   # "),
                   list("    #"),
                   list("#   #"),
                   list(" # # "),
                   list("  #  ")]
    first_filled = [list("***#  "),
                    list("****# "),
                    list("#***# "),
                    list(" #*#  "),
                    list("  #   ")]
    second_world = [list("   #     # "),
                    list("    #     #"),
                    list("#   #    # "),
                    list(" # #    #  "),
                    list("  #   #    ")]
    second_filled = [list("  #******#"),
                    list("    #******#"),
                    list("#   #*****# "),
                    list(" # #*****#  "),
                    list("  #*****#   ")]
    return [(first_world, first_filled, 0, 0,),
             (second_world, second_filled, 4, 4)]
@pytest.mark.parametrize("world, expected, start_x, start_y",
                         create_world_and_expected_fills())
def test_flood_fill(world, expected, start_x, start_y):
    flood_fill(world, start_x, start_y)
    assert world == expected

Solution 10b (★★✩✩✩)

Extend the function to fill any pattern passed as a rectangular array. Spaces are not allowed in the pattern specification.

Example

The following is an impression of how a flood fill with a pattern could look. The pattern consists of several lines with characters:
.|.
-*-
.|.
If the filling starts at the bottom center, you get the following result:
       X        .|..|.x
     #  #       -*--#--#
    ###  #      .|.###.|#
#   ###  #  =>  #|.###.|#
#   #    #      #*--#--*#
 # #    #        #.#|..#
  #   #           #.|.#
Algorithm What needs to be changed to support a pattern? First of all, you must pass the desired pattern to the function. Interestingly, the fill algorithm remains almost the same and is only modified concerning the fill character’s determination. Instead of a fixed value, the helper function find_fill_char() is invoked here, which determines the fill character relevant for the position. The recursive descent is expressed elegantly by using an enumeration for the directions as an alternative to the four individual calls show before.
def flood_fill_with_pattern(values2dim, x, y, pattern):
    max_y, max_x = get_dimension(values2dim)
    # recursive termination
    if x < 0 or y < 0 or x >= max_x or y >= max_y:
        return
    if values2dim[y][x] == ' ':
        # determine appropriate fill character
        values2dim[y][x] = find_fill_char(y, x, pattern)
        # recursive descent in 4 directions
        for dir in Direction:
            dy, dx = dir.value
            flood_fill_with_pattern(values2dim, x + dx, y + dy, pattern)
class Direction(Enum):
    UP = (-1, 0)
    DOWN = (1, 0)
    LEFT = (0, -1)
    RIGHT = (0, 1)
Now let’s determine the fill character based on the current position in relation to the width or the height of the playfield array using a simple modulo calculation:
def find_fill_char(y, x, pattern):
    max_y, max_x = get_dimension(pattern)
    return pattern[y % max_y][x % max_x]

Verification

Analogous to before, you would like to fill the array with delimiters presented in the introduction with the pattern shown before. Therefore, you provide functions to generate patterns:
def generate_pattern():
    return [list(".|."),
            list("-*-"),
            list(".|.")]
def generate_big_world():
    return [[" ", " ", " ", " ", " ", " ", "x", " ", " "],
             [" ", " ", " ", " ", "#", " ", " ", "#", " "],
             [" ", " ", " ", "#", "#", "#", " ", " ", "#"],
             ["#", " ", " ", "#", "#", "#", " ", " ", "#"],
             ["#", " ", " ", " ", "#", " ", " ", " ", "#"],
             [" ", "#", " ", "#", " ", " ", " ", "#", " "],
             [" ", " ", "#", " ", " ", " ", "#", " ", " "]]
For testing, you generate the initial pattern and call the flood fill with the pattern:
>>> world = generate_big_world()
>>> flood_fill_with_pattern(world, 1, 1, generate_pattern())
For control purposes, you now print out the array. This allows you to examine the filling with the respective pattern.
>>> print_array(world)
.|..|.x
-*--#--#
.|.###.|#
#|.###.|#
#*--#--*#
 #.#|..#
  #.|.#
def print_array(values2dim):
    max_y, max_x = get_dimension(values2dim)
    for y in range(max_y):
        for x in range(max_x):
            value = values2dim[y][x]
            print(str(value) + " ", end='')
        print()

6.3.11 Solution 11: Array Min and Max (★★✩✩✩)

Solution 11a: Min and Max (★✩✩✩✩)

Write two functions find_min(values) and find_max(values) that search for the minimum and maximum, respectively, of a given non-empty array using a self-implemented search, thus eliminating the usage of built-ins like min() and sort(). :-)

Example

Input

Minimum

Maximum

[2, 3, 4, 5, 6, 7, 8, 9, 1, 10]

1

10

Algorithm Loop through the array from the beginning. In both cases, assume that the first element is the minimum or maximum. The array is traversed from front to back, searching for a smaller or larger element. If such a candidate is found, the minimum or maximum gets reassigned.
def find_min(values):
    if len(values) == 0:
        raise ValueError("find_min not supported for empty input")
    min = values[0]
    for i in range(1, len(values)):
        if values[i] < min:
            min = values[i]
    return min
def find_max(values):
    if len(values) == 0:
        raise ValueError("find_max not supported for empty input")
    max = values[0]
    for i in range(1, len(values)):
        if values[i] > max:
            max = values[i]
    return max

Due to the boundary condition of a non-empty output array, you can always start with the first element as minimum or maximum.

Solution 11b: Min und Max Pos (★★✩✩✩)

Implement two helper functions find_min_pos(values, start, end) and find-_max_pos(values, start, end) that seek and return the position of the minimum and maximum, respectively. Again, assume a non-empty array and additionally an index range of left and right boundaries. In the case of several identical values for minimum or maximum, the first occurrence should be returned.

To find the minimum and maximum values, respectively, write two functions find_min_by_pos(values, start, end) and find_max_by_pos(values, start, end) that use the helper function.

Examples

Method

Input

Range

Result

Position

find_min_xyz()

[5, 3, 4, 2, 6, 7, 8, 9, 1, 10]

0, 10

1

8

find_min_xyz()

[5, 3, 4, 2, 6, 7, 8, 9, 1, 10]

0, 7

2

3

find_min_xyz()

[5, 3, 4, 2, 6, 7, 8, 9, 1, 10]

2, 7

2

3

find_max_xyz()

[1, 22, 3, 4, 5, 10, 7, 8, 9, 49]

0, 10

49

9

find_max_xyz()

[1, 22, 3, 4, 5, 10, 7, 8, 9, 49]

0, 7

22

1

find_max_xyz()

[1, 22, 3, 4, 5, 10, 7, 8, 9, 49]

2, 7

10

5

Algorithm Based on the determined position of the minimum or maximum, the appropriate return of the corresponding element can be implemented trivially:
def find_min_by_pos(values, start, end):
    min_pos = find_min_pos(values, start, end)
    return values[min_pos]
def find_max_by_pos(values, start, end):
    max_pos = find_max_pos(values, start, end)
    return values[max_pos]
To complete the process, you still need to determine the position of the minimum and maximum. For this, proceed as follows: To find the respective position of minimum and maximum, go through all elements, compare with the current value for minimum or maximum, and update the position if the value is smaller or larger.
def find_min_pos(values, start, end):
    if len(values) == 0:
        raise ValueError("find_min_pos not supported for empty input")
    if start < 0 or start > end or end > len(values):
        raise ValueError("invalid range")
    min_pos = start
    for i in range(start + 1, end):
        if values[i] < values[min_pos]:
            min_pos = i
    return min_pos
def find_max_pos(values, start, end):
    if len(values) == 0:
         raise ValueError("find_max_pos not supported for empty input")
    if start < 0 or start > end or end > len(values):
        raise ValueError("invalid range")
    max_pos = start
    for i in range(start + 1, end):
         if values[i] > values[max_pos]:
             max_pos = i
    return max_pos

Verification

Test the functionality as usual with the inputs from the introduction:
def test_find_min_and_max():
    values = [ 2, 3, 4, 5, 6, 7, 8, 9, 1, 10 ]
    assert find_min(values) == 1
    assert find_max(values) == 10
@pytest.mark.parametrize("lower, upper, expected_pos, expected_value",
                         [(0, 10, 8, 1), (2, 7, 3, 2), (0, 7, 3, 2)])
def test_find_min_pos(lower, upper, expected_pos, expected_value):
    values = [ 5, 3, 4, 2, 6, 7, 8, 9, 1, 10 ]
    result_pos = find_min_pos(values, lower, upper)
    assert result_pos == expected_pos
    assert values[result_pos] == expected_value
@pytest.mark.parametrize("lower, upper, expected_pos, expected_value",
                         [(0, 10, 9, 49), (2, 7, 5, 10), (0, 7, 1, 22)])
def test_find_max_pos(lower, upper, expected_pos, expected_value):
    values = [ 1, 22, 3, 4, 5, 10, 7, 8, 9, 49 ]
    result_pos = find_max_pos(values, lower, upper)
    assert result_pos == expected_pos
    assert values[result_pos] == expected_value

6.3.12 Solution 12: Array Split (★★★✩✩)

Say you have an array (or list) of arbitrary integers. The data structure must be reordered so that all values less than a special reference value are placed on the left. All values greater than or equal to the reference value are placed on the right. The ordering within the subranges is not relevant and may vary.

Examples

Input

Reference element

Sample result

[4, 7, 1, 20]

9

[1, 4, 7, 9, 20]

[3, 5, 2]

7

[2, 3, 5, 7]

[2, 14, 10, 1, 11, 12, 3, 4]

7

[2, 1, 3, 4, 7, 14, 10, 11, 12]

[3, 5, 7, 1, 11, 13, 17, 19]

11

[1, 3, 5, 7, 11, 11, 13, 17, 19]

Solution 12a: Array Split (★★✩✩✩)

Write function array_split(values, reference_element) to implement the functionality described above. In this first part of the exercise, it is allowed to create new data structures, such as lists.

Algorithm To split an array according to a reference element into two halves with values less than or greater than or equal to the reference value, you define two result lists called lesser and bigger_or_equal. Afterwards, you iterate through the array. Depending on the comparison of the current element with the reference element, you populate one of the two lists. Finally, you only need to combine the lists and the reference element into one result list.
def array_split(values, reference_element):
    lesser = []
    bigger_or_equal = []
    for current in values:
        if current < reference_element:
            lesser.append(current)
        else:
            bigger_or_equal.append(current)
    return lesser + [reference_element] + bigger_or_equal
Pythonic algorithm In the solution shown, the for loop with the if and else is stylistically somewhat disturbing. With list comprehensions, this could be implemented a bit nicer as follows. In this alternative, however, the lists are traversed twice.
def array_split_nicer(values, reference_element):
    lesser = [value for value in values
             if value < reference_element]
    bigger_or_equal = [value for value in values
                      if value >= reference_element]
    return lesser + [reference_element] + bigger_or_equal

Solution 12b: Array Split Inplace (★★★✩✩)

Write function array_split_inplace(values, reference_element) that implements the functionality described inside the source array (i.e., inplace). It is explicitly not desirable to create new data structures. To be able to include the reference element in the result, the creation of an array is allowed once for the result. Because this has to be returned, it is permitted to return a value for an inplace function; indeed, it operates only partially inplace here.

Algorithm After you perform the simpler version, which improves your understanding of the processes, dare to try the inplace version! Here you cannot use auxiliary data structures. Rather, you implement the logic by swapping elements several times. Two position markers indicate which elements are to be swapped. The first position marker is increased as long as you encounter smaller values than the reference element, starting from the beginning. You do the same with the position marker for the upper part. As long as the values are larger than or equal to the reference element, you decrease the position. Finally, you swap the two values at the index positions found, but only if the position markers have not yet crossed. When crossing, you find no more mismatching elements. The last thing to do is to integrate the reference element at the correct position based on the newly arranged values. Some care has to be taken if the sequence of the higher elements is empty.
def array_split_inplace(values, reference_element):
    low = 0
    high = len(values) - 1
    while low < high:
        while low < high and values[low] < reference_element:
            low += 1
        while high > low and values[high] >= reference_element:
            high -= 1
        if low < high:
            swap(values, low, high)
    if len(values[high + 1:]) == 0:
         return values[:high + 1] + [reference_element]
    else:
        return values[:high] + [reference_element] + values[high:]

Solution 12c: Array Split Quick Sort Partition (★★★✩✩)

For sorting according to Quick Sort, you need a partitioning functionality similar to the one just developed. However, often the foremost element of the array is used as the reference element.

Based on the two previously developed implementations that use an explicit reference element, your task is to create corresponding alternatives such as the functions array_split_qs(values) and array_split_qs_inplace(values).

Examples

Input

Reference element

Sample result

[9, 4, 7, 1, 20]

9

[1, 4, 7, 9, 20]

[7, 3, 5, 2]

7

[2, 3, 5, 7]

[7, 2, 14, 10, 1, 11, 12, 3, 4]

7

[2, 1, 3, 4, 7, 14, 10, 11, 12]

[11, 3, 5, 7, 1, 11, 13, 17, 19]

11

[1, 3, 5, 7, 11, 11, 13, 17, 19]

Algorithm 1 When the element at position 0 acts as reference element, this is the only thing that must be taken into account in the implementation. Thus, the processing starts at index 1.
def array_split_qs(values):
    reference_value = values[0]
    lesser = [values[i] for i in range(1, len(values))
             if values[i] < reference_value]
    bigger_or_equal = [values[i] for i in range(1, len(values))
                      if values[i] >= reference_value]
    return lesser + [reference_value] + bigger_or_equal
Algorithm 2 The inplace variant also works with two position markers as before and swaps elements several times if necessary. This is repeated as long as the position markers have not yet crossed. In this particular situation, you no longer find any unsuitable elements. The last thing to do is to move the reference element from its position 0 to the crossover point (i.e., the matching position).
def array_split_qs_inplace(values):
    reference_value = values[0]
    low = 1
    high = len(values) - 1
    while low < high:
        while values[low] < reference_value and low < high:
            low += 1
        while values[high] >= reference_value and high >= low:
            high -= 1
        if low < high:
            swap(values, low, high)
    # important for two elements with values 1, 2 = > then 1 would be pivot, do
        not swap!
    if reference_value > values[high]:
        swap(values, 0, high)

Please remember that this function works inplace (meaning it operates directly on the passed data) and therefore does not return a result.

Verification

Test the functionality as usual with the inputs from the introduction:
>>> values = [2, 14, 10, 1, 11, 12, 3, 4]
>>> array_split(values, 7)
[2, 1, 3, 4, 7, 14, 10, 11, 12]
>>> array_split_inplace(values, 7)
[2, 4, 3, 1, 7, 12, 10, 14]
Let’s have a look at the Quick Sort variants in action:
>>> values2 = [7, 2, 14, 10, 1, 11, 3, 12, 4]
>>> array_split_qs(values2)
[2, 1, 3, 4, 7, 14, 10, 11, 12]
>>> array_split_qs_inplace(values2)
>>> values2
[1, 2, 4, 3, 7, 11, 10, 12, 14]

Due to the slightly different algorithm, the elements in the first variant remain in the order in which they appear in the original array. The inplace variants swap elements, and thus there is a reshuffle. However, all smaller values are still found to the left of the reference element and all larger ones to the right.

6.3.13 Solution 13: Minesweeper Board (★★★✩✩)

Chances are high that you’ve played Minesweeper in the past. To remind you, it’s a nice little quiz game with a bit of puzzling. What is it about? Bombs are placed face down on a playfield. The player can choose any field on the board. If a field is uncovered, it shows a number. This indicates how many bombs are hidden in the neighboring fields. However, if you are unlucky, you hit a bomb field and lose the game. Your task is about initializing such a field and preparing it for a subsequent game.

Solution 13a (★★✩✩✩)

Write function place_bombs_randomly(width, height, probability) that creates a playfield specified in size via the first two parameters, randomly filled with bombs, respecting the probability from 0.0 to 1.0 passed in.

Example

The following is a playfield of size 16 × 7 with bombs placed randomly. Bombs are represented by asterisks (*) and spaces by dots (.).
* * * . * * . * . * * . * . . .
. * * . * . . * . * * . . . . .
. . * . . . . . . . . . * * * *
. . . * . * * . * * . * * . . .
* * . . . . * . * . . * . . . *
. . * . . * . * * . . * . * * *
. * . * * . * . * * * . . * * .
Algorithm Placing bombs randomly distributed in a playfield works as follows. For each position, a random number generated with random.random() and a given probability are used to determine whether a bomb should be placed on the playfield. As a result, a suitable nested list is generated. Here, a peculiarity is found, namely the playfield extends in all directions by one position each, as is covered in the following practical tip.
def place_bombs_randomly(width, height, probability):
    bombs = [[False for x in range(width + 2)] for y in range(height + 2)]
    for y in range(1, len(bombs) - 1):
        for x in range(1, len(bombs[0]) - 1):
            bombs[y][x] = random.random() < probability
    return bombs
NOTE: PLAYFIELD WITH BORDER

For many two-dimensional algorithms, it is necessary to perform special checks at the borders. In some cases, it is helpful to place a special artificial border of one position around the actual playfield. In particular, this often simplifies calculations with neighboring cells in all compass directions, as is the case here with the bombs. But you have to assign a neutral value to the border cells. Here this is simply the value 0. Sometimes, however, special characters like # can be used with str-based playfields.

Some calculations become easier with this artificial boundary cell. However, you must then note that the bounds range from 1 to len() - 1—an additional stumbling block to the treacherous off-by-one errors commonly made with arrays.

Verification

Let’s omit explicit testing here because, on the one hand, you are dealing with random numbers, and a unit test does not directly make sense for this. On the other hand, the algorithm is quite simple and the functionality is tested indirectly later.

Solution 13b (★★★✩✩)

Write function calc_bomb_count(bombs) that computes the number of adjacent fields based on the bomb fields passed and returns a corresponding array.

Examples

A calculation for playfields of size 3 × 3 as well as size 5 × 5, including randomly distributed bombs, results in the following:
* . .      B 2 1     . * * . .      2 B B 3 1
. . *  =>  1 3 B     * . * * .      B 6 B B 1
. . *      0 2 B     * * . . .  =>  B B 4 3 2
                     * . . * .      B 6 4 B 1
                     * * * . .      B B B 2 1
Algorithm To calculate the number of neighboring cells with bombs, you again consider each cell in turn. Here you take advantage of the special margin, so you don’t have to do range checks or special handling. First, you initialize a two-dimensional array of appropriate size with a value of 0 as an assumption that there are no bombs in the neighborhood. If a cell represents a bomb, you use the value 9 as an indicator. If it does not contain one, you must check all eight neighboring cells to see if they are home to a bomb. In this case, the bomb counter is increased by one. The calculation is facilitated by the use of the already known enumeration for the compass directions and their delta values in the x- and y-directions.
def calc_bomb_count(bombs):
    max_y, max_x = get_dimension(bombs)
    bomb_count = [[0 for x in range(max_x)] for y in range(max_y)]
    for y in range(1, max_y - 1):
        for x in range(1, max_x - 1):
            if not bombs[y][x]:
                for current_dir in Direction:
                     dx, dy = current_dir.to_dx_dy()
                    if bombs[y + dy][x + dx]:
                         bomb_count[y][x] += 1
            else:
                 bomb_count[y][x] = 9
    return bomb_count
For better comprehension, the enumeration Direction is shown here again:
from enum import Enum
class Direction(Enum):
    N = (0, -1)
    NE = (1, -1)
    E = (1, 0)
    SE = (1, 1)
    S = (0, 1)
    SW = (-1, 1)
    W = (-1, 0)
    NW = (-1, -1)
    def to_dx_dy(self):
        return self.value

Verification

To check the implementation, use the 3 × 3 distribution, but you must consider the boundary cells accordingly. Until now, modeling of bombs was based on a two-dimensional nested list of bool. Wouldn’t it be more practical to work on graphical representations and have them convert appropriately? Let’s consider this as a unit test.
def create_bomb_array_and_expected():
    bombs1 = ["*..",
              "..*",
              "..*"]
    result1 = ["B21",
               "13B",
               "02B"]
    bombs2 = [".**..",
              "*.**.",
              "**...",
              "*..*.",
              "***.."]
    result2 = ["2BB31",
               "B6BB1",
               "BB432",
               "B64B1",
               "BBB21"]
    return [(to_bool_array(bombs1), to_int_array(result1)),
        (to_bool_array(bombs2), to_int_array(result2))]
@pytest.mark.parametrize("bombs, expected",
                         create_bomb_array_and_expected())
def test_calc_bomb_count(bombs, expected):
    result = calc_bomb_count(bombs)
    assert result == expected

Let’s look again at the helper functions. First, you have a textual representation of the distribution of bombs, which is converted into the required array data structure using to_bool_array(). In doing so, you don’t have to worry about generating the boundary fields. The helper function to_int_array() goes one step further and converts the textual digits into the corresponding int values and takes into account the representation of bombs as B specifically.

The helper functions look like this:
# hiding the border field logic and conversion
def to_bool_array(bombs):
    width = len(bombs[0])
    height = len(bombs)
    result = [[False for _ in range(width + 2)] for _ in range(height + 2)]
    for y in range(height):
        for x in range(width):
            if bombs[y][x] == '*':
                result[y + 1][x + 1] = True
    return result
def to_int_array(values):
    width = len(values[0])
    height = len(values)
    result = [[0 for _ in range(width + 2)] for _ in range(height + 2)]
    for y in range(height):
        for x in range(width):
            current_char = values[y][x]
            if current_char == 'B':
                 result[y + 1][x + 1] = 9
            else:
                 result[y + 1][x + 1] = int(current_char)
    return result
HINT: READABILITY AND COMPREHENSIBILITY IN TESTING

These two helper functions enable the creation of test cases to be kept simple and understandable. This makes it more likely that someone will extend the tests. If writing unit tests is rather tedious or even difficult, hardly anyone will bother to extend them.

Solution 13c (★★✩✩✩)

Write function print_board(bombs, bomb_symbol, bomb_counts) that allows you to display a board as points and stars as well as numbers and B.

Example

The following is the above playfield of size 16 × 7 with all the calculated values for bomb neighbors:
B B B 4 B B 3 B 4 B B 3 B 1 0 0
3 B B 5 B 3 3 B 4 B B 4 3 4 3 2
1 3 B 4 3 3 3 3 4 4 4 4 B B B B
2 3 3 B 2 B B 4 B B 3 B B 4 4 3
B B 3 2 3 4 B 6 B 4 4 B 5 3 4 B
3 4 B 3 3 B 4 B B 5 4 B 4 B B B
1 B 3 B B 3 B 4 B B B 2 3 B B 3
Algorithm For rendering, you use position-based processing. Since you want to implement both an output based on the bool model and, if passed, the values of the number of bomb neighbors in this function, a few cases have to be provided in addition to the loops nested for the x-direction and the y-direction.
def print_board(bombs, bomb_symbol, solution):
    for y in range(1, len(bombs) - 1):
        for x in range(1, len(bombs[0]) - 1):
            if bombs[y][x]:
                print(bomb_symbol, end=" ")
            elif solution is not None and len(solution) != 0:
                print(solution[y][x], end=" ")
            else:
                print(".", end=" ")
        print()
    print()

Verification

Let’s combine the three functions to experience the functionality in its entirety:
>>> import random
>>> from enum import Enum
>>> bombs = place_bombs_randomly(16, 7, 0.4)
>> print_board(bombs, '*', None)
. * * * * . * . * . * . * * . .
. . * . * * . . . * * * . . * *
. . * . . . * . * * * * . . . .
* . . * . . . * * * . * * . * .
. . * . * . . . . . . * * * . *
* . . . . * * * . . * . . * * .
* * * . * . * * * * . . . . . *
>>> solution = calc_bomb_count(bombs)
>>> print_board(bombs, 'B', solution)
1 B B B B 4 B 2 B 4 B 4 B B 3 2
1 4 B 6 B B 3 4 4 B B B 4 3 B B
1 3 B 4 3 3 B 4 B B B B 4 3 3 3
B 3 3 B 2 2 2 B B B 6 B B 4 B 2
2 3 B 3 B 3 4 4 4 3 4 B B B 5 B
B 5 3 4 3 B B B 4 3 B 3 4 B B 3
B B B 2 B 4 B B B B 2 1 1 2 3 B

Summary: What You Learned

Just like strings, arrays are basic building blocks in many programming languages. In Python, lists are often favored, since arrays are not nicely supported in the language. However, there is a valid alternative with NumPy, with which arrays can be easily defined and which can offer significant performance improvements compared to lists. Anyway, it is important to avoid tricky off-by-one errors. In this chapter, you created small helper functions that, when used appropriately, can make algorithms more understandable. For two-dimensional arrays or nested lists, you learned, among other things, how to model directions and how this helps fill areas with patterns. More challenging tasks were the spiral traversal as well as the deletion and filling of a Jewels or Minesweeper playfield.

This chapter concludes the treatment of essential Python language tools and data structures. Now you turn to more complex topics and start with advanced techniques for recursion.

..................Content has been hidden....................

You can't read the all page of ebook, please click here login for view all page.
Reset