Rectangle filling program

Question

There is a problem on the internet in [this SO post] (https://stackoverflow.com/q/44983929):

Prove that there is a matrix with 117 elements containing the digits such that one can read the squares of the numbers 1, 2, ..., 100.

Here read means that you fix the starting position and direction (8 possibilities) and then go in that direction, concatenating the numbers. For example, if you can find for example the digits 1,0,0,0,0,4 consecutively, you have found the integer 100004, which contains the square numbers of 1, 2, 10, 100 and 20, since you can read off 1, 4, 100, 10000, and 400 (reversed) from that sequence.

I tried to make a program for that. I managed to make a function that checks if a number can be placed into a board and another that measures how good is a place where one puts the number, i.e. how many uncovered squares the new number covers. But how can I remove the duplicate code?

# -*- coding: utf-8 -*-

def can_put_on_grid(grid, number, start_x, start_y, direction):
#   Check that the new number lies inside the grid.
    if start_x < 0 or start_x > len(grid[0]) - 1 or start_y < 0 or start_y > len(grid) - 1:
        return False
    end = end_coordinates(number, start_x, start_y, direction)
    if end[0] < 0 or end[0] > len(grid[0]) - 1 or end[1] < 0 or end[1] > len(grid) - 1:
        return False
#   Test if new number does not intersect any previous number.
    for i in range(0,len(number)):
        if direction == 0:
            if number[i] != grid[start_x][start_y + i] and grid[start_x][start_y + i] != "X":
                return False
        elif direction == 1:
            if number[i] != grid[start_x - i][start_y - i] and grid[start_x - i][start_y - i] != "X":
                return False
        elif direction == 2:
            if number[i] != grid[start_x][start_y - i] and grid[start_x][start_y - i] != "X":
                return False
        elif direction == 3:
            if number[i] != grid[start_x + i][start_y - i] and grid[start_x + i][start_y - i] != "X":
                return False
        elif direction == 4:
            if number[i] != grid[start_x - i][start_y] and grid[start_x - i][start_y] != "X":
                return False
        elif direction == 5:
            if number[i] != grid[start_x + i][start_y + i] and grid[start_x + i][start_y + i] != "X":
                return False
        elif direction == 6:
            if number[i] != grid[start_x + i][start_y] and grid[start_x + i][start_y] != "X":
                return False
        elif direction == 7:
            if number[i] != grid[start_x - i][start_y + i] and grid[start_x - i][start_y + i] != "X":
                return False
    return True

def end_coordinates(number, start_x, start_y, direction):
    end_x = None
    end_y = None
    l = len(number)
    if direction in (1, 4, 7):
        end_x = start_x - l + 1
    if direction in (3, 6, 5):
        end_x = start_x + l - 1
    if direction in (2, 0):
        end_x = start_x
    if direction in (1, 2, 3):
        end_y = start_y - l + 1
    if direction in (7, 0, 5):
        end_y = start_y + l - 1
    if direction in (4, 6):
        end_y = start_y
    return (end_x, end_y)

# Greater is better.
def how_good_put(grid,number,start_x,start_y,direction):
    goodness = 0
    for i in range(0,len(str(number))):
        if direction == 0:
            if grid[start_x][start_y + i] != "X":
                goodness += 1
        elif direction == 1:
            if grid[start_x - i][start_y - i] != "X":
                goodness += 1            
        elif direction == 2:
            if grid[start_x][start_y - i] != "X":
                goodness += 1
        elif direction == 3:
            if rid[start_x + i][start_y - i] != "X":
                goodness += 1
        elif direction == 4:
            if grid[start_x - i][start_y] != "X":
                goodness += 1
        elif direction == 5:
            if grid[start_x + i][start_y + i] != "X":
                goodness += 1
        elif direction == 6:
            if grid[start_x + i][start_y] != "X":
                goodness += 1
        elif direction == 7:
            if grid[start_x - i][start_y + i] != "X":
                goodness += 1
    return goodness

if __name__ == "__main__":
    A = [['X' for x in range(13)] for y in range(9)]
    numbers = [str(i*i) for i in range(1, 101)]
    print(numbers)
    directions = [0,1,2,3,4,5,6,7]
    B = end_coordinates("123", 0,0,3)
    print (B)
    print(B[0])
    print(B[1])
    for i in directions:
        C = can_put_on_grid(A, "123", 0, 0, i)
        print(C)
        if C == True:
            D = how_good_put(A, "123", 0, 0, i)
            print(D)
    exit(0)

Answer 1

You should follow the DRY principle, i.e. "Don't repeat yourself". You have three regions, where it seems like you have to do different things, depending on the direction, so you explicitly put every case. These can be reduced by taking out what is different in the cases. This makes it less explicit, but more compact. So this is about finding the right trade-off between readability and compactness.

Two of these can be handled in the same way, namely your functions can_put_on_grid and how_good_put. While we are at it, you might want to try and come up with slightly shorter, but still descriptive, names. I would suggest something like can_put and move_quality, respectively, which I will use in this answer.

Lets start with move_quality.

def move_quality(grid, number, start_x, start_y, direction):
    """How good is it to put number at (start_x, start_y) + direction.
       Greater is better."""
    x, y = [(0, 1), (-1, -1), (0, -1), (1, -1),
            (-1, 0), (1, 1), (1, 0), (-1, 1)][direction]
    return sum(grid[start_x + i * x][start_y + i * y] != "X"
               for i in range(len(str(number))))

Here I added a docstring, explaining what this function does (you might want to check if that is actually what it does).

In addition, I created a list (which I use as a mapping here) to denote all possible cases of offsets for the different directions. Then I can just index into these cases with the actual direction at hand. This works, because all your cases actually do the same thing, just with different positions of the grid being tested.

I also used the fact that bools (True and False) are really just a convenience wrapper around integers (try evaluating True == 1 and False == 0)* in Python. Therefore True + True + False == 2 and we can just sum over an iterable of bools to get the number True within that iterable.

The iterable I used is a generator expression, which generates its values while they are being requested. The syntax is the same as for a list comprehension.

Finally, range starts at 0 by default, so range(0, len(str(number))) is the same as range(len(str(number))).

Now, the function can_put can benefit from the same thing:

def can_put(grid, number, start_x, start_y, direction):
    """Add your docstring here"""
    #   Check that the new number lies inside the grid.
    if start_x < 0 or start_x > len(grid[0]) - 1 or start_y < 0 or start_y > len(grid) - 1:
        return False
    end = end_coordinates(number, start_x, start_y, direction)
    if end[0] < 0 or end[0] > len(grid[0]) - 1 or end[1] < 0 or end[1] > len(grid) - 1:
        return False

    # Test if new number does not intersect any previous number.
    x, y = [(0, 1), (-1, -1), (0, -1), (1, -1),
            (-1, 0), (1, 1), (1, 0), (-1, 1)][direction]
    for i in range(len(number)):
        val = grid[start_x + i * x][start_y + i * y]
        if number[i] != val and val != "X":
            return False
    return True

---

The function end_coordinates is a bit more complicated, but uses the same principle. Only now we have three different cases for the dx, dy, which are stored in cases. For each direction, offsets contains the index in cases (for x and y), which contains the correct offset to use:

def end_coordinates(number, start_x, start_y, direction):
    l = len(number)
    # The three different cases
    cases = 0, 1 - l, l - 1
    # Mapping from direction to the cases, for (x, y)
    offsets = [(0, 2), (1, 1), (0, 1), (2, 1), (1, 0), (2, 2), (2, 0), (1, 2)]
    try:
        end_x = start_x + cases[offsets[direction][0]]
    except IndexError:
        end_x = None
    try:
        end_y = start_y + cases[offsets[direction][1]]
    except IndexError:
        end_y = None
    return end_x, end_y

Potentially wrong input via direction will raise a IndexError and set that end_x/y to None.

---

* Note that while this evaluates as True, 1 and True are not the same object. so True is 1 and False is 0 is False.