Untitled

public class BacktrackingStrategy implements BestRateFinder {
    private double findMaxRate(HashMap<String, ArrayList<Edge>> adjList, HashSet<String> visited, String source, String target){
        if(Objects.equals(source, target)){
            return 1.0;
        }
        visited.add(source);
        double rate = -1.0;
        for(int i = 0;i<adjList.get(source).size();i++){
            if(!visited.contains(adjList.get(source).get(i).target)){
                rate = Math.max(rate, adjList.get(source).get(i).rate  * findMaxRate(adjList, visited, adjList.get(source).get(i).target, target));
            }
        }
        visited.remove(source);
        return rate;
    }
    @Override
    public double findBestRate(ArrayList<Currency> currencies, String source, String target) {
        HashMap<String, ArrayList<Edge>> adjList = new HashMap<>();

        for(Currency curr: currencies){
            adjList.putIfAbsent(curr.getSource(), new ArrayList<>());
            adjList.putIfAbsent(curr.getTarget(), new ArrayList<>());
            adjList.get(curr.getSource()).add(new Edge(curr.getTarget(), curr.getRate()));
        }

        HashSet<String> visitedCurrencies = new HashSet<>();
        return findMaxRate(adjList, visitedCurrencies, source, target);
    }
}


public class BellmanFord implements BestRateFinder {
    @Override
    public double findBestRate(ArrayList<Currency> currencies, String source, String target) {

        HashMap<String, Double> dist = new HashMap<>();
        ArrayList<EdgeV2> edges = new ArrayList<>();

        for(Currency curr: currencies){
            double weight = -Math.log(curr.getRate());
            dist.putIfAbsent(curr.getSource(), Double.MAX_VALUE);
            dist.putIfAbsent(curr.getTarget(), Double.MAX_VALUE);
            EdgeV2 edge = new EdgeV2(curr.getSource(), curr.getTarget(), weight);
            edges.add(edge);
        }

        dist.put(source, 0.0);

        int V = dist.size();

        for(int i = 0;i<V-1;i++){
            for(EdgeV2 curr: edges){
                if(dist.get(curr.getSource()) + curr.getWeight() < dist.get(curr.getTarget())){
                    dist.put(curr.getTarget(), dist.get(curr.getSource()) + curr.getWeight());
                }
            }
        }
        return Math.exp(-dist.getOrDefault(target, Double.MAX_VALUE));
    }
}

public interface BestRateFinder {
    double findBestRate(ArrayList<Currency> currencies, String source, String target);
}


public class Currency {
    private String source;
    private String target;
    private double rate;

    public String getSource() {
        return source;
    }

    public String getTarget() {
        return target;
    }

    public double getRate() {
        return rate;
    }

    public Currency(String source, String target, double rate) {
        this.source = source;
        this.target = target;
        this.rate = rate;
    }
}

public class EdgeV2 {
    String source;
    String target;
    Double weight;

    public EdgeV2(String source, String target, Double weight) {
        this.source = source;
        this.target = target;
        this.weight = weight;
    }

    public String getSource() {
        return source;
    }

    public String getTarget() {
        return target;
    }

    public Double getWeight() {
        return weight;
    }
}

public class Edge {
    public String target;

    public Edge(String target, double rate) {
        this.target = target;
        this.rate = rate;
    }

    public double rate;
}