Ordering pages in a coding challenge scrambled my preconceived notion about "natural ordering"

We have a notion that there is a natural order of things.  I'm talking about ordering, and sorting, by convention as a mental aid or for product reasons.  Everyone is familiar with ordering products by weight, pieces by size, and names by alphabetical order.  We are so used to some types of ordering that it seems like the natural way when there is nothing natural about it.

A common example is the "order of assembly", the order of parts installed onto the device.  The reason for the order on the direction sheet may not be immediately obvious.  The order takes into account the ease of assembly or the reliability of putting it in at that point in the cycle.

This caused me to waste over an hour during a recent programming challenge while implementing an arbitrary set of ordering rules. Eventually, I realized that the notion of order is arbitrary and that I could change the standard to fit my problem space. 

Let's go to the programming challenge.

An example from a coding challenge

The left box represents pages extracted from some document.  Each row is a set of pages that need to be in order.  

 For our purposes, we can consider them page identifiers or page codes rather than page numbers.  They aren't the page numbers in our assembly.  

The pages need to be ordered based on the rule set on the right.  The two numbers represent the order two pages should be placed.  The right two-column image represents our ordering rules".  

All of the pages on the left can be ordered with these rules.  The rules are good enough even if they feel arbitrary because the individual numbers appear different numbers of times in the list on the right. 

This problem made my head hurt.  I was going to have to write some data-walking thing that I could use to, somehow, cross product against the page numbers to even validate the page order let alone reorder them.  My first attempt was probably 30 lines of quasi-custom looping code.

For those keeping score:  Three of the above page sets are out of order. Their correct, order, based on the rule table, is shown to the right.

Sorting - with our own rules

This is still a sorting problem.  We just need to change the rules around sorting.  We can't use some built-in sorting module algorithm.  We can use the idea of sorting and how sorting is implemented using a Comparable.  Basically sorting works by continually comparing two elements with a function.  We tend to ignore this when sorting numbers, dates, or strings because the comparable implementations are well-known.

Our software library already knows how to sort a List or Collection using a comparable.  We just need to provide that comparable implementation, here seen as compareViaTransitions().  The sort then handles everything for us.

The following code shows a 'comparable' called compareViaTransitions.  It accepts two values and the rule table. The function returns -1 if a is less than b within our rule table.  It returns +1 if a is greater than b per the table.  Otherwise, we don't have a rule so we say they are of equal rank or weight. compareToTransitions is compatible with our list sorter and can be plugged into our sort invocation.

AI - gratuitous addition for SEO

AI doesn't have any preconceived notions, or really any notions.  It just bases its answers on previous answers that it can combine in new, novel, and ridiculous ways.  We may see situations where AI creates a new natural order within some domains.

Wrapping up

It is easy to view sorting as something natural, or beyond questioning.  This makes sense because the build of our ordering happens within well-known domains like distance, size, weight, or lexical order. Those standards are useful in standard situations. 

Other situations may require a different kind of order.  We can probably handle that in systems and processes with some type of custom sorter or comparator.

Video

There is also a YouTube short version of this video that does not cover programming

Revision History