So it's sorted alphabetically first, when the sum is equal. It's somewhat cheesy but it works.

Didn't even think of a graph. Clever and efficient solution.
I used a bunch of folds that would essentially reorder the word, given a few simple rules.

I just tested and it does result in [West, West]. Note that because foldr is lazy, all collapse function applications will be delayed until the start element is reached.

Kind of like this:

collapse North (collapse East (collapse West (collapse South (collapse West (collapse West [])))))
collapse North (collapse East (collapse West (collapse South (collapse West [West]))))
collapse North (collapse East (collapse West (collapse South [West, West])))
collapse North (collapse East (collapse West [South, West, West]))
collapse North (collapse East [West, South, West, West]) -- collapse East (West:xs) = xs
collapse North [South, West, West] -- collapse North (South:xs) = xs
[West, West]

Since it's folding from the right side (it's foldr) it goes backwards so it's reducing correctly.
Very clever in my opinion. A good example of how to use foldr properly.