Two lists merging/unifying

Hey, I have a list of inputs, that can be a buy or a sell.
I sort these according to being a sell or a buy and merge the ones with the same price(to be one unit with the sum of the amounts). Also I can keep them in one list with the same result.

What I want to do that with in mind of the order, I want the buys to hit out the sells, if the price is equal or lower, a transaction to happen sort of.

I can’t really wrap my head around it so far,
as I imagine I would need to go on item basis, like take the first from buy and sell, compare them -> make a decision that can be transaction and update the values/remove them -> or keep both of the items. But then on the next round I would need to keep the result of this in mind, and check on it first.

Any thoughts?

Sorry, for not giving context, so,
yes the other question is related, but this introduces a new problem, but that one was solved.

The problem:

I have this json:

{
   "orders": [
      {"command": "sell", "price": 100.003, "amount": 2.4},
      {"command": "buy", "price": 90.394, "amount": 3.445},
      {"command": "buy", "price": 89.394, "amount": 4.3},
      {"command": "sell", "price": 100.013, "amount": 2.2},
      {"command": "buy", "price": 90.15, "amount": 1.305},
      {"command": "buy", "price": 90.394, "amount": 1.0},
      {"command": "sell", "price": 90.394, "amount": 2.2}   
   ]
}

and the expected output is:

{
   "buy": [
     { 
       "price": 90.394,
       "volume": 2.245
     },
     { 
       "price": 90.15,
       "volume": 1.305
     },
     { 
       "price": 89.394,
       "volume": 4.3
     },
   ],
   "sell": [
     { 
       "price": 100.003,
       "volume": 2.4
     },
     { 
       "price": 100.013,
       "volume": 2.2
     }
   ]
}

all the sorting aside, as you see 7 goes in and 5 comes out.
the ones with the same price are added up or if there is a sell and a buy with the same price those take care of each other too.
I solved this by doing this after creating the orders:
my code here works on one list, and then i split that into the buy and sell lists for displaying, but if i split the 2 lists and then pass that list to this function we in the same spot

defp transactions(limit_orders) do
    for order <- limit_orders do
      Enum.reduce(
        limit_orders,
        order,
        fn x, y ->
          cond do
            Decimal.cmp(x.price, y.price) == :eq and x.id != y.id and x.command == y.command ->
              new_amount = Decimal.add(x.amount, y.amount)

              y
              |> Map.put(:amount, new_amount)
              |> Map.put(:id, x.id)

            Decimal.cmp(x.price, y.price) == :eq and x.command != y.command ->
              case Decimal.cmp(x.amount, y.amount) do
                :gt ->
                  new_amount = Decimal.sub(x.amount, y.amount)
                  Map.put(x, :amount, new_amount)

                :lt ->
                  new_amount = Decimal.sub(y.amount, x.amount)
                  Map.put(y, :amount, new_amount)

                :eq ->
                  nil
              end

            true ->
              y
          end
        end
      )
    end
    |> Enum.filter(&(!is_nil(&1)))
    |> Enum.uniq_by(fn x -> x.id end)
  end

The new problem:
let’s say I extend the previous order list with a few new orders:

{
   "orders": [
      {"command": "sell", "price": 100.003, "amount": 2.4},
      {"command": "buy", "price": 90.394, "amount": 3.445},
      {"command": "buy", "price": 89.394, "amount": 4.3},
      {"command": "sell", "price": 100.013, "amount": 2.2},
      {"command": "buy", "price": 90.15, "amount": 1.305},
      {"command": "buy", "price": 90.394, "amount": 1.0},
      {"command": "sell", "price": 90.394, "amount": 2.2},
new one below:
      {"command": "sell", "price": 90.15, "amount": 3.4}     
   ]
}

As you can see from the output of the previous one the the lowest buy price is higher than the lowest sell price 90.15 here. So that transaction should happen as well.
After that, we compare volume of 90.394 with amount of the sell command. volume of 90.394 is 2.245 and amount of 90.15 is 3.4. So that, we’ve amount left is 3.4 - 2.245 = 1.155 There is amount left. Then, this is partially matched! This command has to continue matching next buy price.
Continue next price, We compare 90.15 with 90.15 on Buy side. It is matched again. because the price on both side is equal. Let’s check the volume on buy side with the amount left which is 1.155 - 1.305 = -0.15. It means there is no amount left. And now volume on buy side would be 0.15.

So the expect output after this one is this:

{
   "buy": [
     { 
       "price": 90.15,
       "volume": 0.15
     },
     { 
       "price": 89.394,
       "volume": 4.3
     },
   ],
   "sell": [
     { 
       "price": 100.003,
       "volume": 2.4
     },
     { 
       "price": 100.013,
       "volume": 2.2
     }
   ]
}

my code in it’s current state puts out this:

{
    "buy": [
        {
            "price": "90.394",
            "volume": "2.245"
        },
        {
            "price": "89.394",
            "volume": "4.3"
        }
    ],
    "sell": [
        {
            "price": "90.15",
            "volume": "2.095"
        },
        {
            "price": "100.003",
            "volume": "2.4"
        },
        {
            "price": "100.013",
            "volume": "2.2"
        }
    ]
}

since it doesn’t match on higher buying price, only if it matches exactly.
I made another case where it would match if there is a higher buying price in a similar fashion to the matching price, but if i add other orders as well:

{
   "orders": [
      {"command": "sell", "price": 100.003, "amount": 2.4},
      {"command": "buy", "price": 90.394, "amount": 3.445},
      {"command": "buy", "price": 89.394, "amount": 4.3},
      {"command": "sell", "price": 100.013, "amount": 2.2},
      {"command": "buy", "price": 90.15, "amount": 1.305},
      {"command": "buy", "price": 90.394, "amount": 1.0},
      {"command": "sell", "price": 90.394, "amount": 2.2},
      {"command": "sell", "price": 90.15, "amount": 3.4},      
      {"command": "buy", "price": 91.33, "amount": 1.8},      
      {"command": "buy", "price": 100.01, "amount": 4.0},        
      {"command": "sell", "price": 100.15, "amount": 3.8}          
   ]
}

th3 3 bottom ones,
since my “design” doesn’t respect the order of the commands strictly put, it wont give the desired output:

{
   "buy": [
     { 
       "price": 100.01,
       "volume": 1.6
     },
     { 
       "price": 91.33,
       "volume": 1.8
     },
     { 
       "price": 90.15,
       "volume": 0.15
     },
     { 
       "price": 89.394,
       "volume": 4.3
     },
   ],
   "sell": [
     { 
       "price": 100.013,
       "volume": 2.2
     },
     { 
       "price": 100.15,
       "volume": 3.8
     }
   ]
}

because it would match on the exactly matching prices first

It would be helpful if you could post some code of what you tried so far.

1 Like

At least post example input and expected output?

1 Like

This seems like this is part of this thread: Merging maps in list based on matching value ?

3 Likes
  • Start with two lists buy_in and sell_in

    • Each item in buy_in lists a quantity for a price
    • Each item in sell_in lists a quantity for a price
  • Output:

    • buy_out - list of quantity/price that couldn’t be matched to a sell
    • sell_out - list of quantity/price that couldn’t be matched to a buy
    • matched_out - list of quantity/buy_price/sell_price items.
  • First sort both buy_in and sell_in by asscending price

  • head of buy_in price >= head of sell_in price

    • head of buy_in quantity > sell_in quantity THEN
      • create sell_in quantity at the head of matched_out
      • replace head of buy_in quantity with (quantity - head of sell_in quantity)
      • drop head of sell_in
      • repeat
    • head of buy_in quantity < sell_in quantity THEN
      • create buy_in quantity at the head of matched_out
      • replace head of sell_in quantity with (quantity - head of buy_in quantity)
      • drop head of buy_in
      • repeat
    • head of buy_in quantity == sell_in quantity THEN
      • create buy_in quantity at the head of matched_out
      • drop head of sell_in
      • drop head of buy_in
      • repeat
  • head of buy_in price < head of sell_in price

    • move head of buy_in to buy_out
    • repeat
  • you’re done when either buy_in or sell_in are empty

    • move the rest of buy_in to buy_out
    • move the rest of sell_in to sell_out
    • done

I’d implement this with recursion/pattern matching (guard clauses).

I think, that sorting them by ascending price, while logical it introduces a problem, when you could complete a transaction that was later in the order sooner by just having a higher price

Regarding your first input and desired output:

Not sure I understood your requirements but the code below seems to result in what you want:

defmodule Stock do
  @doc ~S"""
  Parses JSON orders and wraps all floats in `Decimal`s.
  """
  def decode_and_normalize_json_orders(json)
  when is_binary(json) do
    json
    |> Jason.decode!()
    |> Map.get("orders")
    |> Enum.map(fn(%{"amount" => amount, "price" => price} = x) ->
      %{x |
        "price"  => Decimal.from_float(price)  |> Decimal.reduce(),
        "amount" => Decimal.from_float(amount) |> Decimal.reduce(),
       }
    end)
  end

  @doc ~S"""
  Deducts sales from purchases that share the same price
  and groups them by operation (`"buy"` or `"sell"`).
  """
  def aggregate_purchases_and_sales(orders)
  when is_list(orders) do
    orders
    |> Enum.group_by(& &1["price"])
    |> Enum.map(fn({_price, orders}) ->
      Enum.reduce(orders, fn(order, acc) ->
        amount = case order["command"] do
          "buy"  -> Decimal.add(acc["amount"], order["amount"])
          "sell" -> Decimal.sub(acc["amount"], order["amount"])
          _      -> raise(ArgumentError, "Invalid command: #{order["command"]}")
        end

        case Decimal.cmp(amount, Decimal.from_float(0.0)) do
          :lt ->
             %{acc |
               "amount" => Decimal.minus(amount),
               "command" => flip_command(acc["command"])
             }

          _ ->
             %{acc |
               "amount" => amount
             }
        end
      end)
    end)
    |> Enum.group_by(& &1["command"])
    |> Enum.map(fn({command, orders}) ->
      {
        command,
        Enum.map(orders, fn(%{"amount" => amount, "price" => price}) ->
          %{amount: Decimal.to_float(amount), price: Decimal.to_float(price)}
        end)
      }
    end)
    |> Map.new()
  end

  def flip_command("buy"),  do: "sell"
  def flip_command("sell"), do: "buy"
  def flip_command(cmd), do: raise(ArgumentError, "Invalid command: #{cmd}")

  @doc ~S"""
  Encodes the aggregates generated by `aggregate_purchases_and_sales/1` to JSON.
  """
  def encode_json_aggregates(operations)
  when is_map(operations) do
    Jason.encode!(operations)
  end
end

Test in iex:


json = ~S"""
{
   "orders": [
      {"command": "sell", "price": 100.003, "amount": 2.4},
      {"command": "buy", "price": 90.394, "amount": 3.445},
      {"command": "buy", "price": 89.394, "amount": 4.3},
      {"command": "sell", "price": 100.013, "amount": 2.2},
      {"command": "buy", "price": 90.15, "amount": 1.305},
      {"command": "buy", "price": 90.394, "amount": 1.0},
      {"command": "sell", "price": 90.394, "amount": 2.2}   
   ]
}
"""

input = Stock.decode_and_normalize_json_orders(json)
output = Stock.aggregate_purchases_and_sales(input)
json_output = Stock.encode_json_aggregates(output)

EDIT 1: Updated the code to properly flip a buy to a sell or vice versa if the amount becomes negative. Note that it still uses "amount" instead of "volume" in the end result.

EDIT 2: I don’t understand the second and third expected outputs, can you explain?

Hey, thanks for putting the time in, what i do is i get the json, and create the limit_orders in the databse and then get those, and then return them in the view so mine puts out volume, anyway to your question:

so for number 2 as you can see until the new order, it is the same as the first example, but the price is different, if we take the result of the first example, the buys, you can see:

 { 
       "price": 90.394,
       "volume": 2.245
     }

this price is for a buy and it is higher than the price for the new order, which is a sell, so this transaction should go through and then that buy would go away from the list, but we still have some amount left from the sell, and that price matches again for a buy so that transaction would go through as well, and that is how we get the expected result for number 2

I am afraid I don’t understand at all. Weren’t the records supposed to be grouped by exact prices and then processed? And if a price is higher, why would it even be subtracted from the 90.394 record?

EDIT: Reading your post, you seem to also want to work with prices that are not exactly equal. For example, I am noticing you want to group up operations on the prices 90.15 and 90.394. Is that true?

I don’t recall that your initial statement mentioned that order was significant.

So just brute force it:

Session:

$ elixir demo.exs
data
{[
   %{amount: 2245, command: :buy, price: 90394},
   %{amount: 4300, command: :buy, price: 89394},
   %{amount: 1305, command: :buy, price: 90150}
 ],
 [
   %{amount: 2400, command: :sell, price: 100003},
   %{amount: 2200, command: :sell, price: 100013}
 ]}
data2
{[
   %{amount: 4300, command: :buy, price: 89394},
   %{amount: 150, command: :buy, price: 90150}
 ],
 [
   %{amount: 2400, command: :sell, price: 100003},
   %{amount: 2200, command: :sell, price: 100013}
 ]}
data3
{[
   %{amount: 4300, command: :buy, price: 89394},
   %{amount: 150, command: :buy, price: 90150},
   %{amount: 1800, command: :buy, price: 91330},
   %{amount: 1600, command: :buy, price: 100010}
 ],
 [
   %{amount: 2200, command: :sell, price: 100013},
   %{amount: 3800, command: :sell, price: 100150}
 ]}

Code:

defmodule Demo do
  def run(data),
    do: List.foldl(data, {[], []}, &reducer/2)

  defp reducer(%{command: :sell} = sell, {buys, sells}) do
    case apply_sell(sell, buys, []) do
      {nil, new_buys} ->
        {new_buys, sells}

      {new_sell, new_buys} ->
        {new_buys, combine(sells, new_sell, [])}
    end
  end

  defp reducer(%{command: :buy} = buy, {buys, sells}) do
    case apply_buy(buy, sells, []) do
      {nil, new_sells} ->
        {buys, new_sells}

      {new_buy, new_sells} ->
        {combine(buys, new_buy, []), new_sells}
    end
  end

  defp apply_buy(buy, [], other) do
    {buy, :lists.reverse(other)}
  end

  defp apply_buy(
         %{price: buy_price, amount: buy_amount} = buy,
         [%{price: sell_price, amount: sell_amount} = sell | tail],
         other
       )
       when buy_price >= sell_price do
    cond do
      buy_amount > sell_amount ->
        apply_buy(%{buy | amount: buy_amount - sell_amount}, tail, other)

      buy_amount < sell_amount ->
        {nil, :lists.reverse(other, [%{sell | amount: sell_amount - buy_amount} | tail])}

      true ->
        {nil, :lists.reverse(other, tail)}
    end
  end

  defp apply_buy(buy, [sell | tail], other) do
    # buy price too low
    apply_buy(buy, tail, [sell | other])
  end

  defp apply_sell(sell, [], other) do
    {sell, :lists.reverse(other)}
  end

  defp apply_sell(
         %{price: sell_price, amount: sell_amount} = sell,
         [%{price: buy_price, amount: buy_amount} = buy | tail],
         other
       )
       when sell_price <= buy_price do
    cond do
      sell_amount > buy_amount ->
        apply_sell(%{sell | amount: sell_amount - buy_amount}, tail, other)

      sell_amount < buy_amount ->
        {nil, :lists.reverse(other, [%{buy | amount: buy_amount - sell_amount} | tail])}

      true ->
        {nil, :lists.reverse(other, tail)}
    end
  end

  defp apply_sell(sell, [buy | tail], other) do
    # sell price too high
    apply_sell(sell, tail, [buy | other])
  end

  defp combine([], item, other),
    do: :lists.reverse(other, [item])

  defp combine(
         [%{price: head_price, amount: head_amount} = head | tail],
         %{price: item_price, amount: item_amount},
         other
       )
       when head_price === item_price,
       do: :lists.reverse(other, [%{head | amount: head_amount + item_amount} | tail])

  defp combine([head | tail], item, other),
    do: combine(tail, item, [head | other])
end

data = [
  %{command: :sell, price: 100_003, amount: 2_400},
  %{command: :buy, price: 90_394, amount: 3_445},
  %{command: :buy, price: 89_394, amount: 4_300},
  %{command: :sell, price: 100_013, amount: 2_200},
  %{command: :buy, price: 90_150, amount: 1_305},
  %{command: :buy, price: 90_394, amount: 1_000},
  %{command: :sell, price: 90_394, amount: 2_200}
]

IO.puts("data")
IO.inspect(Demo.run(data))

data2 =
  data ++
    [%{command: :sell, price: 90_150, amount: 3_400}]

IO.puts("data2")
IO.inspect(Demo.run(data2))

data3 =
  data2 ++
    [
      %{command: :buy, price: 91_330, amount: 1_800},
      %{command: :buy, price: 100_010, amount: 4_000},
      %{command: :sell, price: 100_150, amount: 3_800}
    ]

IO.puts("data3")
IO.inspect(Demo.run(data3))
2 Likes

Yes, that is true - your edit,
if the buy is higher than the sell then it should pass as a transaction and adjust the amounts left on wither side.
we only need to group the operations strictly speaking for the return.

Sorry, still not getting it. You said you only need to process identical prices. And now it seems that’s no longer true. And you are not saying which prices get coalesced with which others in case of buy > sell.

Anybody else feeling they understand and want to explain? For example, why would the operations for prices 90.15 and 90.394 be grouped together? Why not also include 89.394?

Nono, the grouping is still the same if the command is the same.
the only changes is that if a price is for a selling order is lower than a price from the buying that will match as well, this is where the order of orders come in place

Sequence of events:

{"command": "buy", "price": 90.394, "amount": 3.445}
{"command": "buy", "price": 89.394, "amount": 4.3}
{"command": "buy", "price": 90.15, "amount": 1.305}
{"command": "buy", "price": 90.394, "amount": 1.0}
{"command": "sell", "price": 90.394, "amount": 2.2}
{"command": "sell", "price": 90.15, "amount": 3.4}

  1. {"command": "buy", "price": 90.394, "amount": 3.445}

You have nothing to compare it to so

[
  {"command": "buy", "price": 90.394, "amount": 3.445}
]
  1. {"command": "buy", "price": 89.394, "amount": 4.3}

Both buys, different price, just append

[
  {"command": "buy", "price": 90.394, "amount": 3.445},
  {"command": "buy", "price": 89.394, "amount": 4.3}
]
  1. {"command": "buy", "price": 90.15, "amount": 1.305},

Another buy, different price, just append

[
  {"command": "buy", "price": 90.394, "amount": 3.445},
  {"command": "buy", "price": 89.394, "amount": 4.3},
  {"command": "buy", "price": 90.15, "amount": 1.305}
]
  1. {"command": "buy", "price": 90.394, "amount": 1.0},

Buy - with same price as first - combine

[
  {"command": "buy", "price": 90.394, "amount": 4.445},
  {"command": "buy", "price": 89.394, "amount": 4.3},
  {"command": "buy", "price": 90.15, "amount": 1.305}
]
  1. {"command": "sell", "price": 90.394, "amount": 2.2}

Sell - price is lower or equal to first buy - apply

[
  {"command": "buy", "price": 90.394, "amount": 2.245},
  {"command": "buy", "price": 89.394, "amount": 4.3},
  {"command": "buy", "price": 90.15, "amount": 1.305}
]
  1. {"command": "sell", "price": 90.15, "amount": 3.4}

Sell - price is lower or equal to first buy - apply

[
  {"command": "buy", "price": 89.394, "amount": 4.3},
  {"command": "buy", "price": 90.15, "amount": 1.305}
]

Still left with {"command": "sell", "price": 90.15, "amount": 1.155}
Sell - price is lower or equal to last buy - apply

[
  {"command": "buy", "price": 89.394, "amount": 4.3},
  {"command": "buy", "price": 90.15, "amount": 0.150}
]

  • The working/result set consists of two lists: (unmatched) buys and sells
  • Within each those lists items are ordered “by arrival”. The first item in the list arrived before the second item of the list, etc.
  • An exception to that rule occurs when a new item arrives and its price is identical to an item that already exists in the list. The quantity of the item in the list is increased by the quantity of the new item.
  • A new item with a distinct price is simply appended to the list.

The above explains how a buy item can be combined into the buys list and a sell item can be combined into the sells list.

However upon arrival an item has to be applied to the other list first.

  • A new buy item is applied to the sells list
  • A new sell item is applied to the buys list

Applying a buy to the sells list:

  • The sells list is traversed first to last
  • When the buy_price is less than the sell_price we move to the next item in the sells list.
  • When the buy_price is greater than or equal to the sell_price
    • sell_quantity > buy_quantity THEN new_sell_quantity = sell_quantity - buy_quantity for the item in the sells list. The buy is spent. apply is done.
    • sell_quantity < buy_quantity THEN new_buy_quantity = buy_quantity - sell_quantity for the buy item. The sell item is removed from the sells list. With the updated buy item we proceed to the next sell item in the list.
    • otherwise (quantities are equal) THEN remove the sell item from the sells list. The buy is spent. apply is done.
  • Any buy remaining after traversing the entire sells list is then combined into the buys list.

Applying a sell to the buys list: equivalent to the above.

  • A sell is looking for buys where sell_price <= buy_price
  • Any sell remaining after traversing the entire buys list is then combined into the sells list.
1 Like

Let’s step back from the details of the grouping / buy / sell algorithm for a second and look at this more generally. @benonymus you have a clear idea in your head about what the rules are. However you were unclear about how to work with the two lists. Hopefully these responses have provided some insight into how to work with multiple lists.

What I’d recommend at this point is instead of trying to communicate the exact details of the algorithm to people here so that they can write out an exact solution, instead focus on any remaining questions you have about the Elixir mechanics of dealing with these lists, and then take a crack at it on your own. We’ll be here to review code or questions you may have.

3 Likes

After some research I figured out that what I need is a matching/trading engine:
https://medium.com/lgogroup/a-matching-engine-for-our-values-part-1-795a29b400fa

Does anyone have an example?