Movie Ranking With Sortable.js And Kendall Tau Distance
I've always been quite comfortable with JavaScript; but, I've also always had a huge blind-spot when it comes to drag-and-drop user experiences. Meaning, I never felt confident that I could code them in a way that was generalizable and extensible. And so, I've kind of avoided them. At work, however, we use a Bootstrap 5 template (Phoenix) that comes with the Sortable.js library. Sortable.js makes it effortless to create drag-and-drop, sortable lists. And, I think it's time that I give up on the notion that I can code this by myself; and just rely on a battle-hardened library like this one.
Run this demo in my JavaScript Demos project on GitHub.
View this code in my JavaScript Demos project on GitHub.
Applying Sortable.js to an application is fairly straightforward: you just initialize the Sortable() constructor with a Document Object Model (DOM) node and some settings:
new Sortable(
listNode,
{
direction: "vertical",
animation: 0,
onUpdate: ( event ) => {
console.log( "Sort updated!" );
}
}
);
This simple bit of code will make the listNode element sortable (its children become the sortable items within the list). Of course, there are many more settings that can be used to customize the behavior; but, I'm still learning how it all works.
And, as a learning context for Sortable.js, I thought it would be fun to create a demo app in which two lists of movie rankings could be compared for romantic compatibility. Meaning, the closer the two lists of romantic comedies are in relative ranking, the more likely it is that the curators of said lists could fall in love and life happily ever after.
Aside: this is just for fun - there's no science behind this.
So, in addition to sorting the lists, I needed a way to compare the similarities of the two lists. For this, ChatGPT suggested that I look into the Kendall Tau Distance algorithm, which tallies the number of "discordant pairs" in each list.
Basically, Kendall Tau compares all of the distinct pairings of elements (A,B) in a list; and if A comes before B, it's assigned -1; and, if A comes after B, it's assigned 1. The algorithm then compares the rankings within each list and sees how many pairs result in the same assignment; and how many pairs result in a "discordant" assignment.
I won't go into any more detail here since this was really just a code kata for myself. But, here's the (truncated) HTML for my exploration. It consists of two lists of movie titles that rendered side-by-side using CSS Flexbox:
<body x-data="App" @popstate.window="handlePopstate()">
<h1>
Movie Ranking With Sortable.js And Kendall Tau Distance
</h1>
<p>
Check your movie preference compatibility with others:
</p>
<div class="panels">
<ul x-ref="listOneNode">
<template x-for="id in listOne" :key="randomKeyBecauseXForBug()">
<li :data-id="id" x-text="titles[ id ].name">
<!-- Populated via x-text. -->
</li>
</template>
</ul>
<mark x-text="similarity">
0%
</mark>
<ul x-ref="listTwoNode">
<template x-for="id in listTwo" :key="randomKeyBecauseXForBug()">
<li :data-id="id" x-text="titles[ id ].name">
<!-- Populated via x-text. -->
</li>
</template>
</ul>
</div>
<p class="resets">
<button @click="resetList( 'listOne' )">
Reset List One
</button>
<button @click="syncRight()">
Sync →
</button>
<button @click="resetList( 'listTwo' )">
Reset List Two
</button>
</p>
</body>
</html>
And, here's the App() code for the Alpine.js component that powers the demo. The code works by storing the id of each movie in the DOM; then, the Sortable.js library allows the DOM nodes to be sorted; and, we can read the id back out of the DOM once the sorting operations are completed.
The sorting of id values are pushed into the URL (via the URL fragment) such that you can compare the rankings with your friends and lovers.
function App() {
// Note: the "id" value matches the "index" value. This fact will be leveraged when
// reading the DOM for the sorted list of IDs.
var id = -1;
var titles = [
{ id: ++id, name: "10 Things I Hate About You" },
{ id: ++id, name: "50 First Dates" },
{ id: ++id, name: "Annie Hall" },
{ id: ++id, name: "Bridge Jones's Diary" },
{ id: ++id, name: "Crazy Rich Asians" },
{ id: ++id, name: "Dave" },
{ id: ++id, name: "Defending Your Life" },
{ id: ++id, name: "Dirty Dancing" },
{ id: ++id, name: "Love Actually" },
{ id: ++id, name: "Midnight In Paris" },
{ id: ++id, name: "Moonstruck" },
{ id: ++id, name: "Notting Hill" },
{ id: ++id, name: "Pretty Woman" },
{ id: ++id, name: "Princess Bride" },
{ id: ++id, name: "Say Anything" },
{ id: ++id, name: "Sleepless In Seattle" },
{ id: ++id, name: "Tommy Boy" },
{ id: ++id, name: "Wedding Singer" },
{ id: ++id, name: "What About Bob" },
{ id: ++id, name: "When Harry Met Sally" },
{ id: ++id, name: "You've Got Mail" },
];
// ------------------------------------------------------------------------------- //
// ------------------------------------------------------------------------------- //
return {
// Public properties.
listOne: null,
listTwo: null,
similarity: "100",
titles,
// Private properties.
distance: 0,
sortableOne: null,
sortableTwo: null,
coreIds: null,
// Life-cycle methods.
init,
// Public methods.
handlePopstate,
randomKeyBecauseXForBug,
resetList,
syncRight,
// Private methods.
compareRankings,
getSortedListsFromDom,
loadFromhash,
persistToHash,
};
// ---
// LIFE-CYCLE METHODS.
// ---
/**
* I initialize the component.
*/
function init() {
// Keep track of the core list of title IDs so that we can use this in the default
// list assignment as well as in the hash parsing.
this.coreIds = this.titles.map( title => title.id );
// By default, set each list of title IDs to start with the core list. This will
// then be overridden, as needed, by the URL fragment.
this.listOne = this.coreIds.slice();
this.listTwo = this.coreIds.slice();
// Override the lists (if possible) using the URL fragment.
this.loadFromhash();
this.compareRankings();
var sortableOptions = {
direction: "vertical",
swapThreshold: 0.8, // Overlap required to trigger move (0...1).
animation: 0,
onUpdate: ( event ) => {
this.getSortedListsFromDom( event );
this.compareRankings();
this.persistToHash();
}
};
// Enable sorting on the DOM lists.
this.sortableOne = new Sortable( this.$refs.listOneNode, sortableOptions );
this.sortableTwo = new Sortable( this.$refs.listTwoNode, sortableOptions );
}
// ---
// PUBLIC METHODS.
// ---
/**
* I handle the history popState event, and sync the URL state down into the app state.
*/
function handlePopstate() {
this.loadFromhash();
this.compareRankings();
}
/**
* There's a BUG(ish) in the way that X-For handles DOM-initiated re-sorting. As such,
* we are working around it by providing a random key to the DOM id. This will create
* DOM churn; but, it is what it is.
*
* Read more: https://github.com/alpinejs/alpine/discussions/4157
*/
function randomKeyBecauseXForBug() {
return Math.floor( Math.random() * 999999 );
}
/**
* I reset the selected list to the original titles order.
*/
function resetList( whichList ) {
this[ whichList ] = this.coreIds.slice();
this.compareRankings();
this.persistToHash();
}
/**
* I sync the first list into the second list to give the user a matching base from
* which to start customizing the sort.
*/
function syncRight() {
this.listTwo = this.listOne.slice();
this.compareRankings();
this.persistToHash();
}
// ---
// PRIVATE METHODS.
// ---
/**
* I compute the distance and similarity of the two lists.
*/
function compareRankings() {
// Calculate the Kendall Tau Distance between the two list of titles.
this.distance = kendallTauDistance( this.listOne, this.listTwo );
// Convert the Kendall Tau Distance to something more human friendly.
this.similarity = ( ( 1 - this.distance ) * 100 ).toFixed( 1 );
}
/**
* I read the list of IDs back out of the DOM (via the Sortable proxy).
*/
function getSortedListsFromDom( event ) {
// Our list DOM is rendered by Alpine.js (via the x-for directive); but, we're
// allowing the list to be updated arbitrarily by Sortable.js. Once the sorting
// operation is done, we need to read the state of the DOM back into the state of
// Alpine.js so that the x-for attribute remains in a predictable state.
// --
// Note: there's a bug(ish) in the [x-for] attribute in the way it keeps track of
// keys internally. We get around this by assigning random keys in the DOM.
this.listOne = this.sortableOne.toArray();
this.listTwo = this.sortableTwo.toArray();
}
/**
* I override the rankings if the values are available in the URL fragment.
*/
function loadFromhash() {
var rankings = location.hash
.slice( 1 )
// Split fragment into two comma-delimited lists.
.split( ":" )
// Map each comma-delimited list onto a set of IDs.
.map(
( rankList ) => {
return rankList
// Split each comma-delimited list into a set of IDs.
.split( "," )
// Make sure we didn't have any incorrect mappings.
.filter( id => titles[ id ] )
;
}
)
;
// We've already set up default values for the lists to use the core set of IDs.
// We only want to now override these lists if they have the same length as the
// defaults. This way, we don't have to do any more validation on the URL.
if ( rankings[ 0 ]?.length === this.listOne.length ) {
this.listOne = rankings[ 0 ];
}
if ( rankings[ 1 ]?.length === this.listTwo.length ) {
this.listTwo = rankings[ 1 ];
}
}
/**
* I persist the current ranks to the URL fragment.
*/
function persistToHash() {
var flattenedOne = this.listOne.join( "," );
var flattenedTwo = this.listTwo.join( "," );
var flattenedCore = this.coreIds.join( "," );
// Vanity: if either of the lists matches the original list of titles, just omit
// it from the URL. This has no functional bearing - it just makes the URL look a
// little bit nicer.
if ( flattenedOne === flattenedCore ) flattenedOne = "";
if ( flattenedTwo === flattenedCore ) flattenedTwo = "";
document.title = `Lists are a ${ this.similarity }% match!`;
history.pushState( {}, null, `#${ flattenedOne }:${ flattenedTwo }` );
}
// ---
// HELPER METHODS (ie, pure functions, not on THIS scope).
// ---
/**
* I return an index of the given array in which the value maps to the index of the
* value within the collection.
*/
function arrayReflectIndex( collection ) {
var index = Object.create( null );
collection.forEach(
( element, i ) => {
index[ element ] = i;
}
);
return index;
}
/**
* I calculate the Kendall Tau Distance for the two lists. Returns a decimal value
* between 0 (fully identical) and 1 (fully reversed).
*/
function kendallTauDistance( listOne, listTwo ) {
// We're going to be counting the number of (A,B) pairs that are in a different
// relative order in the two lists.
var size = listOne.length;
var totalPairs = ( size * ( size - 1 ) / 2 );
var discordantPairs = 0;
// As we iterate over the FIRST list, we'll need to check the corresponding rank
// of the same items in the SECOND list. To make this efficient, let's calculate
// the index-by-value for all elements in the second list. We don't need to do
// this for the first list since we'll be iterating over the first list in order.
var listTwoIndex = arrayReflectIndex( listTwo );
// Iterate over the FIRST list using a nested, forward looking loop. The outer
// loop will iterate over the entirety of the first list.
for ( var a = 0 ; a < ( size - 1 ) ; a++ ) {
// ... the inner loop only needs to iterate from [a...] since we're looking
// for unique pairs of elements. If the inner loop started from 0, we'd be
// counting the same pairs more than once (since (A,B) and (B,A) are
// considered the same pair for this algorithm).
for ( var b = ( a + 1 ) ; b < size ; b++ ) {
// Get the elements at the current iteration indices.
var elementA = listOne[ a ];
var elementB = listOne[ b ];
// Since our nested loop is always exploring elements in a forward-looking
// order, we know that the ranking of the elements in the first list is
// always -1. We only need to calculate the corresponding rank in the
// second list.
var rankOne = -1;
var rankTwo = Math.sign( listTwoIndex[ elementA ] - listTwoIndex[ elementB ] );
if ( rankTwo != rankOne ) {
discordantPairs++;
}
}
}
return ( discordantPairs / totalPairs );
}
}
Anyway, this was just for fun to help me learn about Sortable.js. And, you can now see how romantically compatible we are - ooh la la!
Want to use code from this post? Check out the license.
Reader Comments
For the record, never once have I wondered how romantically compatible we are 😜
I'm planning to check out Phoenix through. Would you recommend?
I also think you could build the next big dating app from the idea of movie, food, book...Compatability. It couldn't be worse than all the sciency apps that are popular now.
@Chris,
How dare you! 😆 as far as Phoenix - it seems pretty solid. This is my first Boostrap project, though, at a new job, in a new business sector, with a new ColdFusion framework. I feel like I'm drinking from 8 fire hoses at once! 🔥
It would actually be great to pick your brain about Wheels at some point. I'm feeling a little lost with some of the organization of files; and when I should maybe start to use a "service model" or something to that effect.
@Ben Nadel,
You're super smart to want a service model. Back when I first started, I read some obscure article about how someone integrated services into CFWheels, I did it, and now I cannot even begin to remember how/what I did to make it happen. But I have a folder
/serviceswhich contains several CFCs that I can now use in a very CFWheelsy way. For example...service('timezone').castToUTC(this.startDate, this.timezone)I think it's super cool, but I wish CFWheels had a more native way to do this. Maybe they do now and I'm just not aware.
I'm happy to chat about CFWheels anytime, but if you can get a hold of Tom King, Per Djurner, Anthony Petruzzi, or Peter Amiri. Those are the guys you want to chat with. And I'd be willing to bet they'd be more than happy to chat with you, especially given how much visibility you're likely to bring to the framework.
@Chris,
I actually work for Peter Amiri right now :D re: Services, I was thinking about creating a global helper function called
service()that would essentially look up a table-less model class, but prefix it with an implicit folder name. Basically, instead of doing:model( "services.Timezone" )... I would do something like:
service( "Timezone" )... which would be doing the same thing behind the scenes. So, it would be more about convention than anything technical. I think there might also be a
controller()function (which is primarily used for testing in Wheels, I think) that might allow me to do the same thing.Basically, I want all the class caching and function injection, so I think I need to piggy-back on the same mechanics, just name them something differently to provide more clear intention.
@Ben Nadel,
With Peter Amiri at your disposal, you're set! Maybe you can even sway the add
services()as a blessed part of the framework. I think it would be a great add..and much needed in my opinion. I imagine the reason it has not already been added is because (maybe) it's not part of the Ruby on Rails methodology, which I know they try to follow closely. I never actually used RoR so I'm not sure about that.@Chris,
Here's what I came up with: www.bennadel.com/blog/4819-creating-service-objects-in-the-cfwheels-coldfusion-framework.htm
In the end, it was just a few lines of code, really. Hopefully this is on the right track.
Post A Comment — ❤️ I'd Love To Hear From You! ❤️
Post a Comment →