Help with script for large matrices

[shudson250]

Hello All

 

This was an online test, which I didn't do very well with, and am looking for guidance of where I went wrong.

 

The idea is you'd have a matrix $A with values -1, 0, 1 in each position, in rows M and column N where M,N can be up to 1000. The code is evaluated $k times where $k can be up to 1000 as well.

 

Starting at $A[0][0], evaluate the matrix where -1 means you go down a row and +1 means you go right one column. A 0 value means you continue along your previous direction.

 

After exiting a position, that positions value is multiplied by -1: 1 = (-1); (-1) = 1; 0 = 0

Once you exit the matrix either on the right or below, you stop and start over

 

The goal of the code is to return how many times you exited the bottom right corner, ending up below (not to the right) the matrix; When your spot is [M], [N+1]

 

Here is the code I wrote:

 

function eval_matrix( $A, $k ) {

$x = 0;
$y = 0;
// dir is x or y for up/down //
$dir = "y";

$ball_count = 0;

    // Get columns //
    $maxX = count($A);
    // Get rows //
    $maxY = count($A[0]);
    
// for $k times
for($i=0; $i<$k; $i++) {

	// while we're within the matrix boundaries
	while($x < $maxX && $y < $maxY) {

		// get the value of our current position
		$mode = $A[$x][$y];

		// evaluate the value 0,1,-1
		switch($mode) {
			case 0:
			if($dir =="y") {
				$y++;
			} else {
				$x++;
			}
			break;

			case -1:
			// Change position value
			$A[$x][$y] = 1;
			$y++;
			$dir = "y";
			break;

			case 1:
			// Change position value
			$A[$x][$y] = -1
			$x++;
			$dir = "x";

			break;
		}

	}
	if($x == $maxX-1 && $y == $maxY) {
		$ball_count++;
	}

	$x = 0;
	$y = 0;
	$dir = "y";
}
return $ball_count;
}

 

It may be fairly ugly, but I'm looking for help with how to properly code this type of solution. Any pointers, resources, suggestions are greatly appreciated!

[shudson250]

To be clear: I'm not looking for the strait up solution, I just need help/resources in creating efficient algorithms for large data sets

[requinix]

Uh... The stuff in your first post is different from what you're asking in your second post. The first one is talking about (basically) a code challenge, and the second is talking about large data sets.

 

For the challenge, try a structure like

1. Start with M=0, N=0, direction=down or right or random or whatever
2. Begin loop:
   a. If M=outside grid and N=last column, return 1 (=moved down from the bottom-right corner)
   b. If M=last row and N=outside grid, return 1 (=moved right from the bottom-right corner)
   c. If M or N is outside the bounds of the grid, return 0 (=moved out, but not from the bottom-right corner)
   d. Switch on $A[M][N]:
      = -1: set to +1, direction=down
      =  1: set to -1, direction=right
      else: do nothing
   e. If direction=down, M++; if direction=right, N++

and execute that $k times.

[shudson250]

Mainly I'm looking for advice on efficiency for large data sets (as I mentioned in the first post M, N, and k all approach 1000)

 

Should I break up the matrix and deal with it in smaller pieces? Are there other ways to accomplish this?

[requinix]

echo "Before: ", memory_get_peak_usage(), "\n";

$a = array();
for ($k = 0; $k 	$a[floor($k / 1000)][$k % 1000] = rand(-1, 1);
}

echo "After: ", memory_get_peak_usage(), "\n";

My 5.3.6 Win32 CLI says ~85MB peak usage. Significantly more than a normal script does, but not much in the grand scheme of things. I then ran my solution and saw very little change in that number - small enough that I think it's a memory leak.

 

No worries here.