Search matrix for all rectangles of given dimensions (select blocks of seats)

Question

All,

I have been trying to work out how to select say 15 tickets within a single block of seats.

EDIT: the problem is - how to find all rectangles of given dimensions (say 3x5 for example) of free seats?

The below is my table, and the query selects 4 consecutive seats (or 15 or whatever) which is fine...

But what I want to do is select say 15 seats, these may be split over multiple rows, i.e. 3 x 5, but I would want them to be blocked together i.e.

row 9 ..(some seats)..[5 seats]..(some seats)..
row 8 ..(some seats)..[5 seats]..(some seats)..
row 7 ..(some seats)..[5 seats]..(some seats)..

I.e. they would be 3 rows all in front of each other. row9 seats 10 to 25, row8 seats 10 to 25, row7 seats 10 to 25.

Also may need to consider if a block of seats have varying number of seats i.e. a corner block may be in an arc to has more seats at the back than the front.

Any guidance in form of ehnaceing the SQL or some algorithm or some PHP code. I have been wracking my brain for most of the week now.

CREATE TABLE `seats` (
  `id` int(11) NOT NULL AUTO_INCREMENT,
  `event_id` int(11) DEFAULT NULL,
  `performance` int(11) DEFAULT NULL,
  `block` int(11) DEFAULT NULL,
  `row` int(11) DEFAULT NULL,
  `seat` int(11) DEFAULT NULL,
  `status` int(10) DEFAULT 1,
  PRIMARY KEY (`id`)
) ENGINE=MyISAM AUTO_INCREMENT=11 DEFAULT CHARSET=utf8;

My query to-date - which returns combinations of blocks of X seats.

SELECT    a.event_id, a.performance, a.block,
          a.row, a.seat AS start_seat,
          a.seat + (4 - 1) AS end_seat,
          4 AS requested_seats,
          a.id AS start_allocation_id
FROM      seats a
          LEFT JOIN seats b ON
              a.event_id = b.event_id AND
              a.performance = b.performance AND
              a.block = b.block AND
              a.row = b.row AND
              a.seat < b.seat AND
              b.seat < a.seat + 4 AND
              b.status = 1
WHERE     a.status = 1 AND
          a.event_id = 1
GROUP BY  a.seat
HAVING COUNT(b.seat) + 1 = 4
ORDER BY performance

Thanks in advance, need more info please just ask!

Busby

I'm not sure I got the idea of what you're trying to do and what is the situation... but what about applying a mask (like an IP subnet mask) of available seats in a row ? e.g. 00011111000, all the 1's are available. – Medalist

Brian, are you trying to find all rectangle blocks 3x5 of free seats? Is that correct? – Corazoncorban

I posted an answer - is this what you want? – Corazoncorban

you could modify this single pass linear solution that find largest rectangle to stop as soon as it find a rectangle of required size – Confectionery

Answer 1

This problem is much better solved outside mysql, in another language. In other words, you have a matrix of seats, some of which are occupied (grey ones):

and you want to find all rectangles of given dimensions, say 3x5. You can do this very efficiently by two pass linear O(n) time algorithm (n being number of seats):

1) in a first pass, go by columns, from bottom to top, and for each seat, denote the number of consecutive seats available up to this one:

repeat, until:

2) in a second pass, go by rows, and look for at least 5 consecutive numbers greater or equal to 3:

so, finally, you get:

which yields the solution: these number sequences (green areas) are top edges of the 2 possible rectangles 3x5 of free seats.

The algorithm could be easily enhanced to e.g. get all rectangles with maximum area. Or, it could be used to find any continuous regions (not only rectangle-shaped) of N seats - just, during the second pass, look for continuous sequence of numbers which sums up to at least N.

Corazoncorban

Very nice, given that the naive solution (trying every bounding box) is at least O(nm), where m is the size of the block. How would you find a block of seats for 7 people, though? – Cheater

@Nick, very simply - in the second pass, just look for sequence of numbers which sums up to at least 7. You can e.g. add a condition like "no more than two rows", so in that case each number > 2 would only count as 2. – Corazoncorban

Project was binned sadly... but would have been an elegant solution tho. – Busby

Answer 2

From your description this isn't a database problem but an algorithmic problem. I suggest a tiling schema maybe a quadtree or a space-filling-curve. Perhaps a spatial-index in MySQL would help you solve your problem, too. A si subdivide the 2d plane into 4 tiles.

Solferino

Cheers for that... great info to investigate, as you can appreciate the complexity (and very busy) it may take some time to verify findings! I have up-voted in the mean-time, – Busby

I don't think doing this in the DB is a good idea. A venue is small enough that it's likely to be quicker and more efficient to load it into memory and do operations there, rather than doing disk ops. – Cheater

all this is overly complicated. There is very simple solution in O(N), see my post. – Corazoncorban

Answer 3

I came here looking for a Python solution. Here is mine, which returns all positions:

import numpy

s = '''0 0 0 0 1 0 0 0 1 0 0
0 0 0 0 0 0 1 0 1 0 1
0 1 0 0 0 0 0 0 0 1 0
0 0 0 0 0 0 0 0 0 0 0
0 0 1 1 0 0 0 0 0 0 0
0 0 0 0 0 1 0 0 0 0 0'''

area = 15
nrows = 6
ncols = 11
skip = 1

a = numpy.fromstring(s, dtype=int, sep=' ').reshape(nrows, ncols)
w = numpy.zeros(dtype=int, shape=a.shape)
h = numpy.zeros(dtype=int, shape=a.shape)
for r in range(nrows):
    for c in range(ncols):
        if a[r][c] == skip:
            continue
        if r == 0:
            h[r][c] = 1
        else:
            h[r][c] = h[r-1][c]+1
        if c == 0:
            w[r][c] = 1
        else:
            w[r][c] = w[r][c-1]+1
        minw = w[r][c]
        for dh in range(h[r][c]):
            minw = min(minw, w[r-dh][c])
            if (dh+1)*minw == area:
                print(
                    'area', area, 'row', r, 'col', c,
                    'height', dh+1, 'width', minw)

Output:

area 15 row 4 col 8 height 3 width 5
area 15 row 5 col 10 height 3 width 5

Testee

Answer 4

    $nr_tickets = 15; // or whatever


// build an array of different configurations:
// since you always want people as close to eachother as possible this is a suggestion:

$configurations = array();
for($columns=1; $columns<=$nr_tickets; $columns++)
{
    $BLOCK = array();
    $remainder = $nr_tickets % $columns;
    // $nr_tickets - $remainder = greatest number divisible exactly by $i (columns) which is the number of rows you want.
    $rows = (($nr_ticket-$odd) / $i);
    //$configurations[$columns] = $rows // make a rectangle configuration or $columns x $rows with $remainder tickets left.
    $BLOCK[] = array_fill(0, $columns, array_fill(0, $rows, X); // multidimensional array
    for($a=0; $a<$odd; $a++)
    {

        // each of the remainder seats need to be 'stuck on to the block/rectangle of seats you already have, this can be done in
        // ($rows + $columns * 2) - $a ways for each of the consecutive non-assigned tickets
        /*
            lets say you have a block of 2x7 (s) with 1 (N) possible ticket left 
                   N  N  N  N  N  N  N  
            N  s  s  s  s  s  s  s  N 
            N  s  s  s  s  s  s  s  N   
               N  N  N  N  N  N  N 
        */
        // so basically we can add a ticket to each of the rows and for each of those configurations we need to add $a more
        // this may be simpler with a recursive function call that adds $a more for each 1 ticket you add here to a row or a column. 
    }


}



// now you can go select all different permutations of settings from the database and select one you like :) 

Pinole

just a 'draft' btw, but you get the idea – Pinole

yip have written something like this already - blocks may be curved or trapezoid shaped with fewser seats at front than rear – Busby

Answer 5

I would just write a query for each row and combine it using UNION if you can programmatically create your query, then just use the same query X number of times just keep appending them with UNION.

From the mysql manual

UNION is used to combine the result from multiple SELECT statements into a single result set.

Salverform

Had already done this, which was fine for proof-of-concept - but if you were handling 100s or 1000s of booking requests this is not workable :) – Busby

Answer 6

First, I'm going to assume that most venues can be mapped (even if approximated) to a square grid, ie. where the seats aren't strangely setup or weirdly offset. As such, each seat may have up to eight seats around it.

CREATE TABLE Seat {
   SeatID int,
   Status int,
   ...
   NorthID int,
   NorthWestID int,
   WestID int,
   ...
   NorthEastID int
}

Essentially, I will be able to create a "seat graph" and walk it according to needs in querying. Then, you can create queries to get certain shapes or blocks.

A 3x3 grid would consist of selecting an open seat where the immediate linked seats in all directions are also open. Yes, it would be eight JOINS, but try it out and optimize later.

SELECT * FROM Seat x
INNER JOIN Seat n ON x.NorthID = n.SeatID
INNER JOIN Seat nw ON x.NorthWestID = n.SeatID
...

A 1x15 block would be a query to select an open seat where you join 14 deep along the EastID or WestID.

You can probably generalize and generate the queries programatically.

PS: Depending on which engine you are using, you may have built-in spatial capabilities.

Good luck.

Colet

Answer 7

Here is a straightforward approach. It may not be fast enough for your needs, but it is a place to start.

Let's simplify the problem and consider a table called seat having columns row, col, and taken. The first two are integers, the other is a boolean. We want to find values of row and col constrained to certain sized rectangles wherein taken is universally false. We'll try a query which moves a rectangle around and records the sum of the taken values within. The rectangles we want will have a sum of zero.

Let's just say we're looking for 2x2 blocks of open seats. Here's the query.

SELECT row, col,
       (select sum(taken) from seat as s2
               where s2.row >= s1.row and s2.row < s1.row + 2
                 and s2.col >= s1.col and s2.col < s1.col + 2) as count
       FROM seat as s1

Just filter the output of this query where count = 0. The row and col will designate the upper left corner of the open block. One final quirk is that you will want to filter out upper left corners that cut too close to the right or bottom edges of the seating, because that will artificially decrease their sum (the tested rectangle is clipped against the edges of the seating). In the case of 2x2 blocks, this means row < max(row) and col < max(col).

Now in the case of finding 15 adjacent seats, you are looking for 15x1, 1x15, 3x5 and 5x3 rectangles. You could make the above query into a stored procedure that takes rectangle width and height parameters, and then call it with those sizes until you find a match.

Dacy