randomly filling in empty spaces in a matrix - O(N) amortized time?

Question

Here are two ways to answer the following question. I'm trying to confirm what I believe their time complexity to be:

If I had a snake game with a x,y matrix of spaces, some of which were occupied the snake, how would I best find an available space to place an apple?

I could run through the existing matrix and store a new list of coords which are free, then pick a random element from that array.
I could pick a random x,y and, if it's taken, pick another random coord (repeating as necessary)

It seems like the first one is O(N) time, since it always checks each space in the playfield once

The second one seems like O(N) amortized, since if the snake is at 50% of the playfield then on average it will take N checks to find an open space. Yet if the snake is smaller than 50%, the random approach will be better, and if it's more than 50%, it will be worse.

Is this thinking correct? I'm not sure I'm using the term "amortized" correctly, since I have only had a very brief introduction to the concept in the context of dynamic arrays in ruby.

You can also get an O(snake) solution by taking a random integer from [0, N-snake[ and then test each element of the snake whether it's smaller than your integer and needs to be skipped when translating the integer to a position. — Bergi
– Bergi, Commented Jul 14, 2017 at 21:47
The second one should be O(n log(n)) if you completely fill the matrix. If you only fill it up to a fixed fraction independent of n, it's only O(n). — CodesInChaos
– CodesInChaos, Commented Jul 18, 2017 at 7:44

Adrian Maire · Accepted Answer · 2017-07-18 06:28:42Z

4

Is this thinking correct?

Mostly, but no exactly: If the snake is 50%, each try has 50% of getting a free space. So the probability is:

50% of getting a position in O(1*k)
75% of getting a position in O(2*k) or less
87.5% of getting a position in O(3*k) or less
99.9% of getting a position in O(10*k) or less

Considering this, you would be much better of trying a simple random than a linear search. However, in games, predictability is some times better than speed. You could also make some hybride: try randomly 5 times and then goes linear, so 5 random tries have not a big impact and the linear solution solve in a predictable time the worse cases.

If your matrix is all occupied by the snake but 1 cell, then the linear search is better.

Others alternatives:

Let define your grid of WxH, where each cell is at w x h (note: upper / lower case).

We may define a hash to identify each cell as: w*H+h;

If you create a hash table of references to empty cells, inserting/removing/reading the table is O(k).

Every time you move your snake, you update the table, so it keep always the empty cells.

You could generate a random number in [0,W*H), use this value as hash value and access the table for getting a position for your apple. That stay at O(k).

edited Jul 18, 2017 at 6:28

answered Jul 14, 2017 at 8:48

Adrian Maire

5895 silver badges16 bronze badges

I don't get how your alternative is any different from the second approach - the generated random number from [0, W*H] might as well point to a snake field not an empty one.

Bergi
– Bergi

2017-07-14 21:44:08 +00:00
Commented Jul 14, 2017 at 21:44
@Bergi I think I see what Adrian is getting at. If you store a separate list of available spaces that is updated whenever the snake moves, you no longer have to iterate through each space when it comes time to place a new apple. Then when you pick a random W,H you know that it will be available and there is no risk of snake collision.

max pleaner
– max pleaner

2017-07-17 18:15:06 +00:00
Commented Jul 17, 2017 at 18:15
Correct, but it needs to be a hash-table (unordered_map in C++), because if not, searching/inserting/deleting from the container would counter any benefit of using this way: A linked list has linear access, arrays has linear removal.

Adrian Maire
– Adrian Maire

2017-07-18 06:26:36 +00:00
Commented Jul 18, 2017 at 6:26
What is the k in 2*k ?

paparazzo
– paparazzo

2017-07-19 17:55:44 +00:00
Commented Jul 19, 2017 at 17:55
@Paparazzi: K is a constant time, in this case, the time to test if a single cell is or not empty.

Adrian Maire
– Adrian Maire

2017-07-19 22:25:45 +00:00
Commented Jul 19, 2017 at 22:25

Add a comment |

Deduplicator · Accepted Answer · 2017-07-18 07:17:29Z

1

You can optimize your first approach like this:

Determine how many acceptable fields there are:
#acceptable = #fields - #all_snake_parts - #walls - #whatever.
This might be cached or easily calculated from available data in O(1).
Select a number from (0, #acceptable] and find that free field in O(#fields).

The changed approach uses O(1) space and O(#fields) time, instead of O(#free) space and O(#fields) time.

answered Jul 18, 2017 at 7:17

Deduplicator

9,3295 gold badges34 silver badges53 bronze badges

Add a comment |

paparazzo · Accepted Answer · 2017-07-23 14:34:34Z

If there is only 1 cell open the random is going to be worse as it will create some duplicates. It will take more than n random to get n unique.

If you have just 2 or more cells open then random is better and will find is just over n / 2 tries. It is pretty close to n / open cell.

The problem is if there are no open cells a random approach never finishes.

You could go with a couple approaches

stop at like n / 5 and then go to scan the array
store the guesses in a hashset and when the hashset size is the size of the array you stop

test program

private static double FindOpen()
{
    Random rand = new Random();
    int runs = 100;
    int sample = 100;
    int guesses = 0;
    double answer = 0;
    HashSet<int> full = new HashSet<int>();
    HashSet<int> findme = new HashSet<int>();
    for (int i = 0; i < sample; i++)
    {
        while (!findme.Add(rand.Next(sample))) { };
        //if (findme.Count < sample * 2 / 10)
        //    continue;
        guesses = 0;

        for (int j = 0; j < sample * runs; j++)
        {
            full.Clear();
            int r = rand.Next(sample);
            full.Add(r);
            guesses++;                 
            while (!findme.Contains(r))
            {
                if (full.Count == sample)
                {
                    Debug.WriteLine("full.Count == sample");
                }
                guesses++;
                r = rand.Next(sample);
                full.Add(r);                      
            }
        }
        double avgGuesses = (double)guesses / runs / sample ;
        double fraction = avgGuesses / sample;
        Debug.WriteLine($"empty = {i + 1}/{sample}  average gusses = {avgGuesses.ToString("N2")}   avgGuesses/{sample} = {fraction.ToString("N4")}");
    }
    return (answer);
}

empty = 1/100 average gusses = 100.41 avgGuesses/100 = 1.0041
empty = 2/100 average gusses = 50.24 avgGuesses/100 = 0.5024
empty = 3/100 average gusses = 34.04 avgGuesses/100 = 0.3404
empty = 4/100 average gusses = 25.13 avgGuesses/100 = 0.2513
empty = 5/100 average gusses = 19.90 avgGuesses/100 = 0.1990
empty = 6/100 average gusses = 16.60 avgGuesses/100 = 0.1660
empty = 7/100 average gusses = 14.02 avgGuesses/100 = 0.1402
empty = 8/100 average gusses = 12.60 avgGuesses/100 = 0.1260
empty = 9/100 average gusses = 11.04 avgGuesses/100 = 0.1104
empty = 10/100 average gusses = 10.10 avgGuesses/100 = 0.1010
empty = 11/100 average gusses = 9.13 avgGuesses/100 = 0.0913
empty = 12/100 average gusses = 8.31 avgGuesses/100 = 0.0831
empty = 13/100 average gusses = 7.67 avgGuesses/100 = 0.0767
empty = 14/100 average gusses = 7.25 avgGuesses/100 = 0.0725
empty = 15/100 average gusses = 6.71 avgGuesses/100 = 0.0671
empty = 16/100 average gusses = 6.17 avgGuesses/100 = 0.0617
empty = 17/100 average gusses = 5.91 avgGuesses/100 = 0.0591
empty = 18/100 average gusses = 5.50 avgGuesses/100 = 0.0550
empty = 19/100 average gusses = 5.23 avgGuesses/100 = 0.0523
empty = 20/100 average gusses = 4.99 avgGuesses/100 = 0.0499
empty = 21/100 average gusses = 4.71 avgGuesses/100 = 0.0471
empty = 22/100 average gusses = 4.52 avgGuesses/100 = 0.0452
empty = 23/100 average gusses = 4.36 avgGuesses/100 = 0.0436
empty = 24/100 average gusses = 4.19 avgGuesses/100 = 0.0419
empty = 25/100 average gusses = 4.05 avgGuesses/100 = 0.0405
empty = 26/100 average gusses = 3.82 avgGuesses/100 = 0.0382
empty = 27/100 average gusses = 3.72 avgGuesses/100 = 0.0372
empty = 28/100 average gusses = 3.56 avgGuesses/100 = 0.0356
empty = 29/100 average gusses = 3.43 avgGuesses/100 = 0.0343
empty = 30/100 average gusses = 3.35 avgGuesses/100 = 0.0335
empty = 31/100 average gusses = 3.23 avgGuesses/100 = 0.0323
empty = 32/100 average gusses = 3.13 avgGuesses/100 = 0.0313
empty = 33/100 average gusses = 3.03 avgGuesses/100 = 0.0303
empty = 34/100 average gusses = 2.93 avgGuesses/100 = 0.0293
empty = 35/100 average gusses = 2.83 avgGuesses/100 = 0.0283
empty = 36/100 average gusses = 2.80 avgGuesses/100 = 0.0280
empty = 37/100 average gusses = 2.71 avgGuesses/100 = 0.0271
empty = 38/100 average gusses = 2.63 avgGuesses/100 = 0.0263
empty = 39/100 average gusses = 2.58 avgGuesses/100 = 0.0258
empty = 40/100 average gusses = 2.47 avgGuesses/100 = 0.0247
empty = 41/100 average gusses = 2.41 avgGuesses/100 = 0.0241
empty = 42/100 average gusses = 2.37 avgGuesses/100 = 0.0237
empty = 43/100 average gusses = 2.33 avgGuesses/100 = 0.0233
empty = 44/100 average gusses = 2.28 avgGuesses/100 = 0.0228
empty = 45/100 average gusses = 2.22 avgGuesses/100 = 0.0222
empty = 46/100 average gusses = 2.18 avgGuesses/100 = 0.0218
empty = 47/100 average gusses = 2.15 avgGuesses/100 = 0.0215
empty = 48/100 average gusses = 2.07 avgGuesses/100 = 0.0207
empty = 49/100 average gusses = 2.05 avgGuesses/100 = 0.0205
empty = 50/100 average gusses = 2.02 avgGuesses/100 = 0.0202
empty = 51/100 average gusses = 1.94 avgGuesses/100 = 0.0194
empty = 52/100 average gusses = 1.95 avgGuesses/100 = 0.0195
empty = 53/100 average gusses = 1.90 avgGuesses/100 = 0.0190
empty = 54/100 average gusses = 1.83 avgGuesses/100 = 0.0183
empty = 55/100 average gusses = 1.83 avgGuesses/100 = 0.0183
empty = 56/100 average gusses = 1.79 avgGuesses/100 = 0.0179
empty = 57/100 average gusses = 1.75 avgGuesses/100 = 0.0175
empty = 58/100 average gusses = 1.72 avgGuesses/100 = 0.0172
empty = 59/100 average gusses = 1.68 avgGuesses/100 = 0.0168
empty = 60/100 average gusses = 1.67 avgGuesses/100 = 0.0167
empty = 61/100 average gusses = 1.64 avgGuesses/100 = 0.0164
empty = 62/100 average gusses = 1.61 avgGuesses/100 = 0.0161
empty = 63/100 average gusses = 1.60 avgGuesses/100 = 0.0160
empty = 64/100 average gusses = 1.56 avgGuesses/100 = 0.0156
empty = 65/100 average gusses = 1.53 avgGuesses/100 = 0.0153
empty = 66/100 average gusses = 1.53 avgGuesses/100 = 0.0153
empty = 67/100 average gusses = 1.49 avgGuesses/100 = 0.0149
empty = 68/100 average gusses = 1.46 avgGuesses/100 = 0.0146
empty = 69/100 average gusses = 1.45 avgGuesses/100 = 0.0145
empty = 70/100 average gusses = 1.43 avgGuesses/100 = 0.0143
empty = 71/100 average gusses = 1.41 avgGuesses/100 = 0.0141
empty = 72/100 average gusses = 1.39 avgGuesses/100 = 0.0139
empty = 73/100 average gusses = 1.36 avgGuesses/100 = 0.0136
empty = 74/100 average gusses = 1.34 avgGuesses/100 = 0.0134
empty = 75/100 average gusses = 1.32 avgGuesses/100 = 0.0132
empty = 76/100 average gusses = 1.31 avgGuesses/100 = 0.0131
empty = 77/100 average gusses = 1.30 avgGuesses/100 = 0.0130
empty = 78/100 average gusses = 1.28 avgGuesses/100 = 0.0128
empty = 79/100 average gusses = 1.27 avgGuesses/100 = 0.0127
empty = 80/100 average gusses = 1.26 avgGuesses/100 = 0.0126
empty = 81/100 average gusses = 1.24 avgGuesses/100 = 0.0124
empty = 82/100 average gusses = 1.22 avgGuesses/100 = 0.0122
empty = 83/100 average gusses = 1.21 avgGuesses/100 = 0.0121
empty = 84/100 average gusses = 1.19 avgGuesses/100 = 0.0119
empty = 85/100 average gusses = 1.18 avgGuesses/100 = 0.0118
empty = 86/100 average gusses = 1.16 avgGuesses/100 = 0.0116
empty = 87/100 average gusses = 1.14 avgGuesses/100 = 0.0114
empty = 88/100 average gusses = 1.14 avgGuesses/100 = 0.0114
empty = 89/100 average gusses = 1.12 avgGuesses/100 = 0.0112
empty = 90/100 average gusses = 1.11 avgGuesses/100 = 0.0111
empty = 91/100 average gusses = 1.10 avgGuesses/100 = 0.0110
empty = 92/100 average gusses = 1.09 avgGuesses/100 = 0.0109
empty = 93/100 average gusses = 1.08 avgGuesses/100 = 0.0108
empty = 94/100 average gusses = 1.06 avgGuesses/100 = 0.0106
empty = 95/100 average gusses = 1.05 avgGuesses/100 = 0.0105
empty = 96/100 average gusses = 1.05 avgGuesses/100 = 0.0105
empty = 97/100 average gusses = 1.03 avgGuesses/100 = 0.0103
empty = 98/100 average gusses = 1.02 avgGuesses/100 = 0.0102
empty = 99/100 average gusses = 1.01 avgGuesses/100 = 0.0101
empty = 100/100 average gusses = 1.00 avgGuesses/100 = 0.0100

I am surprised one open cell did so well. I would expect about 5 n due to duplicates. At 1/2 it is around 2 which is what you should expect.

Stack Exchange Network

randomly filling in empty spaces in a matrix - O(N) amortized time?

3 Answers 3

Your Answer

Hot Network Questions

randomly filling in empty spaces in a matrix - O(N) amortized time?

3 Answers 3

Your Answer

Sign up or log in

Post as a guest

Related

Hot Network Questions