AdSense

Sunday, March 15, 2015

Ice cream order



Write algorithm to determine the total time to make ice cream and when it leaves the store.
Consist of an order time, order number, and ice cream type.
“ice cream Type” is an integer: 0 for combo, 1 for vanilla. Order numbers are increasing.
We have three machines for making ice creams.
It takes 45 seconds to make a combo ice cream and 15 for vanilla. Can only make one ice cream at a time.
Need to determine total time to make ice cream and time the ice cream leaves the store (delivered).
In: order_time,order_num,ice_cream_type
Out: order_num,depart_time,total_time
This is a very interesting problem, I don't think I am at a very good approach, but it sort of works. Assuming we should process the problem in this way, each order comes continuously, so every time there is an available machine, we should use it for the new order.

Two thoughts:

First, use threads. Use takeOrder and finishOrder methods. Use a boolean variable available and ask the thread to wait before taking the order if the machine is working and wait before working if the machine hasn't taken any order. I can write a code if there is only one machine. However, the problem states that there are three machines, I stuck in how to create three threads and share the variable of number of ice cream in each order.

Second, write a machine class and create three objects. This approach is based on the assumption that, first, the start time of the next order is the later between the order time and the end time of the previous order, and second, the total time of finishing an order only depends on the number of orders, or the longest worked time among all three machines, and depart time is start time plus total time.

I think I missed something. But I don't know what. Moreover, I cannot generalize this approach, i.e., what if there are N machines?


import java.io.BufferedReader;
import java.io.FileReader;
import java.io.IOException;

public class RunMachine {

 public static void main(String[] args) {
  BufferedReader br = null;
  String currLine;
  Machine machine1 = new Machine();
  Machine machine2 = new Machine();
  Machine machine3 = new Machine();
  int iceCreamType;
  int orderNumber;
  int startTime;
  int totalTime;
  int nextStartTime = 0;
  try{
   br = new BufferedReader(new FileReader("iceCreamOrder.txt"));
   while((currLine = br.readLine()) != null){
    String[] order = currLine.split(" ");
    //start time is the later between the order time and the time when last order is finished
    startTime = (Integer.parseInt(order[0]) > nextStartTime) ? Integer.parseInt(order[0]) : nextStartTime;
    orderNumber = Integer.parseInt(order[1]);
    iceCreamType = Integer.parseInt(order[2]);
    int totalNumber = orderNumber;
    while(orderNumber > 0){
     machine1.getOrder(orderNumber--, iceCreamType);
     machine2.getOrder(orderNumber--, iceCreamType);
     machine3.getOrder(orderNumber--, iceCreamType);
     if(machine1.isFinished() || machine2.isFinished() || machine3.isFinished())
      break;
    } 
    totalTime = Math.max(machine1.getTime(), Math.max(machine2.getTime(), machine3.getTime()));
    int departTime = startTime + totalTime;
    System.out.format("%d, %d, %d\n", totalNumber, departTime, totalTime);
    machine1.set();
    machine2.set();
    machine3.set();
    nextStartTime = departTime;
    
   }
  } catch (Exception e){
   System.out.println(e);
  }
  finally {
   if(br != null){
    try{
     br.close();
    } catch (IOException er){
     er.printStackTrace();
    }
   } 
  }

 }

}
public class Machine {
 private boolean finished = false;
 private int timeWorked = 0;
 
 public void getOrder(int orderNumber, int orderType){
  if(orderNumber == 0){
   finished = true;
   return;
  }
  timeWorked += orderType == 0 ? 45 : 15;
 }
 public int getTime(){
  return timeWorked;
 }
 public void set(){
  timeWorked = 0;
  finished = false;
 }

 public boolean isFinished(){ 
  return finished;
 }
}

No comments:

Post a Comment