2
\$\begingroup\$

The problem is to design an structure which generates "uniformly" the next one in an initially zero matrix. Taking an arbitrary index i in the range [0,m-1] for any j where a[i,j] == 0.

It is, for example:

\begin{gather} \begin{bmatrix} 0 & 0 & 0\\ 0 & 0 & 0\\ 0 & 0 & 0\\ 0 & 0 & 0\\ \end{bmatrix} \to \begin{bmatrix} 1 & 0 & 0\\ 0 & 0 & 0\\ 0 & 0 & 0\\ 0 & 0 & 0\\ \end{bmatrix} \to \begin{bmatrix} 1 & 0 & 1\\ 0 & 0 & 0\\ 0 & 0 & 0\\ 0 & 0 & 0\\ \end{bmatrix}\\ \to\begin{bmatrix} 1 & 0 & 1\\ 1 & 0 & 0\\ 0 & 0 & 0\\ 0 & 0 & 0\\ \end{bmatrix} \to \begin{bmatrix} 1 & 1 & 1\\ 1 & 0 & 0\\ 0 & 0 & 0\\ 0 & 0 & 0\\ \end{bmatrix} \to \begin{bmatrix} 1 & 1 & 1\\ 1 & 1 & 0\\ 0 & 0 & 0\\ 0 & 0 & 0\\ \end{bmatrix}\\ \to\begin{bmatrix} 1 & 1 & 1\\ 1 & 1 & 0\\ 0 & 1 & 0\\ 0 & 0 & 0\\ \end{bmatrix} \to \begin{bmatrix} 1 & 1 & 1\\ 1 & 1 & 0\\ 1 & 1 & 0\\ 0 & 0 & 0\\ \end{bmatrix} \to \begin{bmatrix} 1 & 1 & 1\\ 1 & 1 & 1\\ 1 & 1 & 0\\ 0 & 0 & 0\\ \end{bmatrix} \to \cdots \to \begin{bmatrix} 1 & 1 & 1\\ 1 & 1 & 1\\ 1 & 1 & 1\\ 1 & 1 & 1\\ \end{bmatrix} \end{gather}

Where is the utility? This algorithm can be used for procedural generation in any tile game. Now, I'm not a game programmer but I found really annoying the tile generation of Audiosurf 2 so, I want to perhaps provide a better solution.

(Note that the ones can be replaced by a number located by its input order.)

(I know the implications of the player when he doesn't "tap" some tile but there are other alternatives.)

My solution is:

import numpy as np
import numpy.random as rd

class RandomMatrixGenerator():

    def __init__(self, m: int, n: int):
        self.m = m
        self.n = n
        self.matrix = np.zeros(shape=(m,n), dtype='int8')
        self.ones = np.ones(shape=(m,n), dtype='int8')

    def __put_next(self):
        j: int = rd.randint(0, self.n, dtype='int8')

        if self.ones[:,j].all() == self.matrix[:,j].all():
            self.__put_next()

        for i in range(self.m):
            if self.matrix[i, j] == 0:
                self.matrix[i, j] = 1
                return

    def put_next(self):
        if self.ones.all() == self.matrix.all():
            return
        self.__put_next()

# Mini test
gen = RandomMatrixGenerator(4, 5)

for i in range(4 * 5):
    gen.put_next()
    if gen.matrix.all() == gen.ones.all():
        print(i + 1)

I'm learning Python for a class and I want to know if there is a way to optimize this code or reduce syntax, I greatly appreciate it.

\$\endgroup\$
3
  • \$\begingroup\$ The generation is done previous the exposure of the map, else I think it would be very time consuming. \$\endgroup\$ Sep 21 '20 at 0:25
  • \$\begingroup\$ Your example looks like a very special case, the ones don't appear randomly anywhere in the matrix, but only from the top downwards. \$\endgroup\$ Sep 21 '20 at 11:49
  • \$\begingroup\$ As I said, in example, it was to show how the first rows would get filled first (probably) also, the intention is to get the first rows filled first. \$\endgroup\$ Sep 21 '20 at 14:31
1
\$\begingroup\$

You don't need to create a second m x n matrix to track where you've set. Since you're only interested in the index of the last one placed in each column you can use an one dimensional n-length array to track the row of the last one added and then use that directly when indexing the matrix.

Similarly, it also lets you randomly choose columns that still have space to add ones directly (that is, the nber of ones added is less than the length of the column) using np.less, np.where, and np.random.choice instead of picking a column, checking if it contains all ones, and resampling if it does. That's almost always a bad approach, especially when you start to have more columns full than not. If there are 5 full columns and 1 non-full one you have to keep sampling until you randomly select the one non-full column with only 1/6th odds which is going to be slow.

Combining all that you can write everything you need in about 8 lines with a 6-7x speed up

def matrix_generator(m, n): 
    matrix = np.zeros((m,n), dtype="int")
    ones = np.zeros(n, dtype="int")

    while np.any(np.less(ones, m)):
        i = np.random.choice(np.where(np.less(ones, m))[0])

        matrix[ones[i],i] = 1
        ones[i] += 1

        yield matrix
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.