Algorithm for Room Allocation Using PHP

I need help with an algor开发者_StackOverflow中文版ithm to allocate rooms to people. I need to shuffle through a list of rooms to assign a room to a person and after the fourth person is assigned to the room, it should be out of the list(should be unavailable). I have not had any luck with PHP shuffling and sorting functions yet.

Any help (pointers, references, etc.) will greatly be appreciated.

---

This sounds like both a homework assignment and a problem with thousands of solutions.

As Jack already said, try to develop your algorithm before you try to implement it in code. If you're having trouble understanding this, then just imagine the scenario and try to write simple rules for solving it in real life

Let's say I have a hallway with 10 rooms. Each room can support up to 4 people. Then 35 people show up and want to be assigned to rooms. How would I do this?

I would probably start at the beginning of the hallway and fill up the first room, then fill up the next room, and continue until I ran out of people or rooms (whichever came first). This solution has the advantage of not having to walk very far down the hallway, but the disadvantage of crowding 4 people into one room instead of spreading them evenly.

If you chose to spread them evenly then you'd want to put one in the first room, then one in the second room, etc. Do this until you run out of rooms, then go back through every room putting a second person.

Since you have two methods of doing this, the next step is determining how to represent your basic components in code. You need a way to represent a room and a way to represent a person. The most important feature of a room is that it can hold up to four people, but it always has to know how many people it's holding. Therefore it might be good to think of each room as it's own number, the number telling you how many people are already in that room.

In PHP, if you want several numbers which are related and ordered (as the rooms in a hallway would be) you use an array. This is true when you have several of ANY variable that need to be related to one another and maintain their respective order.

$rooms = array(0, 0, 0, 0, 0); // 5 rooms, all with 0 people in them

If your room needs to know who is staying in the room (if they need to differentiate between different guests) then you might consider each individual room as a 4-element array, each element of which represents a person and is able to identify that person.

$rooms = array(
    array(null, null, null, null),
    array(null, null, null, null),
    array(null, null, null, null),
    array(null, null, null, null),
    array(null, null, null, null)
);

After you've created your rooms, you have a certain number of people who are waiting to enter a room. Since each person only counts as 1, unless you need to remember extra information about each person (such as their name, age, etc.) then you should be able to see a very convenient way of representing people.

$peopleNotInARoomYet = 10;

If you do need to remember extra information about these people (suppose after assigning rooms you are asked the question "In which room is Bob?") then you would need something much more intelligent. Perhaps an array of classes, each class representing a person. Unless, of course, the person need only be represented by a single variable. Then you could boil them doing to just an array.

$peopleNotInARoomYet = array("Bob", "Sally", "Bill", "Mary");
//or
$peopleNotInARoomYet = array(new Person('Bob'), new Person('Sally'), new Person('Bill'), new Person('Mary'));

Note that the second method required the Person class already be defined, and it can get very convoluted if you aren't careful.

Once you have a way of representing the people, you want to loop through every person to find them a room. If people are represented by a single number, this would look like:

while($peopleNotInARoomYet > 0){
    // Assign a room
    $peopleNotInARoomYet--;
}

If the people are represented as an array, you might want to consider the PHP array_pop() function.

PHP.net array_pop manual

$nextPerson = array_pop($peopleNotInARoomYet){
while($nextPerson != NULL){
    // Assign a room
    $nextPerson = array_pop($peopleNotInARoomYet);
}

Having a way to represent rooms and people now, your new task is to take our definition of assignment from above and turn it into code. So let's look at our first (and probably simpler) method. We put people into a room until it's full, then go to the next room.

This actually poses a few algorithmic challenges. First, how do you "put someone into a room"?

The answer to this actually depends on which definition of a room we used. If we simply had an array of integers (the case when we care how many people are in a room but do not care who is in the room) then we need to add one to this integer.

If we had an array of 4-element arrays, then we need to find the first empty element and place the person in that element. Putting a person into a non-empty element will replace the person who was there before.

Since it's obvious from this first attempt to convert our rule set to code that the method will differ depending on the implementation chosen, for the rest of the example I will assume that rooms need only know how many people are in them, and not who is in them in specific. If you do need this further information, that's a lesson left up to the reader to figure out on their own.

So here's our definition of a room, a person, and the beginning of our loop:

<?php
    $rooms = array(0, 0, 0, 0, 0); // 5 empty rooms
    $peopleNotInRoomsYet = 14; // We'll choose a number that won't divide evenly

    while($peopleNotInRoomsYet > 0){
        // Assign a room
        $peopleNotInRoomsYet --;
    }
?>

And we know that once we've chosen which room to put someone in, actually putting them there involves the following:

$rooms[$roomNumber]++;

So now let's go back to our original problem definition and see where we left off. We want to fill up the first room, then the second, then the third, etc.

So first we needed a way to define filling up a room. Well filling a room involves putting people in it (done) until it's full (not done). So now we need a way to check and see if a room is full.

if($rooms[$roomNumber] == 4)

should do nicely. So now we have a way of "filling a room until it's full"... But after this we need to start on the next room. This means we need to always know which room we are currently filling. If there's something new that we need to know, we need a new variable for it. Let's call this variable $roomNumber. We'll start with $roomNumber = 0; (the first room in the array) and continue until it's 5. Since there is no sixth room (element 5) then if $roomNumber ever becomes 5, we have too many people.

<?php
    $rooms = array(0, 0, 0, 0, 0); // 5 empty rooms
    $peopleNotInRoomsYet = 14; // We'll choose a number that won't divide evenly
    $roomNumber = 0;

    while($peopleNotInRoomsYet > 0){ // If there are people waiting...
        if($rooms[$roomNumber] == 4){ // If the room is full...
            $roomNumber ++; // Go to the next room
        }
        if($roomNumber == 5){ // If we are out of rooms...
            die("Too many people!!!"); // die
        }
        $rooms[$roomNumber] ++; // Otherwise, add someone to the room
        $peopleNotInRoomsYet --; // And remove them from the waiting list
    }
?>

I know this was extremely length for the tiny amount of code we ended with, but I was attempting to explain the process of going from concept to code. Recognize the simple rules that you need to follow, then recognize the items you need to keep track of. Also remember that the solution I posted works only in the simplest situation, that being you don't need to know who is in the room, just how many people. It also assumes that no room starts with anyone in it. If room two started out full then this algorithm would fall apart since I didn't check for that. There are plenty of modifications left to be done by the reader, but this should get you pointed in the right direction.

---

This is not directly a PHP question, you should first describe the algorithm and then try to implement it.

From what I understand the best solution would be to keep a list of rooms sorted by actual empty spaces (so at the beginning you will have empty rooms, then rooms with 1 people, then rooms with 2, etcetera).

Then whenever a new user comes you have to choose a policy to assign it to a room, for example you could choose to always add the newcomer to a most empty room (so you will choose a random one between the empty ones, or between the rooms with just 1 people if no empty one is available and so on).. or you could decide to assign it to one random room which is not full. It depends on what you really need to do.

In anycase you could keep 2 lists of rooms, one for the not-full and one for the full rooms. When a room becomes full because a newcomer fills it you just swap it to the other list. When, instead, an user leaves a full room you switch it back to original list.

Of course keeping the not-full room list ordered by empty spaces is useful just when you policy needs to perform a choice that depends on how many empty spaces there are in any room, otherwise you could just keep all of them together and choose one randomly.