Grab&Go supermarket currently has n traditional checkout lanes open. A customer
ID: 3543198 • Letter: G
Question
Grab&Go supermarket currently has n traditional checkout lanes open. A customer arrives to checkout approximately every m minutes, and it takes x minutes to finish the checkout process for one customer, x is a random number draw from the range of [a,b]. Assume each customer always enters the shortest checkout line upon arrival. In case there are multiple shortest lines, the customer chooses one randomly. The manager of the supermarket Tom is considering adding k self-checkout lanes to reduce the average wait time. The assumption is that customers will use self-checkout lanes only when all of the following conditions are satisfied:
Assume that it takes 1.5x minutes for a customer to use self-checkout lane if it takes x minutes with traditional checkout. Also assume that a customer does not change lane after entering into one lane.
Construct a simulation of the Grab&Go supermarket to help Tom make the decision. A typical day is [9am-9pm] and the length of the simulation is 720 minutes.
(1) Implement a generic class MyQueue<E> using array, linked list, or ADT list. The interface or MyQueue<E> class must contain the following operations: boolean isEmpty(),int size(), void enqueue, dequeue(), and void clear().
(2) Write a program to simulate the supermarket checkout scenario, and report the average waiting time for the following test cases, with k self checkout lanes (k=0,1,2):
a) n=5, m=3, a=5, b=12 }
b) n=3, m=0.5, a=2, b=10 } it would be ideal to enter these at the start of the program
c) n=6, m=1, a=2, b=15 }
based on the results, make a recommendation for each case, should self-checkout lanes be added, if so, how many? (k=0, 1, or 2)
(3) Analyze the running time of your program
Please use C++
Comment as much as possible so I can follow what you are doing
Here is some psuedo code to help you get started:
for (t=0, t<=720, t++)
{
t % m == 0; //check if there is a new customer arriving
//add customer to shortest line
c.arriveTime = t, c.x = random[a,b]
//For each checkout line:
if ( t - c.startCheckout) >= c.checkoutProcesstime
//move next customer to start checkout c'
c'.startCheckouttime = t
c'.waitingtime = c'.startcheckouttime - c'.arrivetime
//make a class for customer
output:
averagewaitingtime = totalwaitingtime / numberofcustomers
THANK YOU SO MUCH FOR YOUR HELP!!!
Explanation / Answer
This took more than the expected time. I hope it helps you!
(It is a highly efficient implementation using heaps, way fast than normal ones)
/*
shoppers is an array of ints on the heap; time,items per shopper
size is the number of ints in the array
numberShoppers is the number of shoppers go figure:)
Index is an array of pointers on the heap, each pointer is pointing to the closest shopper to arrive at time; time is incremted by 600 seconds
IndexSize is the number of ints in Index
*/
typedef struct shoppers_s
{
void *shoppers;
int size;
int numberShoppers;
void *Index;
int IndexSize;
}shoppers_t;
typedef struct checkoutQuery_s
{
int checkouts[TIMESLOTS];
int losses[TIMESLOTS];
int lastCheckoutTime[TIMESLOTS][MAXNUMCHECKOUTS];
int q[TIMESLOTS][MAXNUMCHECKOUTS];
}checkoutQuery_t;
void printcheckouts(checkoutQuery_t *cq);//prototype
void printQuery(checkoutQuery_t *cq);
//free shoppers data struct
void freeshoppers(shoppers_t *sh)
{
free(sh->shoppers);
free(sh->Index);
}
//load shoppers
void loadshoppers(const char *filename, shoppers_t *sh)
{
FILE *mf;
int count = 0;
int time;
int item;
int currentShopper;
int IndexOffset;
int currentIndex;
mf = fopen(filename,"r");
while (!feof(mf)){
fscanf(mf,"%d,%d ",&time,&item);
if (time < 0)
{
printf("error negitive time at %d ",count);
return;
}
if (item < 0)
{
printf("error negitive item's at %d ",count);
return;
}
count++;
}
sh->numberShoppers = count;
sh->size = count*2;
sh->shoppers = malloc(sh->size*sizeof(int));
sh->IndexSize = time/600;
if ((time%600) != 0)//round up always
{
sh->IndexSize += 1;
}
sh->Index = malloc(sh->IndexSize*sizeof(int));
count = 0;
currentShopper = 0;
currentIndex = 0;
IndexOffset = 0;
rewind(mf);
while (!feof(mf))
{
fscanf(mf,"%d,%d ",&time,&item);
*((int *)sh->shoppers+count) = time;
*((int *)sh->shoppers+count+1) = item;
if (time >= currentIndex)
{
*((int *)sh->Index+IndexOffset) = currentShopper;
currentIndex += 600;
IndexOffset += 1;
}
count +=2;
currentShopper +=1;
}
fclose(mf);
}
void getshopper(const shoppers_t *sh,int shopperNumber,int *time, int *items)
{
if ( (shopperNumber>=0) && ( shopperNumber < sh->numberShoppers) )
{
shopperNumber *= 2;
*time = *((int *)sh->shoppers+shopperNumber);
*items = *((int *)sh->shoppers+shopperNumber+1);
}
else
{
printf("error shopper number %d out of range ",shopperNumber);
}
}
void getIndex(const shoppers_t *sh, int n, int *time, int *item)
{
int a;
if ( (n>=0) && ( n < sh->IndexSize) )
{
a = *((int *)sh->Index+n);
getshopper(sh,a,time,item);
}
else
{
printf("error index %d out of range",n);
}
}
void printShoppers(const shoppers_t *sh)
{
int i,time,item;
for (i=0;i<sh->numberShoppers;i++)
{
getshopper(sh,i,&time, &item);
printf("%d, %d ",time,item);
}
}
void printShopperIndex(const shoppers_t *sh)
{
int i,n,time,item;
for (i=0;i<sh->IndexSize;i++)
{
getIndex(sh, i, &time, &item);
printf("%d, %d ",time,item);
}
printf("sh indexsize %d ",sh->IndexSize);
}
void processQuery(checkoutQuery_t *cq,int time,int slot)
{
int i;
for (i=0;i<MAXNUMCHECKOUTS;i++)
{
if ( (cq->lastCheckoutTime[slot][i])+CHECKOUTRATE == time)
{
//printf("query exit n %i t %i ",i,time);
if (cq->q[slot][i]!=0)
{
cq->q[slot][i] -= 1;
}
cq->lastCheckoutTime[slot][i] = time;
}
else if (cq->q[slot][i] == 0)
{
cq->lastCheckoutTime[slot][i] = time;
}
}
/*printf("time: %i, slot %i ",time,slot);
printf("query: ");
for (i=0;i<cq->checkouts[slot];i++)
{
printf("%i ",cq->q[slot][i]);
}
printf(" ");
printf("time: ");
for (i=0;i<cq->checkouts[slot];i++)
{
printf("%i ",cq->lastCheckoutTime[slot][i]);
}
printf(" ");*/
}
void AddToQuery(const shoppers_t *sh,checkoutQuery_t *cq,int time, int slot,int shopperNumber,int *incShopperNum, int *overflow, int *added)
{
int i;
int best;
int stime,sitem;
*overflow = 0;
*incShopperNum = 0;
*added = 0;
getshopper(sh,shopperNumber,&stime,&sitem);
if (stime==time)
{
*incShopperNum = 1;
best = -1;
for (i=0;i<cq->checkouts[slot];i++)
{
if (cq->q[slot][i]+sitem <=MAXITEMS-1)//make maxitems-1 for safty
{
if (best == -1)
{
best = i;
}
else if (cq->q[slot][i] < cq->q[slot][best])
{
best = i;
}
}
}
if (best!=-1)
{
//printf("added 2 q : %i ",sitem);
cq->q[slot][best] +=sitem;
return;
}
if (cq->checkouts[slot]<MAXNUMCHECKOUTS)
{
*added = 1;
cq->checkouts[slot] ++;
cq->lastCheckoutTime[slot][cq->checkouts[slot]] = time;
cq->q[slot][cq->checkouts[slot]] = sitem;
//printf("checkout added c %i, t %i, i %i ",cq->checkouts[slot], time,sitem);
}
else
{
//printf("loss at t:%d, s:%d ",time,slot);
cq->losses[slot] ++;
*overflow = 1;
}
}
}
void EvaluateTimeSlot(const shoppers_t *sh,checkoutQuery_t *cq,int slot,int forceIT)
{
int i;
int shNum;
int inc;
int of;
int added;
if ( (slot>=0) && ( slot <= sh->IndexSize) )
shNum = *((int *)sh->Index+slot);
else
printf("shNum oversized for slot %d ",slot);
//printf("slot %d shNum %d ",slot,shNum);
//copy the previews lastCheckoutTime and q
if (slot != 0)
{
for (i=0;i<MAXNUMCHECKOUTS;i++)
{
cq->lastCheckoutTime[slot][i] = cq->lastCheckoutTime[slot-1][i];
cq->q[slot][i] = cq->q[slot-1][i];
}
}
//reset losses
cq->losses[slot] = 0;
if (forceIT)
{
if (cq->checkouts[slot]<MAXNUMCHECKOUTS)
{
cq->checkouts[slot] ++;
cq->lastCheckoutTime[slot][cq->checkouts[slot]] = slot*TIMESLOTLENGTH*60;
cq->q[slot][cq->checkouts[slot]] = 0;
}
}
/*printf("query: ");
for (i=0;i<cq->checkouts[slot];i++)
{
printf("%i ",cq->q[slot][i]);
}
printf(" ");
printf("time: ");
for (i=0;i<cq->checkouts[slot];i++)
{
printf("%i ",cq->lastCheckoutTime[slot][i]);
}
printf(" -------------------- ");*/
for (i=slot*TIMESLOTLENGTH*60;i<(slot+1)*TIMESLOTLENGTH*60;i++)
{
processQuery(cq,i,slot);
AddToQuery(sh,cq,i,slot,shNum,&inc,&of,&added);
if (inc == 1)
{
if (shNum+1 < sh->numberShoppers)
shNum++;
}
if (added==1)
{
/*if (forceIT)
{
if (cq->checkouts[slot]<MAXNUMCHECKOUTS)
{
cq->checkouts[slot] ++;
cq->lastCheckoutTime[slot][cq->checkouts[slot]] = time;
cq->q[slot][cq->checkouts[slot]] = 0;
}
}*/
}
if (of==1)//overflow in the last AddtoQuery
{
if (cq->checkouts[slot-1] < MAXNUMCHECKOUTS)
{
if (!forceIT)
{
//printf("backtracking for slot %d ",slot);
EvaluateTimeSlot(sh,cq,slot-1,1);
return;
}
}
}
}
/*printf("query: ");
for (i=0;i<cq->checkouts[slot];i++)
{
printf("%i ",cq->q[slot][i]);
}
printf(" ");
printf("time: ");
for (i=0;i<cq->checkouts[slot];i++)
{
printf("%i ",cq->lastCheckoutTime[slot][i]);
}
printf(" -------------------- ");*/
if (slot < ((NUMBERSTOREHOURS*60 / TIMESLOTLENGTH)-1) )
EvaluateTimeSlot(sh,cq,slot+1,0);
}
void clearcheckouts(checkoutQuery_t *cq)
{
int i;
int j;
for (i=0;i<TIMESLOTS;i++)
{
cq->checkouts[i]=1;
cq->losses[i] = 0;
for (j=0;j<MAXNUMCHECKOUTS;j++)
{
cq->lastCheckoutTime[i][j] = 0;
cq->q[i][j] = 0;
}
}
}
void printcheckouts(checkoutQuery_t *cq)
{
int i,j;
int c;
printf("checkouts ");
//1|2|3|4|5|6
//
for (i=0;i<TIMESLOTS;i+=10)
{
for (j=i,c=0;c<10;j++,c++)
{
if (j<TIMESLOTS)
printf("%2d |",j);
}
printf(" ");
for (j=i,c=0;c<10;j++,c++)
{
if (j<TIMESLOTS)
printf("%2d |",cq->checkouts[j]);
}
printf(" ");
for (j=i,c=0;c<10;j++,c++)
{
if (j<TIMESLOTS)
printf("%2d |",cq->losses[j]);
}
printf(" ---------------------------------------- ");
}
printf(" ");
int total=0;
for (i=0;i<TIMESLOTS;i++)
{
total += cq->losses[i];
total += cq->checkouts[i];
}
printf("total: %d ",total);
}
void printQuery(checkoutQuery_t *cq)
{
int i,j;
for (i=0;i<TIMESLOTS;i++)
{
for (j=0;j<MAXNUMCHECKOUTS;j++)
{
printf("%i ",cq->q[i][j]);
}
printf(" ");
}
}
int main()
{
shoppers_t shoppers;
checkoutQuery_t cq;
FILE *output;
int i;
loadshoppers("shoppers.txt", &shoppers);
//printShoppers(&shoppers);
//printShopperIndex(&shoppers);
clearcheckouts(&cq);
EvaluateTimeSlot(&shoppers,&cq,0,0);
//printcheckouts(&cq);
output=fopen("tills.txt","w");
for (i=0;i<TIMESLOTS;i++)
{
fprintf(output,"%d ",cq.checkouts[i]);
}
fclose(output);
freeshoppers(&shoppers);
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.