Re: Algorithm Help

On Oct 2, 2013, at 9:51 AM, Tamara Temple <tamouse.lists@gmail.com> wrote: > > On Oct 1, 2013, at 1:51 PM, Floyd Resler <fresler@adex-intl.com> wrote: > >> Here's my task: A group of kids is going to be staying with different host families >> throughout the next 8 months. The number of kids staying with a host family can range from 2 to 10. >> When deciding which kids should stay together at a host family, the idea is for the system to put >> together kids who have stayed with each other the least on past weekends. So, if a host family can >> keep 5 kids, then the group of 5 kids who have stayed together the least will be chosen. >> >> I can't think of an easy, quick way to accomplish this. I've tried various >> approaches that have resulted in a lot of coding and being very slow. My idea was to give each >> group of kids a score and the lowest score is the group that is selected. However, this approach >> wound of iterating through several arrays several times which was really slow. Does anyone have any >> ideas on this puzzle? >> >> Thanks! >> Floyd >> >> >> -- >> PHP General Mailing List (http://www.php.net/) >> To unsubscribe, visit: http://www.php.net/unsub.php >> > > While definitely a tempting coding exercise, I just want to say that if this is urgent in any > way, shuffling cards with the kids' names on them by hand might just be faster and less > frustrating :) > > OTOH, if this is something you're going to have to figure out week after week, then a > software solution might be handy. > > This is also not an *easy* problem to solve; there isn't a simple approach to optimizing > this sort of thing because you're building a net between all the various kids based on past > stays, in addition to the constraints of host family capacity. Thus your previous code attempts > might in fact be the end result. > > Obviously, structuring the data is the key here. > > I'm thinking of 3 primary models: Kids, Hosts, and Stays. > > Kids and Hosts seem pretty obvious. Stays is the interesing model, and needs to have joining > tables with Kids and Hosts. > > A Stay will have one Host, and have many Kids and a date. > > The algorithm then needs to make the graph where it can pull out the number of times any > particular kid has stayed with another, looking something like this: > > Amy: > Ben: 10 > Jill: 3 > Carlos: 7 > Chen: 2 > Ben: > Amy: 10 > Jill: 5 > Carlos: 8 > Chen: 3 > Jill: > … and so on > > Then you be able to pull through that graph and find the smallest number of stays for each kid. > > Not simple, but I hope this helps. > > That's the only approach I could think of. I may have to tell the director it may be a bit slow but at least she won't have to do it by hand! Thanks! Floyd