ndac_todoroki

How to implement complexed custom sort?

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!

11 comments

#lists #structs #sort

0 4572 11

2018-11-19 20:55:54 UTC

Marked As Solved

Qqwy

TypeCheck Core Team

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

Post #6

Also Liked

kokolegorille

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

Post #1

japplegame

My AVLTree implementation with custom sorting function: GitHub - japplegame/avl_tree: Pure Elixir AVL tree implementation · GitHub

Post #2

Qqwy

TypeCheck Core Team

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

Post #10

Last Post!

OvermindDL1

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. ^.^

Post #11