StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>Here's a problem inspired by <a href="http://www.cs.chalmers.se/~rjmh/Papers/whyfp.html" rel="noreferrer">Why Functional Programming Matters</a> by John Hughes: find the most efficient way to archive digitized record albums onto DVD:</p> <p>The problem is as follows:</p> <ul> <li>I want to archive my music collection on DVD. An album takes up 300–600MB, but a DVD holds 4,700,000B. I want to pack as many albums as possible into a DVD. <p> If two different packings use the same number of DVDs, I prefer the one that leaves the most amount of free space on the least full DVD, so that all the other DVDs are as full as possible. <li>The problem is NP-hard, but basic step is to use the standard greedy hueristic: <ol> <li>Sort the albums into a list, largest one first. <li>Start with an infinite list of empty DVDs. <li><pre> repeat take the first album from the list put the album in the first DVD that has room for it until there are no more albums on the list </pre> Burn all the nonempty DVDs. </ol> </ul> <p>Please solve these programming problems:</p> <ol start="8"> <li>Implement the standard greedy algorithm by writing a function <pre> pack :: [(Album, Integer)] -> [DVD] </pre> where <pre> type Album = String type DVD = [Album] </pre> Decompose your solution into separate functions as described by Hughes. <li>The result of a packing is a pure function of the order in which albums appear on the list. You can <em>improve</em> a packing by using <em>bubble search</em>: take the sorted list producing a new list using this algorithm: <pre> repeat probabilistically choose an item from the old list remove that item from the old list and place it at the end of the new list until the old list is empty </pre> Then you do the greedy packing algorithm on the perturbed list. If the packing improves, the new ordering then becomes the basis for further perturbations. <p> The probabilistic choice is parameterized by a probability <i>p</i>: <ul> <li>Choose the first item with probability <i>p</i> <li>Choose the second item with probability <i>p×(1-p)</i> <li>Choose the <i>i</i>th item with probability <i>p×(1-p)^i-1</i> <li>Choose the last item (in a list of length <i>n</i>) with probability <i>(1-p)^n-1</i> </ul> <p> The problem is to <em>implement packing by Bubble Search</em> <p> Your function can take as an argument need an infinite list of random numbers. </ol> <p>With <i>p=0.45</i> and 10,000 iterations bubble search can consistently produce packings of DVDs that are over 99.5% full. <p> Hints:</p> <ul> <li>Reuse as many of Hughes's combinators as possible. <li>You'll need to plumb through an infinite list of random numbers. Write new higher-order functions to help you do so. </ul>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload