Saturday, October 29, 2016

Optimised Painting

Problem https://saikatd.wordpress.com/2016/07/03/optimized-painting/
Given the cost of painting different intervals of a wall, find the minimum cost of painting the entire wall.
Java Program
package com.sourabh.first;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class OptimisedPainting {
 public static void main(String[] args) {
  Interval paintInterval = new Interval();
  paintInterval.setStart(0);
  paintInterval.setEnd(5);
  Map<Interval, Integer> unitHashMap = new HashMap<>();
  for(int i=paintInterval.getStart(); i<paintInterval.getEnd(); i++)
  {
   Interval interval = new Interval();
   interval.setStart(i);
   interval.setEnd(i+1);
   unitHashMap.put(interval, 0);
  }
  //String intervalString = "[0, 5, 10], [0, 4, 1], [0, 2, 5], [2, 5, 1]";
  String intervalString = "[1, 4, 10], [2, 5, 6]";
  String[] intervals = intervalString.split("],");
  List<Interval> intervalsList = new ArrayList<>();
  for(int i=0;i<intervals.length;i++)
  {
   String[] parts = intervals[i].split(",");
   Interval interval = new Interval();
   interval.setStart(Integer.parseInt(parts[0].trim().substring(1)));
   interval.setEnd(Integer.parseInt(parts[1].trim().replaceAll(",", "")));
   interval.setCost(Double.parseDouble(parts[2].trim().replaceAll("]", "")));
   intervalsList.add(interval);
  }
  System.out.println("Input");
  for(Interval combination : intervalsList) {
   System.out.println(combination.getStart() + "," + combination.getEnd() + "," + combination.getCost());
  }
  System.out.println("Output");
  OptimisedPainting op = new OptimisedPainting();
  List<List<Interval>> intervalsCombinations = op.generateCombinations(intervalsList, new ArrayList<>(), 0, new ArrayList<>());
  Double minCost = 999999.99;
  for(List<Interval> intervalsCombination : intervalsCombinations) {
   Double cost = 0.0;
   if(op.isValidIntervalList(intervalsCombination, unitHashMap)) {
    for(Interval combination : intervalsCombination) {
     cost += combination.getCost();
    }
    if(minCost > cost) {
     minCost = cost;
    }
   }
   unitHashMap = op.refreshUnitHashMap(paintInterval);
  }
  if(minCost == 999999.99) {
   System.out.println("-1");
  } else {
   System.out.println("Minimum cost: " + minCost);
  }
 }
 
 public Map<Interval, Integer> refreshUnitHashMap(Interval paintInterval) {
  Map<Interval, Integer> unitHashMap = new HashMap<>();
  for(int i=paintInterval.getStart(); i<paintInterval.getEnd(); i++)
  {
   Interval interval = new Interval();
   interval.setStart(i);
   interval.setEnd(i+1);
   unitHashMap.put(interval, 0);
  }
  return unitHashMap;
 }
 
 public boolean isValidIntervalList(List<Interval> intervalsList, Map<Interval, Integer> unitHashMap) {
  for(Interval interval : intervalsList) {
   for(int i=interval.getStart(); i<interval.getEnd(); i++)
   {
    Interval temp = new Interval();
    temp.setStart(i);
    temp.setEnd(i+1);
    unitHashMap.put(temp, 1);
   }
  }
  return !unitHashMap.containsValue(0);
 }
 
 public List<List<Interval>> generateCombinations(List<Interval> intervalsList, 
   List<List<Interval>> intervalsCombinations, int start, List<Interval> outputList) {
  for(int index = start; index < intervalsList.size(); index++) {
   outputList.add(intervalsList.get(index));
   List<Interval> tempList = new ArrayList<>();
   for(Interval interval : outputList) {
    tempList.add(interval);
   }
   intervalsCombinations.add(tempList);
   tempList = null;
   intervalsCombinations = generateCombinations(intervalsList, intervalsCombinations, index+1, outputList);
   outputList.remove(outputList.size() - 1);
  }
  return intervalsCombinations;
 }
}

class Interval {
 private int start;
 private int end;
 private double cost;
 public int getStart() {
  return start;
 }
 public void setStart(int start) {
  this.start = start;
 }
 public int getEnd() {
  return end;
 }
 public void setEnd(int end) {
  this.end = end;
 }
 public double getCost() {
  return cost;
 }
 public void setCost(double cost) {
  this.cost = cost;
 }
 @Override
 public int hashCode() {
  final int prime = 31;
  int result = 1;
  result = prime * result + end;
  result = prime * result + start;
  return result;
 }
 @Override
 public boolean equals(Object obj) {
  if (this == obj)
   return true;
  if (obj == null)
   return false;
  if (getClass() != obj.getClass())
   return false;
  Interval other = (Interval) obj;
  if (end != other.end)
   return false;
  if (start != other.start)
   return false;
  return true;
 }
}

2 comments: