Reservations in the tavern. There are long tables consisting of N small ones. Behind each little one, you can seat 2 people, and only beyond the extreme - 3 (two on the sides and one at the head of the table, it turns out):

xxxx x[ ][ ][ ][ ]x xxxx 1 2 3 4

There is a variant of long tables, when there is a place at the head of a table on one side only.

Visitors choose a table and indicate how many people there will be.

The desired booking algorithm should choose the best places for K people at their chosen table. For example if 3 people arrived and the table is empty so far - let them go to the last table, of course. 2 came to them from the other end.

  oxxo o[-] [ ][ ] [-]x oxxo 1 2 3 4

It is undesirable to replant - bought - received a letter with a ticket for two at a table 21 (3), for example. Maybe it was better for two people to saw off the 3rd table, because more likely that someone else will need 3 places at once? What does teverver say?

There are two more questions:

  1. Do you know the "classic" algorithm for such a task of gradual cutting?
  2. How would it be better in the code to describe such long tables and their current fullness? The language is unprincipled, but now I write it on JS, a long table is an object (there is also drawing it in SVG). From the server about the long table comes JSON with numbers of sub-tables : ) for each reservation: [{"n":4,"desks":[1,2]},{"n":3,"desks":[4]},]

The feeling that I invent the bicycle, does not give rest. Need a fresh look!

  • > 2 came to them from the other end. It is not clear why this is optimal. Isn't it better to put them at the second table on the left, so that if 5 more people come, they will find a place? - VladD
  • one
    This I suggested from the logic by which the urinals occupy - trying max. to distance oneself from the neighbors:) For 2, on the other end, in fact, it makes sense only for the case of “with one tamada” —when someone is sitting on one side, and already the odd is busy. The choice between comfort and optimum filling. Another rule is: If there are three, and there are only 2x2 tables, they will have to buy 4 places. - Sergiks
  • Then the objective function is not completely clear. I correctly understand the algorithm: (1) the group should sit together, (2) if possible, there should be free space between beginners and those already at the table, (3) a probabilistic distribution of the number of people in the group is given, (4) find an algorithm, maximizing the expectation of the average number of people at the table. - VladD
  • Right. Only data from (3) will begin to be collected from scratch, as we launch this system. This is a blues club, there is not always going to pairs for the handle. - Sergiks
  • one
    Yeah, got it. It is necessary to think, but in general, the task is for mathematicians, not programmers. - VladD

1 answer 1

Very unsure of his version and would have written in a comment, but not a contagion)) Well, oh well, we will risk it

Below is a link to an example, but since there is a full * ovnod there, I will describe the meaning here. Table sections and footprints are located in a multidimensional array, more precisely an object:

 var allTables = { 0:{ t1:[0,0,0], t2:[0,0], t3:[0,0], t4:['reserv1','reserv1'], t5:[0,0,0] }, 1:{ t1:['reserv2','reserv2','reserv2'], t2:[0,0], t3:[0,0], t4:[0,0], t5:[0,0,0] }, 2:{ t1:[0,0,0], t2:[0,0], t3:[0,0], t4:[0,0], t5:[0,0,0] } };

Zero values ​​are empty spaces. The values ​​of the reserved seats can be order numbers or just some value! = 0 at its discretion. We get the number of seats that must be booked (for example, take 4 ). We run over the tables, in each we find a row of empty places. For example, on the first table - it will be 7 and 3 places. In the same cycle, we find completely empty sections and their number of places. Again, on the first table - we get such an array [3,2,2,0,3]. I'll go: not arrays, but objects . Next, compare the desired number of booking places with the first object. If this number is 7 or 3, then we return the corresponding key. Since we agreed that seats 4, then we go further. We are looking for a match in the second object. If we had to reserve 2 or 3 places, then if we coincided, we would also return the corresponding key, but we have 4 and we proceed to a simple search, using the second object ( [3,2,2,0,3] ) . We are looking for the nearest empty sections, the number of places which, in the amount will give us the right, i.e. 4. In our case, the second and third sections are suitable: t2, t3 . Calculating them, we pass an array of keys of these sections. Next thing technology. In the objects, we change the zero values ​​to the order number. If necessary, then display on the screen.

Now, just a couple of words, about if a decent option was not found on the current table. For example, the number of places is 6 . In this case, instead of keys, we get "undefined" and recursively send the index of the "second table" to the above process. There, for 6 places, there is a variation of the 2nd, 3rd and 4th sections. If there are 12 places, then it’s natural that we’ll stop at the “third table”.

Actually, here is my * ovnoprimer in action . To say that it is not finalized means to say nothing, but at 5 o'clock in the morning there are no forces to fight. )) One way or another, I hope that at least something helped.

  • Thank you very much for the detailed answer! Complicated beyond the task, or I vaguely described. Tables are one-dimensional: #### and one person cannot sit exactly at one: they put min 2 at the sub-table (1 wants to come - you need to buy 2 tickets), or optionally 3 at the extreme. Therefore, we can describe the occupancy of a long table as an array of 0.2, or 3: [3,0,0,2] . Then the maximum that can be set for it is (число 0-подряд)*2 + the number of extreme zeros included there. Or in a separate array to keep the maxima of the seats: [3,2,2,2] for the table, in which the head can be planted only on one side. - Sergiks
  • And for svg-drawing, the border of zero and non-zero employment value will be an indicator of the "break" of the table in this place. Thanks, helped me "drive" in the task! I'll do it, show you what's coming out! - Sergiks