Forum: Ruby B & E (#72)

Announcement (2017-05-07): is now read-only since I unfortunately do not have the time to support and maintain the forum any more. Please see and for other Rails- und Ruby-related community platforms.
4299e35bacef054df40583da2d51edea?d=identicon&s=25 James Gray (bbazzarrakk)
on 2006-03-30 18:46
(Received via mailing list)
This quiz turned out to be surprisingly tough.  Ross Bamford seemed to
get the
tighter solution and it's not as big a difference as you might think.
some output from running Ross's solution:

	 ### 4 digits, [1,2,3] stops ###
	      user     system      total        real
	seq.     1.000000   0.020000   1.020000 (  1.021674)
	Search space exhausted.
	Tested 10000 of 10000 codes in 50000 keystrokes.
	6146 codes were tested more than once.

	seq/chk  0.790000   0.000000   0.790000 (  0.804365)
	Search space exhausted.
	Tested 10000 of 10000 codes in 33395 keystrokes.
	2557 codes were tested more than once.

	simple   2.840000   0.040000   2.880000 (  2.930310)
	Search space exhausted.
	Tested 10000 of 10000 codes in 33830 keystrokes.
	2721 codes were tested more than once.

	best   665.050000   5.390000 670.440000 (678.840230)
	Search space exhausted.
	Tested 10000 of 10000 codes in 28687 keystrokes.
	464 codes were tested more than once.

Compare that with the trivial tests in the quiz code:

	Search space exhausted.
	Tested 10000 of 10000 codes in 33635 keystrokes.
	2664 codes were tested more than once.

At "best", Ross managed to trim 4,948 keystrokes and there was a hefty
penalty to pay for getting that far.

Let's work through the code that amounts to the "best" search.  First we
need to
examine a helper class it makes use of:

	# This was originally a delegator, but that was *slow*
	class PoolStr < String
	  def initialize(obj, parent = nil)
	    @parent = parent
	  def suffixes(maxlen = nil)
	    @suffixes ||= get_suffixes(maxlen).map do |s|,self)
	  def prefixes(maxlen = nil)
	    @prefixes ||= get_suffixes(maxlen,reverse).map do |s|,self)
	  def get_suffixes(maxlen = nil, str = self)
	    start = maxlen ? str.length-maxlen : 1
	    (start..(str.length-1)).map do |i|
	      suf = str[i..-1]

There's nothing too tricky hiding in here.  Basically we have a String,
that can
give us an Array of suffixes or prefixes as needed.  Those are both
found with
some simple index work in get_suffixes().  To handle prefixes, the
String is
reversed before it goes in, and the suffixes are reversed as they come
out to
transform them into prefixes.  Note that both of these are cached the
first time
they are figured, to speed up future calls.  (I'm not sure what @parent
is for
here.  It doesn't seem to be used.)

Next we need to look at one more short helper, which turns out to be the
of the "seq." search from the results:

	# Make our codes. Using random stop digits gives a more
	# compressible string (less stop digits = longer string).
	def mkpool(digits, stops)
	  (("0"*digits)..("9"*digits)).inject([]) do |ary,e|
	    ary <<"#{e}#{stops[rand(stops.length)] if stops}",

Again, nothing tricky here.  Assuming a parameter of 4 for digits, this
an Array of the codes from "0000" to "9999", with a random stop digit at
the end
of each one.

Now we are ready for the main method of the "best" search:

	# A more involved way, a simplified greedy heuristic
	# that takes _forever_ but gives (slightly) better results.
	def best_code(digits, stops = [1,2,3])
	  out = ""
	  pool = mkpool(digits, stops)
	  best = []
	  bestcode = nil

	  # Keep going until it's empty - if ever we can't find a match
	  # we'll just take one at random.
	  until pool.empty?
	    unless bestcode
	      # first iteration, just grab a start and carry on
	      bestscore = 0
	      bestcode = pool[rand(pool.length)]
	      # Get the array of arrays of best matches for the previous code.
	      # This array matches suffixes to best-fit prefixes for
	      # the previously-added code to find the most mergeable code
	      # (i.e. the one that shares most of it's prefix with the end
	      # of the output string).
	      # This contains at a given index all the codes that share that
	      # many letters of pre/suffix with 'need'. Eh? Well, it's like
	      #   best for "1234" => [ nil, ["4321", "4048"], ["3412"],
	      # Then, (one of) the highest scoring code(s) is taken from
	      # the top of the last nested array, best[best.length-1].
	      # We do it this way, rather than reversing the array, because
	      # we need to know what the actual score was, to merge the
	      # strings. Running on each iteration helps a bit
	      # with performance, since as time goes on the number of
	      # elements decreases.
	      pool.each do |nxt|
	        next if nxt == bestcode
	        if r = (bestcode.suffixes & nxt.prefixes).first
	          (best[r.length] ||= []) << nxt

	      bestcode = (best[bestscore = best.length - 1] ||

	      # No best code? Nothing with matching pre/suff, so let's just
	      # a code at random instead to keep things moving.
	      unless bestcode
	        bestscore = 0
	        bestcode = pool[rand(pool.length)]

	    # Remove from the pool. Bit slow...
	    pool[pool.index(bestcode),1] = nil

	    # Chop off matched prefix from this code and append it
	    merged = bestcode[bestscore..-1]
	    out << merged

Here's the beast, but the comments are good and they will get us through
First you can see that the method makes a pool of all the codes, using
mkpool() method we just examined.  Now anytime this method doesn't have
bestcode, like right at the beginning here, it just pulls one at random
from the
pool.  (You can see the code for this in the first unless clause and at
the end
of the big else clause.)

The real work is done right after that big comment.  The pool is walked
comparing prefixes of possible codes with the suffixes of the bestcode
(our last
find).  The matching groups are placed in an Array where the index is
score or how many digits they share.  The code then just chooses a match
the highest score so it shares the most possible digits.  (The
constant used here is defined elsewhere in the code as `EMPTYARRAY =

From there the code merges the suffix of the selected code (we already
have the
matching prefix from the last code), and adds it to the digits to enter.
then loops until the pool is exhausted.

The actual solution is just one line from that:

	best_code(n).split(//).each { |c| c.to_i }

You saw the results of that at the beginning of this summary.  You would
have to
examine usage for this code carefully though, to determine if shaving
5,000 keystrokes is worth the unfortunately large speed penalty.  It's
all about

A huge thank you to the quiz creator for a challenging little problem
and the
two brave souls who were equal to the task.

Tomorrow's quiz is still up in the air!  We're trying to sneak in a
project we can all help with, if we can get it ready in time...
A9b6a93b860020caf9d2d1d58c32478f?d=identicon&s=25 Ross Bamford (Guest)
on 2006-03-31 09:07
(Received via mailing list)
On Fri, 2006-03-31 at 01:43 +0900, Ruby Quiz wrote:
> This quiz turned out to be surprisingly tough.  Ross Bamford seemed to get the
> tighter solution and it's not as big a difference as you might think.

Thanks both James and Stephen for a good quiz, this one really got me
thinking :) I knew my solution was slow, and at least I can now prove it
- check out Timothy Bennett's solution (which I think just missed the
summary, unfortunately) - it kicks my solution's ass on performance and
comes up with similar (even slightly shorter) codes. Good work, Tim!
4299e35bacef054df40583da2d51edea?d=identicon&s=25 James Gray (bbazzarrakk)
on 2006-03-31 15:55
(Received via mailing list)
On Mar 31, 2006, at 1:05 AM, Ross Bamford wrote:

> check out Timothy Bennett's solution (which I think just missed the
> summary, unfortunately)

Yes, I was done with the summary when this came in.  :(  It is very
nice though.

James Edward Gray II
280b41a88665fd8c699e83a9a25ef949?d=identicon&s=25 Stephen Waits (Guest)
on 2006-03-31 18:25
(Received via mailing list)
On Mar 31, 2006, at 5:54 AM, James Edward Gray II wrote:

> It is very nice though.

Indeed, as were all of the solutions.  Thanks everyone for

This topic is locked and can not be replied to.