How do I find the best available position in a 2D array

Question

5.00/5 (1 vote)

See more:

Hi I'll try to keep this short,

So I'm working on a Cinema booking system and it is time for me to think of an algorithm to decide the "best" place(s) in the Cinema. I've been thinking of maybe using a BFS but jumped to the conclusion that this may not work as each hall may vary in size, on hall could have 20x30 seats, where an other could only have 8x5.

The problem is, given a number of people, find the best possible Seat(s) for each person so they're still able to sit next to each other.

My current solution is a n^2 complexity where I simply just check X to the left/right and Y up/down, but I'm curious if I could bring it into linear or even constant time and which algorithm could be useful for this.

For now it's decided that the best place is always right in the middle and as you move forward/backward or left/right the the place slow becomes worse. eg the worst place would be in a corner.

Thanks in regards, I don't hope this question is overly dumb :)

- Jackie

Posted 25-Nov-13 11:29am

Jackie00100

Updated 25-Nov-13 11:51am

v2

Add a Solution

Comments

Sergey Alexandrovich Kryukov 25-Nov-13 18:06pm

Before going into this complex issue of performance of the algorithm: you never defined what do you consider as "best", even for a single person. I know on my personal example, that it really depends on personal preferences. People are way too different, to assume anything in common in such a complex choice.

Now, what makes you thinking that you really need to look for less time complexity of the algorithm? For such a low number as the total number of seats in the cinema hall, the complexity of N^2 is next to nothing. If you don't do anything especially bad, any reasonable powerful computer should cope with each selection in no time. Am I right? Did you time it? What was you maximum total number of operations? I don't think it could be too big. Say, 2000 seats (600 is a relatively small hall), roughly speaking, some 2000^2 = 4,000,000 operations. Do you think this is a big number. And of course you will need less, so what's the problem?

It does not seems to me that the complexity evaluates to N^2, please see my answer.

—SA

Jackie00100 25-Nov-13 18:36pm

I kinda did define which we've chosen as the "best place" Quote: the best place is always right in the middle and as you move forward/backward or left/right the place slow.y becomes worse. eg the worst place would be in a corner.

BillWoodruff 25-Nov-13 18:15pm

Perhaps of interest: "Here's the visual guideline of the Society of Motion Picture and Television Engineers (SMPTE), as described by Ralph Davis, AMC's Vice-President of Facilities:

The horizontal subtended angles created by a customer's lines of sight to the left and right edges of the screen should not be less than 30 degrees. The viewer's vertical line of sight should not exceed 35 degrees from the horizontal to the top of the projected images. Ideally, the sightline should be 15 degrees below the horizontal centerline of the image."

http://gizmodo.com/5932765/how-to-find-the-best-seat-in-a-theater

Are you describing a system that automatically assigns seats ? The person booking has no choice in the matter ?

Sergey Alexandrovich Kryukov 25-Nov-13 18:19pm

Interesting information, thank you, Bill. By the way, I just answered the question, which anyway looks somewhat artificial to me, as I tried to explain in the above comments.
—SA

Jackie00100 25-Nov-13 18:33pm

It do wanna give the customer the option to change but I'm also thinking of trying to give it a test run where the system should be able to assign everything automatically. I know there is no such thing as the "best" seat, some prefer sitting closer of further way to/from the screen, but the idea was to have some sort of automated process to assign what would be the ideal "best" seat from knowledge, from your link for instance :)

BillWoodruff 25-Nov-13 19:48pm

I was going to post a response, but Ron already brought up the idea of "weighting" in his response: I think you are going to have to define some form of weighting algorithm, no matter how you proceed, and whether or not you factor in customer preferences.

I think this becomes a very interesting problem to consider if you really start trying to model a real movie theater. Perhaps assume a 15 degree stepped seating slope, assume a certain screen size, a certain distance between screen and first row, a certain row space distance interval, etc.

Where it would get really interesting is when you have an order for some arbitrary number of people who wish to sit together.

I'd see the automatic simulation of a series of booking orders in this scenario as kind of a form of unit-testing.

I'd try visualizing your ideas of optimum seating as a kind of geometric shape overlaid on the "grid of seats:" my choice would be think of two trapezoids together creating a kind of vertically stretched hexagon with its center somewhere ... vertically ... between one-third to one-half of the distance from first seat to the screen, and centered ... horizontally ... in the middle of the theater.

p.s. also see:

http://www.howstuffworks.com/question494.htm

Jackie00100 25-Nov-13 21:54pm

Thanks, Another thing I though about was to simply use datamining, and store data about where the most people would prefer sitting which is another fun idea I've been trying to put on the drawing board. But for now it seems I'm going for a sort of weights, either by masking or by a simple "length" calculation.

2 solutions

Add a Solution

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

Sergey Alexandrovich Kryukov · Accepted Answer · 2013-11-25T12:16:00

Solution 1

Please see my comments to the question, and the main one would be the first, about personal preference, which render the whole idea making little sense. However, it's not clear, maybe you already solved it. It can be solved by asking about personal preferences in some way. Every time I had to book fixed seats for my tickets, I was asked about my preferences, with some options followed with me.

Now, it looks like with your algorithm, the actual time complexity is O(N), in a worse case. Indeed, you have N seats, and can check all N, as a starting point for just one ticket. It gives you O(N) already. With each such seat, you need to check up at most X*Y seats around this point. But X*Y is a constant parameter. You don't test all values of y from 0 to X − 1, and the same for Y. This constant "carries out of brackets", it does not effect the complexity. This is because the constant factor does not change asymptotic behavior of a function.

Please see:
http://en.wikipedia.org/wiki/Computational_complexity_theory[^],
http://en.wikipedia.org/wiki/Time_complexity[^],
http://en.wikipedia.org/wiki/Big_O_notation[^].

—SA

Posted 25-Nov-13 12:16pm

Sergey Alexandrovich Kryukov

Comments

Ron Beyer 25-Nov-13 18:24pm

Sure, 5. I also added something about how to select the "best" seats.

Sergey Alexandrovich Kryukov 25-Nov-13 18:40pm

Thank you, Ron.

You are right: I did not state that his is the best way, I just described the estimate in worst case. My point is different: it does not really matter. What is 600 seats (or even 2000, for quite a big hall)? Nothing!

OP was probably mislead by something which could be just a misconception: representation of a hall as a M*N matrix, something 2D. But it has nothing to do with complexity of the algorithm. The algorithm still primarily scans all N seats.

—SA

Jackie00100 25-Nov-13 18:47pm

Time complexity have never been my cup of tea so sorry for any mistakes made :) but any how, it does right now run in what i believe should be N^2 (a for loop with a nested loop yes?) but it does check multiple seats each time as it check both up, down, and the sides. I read what you've wrote, but still doesn't seem completely obvious to me.

Sergey Alexandrovich Kryukov 25-Nov-13 19:31pm

Please, not need to apologize: the whole idea of asking your question here (and this is a correct reasonable question, no matter if you did any mistakes or not, in contrast to very many really pointless questions I we can see on this forum, so I only can say thank you for that) is to critically review your decisions and try no to overlook important improvements or fixes. Perhaps, to understand my estimate of complexity, you need to read on the theory, and perhaps on the some elementary calculus: how limit works and how asymptotic works.

Let's say, for simplicity, you have complexity of O(1). It means the time of calculation does not depend on the size of the data set. Now, change the complexity of the algorithm the way it works F times slower, where F is a fixed number of some operations. As O(1) means fixed number, let's say, we had L total operations before the change in the algorithm, and after adding complexity, we came to L*F. We made the complexity F times slower. What is the time complexity no, after it became F times slower? Still O(1).

And this is "even more correct" in the case of O(N), and all other functions. Fixed factor does not change complexity. In other words, asymptotic behavior "absorbs" the constant factors.

Are you getting the picture?

—SA

Jackie00100 25-Nov-13 21:46pm

Magic! got it :D - hehe all seriously - I do have a bit knowledge about this but never really understood how to calculate it probably, and never really have much interest in it either which I will agree on is sad and really lazy to say. I kinda get that tree structures run at log(n) if I remember correctly, binary search and such. I've tried to read on it multiple times but I tend to forget it fast afterwards. I'll have another look in near future, probably worth the while!

Sergey Alexandrovich Kryukov 26-Nov-13 0:14am

I perfectly understand you here, including some laziness. Here is my approach to some reading: anyway, there are things which you better understand only after you solve some problems by yourself. Sometimes I intentionally don't read on some topic before I think about it myself or try to solve some problem. It has two benefits: 1) you use yourself a chance to invent/discover something new before existing knowledge leads you away from the new ideas; 2) you get more familiar with the subject or more interested in it, it will give you better understanding when you finally get to reading. How about this idea?

Good luck, call again.
—SA

Jackie00100 26-Nov-13 6:47am

I'll give that idea a shot Thanks mate :)

Sergey Alexandrovich Kryukov 26-Nov-13 11:20am

Sure. Good luck, call again.
—SA

Ron Beyer · Accepted Answer · 2013-11-25T12:23:00

Solution 2

To add to what Sergey said (in that finding the seats is O(N), but really doesn't say what ones are the "best".

You could assign weights to each seat, with "better" seats having higher values. While searching for seats you hold the currently selected seats as the highest value (sum of y (where y is the number of required seats) seats in a row for each guest). If you find y seats with a higher value, select those.

This then can come down to a simple sorting algorithm, where you remove occupied seats from the list and then sort based on index. After that you just select the top y seats that are sequential.

Posted 25-Nov-13 12:23pm

Ron Beyer

Comments

Jackie00100 25-Nov-13 18:41pm

I did think about doing this too but I tried to wrap my head around if there were any better solutions - that's what caused this question in the first place :)

Sergey Alexandrovich Kryukov 25-Nov-13 18:57pm

Again, why would you need a much faster solution? You 600 seats is next to nothing... :-)
—SA

Jackie00100 25-Nov-13 19:08pm

Well, I've always been glad to have all the cards on the table, I feel sometimes it's better to take the extra time needed to think about an optimal solution rather than the fast (and maybe even less optimal), also the calculation is needed to be calculated on a server where from my knowledge a lightweight solution is preferable.

Sergey Alexandrovich Kryukov 25-Nov-13 19:35pm

I really appreciate your attitude...
—SA

Jackie00100 25-Nov-13 21:33pm

Sarcasm?

Sergey Alexandrovich Kryukov 26-Nov-13 0:05am

No way, why? Seriously...
—SA

Jackie00100 26-Nov-13 6:44am

The dots made it seem like you didn't meant it :D but nvm

Sergey Alexandrovich Kryukov 26-Nov-13 11:31am

Please stop it. You need to learn about the expressive meaning of punctuation and not imagine who knows what.
Do I have to convince you it's not sarcasm? I would prefer not to... :-)
—SA

Jackie00100 26-Nov-13 12:24pm

Well you could always write a algorithm running in polynomial time to decide whether a given comment is sarcastic ;)

Sergey Alexandrovich Kryukov 26-Nov-13 12:33pm

:-)

Sergey Alexandrovich Kryukov 25-Nov-13 18:56pm

Well, the seat weight is the next step, not much related to the time complexity (but something which could make total time longer; in practice, we ultimately care only about the total throughput, don't we? :-).
Again, the complication is the personal preference; ignoring it would totally defeat the purpose of the whole thing. And the result of the selection should be giving out several options. In practice, this is the user who can assign weights to the preference factors, but people cannot do it precisely and could shift them depending of available choices, which is actually is a perfectly rational behavior.
So, the fuzzy-set theory can also be used. (Are you familiar with it? Even if you are not, I'll vote 5... :-)
—SA

Jackie00100 25-Nov-13 19:11pm

Well I guess I'll stick with some sort of weights - I'll give it a shot :)

Ron Beyer 25-Nov-13 19:12pm

Yes, I am vaguely familiar with fuzzy set theory (I did an MIT online course in AI which one topic was fuzzy sets, still fuzzy on it myself but I get the concept). There's a couple paradigms that can be applied here, none of which should increase time.

Sergey Alexandrovich Kryukov 25-Nov-13 19:36pm

:-)

How do I find the best available position in a 2D array

2 solutions

Solution 1

Solution 2

Add your solution here

Preview 0

How do I find the best available position in a 2D array

2 solutions

Solution 1

Solution 2

Add your solution here

Preview 0

Existing Members

...or Join us