import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.Reader;
import java.nio.charset.Charset;
import java.nio.charset.StandardCharsets;
import java.util.HashMap;
import java.util.Iterator;
/*
*
curl https://freecurrencyrates.com/en/EUR-exchange-rate-calculator > EUR.html
curl https://freecurrencyrates.com/en/CNH-exchange-rate-calculator > CNH.html
python -m SimpleHTTPServer 8080
*
*/
import java.util.Map;
import java.util.regex.Matcher;
import java.util.regex.Pattern;
//Arbitrage.java
public class Arbitrage {
public static String[] CURRENCIES = {"USD", "CAD", "EUR", "CNY", "BTT", "HKD", "JPY"};
public static void main(String[] args) {
int V = CURRENCIES.length;
SimpleRateCropper src = new SimpleRateCropper();
Map<Integer, Double> rates = new HashMap<>();
EdgeWeightedDigraph G = new EdgeWeightedDigraph(V);
for (int v = 0; v < V; v++) {
src.getRate(CURRENCIES[v], rates);
for (int w = 0; w < V; w++) {
if(w == v) continue;
Double rate = rates.get(w);
if(rate == null) continue;
DirectedEdge e = new DirectedEdge(v, w, -Math.log(rate));
G.addEdge(e);
}
}
BellmanFordSP spt = new BellmanFordSP(G, 0);
if (spt.hasNegativeCycle()) {
double stake = 1000.0;
for (DirectedEdge e : spt.negativeCycle()) {
System.out.printf("%10.5f %s ", stake, CURRENCIES[e.from()]);
stake *= Math.exp(-e.weight());
System.out.printf("= %10.5f %s\n", stake, CURRENCIES[e.to()]);
}
} else {
System.out.println("No arbitrage opportunity");
System.out.println(G.E() + " exchange among " + G.V() + " currency Examed");
}
}
}
class SimpleRateCropper {
/* looking for 4.36 and ZRX
* <div class="rate-box col l4 m6 s12">
<input id="rate-iso-ZRX" type="text" class="rate-value" value="4.36" data-rate="3.9939599842084">
<a class="data-cell" href="/en/convert-EUR-ZRX" title="Free online Euro (EUR) and 0x (ZRX) exchange rate calculator">0x (ZRX)</a>
</div>
*/
public void getRate(String currentCode, Map<Integer, Double> rates) {
rates.clear();
System.out.println("cropping for " + currentCode);
try {
String txt = getRatePage(currentCode);
for(int i = 0; i < Arbitrage.CURRENCIES.length; i++) {
if(!Arbitrage.CURRENCIES[i].equals(currentCode)) {
String regex = String.format(
"<input id=\"rate-iso-%s\" type=\"text\" class=\"rate-value\" value=\"([0-9.]+)\" data-rate=\"[0-9.]+\">"
, Arbitrage.CURRENCIES[i]);
Pattern pattern = Pattern.compile(regex);
Matcher matcher = pattern.matcher(txt);
if(matcher.find()) {
System.out.println("found: " + Arbitrage.CURRENCIES[i] + " : "
+ matcher.group(1));
rates.put(i, Double.parseDouble(matcher.group(1)));
}
}
}
} catch (IOException e) {
e.printStackTrace();
}
}
public String getRatePage(String currentCode) throws IOException {
String command = String.format(
"curl -X GET https://freecurrencyrates.com/en/%s-exchange-rate-calculator", currentCode);
Process process = Runtime.getRuntime().exec(command);
StringBuilder textBuilder = new StringBuilder();
try (Reader reader = new BufferedReader(new InputStreamReader
(process.getInputStream(), Charset.forName(StandardCharsets.UTF_8.name())))) {
int c = 0;
while ((c = reader.read()) != -1) {
textBuilder.append((char) c);
}
}
process.destroy();
return textBuilder.toString();
}
}
// BellmanFordSP.java
class BellmanFordSP {
private double[] distTo;
private DirectedEdge[] edgeTo;
private boolean[] onQ;
private Queue<Integer> queue;
private int cost;
private Iterable<DirectedEdge> cycle; // negative cycle in edgeTo[]?
public BellmanFordSP(EdgeWeightedDigraph G, int s) {
distTo = new double[G.V()];
edgeTo = new DirectedEdge[G.V()];
onQ = new boolean[G.V()];
queue = new Queue<Integer>();
for (int v = 0; v < G.V(); v++)
distTo[v] = Double.POSITIVE_INFINITY;
distTo[s] = 0.0;
queue.enqueue(s);
onQ[s] = true;
while (!queue.isEmpty() && !this.hasNegativeCycle()) {
int v = queue.dequeue();
onQ[v] = false;
relax(G, v);
}
}
private void relax(EdgeWeightedDigraph G, int v) {
for (DirectedEdge e : G.adj(v)) {
int w = e.to();
if (distTo[w] > distTo[v] + e.weight()) {
distTo[w] = distTo[v] + e.weight();
edgeTo[w] = e;
if (!onQ[w]) {
queue.enqueue(w);
onQ[w] = true;
}
}
if (cost++ % G.V() == 0)
findNegativeCycle();
}
}
public double distTo(int v) {
return distTo[v];
}
public boolean hasPathTo(int v) {
return distTo[v] < Double.POSITIVE_INFINITY;
}
public Iterable<DirectedEdge> pathTo(int v) {
if (!hasPathTo(v))
return null;
Stack<DirectedEdge> path = new Stack<DirectedEdge>();
for (DirectedEdge e = edgeTo[v]; e != null; e = edgeTo[e.from()])
path.push(e);
return path;
}
private void findNegativeCycle() {
int V = edgeTo.length;
EdgeWeightedDigraph spt;
spt = new EdgeWeightedDigraph(V);
for (int v = 0; v < V; v++)
if (edgeTo[v] != null)
spt.addEdge(edgeTo[v]);
EdgeWeightedDirectedCycle cf;
cf = new EdgeWeightedDirectedCycle(spt);
cycle = cf.cycle();
}
public boolean hasNegativeCycle() {
return cycle != null;
}
public Iterable<DirectedEdge> negativeCycle() {
return cycle;
}
}
// EdgeWeightedDigraph.java
class EdgeWeightedDigraph {
private final int V;
private int E;
private Bag<DirectedEdge>[] adj;
public EdgeWeightedDigraph(int V) {
this.V = V; // number of vertices
this.E = 0; // number of edges
adj = (Bag<DirectedEdge>[]) new Bag[V]; // adjacency lists
for (int v = 0; v < V; v++)
adj[v] = new Bag<DirectedEdge>();
}
public int V() {
return V;
}
public int E() {
return E;
}
public void addEdge(DirectedEdge e) {
adj[e.from()].add(e);
E++;
}
public Iterable<DirectedEdge> adj(int v) {
return adj[v];
}
public Iterable<DirectedEdge> edges() {
Bag<DirectedEdge> bag = new Bag<DirectedEdge>();
for (int v = 0; v < V; v++)
for (DirectedEdge e : adj[v])
bag.add(e);
return bag;
}
}
// DirectedEdge.java
class DirectedEdge {
private final int v; // edge source
private final int w; // edge target
private final double weight; // edge weight
public DirectedEdge(int v, int w, double weight) {
this.v = v;
this.w = w;
this.weight = weight;
}
public double weight() {
return weight;
}
public int from() {
return v;
}
public int to() {
return w;
}
public String toString() {
return String.format("%d->%d %.2f", v, w, weight);
}
}
// Stack.java
class Stack<Item> implements Iterable<Item> {
private Node first; // top of stack (most recently added node)
private int N; // number of items
private class Node { // nested class to define nodes
Item item;
Node next;
}
public boolean isEmpty() {
return first == null;
} // Or: N == 0.
public int size() {
return N;
}
public void push(Item item) { // Add item to top of stack.
Node oldfirst = first;
first = new Node();
first.item = item;
first.next = oldfirst;
N++;
}
public Item pop() { // Remove item from top of stack.
Item item = first.item;
first = first.next;
N--;
return item;
}
public Iterator<Item> iterator() {
return new ListIterator();
}
private class ListIterator implements Iterator<Item> {
private Node current = first;
public boolean hasNext() {
return current != null;
}
public void remove() {
}
public Item next() {
Item item = current.item;
current = current.next;
return item;
}
}
}
// Queue.java
class Queue<Item> implements Iterable<Item> {
private Node first; // link to least recently added node
private Node last; // link to most recently added node
private int N; // number of items on the queue
private class Node { // nested class to define nodes
Item item;
Node next;
}
public boolean isEmpty() {
return first == null;
} // Or: N == 0.
public int size() {
return N;
}
public void enqueue(Item item) { // Add item to the end of the list.
Node oldlast = last;
last = new Node();
last.item = item;
last.next = null;
if (isEmpty())
first = last;
else
oldlast.next = last;
N++;
}
public Item dequeue() { // Remove item from the beginning of the list.
Item item = first.item;
first = first.next;
if (isEmpty())
last = null;
N--;
return item;
}
public Iterator<Item> iterator() {
return new ListIterator();
}
private class ListIterator implements Iterator<Item> {
private Node current = first;
public boolean hasNext() {
return current != null;
}
public void remove() {
}
public Item next() {
Item item = current.item;
current = current.next;
return item;
}
}
}
// Bag.java
class Bag<Item> implements Iterable<Item> {
private Node first; // first node in list
private class Node {
Item item;
Node next;
}
public void add(Item item) { // same as push() in Stack
Node oldfirst = first;
first = new Node();
first.item = item;
first.next = oldfirst;
}
public Iterator<Item> iterator() {
return new ListIterator();
}
private class ListIterator implements Iterator<Item> {
private Node current = first;
public boolean hasNext() {
return current != null;
}
public void remove() {
}
public Item next() {
Item item = current.item;
current = current.next;
return item;
}
}
}
//EdgeWeightedDirectedCycle.java
class EdgeWeightedDirectedCycle {
private boolean[] marked; // marked[v] = has vertex v been marked?
private DirectedEdge[] edgeTo; // edgeTo[v] = previous edge on path to v
private boolean[] onStack; // onStack[v] = is vertex on the stack?
private Stack<DirectedEdge> cycle; // directed cycle (or null if no such cycle)
/**
* Determines whether the edge-weighted digraph {@code G} has a directed cycle and,
* if so, finds such a cycle.
* @param G the edge-weighted digraph
*/
public EdgeWeightedDirectedCycle(EdgeWeightedDigraph G) {
marked = new boolean[G.V()];
onStack = new boolean[G.V()];
edgeTo = new DirectedEdge[G.V()];
for (int v = 0; v < G.V(); v++)
if (!marked[v]) dfs(G, v);
// check that digraph has a cycle
assert check();
}
// check that algorithm computes either the topological order or finds a directed cycle
private void dfs(EdgeWeightedDigraph G, int v) {
onStack[v] = true;
marked[v] = true;
for (DirectedEdge e : G.adj(v)) {
int w = e.to();
// short circuit if directed cycle found
if (cycle != null) return;
// found new vertex, so recur
else if (!marked[w]) {
edgeTo[w] = e;
dfs(G, w);
}
// trace back directed cycle
else if (onStack[w]) {
cycle = new Stack<DirectedEdge>();
DirectedEdge f = e;
while (f.from() != w) {
cycle.push(f);
f = edgeTo[f.from()];
}
cycle.push(f);
return;
}
}
onStack[v] = false;
}
public boolean hasCycle() {
return cycle != null;
}
public Iterable<DirectedEdge> cycle() {
return cycle;
}
private boolean check() {
// edge-weighted digraph is cyclic
if (hasCycle()) {
// verify cycle
DirectedEdge first = null, last = null;
for (DirectedEdge e : cycle()) {
if (first == null) first = e;
if (last != null) {
if (last.to() != e.from()) {
System.err.printf("cycle edges %s and %s not incident\n", last, e);
return false;
}
}
last = e;
}
if (last.to() != first.from()) {
System.err.printf("cycle edges %s and %s not incident\n", last, first);
return false;
}
}
return true;
}
}
