Custom permalink structure: /%custom-post-type%/%custom-taxonomy%/%post-name%/

/**
 * Tell WordPress how to interpret our movies URL structure
 *
 * @param array $rules Existing rewrite rules
 * @return array
 */
function cww_add_rewrite_rules( $rules ) {
  $new = array();
  $new['movies/([^/]+)/(.+)/?$'] = 'index.php?movies=$matches[2]';
  $new['movies/(.+)/?$'] = 'index.php?genre=$matches[1]';

  return array_merge( $new, $rules ); // Ensure our rules come first
}
add_filter( 'rewrite_rules_array', 'cww_add_rewrite_rules' );

/**
 * Handle the '%genre%' URL placeholder
 *
 * @param str $link The link to the post
 * @param WP_Post object $post The post object
 * @return str
 */
function cww_filter_post_type_link( $link, $post ) {
  if ( $post->post_type == 'movies' ) {
    if ( $cats = get_the_terms( $post->ID, 'genre' ) ) {
      $link = str_replace( '%genre%', current( $cats )->slug, $link );
    }
  }
  return $link;
}
add_filter( 'post_type_link', 'cww_filter_post_type_link', 10, 2 );

// Used for registering movies custom post type
$post_type_args = array(
  'rewrite' => array(
    'slug' => 'movies/%genre%',
    'with_front' => true
  )
);

// Some of the args being passed to register_taxonomy() for 'genre'
$taxonomy_args = array(
  'rewrite' => array(
    'slug' => 'genre',
    'with_front' => true
  )
);