Currency Convert
Problem Statement
Given the following input CSV file:
From To Rate
USD;EUR;0.89
USD;GBP;0.79
GBP;CHF;1.26
CHF;JPY;108.66
... ... ...
Implement an algorithm to convert from a source currency to a target currency.
package problems; import java.io.FileInputStream; import java.io.FileNotFoundException; import java.util.*; /** * Given the following input CSV file: * * From To Rate * USD;EUR;0.89 * USD;GBP;0.79 * GBP;CHF;1.26 * CHF;JPY;108.66 * ... ... ... * * * Implement an algorithm to convert from a source currency to a target currency. */ public class ConvertCurrency { static class CurrencyGraph { Map<String, Set<String>> nodeToNeighbors; Map<String, Map<String, Double>> sourceToTargetRate; public CurrencyGraph() { nodeToNeighbors = new HashMap<>(); sourceToTargetRate = new HashMap<>(); } void addEdge(String source, String target, Double rate) { if (!nodeToNeighbors.containsKey(source)) { nodeToNeighbors.put(source, new HashSet<>()); } nodeToNeighbors.get(source).add(target); if (!sourceToTargetRate.containsKey(source)) { sourceToTargetRate.put(source, new HashMap<>()); } sourceToTargetRate.get(source).put(target, rate); } Set<String> getNeighborsOf(String node) { if (!nodeToNeighbors.containsKey(node)) { throw new IllegalStateException("Node " + node + " does not exist!"); } return nodeToNeighbors.get(node); } double getRateFor(String source, String target) { if (!nodeToNeighbors.containsKey(source)) { throw new IllegalStateException("Node " + source + " does not exist!"); } if (!(sourceToTargetRate.get(source)).containsKey(target)) { throw new IllegalStateException("Node " + target + " does not exist!"); } return sourceToTargetRate.get(source).get(target); } double dfs(String source, String target, double currentAmount, Set<String> visited) { visited.add(source); Set<String> neighbors = getNeighborsOf(source); for (String neighbor : neighbors) { if (!visited.contains(neighbor)) { double rate = getRateFor(source, neighbor); if (neighbor.equals(target)) { return currentAmount * rate; } else { double tempResult = dfs(neighbor, target, currentAmount * rate, visited); if (tempResult != -1) { return tempResult; } } } } return -1; } double convert(String source, String target, double amount) { if (source.equals(target)) { return amount; } double result = dfs(source, target, amount, new HashSet<>()); if (result != 1) { return result; } else { throw new IllegalStateException("Unable to solve!"); } } } public static void main(String[] args) throws FileNotFoundException { System.setIn(new FileInputStream(System.getProperty("user.home") + "/" + "currencies.csv")); Scanner scanner = new Scanner(System.in); CurrencyGraph graph = new CurrencyGraph(); while (scanner.hasNext()) { String line = scanner.next(); String[] lineSplit = line.split(";"); String source = lineSplit[0]; String target = lineSplit[1]; Double rate = Double.parseDouble(lineSplit[2]); graph.addEdge(source, target, rate); graph.addEdge(target, source, 1 / rate); } String searchSource = "USD"; String searchTarget = "EUR"; double amount = 5; System.out.println(String.format("%f%s is %f%s", amount, searchSource, graph.convert(searchSource, searchTarget, amount), searchTarget)); searchSource = "EUR"; searchTarget = "EUR"; amount = 5; System.out.println(String.format("%f%s is %f%s", amount, searchSource, graph.convert(searchSource, searchTarget, amount), searchTarget)); searchSource = "EUR"; searchTarget = "USD"; amount = 5; System.out.println(String.format("%f%s is %f%s", amount, searchSource, graph.convert(searchSource, searchTarget, amount), searchTarget)); searchSource = "EUR"; searchTarget = "GBP"; amount = 5; System.out.println(String.format("%f%s is %f%s", amount, searchSource, graph.convert(searchSource, searchTarget, amount), searchTarget)); searchSource = "EUR"; searchTarget = "JPY"; amount = 5; System.out.println(String.format("%f%s is %f%s", amount, searchSource, graph.convert(searchSource, searchTarget, amount), searchTarget)); searchSource = "JPY"; searchTarget = "USD"; amount = 5; System.out.println(String.format("%f%s is %f%s", amount, searchSource, graph.convert(searchSource, searchTarget, amount), searchTarget)); } }