Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

How to produce a random number sequence that doesn't produce more than X consecutive elements

Ok, I really don't know how to frame the question properly because I barely have any idea how to describe what I want in one sentence and I apologize.

Let me get straight to the point and you can just skip the rest cause I just want to show that I've tried something and not coming here to ask a question on a whim.

I need an algorithm that produces 6 random numbers where it may not produce more than 2 consecutive numbers in that sequence.

example: 3 3 4 4 2 1

^FINE.

example: 3 3 3 4 4 2

^NO! NO! WRONG!

Obviously, I have no idea how to do this without tripping over myself constantly.

Is there a STL or Boost feature that can do this? Or maybe someone here knows how to concoct an algorithm for it. That would be awesome.

What I'm trying to do and what I've tried.(the part you can skip)

This is in C++. I'm trying to make a Panel de Pon/Tetris Attack/Puzzle League whatever clone for practice. The game has a 6 block row and 3 or more matching blocks will destroy the blocks. Here's a video in case you're not familiar.

When a new row comes from the bottom it must not come out with 3 horizontal matching blocks or else it will automatically disappear. Something I do not want for horizontal. Vertical is fine though.

I've tried to accomplish just that and it appears I can't get it right. When I start the game chunks of blocks are missing because it detects a match when it shouldn't. My method is more than likely heavy handed and too convoluted as you'll see.

enum BlockType {EMPTY, STAR, UP_TRIANGLE, DOWN_TRIANGLE, CIRCLE, HEART, DIAMOND};
vector<Block> BlockField::ConstructRow()
{
    vector<Block> row;

    int type = (rand() % 6)+1;

    for (int i=0;i<6;i++)
    {
        row.push_back(Block(type));
        type = (rand() % 6) +1;
    }

    // must be in order from last to first of the enumeration
    RowCheck(row, diamond_match);
    RowCheck(row, heart_match);
    RowCheck(row, circle_match);
    RowCheck(row, downtriangle_match);
    RowCheck(row, uptriangle_match);
    RowCheck(row, star_match);

    return row;
}

void BlockField::RowCheck(vector<Block> &row, Block blockCheckArray[3])
{
    vector<Block>::iterator block1 = row.begin();
    vector<Block>::iterator block2 = row.begin()+1;
    vector<Block>::iterator block3 = row.begin()+2;
    vector<Block>::iterator block4 = row.begin()+3;
    vector<Block>::iterator block5 = row.begin()+4;
    vector<Block>::iterator block6 = row.begin()+5;

    int bt1 = (*block1).BlockType();
    int bt2 = (*block2).BlockType();
    int bt3 = (*block3).BlockType();
    int bt4 = (*block4).BlockType();
    int type = 0;

    if (equal(block1, block4, blockCheckArray)) 
    {
        type = bt1 - 1;
        if (type <= 0) type = 6;
        (*block1).AssignBlockType(type);
    }
    else if (equal(block2, block5, blockCheckArray)) 
    {
        type = bt2 - 1;
        if (type <= 0) type = 6;
        (*block2).AssignBlockType(type);
    }
    else if (equal(block3, block6, blockCheckArray)) 
    {
        type = bt3 - 1;
        if (type == bt3) type--;
        if (type <= 0) type = 6;
        (*block3).AssignBlockType(type);
    }
    else if (equal(block4, row.end(), blockCheckArray)) 
    {
        type = bt4 - 1;
        if (type == bt3) type--;
        if (type <= 0) type = 6;

        (*block4).AssignBlockType(type);
    }
}

Sigh, I'm not sure if it helps to show this...At least it shows that I've tried something.

Basically, I construct the row by assigning random block types, described by the BlockType enum, to a Block object's constructor(a Block object has blockType and a position).

Then I use a RowCheck function to see if there's 3 consecutive blockTypes in one row and I have do this for all block types. The *_match variables are arrays of 3 Block objects with the same block type. If I do find that there are 3 consecutive block types then, I just simply subtract the first value by one. However if I do that I might end up inadvertently producing another 3 match so I just make sure the block types are going in order from greatest to least.

Ok, it's crappy, it's convoluted and it doesn't work! That's why I need your help.

like image 466
Mathmagician Avatar asked Jul 01 '11 08:07

Mathmagician


People also ask

How will you generate a random number which does not get repeated?

We can use either the RAND or RANDBETWEEN functions for this. The RAND function is the fastest because we don't have to specify any arguments. The RAND function returns a random decimal number to the cell. Input the formula =RAND() in the first cell and double-click the fill handle to copy the formula down.

How do I make a list of random numbers without duplicates in Python?

To create a list of random numbers without duplicates with Python, we can use the random. sample method. We call random. sample with the range of numbers to generate and the number of random numbers to generate respectively.


Video Answer


2 Answers

It should suffice to keep record of the previous two values, and loop when the newly generated one matches both of the previous values.

For an arbitrary run length, it would make sense to size a history buffer on the fly and do the comparisons in a loop as well. But this should be close to matching your requirements.

int type, type_old, type_older;

type_older = (rand() % 6)+1;
row.push_back(Block(type_older));

type_old = (rand() % 6)+1;
row.push_back(Block(type_old));

for (int i=2; i<6; i++)
{
    type = (rand() % 6) +1;
    while ((type == type_old) && (type == type_older)) {
        type = (rand() % 6) +1;
    }

    row.push_back(Block(type));
    type_older = type_old;
    type_old = type;
}
like image 134
GargantuChet Avatar answered Nov 10 '22 04:11

GargantuChet


Idea no 1.

while(sequence doesn't satisfy you)
      generate a new sequence 

Idea no 2.

Precalculate all allowable sequences (there are about ~250K of them) 
randomly choose an index and take that element.

The second idea requires much memory, but is fast. The first one isn't slow either because there is a veeery little probability that your while loop will iterate more than once or twice. HTH

like image 40
Armen Tsirunyan Avatar answered Nov 10 '22 04:11

Armen Tsirunyan