Programming Geek
Rated 4.7/5 based on 1446 reviews

MUPHORIA organized by MU Sigma


MUPHORIA
Do you enjoy solving problems?
Do you like flaunting your programming skills?
Wanna do this by being part of a category defining company

Participate in MuPhoriaTM. Win upto Rs.6 Lakhs* and a chance to work with Mu Sigma!


Although the contest is now over, I want to give a brief introduction of this contest along with my submission:

PURPOSE

MuPhoria (the “Contest”) was designed to:
1.Create awareness about the Decision Sciences industry.
2.Encourage and inspire students to gain exposure to real world business problems.
3.Provide students an opportunity to innovate by integrating Math, Business and Technology.

I too partcipated in MUPHORIA and got selected in top five thrice thereby secured an interview with MU Sigma.
To see the sample problem : please visit http://www.mu-sigma.com/muphoria .
Download the datasets, visit http://www.mu-sigma.com/muphoria .
The problem was to find the shortest routes for a set of vehicles so as to minimize the total cost for three years.
Although I tried best but my solution was not so great. Here goes my solution for the concerned problem:

Business logic class: Muphoria

//Muphoria.java

import java.io.FileReader;
import java.io.FileWriter;
import java.io.LineNumberReader;
import java.util.ArrayList;
import javax.swing.JOptionPane;

/**
 *
 * @author VIKASH MAYANK
 */
public final class Muphoria {

    /**
     * instance variables
     * 
     */
    private long total = 0;//stores total distance travelled
    private String storeDcMatrix[][] = new String[602][602];//2D array to store the distance among stores and distribution centre containing first row of stores name also
    private int distanceSheetMatrix[][] = new int[601][601];//2D array to store distance among store and distribution centre i.e an array containg 601 rows and 601 columns
    private String storeWeightMatrix[][] = new String[600][2];//stores store name and their respective demand
    private int weightSheetMatrix[] = new int[600];//this array contains only demands of all the 600 stores
    private Store[] stores = new Store[600];//this array contains store information
    private ArrayList<Truck> truckList = new ArrayList<Truck>();//an arraylist containing list of trucks
    private ArrayList<Integer> deliveredStoreindexList = new ArrayList<Integer>();//this arraylist stores index  of store where goods have been delivered
    private boolean flag = true;//this becomes false as soon a store is served
    private FileWriter fileWriter;//writes csv(comma separated values) file
    private int adjustmentFactor = 1000;//determine the maximum goods delivered by a truck so that adjustStore(-,-,-) method can be called...
    private String sheet1 = "";//get sheet1.csv
    private String sheet2 = "";//get sheet2.csv
    /**
     * constructor
     */

    public Muphoria(String sheet1, String sheet2) {
        this.sheet1 = sheet1;
        this.sheet2 = sheet2;
        readData();
    }//constructor-----end-----

    /**reads data from comma delimited csv  file
     * 
     */
    private void readData() {
        try {
            FileReader file = new FileReader(sheet1);//gets file
            LineNumberReader lnr = new LineNumberReader(file);//reads one line at a time

            //skip four lines of csv file to start reading data
            lnr.readLine();
            lnr.readLine();
            lnr.readLine();
            lnr.readLine();

            //read csv file line by line and store data in storeDcMatrix
            for (int i = 0; i < 602; i++) {
                //read one line
                String string = lnr.readLine();
                //split the string on the basis of comma(,) as a regular expression
                storeDcMatrix[i] = string.split("[,]");
            }

            file = new FileReader(sheet2);//get dataSheet2
            lnr = new LineNumberReader(file);
            //skip two lines
            lnr.readLine();
            lnr.readLine();

            //stores store and their respective demand in storeWeightMatrix
            for (int i = 0; i < storeWeightMatrix.length; i++) {
                //read a line
                String string = lnr.readLine();
                for (int j = 0; j < storeWeightMatrix[i].length; j++) {
                    storeWeightMatrix[i] = string.split("[,]");//split the string and return values...
                }
            }
        } catch (Exception e) {
            System.err.println("System can not find the file specified...\nMake sure...\na)sheet1.csv and sheet2.csv are in the current directory...\nb)Please take a look at readme.pdf document for setup instructions...");
            javax.swing.JOptionPane.showMessageDialog(null, "System can not find the file specified...\nMake sure...\na)sheet1.csv and sheet2.csv are in the current directory...\nb)Please take a look at readme.pdf document for setup instructions...", "Error Occured!", JOptionPane.ERROR_MESSAGE);
            System.exit(0);
        }

        //transferring string array(storeDcMatrix) values into int array(distanceSheetMatrix)
        for (int i = 0; i < distanceSheetMatrix.length; i++) {
            for (int j = 0; j < distanceSheetMatrix[i].length; j++) {
                if (i + 1 == j + 1) {
                    distanceSheetMatrix[i][j] = 0;//put zero as distance of a store from itself is zero
                } else {
                    /**To avoid weird behaviour of floating arithmetic...
                     * We have multiplied distance by 100 here and casted the data into int type so as to ease calculation part ...
                     * This does not affect the calculation and actual output because the 65 km distance limit has been checked properly ...
                     */
                    distanceSheetMatrix[i][j] = (int) (Float.parseFloat(storeDcMatrix[i + 1][j + 1]) * 100);//distanceSheetMatrix contains distance only, storeDcMatrix contains name of the store as well 
                }
            }
        }

        //get demand of 600 stores in stores array as well as in weightSheetMatrix
        for (int i = 0; i < 600; i++) {
            weightSheetMatrix[i] = Integer.parseInt(storeWeightMatrix[i][1].trim());
            stores[i] = new Store();
            stores[i].setDemand(Integer.parseInt(storeWeightMatrix[i][1].trim()));
        }

    }//readData()--------------end-------------------

    /**
     * getResult() method changes the value of adjustmentFactor which determines the minimum amount of goods so that
     * a truck can adjust its store by making a calll to adjustStore(-,-,-) method.
     * 
     * This determines the best value of adjustmentFactor so that total cost over three year is minimum...
     */
    public void getResult() {
        //make a new Muphoria class object(adjustmentFactor is by default 1000)
        Muphoria muphoria = new Muphoria(sheet1, sheet2);
        muphoria.readData();//read data from csv files...
        muphoria.process();//process the result...
        muphoria.calculateTotalCost();//calculate total cost

        //loop again and again determine the best adjustmentfactor for ehich total cost over three year is minimum...
        for (int i = 1000; i > 900; i--) {
            truckList.clear();//clear the current truckList...
            deliveredStoreindexList.clear();//clear the deliveredStoreIndexlist..
            for (int j = 0; j < stores.length; j++) {//set status of every store to true...
                stores[j].setStatus(true);
            }
            adjustmentFactor = i;//set the new adjustmentFactor
            flag = true;//set flag true...
            this.process();//process result...
            this.calculateTotalCost();//calculate total cost considering new adjustment factor...
            if (total < muphoria.total) {//if total cost for this adjustment factor is minimum then store the truckList and total cost in muphoria(object of Muphoria class)...
                muphoria.total = total;//set new total cost
                muphoria.truckList.clear();//clear muphoria object truckList
                for (Truck t : truckList) {
                    muphoria.truckList.add(t);
                }
            }
        }
        muphoria.generateOutput();//generate the best output... 
        System.out.println("output.csv file is generated in the current directory!");
        javax.swing.JOptionPane.showMessageDialog(null, "output.csv file is generated in the current directory!", "Output Generated", JOptionPane.INFORMATION_MESSAGE);
    }//getResult()--------------end----------

    //find the total number of truck needed...
    private void process() {
        int j = 1;
        while (deliveredStoreindexList.size() < 600) {
            Truck truck = new Truck(j);
            truckList.add(truck);
            flag = true;
            findRoutes(truckList.get(j - 1));
            // truckList.add(truck);
            j++;
        }
    }//process()--------------------end---------------

    //calculate total cost...
    private void calculateTotalCost() {
        total = 0;
        //calculate total distance travelled
        for (Truck truck : truckList) {
            total += truck.getDistance();
        }
        total = (total * 30 * 365 * 3) / 100;//cost of travel for three year...
        total += truckList.size() * 20000 * 12 * 3;//total cost over three year...
    }//calculateTotalCost()----------------end-------------

    //generate output.csv file...
    private void generateOutput() {
        int maximumSore = 0;
        total = 0;
        //find the maximum number of store delivered by a truck...
        for (Truck truck : truckList) {
            total += truck.getDistance();
            if (maximumSore < truck.getPath().size()) {
                maximumSore = truck.getPath().size();
            }
        }

        try {
            fileWriter = new FileWriter("output.csv", false);//create a output.csv file
            fileWriter.write("          Total  truck  needed : " + truckList.size() + "\n          Total distance  travelled each day(in km) : " + (float) total / 100.0f + "\n");
            calculateTotalCost();
            fileWriter.write("          Total cost over three years  :  " + total + "\n");
            fileWriter.write("\n          DC : Distribution Centre (DC is not a stop)\n");
            fileWriter.write("\n          Routing for each truck   \n\n");
            fileWriter.close();
            //this for loop write name of each truck in output.csv file...
            for (Truck truck : truckList) {
                fileWriter = new FileWriter("output.csv", true);
                fileWriter.write(truck.getName() + ",");
                fileWriter.close();
            }

            //write route of each truck...
            for (int i = 0; i < maximumSore; i++) {
                fileWriter = new FileWriter("output.csv", true);
                fileWriter.flush();
                fileWriter.write("\n");
                for (int j = 0; j < truckList.size(); j++) {
                    Truck truck = truckList.get(j);
                    if (truck.getPath().size() > i) {
                        fileWriter.write(truck.getPath().get(i) + ",");
                    } else {
                        fileWriter.write(",");
                    }
                }
                fileWriter.close();
            }
        } catch (Exception e) {
            System.err.println("can not generate output file...\nMake sure...\n1)The output.csv file is not being used by another process.\n2)Current directory has sufficient file write permission...");
            javax.swing.JOptionPane.showMessageDialog(null, "can not generate output file...\nMake sure...\n1)The output.csv file is not being used by another process.\n2)Current directory has sufficient file write permission...", "Error generating file!", JOptionPane.ERROR_MESSAGE);
            System.exit(0);
        }
    }//generateOutput()----------------------end---------

    //finds the route of trucks
    private void findRoutes(Truck truck) {
        Store store = new Store();
        int index = 0;
        int demand = 0;
        int distance = 0;
        // while(-) runs until all the stores are visited 
        while (flag) {
            if (deliveredStoreindexList.size() == 600) {
                flag = false;
                break;
            }

            if (truck.isStatus()) {
                if (truck.getIndex().size() == 0) {
                    //  get nearest store from distribution centre
                    store = getNextStore(distanceSheetMatrix[600]);
                    truck.addPath("DC");
                } else {
                    //get store nearest to previous store
                    store = getNextStore(distanceSheetMatrix[truck.getIndex().get(truck.getIndex().size() - 1)]);
                }

                //get details of nearest store
                index = store.getIndex();
                demand = store.getDemand();
                distance = store.getDistance();
                //update truck
                truck.addDistance(distance);
                truck.addIndex(index);
                truck.setDelivered(demand);
                truck.setTime();
                store.setStatus(false);
                /**if goods delivered exceeds 1000 kg or
                 * time spent exceeds 10800 seconds =3 hours or
                 * distance travelled + return distance exceeds 65km then remove the last updated record
                 * 
                 */
                if (truck.getDelivered() > 1000 || truck.getTime() > 10800 || (truck.getDistance() + distanceSheetMatrix[600][index]) / 100 > 65) {
                    store.setStatus(true);
                    truck.getIndex().remove(truck.getIndex().size() - 1);
                    distance = -distance;
                    truck.addDistance(distance);
                    demand = -demand;
                    truck.setDelivered(demand);
                    truck.setTime();


                    //adjust the last store with a new store where goods to be delivered is less than required to complete 1000 kg
                    if (truck.getDelivered() < adjustmentFactor) {
                        store = adjustStore(distanceSheetMatrix[truck.getIndex().get(truck.getIndex().size() - 1)], 1000 - truck.getDelivered());

                        //get details of nearest store
                        index = store.getIndex();
                        demand = store.getDemand();
                        distance = store.getDistance();
                        //update truck
                        truck.addDistance(distance);
                        truck.addIndex(index);
                        truck.setDelivered(demand);
                        truck.setTime();
                        store.setStatus(false);
                        deliveredStoreindexList.add(index);
                    }


                    //set truck status false
                    truck.setStatus(false);
                    //add return distance
                    truck.addDistance(distanceSheetMatrix[600][truck.getIndex().get(truck.getIndex().size() - 1)]);


                    //time exceeds 3 hours then remove the last updation
                    if (truck.getTime() > 10800) {
                        store.setStatus(true);
                        truck.getIndex().remove(truck.getIndex().size() - 1);
                        distance = -distance;
                        truck.addDistance(distance);
                        demand = -demand;
                        truck.setDelivered(demand);
                        truck.setTime();
                        deliveredStoreindexList.remove(deliveredStoreindexList.size() - 1);
                    }

                    // distance travelled exceeds 65 km then remove the last updation
                    if ((truck.getDistance() / 100) > 65) {//truck.getDistance() is  divided by 100 as we originally multiplied each distance by 100 in distanceSheetMatrix 
                        store.setStatus(true);
                        truck.getIndex().remove(truck.getIndex().size() - 1);
                        distance = -distance;
                        truck.addDistance(distance);
                        demand = -demand;
                        truck.setDelivered(demand);
                        truck.setTime();
                        deliveredStoreindexList.remove(deliveredStoreindexList.size() - 1);

                    }
                    flag = false;
                    truck.addPath("DC");


                } else {
                    //add visited store name in path
                    truck.addPath(storeDcMatrix[0][index + 1]);

                    //update deliveredStoreindexList
                    deliveredStoreindexList.add(index);

                }

                //add return distance of the truck if all the stores are visited
                if (deliveredStoreindexList.size() == 600 && truck.getIndex().size() < 35 && truck.getDelivered() <= 1000) {
                    truck.addDistance(distanceSheetMatrix[600][truck.getIndex().get(truck.getIndex().size() - 1)]);
                    flag = false;
                    truck.addPath("DC");
                }

                //set truck status false if 35 stores are served ...
                if (truck.getIndex().size() == 35) {
                    truck.setStatus(false);
                    truck.addDistance(distanceSheetMatrix[600][truck.getIndex().get(truck.getIndex().size() - 1)]);
                    flag = false;
                    truck.addPath("DC");
                }
            }
        }//while end ...
    }//findRoutes()------------end-----------

    //getNextStore(-,-,-) finds the nearest store from the previously visited store
    private Store getNextStore(int[] prevStore) {
        int index = 0;
        int distance = 0;

        //find store where goods have not been delivered...
        for (int i = 0; i < 600; i++) {
            if (prevStore[i] != 0 && stores[i].isStatus()) {
                index = i;
                distance = prevStore[i];
                stores[i].setIndex(index);
                stores[i].setDistance(distance);
                break;
            }
        }

        //find the nearest store where goods have not been delivered...
        for (int i = 0; i < 600; i++) {
            if (prevStore[i] != 0 && (prevStore[i]) <= distance && stores[i].isStatus()) {
                distance = prevStore[i];
                index = i;
                stores[i].setIndex(index);
                stores[i].setDistance(distance);
            }
        }

        //return the nearest store
        return stores[index];

    }//getNextStore(-)-------------end------------

    /**called when  the last nearest store has more demand of goods than goods that can be delivered by the truck keeping 1000 kg limit
     * this method takes input as previous store and required goods in the truck and returns the store having highest demand of goods(less than required goods)...
     */
    private Store adjustStore(int[] prevStore, int required) {
        int index = 0;
        int distance = 0;
        int weight = 0;
        //finds a store which is not visited...
        for (int i = 0; i < 600; i++) {
            if (prevStore[i] != 0 && stores[i].isStatus() && weightSheetMatrix[i] < required) {
                index = i;
                distance = prevStore[i];
                weight = weightSheetMatrix[i];
                stores[i].setIndex(index);
                stores[i].setDistance(distance);
                break;
            }
        }

        //finds the store having highest demand of goods(less than required)...  
        for (int i = 0; i < 600; i++) {
            if (prevStore[i] != 0 && (weightSheetMatrix[i]) >= weight && weightSheetMatrix[i] < required && stores[i].isStatus()) {
                distance = prevStore[i];
                weight = weightSheetMatrix[i];
                index = i;
                stores[i].setIndex(index);
                stores[i].setDistance(distance);
            }
        }

        return stores[index];
    }//adjustStore(-,-)----------------------end---------------
}//Muphoria-------------------business logic class--------------

//
class Store {

    private int distance;//distance of a store from previously visited store(dynamically changes as the previously visited store changes)...
    private int demand;//demand of goods...
    private int index;//index position in array...
    private boolean status;//becomes false as soon as goods have been delivered...

    public Store() {
        status = true;
    }

    public boolean isStatus() {
        return status;
    }

    public void setStatus(boolean status) {
        this.status = status;
    }

    public int getDemand() {
        return demand;
    }

    public void setDemand(int demand) {
        this.demand = demand;
    }

    public int getDistance() {
        return distance;
    }

    public void setDistance(int distance) {
        this.distance = distance;
    }

    public int getIndex() {
        return index;
    }

    public void setIndex(int index) {
        this.index = index;
    }
}//Store-------business logic class------------

// 
class Truck {

    private boolean status = true;//status becomes false as soon as any constraints like time limit  ,maximum goods that can be delivered or maximum distance that can be travelled tends to be invalid
    private int distance;//total distance travelled...
    private ArrayList<string> path = new ArrayList<string>();//keep track of stores where goods have been delivered...
    private ArrayList<Integer> index = new ArrayList<Integer>();//keep track of index of stores in array
    private int delivered;//total goods delivered...
    private int time;//time spent...
    private String name;//name of the truck...

    public Truck(int number) {
        setName("Truck#" + number);
    }

    public int getDelivered() {
        return delivered;
    }

    public void setDelivered(int delivered) {
        this.delivered += delivered;
    }

    public String getName() {
        return name;
    }

    private void setName(String name) {
        this.name = name;
    }

    public int getTime() {
        return time;
    }

    public void setTime() {
        //aeach truck can travel upto 3 hours to deliver goods i.e. 60*60*60=10800 seconds
        int seconds = 0;
        //add total time taken to travel the distance 
        seconds += getDistance() * 90 / 100;
        //add 5 minutes =5*60 = 300 seconds for each stop
        seconds += getIndex().size() * 300;
        this.time = seconds;

    }

    public int getDistance() {
        return distance;
    }

    public void setDistance(int distance) {

        this.distance += distance;
    }

    public void addDistance(int distance) {
        this.distance += distance;
    }

    public ArrayList<Integer> getIndex() {
        return index;
    }

    public void setIndex(ArrayList<Integer> index) {
        this.index = index;
    }

    public void addIndex(int index) {
        this.index.add(index);
    }

    public ArrayList<string> getPath() {
        return path;
    }

    public void setPath(ArrayList<string> path) {
        this.path = path;
    }

    public void addPath(String path) {
        this.path.add(path);
    }

    public boolean isStatus() {
        return status;
    }

    public void setStatus(boolean status) {
        this.status = status;
    }
}//Truck---------------business logic class-------------


Execution logic class: Main
  
//Main.java
public class Main
{
 public static void main(String[] args)
 {
  Muphoria muphoria=new Muphoria("sheet1.csv","sheet2.csv");
  muphoria.getResult();
 }
}//Main---------execution logic class-------

5 comments :

  1. Can share you the problem statement of Muphoria 2012 . I tried googling but i didnt find any.Please respond soon.Thanks in advance

    ReplyDelete
    Replies
    1. PROBLEM STATEMENT
      GroceryKart.com is responsible for supplying fresh vegetables and produce to all mom-and-pop retail stores in Mumbai and adjoining suburbs. There are about
      600 stores in their network. They have a fleet of old Matador vans that are being used to haul the goods from their central warehouse in Andheri. Given the
      perishable nature of the goods, all vans leave at 5:00 AM and all deliveries have to happen before 8:00 AM. Each van can make multiple stops but the union contract
      prevents any truck from making more than 35 stops or travelling more than 65 KM in any trip.
      In an effort to reduce costs and minimize greenhouse emissions, GroceryKart.com is planning to retire all the old Matador vans and purchase a new fleet of
      Mahindra vans. They believe the cost of purchasing the Mahindra vans will more or less be covered by the sale of Matador vans and the rest of the money will come
      from the existing savings fund. However, maintaining each truck costs Rs. 20,000 a month (including driver, etc.). Also, the variable cost/km of travel is around Rs.
      30 for the first three years of the truck usage. Each Mahindra truck can carry up to 1000 kg at full capacity and at the end of the trip, all trucks return back to the
      warehouse. Each stop at the store takes 5 minutes to download (irrespective of the weight) and every KM travelled takes 90 seconds on an average.
      The distance between each store and the warehouse is provided in Table 1. The daily demand for each store is provided in Table 2. (Click here to download the
      dataset)
      Can you write a program to determine the number of Mahindra vans required to be purchased and the total KM that will be travelled to service the daily demand of all
      the stores so as to minimize the total cost over the first three years?
      The output of the code should clearly mention:
      The number of trucks needed
      Routing for each truck and
      The total miles travelled each day
      The output should be in a csv where every column of the output is a truck and the entries in the column correspond to the stops the truck makes.

      Delete
  2. how could you write such a lengthy code?...have you used SAS software?

    ReplyDelete
  3. can you also share the dataset to help us understand it?

    ReplyDelete