I want to implement a generic barter plateform, but the algorithm is a bit tricky to write.
Here is the idea: we have a bunch of exchange orders between assets called asset1, asset2, etc.
An order looks like that:
#n -q1 assetA q2 assetB
#n is the reference of the order
q1 is the quantity of assetA that is given
q2 is the quantity of assetB that is desired in exchange for assetA
I've made a simple bash function that generates random orders:
randtrades() {
for a in asset{1..10}
do for b in asset{1..10}
do
if [[ "$a" != "$b" ]]
then echo -$((RANDOM%10)) $a $((RANDOM%10)) $b
fi
done
done |
grep -v -e '^-0' -e ' 0' |
sort -r |
cat -n |
sed -r 's/^\s+/#/'
}
The goal is to create a function that takes the output of randtrades as input, and returns list of possible trade cycles:
exemples:
#1 -2 assetA 4 assetB
#2 -1 assetB 2 assetC
#3 -4 assetB 1 assetA
returns:
#1 #3
because obviously orders #1 and #3 match one another (they make a 2-lenghted cycle).
An other exemple:
#1 -2 assetA 4 assetB
#2 -1 assetB 5 assetD
#3 -2 assetC 1 assetA
#4 -5 assetB 2 assetC
returns:
#1 #3 #4
because #1 gives the required asset to #3 which gives the required asset to #4 which finally gives the required asset back to #1. They make a 3-lenghted cycle. Hope it's clear.
Don't worry too much about quantities. The only important thing is that an order is capable of giving at least what is required.
Of course if there are muliple possibilities, all of them should be displayed, one per line.
