Mathematical Symbols

Set Symbols

Dynamic programming solution for buying a new machine

1. Suppose a company needs to have a machine over the next five year period. Each new machine costs Rs.100,000. The annual cost of operating a machine during its ith year of operation is given as follows: C1 = 6000, C2 = 8000 and C3 = 12,000. A machine may be kept up to three years before being traded in. This means that a machine can be either kept or traded with in the first two years and has to be traded when its age is three. The trade in value after i years is t1= 80,000, t2 = 60,000 and t3 = 50,000. How can the company minimize costs over the five year period (year 0 to year 5) if the company is going to buy a new machine in the year 0? Devise an optimal solution based on dynamic programming. Illustrate appropriate stages/ states and the optimal-value function.

import java.util.*;

/**
 * Created by IntelliJ IDEA.
 * User: uchan
 * Date: 5/7/12
 * Time: 1:41 PM
 * To change this template use File | Settings | File Templates.
 */
public class OptimalMachineUsage {
    
    private static int initialMachineValue = 100000;
    private static int[] yearlyCost = new int[]{0,6000,8000,12000}; 
    private static int[] valueAfterYear = new int[]{100000,80000,60000,50000};
    
    public static void main(String[] args) {

        Map<String, Integer> possibleSolutions = new LinkedHashMap<String, Integer>();
        findCost(0, 1, 5, 0, new StringBuilder("buy at 0"), possibleSolutions);
        findCost(0, 2, 5, 0, new StringBuilder("buy at 0"), possibleSolutions);
        findCost(0, 3, 5, 0, new StringBuilder("buy at 0"), possibleSolutions);

        int lowCost = Integer.MAX_VALUE;

        List<String> lowCostPaths = new ArrayList<String>();

        for (String path : possibleSolutions.keySet()) {
            System.out.println("(" + path + ") ==> " + possibleSolutions.get(path));
            if(lowCost > possibleSolutions.get(path)) {
                lowCost = possibleSolutions.get(path);
                lowCostPaths.clear();
                lowCostPaths.add(path);
            } else if(lowCost == possibleSolutions.get(path)){
                lowCostPaths.add(path);
            }
        }

        System.out.println("\nLow Cost Paths are ");
        for (String lowCostPath : lowCostPaths) {
            System.out.println(lowCostPath);
        }
        System.out.println("Low Cost Value " + lowCost);

    }
    
    private static void findCost(int buyingYear, int sellingYear, int lastYear, int cost, StringBuilder path, Map<String, Integer> possibleSolutions){
        int operatingCost = findOperatingCost(buyingYear, sellingYear);
        int depreciationCost = findDepreciationCost(buyingYear, sellingYear);


        int costSoFar = cost + (operatingCost + depreciationCost);

        if(sellingYear == lastYear){
            path.append("/sell at " + sellingYear);
            possibleSolutions.put(path.toString(), cost + operatingCost + depreciationCost);
            return ;
        }  else if(sellingYear > lastYear){
            return;
        }

        path.append("/sell and buy at "+ sellingYear);

        findCost(sellingYear, sellingYear+1, lastYear, costSoFar, new StringBuilder(path.toString()), possibleSolutions);
        findCost(sellingYear, sellingYear+2, lastYear, costSoFar, new StringBuilder(path.toString()), possibleSolutions);
        findCost(sellingYear, sellingYear+3, lastYear, costSoFar, new StringBuilder(path.toString()), possibleSolutions);

    }

    private static int findOperatingCost(int buyingYear, int sellingYear) {
        int cost = 0;
        int usage = sellingYear - buyingYear;
        for(int i = 1; i <= usage; i++){
            cost += yearlyCost[i];
        }
        return cost;
    }

    private static int findDepreciationCost(int buyingYear, int sellingYear){
        int usage = sellingYear - buyingYear;
        return initialMachineValue - valueAfterYear[usage];
    }

}

(buy at 0/sell and buy at 1/sell and buy at 2/sell and buy at 3/sell and buy at 4/sell at 5) ==> 130000
(buy at 0/sell and buy at 1/sell and buy at 2/sell and buy at 3/sell at 5) ==> 132000
(buy at 0/sell and buy at 1/sell and buy at 2/sell and buy at 4/sell at 5) ==> 132000
(buy at 0/sell and buy at 1/sell and buy at 2/sell at 5) ==> 128000
(buy at 0/sell and buy at 1/sell and buy at 3/sell and buy at 4/sell at 5) ==> 132000
(buy at 0/sell and buy at 1/sell and buy at 3/sell at 5) ==> 134000
(buy at 0/sell and buy at 1/sell and buy at 4/sell at 5) ==> 128000
(buy at 0/sell and buy at 2/sell and buy at 3/sell and buy at 4/sell at 5) ==> 132000
(buy at 0/sell and buy at 2/sell and buy at 3/sell at 5) ==> 134000
(buy at 0/sell and buy at 2/sell and buy at 4/sell at 5) ==> 134000
(buy at 0/sell and buy at 2/sell at 5) ==> 130000
(buy at 0/sell and buy at 3/sell and buy at 4/sell at 5) ==> 128000
(buy at 0/sell and buy at 3/sell at 5) ==> 130000

Low Cost Paths are
buy at 0/sell and buy at 1/sell and buy at 2/sell at 5
buy at 0/sell and buy at 1/sell and buy at 4/sell at 5
buy at 0/sell and buy at 3/sell and buy at 4/sell at 5
Low Cost Value 128000

Coin problem with greedy approach

import java.util.*;

/**
 * Created by IntelliJ IDEA.
 * User: uchan
 * Date: 5/6/12
 * Time: 9:41 PM
 * To change this template use File | Settings | File Templates.
 */
public class CoinCalc {

    private static int[] coinArray = new int[]{100, 50, 10, 5, 2, 1};

    public static void main(String[] args) {
        if (args.length != 1) {
            System.err.println("Please give the amount as an argument");
            return;
        }
        try {
            int amount = Integer.parseInt(args[0]);
            Map<integer, integer> coinSelectionMap = getCoins(amount);
            System.out.println("CoinSelection = " +  coinSelectionMap);
        } catch (NumberFormatException e) {
            System.err.println("Please specify amount as an integer");
        }
    }

    private static Map<integer, integer> getCoins(int amount) {
        Map<integer, integer> coinSelection = new LinkedHashMap<integer, integer>();
        int rest = amount;

        for (int coinValue : coinArray) {
            int numberOfCoins = rest / coinValue;

            if (numberOfCoins == 0) {
                continue;
            }
            rest = rest % coinValue;
            coinSelection.put(coinValue, numberOfCoins);

            if (rest == 0) {
                break;
            }
        }
        return coinSelection;
    }
}

String search on receive a character ( with knuth morris pratt)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.concurrent.LinkedBlockingQueue;

/**
 * Created by IntelliJ IDEA.
 * User: uchan
 * Date: 3/27/12
 * Time: 9:10 AM
 * To change this template use File | Settings | File Templates.
 */
public class KnuthMorrisPratt {

    private boolean running = true;
    private LinkedBlockingQueue blockingQueue = new LinkedBlockingQueue();

   /**
     * Initialize the character processing thread.  Pass the thread need to be match
     * @param pattern
     */
    public void init(final  char[] pattern){
        Thread thread = new Thread(){ //Below thread will listen for any character received
            public  void run(){
                try {
                    KnuthMorrisPratt.this.match(pattern);
                } catch (Exception e) {
                    System.out.println("Unexpected error occurred " + e.getMessage());
                }
            }
        };
        thread.start();
    }

    /**
     *   This will match for any received characters  for the given pattern. Knuth morris pratt algorithm is used for String matching.
     * @param pattern
     * @throws InterruptedException
     */
    public void match(char[] pattern) throws InterruptedException {
        short [] pi = calculatePi(pattern);
        int q = 0; //number of character matched
        int i = 0;
        while (running) {
            char receivedCharacter = blockingQueue.take();
            while(q > 0 && pattern[q] != receivedCharacter){
               q = pi[q-1];
            }
            if(pattern[q] == receivedCharacter) {
                q = q + 1;
            }
            if(q == pattern.length) {
                System.out.println("Pattern found at [" + (i - pattern.length + 1) + "]");
                q = pi[q-1];
            }
            i++;
        }
    }


    /**
     * Generate pi array for a given pattern
     * @param pattern
     * @return  pi 
     */
    private short[] calculatePi(char[] pattern) {
        short [] pi = new short[pattern.length];
        pi[0] = 0;
        int k = 0;
        for (int i = 1; i < pattern.length; i++) {
            while(k > 0 && pattern[k] != pattern[i]) {
               k = pi[k-1];
           }
           if(pattern[k] == pattern[i]) {
                k = k + 1;
           }
            pi[i] = (short) k;
        }
        return pi;
    }

   /**
     *  Add character to process  for the given pattern
     * @param character
     */
    public void addCharacterToProcess(Character character){
        blockingQueue.add(character);
    }

    /**
     * Convert a text sequence to reverse
     * @param pattern
     * @return
     */
    private static char[] reverse(char[] pattern) {
        char[] reversePattern = new char[pattern.length];
        for (int i = 0; i < pattern.length; i++) {
            reversePattern[pattern.length - 1- i] = pattern[i];
        }
        return  reversePattern;
    }
    
    public static void main(String ... arg) throws IOException {

        if(arg.length != 1 && arg.length != 2) {
            System.out.print("Pass the pattern as an argument");
            return;
        }

        char[] pattern = arg[0].toCharArray();

        if(arg.length == 2) {
            String reverse = arg[1];
            if(reverse.equals("reverse=true")) {
               pattern = reverse(pattern);
            }
        }

        System.out.println("Matching pattern [" + new String(pattern) +"]");
        System.out.println("Type a text and press enter");

        KnuthMorrisPratt knuthMorrisPratt = new KnuthMorrisPratt();
        knuthMorrisPratt.init(pattern);

        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));

        while (true) {
           char c = (char) reader.read();
           knuthMorrisPratt.addCharacterToProcess(c);
        }

    }
}

Knuth moris pratt in java

package kws.algo.string;

import java.util.Arrays;

/**
 * Created by IntelliJ IDEA.
 * User: uchan
 * Date: 3/27/12
 * Time: 9:10 AM
 * To change this template use File | Settings | File Templates.
 */
public class KnuthMorrisPratt {

    public void match(char[] t, char[] p) {
        short [] pi = calculatePi(p);
        int q = 0; //number of character matched
        for(int i = 0; i < t.length; i++) {
            while(q > 0 && p[q] != t[i]){
               q = pi[q-1];
            }
            if(p[q] == t[i]) {
                q = q + 1;
            }
            if(q == p.length) {
                System.out.println("Pattern found ");
                q = pi[q-1];
            }
        }
    }

    private short[] calculatePi(char[] p) {
        short [] pi = new short[p.length];
        pi[0] = 0;
        int k = 0;
        for (int i = 1; i < p.length; i++) {
            while(k > 0 && p[k] != p[i]) {
               k = pi[k-1];
           }
           if(p[k] == p[i]) {
                k = k + 1;
           }
            pi[i] = (short) k;
        }
        return pi;
    }
    
    public static void main(String ... arg) {
        KnuthMorrisPratt knuthMorrisPratt = new KnuthMorrisPratt();
        knuthMorrisPratt.match("xaababacahsababacagadfasd".toCharArray(), "ababaca".toCharArray());
    }
}

String search on receive a character

  
package kws.algo.string;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

/**
 * Created by IntelliJ IDEA.
 * User: uchan
 * Date: 3/25/12
 * Time: 12:56 PM
 * To change this template use File | Settings | File Templates.
 */
public class SignalReceiver {
    
    private LinkedList signalReceived = new LinkedList();
    private char[] pattern;
    
    public void onReceive(char c){
        signalReceived.addLast(c);
        int j = 1;
        if(signalReceived.size() >= pattern.length) {
            for(int i = pattern.length - 1; i > 0; i--){
                if(!signalReceived.get(signalReceived.size() - j++).equals(pattern[i])){
                    return;
                }
            }
            System.out.println("Found the pattern at " + (signalReceived.size() - pattern.length));
        }
    }

    public void setPattern(char[] pattern) {
        this.pattern = pattern;
    }
    
    public void setReversePattern(char[] pattern) {
        setPattern(reverse(pattern));
    }

    private char[] reverse(char[] pattern) {
        char[] reversePattern = new char[pattern.length];
        for (int i = 0; i < pattern.length; i++) {
            reversePattern[pattern.length - 1- i] = pattern[i];                                                        
        }
        return  reversePattern;
    }

    public static void main(String[] args) {
        SignalReceiver signalReceiver = new SignalReceiver();
        signalReceiver.setPattern("msc".toCharArray());
//        signalReceiver.setReversePattern("ccs".toCharArray());

        signalReceiver.onReceive('a'); //0
        signalReceiver.onReceive('m'); //1 <----
        signalReceiver.onReceive('s'); //2 >----
        signalReceiver.onReceive('c'); //3
        signalReceiver.onReceive('c'); //4
        signalReceiver.onReceive('m'); //5 <----
        signalReceiver.onReceive('s'); //6
        signalReceiver.onReceive('c'); //7
        signalReceiver.onReceive('a'); //8
        signalReceiver.onReceive('a'); //9

    }

}