Learning to dance the Ewan Shuffle

In the broadband team at uSwitch, we're constantly striving to improve and innovate. Part of this work involves automating some of the more boring repetitive tasks the team performs, giving that work to a machine instead. A little while ago we moved to a fully automated approach for deciding the ordering of the products on our tables, taking over from our Performance Marketing Lead, Ewan. Today we're going to focus on a small part of how that works and the code we wrote to solve it.

Once we’ve finished the main process of ordering the table, we want to ensure there aren’t any large blocks from any one retailer. The rules for this, in human terms, are simple:

  1. Ensure that no retailer has more than two products in a row.
  2. Keep the order of the table as undisturbed as possible.

Here's an example of how this might work.

Imagine a collection of products, like so:

[{:rank 1 :retailer_id 1}
 {:rank 2 :retailer_id 1}
 {:rank 3 :retailer_id 1}
 {:rank 4 :retailer_id 2}
 {:rank 5 :retailer_id 2}
 {:rank 6 :retailer_id 3}]

Ewan would previously have reordered this list, using our admin console, to look more like this:

[{:rank 1 :retailer_id 1}
 {:rank 2 :retailer_id 1}
 {:rank 4 :retailer_id 2} ;; This product has moved up
 {:rank 3 :retailer_id 1} ;; This product has moved down
 {:rank 5 :retailer_id 2}
 {:rank 6 :retailer_id 3}]

The ‘rank 4’ product has been bumped up one place to avoid having a block of more than two products from ‘retailer 1’ in a row.

This is what is referred to internally as "The Ewan Shuffle". Below is the Clojure code we've used to implement it:

(defn- splice [result [incoming-head & incoming-tail] overflow]
  (concat result [incoming-head] overflow incoming-tail))

(defn- ewan-reducer [{:keys [result remainder]} incoming]
  (let [[incoming-ok incoming-rejects] (split-at 2 incoming)]
    {:result (splice result incoming-ok remainder)
     :remainder incoming-rejects}))

(defn ewan-shuffle [starting-list]
  (loop [original starting-list]
    (let [result (->> original
                      (partition-by :retailer_id)
                      (reduce ewan-reducer {:result [] :remainder []}))
          new-list (concat (:result result) (:remainder result))]
      (if (= new-list original)
          new-list
          (recur new-list)))))

Let's look at our entry point, ewan-shuffle, and step through the code, using our example list shown above as our arguments.

First up, we can see that ewan-shuffle is a recursive function: It's plausible that in rearranging to break up one grouping, we can create another. So looking at the end of our function, we can see the following:

(if (= new-list original)
    new-list
    (recur new-list))

What this means is that if the result of ewan-shuffle (which is in new-list) is the same as the list was before we shuffled it (in this loop), we've reached the end of our algorithm and we can return that list as completely shuffled. Normally this is a completely unshuffled list as our retailers are always vying for the top position on our table. It's not always that simple, though, so let's have a look at how the shuffle itself works.

We'll look at this in stages, looking at the arguments we can expect to have at each point and why the logic is written the way that it is. Let's start with the outside of our reducer, our let block:

(let [result (->> original
                  (partition-by :retailer_id)
                  (reduce ewan-reducer {:result [] :remainder []}))
      new-list (concat (:result result) (:remainder result))]
      (if (= new-list original)
          new-list
          (recur new-list)))

We've already covered the if above, so let’s just look at the let without it:

(let [result (->> original
                  (partition-by :retailer_id)
                  (reduce ewan-reducer {:result [] :remainder []}))
      new-list (concat (:result result) (:remainder result))])

We take the original list of products and partition them by which retailer they're from (:retailer_id). This looks like so:

(({:rank 1, :retailer_id 1}
  {:rank 2, :retailer_id 1}
  {:rank 3, :retailer_id 1})
 ({:rank 4, :retailer_id 2}
  {:rank 5, :retailer_id 2})
 ({:rank 6, :retailer_id 3}))

Then we pass this partitioned list of products into our reduce function, which has an initial value of a map with an empty list of results and an empty list of "remainders". Now let's have a look at the internals of the reducer to see how we turn our partitioned list into a shuffled one in the reducer:

(defn- ewan-reducer [{:keys [result remainder]} incoming]
  (let [[incoming-ok incoming-rejects] (split-at 2 incoming)]
    {:result (splice result incoming-ok remainder)
     :remainder incoming-rejects}))

We pull the result and remainder out of our accumulator and call our first collection of products (partitioned already by :retailer_id) our incoming. We split this list of incoming products at two. This two is the maximum number of products from any one retailer we want in a row, as mentioned above. Then we splice the result (currently empty) with our (up to) two products from our retailer and our remainder (also currently empty). Here's what's in scope:

[] ;; result
[] ;; remainder

;; incoming-ok
({:rank 1, :retailer_id 1}
 {:rank 2, :retailer_id 1})

;; incoming-rejects
({:rank 3, :retailer_id 1})

So let's take those arguments and look at splice:

(defn- splice [result [incoming-head & incoming-tail] remainder]
  (concat result [incoming-head] remainder incoming-tail))

splice has taken result, incoming-ok, and remainder as its arguments. On our first run-through, this doesn't do very much: It concats together to be ({:rank 1, :retailer_id 1} {:rank 2, :retailer_id 1}) — our original incoming-ok — thanks to the emptiness in remainder.

Returning to our reducer, it's return time: We return our result from splice in result and our leftover product in remainder. Now the reducer runs again, with fresh scope after the let:

;; result
({:rank 1, :retailer_id 1}
 {:rank 2, :retailer_id 1})

;; remainder
({:rank 3, :retailer_id 1})

;; incoming-ok
 ({:rank 4, :retailer_id 2}
  {:rank 5, :retailer_id 2})

[] ;; incoming-rejects

This means when splice runs, its scope is as follows:

;; result
({:rank 1, :retailer_id 1}
 {:rank 2, :retailer_id 1})

;; incoming-head
{:rank 4, :retailer_id 2}

;; incoming-tail
({:rank 5, :retailer_id 2})

;; remainder 
({:rank 3, :retailer_id 1})

We concat these things together, starting with our shuffled, accepted list. We then include the incoming-head in order to break up our list of products we've identified in the last iteration, followed by our remainder, the rest of the block of ‘retailer 1’ products from the last iteration. Finally, we include the incoming-tail. Our return value is:

({:rank 1 :retailer_id 1}
 {:rank 2 :retailer_id 1}
 {:rank 4 :retailer_id 2} ;; This product has moved up
 {:rank 3 :retailer_id 1} ;; This product has moved down
 {:rank 5 :retailer_id 2})

In our final run-through, the last product is added without incident, and our shuffled list is returned! The loop runs once more, checking that in our efforts to clean up existing blocks of a single retailer, we haven't created more. We haven't, so shuffling this new list is a no-op. When the same list is returned from the shuffle, we are done with the loop, and we return our shuffled list of products, ready to be picked up by other systems and applied to our product tables, such as the broadband packages page.

This is one of the many ways that we as devs collaborate with our retailer-facing colleagues to try and take some of the repetitive tasks away from them to allow them to focus on the core of their roles: working closely with our retailers to come up with deals that work best for our customers. I love being able to automate boring jobs like this with a relatively short amount of clojure, and uSwitch does a great job of encouraging us to spot opportunities like these to improve the world around us for ourselves, our colleagues and our customers.