[thelist] PHP algorithm help
Andy Warwick
mailing.lists at creed.co.uk
Wed Sep 3 06:06:31 CDT 2003
Hi
Having a complete non-brain day, and can't seem to crack the following
algorithm.
I've got multiple rows of 'image slots', and need to randomly place a
single image in each row, thus:
++++++++0++++++++++++++++++++
+++++++++++++++++0+++++++++++
++++++0++++++++++++++++++++++
+++++++++++++0+++++++++++++++
What I need to avoid is two images in adjacent rows being too close to
each other, thus:
++++++++0++++++++++++++++++++
+++++++++++++++++0+++++++++++
++++++0++++++++++++++++++++++
+++++++0+++++++++++++++++++++
Images at least one row apart are fine to line up, thus:
++++++++0++++++++++++++++++++
+++++++++++++++++0+++++++++++
++++++0++++++++++++++++++++++
+++++++++++++++++0+++++++++++
I figure I need some way to draw the grid row-by-row, generating the
valid slots for each row depending on the position of the image in the
row directly above.
Assuming $row_length is the length of each row, $prev_row_pos' is the
position of the image in the previous row, and $min_sep is the minimum
separation of the images, I need to find all the valid values of
$cur_row_pos, which are the legal values for the position of the image
in this row.
So for a 2 rows of eight, with a minimum separation of 2 I would have:
$prev_row_pos valid values of $cur_row_pos
------------ -----------------------
1 4, 5, 6, 7, 8
2 5, 6, 7, 8
3 6, 7, 8
4 1, 7, 8
5 1, 2, 8
6 1, 2, 3
7 1, 2, 3, 4
8 1, 2, 4, 4, 5
What I can't seem to do is get the generic algorithm that works for all
row lengths and all separations, combined with a program structure that
avoids having to randomly assign the image position, check it and--if
invalid--try again; I assume it would be faster (and more elegant) to
create the array of valid values of $cur_row_pos, and *then* assign
one?
So far I've got:
<pre>
<table border="1" cellpadding="3">
<?php
$num_rows = 10 ;
$row_length = 8 ;
$min_sep = 2 ;
$prev_row_pos = 0 ;
$cur_row_pos = rand( 1, $row_length ) ;
for ( $row = 0; $row < $num_rows; $row++ )
{
echo '<tr>' ;
if ( $prev_row_pos !== 0 ) { // Ignore for first row
while ( ! ( $cur_row_pos < $prev_row_pos - $min_sep OR $cur_row_pos
> $prev_row_pos + $min_sep ) ) {
$cur_row_pos = rand( 1, $row_length ) ;
}
}
for ( $i = 0; $i < $row_length; $i++ ) {
echo ( $i + 1 !== $cur_row_pos ) ? '<td>+</td>' : '<td
bgcolor="#999900">O</td>' ;
}
printf( '<td>curr_row_pos: %s; prev_row_pos: %s</td></tr>',
$cur_row_pos, $prev_row_pos ) ;
$prev_row_pos = $cur_row_pos ;
}
?>
</table>
</pre>
Which works AFAICT, but as the separation gets larger the time taken in
the while loop, checking for valid values, increases horribly.
Is this really the most efficient way to do it?
Any math's/PHP whiz care to help me out?
TIA
--
Andy Warwick
Creed New Media Design
w: http://www.creed.co.uk
More information about the thelist
mailing list