From: Daniel Moore <yahivin@...>
Date: 2009-05-25T03:31:34+09:00
Subject: [QUIZ][SUMMARY] Encyclopedia Construction (#205)

--001636c92ea8506ec1046aac97ce
Content-Type: text/plain; charset=ISO-8859-1
Content-Transfer-Encoding: 7bit

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

--001636c92ea8506ec1046aac97ce
Content-Type: application/x-gzip; name="205.tar.gz"
Content-Disposition: attachment; filename="205.tar.gz"
Content-Transfer-Encoding: base64
X-Attachment-Id: f_fv42djtj0

H4sICE+NGUoAAzIwNS50YXIA7Vt7bxs5ks/f/SlqHMxFWisdSX4FSTTJzNzMYYHDLJDZncNBK2go
NSUx7tc0uy0rtr/7/YpkvyQ5sXNJBot1B7G6yWKxqlisKlZ3Dfsnzx594auP6+zkhH8HZyf95m95
PRoMhv3T/tHp0dnpo/6gf3o8fEQnX5owvgqdi4zoUSBiJcPb4T7W/y96DbH+6yQLtJ9f5l9oDl7g
0+Pj29Z/cDI4rdZ/MDzC+g9PjrD+/S9ET+v6N19/kUpPpGnIfzM1T3JP/FGISGQqRlM2X6lcztGY
5Wq+Ss7R9r7IpDcTsySJ8RMsZYafGP/wk/P/PJR6pVJvJqVei0v+5SZvFor5Of4mSzMmLIAGU56H
YoPnHzK1FAEjnYsswJ/cm69klm08M+/M3ibzJC7Qk2Qi9OaZijQPKLJMxLkXiMgLJCiQ+AkVhohc
JbHGUySWyRITBsnSC4pMidiToUxXPExGqchXG0/G8808TFIZKOEt1NJbJJfeUryXIaSzVJlYLPCb
hIGMsyTwlpnYeOAzTdIkF1GhvVUBZhylmP3SUxFkihlUHKhl4qmLBD3vxAz/5+eZmM1UjlsI9Xwl
zpV3rtb4UwTvCy8UFzIOIJZQRpGKl/hNUpZLqCLpQYQitvNEIgZmrBdLLpIRzxAlIDhK4nPJ94XG
Q6HPwcwvCpIHc7+IC/Eu8ZJQXUgPDGfCSyEJiBu/Wb7xUinmK/6LBhkvCxXjN9MqAlYvDYvISxOZ
40+ooBcsTTB6gXFZArFEERA59jIZ4L+WrEpetlJx4r0tolSGOldhrs+BWYuQ0WoVXmCcjpO1pyFl
xQ9JvNSRylee/qNQWSZDj7erUS+dS/OYibUVhc4LLE3u5SAnF6nKPHAEZTC/WhQZlijPpPTyIvuj
SBTkUkQz4AyFtwbbK+jGmuHDJPHWCuvMGpx76yRc4E8SzHmBvcsNdGSVYHtsxAqQGyAAye/lLBN/
9m6+/8X2XxcRFGjzxTzAR+z/6dnw2Nr/I/b7Q9j/o0F/8GD/v8b1d2x6SWv+k6+wOUgXM2y4XAaE
TVgY+0l5gk6lASbPn2jCVnzv06+Zeic2bDb4NlhBitj+FyrAUGw4WiS8L2C7Xnge4Xr8DT0rdPZs
puJnWTHb2NZM8saW9CRNn9gWE42Mflah9DMpghCOSHcOfL8OUw66fiRSuqJrbro2I3x4iSj159j3
uQjVe0k3Blug5jmN6Oqmxu2zcaMgccNNh4Mcc8u47/v9yYSur0c0ntza/eqVQWf6Yast8fOkiPNR
39xDklMBz7ShCk8kVDx1JJU08aMPU619nWR5TZwI4Z4MwRWJNcbDkSWoBqoINSQwQAXtL0J4ZRn7
GnIpwdSCOg72uxEN+tQte3AZtKNdBE7sl9d0acVAN34Rqz+2h5qZ6Dsa0GsCa6O38FLSj+W6Y7vh
0nruTlx26YUdNe5PGogqWY2BYUJ7+GkAW0ZG1G+0VfCjehV5oZq/VjPp+zxnsYdC59BInhl6a7XF
+2R5fAZJ3FEGbe5bfJuWNK0xWbbrzYv9XG50Zvhc02xDswLuj0UgjJqhD/6BkgWoC83mNqKhZZYU
CJd4xEJlkF0oQVMG25BzwIjxiyyJzICZXKrYSLUermLzEMvLciQJmAIRsAkBR8rOlSO8CimGrwYA
aGgN5tgPTp8uwEMkSTFRxumjV8SUZAQDg+EwYb8bMf1OHSg7KA7kQhRh3vU9D0YQs15AHGIpeQpj
7Sqx4B7IclI53yIKQrjMCM1NxLOLOKAkDjfgRQbGXkYI69AkKRWah0NSy5WhOFQ61xUfPv2NgRIs
Za5A51qKcxg8XU+62JWYlgiDA57GaGwpOyM3JgWELhOpCUH6hbQyhG3XK0RVPX6MGyjrhVkjzrIU
NpCuk/hJTiuEo8C8AaFaq5lC2Lfh6WeSEOstMS0o45kh4jDg5lAuIBaQQAjqNqQj1hy7SBD4fxeQ
zo/JGqFTU/8ymfLaBRCkQasttzwWgRgYRNzM4k4FtK2hIexEAAAyai2xcxk5ZmxTZeDT33lZFRNl
FxFKIucr7NdCGurhv4JijkFpBu43EGISYLSGmmhmJkx4S1iqVJwWOQUiF2Q8I9ibSZZTAP5+xnnk
nH5Wmo8wTQ4RjGsaB5tYRGpOZbgM6U/Gg4lP/7nbYemNJMLTgPkCqgtunifMwSWDzqCFdtuC03O3
xyI4kTV0N8YyldxCRKlmMbC7562WrxO2SgRTkqlZkUundKJESzg5uOVXvJtwJIFjz2gPB04f+DCp
5gKDX1CS5gqLxxYJcXoxR+BtBQ21zEJA8jB0ljxgM+wbEUkRO8KMPpTCxISCljjDxHYm9d6c9yra
5zAAoCiZ5TB+1kwZk5FEiEEsKARaEdkMdxQWvE3Yfop3aEuhoWaZmjAsw5lT5J7b1rpnNlQmYcG0
4u0VLpMMWzCqlpgRlrxg8/LO4i67o7WIZGsWlmkl3B7h7LsqreBSxuYsDJzwPC3GnK42ddRFcRqm
HydeY12t+hnJOElbItjNwJ8ZG5hYQ+X2ne+CPiBhZFYPD+NZkpzrQzI/vB5QHMZWcgsfaNbCbmOH
oWny2aLyYBs5yQUjmJpRRdQhi74RyUBNp4Coe9hbQ/LY0/k1jd0dIj3qT9gBu6CxHR34vt+MFe7F
EHxPwJKfg9gLZXTOoak8I/ZWxm5nj4Pby61FNNzDLeuiiREgij6BbHoTWzOubRjS9fNkuqBnbugd
xdSpZNSlQ+poempm6tJf/kLDbYn9xHGUVQUtK71hJ8j+qKFSszCZn9uThaTfHQW/l4YugCeITQTC
YQlvmGT2TiISgfZvkgK+Sq+a2miM2i4albPey7YDtj4slI0dz9tG50nmPM6MGW6YCd10KGI+x/o4
g2eUVsJ4zi2P7AhNQMH2nwmtA60emZ3WM5MZB8iGFDAZpoqt/bXmpzxqARG8wgta5Xn64tkzxJtr
da5MfspPsuUzfnrmXMa0YYnvc/7j83/LW32BtwH3yP8PzvpnfP4fHvcf8v9f4+L1b0RjX+Rd0D3W
/2R4yus/PDs+fVj/r3Hx+u9mcj6vGtxn/c/O+P3P8dHR0cP6f41r1/6XXtHPZp9pjg/nfwcD7nP5
3xMDNzg5Pjl6yP9+javKv3JKFpG8fuJVTQucZXKNuANxT8Ynukafa0TM1Gg0OVyOXqcLhfhqRN+/
/a/ffL1Si9wGmggi25lcz0WcI+o0YAH23MSqyqtPRTsgxw7Ee0xMPA38555a0Nt//PC/099+evvr
X//2y7jfO57QaEQH6PQPbLIs5IzMX+NcLt0Ro4yuQdVL0jJcvGzlCU1yF5N8b2JxE6y5BGGdRdFl
wsskUUSZPUEMbxNjiMU5q+LZyX/gmN7mCHHwnnKaG8AvDGiPXjAkfuKpwY07m4h0B4cfTX4Lcxhq
zHyxo2K9ShB0N1NxnD0AEeaU5lfHCFDPySbEzR3b1SM3WeM08cb0QOx2MAJLBJ0Bc+IaxKVf5r8N
fIliVCJrp8Yd+b/KfDuhBRpbpxz7BqBDOxSV+K3+LFQcTHGivrpeXwPRPCwC+bqz9jnvMRdajvuT
7s0+8iyeOhu+TeJbmRcZB+JZIdv5t/Yyc7tNPzSyl6o84O3yVdFYwm8L29+GMBJ/Sq+Fuem2qW0Q
ylkNuG0xx5inW4ttHquJwM6bakF5Z7ypVrOROifqvP7ezHnYAO/681W9Y2So5d2GoOXg6QGfHXcg
xOUW0sa+8yoWsM31Szp4xfvmBX17hD3Bi/eCHper+t0BfWs5fVkLyMpcpzg3vnQ4qnOqncBux/8B
Bs7K7tmS9py8d+Nsa+dj4vc3JvV2m8YaAKjroEfr4TWtB5Wu0qvRd2irn2vFbUywxN7ZThOkeLDK
0lB1d+pnC2xeFvD7Bhqe9qi/s50ab8OuW8tZYRm3tlRLJSf8nmmwf/X2bajVbpqD6a90txK0nXpq
MvZ1nqLT932/ndPgV4F6dXWtrmnccfvkkJTRql6DBzWZ3Oyl7V81P3UPHnj6Bg8qvicL4nJq5PAp
LDzFbZVAeqq7O2x8yjJUubQqi+awfFou7eul0m7Npflipj9tcf99842e+eiIv/ZyLPIrEX6H4R75
TWg0vVL/LAOgm5Y9qJg09Ntgp+at9MecdOyAkCvQBxvTRADi9P4l+9ERwi+ayqz61kLV6cxFEZs3
rLXH3hJPj/6DYVquZm6DQOePnDp0Buamhitj64YT2F6hCla33p53tuCe0qBrvECesDTYXai2u9Ds
Cnbk2xInZlB71KSNpoicSpkh3Van4YclP6LxmIMBy5MLYXlod9IzAvXnCAw7aEFkq8JuTUy1VIZL
p3+Gu1xxdhec7U7JZ499Cl59h6LbsjADocTTCxEWzDZo2A8Acm7ptoKoBaonWHaLz71pKV998yd7
O8M5t2ze2WnfvF//iNjLC+GhFbKc7O3nq2RqS87luPFg0r11LOOvBOOD79e80S3GV42uWxFUkiup
uCO4FfTtgGXoctd2Xp6WwsuJMVk7wC2FK6+WGPbib+i3xtqVPBgtb7V0uzBEt7Bll6SEnCB66+2H
rInZXfadOL+89mnttrhuWk87gWKr8U251yzZ/UnzeyC27mEIk9k6PLo3MG3vYvHUcS0/Xu9sar99
Gtwbw5q1e8zfDwRmSvPthlcOHE8885VaksrYHgdM2qNHB9kBWRu5sPMuDDFT/pTNNPNNTRE/+TrP
VPpN1WbnePXKdFIBLcM5xQDKKM03r7eSEx4TBpLKk4y1i+UJJTV0++2YGg5K08Ev7SAAJ6qrXVjf
aIauvSE7w8trNvl0eXNzgHMUH1mqVI235k9M7LHAYNsfBBuoYQNqb5xpoI7auHbCNgN0vA+oGbdU
mpwJBXoP/hGfx/yNREU4s1893CD0WJWfs8CQXg16w95R7/ime2Clnjq5WnWzxxCjazQ2CubcUq1s
OIHcY4g72WLQl8z/bb//+fzZ349+/3tydnxk878D/vCX8/8ng+OH+o+vcrVztzYf8lOzEGIrIeLe
grNL20qImBIR2KkeOjRQBlMHa6OBN+X78xH95j4RMV9BulEWyH31NaqgYYjiZb5ChLaFtAFeRW7O
elZjTXenejT5wvJjsil/Q1Yn1Co/7dJNK9NjR05X2Kf1N8QVvsrB2IbSoDcGjd0Hb7nKQ8lRq31u
zNoCb1MRFFF6pwln0N8RHRy05neCc7K5YhiEKwePD0qPbCpT0HDVpPHm+jGD3vwzPrhVNKJFlNf0
lL/V39zhZGi/VIZrsc1OuUqYV/ZUcrse2cVRi6qh1IXvcDBs8coKo9NQ5dPZZurisS00jSCmHlOC
tNZDF6nMOg3VbXD/kUlsd70P6izcGMcSyzgrvWflD/+UFNrhqraFb9L3rrWagHPZLj1ZSqP+UNy2
lOrQHG++Yf8A3lKOkHJr2DejbfoaB8UWlyZGsXzWAU3F9xbP+/luzuy1g7AaF6ZxU7ZX6wPENBZu
d+tb5YoDeVl/N93sn9rz16B/dnR2PHg+PNoFqQaa4M7iMgdjvruuJWt7mDJnyga1MB0e3lbZpmrl
VwdNKvh2bNBMyk1w2Gg8HJTN9SLt8MKa0MZrrmoECG13v9pF0jzXbYvCUHJbv+OjNcGew8D21/nb
K+ZW9LEx7DSsPwiujZHJWhm7nywWWuaVFbGP1TJUFmRb+hdjCzlpqW+nbj6sQHBbn3UDCc2TU4Sl
tvNwsO1dmjZy20RWpqhpJLdspLHQdrbFLebCPDiKwltg+O2iA+FPf9kpXC1uniLwvznYMncyXLTH
ckRqx9pKmAmn2f0i5fjfji1frVRbckTfwsun9sNg/muqTKmuMqWqypSqKlMyVaZkq0zJVpmSrTLF
T051lSm5KlNyVaZkqkzJVZkSV5lSXWVKVZUpcZUp/uRkq0yprjIlV2VKpsqUXJUpuSpTCkREtsqU
WlWmVFWZwgosyVaZUlllSq7KlJpVprBLS1okl+SqTMlVmVJVZUpcZUrNKlNqVJkSV5mSqzIlW2VK
psqU3okZ1VWmxFWmZKpMiatMyVSZUlllSq7KlFyVKXGVKdVVpmSqTMlWmZKtMiWuMiVbZUqmypRs
lSm5KlOyVaZkqkzJVJmSqzI1KasNmSpT/osGW2VKVZUpcZUpcZUp1VWmZKpMqa4yJcceAkMqq0zJ
VJnSVpUp2SpTslWmxFWm5KpMqaoypbLKlMoqUzJVplRXmZKrMqUc5JgqU3JVplRVmRJXmVJVZUpl
lSm5KlMqq0yprjIlrjKlqsqUqipTMlWmZKtMyVSZIhLgzFczTG/F0j163uXTqfRNJPvB+P+W778+
6zHwY/X/R6eu/n8wBDknOP+dnhz1H85/X+Parcrc/Zrn81Rj1pWYt1VhfqAC89bqS+NsyqrLrYrL
7WrLO1ZafrTK8g4VllvVlc+rFy2fWFn5Waoq71xRuV1NuV1JWUYz5N2bnf8nI3dgoSa+XQjZLIL8
s3fdw/VwPVwP18P1cD1cD9efd/0ft0mtSABQAAA=
--001636c92ea8506ec1046aac97ce--