[QUIZ][SUMMARY] Encyclopedia Construction (#205)

There were three submitted solutions to this week's quiz. Srijayanth
Sridhar provided the following:

    #! /usr/bin/ruby

    require 'pp'

    words=File.readlines("../words.txt").map { |word| word.chomp.capitalize }
    dict = {}
    words.each do |word|
       dict[word[0..0]] ||= []
       dict[word[0..0]] << word
    end

    count=0
    sub_array = []
    main_dict =  {}
    dict.keys.sort.each do |alphawords|
       sub_array += dict[alphawords]
       count += sub_array.flatten.size
       if ( count >= 10 )
          alpha=sub_array.flatten.map { |x| x[0..0] }.uniq
          alpha.size > 1 ? key=Range.new(alpha.min,alpha.max) : alpha[0]
          main_dict[key] = sub_array.flatten
          count = 0
          sub_array=[]
       end
    end

    # Attach last remaining words
    alpha=sub_array.flatten.map { |x| x[0..0] }.uniq
    alpha.size > 1 ? key=Range.new(alpha.min,alpha.max) : alpha[0]
    main_dict[key] = sub_array.flatten
    count = 0
    sub_array=[]

    pp main_dict

Srijayanth's solution works by building a dictionary of all the words
grouped by first letter. Starting from the beginning the words in the
next letter are added until the total number of words in the current
volume is greater than or equal to `count` (10 by default).

The advantage of this solution is that it is simple to implement and
only needs to make one pass through the lists of words. One potential
weakness is that if the words in the second to last letter added and
it goes above the threshold, then the words beginning with the last
letter won't have any possibility to be merged in and could be left as
a very small volume.

Luke Cowell's solution repeatedly merges the smallest adjacent pairs
until the requested number of volumes is reached. This is a simpler
technique and produces pretty good results as long as the input data
is well behaved.

Frank Fischer's solution uses dynamic programming[1]. Dynamic
programming is a method of solving complex problems by breaking them
down into simpler steps. There are two key attributes that a problem
must have in order for dynamic programming to be applicable: optimal
substructure and overlapping subproblems. Optimal substructure means
that the solution to a given optimization problem can be obtained by
the combination of optimal solutions to its subproblems. Overlapping
subproblems means that the space of subproblems must be small, that
is, any recursive algorithm solving the problem should solve the same
subproblems over and over, rather than generating new subproblems.

Frank's solution provides different methods to optimize the
arrangement of the volumes.

    # divide into +nbooks+ books by minimizing the maximal number
    # of words in one book
    def min_maximum( nbooks )
        dyn_min( nbooks ) { |s, rest| [s, rest || 0].max }
    end

    #...

    # divide into +nbooks+ books by minimizing the quadratic deviation
    # from the average number of words in one book
    def min_deviat2( nbooks )
        mean = sum( 0 ... @nletters.size ).to_f / nbooks
        dyn_min( nbooks ) { |s, rest| (rest || 0) + (s - mean) ** 2 }
    end

Each of these methods passes a different block to the `dyn_min` method
depending on what objective you wish to optimize. The `dyn_min` method
iterates through the possible solutions and stores the best
combinations of volumes according to the metric passed in.

Thank you Srijayanth, Frank, and Luke for your contributions this week.

P.S. From now on the summaries will have an attached archive of the
quiz solutions.

[1]: http://en.wikipedia.org/wiki/Dynamic_programming