Programming Geek
Rated 4.1/5 based on 446 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 .
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:

```//Muphoria.java

import java.io.FileWriter;
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;
}//constructor-----end-----

/**reads data from comma delimited csv  file
*
*/
try {

//skip four lines of csv file to start reading data

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

//skip two lines

//stores store and their respective demand in storeWeightMatrix
for (int i = 0; i < storeWeightMatrix.length; i++) {
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()));
}

/**
* 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.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);
}
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.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);
flag = true;
findRoutes(truckList.get(j - 1));
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]);
} 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.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;
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
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.setDelivered(demand);
truck.setTime();
store.setStatus(false);
}

//set truck status false
truck.setStatus(false);

//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;
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;
demand = -demand;
truck.setDelivered(demand);
truck.setTime();
deliveredStoreindexList.remove(deliveredStoreindexList.size() - 1);

}
flag = false;

} else {
//add visited store name in path

//update deliveredStoreindexList

}

//add return distance of the truck if all the stores are visited
if (deliveredStoreindexList.size() == 600 && truck.getIndex().size() < 35 && truck.getDelivered() <= 1000) {
flag = false;
}

//set truck status false if 35 stores are served ...
if (truck.getIndex().size() == 35) {
truck.setStatus(false);
flag = false;
}
}
}//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];

//
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;
}

//
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;
}

this.distance += distance;
}

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

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

}

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

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

}

public boolean isStatus() {
return status;
}

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

```
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-------

```