Поиск повторяющихся последовательностей(мне стыдно)

[craz]

131104223333124
330433222100141
031303021342040
040212024023204
320042033003402
433140440301323
230214234042101
003110214123424
304342331344324
032441423412031
423210210101310
220110332401222
434104431303104
013020313322340
332041040414034

как найти все подмассивы в данном массиве, которые содержат 3 и более подряд идущих цифры.

типа array[0][0][7][4] где
первый индекс это по счету первый подмассив
второй индекс это строка
третий начало последовательности
четвертый длина последовательности

Я чето искал искал функцию нифига не нашел... чем бы это можно было сделать

Кстати по вертикали тоже нужно.

Ни кто не встречался с алгоритмом хотябы?

 

[Тугай]

Если по горизонтали это по строкам, то

131104223333124 = применяем RLE = 1(1),3(1),1(2),0(1),4(1),2(2),3(4)

если посчитать индексы в скобах до 3(4) - то получим 8 (или для индекса 7)

 

[craz]

применяем RLE

wtf?

вообще как я тебя понял ты предлагаешь считать частату встречания циферок...
такая йункция есть....

то есть если взять строку посчитать встречание и если оно больше трех то те цифры и искать... ну да как вариант... проще нет ничего?

горизонтально и вертикально - это одно и тоже вроде будет, только надо будет матрицу ?транспонировать? - вроде такое слово откуда-то из памяти вылазиет для преобразования столбцов в строку.

 

[Тугай]

http://en.wikipedia.org/wiki/Run-length_encoding

 

[craz]

http://en.wikipedia.org/wiki/Run-length_encoding

http://php.su/functions/?array-count-values
Это?

 

[Тугай]

Нет. array_count_values() - не дает вычислить начало последовательности.

"abbdacccce" - применяем RLE и получаем array( array('a' => 1), array('b' => 2), array('d' => 1), array('a' => 1), array('c' => 4), array('e' => 1) );

Теперь его перебираем и ищем > 3 и заодно склаываем 1+2+1+1=5 - это начало дилнной последовательноси.

 

[craz]

Зачем складываем?
Это двумерный массив, надо искать только в строках. Это не одномерный массив чисел

 

[Тугай]

вообще как я тебя понял ты предлагаешь считать частату встречания циферок...

Да.
Если частота больше 3 - это длинная последовательность, начинается она с суммы предыдущих частот.

 

[WMix]

/[0]{3,}|[1]{3,}|[2]{3,}|[3]{3,}|[4]{3,}|[5]{3,}|[6]{3,}|[7]{3,}|[8]{3,}|[9]{3,}/

это имеешь в виду?

 

[craz]

/[0]{3,}|[1]{3,}|[2]{3,}|[3]{3,}|[4]{3,}|[5]{3,}|[6]{3,}|[7]{3,}|[8]{3,}|[9]{3,}/

это имеешь в виду?

не пойму я...

Я имею ввиду что если есть три или более рядом стоящих числа в одной строке горизонтально или вертикально, я бы хотел их уничтожить и сместить вертикально над ними элементы вниз.

 

[WMix]

$pattern = '/[0]{3,}|[1]{3,}|[2]{3,}|[3]{3,}|[4]{3,}|[5]{3,}|[6]{3,}|[7]{3,}|[8]{3,}|[9]{3,}/';
foreach( $in as $string ){
	echo $string."\n";
	preg_match_all($pattern, $string, $matches,PREG_OFFSET_CAPTURE);
	print_r($matches);
}

вертикально тоже?
цикл нужно по другому закрутить....

аааа тетрис? сейчас подумаю...

 

[Тугай]

Я имею ввиду что если есть три или более рядом стоящих числа в одной строке горизонтально или вертикально, я бы хотел их уничтожить и сместить вертикально над ними элементы вниз.

Тогда не нужны никакие подмассивы, двигайся по полю и проверяй соседей, и в другой матрице такого же размера отмечай в 1, в те клетки которые надо удалить.
Ну и потом осыпай исходную матрицу по маске.

 

[WMix]

слегонца наговнокодил.... но работает.... оптимируй, но только если это тетрис и округу найденного нужно добавить...

class Tetris{

	protected $in;
	protected $f;

	private $w = 15;
	private $h = 15;
	private $s;
	
	private function rec($x,$y){
		if($this->iae($x,$y)){
			$this->f[$y][$x] = $this->s;
			$this->parse($x,$y);
		}
	}

	private function parse($x,$y){
		$this->rec($x-1,$y);
		$this->rec($x+1,$y);
		$this->rec($x,$y-1);
		$this->rec($x,$y+1);
	}

	private function iae($x,$y){
		return isset($this->in[$y][$x]) && !isset($this->f[$y][$x]) && $this->in[$y][$x] == $this->s;
	}
	
	public function start($in){
		$this->in=$in;
		for ($y=0; $y<$this->h; $y++){
			for ($x=0; $x<$this->w ; $x++){
				$this->s = $this->in[$y][$x];
				if( $this->iae($x+1,$y) && $this->iae($x+2,$y)){
					$this->f[$y][$x] = $this->s;
					$this->parse($x,$y);
				}
				if( $this->iae($x,$y+1) && $this->iae($x,$y+2)){
					$this->f[$y][$x] = $this->s;
					$this->parse($x,$y);
				}
			}
		}
	}
	
	public function out(){
		for ($y = 0 ; $y < $this->h ; $y++){
			for ($x = 0 ; $x < $this->w ; $x++){
				echo (isset($this->f[$y][$x]) ? $this->f[$y][$x] : '.');
			}
			echo "\n";
		}
	}
}

$t = new Tetris;

$t->start(array(
		array(1,3,1,1,0,4,2,2,3,3,3,3,1,2,4),
		array(3,3,0,4,3,3,2,2,2,1,0,0,1,4,1),
		array(0,3,1,3,0,3,0,2,1,3,4,2,0,4,0),
		array(0,4,0,2,1,2,0,2,4,0,2,3,2,0,4),
		array(3,2,0,0,4,2,0,3,3,0,0,3,4,0,2),
		array(4,3,3,1,4,0,4,4,0,3,0,1,3,2,3),
		array(2,3,0,2,1,4,2,3,4,0,4,2,1,0,1),
		array(0,0,3,1,1,0,2,1,4,1,2,3,4,2,4),
		array(3,0,4,3,4,2,3,3,1,3,4,4,3,2,4),
		array(0,3,2,4,4,4,4,2,3,4,1,2,3,3,3),
		array(4,2,3,2,1,0,2,1,0,1,0,1,3,1,0),
		array(2,2,0,1,1,0,3,3,2,4,0,1,2,2,2),
		array(4,3,4,1,0,4,4,3,1,3,0,3,1,0,4),
		array(0,1,3,0,2,0,3,1,3,3,2,2,3,4,0),
		array(3,3,2,0,4,1,0,4,0,4,1,4,0,3,4)
	));
$t->out();

.3....223333...
33....222......
.3....02.......
......02.......
......0........
...............
...............
...............
....4.......3..
...4444.....333
..........0.3..
..........0.222
..........0....
...............
...............

 

[DiMA]

/[0]{3,}|[1]{3,}|[2]{3,}|[3]{3,}|[4]{3,}|[5]{3,}|[6]{3,}|[7]{3,}|[8]{3,}|[9]{3,}/

лол, шо? .-)

preg_match_all("!(\d)\\1\\1+!is", $text, $reg)

выполняем рег 2 раза, перевернув массив данных и объединив результат в один

 

[craz]

Да это типа тетриса. Только на js) поэтому мне и нужен был алгоритм. Щас буду посмотреть предложенные решения)

 

[WMix]

DiMA
регулярку красиво ужал, можно еще и is убрать, \\1 запомню)

выполняем рег 2 раза, перевернув массив данных и объединив результат в один

это предложил выше, но думая о тетрисе без рекурсии не смог решить