For all of them --- not guaranteed that you'll be able to achieve the optimum..
My solution is basically a greedy algorithm: Make a list of (artist,
tracks) pairs, and sort descending by len(tracks). Then iteratively:
1. Take the next track from the first artist on the list.
2. Move that artist down to position total/len(tracks).
Repeat until all tracks have been selected :-)
Generally it works well, except at the end of the playlist sometimes.
See attachment for my implementation. (uses mmpython, which you can
find on the net)
--
John.
On 21/10/05, Liam Clarke <[EMAIL PROTECTED]> wrote:
> Hmmm, that's interesting.
>
> Obviously, for a playlist with x songs, and n songs by a particular
> artist, the optimum separation between songs would be x/n.
>
> Which would be easy for one artist, but for all of them?
>
> Hmm...
>
> Let's see. First off, let's discount all the artists with only one
> song, they can be the space filler.
>
> Next, you'd have to work out optimal spacing for each artist's songs,
> and try to insert them into a list. If that slot was already taken,
> you'd want to look down and up the list for the next free space,
> choosing whichever maximised the distance. And you'd have to treat
> x[5] - 10 as x[96] for a list x where len(x) == 100.
>
> Err, there's got to be an algorithm for this sorta stuff, but I can't
> understand the big words when I google it... what's your solution?
>
> On 10/21/05, John Fouhy <[EMAIL PROTECTED]> wrote:
> > Hmm, neat. I don't have any feedback for you on your code, but since
> > you're working with this sort of thing, I have a puzzle for you:
> >
> > Suppose you have a collection of MP3 files. You want to build a
> > random playlist, subject to the condition that tracks by the same
> > artist are as far apart as possible. You can assume you have the
> > track / artist data in any structure you like. How would you do this?
> >
> > (I have a solution, but I don't think it is optimal. In fact, I'm not
> > sure how to actually define "optimal" here... And so I am interested
> > in how other people would solve this problem :-) )
> >
> > --
> > John.
import os
import mmpython
import random
from math import log, ceil
from itertools import *
def getFiles(directory):
""" Walk directory under root, getting a list of all regular files. """
res = []
for root, dirs, files in os.walk(directory):
for f in files:
res.append(os.path.join(root, f))
return res
def getMusic(files):
""" Filter a list of files for music files. """
return [f for f in files if os.path.splitext(f)[1][1:].lower() in ('mp3',
'ogg')]
def addInfo(files):
""" Add tag info to a list of files. """
return [(mmpython.parse(f), f) for f in files]
def getMusicByArtist(musicInfo):
""" Process a list of (taginfo, filename) pairs into a dict of artist |->
filename. """
files = {}
errors = []
for info, filename in musicInfo:
if not info:
errors.append(filename)
continue
try:
files[info.artist].append((info, filename))
except KeyError:
files[info.artist] = [(info, filename)]
return files, errors
def extraRandom((musicByArtist, errors)):
""" Produce a list of files with maximum gaps between artists. """
# Do some shuffling first.
musicByArtist = dict(musicByArtist)
for stuff in musicByArtist.values():
random.shuffle(stuff)
data = musicByArtist.items()
data.sort(key=lambda x: len(x[1]), reverse=True)
# Total number of tracks.
total = sum(len(x) for x in musicByArtist.itervalues())
# Current position in list of each artist.
positions = dict(izip(musicByArtist.iterkeys(), repeat(0)))
randList = []
while len(randList) < total:
artist, tracks = data[0]
randList.append((artist, tracks[positions[artist]]))
jump = total / len(tracks)
del data[0]
positions[artist] += 1
if positions[artist] < len(tracks):
data[jump:jump] = [(artist, tracks)]
return randList, errors
def copy(source, dest):
f = file(dest, 'wb')
f.write(file(source, 'rb').read())
f.close()
def procFiles(inDir, outDir):
""" Take files from structure in inDir, randomize, produce flat list of
numbered tracks in outDir. """
randList, errors =
extraRandom(getMusicByArtist(addInfo(getMusic(getFiles(inDir)))))
files = [x[1] for x in randList]
precision = int(ceil(log(len(files), 10)))
for i, (info, fn) in enumerate(files):
ext = os.path.splitext(fn)[1]
name = '%0*d. %s - %s%s' % (precision, i, info.artist, info.title, ext)
for c in '?*\'"':
name = name.replace(c, '')
fullname = os.path.join(outDir, name)
copy(fn, fullname)
if __name__ == '__main__':
import sys
procFiles(*sys.argv[1:])
_______________________________________________
Tutor maillist - Tutor@python.org
http://mail.python.org/mailman/listinfo/tutor
