From: Frank Fischer <frank-fischer@...>
Date: 2009-05-19T00:40:09+09:00
Subject: Re: [QUIZ] Encyclopedia Construction (#205)

Hi,

here's my solution.  It's based on classic dynamic programming over the
number of words for each letter.  

I used different objective functions to get good book sizes:

  1. Maximize the minimal number of words in one book,
  2. minimize the maximal number of words in one book,
  3. minimize the absolute deviation of the number of words in one 
     book to the average number of words in one book ,
  4. minimize the quadratic deviation of the number of words in one
     book to the average number of words in one book.

For the given word list, objective function 4 seems to yield the best
results with good distributed word counts.

The program is called with three arguments:

  1. The name of the word-list file (one word per line), 
  2. the number of books in which the words should be distributed,
  3. a number 1,2,3 or 4 selecting the objective function.

The programm prints 

  1. the number of words per letter,
  2. the words per book,
  3. the number of words per book.

The current implementation is quite inelegant and could be improved
and be more rubyish.


---
require 'facets/enumerable'
require 'enumerator'
require 'pp'

word_file = ARGV.shift      || "words.txt"
nbooks = ARGV.shift.to_i    || 10
algorithm = ARGV.shift.to_i || 3

# ruby 1.8
class Integer
    def ord; self; end
end


class Wordlist

    attr_reader :books

    def initialize( words )
        # sort them
        @words = words.sort {|w1, w2| w1.downcase <=> w2.downcase }
        
        # get number of words per letter
        @nletters = Array.new(26, 0)
        @words.each do |w|
            @nletters[w.downcase[0].ord - ?a.ord] += 1
        end

    end

    
    # Returns the number of words per character
    def letter_counts
        (?A .. ?Z).mash{|c| [c.chr, @nletters[c.ord - ?A.ord]]}
    end

    
    # Returns number of words in each book
    def counts
        @books.mash{|range, words| [range, words.size]}
    end

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

    
    # divide into +nbooks+ books by maximizing the minmal number
    # of words in one book
    def max_minimum( nbooks )
        dyn_min( nbooks ) { |*s| -s.min }
    end


    # divide into +nbooks+ books by minimizing the deviation from the
    # average number of words in one book
    def min_deviat( nbooks )
        mean = sum( 0...@nletters.size ).to_f / nbooks
        dyn_min( nbooks ) { |*s| s.inject(0){|sum,x| sum + (x - mean).abs} }
    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| s.inject(0){|sum,x| sum + (x - mean) ** 2 } }
    end

private

    # computes
    #   sum_{i\in range} @nletters[i]
    def sum( range )
        range.inject(0) {|s,i| @nletters[i] + s}
    end

    
    # A range of letters in the same book.
    class Book
        def initialize( range, n_words )
            @range = range
            @n_words = n_words
        end

        # The first letter in this book
        def min; @range.min; end

        # The last letter in this book
        def max; @range.max; end

        # Is letter x in this book?
        def include?(x); @range.include?(x); end

        # returns the number of all words in this book
        attr_reader :n_words
    end


    # Computes a solution where
    #   max{ func(part_sum) }
    # is minimized
    def dyn_min( nbooks, &func )
        mean = sum( 0...@nletters.size ).to_f / nbooks
        
        books = Array.new( @nletters.size )
        s = 0
        (@nletters.size - 1).downto(0) do |i|
            s += @nletters[i]
            range = i ... @nletters.size
            books[i] = [Book.new( range, sum(range) )]
        end

        nbooks.times do 

            new_books = Array.new( @nletters.size )
            
            for s in 0 ... @nletters.size
                best_value = nil
                best_end = nil
                sum = @nletters[s] # value of the current part
                for e in (s + 1) ... @nletters.size
                    # stop if no further subdivisions are possible
                    break unless books[e]
                    
                    value = func.call(sum, *books[e].map{|r| r.n_words})
                    if best_value.nil? || value < best_value
                        best_value = value
                        best_end = e
                    end
                    
                    sum += @nletters[e] || 0
                end

                if best_value
                    new_books[s] = [Book.new(s ... best_end, 
		                             sum(s ... best_end))] + 
				    books[best_end]
                end
            end

            books = new_books
        end

        @books = Hash.new 
        books[0].each do |book|
            words = @words.find_all{|w| 
	        book.include?(w.downcase[0].ord - ?a.ord)
	    }
            if book.min == book.max
	        key = (?A.ord + book.min).chr
            else
	        key = "#{(?A.ord + book.min).chr}-#{(?A.ord + book.max).chr}"
            end
            @books[key] = words
        end

        @books
    end
end

# read word list
words = []
File.open( word_file, "r" ) do |f|
    f.each_line do |line|
        line.strip!
        words << line unless line.empty?
    end
end



list = Wordlist.new( words )
p list.letter_counts

case algorithm
when 1
    list.min_maximum( nbooks )
when 2
    list.max_minimum( nbooks )
when 3
    list.min_deviat( nbooks )
when 4
    list.min_deviat2( nbooks )
else
    raise "Unknown algorithm: #{algorithm} (should be in {0,1,2,3})"
end

pp list.books
p list.counts
---

Bye,
Frank