RewriteRule rewriting legacy slugs

RewriteRule rewriting legacy slugs

I'm working on updating a website, moving from Drupal to Wordpress MS. One
of the big challenges is taking all of our old URLs that have been indexed
by google, and making them a lot prettier and smaller.
The old structure looks something like this:
<domain>/CA/<location_name>-superflous-data-slapped-at-the-end
The catch is that often times <location_name> contains hyphen characters
as well that we want to strip.
The new structure should look like
<domain>/<hyphen-stripped-location-name> Where we've trimmed off the state
abbreviation, the superflouous data, and we've stripped out the hyphens
from our location name.
Just to be clear I'd like to catch forward from the old URLs, whenever
they're requested, to these new pretty URLs that already exist.
I have a beginner's understanding of rewrite rules and my regex isn't very
good either. I have no idea where to begin, any help is greatly
appreciated!