Wednesday, April 23, 2008 3:46:35 AM UTC

If you aren't already in the know, these ten problems are from the 2008 Winter Scripting games.

For each problem, I'm going to quickly sum up the interesting (interesting TO ME) bits of each problem, then I'm going to post the full source.

Event 8: Making Beautiful Music

In this problem, we are asked to generate a random playlist for our CDs. I'll just say: I cheated. If you look carefully, you'll notice I sorted the songs from longest to shortest, making the "song packing" algorithm more likely to succeed. But it's not perfect and can fail.

So, in summary, I solved the problem like everyone else, but probably not well enough.

Source

#PROBLEM #8 
$filename = "C:\Scripts\songlist.csv" 
$global:nextId = 0 
$minimumSecondsPerCd = (75 * 60) 
$maximumSecondsPerCd = (80 * 60) 
$maximumSongsPerArtistOnPlaylist = 2 


function Create-SongObject ($artist, $title, $durationString) 
{ 
    $o = new-object PSObject 


    Add-Member -inputObject $o -memberType NoteProperty -name "Artist" -value $artist 
    Add-Member -inputObject $o -memberType NoteProperty -name "Title" -value $title 
    Add-Member -inputObject $o -memberType NoteProperty -name "Duration" -value $durationString 


    Add-Member -inputObject $o -memberType ScriptProperty -name "GetSeconds" -value { Get-DurationInSeconds $this.Duration } 


    Add-Member -inputObject $o -memberType NoteProperty -name "Id" -value $nextId 
    $global:nextId++ 


    Add-Member -inputObject $o -memberType ScriptProperty -name "PrintDetails" -value { "$($this.Artist)`t$($this.Title)`t$($this.Duration)"} 
    
    $o 
} 


#POSTSCRIPT-OOPS: I forgot the TimeSpan class! Argh! Instead of 
#using TimeSpan, I implement it again here below! 
function Get-DurationInSeconds ($durationString) 
{ 
    $column = $durationString.Split(":") 
    $minutes = [int]$column[0] 
    $seconds = [int]$column[1] 
    
    $minutes * 60 + $seconds 
} 


function Get-AvailableSongs 
{ 
    foreach ($line in (cat $filename) ) 
    { 
        $column = $line.Split(",") 
        Create-SongObject -artist $column[0] -title $column[1] -durationString $column[2] 
    } 
} 


function Sum-PlaylistTime ($playlist) 
{ 
    #initialize to 0 in case of empty playlist 
    $totalSeconds = 0 
    
    foreach ($song in $playlist) 
    { 
        $totalSeconds += $song.GetSeconds 
    } 
    
    $totalSeconds 
} 


#POSTSCRIPT-OOPS: ok, well, this isn't an oops moment 
#necessarily. But I do apologize for the THIRTY ONE 
#CHARACTER variable name used below. 31! 
function Has-PlaylistReachedArtistSongLimit ($artist, $playlist) 
{ 
    $playlistArtistSongCount = $playlist | group Artist | ? { $_.Name -eq $artist } | % { $_.Count } 
    
    $maximumSongsPerArtistOnPlaylist -le $playlistArtistSongCount 
} 


function Add-NextEligibleSong ($catalog, $existingPlaylist) 
{ 
    $existingPlaylistIds = $existingPlaylist | % { $_.Id } 
    
    foreach ($candidateSong in $catalog) 
    { 
        if ($existingPlaylistIds -contains $candidateSong.Id) 
        { 
            continue 
        } 
        
        if ( Has-PlaylistReachedArtistSongLimit -artist $candidateSong.Artist -playlist $existingPlaylist ) 
        { 
            continue 
        } 
        
        #I should handle the possibility of building a playlist in a combinatorial manner, i.e. 
        #I should be attempting to remove songs to make room for others if necessary. 
        #this would be the spot for it (would require some restructuring in how I add/remove songs from the list) 
        if ( ((Sum-PlaylistTime $existingPlaylist) + $candidateSong.Seconds) -gt $maximumSecondsPerCd) 
        { 
            continue 
        } 


        return $candidateSong 
    } 
    
    Throw "No candidate songs remain." 
} 


function Solve-Problem8 
{ 
    $songs = Get-AvailableSongs | sort GetSeconds -desc 
    
    $myPlaylist = @() 
    
    while ((Sum-PlaylistTime $myPlaylist) -lt $minimumSecondsPerCd ) 
    { 
        $myPlaylist += Add-NextEligibleSong -catalog $songs -existingPlaylist $myPlaylist 
    } 
    
    foreach ($song in $myPlaylist) 
    { 
        Write-Host $song.PrintDetails 
    } 
    
    $totalSeconds = Sum-PlaylistTime $myPlaylist 
    $totalMusicMinutes = [int]([Math]::Floor($totalSeconds / 60)) 
    $totalRemainingSeconds = $totalSeconds % 60 
    $totalMusicTime = "$($totalMusicMinutes):$($totalRemainingSeconds)" 
    
    Write-Host "`nTotal music time: $totalMusicTime" 
} 




Solve-Problem8 

2008 Winter Scripting Game Events: Index

Categories: PowerShell

Technorati: PowerShell

Wednesday, April 23, 2008 3:46:35 AM UTC

| Comments [0] | Trackback Tracked by:
"2008 Winter Scripting Games Event 8" (Peter Seale's weblog) [Trackback]
"2008 Winter Scripting Games Event 9" (Peter Seale's weblog) [Trackback]
"2008 Winter Scripting Games Event 10" (Peter Seale's weblog) [Trackback]
"2008 Winter Scripting Games: Recap" (Peter Seale's weblog) [Trackback]

Name
E-mail
Home page

	Remember Me
Comment (Some html is allowed: `a@href@title, b, blockquote@cite, em, i, strike, strong, sub, sup, u`) where the @ means "attribute." For example, you can use <a href="" title=""> or <blockquote cite="Scott">.
Enter the code shown (prevents robots):
Live Comment Preview

Syndication

Posts on this page

Peter Seale's weblog

Opinionated SharePoint | the Joys of PowerShell | Awesomeness

Event 8: Making Beautiful Music

Source

2008 Winter Scripting Game Events: Index