How to implement complexed custom sort?

Questions / Help
, ,
1

Thinking of implementing a Chess game in Elixir, I created a module which will represent a chess piece as a struct.

defmodule Piece do
  alias __MODULE__, as: Piece
  @piece_types ~w(King Queen Rook Bishop Knight Pawn)a
  @type type :: :King | :Queen | :Rook | :Bishop | :Knight | :Pawn

  defstruct [:type]
  @type t :: %Piece{ type: type() }

  defguard is_type(piece_type) when piece_type in @piece_types
      
  def new(type) when is_type(type), do: %Piece{type: type}
end

then there is a struct that represents an active piece:

defmodule Fighter do
  alias __MODULE__, as: Fighter
  @type owner ::  :player | :opponent
  
  defstruct [ :owner, :piece, :position ]
  @type t :: %Fighter{ owner: owner(), piece: Piece.t(), position: BoardCoordinate.t }
end

So I have a List of Fighters when the game starts. I came to a circumstance where I want to sort the Fighters.
The result should be sorted first by fighter.owner, then by fighter.piece.type, and then by fighter.position, so it will be

  • my king
  • my queen
    …
  • my most left-top pawn
  • my secondly left-top pawn
    …
  • opponent’s king
  • opponent’s queen
    …

and so on. Can I perform this on a single custom sort? (Like performing fighters |> Fighter.sort())?
For that I thought setting a default sort algorism for each struct type could be a simple way, but I couldn’t have sorted(!) this out.

Any help and thoughts are welcomed!

2

Not that it helps with your sorting question, but I have done two chess libs in Elixir…

The second is a translated from Erlang and generates all possible moves. Maybe it helps

2 Likes
3

My AVLTree implementation with custom sorting function: https://github.com/japplegame/avl_tree

2 Likes
4

Thanks, but this is just an example for a more generic question… Sorting your nested structs in ways you desire to.
But I’m gonna have fun with those repos! :+1:

5

Giving a custom function to (e.g. Enum.sort/3) was what I first considered, but it doesn’t help when you want to sort nested structs… :disappointed:
But anyway, I like your AVLTree! It is very simple. Thanks!

6

And I’ve kind of came up with some way: implementing a custom sort Protocol may do.

defprotocol ChessSorter do
  @spec asc(any, any) :: boolean
  def asc(_, _)
end

defmodule Coordinate do
  defstruct [:x, :y]

  defimpl ChessSorter, for: __MODULE__ do
    def asc(%{x: x1, y: y1}, %{x: x2, y: y2}) when x1 == x2, do: y1 <= y2
    def asc(%{x: x1}, %{x: x2}), x1 <= x2
  end
end

defmodule Piece do
  defstruct [:type]

  defimpl ChessSorter, for: __MODULE__ do
    @types %{
      Pawn => 1,
      Knight => 2,
      Bishop => 3,
      Rook => 4,
      Queen => 5,
      King => 6,
    }

    def asc(%{type: t1}, %{tpe: t2}), do: @types[t1] <= @types[t2]
  end
end

defmodule Fighter
  defstruct [ :owner, :piece, :position ]

  defimpl ChessSorter, for: __MODULE__ do
    def asc(
          %{owner: o1, piece: p2, position: pos1},
          %{owner: o2, piece: p2, position: pos2}
        )
        when o1 == o2 and p1 == p2,
        do: ChessSorter.asc(pos1, pos2)

    def asc(%{owner: o1, piece: p2}, %{owner: o2, piece: p2}) when o1 == o2,
      do: ChessSorter.asc(p1, p2)

    def asc(%{owner: :opponent}, %{owner: :player}), do: false
    def asc(%{owner: :player}, %{owner: :opponent}), do: true
  end
end

And then : fighters |> Enum.sort(&ChessSorter.asc/2). So this recursively does sorting down to basic Kernel.<= s.

But I am afraid this may be veery slow. :disappointed: Is it?

7

Elixir’s sorting function is stable. This means that you can first sort the whole list of fighters on the least-important condition, then on the second-least important condition , etc. and finally on the most important condtion, and they will end up in the order you’d expect.

So in your case

fighters
|> Enum.sort_by(fn fighter -> fighter.position end)
|> Enum.sort_by(fn fighter -> fighter.piece.type end)
|> Enum.sort_by(fn fighter -> fighter.owner end)

And, by taking advantage of the fact that tuples are ordered elementwise (we look at the next element only if the current element is equal), we could write it like this instead as well:

fighters
|> Enum.sort_by(fn fighter -> {fighter.owner, fighter.piece.type, fighter.position} end)

However, this will not give the answer you’d like yet, because many things are represented by symbols, which by default are sorted alphabetically (whereas you’d like the given order King > Queen > Bishop > ... and player > opponent. The translation functions you wrote for your custom sorter would indeed be a solution to this.

It is possible to automate that a little, by creating a map of the numerically ordered equivalents (like piece_type_ordering = piece_types |> Enum.with_index |> Enum.into(%{})), which you’d want to generate at compile time, so you can just write a function then that will turn a given thing into their ordering.

I think a protocol like the following might make sense:

defprotocol Orderable
  @doc """ 
   Turns the given structure into something that can be compared and sorted in the desired order.
   """
  @spec orderable(any) :: any
  orderable(_)
end

whose implementation for e.g. %Piece would simply return the number that is stored for the given type’s symbol key.

And for %Fighter, it would return e.g.

def orderable(fighter)
  import Orderable
  {orderable(fighter.owner), orderable(fighter.piece), fighter.position}
end
5 Likes
8

Wow, this is amazing how minimum the code could be. It was a whole new study for me. Thanks for the information!!

1 Like
9

With Orderable protocol you also can use AVLTree like this:

AVLTree.new(fn a, b -> Orderable.orderable(a) < Orderable.orderable(b))

All inserted elements will be automatically sorted.

1 Like
10

@japplegame Interesting! I wrote a library a while back to build and work with Priority Queues called prioqueue, which abstracts away the implementation details of how this queue is maintained, and lets you plug in your own. I think making an AVLTree implementation would be a great idea! When will you upload AVLTree to Hex.PM? :slight_smile:

@ndac_todoroki Glad to be able to help. I guess the Orderable protocol could be wrapped in a library, since I think it is rather common to want to do this kind of stuff. We might even provide built-in implementations for common ordered enumerables that call Orderable.orderable for all their contained elements… Let me conjure up something! :smiley:

1 Like
11

Done! The orderable library has been built, tested, documented and published.

2 Likes
12

Just because I find it fun, this is why I don’t like Elixir’s protocol implementation… ^.^;
I implemented the same trivial protocol implementation with protocol_ex with full optimizations enabled (though not bothered setting priority of callbacks or anything, it’s almost a 1-to-1 copy of the orderable protocol and implementations) and this is the benchmark using the Rating object from the readme of that project (yes there is a test to ensure they generate identical output for identical input) in a Tuple of 1000 Ratings:

╰─➤  mix bench ordered
Compiling 1 file (.ex)
Operating System: Linux"
CPU Information: AMD Phenom(tm) II X6 1090T Processor
Number of Available Cores: 6
Available memory: 15.67 GB
Elixir 1.7.4
Erlang 21.1.1

Benchmark suite executing with the following configuration:
warmup: 5 s
time: 5 s
memory time: 0 μs
parallel: 1
inputs: tuples
Estimated total run time: 20 s


Benchmarking Orderable with input tuples...
Benchmarking OrderableEx with input tuples...

##### With input tuples #####
Name                  ips        average  deviation         median         99th %
OrderableEx        2.67 K      375.12 μs    ±12.98%         361 μs         459 μs
Orderable          1.22 K      821.59 μs     ±9.05%         803 μs      993.54 μs

Comparison: 
OrderableEx        2.67 K
Orderable          1.22 K - 2.19x slower

Elixir protocols could have such a more efficient implementation… ^.^;

With some slight optimizations of Rating itself (the rating_index part to be specific, using proper constant mappings instead of a map) I got them both up to:

##### With input tuples #####
Name                  ips        average  deviation         median         99th %
OrderableEx        3.03 K      330.57 μs    ±16.23%         313 μs         427 μs
Orderable          1.32 K      757.94 μs    ±13.54%         742 μs         946 μs

Comparison: 
OrderableEx        3.03 K
Orderable          1.32 K - 2.29x slower

I did multiple runs of each benchmark and always got the same instruction counts and ratio, no real variance.

And if you think that’s fast, you should see my ‘Access’ replacement. ^.^

1 Like