Beefy Boxes and Bandwidth Generously Provided by pair Networks
Don't ask to ask, just ask
 
PerlMonks  

comment on

( [id://3333]=superdoc: print w/replies, xml ) Need Help??

For each room type you have available, allocate the most people you can to the room, repeat until you run out of rooms. Do it recursively for each legal possibility and then sort them by the amount of rooms used and the amount of wastage on the room. Somthing like below.

By-the-way, for some reason i see this as more of a game play kind of scenario. You can kind of imagine a room allocation as a "move". Some moves prevent other moves, and ultimately a move cant be properly scored until you see its consequences. Thus for instance if you were allocating lots of people over lots of rooms types, the recursion would start getting heavy, so you could use wastage to prune moves. Ie, once the accumulated wastage went over a certain threshold it doesnt matter how you allocate the following moves, they are still in a losing "game".

Also, i should say that I think an important simplification is that you probably aren't trying to match people to specific rooms, but rather to one of many rooms of a given type. So dont iterate over all the rooms, iterate over the roomtypes that are available, and keep track how many of each you have. Then once you have allocated recurse in and do it again, with the new people and room counts in play. By doing it this way you reduce the number of possible moves at any one time by not having to worry about "duplicate" moves where book the people into different rooms with identical characteristics. This should keep the size of the search space managable. I mean my girlfriend works in the business and she says twenty room types would be quite a lot for even a large hotel. Something like this is fairly managable IMO.

So for instance the procedure might be something like selecting the room types and counts for all rooms available in the required time-period, then applying something like the below code on the results.

Anyway, here is my really hacky attempt at a solution. (really hacky, im too tired now to document it or clean it up, maybe another day)

use strict; use warnings; use List::Util qw(sum min max); use Data::Dump::Streamer; $|++; my $id=0; my @rooms = map { $_->{id}=$id++; $_ } sort { $b->{maxocc} <=> $a->{maxocc} } ( { name => "Double", maxocc => 2, maxadults => 2, maxchildren => 0, maxinfants => 0, propertyid => 1, }, { name => "Triple", maxocc => 3, maxadults => 3, maxchildren => 3, maxinfants => 2, propertyid => 1, }, { name => "Quad", maxocc => 4, maxadults => 4, maxchildren => 2, maxinfants => 2, propertyid => 1 } ); sub find_best { my ( $res, # where the list of possible tuples will go $adults,$children,$infants, # how many people $rref, # this is data about the rooms we have already booked $depth, # depth for debugging only @rcounts, # count of rooms, in the same order as @rooms )=@_; #print " " x $depth,"$adults,$children,$infants [@rcounts]\n"; if ( $infants + $adults + $children <= 0 ) { # if we get here we either have an error case ( sum < 0) if ( $infants + $adults + $children==0 ) { # or we have alocated all the people and we can use this # combination push @$res,$rref; @$rref=sort { $a->[3]{name} cmp $b->[3]{name} } @$rref; # add in some total info. unshift @$rref,0,0; foreach my $item (@$rref) { next unless ref $item; $rref->[0]+=$item->[1]; # wastage $rref->[1]++; # rooms } } return; } # see what the possibilities are my @ok; foreach my $roomid (0..$#rooms) { my $room=$rooms[$roomid]; next if $rcounts[$roomid]<=0; my ($ad,$ch,$inf)=(0,0,0); if ($room->{maxinfants} and $infants and $adults) { $ad=1; $inf=min($room->{maxinfants},$infants); } if ($room->{maxchildren} and $children and $adults and $ad+$inf < $room->{maxocc} ) { $ad||=1; $ch = min( $room->{maxocc} - $ad - $inf, $room->{maxchildren}, $children); } if ($room->{maxadults} and $adults-$ad>0 and $ad+$inf+$ch < $room->{maxocc} ) { $ad+=min($room->{maxocc} - $ad-$inf-$ch, $adults - $ad ); } if ($ad+$ch+$inf) { push @ok, [ $ad+$ch+$inf, # total $room->{maxocc} - $ad-$ch-$inf, #wastage $ch + $inf, # kids $room, # room hash $ad, $ch, $inf ] # counts } } return unless @ok; # dunno if this sort is really necessary. @ok=sort { $a->[1] <=> $b->[1] # minimize wastage! || # get rid of the kids first $b->[2] <=> $a->[2] || # get rid of as many people as possible $b->[0] <=> $a->[0] } @ok; # ok now see what possible followup room bookings can be made for my $try (@ok) { next unless $try; my @rref=(@{$rref||[]},$try); my ($total, $wastage, $kids, $room, $ad, $ch, $inf)=@$try; local $rcounts[$room->{id}] = $rcounts[$room->{id}] - 1; #print "$room->{name} Occupants:$total (Adults:$ad Children:$c +h Infants:$inf) [$wastage]\n"; find_best($res, $adults-$ad, $children-$ch, $infants-$inf, \@rref,$depth+1, @rcounts); } } sub pair { # utility function my ($array1,$array2)=@_; return join ", ",map { (ref $array1->[$_] ? $array1->[$_]{name} : $array1->[$_]). " => $array2->[$_]" } (0..min($#$array1,$#$array2)); } my @people=qw(Adults Children Infants); for my $cond ( [[4,1,0],[0,2,2]], #people, rooms [[6,0,0],[1,1,4]], ) { my @res; print "Finding best fit for ". pair(\@people,$cond->[0]). "\n\t in rooms ". pair(\@rooms,$cond->[1])."\n\n"; find_best(\@res,@{$cond->[0]},undef,0,@{$cond->[1]}); @res=sort { $a->[0]<=>$b->[0]||$a->[1]<=>$b->[1]}@res; my %seen; foreach my $res (@res) { my ($wastage,$rooms,@trys)=@$res; my $room_key=join "-",map { $_->[3]{name} } @trys; next if $seen{$room_key}++; print "Rooms:$rooms Wastage:$wastage\n"; foreach my $roomdata (@trys) { my ($total,$wastage,$kids, $room, $ad, $ch, $inf)=@$roomda +ta; print "$room->{name} Occupants:$total (Adults:$ad Children +:$ch Infants:$inf) [$wastage]\n"; } print "\n"; } print "---\n"; } __END__ Finding best fit for Adults => 4, Children => 1, Infants => 0 in rooms Quad => 0, Triple => 2, Double => 2 Rooms:2 Wastage:0 Double Occupants:2 (Adults:2 Children:0 Infants:0) [0] Triple Occupants:3 (Adults:2 Children:1 Infants:0) [0] Rooms:2 Wastage:1 Triple Occupants:3 (Adults:2 Children:1 Infants:0) [0] Triple Occupants:2 (Adults:2 Children:0 Infants:0) [1] --- Finding best fit for Adults => 6, Children => 0, Infants => 0 in rooms Quad => 1, Triple => 1, Double => 4 Rooms:2 Wastage:0 Double Occupants:2 (Adults:2 Children:0 Infants:0) [0] Quad Occupants:4 (Adults:4 Children:0 Infants:0) [0] Rooms:3 Wastage:0 Double Occupants:2 (Adults:2 Children:0 Infants:0) [0] Double Occupants:2 (Adults:2 Children:0 Infants:0) [0] Double Occupants:2 (Adults:2 Children:0 Infants:0) [0] Rooms:2 Wastage:1 Quad Occupants:4 (Adults:4 Children:0 Infants:0) [0] Triple Occupants:2 (Adults:2 Children:0 Infants:0) [1] Rooms:3 Wastage:1 Double Occupants:2 (Adults:2 Children:0 Infants:0) [0] Double Occupants:1 (Adults:1 Children:0 Infants:0) [1] Triple Occupants:3 (Adults:3 Children:0 Infants:0) [0] Rooms:3 Wastage:2 Double Occupants:2 (Adults:2 Children:0 Infants:0) [0] Double Occupants:2 (Adults:2 Children:0 Infants:0) [0] Quad Occupants:2 (Adults:2 Children:0 Infants:0) [2] Rooms:3 Wastage:3 Double Occupants:2 (Adults:2 Children:0 Infants:0) [0] Quad Occupants:1 (Adults:1 Children:0 Infants:0) [3] Triple Occupants:3 (Adults:3 Children:0 Infants:0) [0] ---
---
$world=~s/war/peace/g


In reply to Re: Assign guests to hotel rooms by demerphq
in thread Assign guests to hotel rooms by richard5mith

Title:
Use:  <p> text here (a paragraph) </p>
and:  <code> code here </code>
to format your post; it's "PerlMonks-approved HTML":



  • Are you posting in the right place? Check out Where do I post X? to know for sure.
  • Posts may use any of the Perl Monks Approved HTML tags. Currently these include the following:
    <code> <a> <b> <big> <blockquote> <br /> <dd> <dl> <dt> <em> <font> <h1> <h2> <h3> <h4> <h5> <h6> <hr /> <i> <li> <nbsp> <ol> <p> <small> <strike> <strong> <sub> <sup> <table> <td> <th> <tr> <tt> <u> <ul>
  • Snippets of code should be wrapped in <code> tags not <pre> tags. In fact, <pre> tags should generally be avoided. If they must be used, extreme care should be taken to ensure that their contents do not have long lines (<70 chars), in order to prevent horizontal scrolling (and possible janitor intervention).
  • Want more info? How to link or How to display code and escape characters are good places to start.
Log In?
Username:
Password:

What's my password?
Create A New User
Domain Nodelet?
Chatterbox?
and the web crawler heard nothing...

How do I use this?Last hourOther CB clients
Other Users?
Others meditating upon the Monastery: (6)
As of 2024-03-28 20:02 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    No recent polls found