Ask Your Question
2

Solving an optimization problem by Sage

asked 2018-07-16 10:04:04 -0500

mathhobbyist gravatar image

updated 2018-07-16 23:44:03 -0500

I would like to know how one can solve the following optimization problem using Sage.

I would like to have a matrix where every element is an integer from 0 to 9. One can read numbers from the matrix by choosing the starting element and direction from one of the eight direction (horizontal, vertical, diagonal) and go to that direction 0 to 5 steps and concatenate the numbers.

For example, one can read the squares of 1 to 10 from the following matrix:

0 0 1 8 2
3 6 4 9 5

Now the problem is to find an $n\times m$ matrix with digits from 0 to 9 where one can read the squares of 1 to 100 in a way described above where $nm$ is the smallest possible. How can I do that on Sage? I would like to see how good result we can achieve.

edit retag flag offensive close merge delete

Comments

General note : this marvelous book has a nice set of discussions about various optimization problems...

Emmanuel Charpentier gravatar imageEmmanuel Charpentier ( 2018-07-18 01:50:44 -0500 )edit

1 answer

Sort by ยป oldest newest most voted
0

answered 2018-07-17 12:36:35 -0500

Nice problem! Here is a brute force solution. First we define some convenient helper functions:

import itertools

def digit_matrix_to_digit_positions(M):
    positions = { d: [] for d in range(0,10)}
    for i in range(0, M.nrows()):
        for j in range(0, M.ncols()):
            positions[M[i,j]].append((i,j))
    return positions

def digit_paths_for_number(digit_positions, number):
    digits = map(int, str(number))
    return itertools.product(*[digit_positions[d] for d in digits])

def is_digit_path_allowed(path):
    if len(path) == 0: return False
    if len(path) == 1: return True
    # determine direction of path
    first, second = path[0], path[1]
    direction = (second[0]-first[0], second[1]-first[1])
    # check if direction is valid
    if not all(d in [-1,0,1] for d in direction): return False
    # check if the rest of the path goes in this direction
    if len(path) == 2: return True
    return all((path[i][0]-path[i-1][0], path[i][1]-path[i-1][1]) == direction for i in range(2, len(path)))

def digit_matrix_contains_numbers(M, numbers):
    digit_positions = digit_matrix_to_digit_positions(M)
    for number in numbers:
        if len(filter(is_digit_path_allowed, digit_paths_for_number(digit_positions, number))) == 0:
            return False
    return True

Now we can e.g. verify your example:

sage: M = Matrix(ZZ, [[0,0,1,8,2], [3,6,4,9,5]])
sage: digit_matrix_contains_numbers(M, [x^2 for x in range(0, 11)])
True
sage: filter(is_digit_path_allowed, digit_paths_for_number(digit_matrix_to_digit_positions(M), 100))
[((0, 2), (0, 1), (0, 0))]

To find the smallest digit matrix with this property, we iterate over $n\times m$ digit matrices with $N=nm \geq 9$:

numbers = [x^2 for x in range(0, 11)]
needed_digits = set(sum((map(int,str(y)) for y in numbers), []))
found = False
N = len(needed_digits)
while True:
    for n in divisors(N):
        m = N/n
        if m < n: continue # equivalent to m x n anyway
        print 'Trying', n, 'x', m
        for matrix_entries in itertools.product(range(0,10), repeat=n*m):
            if len(needed_digits & set(matrix_entries)) < len(needed_digits): continue
            matrix = Matrix(ZZ, [[matrix_entries[i*m+j] for j in range(0,m)] for i in range(0,n)])
            if digit_matrix_contains_numbers(matrix, numbers):
                found = True
                print 'Found one!'
                print matrix
                break
        if found: break
    if found: break
    N += 1

The output after several hours is:

Trying 1 x 9
Trying 3 x 3
Trying 1 x 10
Trying 2 x 5
Found one!
[0 0 1 3 2]
[9 4 6 8 5]

So $2 \times 5$ (or $5 \times 2$ after transposition) is minimal. You can also let the code print all the solutions, if you want.

It would be interesting to see other approaches.

edit flag offensive delete link more

Comments

1

Thanks for that! I think this proves the minimality of the example. But the case I would like to solve is much bigger. I think it might be solved by genetic algorithm of by simulated annealing but I have no experience of implementing those.

mathhobbyist gravatar imagemathhobbyist ( 2018-07-18 10:54:48 -0500 )edit

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools

1 follower

Stats

Asked: 2018-07-16 10:04:04 -0500

Seen: 169 times

Last updated: Jul 17