info@meritcampus.com    +91-85006-22255
...
`

# Weekend Hack - 16 Mar 2013 - Results

Thanks to Srihari Adelli for spending so much time, coming up with original and innovative answers and for submitting them. Thanks to many others who have tried to get the solution.
We have reviewed the solutions as per the criteria mentioned at Weekend Hack and included the comments below. Few minor comments found are included below in the order of the submission. These comments are not intended to point out the mistakes in the solutions but to learn from them.

The winner of the Weekend Hack 16 Mar 2013 - 1 is Srihari Adelli. He will get a recharge or gift voucher worth Rs. 125.
Weekend Hack 16 Mar 2013 - 2 is not solved.

# Dispense Cash using Currency Notes

Given the currency notes in a cash box, write a program to select which notes should be dispensed to return an amount. When returning, higher preference should be given to larger notes.

Input (List, int) Output (List)
[0], 1 null
[1, 2, 4], 1 [1]
[2, 4, 4, 5, 8], 16 [4, 4, 8]
[1, 2, 4, 20, 40 , 60], 70 null
[2, 4, 5, 6, 15, 20, 30, 45, 70], 90 [20, 70]
[2, 4, 6, 20, 30, 70, 120, 200, 400, 500], 1000 [30, 70, 400, 500]
[100, 500, 342, 12, 6, 1], 443 [1, 100, 342]
[92, 89, 91, 6, 7, 8, 10, 30], 220 [7, 30, 91, 92]
[191, 236, 432, 409, 698], 889 [191, 698]
[1, 1, 1, 1, 1, 6, 6, 6, 6, 6, 6, 12, 90, 100, 800, 800, 1200, 600, 1600, 1900], 3109 [1, 1, 1, 6, 1200, 1900]

## Solution 1 - Submitted on Sun Mar 17 01:46:20 2013

``` import java.util.ArrayList;import java.util.Collections;import java.util.Comparator;import java.util.List;public class DispenseCash {    public static void main(String args[]) {        List currencyNotes = new ArrayList();        currencyNotes.add(2);        currencyNotes.add(4);        currencyNotes.add(4);        currencyNotes.add(5);        currencyNotes.add(8);        List output = dispense(currencyNotes, 16);        System.out.println("The notes to be returned are : " + output);    }    public static List dispense(List currencyNotes, int amount) {        List listOfNotes = new ArrayList();        int dispensedMoney = -1;        int currency = 0;        class sortDescendingOrder implements Comparator {            @Override            public int compare(Integer integer1, Integer integer2) {                return integer2 - integer1;            }        }        class sortAscendingOrder implements Comparator {            @Override            public int compare(Integer integer1, Integer integer2) {                return integer1 - integer2;            }        }        Collections.sort(currencyNotes, new sortDescendingOrder());        outer : for (int i = 0; i < currencyNotes.size(); i++) {            currency = currencyNotes.get(i);            if (currency <= amount) {                listOfNotes.add(currency);                for (int j = i + 1; j < currencyNotes.size(); j++) {                    listOfNotes = new ArrayList();                    listOfNotes.add(currency);                    dispensedMoney = toGetTheNotes(currency, j, currencyNotes, amount, listOfNotes);                    if (dispensedMoney == amount)                        break outer;                }            }            if (currency == amount) {                dispensedMoney = currency;                break outer;            }        }        if (dispensedMoney != amount)            listOfNotes = null;        else            Collections.sort(listOfNotes, new sortAscendingOrder());        return listOfNotes;    }    public static int toGetTheNotes(int currency, int index, List currencyNotes, int amount, List listOfNotes) {        int note = currencyNotes.get(index);        if (currency + note <= amount) {            listOfNotes.add(note);            currency += note;        }        if (index < currencyNotes.size() - 1)            currency = toGetTheNotes(currency, index + 1, currencyNotes, amount, listOfNotes);        return currency;    }} ```

1. The code is easy to understand and the methods are created properly.
2. Effective use of recursive methods to solve the problem.
3. No need to create separate Comparators. Since Integer implements Comparable interface, we can use Collections.sort with out passing any Comparator

# Get Horse Path

In chess, assuming that the columns are numbered A to H and the rows are numbered 1 to 8. Write a program to find the path of a horse from one position to another position. The path returned should be the shortest (minimum number of steps). Assume that there is nothing else on the chess board.

Input (ChessPosition, ChessPosition) Output List (ChessPosition)
C2, B3 [C2, A1, B3]
G1, H1 [G1, E2, G3, H1]
B7, A8 [B7, A5, C4, B6, A8]
A1, H8 [A1, B3, A5, C4, B6, A8]
G1, H1 [G1, E2, G3, H1]
B7, A8 [B7, A5, C4, B6, A8]
G2, B8 [G2, E1, C2, B4, A6, B8]