A Question for the Mathematicians in the audience...

minorgod

Nevermind this question...i added $i-- to the script and it is fixed!

This is a brain teaser that's been bugging me for several hours. I'm building a multicolumn table layout in PHP to lay out an answer sheet for a multiple choice test. I want to be able to feed it an arbitrary number of questions ($num_questions) and number of columns ($num_columns) and have it lay them out in columns with the minimum number of rows to fit them all. So when I have $num_questions=30 and $num_columns=5, it would produce a layout like this:

1 7 13 19 25

2 8 14 20 26

3 9 15 21 27

4 10 16 22 28

5 11 17 23 29

6 12 18 24 30

The problem is that tables must be rendered horizontally, so in this instance we would be rendering the questions in this order 1,7,13,19,25,2,8,14,20,26,...

So my question is, what is the algorithm that will calculate the current $question_number for a given position in the grid. The algorithm I've come up with so far is working for low numbers of questions and columns such as the example above, but I know there's a better way that will work for all possible combinations of test sizes and column specifications. Here's the algorithm I came up with so far:

<table border="1">
<?php
$num_questions=30;
$num_columns=5;
$column_count=0;
$row_count=1;
//calculate the number of rows we will need in our grid.
//we round up here in case there's any spillover
$num_rows=ceil($num_questions/$num_columns);
for($i=0;$i<$num_questions;$i++){
	$column_count++;
	if( $column_count==1 ){ ?>
    <tr class="table-heading1"> 
      <?php } //end if
	if( (1 * $row_count) + ($num_rows * ($column_count-1) ) <= $num_questions){ 
	?>
      <td valign="middle"><?php echo (1 * $row_count) + ($num_rows * ($column_count-1) ) ?></td>
      <?php }else{$i--;}
	if($num_columns == $column_count){ ?>
    </tr>
    <?php $row_count++; $column_count=0;} //end if 


} //end for
?>
</table>

The interesting part of the above code is this:

(1 $row_count) + ($num_rows ($column_count-1) )

That's what I'm using to caculate the number that needs to be displayed in any given table cell as we loop from 1-$num_questions. I know there's a better formula for determining this, but I can't ficure it out. Here's my reasoning behind the above formula:

We know the first number of each row will simply be the same as the count for the row we're in. So then we just count by a specific increment to determine the number for other columns. In other words, the number at any given position should be it's row number plus the product of the number of rows and the current column number-1. The problem here is when data doesn't perfectly fill all the cells. We want the last column to be incomplete. We will still need to iterate past the unfilled cells in the last column to fill in the last rows of the table, so we simply don't fill it. To determine if the cell should be filled or not, I simply test the algorithm to see if it generates a number higher than the highest number in our set ($num_questions), and if so, we don't fill it. So basically the above code does all that, but not once you get past 50 or so questions, it craps out because of my conditional. So I guess that's what needs fixing is just the conditional that determines whether or not to fill the table cell with the number. Try out the above code with $num_questions=30 and then with $num_questions=100 and $num_columns=7 and see the problem in action.

******NOTE I have fixed the test code above to account for the problem...now if only the more complicated version worked right in my program!

drawmack

Often times problems like this arise by looking at the problem incorrectly.

Here is what you want to do. You want to create a series (x) of rows. Each row must contain a number (y) or columns. Sounds to me like you want two loops one to create the rows and one to create the columns.

Now let's look at the information we have available the total number of questions or cells and the number of questions or cells per row. So the question simple becomes what math is needed on each loop.

Well for the row loop you're look at creating a number of rows equal to ciel($num_questions/$num_columns). With a little algebra we can see that you can do this

for($i=0;$i<$num_questions;$i+=$num_columns)

which avoids all the costly mathematics and reduces the problem to simple addition.

What about the loop creating the columns? Well that's even simpler

for($j=1;$j<=$num_columns;$j++)

which has no math.

Coding it this way also remove all those costly if statements you were executing $num_questions times.

Now we have one more problem (which wasn't handled in the original code). What if $num_questions/$num_columns isn't an integer? So we trap for that too and we end up witha final product that looks like this:

<?php 
$num_questions=30; 
$num_columns=7;

//here we calculate number padding cells needed
$padding = (ceil($num_questions/$num_columns) * $num_columns) - $num_questions;

//here we loop through the rows 
for($i=0;$i<$num_questions;$i+=$num_columns){ 
    echo '<tr class="table-heading1">';

//here we loop through the columns
for($j=1;$j<=$num_columns;$j++) {
  //if we need padding cells we break here.
  if(($i+$j) > $num_questions)
      break; 
  echo '<td valign="middle">' . ($i + $j) . "</td>\n";
}

//if we broke above adding padding cells
if(($i + $num_columns) > $num_questions)
     echo '<td colspan="' . $padding . "\">&nbsp;</td>\n";

echo '</tr>'; 
} //end for 
?>

As you can see the code is slightly optimized because it only executes 2 if statements. One executes num_questions times and one executes ciel($num_questions/$num_columns) times. As opposed to your original code which had three if statements executing $num_questions times.

Also it is much more user friendly because it will padd the table with blank cells if need be.

Hope that helps.

minorgod

Thanks for the excellent explanation. However this code lays out the questions horizontally instead of vertically. Vertical sequences are much trickier to do since we need to build the tables horizontally (unless we do some even trickier javascript manipulation of the DOM), but number them vertically. If you run the code in my original post, you'll see that it lays them out vertically. The strange thing is, my test code works perfectly for just laying out a grid of numbers, but now that I've added the correct content into the layout, I'm getting weird behavior that I suspect is just an error caused when I added the extra content into my script. It's a bloody mess because I'm displaying multiple grids of javascripted buttons. I'm looking for the bug now. I'd love to know if you can come up with a more elegant solution to laying out the content in vertical rows instead of horizontal ones though. Here's my test page with my script followed by your script...

http://www.realestate-school.com/layout_test.php

drawmack

To order the numbers vertically take a look at it like this.

You are printing a grid. The corordinates of each cell are row (y) and col (x).

Let's add a variable that let's us know how many rows we have, we'll call it $num_rows and it equals ceil($num_questions/$num_columns).

Now that we've defined a grid system let's take a look at the contents of each cell.

For values 30 (num quest) and 5 (num col)
The first row is: 1 7 13 19 25
The second row is: 2 8 14 20 26

Let's say 1 <= y <= $num_rows and 0 <= x < $num_columns. This gives us our loop delimiters.

So it looks like the matematical relationship of
$i - ($num_rows) + ($j+1)($num_rows) will give us the value for any cell. y = $i, x = $j

We don't use the formula in this exact format as it's easier on the cpu to just deal with addition and subtraction which we can so since we're inside of for loops. So we come up with code that looks like this.

<?php 
$num_questions=30; 
$num_columns=5;
//the number of rows
$num_rows = ceil($num_questions/$num_columns);

//here we loop through the rows 
for($i=1;$i<=$num_rows;$i++){ 
    echo '<tr class="table-heading1">';
    $start = $i - $num_rows;
    //here we loop through the columns
    for($j=$i;$j<($i+$num_columns);$j++) {
      $start += $num_rows;
      echo '<td valign="middle">';
      //are we printing a number or an empty cell
      if($start <= $num_questions)
          echo $start;
      else
          echo '&nbsp;';

  echo "</td>\n";
} //end for

echo '</tr>'; 
} //end for 
?>

NOTE: It would be neat if you broke out of the loops when you hit padding and just put in a single colspanned cell to do the padding, but that is left as an exercise for the reader.

Hope that helps.

minorgod

That's exactly the kind of mathematical explanation I was looking for. Thanks a million! I actually managed to hack my original algorithm to work correctly and it's very similar to yours now, but not quite as elegant. I think my version might actually be faster though, since there's only 1 loop with a few conditionals. Here's final solution...note that I chose not to echo the HTML via PHP for increased speed and visual editability. I remember reading an article that said it was faster to let apache render straight HTML rather than have PHP do it. Also, this allows me to visually edit the layout in dreamweaver since the HTML layout is not hidden in PHP, though it does make for a much harder code read:

<table border="1"> 
<?php 
$num_questions=100; 
$num_columns=5; 
$column_count=0; 
$row_count=1; 
//calculate the number of rows we will need in our grid. 
//we round up here in case there's any spillover 
$num_rows=ceil($num_questions/$num_columns); 
$num_cells=$num_rows * $num_columns;
for($i=0;$i<$num_cells;$i++){ 
    $column_count++; 
    if( $column_count==1 ){ ?> 
    	<tr class="table-heading1"> 
     <?php } //end if
    if( (1 * $row_count) + ($num_rows * ($column_count-1) ) <= $num_questions){ ?> 
      	<td valign="middle"><?php echo (1 * $row_count) + ($num_rows * ($column_count-1) ) ?></td> 
     <?php } else { ?>
	  <td>&nbsp;</td>";
	  <?php } //end if
    if($num_columns == $column_count){ ?> 
    </tr> 
    <?php $row_count++; 
		$column_count=0;
		}//end if 

} //end for 

?> 
</table>

Note that I was able to get rid of my $i-- statement by calculating the exact number of cells up front. That was the missing piece of my puzzle that allowed me to correctly render empty cells. Using my original method would be better if you didn't want to render the empty cells at all.

Thanks again for your explanation. This will really help me the next time I need to design a dynamic grid from scratch.

drawmack

As far as speed, we'd be spitting into the wind to argue it until you get around 2¹⁵ or so cells in the table it'll be too small to matter between these two scripts. As for echoing the html, I agree my program was academic where as your's is production.

I'm glad the explaination helped. It's also nice to see all that math they made me take in college has paid off for something.

drawmack

One question:
1 * n = n; n = any real number

So what exactly does this (1 * $row_count) accomplish?

minorgod

It was in there when I was thinking about the mathematical relationships and I just never removed it after I discovered I wouldn't need to multiply by anything. I was thinking I might need to replace the 1 with a variable to get things working so I just put it there to visualize things and then realized I didn't need it, but never removed it.