Complex problem I need to solve with perl

[jimnl69]

I have a problem that to me seems complex. I put it here in the perl
forum because this is how I need to solve it. I've translated the
scenario into a psuedo scenario below but the concept is identical.
Here goes:

I have 10 people: p1..p10
I have 2 products: milk and cookies

I have a list of all 10 people:
p1 gets cookies
p2 gets milk
p3 gets either
p4 gets either
p5 gets milk
p6 gets cookies
p7 gets either
p8 gets cookies
p9 gets milk
p10 gets cookies

I turn the assembly belt on and out comes cookies and milk, random
order. I need to distribute, one at a time, to the 10 people in a way
that somebody doesn't get seconds, before everybody else capable of
getting that item gets firsts. I've been trying to figure out how to
keep indexes of where each item type was but the problem is the people
that get both. How do I store who got what? Now, here's the kicker.
I need to store this in-between program runs. If it runs every 5
minutes, one time I may get 20 items and one time I may get 2.
Whatever the case may be, it's a continuous loop that needs to start
where it left off.

 

[xhoster]

I have a problem that to me seems complex. I put it here in the perl
forum because this is how I need to solve it. I've translated the
scenario into a psuedo scenario below but the concept is identical.
Here goes:

I have 10 people: p1..p10
I have 2 products: milk and cookies

I have a list of all 10 people:
p1 gets cookies
p2 gets milk
p3 gets either
p4 gets either
p5 gets milk
p6 gets cookies
p7 gets either
p8 gets cookies
p9 gets milk
p10 gets cookies

I turn the assembly belt on and out comes cookies and milk, random
order. I need to distribute, one at a time, to the 10 people in a way
that somebody doesn't get seconds, before everybody else capable of
getting that item gets firsts.

Are firsts/seconds on a per person*item basis or a per person basis? For
example, if p3 gets a milk, would giving p3 a cookie by considered firsts,
or seconds, because it would be his first cookie, but second item?

What kind of efficiency do you need?

I've been trying to figure out how to
keep indexes of where each item type was but the problem is the people
that get both. How do I store who got what?

Depending on your answer above, two circular lists might be a good way.
When a cookie comes off the line, you shift the first person off
@can_get_cookie, give them a cookie, then push them back onto the end
of @can_get_cookie.

Same thing with @can_get_milk.

Or @{$canget{$item}} where $item is 'cookie' or 'milk', to be general about
it.

Now, here's the kicker.
I need to store this in-between program runs. If it runs every 5
minutes, one time I may get 20 items and one time I may get 2.
Whatever the case may be, it's a continuous loop that needs to start
where it left off.

If efficiency isn't a problem and you have file locks, then this is simple.
You open "+<" and lock a file, read state from it, do your thing, truncate
the file, write the new state to it, close the file. Storable,
Data:umper; DBM:eep, etc.

If efficiency is a problem, then you need to disclose more information
about the problem.

Xho

 

[bugbear]

Now, here's the kicker.
I need to store this in-between program runs. If it runs every 5
minutes, one time I may get 20 items and one time I may get 2.
Whatever the case may be, it's a continuous loop that needs to start
where it left off.

Heh. Dirty ol' Data:umper
will dump out most perl data structures
in valid perl syntax.

This means you could simply "print" them
to a file, and get them back by reading
back in and hitting eval() !

BugBear

 

[jimnl69]

It would be on a per person basis. Lets take this example:

p1 gets cookies
p2 gets milk
p3 gets either
p4 gets either
p5 gets milk
p6 gets cookies
p7 gets either
p8 gets cookies
p9 gets milk
p10 gets cookies

The data below is a random list of items coming out and their
respective assignments of where they need to go:

milk p2
milk p3
cookies p1
cookies p4
milk p5
milk p7
cookies p6
milk p9
milk p2
milk p3
cookies p10
cookies p1

etc... Also, keep in mind that I need to remember where I was when
finished so that next time I run I know where to start in the list(s).
I do this today with "index" values that I store in a database. The
difference between today and this problem is that today they can take
one or the other, not both. Now I have these people that can take BOTH
items and I just can't figure out how to do it.

Your @can_get_cookie and @can_get_milk suggestion is basically what I'm
doing with my indexes. However, people that can get both would be in
both lists. If I pop someone off the milk list and he's 3 people down
on the cookie list, he'll get a cookie before someone else when he's
already received milk.

 

[jimnl69]

It would be on a per person basis. Lets take this example:

p1 gets cookies
p2 gets milk
p3 gets either
p4 gets either
p5 gets milk
p6 gets cookies
p7 gets either
p8 gets cookies
p9 gets milk
p10 gets cookies

The data below is a random list of items coming out and their
respective assignments of where they need to go:

milk p2
milk p3
cookies p1
cookies p4
milk p5
milk p7
cookies p6
milk p9
milk p2
milk p3
cookies p10
cookies p1

etc... Also, keep in mind that I need to remember where I was when
finished so that next time I run I know where to start in the list(s).
I do this today with "index" values that I store in a database. The
difference between today and this problem is that today they can take
one or the other, not both. Now I have these people that can take BOTH
items and I just can't figure out how to do it.

Your @can_get_cookie and @can_get_milk suggestion is basically what I'm
doing with my indexes. However, people that can get both would be in
both lists. If I pop someone off the milk list and he's 3 people down
on the cookie list, he'll get a cookie before someone else when he's
already received milk.

 

[xhoster]

It would be on a per person basis. Lets take this example:

p1 gets cookies
p2 gets milk
p3 gets either
p4 gets either
p5 gets milk
p6 gets cookies
p7 gets either
p8 gets cookies
p9 gets milk
p10 gets cookies

The data below is a random list of items coming out and their
respective assignments of where they need to go:

milk p2
milk p3
cookies p1
cookies p4
milk p5
milk p7
cookies p6
milk p9
milk p2
milk p3
cookies p10
cookies p1

So is it based on least recently served, or least often served?

I.e.

p1 gets cookies
p2 gets either

milk p2
milk p2
milk p2
milk p2
cookies p1
cookies ??

Here p2 was least recently served, but p1 was least often served. Who
gets it?

etc... Also, keep in mind that I need to remember where I was when
finished so that next time I run I know where to start in the list(s).

The best way to do this depends on how big the real lists are, etc.
Is it a problem to read in a write out all the data each time the program
starts, or does it need to be more efficient than that.

I do this today with "index" values that I store in a database. The
difference between today and this problem is that today they can take
one or the other, not both. Now I have these people that can take BOTH
items and I just can't figure out how to do it.

Your @can_get_cookie and @can_get_milk suggestion is basically what I'm
doing with my indexes. However, people that can get both would be in
both lists. If I pop someone off the milk list and he's 3 people down
on the cookie list, he'll get a cookie before someone else when he's
already received milk.

So once he's popped off the one list, you have to hunt him down and splice
him out of the other list as well (assuming the "least recently served"
approach, and then push onto the end of both lists. The best way to do
that depends on how big the lists are.

Or you could just keep one list:

sub allocate_food {
my ($lrs, $item)=@_; # least recently served list, item
foreach my $i (0..$#lrs) {
if ($lrs[$i]->offer($item)) {
push @$lrs, splice @$lrs, $i, 1;
return;
};
die "No one can take $item"
};
};

It has a bad worst-case performance, but it is probably rare to encounter
it.

Xho