Check if it's a combo/streak

Newbie & Debugging Questions
#1

Greetings JGO,

In this application I’ve created a grid[][] with Bytes in it.

{1, 0, 2, 0, 0, 0, 2, 0}
{1, 1, 0, 1, 1, 2, 2, 0}
{1, 0, 0, 2, 1, 0, 0, 0}
{0, 1, 0, 2, 2, 0, 1, 0}
{2, 0, 1, 2, 1, 0, 2, 2}
{1, 2, 0, 2, 1, 0, 1, 0}
{0, 1, 1, 0, 0, 0, 1, 2}
{0, 0, 0, 0, 1, 0, 2, 0}

A combo/streak is 3 of the same bytes next to each other, for example {1, 1, 1}. This can occur horizontal and vertical.
But the question is, how do I achieve finding all combos/streaks?

If possible, give an example, explained in words, of how it’s done, as I am here to learn and not copy codes.

If you have any questions, just say it.
-RoseSlayer

#2

You would use a nested for loop.

What have you tried? Can we see an MCVE?

Take a step back and break your problem down into smaller pieces. Can you write a basic program that checks for a streak in a one-dimensional array? Take that logic and expand on it, and post an MCVE when you get stuck on a specific problem.

Good luck!

#3

Sorry for the limited information given.
I’ve tried quite alot, but it was done with objects and not tiles.

First Forloop:
Previously I was checking on every Tile, if it’s connected to the left, right, top, bottem.
and if it was connected to the right and not the left it was assigned as the start of a (horizontal)combo.
the same goes for top and bottem, if it was connected to the bottem and not top, it was assigned as a start of a (vertical)combo

Second Forloop:
In the second forloop the code is searching for the Tiles that were assigned to a forloop and then create a forloop within to get the length of the combo (which is extremely inefficient).

Third Forloop:
Execute the combo in the Tile.executeCombo(comboLength);

Forth Forloop:
Remove every Tile that was in a combo and create a new Tile in the grid.

But if you can read this, there were so much forloops and extremely inefficient…
The problem I am also experiencing is that I don’t know the exact name of that what I am doing, so I cannot google it for any hints/tips…

But long story short I’ve removed all the Tile classes and I am doing it now with the identities(byte) to create a faster and cleaner function.
Also an offtopic question, are double-dimensional arrays not faster as you can write it in [x.][y] instead of [x+y*gridWidth]?

-RoseSlayer

#4

I really wouldn’t worry about the speed of a one-dimensional array vs a two-dimensional array. Premature optimization is the root of all evil. Use whatever makes the most sense in your head.

But back to your question: can you write a simple MCVE program that finds a streak in a single row? I’m not talking about using a one-dimensional array to “fake” a two-dimensional array. I’m talking about starting at the smallest step and just working out the logic for a single row first.

#5

It is possible to use this function:

	public Byte grid[][] = new Byte[8][8];
	public Byte gridComboLength[][] = new Byte[8][8];
	public void checkCombo(){
		for(int y = 0; y < gridHeight; y++){
			for(int x = 0; x < gridWidth; x++){
				int ix = x + 1;
				int comboLength = 0;
				boolean checkHorizontalCombo = true;
				while(checkHorizontalCombo && ix < gridWidth){
					if(grid[x][y] == grid[ix][y]){
						comboLength++;
						ix++;
					} else 
						break;
				}
				gridComboLength[x][y] = (byte) comboLength;
				x = ix;
			}
		}
	}

But this is only for the horizontals, so I need 2 times this code.

Grid[][]=
{1, 0, 2, 0, 0, 0, 2, 0}
{1, 1, 0, 1, 1, 2, 2, 0}

GridComboLength[][]=
{1, 1, 1, 3, 0, 0, 1, 1}
{2, 0, 1, 2, 0, 2, 0, 1}

So you see that at [3][0] there is a combo of 3 (according to this Grid)

#6

I’ve mentioned my recommendation of starting over with a little program that checks a single row and working your way up.

It’s entirely up to you how you proceed, but I’ll be happy to help if you post an MCVE showing your attempt at the above.

#7

Can combos wrap around the beginning or end of rows/columns? I will assume no.
There are also other questions such as, can combos overlap? etc.

Solve 1 problem at a time:

  • Iterate over the array
  • At each point, check and record combos
  • Use those results (probably multiple steps by itself)

Don’t try to do everything in one step, at least not in the first prototype.
Try to use functional/procedural decomposition to break down the problem and separate the steps.
Use types and smart data representation to help solve the problem and encode information.

My take at it if you do want to see some code, hopefully I understand the problem:

[spoiler]
(written in post)

class Combo {
byte val;
boolean horizontal; // true = h, false = vertical
Point center;
}

///

public List combos(Byte[][] grid) { // any reason for boxing?
List list = new ArrayList<>();
for (int x = 1; x < grid.length - 1; x++)
for (int y = 1; y < grid[x].length - 1; y++)
addCombos(x, y, grid, list);
return list;
}

// precondition: (x ± 1, y ± 1) are in bounds
private void addCombos(int x, int y, Byte[][] grid, List collector) {
Byte center = grid[x][y];

// probably use constructors
// horizontal?
if (grid[[b][/b]x - 1][y].equals(center) && grid[[b][/b]x + 1][y].equals(center)) {
    Combo c = new Combo();
    c.val = center;
    c.horizontal = true;
    c.center = new Point(x, y);
    collector.add(c);
}

// vertical?
if (grid[[b][/b]x][y - 1].equals(center) && grid[[b][/b]x][y + 1].equals(center)) {
    Combo c = new Combo();
    c.val = center;
    c.horizontal = false;
    c.center = new Point(x, y);
    collector.add(c);
}

}

This is a reduction over the array, collecting the results into a list as it goes.
[/spoiler]

#8

This instinct is good - and often results in the simplest, easy to understand code. I.e. if you can go:

  • write pseudocode
  • pseudocode becomes the comments
  • fill in the code between the comments
  • job done

In this case I would jot down how I would do it if I was going by eye:

  • Look at each cell that a streak can start on
  • If the next 2 cells on the row are the same, it’s a horizontal streak
  • If the next 2 cells on the column are the same, it’s a vertical streak

Becomes

//Look at each cell that a streak can start on
//If the next 2 cells on the row are the same, it's a horizontal streak
//If the next 2 cells on the column are the same, it's a vertical streak

Becomes

//Look at each cell that a streak can start on
for (int y = 0; y < numrows-2; y++) {
    for (int x = 0; x < numcols-2; x++) {
        byte cellValue = grid[y][x];

        //If the next 2 cells on the row are the same, it's a horizontal streak
        if (grid[y][x+1] == cellValue && grid[y][x+2] == cellValue)
            //Horizontal streak!

        //If the next 2 cells on the column are the same, it's a vertical streak
        if (grid[y+1][x] == cellValue && grid[y+2][x] == cellValue)
            //Vertical streak!
    }
}

Which is much the same as BurntPizza said to be fair :smiley:

I guess my point is that there’s a lot to be said for code which retains a clear correspondence to its underlying algorithm, expressed in words as you originally requested.

#9

First of all, thanks for all the help and time investigated.
BurntPizza, and richierich, you both understood the problem.
But there is another problem by doing the following:

if (grid[y][x+1] == cellValue && grid[y][x+2] == cellValue)
            //Horizontal streak!

and

if (grid[x][y - 1].equals(center) && grid[x][y + 1].equals(center)) {}

The problem of these codes is that the script works by comboLength >= 3, but if you want the comboLength >= 4, you can’t use these scripts.
So the only solution I could think of is a forLoop. By doing that the script gets kinda choatic, and sometimes require more CPU then other times, which result in laggspikes.
Is there no way of finding the streaks within the grid[x.][y]? like:

grid[x][y = 0]{1, 1, 0, 1, 1, 1, 0 , 0}.contains({1, 1, 1}) -> [x=5][y=0]

The above is the psuedocode, but again there is a problem with the variable comboLength, any other ideas how to solve this problem?

-RoseSlayer

#10

Efficiency: Move to a 1d array , if you attempt to check vertically you will cache thrash and im guessing that wont be useful in your program.

#11

You will still thrash just as much with the 1D array: none at all if the array is as small as depicted in the OP.

To match arbitrarily long streaks, do two passes, check for horizontal streaks row by row, and vertical column by column.
The problem in each row/column is then equivalent to run length encoding, will runs below a certain length (3?) thrown out.

#12

could you store the rows and columns as strings and then use regex or string find functions?

The regex “/(.+)\1/” finds patterns 2 or more, you could amend it for any length you want as a minimum

#13

Sounds like you basically have the problem solved but you think maybe the code is too messy, and that there may be some library function to do exactly what’s required. Hardly seems worth it though when the problem is this small - the samples you’ve posted are only 10-20 lines which is not something to be afraid of writing.

If loops 3 or 4 deep seem inelegant, you can make it less “chaotic” (your word) by factoring some things out into subroutines (e.g. BurntPizza addCombos()). Or short of that you would be surprised how much it reduces the chaos to put some comments in your code :wink:

Obfuscating things in regex processing just to reduce line count would me a mistake IMO, even if you could understand the synax (tell me when you do :)) and then get it to work.

Performance wise can it really be this which is causing your spikes? Surely you generate a grid once, find the streaks once and job done. Or is it a dynamically changing grid? In which case only re-scan around cells which change? How big are the grids you are getting performance problems on?

#14

[quote]Previously I was checking on every Tile, if it’s connected to the left, right, top, bottem.
[/quote]
I did not read the whole page, so i am not sure if somebody allready mentioned it:
If you cycle through the 2D-Array from the bottom, left corner to the top, right corner, you only need to check the upper and right tile for every tile you find.
If you find a horizontal match store it somwhere. If it was a horizontal match and the next byte you check is different, throww the match away, if it was vertical, wait until you reach the same position, one row above, if it is no match, throw it away. If there have been matches again, you have your combo. Then there are some new question:

  • What happens, if there are more then 3 in a row? Is it one big combo or are the others ignored?
  • Can 1 byte be part of more then one combo (vertical and horizontal) or is it used by one combo only and then “deleted”?
#15

An algorithm that can be extended to any combo length would be one that counts consecutive elements, first on rows and then on columns.



private final static int COMBO_COUNT = 3;

for(int y = 0; y < numRows; y++){
    Tile element = grid[y][0];
    int occurances = 1;
    for(int x = 1; x < numCols; x++){
        Tile t = grid[y][x];
        if(t.equals(element)){
            occurances++;
        }else{
            element = t;
            occurances = 1;
        }
        if(occurances >= COMBO_COUNT){
            //Combo of length COMBO_COUNT on row
        }
    }
}

You then need a second block like this for detecting combos in columns. This should be faster, especially for higher combo counts. In the nested loop others have suggested, an average element is processed COMBO_COUNT2 times, or another way to see it, each iteration of the nested loop checks COMBO_COUNT2 tiles. My code only ever needs to check each element once per dimension, meaning 2 times for a 2D array, regardless of combo count.