ASKSAGE: Sage Q&A Forum - Individual question feedhttp://ask.sagemath.org/questions/Q&A Forum for SageenCopyright Sage, 2010. Some rights reserved under creative commons license.Tue, 19 Mar 2019 12:16:57 -0500Solving an optimization problem by Sagehttp://ask.sagemath.org/question/43038/solving-an-optimization-problem-by-sage/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? Can Sage do it for example in the case 12x10 griid? Does for example simulated annealing or genetic algorithm work in here, or is it easy to implement the algorithm in https://stackoverflow.com/questions/943113/algorithm-to-generate-a-crossword ? I would like to see how good result we can achieve.Mon, 16 Jul 2018 10:04:04 -0500http://ask.sagemath.org/question/43038/solving-an-optimization-problem-by-sage/Comment by Emmanuel Charpentier for <p>I would like to know how one can solve the following optimization problem using Sage.</p>
<p>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.</p>
<p>For example, one can read the squares of 1 to 10 from the following matrix:</p>
<pre><code>0 0 1 8 2
3 6 4 9 5
</code></pre>
<p>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? Can Sage do it for example in the case 12x10 griid? Does for example simulated annealing or genetic algorithm work in here, or is it easy to implement the algorithm in <a href="https://stackoverflow.com/questions/943113/algorithm-to-generate-a-crossword">https://stackoverflow.com/questions/9...</a> ? I would like to see how good result we can achieve.</p>
http://ask.sagemath.org/question/43038/solving-an-optimization-problem-by-sage/?comment=43060#post-id-43060General note : this [marvelous book](http://sagebook.gforge.inria.fr/english.html) has a nice set of discussions about various optimization problems...Wed, 18 Jul 2018 01:50:44 -0500http://ask.sagemath.org/question/43038/solving-an-optimization-problem-by-sage/?comment=43060#post-id-43060Answer by mathhobbyist for <p>I would like to know how one can solve the following optimization problem using Sage.</p>
<p>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.</p>
<p>For example, one can read the squares of 1 to 10 from the following matrix:</p>
<pre><code>0 0 1 8 2
3 6 4 9 5
</code></pre>
<p>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? Can Sage do it for example in the case 12x10 griid? Does for example simulated annealing or genetic algorithm work in here, or is it easy to implement the algorithm in <a href="https://stackoverflow.com/questions/943113/algorithm-to-generate-a-crossword">https://stackoverflow.com/questions/9...</a> ? I would like to see how good result we can achieve.</p>
http://ask.sagemath.org/question/43038/solving-an-optimization-problem-by-sage/?answer=45840#post-id-45840There is a Python program to solve 11x11 case in https://stackoverflow.com/questions/3382859/solving-a-recreational-square-packing-problemTue, 19 Mar 2019 12:16:57 -0500http://ask.sagemath.org/question/43038/solving-an-optimization-problem-by-sage/?answer=45840#post-id-45840Answer by rburing for <p>I would like to know how one can solve the following optimization problem using Sage.</p>
<p>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.</p>
<p>For example, one can read the squares of 1 to 10 from the following matrix:</p>
<pre><code>0 0 1 8 2
3 6 4 9 5
</code></pre>
<p>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? Can Sage do it for example in the case 12x10 griid? Does for example simulated annealing or genetic algorithm work in here, or is it easy to implement the algorithm in <a href="https://stackoverflow.com/questions/943113/algorithm-to-generate-a-crossword">https://stackoverflow.com/questions/9...</a> ? I would like to see how good result we can achieve.</p>
http://ask.sagemath.org/question/43038/solving-an-optimization-problem-by-sage/?answer=43050#post-id-43050Nice 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.Tue, 17 Jul 2018 12:36:35 -0500http://ask.sagemath.org/question/43038/solving-an-optimization-problem-by-sage/?answer=43050#post-id-43050Comment by mathhobbyist for <p>Nice problem! Here is a brute force solution. First we define some convenient helper functions:</p>
<pre><code>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
</code></pre>
<p>Now we can e.g. verify your example:</p>
<pre><code>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))]
</code></pre>
<p>To find the smallest digit matrix with this property, we iterate over $n\times m$ digit matrices with $N=nm \geq 9$:</p>
<pre><code>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
</code></pre>
<p>The output after several hours is:</p>
<pre><code>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]
</code></pre>
<p>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.</p>
<p>It would be interesting to see other approaches.</p>
http://ask.sagemath.org/question/43038/solving-an-optimization-problem-by-sage/?comment=43073#post-id-43073Thanks 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.Wed, 18 Jul 2018 10:54:48 -0500http://ask.sagemath.org/question/43038/solving-an-optimization-problem-by-sage/?comment=43073#post-id-43073