mcilroy vs knuth

souffle-tracks-reduction.md

mcilroy vs knuth

as per our discussion last night:

original, optimized code

def remove_tracks_from_collections(collections_map, tracks_to_remove, collection_type):
    """From a dictionary mapping collection ids to tracks in the collection, remove all tracks
    in tracks_to_remove from the collection to which the track belongs.
    Notes:
    - this is a helper function for shuffle_tracks, and it is assumed that each track
    belongs to one of the collection ids in the collection_map. separated for testing.
    Args:
        collections_map: Dictionary mapping collection ids to Track namedtuples
        tracks_to_remove: List of Track namedtuples
        collection_type: Type of collection: 'artist' or 'album'
    Returns:
        Dictionary mapping collection ids to Track namedtuples
    Side effects:
        collections_map is filtered as-is rather than copied for the sake of efficiency
    """
    for track in tracks_to_remove:
        collection_id = track._asdict()[collection_type]
        collection_tracks = collections_map[collection_id]
        try:
            collection_tracks.remove(track)
        except KeyError:
            pass

    return collections_map

def shuffle_tracks(tracks, shuffle_by, spotify):
    """Shuffle a list of Track namedtuples by artist or album, in which each track is shuffled
    out with another track on that track's artist or album. If there are no other tracks on a
    track's collection, the track will not be shuffled. Two tracks by the same artist or on
    the same album will not be shuffled to each other, nor will they be shuffled to the same other
    track in that collection. Thus, in the case that a playlist contains all of the tracks on an
    album, and the tracks are requested to be shuffled by album, no track will be shuffled, as there
    is nothing to shuffle to that doesn't exist on the playlist already.
    Args:
        tracks: List of Track namedtuples
        shuffle_by: What collection the track should be shuffled by: 'artist' or 'album'
        spotify: Spotify client
    Returns:
        A list of track ids of the shuffled tracks
    Raises:
        - SpotifyException if an error occurs with the spotify client
    """
    try:
        collection_ids = {track._asdict()[shuffle_by] for track in tracks}
    except KeyError:
        raise SouffleParameterError('Invalid shuffle_by type "%s".', shuffle_by)

    # For each collection (album or arist) get all of the tracks on that collection
    if shuffle_by == 'artist':
        collection_to_tracks_map = get_artist_to_tracks_map(collection_ids, spotify)
    elif shuffle_by == 'album':
        collection_to_tracks_map = get_album_to_tracks_map(collection_ids, spotify)

    # Remove all original tracks from the collections to tracks map to avoid duplicates
    collection_to_tracks_map = remove_tracks_from_collections(
        collection_to_tracks_map,
        tracks,
        collection_type=shuffle_by
    )

    # Shuffle each track
    shuffled_tracks = []
    for track in tracks:
        collection_id = track._asdict()[shuffle_by]
        collection_tracks = collection_to_tracks_map[collection_id]


        # Nothing to shuffle with
        if not collection_tracks:
            shuffled_tracks.append(track)

        # Otherwise, shuffle track with another track in the collection. Remove the
        # track from the collection afterwards to avoid duplication.
        else:
            shuffled_track = random.sample(collection_tracks, k=1)[0]
            shuffled_tracks.append(shuffled_track)
            collection_tracks.remove(shuffled_track)

    return shuffled_tracks

new version

(which I haven't yet tested, but I imagine is at least a tweak away from doing the same thing, albeit slower)

def souffle_tracks(tracks, track_collections):
    """Souffle a list of tracks using track_collections, a map of tracks to the set of tracks in
    each top-level track's collection.
    """
    souffled_tracks = []
    for track in tracks:
        collection_tracks = track_collections[track]
        valid_tracks = collection_tracks - {track} - set(souffled_tracks)
        souffled_track = random.sample(valid_tracks, 1)[0] if valid_tracks else track
        souffled_tracks.append(souffled_track)

    return souffled_tracks

An idea - it's in js because it was easier for me to express, but I could look into reduce in Python:

const get_difference = (itemsA, itemsB) => itemsA.filter(e => !itemsB.includes(e));

const select_random_item = (items) => items[Math.floor(Math.random() * items.length)];
  
function souffle_tracks (tracks, related_tracks_by_track) {
  return tracks.reduce((acc, track) => {
    const related_tracks = related_tracks_by_track[track];
    const used_tracks = [ ...new Set(acc) ].concat([ track ]);
    const valid_tracks = get_difference(related_tracks, used_tracks);
    const souffled_track = select_random_item(valid_tracks) || track;
    return [ ...acc, souffled_track ];
  }, []);
}

And another variant:

function souffle_tracks (tracks, related_tracks_by_track) {
  return tracks
    .map(track => ({ track, related_tracks: related_tracks_by_track[track] }))
    .reduce((acc, { track, related_tracks }) => {
      const used_tracks = [ ...new Set(acc) ].concat([ track ]);
      const valid_tracks = get_difference(related_tracks, used_tracks);
      const souffled_track = select_random_item(valid_tracks) || track;
      return [ ...acc, souffled_track ];
    }, []);
}

And then the last 2 hours got weird:

import R from 'ramda'; // http://ramdajs.com

const get_random_index = num => Math.floor(Math.random() * num);
const get_random_item = items => items[get_random_index(items.length)];

const souffle_track = (souffled_tracks, { track, related_tracks }) => {
  return R.pipe(
    R.uniq,
    R.append(track),
    R.difference(related_tracks),
    R.either(get_random_item, () => track),
    souffled_track => R.append(souffled_track, souffled_tracks)
  )(souffled_tracks);
};

function souffle_tracks (tracks, related_tracks_by_track) {
  return R.pipe(
    R.map((track) => ({
      track,
      related_tracks: related_tracks_by_track[track],
    })),
    R.reduce(souffle_track, []),
  )(tracks);
}

And because I'm nuts, here's a Ramda version I actually like:

import R from 'ramda'; // http://ramdajs.com

const get_random_index = num => Math.floor(Math.random() * num);
const get_random_item = items => items[get_random_index(items.length)];

const souffle_track = (track, related_tracks, souffled_tracks) => {
  const used_tracks = [ ...souffled_tracks, track ];
  return R.pipe(
    ([ related, used ]) => R.difference(related, used),
    valid_tracks => get_random_item(valid_tracks) || track,
  )([ related_tracks, used_tracks ]);
};

function souffle_tracks (tracks, related_tracks_by_track) {
  return R.pipe(
    R.map(track => [ track, related_tracks_by_track[track] ]),
    R.reduce((acc, [ track, related_tracks ]) => [
      ...acc,
      souffle_track(track, related_tracks, acc),
    ], [])
  )(tracks);
}